Assignment 3 Advanced Data Management (CP5520) – 2016 Aim: This assignment is designed to evaluate/improve your critical thinking and problem solving skills. It also evaluate/improve your Information Literacy Skill (i.e. the ability to select and organize information and to communicate it creatively and ethically). 1. Consider theLIBRARY relational schema shown in Figure 1 (i.e. Figure 6.14 of your textbook) which is used to keep track of books, borrowers, and book loans. Referential integrity constraints are shown as directed arcs in Figure 6.14. Figure 1: Specify the query: How many copies of the book titled The Lost Tribe are owned by the library branch whose name is "Sharpstown"? (a) in relational algebra, [1 mark] 1 (b) in tuple relational calculus, [1 mark] (c) in domain relational calculus. [2 marks] 2. A PARTS file with Part# as the key field includes records with the following Part# values; 9, 11, 3, 20, 2, 31, 6, 15, 5, 4, 8. (a) Suppose that the search field values are inserted in the given order in a B+-tree of order p = 4 and Pleaf = 3; show how the tree will expand (after inserting each Part#), and what the final tree would like. [5 marks] (b) Repeat item (a), but use a B-tree of order p = 4 instead of a B+-tree (see Chapter 14 of your textbook for relevant algorithms). [5 marks] 3. Consider the SQL query: SELECT Fname, Lname, Address FROM EMPLOYEE, DEPARTMENT WHERE Dname='Research' AND Dnumber=Dno in which, retrieves the name and address of all employees who work for the 'Research' department. Assuming that the EMPLOYEE relation is: EMPLOYEE (Fname:string, Lname:string, Ssn:string, Bdate:date, Address:string, Sex:char, Salary:real, Super ssn:string, Dno:integer) where the size of each field is as follows: Fname 20 bytes Lname 20 bytes Ssn 10 bytes Bdate 8 bytes Address 40 bytes Sex 1 byte Salary 4 bytes Super ssn 10 bytes Dno 1 byte That is, records are fixed (114 bytes). The DEPARTMENT relation is: DEPARTMENT (Dname:string, Dnumber:string, Mgr ssn:string, Mgr start date:date) where the size of each field is as follows: Dname 20 bytes Dnumber 1 byte Mgr ssn 10 bytes Mgr start date 8 bytes That is, records of DEPARTMENT relation is fixed and each record contains 39 bytes. 2 (a) Draw the initial (canonical) query tree for this query, and then show (step by step, with some justifications/explanations) how the query tree is optimized by the algorithm outlined in Chapter 15. [4 marks] (b) Assuming that EMPLOYEE relation has 150 records and DEPARTMEN relation has 8 records, compare (in terms of the number of bytes that must be transfered) the initial and final query trees of part (a). [3 marks] 4. Consider schedules S1, S2, S3, and S4 below. S1 : r1(X), r2(Z), w1(X), r3(X), c1, w2(Z), r2(Y ), w3(X), w2(Y ), r3(Y ), c2, w3(Y ), c3; S2 : r1(X), r2(Z), r2(Y ), w1(X), r3(X), c1, w2(Y ), w3(X), c3, r2(X), w2(Z), w2(X), c2; S3 : r1(X), r2(Z), w1(X), r3(X), w2(Z), r2(Y ), w3(X), w2(Y ), r3(Y ), w3(Y ); S4 : r1(X), r2(Z), r2(Y ), w1(X), r3(X), w2(Y ), w3(X), r2(X), w2(Z), w2(X); (a) Apply the basic timestamp ordering algorithm to schedules S3 and S4. Determine whether or not the algorithm allows the execution of the schedules, and discuss cascading rollback (if any). Hints: each operation takes one time unit, and timestamp of each transaction is the time associated to its first operation. For example, timestamps of transactions T1, T2, and T3 in schedule S2 are 1,2, and 5 (respectively). [3 marks] (b) Apply the strict timestamp ordering algorithm to schedules S1, and S2. Determine whether or not the algorithm allows the execution of the schedules, show locked items and discuss the cascading rollback (if any). Also, for each completed schedule, show the strict schedule that has been executed by this algorithm. [3 marks] (c) Apply the multiversion technique based on timestamp ordering algorithm to schedules S3 and S4. Determine whether or not the algorithm allows the execution of the schedule. For any data item, show versions with their associated timestamps. [3 marks] 3