# Homework 2 Solutions

1. Question(For Section 1.1)

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.

2. Question(For Section 1.2)

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 each partition we must choose a canonical database. If that canonical database yields a head for Q1, we must apply Q2 to the same tuples. If Q2 does not yield the head of Q1 for any non-empty solution of Q1, then Q2 does not contain Q1.

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

3. Question(For Section 1.3)

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.

4. Question(For Section 1.4)

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.

5. Question(For Section 2.1)

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.

1. questionHow long did it take you to complete this assignment?
My answer It covered all the basics
My answer I should have come up with better real world examples to make the questions less abstract
4. questionWhat helped you learn the best in this assignment?
My answer Reading over student's solutions to see where they got confused.
5. questionWhat distracted from your learning in this assignment?