Name:CSE 444, Spring 2009, Final Examination11 June 2009Rules:• Open books and open notes.• No laptops or other mobile devices.• Please write clearly.• Relax! You are here to learn.Question Max Grade1 252 153 254 155 106 10Total 1001Initials:1. (25 points) SQLConsider a database with the following schema. This database records information about chefs (in-cluding their name and their rating), and the dishes they prepare. For each dish, the database recordsits name and its popularity score.Chef(cid, name, rating) /* cid is a chef’s unique identifier */Dish(did, name, popularity) /* did is a dish’s unique identifier */Prepares(cid, did) /* cid references Chef.cid and did references Dish.did */(a) (7 points) Write a SQL query that lists the names of the dishes prepared by only one chef. Yourquery should return a list of dish names.2Initials:(b) (8 points) Write a SQL query that finds the names of the chefs with above average rating andthe names of the dishes with above average popularity that they prepare. Your query shouldreturn pairs of highly-rated chef name and popular dish name.(c) (10 points) Write a SQL query that finds, for each chef, the most popular dish that he or sheprepares. Your query should output the chef’s name along with the name of his/her most populardish. If there is more than one most popular dish, your query should output them all.3Initials:2. (15 points) TransactionsConsider a concurrency control manager by timestamps. Below are several sequences of events, includ-ing start events, where sti means that transaction Ti starts and coi means Ti commits. These sequencesrepresent real time, and the timestamp-based scheduler will allocate timestamps to transactions in theorder of their starts. In each case below, say what happens with the last request.You have to choose between one of the following four possible answers:(a) the request is accepted,(b) the request is ignored,(c) the transaction is delayed,(d) the transaction is rolled back.(a) st1; st2; r1(A); r2(A); w1(B); w2(B);The system will perform the following action for w2(B):(b) st1; st2; r2(A); co2; r1(A); w1(A)The system will perform the following action for w1(A):(c) st1; st2; st3; r1(A); w3(A); co3; r2(B); w2(A)The system will perform the following action for w2(A):(d) st1; st2; st3; r1(A); w1(A); r2(A);The system will perform the following action for r2(A):(e) st1; st2; st3; r1(A); w2(A); w3(A); r2(A);The system will perform the following action for r2(A):4Initials:3. (25 points) Query ProcessingConsider four tables R(a,b,c), S(d,e,f), T(g,h), U(i,j,k).(a) (5 points) Consider the following SQL query:SELECT R.b, avg(U.k) as avgFROM R, S, T, UWHERE R.a = S.dAND S.e = T.gAND T.h = U.iAND U.j = 5AND (R.c + S.f) < 10GROUP BY R.bDraw a logical plan for the query. You may chose any plan as long as it is correct (i.e. no need toworry about efficiency).5Initials:(b) (10 points) Consider the following two physical query plans. Give two reasons why plan B maybe faster than plan A. Explain each reason.A B A.b = B.b σ B.c < 2000 π A.d,B.d (Index nested loop) (B+ tree index on B.b) (On the fly) σ a>10 (B+ tree index on A.a) (Use B+ tree index) (On the fly) A B A.b = B.b σ B.c < 2000 π A.d,B.d (Hash join) (File scan) (On the fly) σ a>10 (File scan) Plan A Plan B6Initials:(c) (10 points) Explain how two relations R and S can be joined together using a two-pass parti-tioned (Grace) hash join algorithm. In your explanation, use the following facts: R has 90 pages.S has 80 pages. There are 11 pages of memory. Please provide a detailed explanation that includes(1) goal of each step, (2) how many pages are allocated as input buffer(s), (3) how they are used,(4) how many pages are allocated as output buffer(s), (5) how they are used, etc. You can assumethat hash tables have no overhead (a hash table for a relation that has 9 pages will require 9 pagesof memory). You can assume a uniform data distribution.7Initials:4. (15 points) XML/XPath/XQueryConsider an XML instance having the following DTD:<!DOCTYPE university [<!ELEMENT university (student)* ><!ELEMENT student (id, name, major?, course+)><!ELEMENT course (number, name)><!ELEMENT id (#PDCATA) ><!ELEMENT name (#PDCATA) ><!ELEMENT major (#PDCATA) ><!ELEMENT number (#PDCATA) >]>Element id is a unique identifier for students and number is a unique identifier for courses.(a) (1 points) Is the following XML document valid given the above DTD (ignoring headers)? Pleaseanswer true or false.<university><student><id>12345</id><name>Bob</name><course><number>444</number><name>db</name></course><course><number>451</number><name>os</name></course></student><student><id>67890</id><name>Lidia</name><major>CSE</major><course><number>444</number><name>db</name></course></student></university>TRUE or FALSE8Initials:(b) (1 points) Is the following XML document valid given the above DTD (ignoring headers)? Pleaseanswer true or false.<university></university>TRUE or FALSE(c) (1 points) Is the following XML document valid given the above DTD (ignoring headers)? Pleaseanswer true or false.<university><student><id>12345</id><name>Bob</name><major>Math</major></student><student><id>67890</id><name>Lidia</name><major>CSE</major><course><number>444</number><name>db</name></course></student></university>TRUE or FALSE9Initials:(d) (5 points) Write an XPath expression that computes the name of all courses taken by at leastone Math major. Do NOT worry about duplicates. Your answer should only return values suchas:444451444...Note that you have to write an XPath expression, not an XQuery expression.10Initials:(e) (7 points) Write an XQuery expression that reformats a valid XML document as per the aboveDTD into one that matches the following DTD:<!DOCTYPE university [<!ELEMENT university (course)* ><!ELEMENT course (number, student*)><!ELEMENT student (id)><!ELEMENT id (#PDCATA) ><!ELEMENT number (#PDCATA) >]>Courses should occur uniquely. They should include all registered students.11Initials:5. (10 points) Parallel Query ProcessingOlivia is a famous astronomer at the University of Washington. As part of her research, Olivia runsvery large simulations of the universe. These simulations produce massive datasets that Olivia analyzesby executing complex queries. Olivia just ran a simulation that produced 100 GB of data. Her querytook 1,000 minutes to run on this dataset using a single machine.What would it mean for a parallel DBMS (or a system like Pig/MapReduce) to speedup Olivia’s
View Full Document
Unlocking...