Evaluating Queries in Deductive Databases by Generating

1. INTRODUCTION AND MOTIVATION.

Recently deductive database systems have become an area of extensive research {Chang,1976,1978,1981, Gallaire,Minker and Nicolas, 1978, Henschen and Naqvi, 1982,1984, Kellogg, Klahr and Travis, 1978, Klahr,1978, Kowalski,1978, McKay and Shapiro,l981, Minker, 1975,1978, Minker and Nicolas,19B3, Naqvi and Henschen,1980, Naqvi,Fishman and Henschen,1982, Nicolas and Gallaire,l978, Nicolas and Yazdanian,l978, Reiter,1978, Shapiro and McKay,l980, Ullman,1984). Consider a database DB {relational database, in particu­ lar) consisting of a set of relations lRd. extensions of some relations fRd, and axioms l A; I in the form of Horn clauses. A relation presented explicitly by its extension is called base relation, while a relation defined by an axiom is a virtual relation. Base relations consti­ tute the extensional database (EDB ), axioms are con­ tained in the intentional database (!DB) . A query, q, is a formula {in a first order language), and answering q means finding a proof that q is implied by the T!:DB and !DB. Suppose a relation, R, is defined in terms of itself. If such a recursive definition of R is used in the course of a query processing this may lead to an infinite search for a proof. A number of elegant solutions to the prob­ lem of handling recursive axioms have been proposed (Chang, 1981, Henschen and Naqvi, 1982,1984, McKay and Shapiro, 1981, Minker and Nicolas, 1983, Naqvi and Hen­ schen, 1980, Reiter,1978, Shapiro and McKay, 1980, Ullman, 1984).

Most of known methods employ top-down goal­ driven deduction which may be drawn by recursive axioms into an infinite {or at least, too long) evaluation process. Another serious problem of goal-driven stra­ tegies is a fast growth of the search space because being not restricted enough by a specific information the search develops in many directions including the ones neither relevant to the query nor supported by the extensional database. On the other hand, it seems very natural to exploit the problem-specific information proconstants, all terms of P 1,P2 , . ..· Pr<-l are distinct vari­ ables, all variables are typed and universally quantified, so the quantifiers are dropped, and types are shown next to the corresponding terms. For instance,

Relations and axioms of a database can be represented by a system graph, SG, in the following way. Each axiom is represented by a single ax-node, and each relation by a single main rel-node . Let <R>,<A> denote the nodes of SG representing, respectively, a relation, R, and an axiom, A : P 1AP2 11 · · · II Pr II CE ..... PrH· Then the system graph contains arcs (<A>, <Pr+t>) and (<Pi>. <A>) for i = 1,2, . . , r . SG is an AND/OR graph {Nilsson,l971), where rei-nodes play the role of and-nodes, and ax­ nodes that of or-nodes. If a relation, P, is defined recur­ sively, that is, it occurs in the consequent of an axiom as well as in its antecedent, then the occurrence of P in the antecedent is represented by a main rel-mode, while its occurrence in the consequent - by a secondary rei­ node. The latter is connected to the main rel-node of P through an auxiliary ax-node. Figure 1 shows a SG corresponding to {2). Because all terms appearing in rei-nodes are distinct variables {while all specific rela­ tionships among the terms of an axiom are displayed by the corresponding ax-node) all occurrences of a relation in the database are represented by a single main rei­ node (except its occurrence in the consequent of a recursive axiom}. An atomic query has the form {existential quantifiers are dropped) :

The rel-node representing Q is called the target of q

{denoted ta:rg(q)).

Let V, W ,E denote sets of rcl-nodes, ax-nodes, arcs, respectively, of a system graph, SG. Define the following sets of nods:

immediate predecessors of a node, v,

predecessors of v, PRED(v)

base rel-nodes, BR, is the sel of rel-nodes represent­ ing base relations;

base predecessors of v,

immediate successors of v,

Definition. An axiom, A, is said to be executed on a set of facts, F, if the facts of F which correspond to the antecedent of A are used for producing of all generable facts corresponding to the consequent of A.

The following propositions hold (proofs are omitted in this abstract for brevity}:

Proposition 1. Let q : Q be a query, DP - a top­ down derivation proof of q , ANSW - the set of answers (facts) supplied for q by DP, DER - the set of axioms used in DP as derivation rules, F - the set of facts (belonging to base relations} used in DP. Then all facts of ANSW can be produced out of F by using the axioms of DER as generation rules only.

Proposition 2. All answers to a query, q : Q. can be generated by executing a set of axioms, GEN. called generators of q, on a set of facts, ~. such that ~ is represented by BPRED(Q). and GEN consists of axioms displayed by predecessors of Q, GEN = W n PRED(Q) .

3. AN ECONOliT WAY.

A "brute force" generating answers to a query according to Proposition 2 would be very inefficient pro­ ducing many facts unnecessary for t.he query evaluation because in most practical cases DER and F are small subsets of GEN and cf>, respectively. An economy gen­ erating process should use those facts and axioms which are relevant to the query. Thus, the question is how to discover them.

Definition. In the course of generating facts a term, t 1, can be assigned a value of another term, t 2 , (when expressions are unified (Chang and Lee,l973) or axioms are executed}; we say that t 2 can migrate to t 1 . Assume that all terms of relations are distinct variables, and define a migration set of x, MIG(x }, containing all terms to which x can migrate:

(b) if there are any two predicates such that their unifier contains a substitution x / y then y E MIG(x );

• {c) if y E MIG(x) and z E MIG(y) then z E MIG(x);

{d) no other rules define MIG(x ).

MIG(x) can be easily computed by traversing directed paths in the system graph starting from the rei-node that represents the relation containing x, and checking the equalities displayed by the ax-nodes belonging to these paths.

Definition. Consider a query, q: Q( · · · ,xi = ai, · · · ), with a variable, xi, bound to a constant, ai, and a fact, P{y1=P1 ... . ,yi=Pi· . ... y~c=P~c). with all variables bound. We say that P is relevant to q if P contains Y; such that xi E MIG(y; ), and Pi = ai. 1f q specifies no bound variables then P is relevant to q if there are xi and Yj such that xi E MIG(yi ).

During a query processing no new constants are produced, but the constants appearing in the EDB just migrate from tuple to tuple. This implies

Proposition 3. If a set of facts, F, bas been used for producing an answer to a query, q, then F must con­ tain some facts relevant to q.

This observation suggests an economy way of gen­ erating answers to q : Q. Select. a subset, rp, of 41 con­ taining facts relevant to q . Start generating from rp by trying to execute generators of q on the facts of rp. Consider an axiom, A: P 11\ · · · 1\ Pi A · · · 1\ P1c ... P1c+1· If the antecedent of A is satisfied by rp then execute A producing a new fact corresponding to PlcH· and insert it into rp . Let p' be a fact of rp unifiable with P;. by a unifier, -6. In order to execute A as a generation rule using p' we need facts satisfying (P1A · · · 1\P;. - 1 1\ Pit·\ 1\ · · · 1\ P~c)-6. To get them solve all au:ril.iary queries q 1 : P;"'- for j = 1,2, ... ,i-1,i + l, ... ,k using the facts of 41. Upon generating answers to all qi execute A augmenting rp by newly produced facts, and keep executing axioms of GEN on rp . Terminate if no new facts can be produced. Select from rp answers to q.

This approach is implemented by an algorithm called APEX because it employes extensively pro­ cedures APPLY and EXECUTE. Given an axiom, A, and a set of facts, F. APPLY returns a set of all facts corresponding to the consequent of A such that each of them is deducible from the EDB and !DB by a generat­ ing process that uses necessarily F and A; while EXE­ CUTE returns a set of all facts generable out of F only, by using A as a generation rule.

All facts are clustered into extensions of the corresponding relations. This allows to employ well developed tools of Relational Databases, and efficient algorithms for performing procedures on sets of facts instead of tuple-at-a-time processing. For every rei­ node, R, the sets of its base predecessors, BPRED(R), and generators, GEN(R), are preprocessed at the time of designing of the system graph to reduce run-time processing.

Each fact has an associated variable the value of which is the distance in the system graph from the node representing the fact to the target node of q. Axioms of GEN are executed in the increasing order of their dis­ tances from targ {q), that is, first are used the facts nearest to targ{q), and therefore likely to produce an answer to q in a short time. This ordered execution of axioms improves performance especially for such queries that do not require all the possible answers (e.g. "Give a name of a:ny empLoyee, who ... "), or for which the number of all answers is known (e.g. "Who were the (Jour) grandparents of John?") , including such "boolean" queries as "Is there . .. ?"

Any axiom is executed or applied as soon as the necessary data are available. So APEX is well suited for a parallel multiprocess implementation, in particular, in such a manner that rei-nodes and ax-nodes are associ­ ated with a set of communicating processes {Hoare,1978) exchanging messages along lhe arcs of the SG.

It is proved that APEX is complete in the following sense:

Proposition 4. Given a query, APEX generates all answers implied by the database.

4. AN D..LUSTRATION.

In this section APEX is illustrated by an example taken from {Henschen and Naqvi,1984) involving a recursive definition. Consider a database containing relations M.N.P,R,S which may be thought of as spe­ cial kinds of relations between ancestors and descen­ dants. M(m l,m2). P(p l,p2), R(r l,r2) are base rela­ tions with the extensions:

N(n1,n2) and S{s 1,s2) are virtual relations defined by the following axioms {all variables are of the same type, e.g., person names, so type signs are dropped):

The system graph of this database is depicted in Figure 2.

Let a query be q :S (x ,a) which means "Find all S­ ancestors of a". Generating an answer for q (displayed in Figure 3) may be informally described as follows . First, select from the EDB facts relevant to q. P(d,a} is such a fact {and the only one) because s2 E MJG{p2). In order to execute A 1 on P( d ,a) we need a fact of the form S(x 1,d). To get such a fact solve q 1 :S(x 1 ,d). R(e,d) is relevant to q 1 because s2 E MIG(r2) . A3 exe­ cuted on R(e ,d) generates N(e ,d) . To execute A2 on N(e ,d) a fact M(x2 ,e) is neeed, so solve q2:M(x2.e ). This is simple because M is a base relation. and a proper selection produces M(c ,e). Now .42 generates S(c ,d), and Al N(c,a). A fact M(x3,c) is needed and produced as an answer to q 3 :M(x 3 ,c) by selecting M(b,c) from the corresponding extension. Finally, .42 generates the answer S(b ,a), and the process terminates because no new answers to q can be produced.

5. CONCLUSION.

APEX employs a certain kind of bidirectionality: generating of facts is performed bottom-up, while the axioms used for evaluation of a query, q: Q, are deter­ mined in a top-down manner as predecessors of Q in the system graph. A bottom-up generation is directed by actual information stored in the EDB in contrast to a top-down derivation process that can be developed in directions not supported by the database. But although APEX starts only with relevant facts and restricts the set of used axioms, yet a number of facts irrelevant to the query are likely to be generated in the course of the query evaluation. And so, in some cases a generating process can be inferior to a top-down derivation. Ullman ( 1984} describes very convincing examples in which derivation is more efficient than generation, like in the case (section V) where axioms define recursion on struc­ ture with a certain kind of decreasing structural com­ plexity. On the other hand, in systems with a very developed !DB and relatively not large fi:DB generation promises to be thriftier than derivation because of a significant reduction of the search space. Hence, to achieve a high performance of each specific database system a certain combination of top-down and bottom­ up techniques should be employed depending on the actual characteristics of the system.

For all that, a strong advantage of bottom-up gen­ erating is that it by itself guarantees finiteness of all inferences, and so it deserves certain attention like the one it is paid in this paper. It is shown also that generat­ ing methods may influence database structuring provid­ ing a trade-off between storage space and query evalua­ tion time.

ACKNOWLEDGMENTS.

The author is grateful to Michael Rabin and Jeffrey Ullman for most inspiring discussions of the subject of this paper.

REFERENCES.

• [ 1] Chang, C.-1. DEDUCE -a deductive query language for relational databases. In Artificial [ntelligence and Pattern Recognition, Chen, C. G. (Ed.), Academic Press, New York, 1976, 108-134.

1. Chang,C.-1. DEDUCE 2: further investigations of deduction in relational databases. In Logic and. Da.ta Bases, Gallaire, H., and Minker, J. (Eds.}, Plenum Press, New York, 1978, 201-236.
2. Chang, C.-L. On evaluation of queries containing derived relations in a relational data base. In Advances in Data Base Theory, Gallaire, H., Minker, J .. and Nicolas, J.-M. (Eds.}, v.1, Plenum Press, New York, 1981, 235-260.
3. [ 4] Chang, C.-L., and Lee, R.C.-T. Symbolic ltJgic and Mechanical Theorem Proving, Academic Press, New York, 1973.
4. Gallaire, H. , Minker, J., and Nicolas, J .-M. An over­ view and introduction to logic and data bases. In Logic and. Data Bases, Gallaire, H., and Minker, J. (Eds.} Plenum Press, New York, 1978, 3-32.
5. Henschen, L. J., and Naqvi, S.A. On compiling queries in recursive first-order databases. Proc. Workshop on Logical Bases for Data Bases, Nicolas J .-M. (Ed.), Toulouse, 1982.
6. Henschen, L. J., and Naqvi, S. A. On compiling queries in recursive first-order databases. J. ACM 31, 1 {Jan. 1984), 47-85.
7. Hoare, C. A. R. Communicating sequential processes. Comm ACM 21, 8 {Aug. 1978}, 666-677.
8. Horn, A. On sentences which are true on direct unions of algebras. J. Symb. Logic 16 (1951), 14-21.
9. Kellogg, C., Klahr, P., and Travis, L. Deductive plan­ ning and pathfinding for relational data bases. In Logic and. Data Bases, Gallaire, H., and Minker, J. {Eds.), Plenum Press, New York, 1978, 179-200.
10. Klahr, P. Planning techniques for rule selection in deductive question-answering. In Pa.ttern-Direr:ted. Inference Systems, Waterman, D. A .. and Hayes­ Roth, F. {Eds.}, Academic Press, New York, 1978, 223-240.
11. Kowalski, R Logic for data description. In Logic and Da.ta Bases, Gallaire, H., and Minker, J. (Eds.}, Ple­ num Press, New York, 1978, 77-106.
12. McKay, D. P., and Shapiro, ·S.C. Using active connec­ tion graphs for reasoning with recursive rules. Proc. 7th Int. Joint Conf. on Artificial Intelligence, Vancouver, 1981, 368-374.
13. Minker, J. Performing inference over relational databases. ACM SIGMOD Int. Conf. on Management of Data, San Jose, 1975, 79-91.
14. [15J Minker, J. An experimental relational database sys­ tem based on logic. In Logic and. Data Bases, Gal­ laire, H., and Minker, J. (Eds.), Plenum Press, New York, 1978, 107-147.
15. Minker, . J . Search strategy and selection function for an inferential relational system. ACM TODS 3, 1 (March 1978}, 1-31.
16. :~linker, J ., and Nicolas, J. -M. On recursive axioms in deductive databases. Information Systems 8, t ( 1983), 1-13.
17. Naqvi, S.A., and Henschen, L. J . Performing infer­ ences over recursive data bases. Proc. First Annual Nat. Conf. on Artificial Intelligence, Stanford, 1980, 263-265.
18. Naqvi, S. A:, Fishman, D. H., and Henschen, L. J. An improved compiling technique for first-order data­ bases. Proc. Workshop on Logical Bases for Data Bases, Nicolas, J. -M. {"Ed.), Toulouse, 1982.
19. Nicolas, J. -M., and Gallaire, H. Data base: theory vs. interpretation. In Logic and Data Bases, Gallaire, H., and Minker, J. (Eds.}, Plenum Press, New York, 1978, 33-54.
20. Nicolas, J. -M., and Yazdanian, K. Integrity checking in deductive data bases.In Logic and. Data Bases, Gallaire, H., and Minker, J. {Eds.), Plenum Press, NewYork, 1978, 325-346.
21. Nilsson, N. J. Problem-Salving Methods in Artificial JnteUigence, McGraw-Hill, 1971.
22. Reiter, R. On structuring a first order data base. Proc. 2nd Nat. Conf. of lhe Canadian Society on Computational Studies of Intelligence, Perrault, R. (Ed.), Toronto, 1978, 90-99.
23. Reiter, R. On closed world data bases. In Logic and Da.ta Bases, Gallaire, H .. and Minker, J. (Eds.}, Ple­ num Press, New York, 1978, 55-76.
24. Reiter, R. Deductive question-answering on rela­ tional data bases. In Logic and. Data Bases, Gallaire, H., and Minker, J. (Eds.), Plenum Press, New York, 1978, 149-177.
25. Shapiro, S. C., and McKay, D. P. Inference with recursive rules. Proc. First Annual Nat. Conf. On Artificial Intelligence, Stanford, 1980, 151-153.
26. Ullman, J. D. Implementation of logical query languages for databases. Unpublished manuscript, Jerusalem, 1984.