A PARTS file with Part# as the key field includes records with the following

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



Price: £ 48

100% Plagiarism Free & Custom Written, Tailored to your instructions

Leave your Comments


Can't read the image? click here to refresh