Homework Problems

All homework will be due before class. 

HW

Problems

1

11.1, 11.3, 11.4, 11.13,11.19

2

12.5,12,6,12,7,12,12,12,13,12.18, PR1.PartI

3

13.1,13.2, S1, PRI.PartII

4

PR2(Query Optimization)

5

15.8,15.10(please list all the equivalent serial schedules as well),15.11,15.12, S2

6

16.3,16.4,16.14,16.24,16.25,S3

7

S4, PR3

8

10.3,10.14,PR4

9

19.6,19.7,19.18

 Projects

All projects will be due before class. 

PR

Description

1

Part I, Part II

2

Query Optimization

3

Transactions

4

Data Warehousing

Supplement Problems:

S1: Suppose we want to process the natural join of two tables: movie_star(star_name, age, address …)  and contract(movie_name, star_name …) on attribute star_name. The table movie_star has 1,000 tuples (100B each) and the table contract has 10,000 tuples (75B each).  The star_name is 18B and a pointer is 2B. Supposed our block size is 2KB. Assume we have 10 memory buffers for input/output. Allocate buffer properly for each of the following join strategies. Report the lowest cost for each strategy together with the memory allocation you use.

1)      Block nested loop join with movie_star as outer loop

2)      Block nested loop join with contract as outer loop

3)      Indexed nested loop join

a.       primary B+ tree on attribute star_name of table movie_star, table contract as outer loop

b.      secondary B+ tree on attribute star_name of table contract, table movie_star as outer loop

c.       Which (a or b) is more efficient? Justify your answer.

4)      Merge join, assuming movie star is ordered, contract is not, use external merge sort to sort contract, and all contracts with same star_name fit into one disk block

5)      Hash join

Suppose each disk block access is 10 milliseconds, estimate the disk access time for 1) to 5).

S2: Let Wi(j) denote a write operation by Transaction Ti on item j in the database. Let Ri(j) denote a read operation by Transaction Ti on item j in the database. Consider a database with items X, Y, Z and transactions T1, T2, and T3. Each transaction commits right after its last operation is completed.

 

Transaction T1: R1(X), W1(X), R1(Y), W1(Y)

Transaction T2: R2(Z), R2(X), W2(X), R2(Y), W2(Y)

Transaction T3: R3(Y), R3(Z), W3(Y), W3(Z)

 

 

S1:R3(Y),R3(Z),R1(X),W3(Y),W1(X),R2(Z),W3(Z),R2(X),W2(X), R1(Y),R2(Y),W1(Y),W2(Y)

S2:R1(X),W1(X),R1(Y),W1(Y),R3(Y),R3(Z),W3(Y),W3(Z),R2(Z), R2(X),W2(X),R2(Y),W2(Y)

S3:R3(Y),R3(Z),R1(X),W1(X),W3(Y),W3(Z),R2(Z),R2(X),W2(X), R2(Y), W1(Y), R1(Y),W2(Y)

 

a.       Draw conflict graphs and state if S1, S2 and S3 are conflict-serializable.

b.      Are S1,S2, and S3 recoverable?

c.       Are S1,S2, and S3 cascadeless schedules?

S3: Given following transactions:

1.      T1: r1(x)w1(y)r1(x)r1(z)r1(y)w1(z)

2.      T2: w2(x)r2(x)r2(y)w2(y)

3.      T3: r3(x)r3(y)r3(z)w3(x)w3(z)

and following schedules:

4.      S1: r1(x)w1(y)w2(x)r1(x)r2(x)r1(z)r3(x)r1(y)w1(z)r3(y)r2(y)w2(y)r3(z)w3(x)w3(z)

5.      S2: r1(x)w1(y)r1(x)w2(x)r2(x)r1(z)r3(x)r1(y)w1(z)r3(y)r2(y)w2(y)r3(z)w3(x)w3(z)

6.      S3: r1(x)w1(y)r1(x)w2(x)r2(x)r1(z)r3(x)r1(y)w1(z)r2(y)w2(y)r3(y)r3(z)w3(x)w3(z)

Answer questions (a), (b), and (c).

 (a) Which schedule(s) can be the results of conservative 2PL (assuming binary locks are obtained right before the first operation of the transaction and released right after the last read or write operation on variables) ? rigorous 2PL (assuming locks are obtained right before the first read or write operation on variables and released right after the last operation of the transaction)? Justify your answers.

(b) Which schedules(s) can be the results of timestamp ordering? Justify your answers.

(c) Which validations are allowed and disallowed according to the following validation schedule based on the given three transactions. Justify your answers.


S4: Describe the recovery process using undo, redo, and undo-redo logging with non-quiescent checkpointing for crash 1 and crash 2 (assuming crash 1 did not happen when considering crash 2) illustrated in the following figure. Note <START CKPR(T)> denotes: when the check point starts, T is the only active transaction. Also note that new transactions may start at any time and are not specified in the figure. You will need to include them in your discussion.