DOC PREVIEW
Berkeley COMPSCI 186 - Final Exam - Introduction to Database Systems

This preview shows page 1-2-3-4-5 out of 14 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Final Exam: Introduction to Database SystemsDIDUNIVERSITY OF CALIFORNIADepartment of EECS, Computer Science DivisionCS186 Final ExamMay 16, 2000Final Exam: Introduction to Database SystemsThis exam has seven sections, each with one or more problems. Each problem may be made up of multiple questions. You should read through the exam quickly and plan your time-management accordingly. Before beginning to answer a question, be sure to read it carefully and to answer all parts of every question! REFERENCE DATABASE . This is the Reference Database referred to in some of the questions.There are six tables describing a company, describing employees, departments, buildings, which department(s) an employee works in (and a percentage of the time for each), department managers (possibly more than one per department), and in which building an employee works (an employee may have more than one office). The primary key of each table is the attribute(s) in capitals. Other attributes are not necessarily unique.You must write your answers on these stapled pages. You also must write your name at the top of everypage except this one, and you must turn in all the pages of the exam. You may remove this page from the stapled exam, to serve as a reference, but do not remove any other pages from the stapled 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 youranswer continues.EMP – 100,000 tuples, 1,000 pagesEID EName Salary Start_Date End_Date001 Jane $124,000 3/1/93 null002 Jim $32,000 2/29/96 null003 John $99,000 12/12/98 null004 Joe $55,000 2/2/92 null005 Jenny $51,000 5/5/95 nullEID values range from 1 to 100,000BUILDING – 2,000 tuples, 10 pagesBID BName Address201 ATC 1600 Ampitheatre202 CCC 500 Crittenden203 MFB 123 ShorelineBID values range from 1 to 2,000DEPT – 1,000 tuples, 5 pagesDID DName Annual_Budget101 Research $1,001,000102 Development $500,000103 Sales $2,000,000DID values range from 1 to 1000IN_DEPT – 110,000 tuples, 550 pagesEID DID Percent_Time001 101 100002 102 100003 101 60003 102 40004 103 100005 103 100 IN_BUILDING – 110.000 tuples, 550 pagesEID BID001 201002 201003 202003 203004 202005 203MANAGES_DEPT – 800 tuples, 4 pagesEID DID003 101003 102001 103Name________________________________________________ Login_______________________CS186 March 6 Midterm Page 3I. SQL – All queries are based on the sample schema shown on the first page. Assume that the tables have many more rows than are shown there. 15 Points.1. Which of the following queries finds the names of buildings where more than 50 employees work? (Circle as many as are correct.) (5 points)a. SELECT BnameFROM IN_BUILDINGGROUP_BY BIDWHERE Count(*) > 50b. SELECT BnameFROM BUILDINGWHERE BID IN (SELECT BID FROM In_Building GROUP BY BID HAVING Count(*) > 50)c. SELECT BnameFROM Building B, In_Building IWHERE B.BID = I.BIDGROUP BY B.BIDHAVING Count(*) > 50 d. SELECT BnameFROM Building BWHERE 50 < (SELECT Count(*) FROM In_Building I WHERE I.BID = B.BID)e. None of the above2. Which of the following queries finds the name of Departments where no employees work? (Circle as many as are correct.) (5 points)a. SELECT DnameFROM DeptWHERE DID IN (SELECT I.DID FROM In_Dept I GROUP BY I.DID HAVING COUNT(*) = 0)b. SELECT DnameFROM Dept D, In_Dept I, Emp EWHERE I.EID = E.EID and D.DID = I.DID and Count(E.EID) = 0c. SELECT DnameFROM DeptWHERE DID NOT IN (SELECT DISTINCT DID FROM In_Dept I) d. SELECT DnameFROM Dept DWhere Not Exists (SELECT * FROM In_Dept I, EMP WHERE I.EID = EMP.EID and I.DID = D.DID)e. None of the aboveName________________________________________________ Login_______________________3. Which of the following queries finds the name of the Department(s) where the highest paid employee works? (Circle as many as are correct.) (5 points)a. SELECT D.DnameFROM Dept DWHERE D.DID IN (SELECT T.DID, MAX(Salary) FROM Dept T, In_Dept I, Emp E WHERE T.DID = I.DID and E.EID = I.EID)b. SELECT DnameFROM Dept D, In_Dept I, Emp EWHERE D.DID = I.DID and E.EID = I.EID and E.Salary = MAX(Salary)c. SELECT DNameFROM Dept D, In_Dept I, Emp EWHERE D.DID = I.DID and E.EID = I.EID and E.Salary >= ALL (SELECT Salary FROM EMP)d. SELECT DNameFROM DeptWHERE DID IN (SELECT I.DID FROM In_Dept I, Emp E WHERE I.EID = E.EID AND E.Salary = (SELECT MAX(Salary) FROM Emp))e. None of the aboveCS186 March 6 Midterm Page 5Name________________________________________________ Login_______________________II. Implementation of Relational Operators – 18 pointsConsider the schema on the first page, and the number of tuples and pages for each relation shown there. Let “” be the join operator, and “AB” means join with A as the outer relation and B as the inner.As we did in class, when computing the cost for join algorithms, you may ignore output cost (since this is the same for all algorithms).Note: you have 9 pages of main memory to work with in these problems.1. Consider the operation:  (EID < 5000)EMP (2 points)a) What is the I/O cost of this operation? _________b) What is the reduction factor? ________2. Consider the join: In_Dept  Dept (4 points)a) What is the I/O cost of this using Blocked Nested Loops? __________b) What is the I/O cost of this using Index Nested Loops, with a Hash index on Dept.DID? ___________3. Consider the join: Dept  In_Dept (4 points)a) What is the I/O cost of this using Blocked Nested Loops? ____________b) What is the I/O cost of this using Index Nested Loops, with a Hash index on In_Dept.DID? __________________________4. Consider the join: EMP  In_Building (8 points)a) What is the I/O cost of this using Blocked Nested Loops? ___________b) What is the I/O cost to sort EMP? _________c) What is the I/O cost to sort In_Building? _________d) What is the total I/O cost to do this using Sort/Merge join? __________CS186 March 6 Midterm Page 6Name________________________________________________ Login_______________________III. Query Optimization – 13 pointsConsider the schema shown on the first page and especially the number of tuples and pages for each relation. Consider the following query:Select Bname From EMP E, Building B, In_Building IWhere E.EID < 500 and E.EID = I.EID and B.BID = I.BID1. Write this query in


View Full Document

Berkeley COMPSCI 186 - Final Exam - Introduction to Database Systems

Documents in this Course
Load more
Download Final Exam - Introduction to Database Systems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final Exam - Introduction to Database Systems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Exam - Introduction to Database Systems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?