Databases Reference
In-Depth Information
Top-down (backward chaining ). The query evaluation procedure
starts from a query Q and applies deductive rules backward by trying
to deduce new conditions required to make Q true. The conditions
are expressed in terms of predicates that define Q, and they can be
understood as simple subqueries that, appropriately combined, pro-
vide the same answers as Q. The process is repeated until conditions
only in terms of base facts are achieved.
·
Sections 4.3.1 and 4.3.2 present a query evaluation procedure that fol-
lows each approach and comments on the advantages and drawbacks.
Section 4.3.3 explains magic sets, which is a mixed approach aimed at achiev-
ing the advantages of the other two procedures. We present the main ideas of
each approach, illustrate them by means of an example, and then discuss
their main contributions. A more exhaustive explanation of previous work
in query processing and several optimization techniques behind each
approach can be found in most topics on deductive DBs (see, for instance,
[1, 8, 9, 24]).
The following example will be used to illustrate the differences among
the three basic approaches.
Example 4.2
Consider a subset of the rules in Example 4.1, with some additional facts:
Father(Anthony, John)
Mother(Susan, Anthony)
Father(Anthony, Mary)
Mother(Susan, Rose)
Father( Jack, Anthony)
Mother(Rose, Jennifer)
Father( Jack, Rose)
Mother( Jennifer, Monica)
Parent(x,y)
¬
Father(x,y)
(rule R1)
Parent(x,y)
¬
Mother(x,y)
(rule R2)
GrandMother(x,y)
Mother(x,z)
Parent(z,y)
(rule R3)
¬
Ù
4.3.1
Bottom-Up Query Evaluation
The naive procedure for evaluating queries bottom-up consists of two steps.
The first step is aimed at computing all facts that are a logical consequence
of the deductive rules, that is, to obtain the minimal Herbrand model of
the deductive DB. That is achieved by iteratively considering each deductive
rule until no more facts are deduced. In the second step, the query is solved
