Name_________________________________________ - 1 - UNIVERSITY OF CALIFORNIA Department of EECS, Computer Science Division CS186 Hellerstein/Olston Fall 2006 Midterm Exam Midterm Exam: Introduction to Database Systems This exam has four problems and one extra credit question, worth different amounts of points each. Each problem is made up of multiple questions. You should read through the exam quickly and plan your time-management accordingly. Before beginning to answer a problem, be sure to read it carefully and to answer all parts of every problem! Good luck! 1. Relational Query Languages [20 points] Recently, Bob the Builder coded up a Relational Query Language Translator (RQLT) and passed it along to his lesser-known colleague, Ted the Software Test Engineer, for testing. Fortunately for Ted, the RQLT is simple and only operates on a single schema: Tool(tid, brand, cost) Jobsite(location, compensation, task) Toolbox(tbid, location) – location is a foreign key to Jobsite Holds(tbid, tid) – tbid is a foreign key to Toolbox, tid is a foreign key to Tool. a. (5 points) Ted sets the RQLT to translate the following SQL query to Relational Algebra: SELECT T.tid FROM Tool T, Holds H, Toolbox B, Jobsite J WHERE T.tid = H.tid AND H.tbid = B.tbid AND B.location = J.location AND J.task = ’Plumbing’ Which of the following would be an equivalent Relational Algebra query? 1. πtid(Tool Holds Toolbox σtask = ‘Plumbing’ (Jobsite)) 2. πtid(σtask = ‘Plumbing’ (Tool (Holds Toolbox) Jobsite)) 3. σtask = ‘Plumbing’ (πtid (Tool) Holds Toolbox Jobsite) 4. 1 and 2 5. 1, 2, and 3 6. None of the above YOUR ANSWER HERE (1a): _________________ You must write your answers on the exam. Two pages of extra answer space have been provided at the back in case you run out of space while answering. If you run out of space, be sure to make a “forward reference” to the page number where your answer continues. Do not tear pages off of your exam! Class Account: ________________________________Name_________________________________________ - 2 - b. (10 points) Ted switches the RQLT to translate Relational Algebra into Relational Calculus and passes in: πtbid(Toolbox) – πtbid( ( πtbid(Toolbox) × πbrand(Tool) ) – πtbid,brand(Holds Tool) ) Fill in the blanks to complete the equivalent Relational Calculus Query. Note: the correct answer may not require all blanks to be filled in. { B1 | B ∈ Toolbox ___________ B.tbid = B1.tbid ___________ ___________ T ∈ Tool (__________ H ∈ Holds (T.tid = H.tid __________ H.tbid = B.tbid)) } c. (5 points) Ted thinks that he has found a bug in the RQLT. It translates the following Relational Calculus query: { H1 | H ∈ Holds ∧ H1.tbid = H.tbid ∧ ∀ Τ ∈ Tool ( (H.tid = T.tid) ⇒ (T.brand = ‘Craftsman’ ∨ T.brand = ‘Channellock’)) } into the following incorrect SQL query (marked with line numbers for the purpose of this question): 1. SELECT H.tbid 2. FROM Tool T, Holds H 3. WHERE T.tid = H.tid AND T.brand = ‘Craftsman’ 4. INTERSECT 5. SELECT H1.tbid 6. FROM Tool T1, Holds H1 7. WHERE T1.tid = H1.tid AND T1.brand = ‘Channellock’; Fix this SQL query to match the Relational Calculus query by changing exactly ONE line: Answer: Change line _______ into: ______________________________________________________Name_________________________________________ - 3 - 2. B+ Trees [23 points] Consider the following B+ tree index of order 1: a. (3 points) Circle all nodes (not index entries, but entire nodes) in the above figure that must be fetched to satisfy the query "Get all records with search key greater than or equal to 7 and less than 15". b. (15 points) Assume we modify the B+ tree by adding the following keys in the following order: 20, 27, 18, 30, 19 In the answer-boxes below, each row refers to a key being inserted in order, and each column asks if the insertion of that key results in a split of particular nodes. Assume that when splitting up an odd number of entries, the left node gets one more than the right. Place a check mark (✓) in each box whose answer is “Yes”. Blank boxes will be interpreted as “No”. You may want to use the back of the previous page for scratch space. Key Leaf Node Split? Non-Leaf Split? Root Split? 20 27 18 30 19 c. (5 points) Suppose we were to insert all integers in the range 26 to 4112 inclusive (i.e. 26, 27, 28 ... , 4111, 4112) into the tree in part (a), one at a time. At most how many levels would the resulting B+-tree have? (Hint: You should not need to draw a B+-tree to figure this out!) YOUR ANSWER HERE (2c): ____________________Name_________________________________________ - 4 - 3. Query Optimization [32 points] Consider the following schema: Guitars (gid, brand, price) Players (pid, name, age) LastPlayed (gid, pid, date) And the following query: SELECT P.name FROM Guitars G, Played P, LastPlayed L WHERE G.gid = L.gid AND P.pid = L.pid AND P.age < 25 AND G.brand = ‘Gibson’ AND G.price > 3000; In the schema, Guitars.gid is the primary key of Guitars, Players.pid is the primary key of Players, and LastPlayed.gid and LastPlayed.pid are foreign keys referencing the primary keys of Guitars and Players (respectively). Assume that the data is evenly distributed, and that the following properties hold: Players.age ranges from 10 to 85 Guitars.brand has 10 distinct values Guitars.price ranges from 1,000 to 5,000 Guitars.gid has 1,000 distinct values Players.pid has 1,000 distinct values a. (5 points) Compute the selectivity for each individual term in the WHERE clause. You must fill in each blank below! G.gid = L.gid : _________________________________ P.pid = L.pid : __________________________________ P.age < 25 : __________________________________ G.brand = ‘Gibson’ : __________________________________ G.price > 3000 : __________________________________Name_________________________________________ - 5 - b. (5 points) According to the System R query optimizer that we studied, circle all the following join orders that would be considered: c. (12 points) Now consider the following. There is a B+ tree index on Guitars.gid – it is unclustered and it uses Alternative 2 to represent data
View Full Document
Unlocking...