Optimizing the Rule-Data Interface in a KMS

Abstract

Work on integrating systems capable of drawing inferences from knowledge b,wes containing large numbers of logical clauses with relational datab,we 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 elliciently maintainable and incrementally updateable predicate connection graph (PCG), a structure whose use obviates open ended deductive search at query time. When prewnted with a query, the system extracts from the PCG a proof schema that represents all possible derivations of the query from the +af.ional database. Structure sharing within this proof schema provides a b,asis for producing from the schema a significantly optimized R.AP. Direct manipulation of the RAP expression enables fur&r optimization, and the optimized program is then evahmtcd a.gainst the database. The result is a set of all possible answers to the rluery, produced with minimal scar& of the database. Answers may then be combined with certain intermediate rem]Ls and proof schcmn inlormation to gencrate 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 or the explorations are lhat, 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), RN’ size appears to grow only linearly with deduc-