CS632 Prelim IAA. Demers28 Mar 2003 – due 4 April 2003I am so far behind (equivalently, dissatisfied with what I’ve got) that I am forcedto post this is stages. This is stage A. The next stage will appear within a coupleof days at the latest, with due date adjusted.As usual, you may consult others for ideas and proof approaches, but pleasereference your sources and write up answers independently.1 Armstrong Relations for FDsLet R(U ) be a relation schema, and let F be a set of FDs over it. An ArmstrongRelation for F is a relation instance r that satisfies F but violates every FD notin F+.Question 1: Is there an Armstrong Relation for every finite set of FDs?If yes, show how to construct one (no need for efficiency).If no, give a counterexample – a set of FDs along with an argument why noArmstrong Relation exists.2 Dependencies as First Order FormulasHere we generalize FDs and JDs to a framework reminiscent of DRC.LetR(U) = (R1(X1), . . . , Rn(Xn))be a relation scheme. Let {x1, x2, . . .} be a countable set of variables. As usual,we use symbols like y, zi, w0and so forth as arbitrary variables from this set.We allow two kinds of atomic formulas (atoms),1a relation atom of the form Ri(y1, . . . , ym) which is true when thetuple hy1, . . . , ymi is in the relation instance rinamed Ri; andan equality atom of the form y = z, which is the usual equality for-mula.Now we define a dependency as a first order formula of the form(∀x1. . . ∀xm)[φ(x1. . . xm) ⇒ (∃y1. . . ∃yk)ψ(x1, . . . , xm, y1, . . . , yk)]whereformula φ is a conjunction of relation atoms in which every variablexiis mentioned; andformula ψ is a conjunction of relation and equality atoms in whichnone of the equality atoms mentions a variable yj.We classify dependencies along four axes:Full vs embedded: A dependency is full if it has no existential quantifiers.Tuple-generating vs equality-generating: A tuple-generating dependency (tgd) isone in which no equality atoms occur (in either the left or right hand sides ofthe implication). An equality-generating dependency (egd ) is one in which theright hand side of the implication consists of a single equality atom.Typed vs untyped: A typed depe ndency is on for which there is some assignmentof variables to relation attributes (column positions) such that (1) variables inrelation atoms always occur in their assigned column positions, and (2) eachequality atom compares two variables assigned to the same column position.Single-head vs multi-head: A dependency is single-head if the right hand side ofthe implication involves only a single atom; it is multi-head otherwise.The formulas used in dependencies are a subset of the formulas used in DRC.so we can use the DRC definition to say when a dependency δ is satisfied byan instance r. And we can use the usual notion of implication: if Γ is a set ofdependencies and δ is a dependency, then Γ |= δ if every instance that satisfiesall the formulas of Γ also satisfies δ. We extend this to Γ |= Γ0in the naturalway, and define equivalence by Γ ≡ Γ0iff both Γ |= Γ0and Γ0|= Γ.It is easy to see that every (typed) dependency is equivalent to a finite setof typed tgd’s and (typed) single-head egd’s. The tgd’s cannot in general besingle-head, as you will show below.2Problem 2a: Show how to express any FD as a (full) typed egd.Show how to express any JD as a full typed tgd.Show how to express any ID as an untyped embedded tgd. (recall an ID is an in-clusion dependency, a pair of sequences of attribute names hA1. . . Ak, B1. . . Bki,where the ID is satisfied if every sequence of values occurring in the A attributesof any tuple also occurs in the B attributes of some (other) tuple).Problem 2b: Consider the following multi-head tgd over a binary relationscheme R(A, B):(∀x1, x2, x3, x4, x5)[(R(x1, x2) ∧ R(x3, x2) ∧ R(x3, x4) ∧ R(x5, x4))⇒ (∃y)(R(x1, y) ∧ R(x5, y))]Argue that there is no set of single-head tgd’s that is equivalent to it.Problem 2c: Exhibit an infinite se quence τ1, τ2, . . . of typed tgd’s over a bi-nary relation such that each is strictly weaker than the previous one; that is,τi|= τi+1but τi+16|= τifor each i = 1.Problem 2d: In class we discussed the use of tableaux and the Chase proce-dure to test implication for FDs and JDs. Show how to adapt this techniqueto the more general cas e of full typed dependencies. That is, let Σ is a set offull typed dependencies, and τ is a full typed dependency (either a (full) typedegd or a full typed tgd – you will need to treat these cases separately). Giveappropriate definitions of initial tableau, of CHASEΣ, and of the final test todetermine whether Σ |= τ.A detailed proof of correctness is not