COP5725 Database Management SystemsFinal – Fall 2005Instructor: Alin DobraJanuary 4, 2006Name:UFID:Email:• This is a 120 minute, closed-book exam. You are allowed to use handwritten notes on bothsides of a US letter size sheet of paper.• This exam contains 8 single-sided sheets of paper (including this one)• Write all answers on these pages, preferably on the white space in the problem statement.Continue on the back page if running out of space but clearly number your answers if doingso.• Make sure you attack every problem; partial credit will be awarded for incomplete or partiallycorrect results.Grading:1 252 253 154 105 106 15Total 10011. Relational Algebra [25]Consider the following relational schema:employee(empno,name,office,age)books(isbn,title,authors,publisher)loan(empno,isbn,date)[5] Identify the keys (by underlying the attributes) for all three relations above.Write the following queries in relational algebra:a. [5] Find the names of employees who have borrowed a book published by McGraw-Hill.b. [5] Find the names of employees who have borrowed all books published by McGraw-Hill.c. [5] Find the names of em ployees who have borrowed more than five different bookspublished by McGraw-Hill.d. [5] For each publisher, find the names of employees who have borrowed more than fivebo oks of that publisher.22. SQL [25]Consider the employee database with the schema:employee(employee_name, street, city)works(employee_name, company_name, salary)company(company_name, city)manages(employee_name,manager_name)Give an expression in SQL for each of the following queries:a. [5] Find the names, street address, and cities of residence of all employees who work forFirst Bank Corporation and earn more than $10000.b. [5] Find all em ployees in the database who earn m ore than each employee of Small BankCorporation (do not use aggregates).c. [5] Assume that the companies may be located in several cities. Find all companieslocated in every city in which Small Bank Corporation is located.3d. [5] Find the company that has the most employees.e. [5] Find those companies whose employees earn a higher salary, on average, than theaverage salary at First Bank Corporation.43. XML [ 15]Consider the following XML document:<? xml version=’’1.0’’ ... ><BOOKLIST><BOOK GENRE=’’Science’’ FORMAT=’’Hardcover’’><AUTHOR><FIRSTNAME>Richard</FIRSTNAME><LASTNAME>Feynman</LASTNAME></AUTHOR><TITLE>The Character of Physical Law</TITLE><PUBLISHED>1980</PUBLISHED></BOOK><BOOK GENRE=’’Fiction’’><AUTHOR><FIRSTNAME>R.K.</FIRSTNAME><LASTNAME>Narayan</LASTNAME></AUTHOR><TITLE>Waiting for the Mahatma</TITLE><PUBLISHED>1981</PUBLISHED></BOOK><BOOK GENRE=’’Fiction’’><AUTHOR><FIRSTNAME>R.K.</FIRSTNAME><LASTNAME>Narayan</LASTNAME></AUTHOR><TITLE>The English Teacher</TITLE><PUBLISHED>1980</PUBLISHED></BOOK></BOOKLIST>Answer the following questions:a. [5] Give a DTD of this document so that the ab ove document is correct but the DTD isas constrained as poss ible.5b. [5] Give a XPath expression that selects all authors from this document (no need toeliminate duplicates).c. [5] What is the result of the execution of the following XQuery query?FOR $p IN //BOOKLET $q := $p/AUTHORLET $r := $p/PUBLISHEDLET $t := $p/@GENRERETURN<PUBLICATION><AUTHORNAME> {$q/FIRSNAME} {$q/LASTNAME} </AUTHORNAME>{$r}<GENRE>{$t}</GENRE></PUBLICATION>4. Transactions [10]Consider the following two transactions:T1: READ(A,t); t:=t+2; WRITE(A,t); READ(B,t); t:=t*3; WRITE(B,t);T2: READ(B,s); s:=s*2; WRITE(B,s); READ(A,s); s:=s+3; WRITE(A,s);where READ(A,t) means read eleme nt A into local variable t and WRITE(A,t) is similarlydefined.With respect to modification of the database elements A,B, answer the following questions:a. [5] Pick values for t,s and an ordering of the execution of the operations in the twotransactions to show that the result could be different than a serial execution of thetransactions (remember that there are two possible serial executions, T1,T2 and T2,T1).6b. [5] Suppose the transactions are guarded by begin transaction and commit (i.e. trans-action isolation is enforced by the database system). Pick two of the four SQL isolationlevels discussed in class and explain differences in the execution of the two transactionsunder the two isolation levels.5. Data-mining [10]a. [5] Explain what is the difference between ROLAP and MOLAP.b. [5] Briefly describe the frequent itemset problem and hot the A-priori algorithm findssuch frequent itemsets.6. Miscellaneous Questions [15] Answer the following questions. Be precise and concise.a. [3] Describe the difference in meaning between the terms relation and relation schema7b. [3] Why are functional dependencies important? Why should they be preserved?c. [3] Why database systems have their own security and access control mechanisms (asopposed to using the operating systems mechanisms).d. [3] Explain the differences, from a database perspective, between Object-Relational andObject Oriented.e. [3] Why is concurrency control