CS 4163/6523: Introduction to Database Systems - Homework 2
CS 4163/6523: Introduction to Database Systems
Basics
CS 4163/6523: Introduction to Database Systems Homework 2 Your submission containing the solutions to the following problems must be typed in 12pt font with 1” margins. The process followed to generate answers must be evident in your solution.
Problem 1 (25 points): Consider the set of attributes R = {ABCDEF}, and the FD set X = {AB → C, AC → B, AD → E, B → D, BC → A, E → F}. For each of the following decompositions, check if it is dependency-preserving (5 points) and satisfies the lossless-join property (8 points). Determine the normal form of each decomposition by identifying the keys and normal forms for each relation in the decomposition (12 points): (a) D1={AB, BC, ABDE, EF}, (b) D2={ABC, ACDE, ADF}.
Problem 2 (15 points): Use the FDs in Problem 1 to decompose the universal relation into 3NF and BCNF using algorithms 15.4 and 15.5 respectively.
Problem 3 (20 points): Exercises 20.23 and 20.24 from the textbook. To determine serializability, show all conflicting operation pairs and the precedence graph. For determining recoverability, explain why the given schedules are non-recoverable, recoverable, cascadeless or strict.
Problem 4 (25 points): In the following schedule for transactions, wi (A) and ri (A) correspond to read and write operations by transaction i on item A and RLiA and W LiA refer to read and write locking operations on item A by transaction i. RL1X r1 (X)RL2Z r2 (Z)RL3X r3 (X)RL1Z r1 (Z)RL2Y r2 (Y )W L2Z w2 (Z)W L1X w1 (X)W L3Y w3 (Y )W L2Y w2 (Y ) (a) Insert unlock operations into the above schedule so that locks are released as soon as possible while maintaining two-phase locking (2PL) protocol. Which version of 2PL (basic, conservative, rigorous) does this schedule correspond to? Show the corresponding wait-for graph and explain if this schedule produces deadlocks or not. (14 points) (b) When and what transactions, if any, will be aborted if wait-die and wound-wait protocols were used on this schedule? (6 points) (c) For this part, ignore the locking operations in the schedule. When and what transactions, will be aborted by Basic Timestamp Ordering (TO)? What will be the difference in execution between Basic TO and Thomas’s Write Rule? (5 points)
Problem 5 (10 points): Exercises 22.23, 22.24 from the textbook.
Problem 6 (5 points): Exercises 30.34 from the textbook.
