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 mark