Aim: This assignment is designed to evaluate/help improve your critical thinking and problem solving skills. It also evaluates/helps improve your Information Literacy Skill (i.e. the ability to select and organize information and to communicate it creatively and ethically).

1. Consider the LIBRARY relational schema shown in Figure 1 (Figure 6.14 of your text- book) which is used to keep track of books, borrowers, and book loans. Referential integrity constraints are shown as directed arcs in Figure 6.14.

Specify the query:

Retrieve the number of copies of the book titled "The Theory of Relativity" that are owned by the library branch named "Central"

(a )in relational algebra,

(b) in tuple relational calculus,

(c) in domain relational calculus.

2. A PARTS file with Part# as the key field includes records with the following Part# values; 8, 12, 6, 20, 2, 31, 3, 15, 5, 4, 9.

(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 look like.

(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).

3. Consider the SQL query: SELECT Fname, Lname, Address

FROM EMPLOYEE, DEPARTMENT
WHERE Dname=‘Research' AND Dnumber=Dno
which retrieves the names and addresses 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
Superssn 10 bytes
Dno 1 byte
That is, records size is fixed (114 bytes). The DEPARTMENT relation is:
DEPARTMENT (Dname:string,Dnumber:string, Mgrssn:string, Mgrstart date:date) where the size of each field is as follows:
Dname20 bytes Dnumber1 byte
Mgrssn 10 bytes
Mgrstartdate 8 bytes

That is, record size of DEPARTMENT relation is fixed and each record contains 39 bytes.

(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.

(b) Assuming thatEMPLOYEE relation has 150 records and DEPARTMENT relation has 8 records, compare (in terms of the number of bytes that must be transferred) the initial and final query trees of part (a).

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).

(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 cascading rollback (if any). Also, for each completed schedule, show the strict schedule that has been executed by this algorithm.

(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.