For the first two questions, consider the following schema:For the first two questions, consider the following schema:Jedi-Teams (master, apprentice)Jedi(name, side, home-planet)Government(leader planet, postition)Inhabitants(specie, planet)1. Given a query to find all planetary leaders who are apprentices and use the dark side of the force:select leaderfrom Jedi-Teams, Jedi, Governmentwhere apprentice = name and name = leader and side = 'dark'a. Express this query in terms of relational algebraAnswer: leader((Jedi-Teams apprentice = name ( side = ‘dark’ (Jedi))) name = leader Government)b. Write your expression as the corresponding logical query planAnswer:c. Now, according to System-R style optimization, write the best and worst logical query plan (involving only the relations given, wise guys) possible.Answer: Best: Worst:JediGovernmentJedi-Teams side = ‘dark’ leadername = leaderapprentice = nameJediGovernmentJedi-Teams side = ‘dark’ leadername = leaderapprentice = nameJediGovernmentJedi-Teams side = ‘dark’ leadername = leaderapprentice = namei. Under what circumstances would you expect to see the biggest difference?Answer: I’d expect to see the biggest difference when there are a small proportion of Jedi who use the dark sideii. Under what circumstances would you expect to see the smallest difference?Answer: I’d expect to see the smallest difference when most Jedi use the dark side2. select count(*), home-planetfrom Jedi, Inhabitantswhere specie = 'wookies' andplanet = home-planet andside = 'light'group by home-planeta. Express this query in terms of relational algebraAnswer:count(*), home-planet( Group by home-planet (side = ‘light’(Jedi) planet = home-planet (specie = ‘wookies’(Inhabitants))))b. Write your expression as the corresponding logical query planAnswer:c. Now, according to System-R style optimization, write the best and worst logical query plan possible.Answer: Best Worst count, home-planetGroup by home-planetJedi specie = ‘wookies’ side = ‘light’Inhabitantsplanet = home-planet count, home-planetGroup by home-planetJedi specie = ‘wookies’ side = ‘light’Inhabitantsplanet = home-planet count, home-planetGroup by home-planetJedi specie = ‘wookies’ side = ‘light’Inhabitantsplanet = home-planetGroup by planet Group by home-planeti.ii. Under what circumstances would you expect to see the biggest difference?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.iii. Under what circumstances would you expect to see the smallest difference?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.d. What kind of optimizations are you able to make using the group by? If none, why can’t you improve your plan with it?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:a. With no knowledge about the data sources, which plan would you prefer?Answer: Plan Ab. Is there a reason that you might prefer the other plan?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.BA.A = 3A Answer.A = 3A BPlan A Plan B4. In the following example, push the selection beneath the union:Answer:5. Can you un-nest the following query?Select A.A From AWhere A.B = 42and A.C in (Select B.AFrom BWhere B.D = 'Darth' and A.E = B.B)Answer:Yes (well, I can):Select A.AFrom A,BWhere A.B = 42 andB.A = A.C andB.D = ‘Darth’ andA.E = B.B6. 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) Planet = ‘Naboo’UnionA BUnionA B Planet = ‘Naboo’ Planet = ‘Naboo’Is Q1 contained in Q2? Is Q2 contained in Q1? Justify your answers.Answer: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 > 25V1(A):- e1(A)V2(B):- e2(B,C), C > 25V3(E):- e2(E,D), e3(D,F), D > 24V4(G):- e2(G,H), e3(H,I), H > 26V5(K):- e1(J), e2(J,K), e3(K,L), K > 25V6(M,N):- e2(M,N)V7(P):- e1(O),e2(O,P)V8(R):- e3(R,R)a. In a query optimization context,i. For each of V1-V8, is it able be used in rewriting Q? If not, why?Answer:V1: Yes.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 V2V3: No, y is mapped to D, and D needs to be greater than 25, and in V3 it’s only > 24 and D is existentialV4: No. We are looking for an equivalent rewriting, and this will only return a subset of the correct answersV5: 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.V6: Yes.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 equatedii. Is there an equivalent rewriting? If so, what is it?Answer:No.b. In a data integration context, i. Does your answer for a.i change for any of the views? If so, which ones, and why?Answer:Yes. V4 and V8 can now both be used because we are looking for maximally contained rewritings rather than equivalent rewritings.ii. Assuming that each of the sources are non-overlapping, if there is a maximally contained rewriting, what is it?Answer:(Q’1(x):-V1(x), V4(x)) (Q’2(x):-V1(x), V6(X,Y), V8(Y),Y >
View Full Document
Unlocking...