# Assignment 5 Database System _SOLUTION

Problem 1 [20 pts] Prove the following (if it is one of the three basic rules, you need to prove by deﬁnition). 1. Given A → B, and B → C, we have A → C. 2. Given A → B, and C → D, we have AC → BD.Problem 2 [30 pts] Consider a schema R=ABCDE (i.e., 5 attributes, A, B, C, D, and E), and a set of functional dependencies F={AB → C, AC → B, B → D, D → E} that hold over R. 1. What are the keys for schema R? 2. Show the attribute closure of BC. 3. Is R in BCNF? Why or why not? 4. Is R in 3NF? Why or wny not? 5. If we decompose R into R1 = ABC and R2 = BDE, is this decomposition a lossless join decomposition? Prove your claim. 6. Is R1 in BCNF or 3NF? Why or why not? 7. Is R2 in BCNF or 3NF? Why or why not? Problem 3 [20pts] In the following schedules, Ri(A) stands for Read(A) by transaction i and Wi(A) stands for write(A) by transaction i. for each of the following schedules, show if it is a serializable schedule and give an equivalent serial schedule if it is. Show all the conﬂict operations. 1. R1(A) R2(B) W3(A) R2(A) R1(B) 2. R1(A) R2(B) W1(A) R3(C) W2(B) W3(C) R4(D) R4(A) W4(D) 3. R3(E) R1(D) W2(C) W3(A) R1(E) W4(B) R1(B) W3(E) R4(A) W4(C) Problem 4 [30pts] Assume the following database exists: • Employee-Table (ssn, name, salary) – E1(132, Smith, 20K) – E2(456, Kelley, 40K) – E3(678, Johnson, 400K) – E4(792, Preston, 40K) – E5(865, Johnson, 60K) ... • DPT-Table(dnumber, dname, budget) – D1(1, Marketing, 1M) – D2(2, Engineering 2M) – D3(3, R&D, 4M) – D4(4, HR, 1M) ... For each of the schedules below, explain if it is valid in: • serializable isolation level • repeatable read isolation level 1. T1.R(E1), T1.W(E1), T2.R(E2), T2.W(E2), T1.R(D1), T1.commit, T2.commit 2. T1.R(E1), T1.W(E1), T2.R(E2), T2.W(E2), T2.W(E1), T1.R(E1). T1.commit, T2.commit 3. T1.R(E where salary40K and salary<100K), T2.Insert(into E, (999, Bob, 50K)), T2.commit, T1.R(E where salary40K and salary<100K), T1.commit 4. T1.R(E where salary40K and salary<100K), T2.Insert(into E, (999, Bob, 50k)), T1.R(E where salary40K and salary<100K), T2.commit, T1.commit. 5. T1.R(E where salary40K and salary<100K), T2.Update(set E.name=Alien where salary=60K), T2.commit, T1.R(E where salary40K and salary<100K), T1.commit.