CS 347 -- Assignment #5

File Structures

Due Friday, November 2 by 5pm

Draw a B+ tree that initially contains an empty file. Assume each block has a capacity of 3 index records or 3 data records (tuples).

(a) Draw the tree after inserting each of the following records whose keys are:

11, 37, 53, 31, 2, 75, 16, 61

(b) Start from your tree in (a), and draw the tree after deleting each of the following records whose keys are:

75, 11, 31
Draw an extendible hash structure that initially contains an empty file. Assume each block has a capacity of 3 data records (tuples). Draw the structure after inserting each of the following records whose extended hash keys are:

0101, 0000, 1101, 0101, 0100, 0100, 1011, 1000, 1011
You are to draw an ISAM structure whose data nodes are initially filled with 2 records, although the block capacity is 3 records.

(a) Draw the initial tree that contains the following records whose keys are:

2, 11, 31, 37, 53, 75

(b) Using the tree in (a), draw the tree after inserting each of the following records whose keys are:

48, 36, 79, 84, 16

(c) Start from your tree in (b), and draw the tree after deleting each of the following records whose keys are:

11, 36, 79
Relation A(A1,...,A9) has 9 attributes, the first four (A1...A4) are indexed. The selectivity of attribute Ai is .01*i. That is, A1 has selectivity .01, A5 has selectivity .05, etc. How are the following SQL statements processed? Say explicitly the actions that are taken by a DBMS on behalf of that statement, clearing indicating what index records are accessed and updated.

(a) select * from A where A1=1

(b) update A set A6=A6*2 where A8=8

(c) select * from A where A8=8 and A4>4

(d) update A set A2=2 where A2=5

(e) select * from A where A2=2 and A3=3

(f) delete from A where A9=9

(g) update A set A7=7 where A4=4

(h) delete from A where A3=3

(i) select * from A where A2<2 and A6=6