COP 4710 Database Systems Assignment 4 | Complete Solution

Problem 1 [20′ = 2 ∗ 10′]
We want to index the following key values based on an extensible hash table. Such keys are inserted into the database in the order of 21, 35, 49, 56. The hash function h(x) for the key x is (x mod 32). Namely, the hash value is the remainder of the key x divided by 32, and it is a 5-bit value. Assume each block holds 2 tuples.

1. Please draw the hash table containing the hash structure in main memory and the data blocks on disks after these four keys are inserted. Make sure to indicate the number of bits used during hashing;
2. We keep inserting 82 and 89 into the hash table. Draw the table to refl the new values. Be sure to indicate the number of bits used during hashing.

Problem 2 [20′ = 2 ∗ 10′]
1. Explain why it is not necessarily desirable to execute multiple transactions as a serial schedule in a database system;
2. If two transactions consist of 7 and 3 read/write actions, respectively, how many interleaving of these two transactions are there?

Problem 3 [15′ = 5′ ∗ 3]
Suppose that the consistency constraint on the database is 0 ≤ A ≤ B. Tell whether each of the following transactions preservers consistency:
1. A := A + B; B := A + B;
2. B := A + B; A := A + B
3. A := B + 1; B := A + 1;
Problem 6 2

Problem 4 [15′ = 5′ ∗ 3]
Show the undo-log records of each of the following transactions (call each T ), assuming that initially A = 5 and B = 10 and both values are stored in memory.
1. A := A + B; B := A + B;
2. B := A + B; A := A + B
3. A := B + 1; B := A + 1;

Problem 5 [15′ = 5′ ∗ 3]
The following is a sequence of undo-log records written by two transactions T and
U : < START T >; < T, A, 10 >; < START U >; < U, B, 20 >; < T, C, 30 >;
< U, D, 40 >; < COMMIT U >; < T, E, 50 >; < COMMIT T >. Describe the
actions of the recovery manager, including changes to both disk and the log, if there is a crash and the last log record to appear on the disk is
1. < START U >
2. < T, E, 50 >
3. < COMMIT T >

Problem 6 [15′ = 5′ ∗ 3]
Repeat the Problem 5 for redo logging.
COP 4710: Database Systems Assignment 4