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