E-mail Address:
![rap [at] cs [dot] ubc [dot] ca](/~rap/address.jpg)
Office Location: CICSR 393
Phone: (604)822-0436
Fax:(604)822-5485
Postal/Courier address:
The Department of Computer Science
University of British Columbia
201-2366 Main Mall
Vancouver, B.C. V6T 1Z4
Canada
Q1: p(X,Y):-r(X,Z) & g(Z,Z) & r(Z,Y)
Q2: p(A,B):-r(A,C) & g(C,D) & r(D,B)
Does Q2 contain Q1? Why or why not?
SolutionIn order to show containment, we must show that applying Q2 to the canonical database of Q1 yields the head of Q1. As our canonical database we take r(X,Z), G(Z,Z), r(Z,Y). applying Q2 to these tuples yields p(X,Y). Since this is the head of Q1, Q2 contains Q1.
Q1: p(X,Y) :- a(X,Z) & a(Z,Y) & NOT a(X,Y)
Q2: p(X,Y) :- a(X,Y) & NOT a(Y,X)
Does Q2 contain Q1? Why or why not?
Solution To prove or disprove this we must consider all possible partions of X, Y, and Z:
| {X},{Y},{Z} |
| {X Y}, {Z} |
| {X}, {Y, Z} |
| {X,Z} {Y} |
| {X, Y, Z} |
For the first partition {X}, {Y}, {Z}, I chose the canonical database X = 0, Y = 1, Z = 2. Q1 Yields p(0,1), so we must check to see if Q2 also yields p(0,1). However, Q2 yields p(0,2), and p(2,1) and not p(0,1), so Q2 does not contain
Q1: p(X,Y) :- q(X,Y) & r(U,V) & r(V,U)
Q2: p(X,Y) :- q(X,Y) & r(U,V) & U <= V
Does Q2 contain Q1? Why or why not?
Solution In essence the problem comes down to this: there is only one arithmetic comparsion, so there are three situations that we have to check carefully: (1) U = V, (2) U < V, (3), U > V. Assigning integers to each of these cases, we see that in each case given the canonical database of Q1, Q2 yields the head of Q1. Therefore Q2 contains Q1.
Q: p(X,Y) :- a(X,Z) & a(Z,W) & a(W,Y)
P: p(X,Y) :- a(X,Y)
p(X,Y) :- p(X,Z) & p(Z,Y)
Does P contain Q? Why or why not?
Solution
In order to tell if P contains Q, we must take the tuples of Q (the canonical database) and see repeated repetition of P will eventually have the head of P yield Q. Our first iteration of the first conjunctive query of P fields p(X,Z),p(Z,W),p(W,Y)
Checking the second rule on the above tuples yields p(X,W), p(Z,Y)
Since we don't yet have p(X,Y) (the head of Q), we need to try the rules of P again on all of the tuples yielded by P so far. Applying the first rule gives us no new tuples, but applying the second rule yields p(X,Y) (twice actually, once by combining p(X,Z) with P(Z,Y) and once with p(X,W), p(W,Y)), so P contains Q.
Given query q and views v1 and v2:
q(X):-e1(X,Y),e2(Y,Z),e3(Z,X)
v1(A,B,C,D):-e1(A,B),e2(C,D)
v2(D,E):-e3(D,E)
Use v1 and v2 to create an equivalent query to q that does not access e1, e2, or e3. There is no need to show that they are equivalent.
Solution
The key is to realize that we must have the same values for the second
attribute of e1 as the first attribute of e2. Similarly the second
attribute of e2 must match the first attribute of e3, and the first
attribute of e1 must be the same as the second attribute of e3. There
are a number of ways that this can be done. The most succinct solution
is:
q(x):-v1(X,Y,Y,Z), v2(Z,X)
If you expand the view definitions with the above variables, this
gives you back q(x):-e1(X,Y),e2(Y,Z), e3(Z,X), so the two queries are equivalent.
QuestionBonus thought experiment (no need to turn this in for credit): if the definition of V1 was v1(A,D), could you create an equivalent query for q using only v1 and v2? Why or why not?
Solution No. If the definition of V1 was V1(A,D), then we couldn't guarantee that the second attribute of e1 and the first attribute of e2 were the same.