Databases Reference
In-Depth Information
cause reevaluation of the subquery, thus reducing efficiency of the
whole evaluation.
4.3.3
Magic Sets
The magic sets approach is a combination of the previous approaches, aimed
at providing the advantages of the top-down approach when a set of deduc-
tive rules is evaluated bottom-up. Given a deductive DB D and a query Q
on a derived predicate P, this method is aimed at rewriting the rules of D into
an equivalent DB D
by taking Q into account. The goal of rule rewriting
is to introduce the simulation of top-down into D
¢
¢
in such a way that a
bottom-up evaluation of rules in D
will compute only the information nec-
essary to answer Q. Moreover, the result of evaluating Q on D
¢
¢
is equivalent
to querying Q on D.
Intuitively, this is performed by expressing the information of Q as
extensional information and by rewriting the deductive rules of D used dur-
ing the evaluation of Q. Rule rewriting is performed by incorporating the
information of Q in the body of the rewritten rules.
Example 4.5
Consider again Example 4.2 and assume now that it also contains the follow-
ing deductive rules defining the derived predicate Ancestor:
Ancestor(x,y)
¬
Parent(x,y)
Ancestor(x,y)
¬
Parent(x,z)
Ù
Ancestor(z,y)
Rewritten magic rules for evaluating bottom-up the query ?-Ancestor(Rose,x)
are as follows:
Magic_Anc(Rose)
Ancestor(x,y)
¬
Magic_Anc(x)
Ù
Parent(x,y)
(rule R1)
Magic_Anc(z)
¬
Magic_Anc(x)
Ù
Parent(x,z)
(rule R2)
Ancestor(x,y)
¬
Magic_Anc(x)
Ù
Parent(x,z)
Ù
Ancestor(z,y)
(rule R3)
Assuming that all facts about Parent are already computed, in particular,
Parent(Rose, Jennifer) and Parent( Jennifer, Monica), a naive bottom-up
evaluation of the rewritten rules would proceed as follows:
