For the first two questions, consider the following schema:
Jedi-Teams (master, apprentice)
Jedi(name, side, home-planet)
Government(leader planet, postition)
from Jedi-Teams, Jedi, Government
where apprentice = name and
name = leader and
side = 'dark'
Answer: Best: Worst:
Answer: I’d expect to see the biggest difference when there are a small proportion of Jedi who use the dark side
Answer: I’d expect to see the smallest difference when most Jedi use the dark side
2. Please look at the following query:
select count(*), home-planet
from Jedi, Inhabitants
where specie = 'wookies' and
planet = home-planet and
side = 'light'
group by home-planet
Answer: I'd expect to see the biggest difference when there was a wide variation on planets, home-planets, and there were a lot of species other than wookies, and wookies lived on a large number of planets.
Answer: I'd expect to see the smallest difference (or even have the best plan run slower) if wookies lived on only one planet, and there were a very small number of planets and home planets.
Answer: I assumed that the number of home planets and planets total would be significant; thus we can optimize by pushing down the group by. If there were few, then the savings would not be as great, and this might be a bad place to do this.
3. Here are two plans for the same query:
Answer: Plan A
Answer: If there were going to be no tuples out of the join of A and B, and all of them had A.A equal to 3, I would prefer the second plan. It doesn’t save that much work (since selects are cheap), but it does save some.
5. Can you un-nest the following query?
Where A.B = 42
and A.C in (
Where B.D = 'Darth' and
A.E = B.B
Yes (well, I can):
Where A.B = 42 and
B.A = A.C and
B.D = ‘Darth’ and
A.E = B.B
6. Consider the conjunctive queries Q1 and Q2.
Q1: p(U,Z) :- q(U,V) & q(X,Y) & r(Y,Z) & r(V,X)
Q2: p(U,V) :- q(Y,U) & q(U,X) & r(U,V) & r(X,Y)
Is Q1 contained in Q2? Is Q2 contained in Q1? Justify your answers.
Q2 is contained in Q1. Containment mapping from Q1 to Q2: U->U, Z->V, V->X, X->Y, Y->U.
7. Consider the following query and views:
Q(x) :- e1(x), e2(x,y), e3(y,z), y > 25
V2(B):- e2(B,C), C > 25
V3(E):- e2(E,D), e3(D,F), D > 24
V4(G):- e2(G,H), e3(H,I), H > 26
V5(K):- e1(J), e2(J,K), e3(K,L), K > 25
V2: No, we need to use y in e3 in addition to e2, and it is not mapped by V2, and C is existential in V2
V3: No, y is mapped to D, and D needs to be greater than 25, and in V3 it’s only > 24 and D is existential
V4: No. We are looking for an equivalent rewriting, and this will only return a subset of the correct answers
V5: No. We need x to be distinguished since it is returned in the head. Since x is mapped to J, and J is existential, it cannot be used.
V7: No. we need to map x to o, and since x is distinguished in the query, we can't use it.
V8: No. We are looking for an equivalent rewriting, and thus we cannot accept that y and z are equated
Yes. V4 and V8 can now both be used because we are looking for maximally contained rewritings rather than equivalent rewritings.
(Q’1(x):-V1(x), V4(x)) È (Q’2(x):-V1(x), V6(X,Y), V8(Y), Y > 25)