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




Allowed (yes or no)

Anomaly averted



















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)