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