程序代写代做代考 concurrency Functional Dependencies database CS 411: Database Systems Fall 2018 Homework

CS 411: Database Systems Fall 2018 Homework
3 (Due by 23:59 CDT on October 26)

October 15 2018

1 Relational database design
1. Consider the following relations R1 and R2. What are the normal forms (BCNF,

3NF) that each of the relations are in? Justify why R1/R2 is or is not in each of
these normal forms. (4 Points)

(a) R1(A,B,C,D,E) with a set of functional dependencies FD = {D →
B,CE → A}

(b) R2(A,B,C,D,E) with a set of functional dependencies FD = {A →
E,BC → A,DE → B}

2. Consider the relation R(A,B,C,D,E, F,G,H) with the functional dependen-
cies FD = {A→ BC,ABCD → E,EF → GH,ABDF → EC}

(a) Compute the minimal cover of FD. Show the steps of your computation.
(4 Points)

(b) Decompose the relation, as necessary, into a collection of relations that are
in 3NF. (4 Points)

3. Consider the relation R(A,B,C,D,E, F ) and the functional dependencies F =
{A→ B,C → AF,B → D}

Are the following decompositions lossless? Explain your answer. (6 Points)

(a) (AEF )(ABCDE)

(b) (CB)(ACDEF )

4. Consider the relation R(A,B,C,D,E, F ) with the functional dependencies F =
{A→ B,C → AD,BE → DF}

(a) Decompose the relation, as necessary, into a collection of relations that are
in BCNF. Explain which dependency violation you are correcting by your
decompositions. (6 Points)

(b) Do we have a unique BCNF decomposition for R? (2 Points)

5. Consider the relation R(A,B,C,D,E, F ) with the functional dependencies FD =
{A→ BD,AC → DE,D → F}.

Is there a BCNF decomposition for R that preserves the functional dependen-
cies? Justify your answer. (4 Points)

2 Updates and Transactions
1. Consider the following schedules S1 and S2 by transactions T1, T2 and T3 on

database objects A and B.

S1 : R1(A), R3(B),W1(B), R2(B),W3(A),W1(A), R3(A)

S2 :W1(A), R1(B),W2(B),W1(B), R2(A),W3(B), R3(A)

(a) Determine if schedules S1 and S2 are conflict-serializable by drawing a
precedence graph of transactions. (2+2 = 4 points)

(b) For the same schedules S1 and S2, determine if they are serializable. If
serializable, then give a corresponding serial schedule. If not serializable,
provide a suitable justification. (2+2 = 4 points)

2. Consider another set of schedules S1 and S2 by transactions T1, T2 and T3 on
database objects A, B and C

S1 : R2(A), R1(B), R3(C), R2(B), R1(C),W2(A),W1(B),W3(C)

S2 : R1(C),W2(A),W3(B),W3(C), R2(B),W2(B), R2(A), R3(C)

(a) Determine whether schedules S1 and S2 can be produced by a Two Phase
Lock (2PL) scheduler. If yes, provide a table with placements of shared
locks (Slock), exclusive locks (Xlock) and lock releases (Rel) that follows
2PL and obeys lock-compatibility restriction. Structure the table so that
each column corresponds to a single transaction and each row has a single
operation. Or else, give a partial table marked with the first point of the
schedule where a transaction fails to get a required lock. (4 points)

(b) For the same schedules S1 and S2, determine whether schedules S1 and S2
can be produced by a strict Two Phase Lock (2PL) scheduler. Similar to
part (a), provide the corresponding lock placement table. (4 points)

3. Given two transaction T1 and T2 operating on objects A, B and C.

T1 : R1(A), R1(B),W1(B), R1(C)

T2 : R2(A),W2(C), R2(A),W2(A)

Consider two operating scenarios of isolation levels for these transactions.

• Scenario 1: Read Committed (T1) and Repeatable Read (T2).
• Scenario 2: Repeatable Read (T1) and Repeatable Read (T2).

For each scenario, answer the following questions:

(a) Rewrite each transaction with appropriate locks for each of the below sce-
narios. For full credit, place the locks to maximize concurrency in each
transaction. (2 + 2 = 4 points)

(b) Check whether a deadlock is possible. If deadlock is possible, then give
an example of a schedule in which deadlock happens under the assumed
isolation levels (Use a table to show the place of deadlock). If it is not
possible, provide a clear explanation that covers all allowed schedules. (2
+ 2 = 4 points)

4. Consider two transactions T1 and T2 operating on database objects A and B.
T1 : R1(A), R1(B),W1(B)

T2 : W2(A), R2(B),W2(B)

(a) What is the total number of possible schedules of transactions T1 and T2 ?
(1 point)

(b) Among the possible schedules of transactions T1 and T2, how many are
conflict-equivalent to the serial order (T1, T2) ? (2 point)

Related Posts