Optimizing the Rule-Data Interface in a KMS.
Charles Kellogg, Anthony B. O'Hare, Larry Travis:
Optimizing the Rule-Data Interface in a KMS.
VLDB 1986: 42-51@inproceedings{DBLP:conf/vldb/KelloggOT86,
author = {Charles Kellogg and
Anthony B. O'Hare and
Larry Travis},
editor = {Wesley W. Chu and
Georges Gardarin and
Setsuo Ohsuga and
Yahiko Kambayashi},
title = {Optimizing the Rule-Data Interface in a KMS},
booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
August 25-28, 1986, Kyoto, Japan, Proceedings},
publisher = {Morgan Kaufmann},
year = {1986},
isbn = {0-934613-18-4},
pages = {42-51},
ee = {db/conf/vldb/KelloggOT86.html},
crossref = {DBLP:conf/vldb/86},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Work on integrating systems capable of drawing inferences from
knowledge bases containing large numbers of logical clauses with
relational database systems containing large numbers of facts is
described. The aim is to realize the derivational power of symbolic
logic while at the same time exploiting the set-processing capabilities
and potential parallelism of relational data base systems. We propose
that the interface between the deduction and database components
involve set-characterizing relational algebra programs
(RAPS) and sets of answer values, rather than proceeding sequentially
with single answer tuples being requested and returned from
the database system one by one. Our design includes a query compiler
that translales queries into RAPS, as well as a rule compiler
that compiles rules into an efficiently maintainable and incrementally
updateable predicate connection graph (PCG), a structure
whose use obviates open ended deductive search at query time.
When presented with a query, the system extracts from the PCG a
proof schema that represents all possible derivations of the query
from the relational database. Structure sharing within this proof
schema provides a basis for producing from the schema a
significantly optimized RAP. Direct manipulation of the RAP
expression enables further optimization, and the optimized program
is then evaluated against the database. The result is a set of all
possible answers to the query, produced with minimal search of the
database. Answers may then be combined with certain intermediate
results and proof schema information to generate explanations
describing how the answers were derived from the knowledge base.
We describe a prototype implementation of this proposed design and
report on preliminary empirical explorations. Some results of the
explorations are that, although the number of derivations
represented in a proof schema grows log exponentially with respect
to deductive complexity (in one example the number approaches
three million), RAP size appears to grow only linearly with deductive
complexity.
Copyright © 1986 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.):
VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings.
Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents BibTeX
References
- [BAN85]
- ...
- [BAN86]
- François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman:
Magic Sets and Other Strange Ways to Implement Logic Programs.
PODS 1986: 1-15 BibTeX
- [BIB82]
- ...
- [GMN84]
- Hervé Gallaire, Jack Minker, Jean-Marie Nicolas:
Logic and Databases: A Deductive Approach.
ACM Comput. Surv. 16(2): 153-185(1984) BibTeX
- [JACV84]
- Matthias Jarke, James Clifford, Yannis Vassiliou:
An Optimizing Prolog Front-End to a Relational Query System.
SIGMOD Conference 1984: 296-306 BibTeX
- [GRN69]
- ...
- [HAN86]
- ...
- [HENA84]
- Lawrence J. Henschen, Shamim A. Naqvi:
On compiling queries in recursive first-order databases.
J. ACM 31(1): 47-85(1984) BibTeX
- [KBZ86]
- ...
- [KETR81]
- Charles Kellogg, Larry Travis:
Reasoning with Data in a Deductively Augmented Data Management System.
Advances in Data Base Theory 1979: 261-295 BibTeX
- [KETR76]
- Charles Kellogg, Philip Klahr, Larry Travis:
A Deductive Capability for Data Management.
VLDB 1976: 181-196 BibTeX
- [KEL86]
- Charles Kellogg:
From Data Management to Knowledge Management.
IEEE Computer 19(1): 75-84(1986) BibTeX
- [KOW75]
- Robert A. Kowalski:
A Proof Procedure Using Connection Graphs.
J. ACM 22(4): 572-595(1975) BibTeX
- [KUYO82]
- ...
- [MKSH81]
- ...
- [REI78]
- Raymond Reiter:
Deductive Question-Answering on Relational Data Bases.
Logic and Data Bases 1977: 149-177 BibTeX
- [PRO75]
- ...
- [SIC76]
- ...
- [STI82]
- Mark E. Stickel:
A Nonclausal Connection-Graph Resolution Theorem-Proving Program.
AAAI 1982: 229-233 BibTeX
- [TZ86]
- Shalom Tsur, Carlo Zaniolo:
LDL: A Logic-Based Data Language.
VLDB 1986: 33-41 BibTeX
- [ULL85]
- Jeffrey D. Ullman:
Implementation of Logical Query Languages for Databases.
ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
- [ZAN85a]
- Carlo Zaniolo:
The Representation and Deductive Retrieval of Complex Objects.
VLDB 1985: 458-469 BibTeX
- [ZAN85b]
- Carlo Zaniolo:
Safety and Compilation of Non-recursive Horn Clauses.
Expert Database Conf. 1986: 237-252 BibTeX
Referenced by
- Arie Segev, J. Leon Zhao:
A Framework for Join Pattern Indexing in Intelligent Database Systems.
IEEE Trans. Knowl. Data Eng. 7(6): 941-947(1995)
- Amit P. Sheth, Anthony B. O'Hare:
The Architecture of BrAID: A System for Bridging AI/DB Systems.
ICDE 1991: 570-581
- Arie Segev, J. Leon Zhao:
Evaluation of Rule Processing Strategies In Expert Databases.
ICDE 1991: 404-412
- Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy, Shamim A. Naqvi, Shalom Tsur, Carlo Zaniolo:
The LDL System Prototype.
IEEE Trans. Knowl. Data Eng. 2(1): 76-90(1990)
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - Jiawei Han, Lawrence J. Henschen:
Handling Redundancy in the Processing of Recursive Database Queries.
SIGMOD Conference 1987: 73-81
- Shalom Tsur, Carlo Zaniolo:
LDL: A Logic-Based Data Language.
VLDB 1986: 33-41
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:28 2009