CS632 Prelim IBA. Demers3 Apr 2003 – due 10 April 2003At last here is the second part of the take-home. As usual, you may consultothers for ideas and proof approaches, but please reference your sources andwrite up answers independently.3 Vertical DecompositionsIn this exercise we extend our treatment of vertical decompositions and ade-quacy of representation.We start with a database schema containing a single relation, together withsome integrity constraints:R = (R(U)) and CRRelation R is over attributes U . For this exercise the set CRof integrity con-straints may contain functional dependencies (FDs) each of which applies to aparticular Si. It may also contain key dependencies (KDs):Key(X) ≡ X → Ubut these are just a special case of FDs.We let I(R) be the set of all instances of R, whether or not they satisfy CR;and L(R) be the set of legal instances, which are required to satisfy CR.We next introduce S and its constraints:S = (S1(U1), . . . , Sn(Un)) and CS1Here S has relations Si(Ui) satisfyingU = U1∪ U2∪ . . . ∪ UnThe set CSof integrity constraints may contain FDs and KDs, each of whichapplies to a particular Si.As above, I(S) is the set of all instances of S, whether or not they satisfy CS;and L(S) is the set of instances that satisfy CS.We use the standard transformation between R and S:ΠS: I(R) → I(S) and 1S: I(S) → I(R)these are respectively projection onto the attributes in Uiand (natural) join.Recall the first two of our definitions of adequacy:Def: Decomposition S is α-adequate ifΠS|L(R)↔ (ΠS(I(R)) ∪ L(S))That is, ΠSis a bijection between the specified sets. Note that ΠSneed notbe 1-to-1 when considered as a function on all of I(R), only when restricted toL(R) as above.Def: Decomposition S is β-adequate if it is α-adequate andΠS(I(R) − L(R)) ⊆ (I(S) − L(S))That is, in addition to being α-adequate, ΠSmaps inconsistent instances toinconsistent instances.In practice, we would like to be able to store the database according to thedecomposed scheme S, so we want to know that enforcing the constraints in CSis sufficient to guarantee consistency with respect to the original schema; thatis, satisfying CSshould guarantee that CRwould be satisfied as well.So here is yet another adequacy definition.Def: Decomposition S is φ-adequate ifΠS|L(R)↔ (L(S))that is, if ΠSis a 1-to-1 correspondence between consistent instances in L(R)and L(S).2Question 2a: We know that β-adequacy implies α-adequacy. What is therelation between β-adequacy and φ-adequacy? In each direction, either provethe implication or exhibit a counterexample.We now explore what happens when CSmay contain interrelational constraintsin the form of inclusion dep endencies (IDs). Recall an ID has the formSi[A1, . . . , Ak] ⊆ Sj[B1, . . . , Bk]and is satisfied if(∀t ∈ si)(∃t0∈ sj) t[A1, . . . , Ak] = t0[A1, . . . , Ak]Obviously an ID may b e either an interrelational or intrarelational constraint,depending on whether Siand Sjare the same. An interrelational ID is oftencalled a foreign key.Question 2b: (An aside). When discussing BCNF, which essentially reducesFDs to KDs, we argued that this was a good thing to do in practice because adatabase management system necessarily has a B-tree indexing implementation(or something equivalent), and it is possible to implement KDs efficiently usingthat functionality. Give a similar argument for IDs / foreign keys.Here is yet another normal form:Def: Scheme S is in IK normal form if CSconsists only of (intrarelational)KDs and (interrelational) IDs.Question 2c: Describe an algorithm that, starting with a s chema R = (R(U ))and a set CRof FDs, finds a φ-adequate decomposition (S, CS) in IK normalform.Is the resulting decomposition β-adequate as well?4 SerializabilityIn this question we will not consider multi-version schedules.Recall that for unrestricted transactions conflict serializability (CSR) is strictlystronger than view serializability (VSR). That is, every CSR schedule is nec-essarily VSR, but there exist VSR schedules that are not CSR. (Actually, weshowed this for transactions satisfying the requirement that no entity x is reador written more than once.)3For some more constrained transaction models this distinction disappears. Re-call in the restricted model (which prohibits blind writes by requiring that everyentity x written in a transaction must have been read by some earlier step ofthe transaction) a schedule is VSR if and only if it is CSR.For each of the following models, either give a schedule that is VSR but notCSR, or else argue that no such schedule exists.(3a) the very short transaction model: each transaction consists of a single(read or write) step.(3b) The short transaction model: each transaction consists of at most 2steps.(3c) The atomic write model: each transaction consists of a sequence of 0 ormore read steps, followed by a single write step that writes the values of 0 ormore entities atomically.(3d) The single write model: each transaction contains at most one write step(which writes a single entity).(3e) The review model: if an entity x is written by a transaction, then x mustbe read by some later step of the same transaction (a transaction is allowed toread the same entity more than