Database Administrators Asked by Kevin Wu on December 23, 2020
On Wikipedia, it says:
The decomposition is a lossless-join decomposition of R if at least one of the following functional dependencies are in
F+ (where
F+ stands for the closure for every attribute or attribute sets in
F):
R1 ∩ R2 → R1 or R1 ∩ R2 → R2
Unfortunately, I do not understand this criteria. It is known that the decomposition is lossless if the join of R1 and R2 is R, but how is this derivable from the criteria above?
Here is the proof.
(⇐) Suppose T1 ∩ T2 → T1 ∈ F+. Let r a valid instance of R⟨T, F⟩, and s = π T1(r ) ⨝ π T2(r ). If t ∈ s, then we need to show that t ∈ r. By definition of s, we have two tuples u and v in r such that u [T1] = t [T1], v [T2] = t [T2] and u [T1 ∩ T2] = v [T1 ∩ T2] = t [T1 ∩ T2]. Since T1 ∩ T2 → T1 ∈ F+, then u [T1] = v [T1] and so t = v.
The case T1 ∩ T2 → T2 ∈ F+ can be proved in the same way.
(⇒) Suppose that, for each valid instance r of R⟨T,F⟩, r = π T1(r ) ⨝ π T2(r ); we need to show that T1 ∩ T2 → T1 ∈ F+ or T1 ∩ T2 → T2 ∈ F+.
Using reductio ad absurdum, we suppose that none of the two functional dependencies is implied by F. Let W = (T1 ∩ T2)+, Y1 = T1 − W and Y2 = T2 − W. Y1 and Y2 are not empty by hypothesis, and W, Y1 and Y2 are a partition of T. For each Ai ∈ T, 1 ≤?? i ≤?? k, we consider two values ai, ai′ ∈ dom(Ai), such that ai ≠ ai′. Let’s build a relation r with attributes WY1Y2 constituted by the two tuples:
e1[Ai] = ai, 1 ≤? i ≤?? k ?
e2[Ai] = ai if Ai ∈ W; ai′ if Ai ∈ Y1Y2
r satisfies each dependency V → Z ∈ F. In fact, if V ⊈ W, then e1[V] ≠ e2[V], and r obviously satisfies the dependency. If V ⊆ W, then (T1 ∩ T2) → V, so (T1 ∩ T2) → Z for transitivity, from which Z ⊆ W, and so e1[Z] = e2[Z], an this implies that r satifies the dependency. Moreover, since Y1 and Y2 are not empty, π T1 (r ) and π T2 (r ) contain two tuples and their natural join contains four tuples, more than those of r:
π T1 (r ) ⨝ π T2 (r )
contradicting the hypothesis.
Answered by Renzo on December 23, 2020
1 Asked on October 27, 2021 by erwin-zangwill
3 Asked on October 27, 2021 by patrickdavey
0 Asked on October 27, 2021 by akhilesh-kedarisetty
1 Asked on October 27, 2021 by d4bbi
1 Asked on March 1, 2021 by mikhail-aksenov
0 Asked on February 27, 2021 by plisken
2 Asked on February 25, 2021 by develjoe
1 Asked on February 23, 2021 by rameez
4 Asked on February 23, 2021 by user1870400
1 Asked on February 22, 2021 by ramy-khalifa
0 Asked on February 20, 2021 by gfbaggio
0 Asked on February 19, 2021 by immobiluser
3 Asked on February 19, 2021 by ammar-faizi
1 Asked on February 19, 2021 by radu-dumbrveanu
2 Asked on February 18, 2021 by gandalf-stormcrow
1 Asked on February 17, 2021 by caltor
Get help from others!
Recent Answers
Recent Questions
© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP