ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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}
}

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BIB82]
...
[GMN84]
Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JACV84]
Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GRN69]
...
[HAN86]
...
[HENA84]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KBZ86]
...
[KETR81]
Charles Kellogg, Larry Travis: Reasoning with Data in a Deductively Augmented Data Management System. Advances in Data Base Theory 1979: 261-295 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KETR76]
Charles Kellogg, Philip Klahr, Larry Travis: A Deductive Capability for Data Management. VLDB 1976: 181-196 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KEL86]
Charles Kellogg: From Data Management to Knowledge Management. IEEE Computer 19(1): 75-84(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KOW75]
Robert A. Kowalski: A Proof Procedure Using Connection Graphs. J. ACM 22(4): 572-595(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KUYO82]
...
[MKSH81]
...
[REI78]
Raymond Reiter: Deductive Question-Answering on Relational Data Bases. Logic and Data Bases 1977: 149-177 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PRO75]
...
[SIC76]
...
[STI82]
Mark E. Stickel: A Nonclausal Connection-Graph Resolution Theorem-Proving Program. AAAI 1982: 229-233 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TZ86]
Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ULL85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ZAN85a]
Carlo Zaniolo: The Representation and Deductive Retrieval of Complex Objects. VLDB 1985: 458-469 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ZAN85b]
Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:58 2010 by Michael Ley (ley@uni-trier.de)