CSE 444 Final ExaminationJune 10th, 2010Name:Question Points Score1 152 203 104 105 106 107 158 10Total: 100This exam is an open book exam. You have 1 hour 50 minutes; budget time carefully.Intermediate steps are rarely required but often useful for partial credit. Good luck!1CSE 444 Final June 10, 20101 SQL1. (15 points)Consider the following Flickr-type database:Users(uid, name)Picture(pid, owner, size)Comment(cid, auth, pict, text)Where:• User.uid, Picture.pid, Comment.cid are keys.• Picture.owner, Comment.auth are foreign keys into Users.• Comment.pict is a foreign key to Picture.(a) (5 points) Write a SQL query that counts, for every user, the number of other userswho have commented on their pictures. That is, for each user you need to computethe total number of distinct users (including herself) who have commented on anyof her pictures. Your answer should return only those answers where the count is≥ 1 (i.e. you don’t need to return users that have no comments on any of theirpictures).Page 2CSE 444 Final June 10, 2010Users(uid, name)Picture(pid, owner, size)Comment(cid, auth, pict, text)(b) (5 points) A spammer is a user who comments on all pictures that are not ownedby him (her). Write a SQL query that returns all spammers.Page 3CSE 444 Final June 10, 2010Users(uid, name)Picture(pid, owner, size)Comment(cid, auth, pict, text)(c) (5 points) Two users are friends if they comment on each others’ pictures: that is,x, y are friends if x made a commented on some picture of y, and y made a commenton some picture of x. Write a SQL query that computes, for each user, the numberof his/her friends. Your query should return only those answers where the count is≥ 1.Page 4CSE 444 Final June 10, 20102 Transactions2. (20 points)Consider a concurrency control manager by timestamps. Below are several sequences ofevents, including start events, where sti means that transaction Ti starts and coi meansTi commits. These sequences represent real time, and the timestamp-based schedulerwill allocate timestamps to transactions in the order 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:1. the request is accepted,2. the request is ignored,3. the transaction is delayed,4. the transaction is rolled back.(a) (4 points) st1; st2; st3; r1(A); w1(A); r2(A);The system will perform the following action for r2(A):(b) (4 points) st1; st2; r2(A); co2; r1(A); w1(A)The system will perform the following action for w1(A):(c) (4 points) st1; st2; st3; r1(A); w2(A); w3(A); r2(A);The system will perform the following action for r2(A):(d) (4 points) st1; st2; r1(A); r2(A); w1(B); w2(B);The system will perform the following action for w2(B):(e) (4 points) st1; st2; st3; r1(A); w3(A); co3; r2(B); w2(A)The system will perform the following action for w2(A):Page 5CSE 444 Final June 10, 20103 Conceptual Design3. (10 points)(a) (5 points) Decompose in BCNF the relation R(A, B, C, D, E) that satisfies the fol-lowing functional dependencies. Show your steps, and show the keys in the decom-posed relations.A → BCD → EPage 6CSE 444 Final June 10, 2010(b) (5 points) For each of the statements below, indicate whether they are true or false.You do not need to justify your answers.• Every relation with only two attributes is in BCNF.• If X and Y are super-keys then X ∪ Y is also a super-key.• If X and Y are super-keys then X ∩ Y is also a super-key.• If X → A and Y → A, then (X ∩ Y ) → A.• If X+= X and Y+= Y then (X ∩ Y )+= (X ∩ Y ).Page 7CSE 444 Final June 10, 20104 Indexes4. (10 points)Consider the following database about word occurrences in Webpages:Webpage(url, author)Occurs(url, wid)Word(wid, text, language)where:• Webpage.url and Word.wid are keys.• Occurs.url and Occurs.wid are foreign keys to Webpage and Word respectively.Assume the following statisticsT (Webpage) = V (Occurs, url) = 109T (Occurs) = 1012T (Word) = V (Occurs, wid) = 106V (Webpage, author) = 107V (Word, language) = 100Assume ten records can be fit in one block, hence B(Webage) = T (Webpage)/10 andsimilarly for all other tables.(a) (5 points) Consider the following plan:(σindex-lookupauthor=’John’(Webpage) 1index-joinurl=urlOccurs)1main-memory-hash-joinwid=widσindex-lookuplanguage=’French’(Word)Compute the cost of the plan in each of the following cases:Page 8CSE 444 Final June 10, 20101. We have the following indexes:Webpage.url = primary indexWebpage.author = secondary indexOccurs.url = secondary indexOccurs.wid = primary indexWord.wid = primary indexWord.language = secondary index2. We have the following indexes:Webpage.url = secondary indexWebpage.author = primary indexOccurs.url = primary indexOccurs.wid = secondary indexWord.wid = secondary indexWord.language = primary indexPage 9CSE 444 Final June 10, 2010(b) (5 points) Consider the following plan:(Webpage 1merge-joinurl=urlOccurs) 1merge-joinwid=widWordChoose a set of indexes that minimizes the total number of disk I/O’s for the plan.Each index should be on a single attribute, and you can choose as many (or as few)indexes as you want. Indicate for each index if it is primary or secondary. For eachmerge-join we assume to have sufficient main memory to complete it in two pass.(There are no index-join operators in this plan: you need to figure out how indexescan help at all in this query plan.)Page 10CSE 444 Final June 10, 20105 Query Optimization5. (10 points)For the following questions, we consider the schema R(A, B), S(C, D), T (E, F ), U(G, H).(a) (5 points) Write a logical plan for the following query:select R.A, sum(T.F)from R, S, Twhere R.B = S.C and S.D = T.Egroup by R.Ahaving count(*) > 20Page 11CSE 444 Final June 10, 2010(b) (5 points) Consider the following query:select *from R, S, T, Uwhere R.B = S.C and S.D = T.E and S.D = U.G• Write all left-deep, cartesian-free join trees for this query. Assume that thejoin operator is not commutative: that is, you should report both R 1 S andS 1 R as distinct plans. Note: you need to turn in several plans.Page 12CSE 444 Final June 10, 2010• Write a full semijoin reducer for this query.Page 13CSE 444 Final June 10, 20106 Statistics6. (10 points)Consider the relations R(A, B), S(C, D), T (E, F ) and the following histograms on R.Aand T.F :R.A 0 . . . 999 1000 . . . 1999 2000 . . . 2999 3000 . . . 3999 4000 . . . 49991042 · 1043 · 1043 · 1042 · 104T.F 0 . . . 2499 2500 . . . 2699 2700 . . .
View Full Document
Unlocking...