†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† Name___________________

 

CPTR349Spring '04 (100 total points)††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† Exam 3

 

1.      Terminology:Select the word the best matches the description given.Each word will be used exactly once.(2 points each)

 


a.       clustered

b.      disks

c.       heap

d.      index

e.       log

f.        page

g.       recoverable schedule

h.       serial schedule

i.         serializable schedule

j.        sorted

k.      tapes

l.         transaction


 

 

____ a block of data, usually 4K or 8K, that is read from external storage into memory

 

 

____ storage medium that supports random access of information

 

 

____ storage medium in which pages must be read sequentially; relatively cheap and usually used for archival storage

 

____ file structure in which data records are in no particular order

 

 

____ file structure in which data records are kept in some specific order

 

 

____ a data structure used to access data records more quickly

 

 

____ an atomic sequence of database actions (reads/writes)

 

 

____ a file containing the history of all actions carried out by a DBMS, used for crash recovery

 

 

____ describes an index in which the data entries are in the same order as the data records

 

 

____ a schedule that does not interleave the actions of different transactions

 

 

____ a schedule that is equivalent to some serial execution of the transactions

 

 

____ a schedule in which transactions commit only after (and if) all transactions have committed.


2.      Give one reason why a DBMS stores data on external storage (disk)?(3 points)

 

 

 

 

 

3.      Why are I/O costs important in a DBMS?(3 points)

 

 

 

 

 

4.      What is a record id (RID)?(3 points)

 

 

 

 

 

5.      Given a recordís id, how many I/Os are needed to fetch it into the main memory of the computer?(3 points)

 

 

 

 

 

6.      Build a hash index for the following database that has 4 hash buckets.Use mod 4 for the hash function.Record ids should have the form <page#, record#> as in the homework.(5 points)

 

 


7.      Suppose that for a given database, the data records are sorted and a clustered B+ tree index has been built.Suppose that a new record is to be inserted into a page that is already full.

 

a.       Describe what the DBMS would do to the data record(s) in this case.(Drawings may help in your explanation.)(5 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b.      Describe if and how this would affect the B+ tree index.(4 points)


8.      Remove the last page from the exam to use as a reference.Give brief explanations for each of the following:

 

a.       Why is the file scan for the heap and/or sorted file equal to BD? (2 points)

 

 

 

 

 

 

 

 

 

 

 

 

b.      Why is the file scan for the file with the clustered B+ tree equal to 1.5 times that of the heap or sorted file? (2 points)

 

 

 

 

 

 

 

 

 

 

 

 

c.       Why is the equality search for the file with the clustered B+ tree equal to DlogF1.5B?(2 points)

 

 

 

 


9.      With respect to query evaluation and optimization, what can we realistically expect from a DBMS?(4 points)

 

 

 

 

 

 

 

 

 

 

10.  With respect to query optimization, describe pipelining and its advantages.(4 points)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

11.  Why is it a good idea to push a selection earlier, or down the RA tree, when optimizing a query?(4 points)

 

 


12.  For each of the following, indicate if it is the responsibility of the DBMS (D) or the application programmer (A).(6 points)

 

____ Make sure that a single transaction leaves the database in a consistent state if the transaction is executed all by itself

 

____ Make sure that multiple transactions running simultaneously will yield the same result as if they were run individually, one after the other

 

____ Make sure that the database is in a consistent state after the system is restarted after a crash.

 

13.  Below are the three anomalies that can occur with interleaved transactions.For each one give an example of an interleaving of two transactions that demonstrates the anomaly.(9 points)

 

a.       Reading uncommitted data

 

 

 

 

 

 

 

 

 

 

b.      Unrepeatable read

 

 

 

 

 

 

 

 

 

 

 

c.       Overwriting uncommitted data

 

 

 

 

 


14.  Why does the DBMS interleave transactions?(2 points)

 

 

 

 

15.  Assume that two transactions, T1 and T2, use the same object and are interleaved by a DBMS that uses Strict2PL locking.Suppose transaction T1 requests the lock that appears column 1 (S for shared, X for exclusive) followed by the request by T2 that appears in column 2.Fill in columns 3 and 4 as follows:In column 3, enter yes or no to indicate whether or not Strict 2PL will allow the lock requested by T2.In column 4, if the answer in column 3 is no, enter the anomaly (reference question #13) that is averted by Strict2PL.(8 points)

 

T1

T2

Allowed (yes or no)

Anomaly averted

X

X

 

 

S

X

 

 

X

S

 

 

S

S

 

 

 

 

16.  Give an example of two interleaved transactions demonstrating how deadlock can occur.(4 points)

 

 

 

 

 

 

 

 

 

 

 

 

17.  Briefly describe what the DBMS will do when it detects a deadlock.(3 points)