Optimizing the Rule-Data Interface in a KMS.

@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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

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

1. 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)
2. Amit P. Sheth, Anthony B. O'Hare: The Architecture of BrAID: A System for Bridging AI/DB Systems. ICDE 1991: 570-581
3. Arie Segev, J. Leon Zhao: Evaluation of Rule Processing Strategies In Expert Databases. ICDE 1991: 404-412
4. 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)
5. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
   Contents
6. Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81
7. Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41