Databases Reference
In-Depth Information
against the set of facts computed by the first step, since that set contains all
the information deducible from the DB.
Example 4.3
A bottom-up approach would proceed as follows to answer the query
?-GrandMother (x, Mary), that is, to obtain all grandmothers x of Mary:
1.
All the information that can be deduced from the DB in Example
4.2 is computed by the following iterations:
a. Iteration 0: All base facts are deduced.
b. Iteration 1: Applying rule R1 to the result of iteration 0, we get
Parent(Anthony, John)
Parent( Jack, Anthony)
Parent(Anthony, Mary)
Parent( Jack, Rose)
c.
Iteration 2: Applying rule R2 to the results of iterations 0 and
1, we also get
Parent(Susan, Anthony)
Parent(Rose, Jennifer)
Parent(Susan, Rose)
Parent( Jennifer, Monica)
d. Iteration 3: Applying rule R3 to the results of iterations 0 to 2,
we further get
GrandMother(Rose, Monica)
GrandMother(Susan, Mary)
GrandMother(Susan, Jennifer)
GrandMother(Susan, John)
e.
Iteration 4: The first step is over since no more new
consequences are deduced when rules R1, R2, and R3 are
applied to the result of previous iterations.
2.
The query ?-GrandMother (x, Mary) is applied against the set con-
taining the 20 facts deduced during iterations 1 to 4. Because the
fact GrandMother(Susan, Mary) belongs to this set, the obtained
result is x
Susan, which means that Susan is the only grand-
mother of Mary known by the DB.
Bottom-up methods can naturally be applied in a set-
oriented fashion, that is, by taking as input the entire extensions of
DB predicates. Despite this important feature, bottom-up query
evaluation presents several drawbacks.
=
It deduces consequences that are not relevant to the requested query.
In the preceding example, the procedure has computed several
ยท
