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 T_{1} ∩ T_{2} → T_{1} ∈ 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* [T_{1}] = *t* [T_{1}], *v* [T_{2}] = *t* [T_{2}] and *u* [T_{1} ∩ T_{2}] = *v* [T_{1} ∩ T_{2}] = *t* [T_{1} ∩ T_{2}]. Since T_{1} ∩ T_{2} → T_{1} ∈ F^{+}, then *u* [T_{1}] = *v* [T_{1}] and so *t* = *v*.

The case T_{1} ∩ T_{2} → T_{2} ∈ 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 T_{1} ∩ T_{2} → T_{1} ∈ F^{+} or T_{1} ∩ T_{2} → T_{2} ∈ F^{+}.

Using reductio ad absurdum, we suppose that none of the two functional dependencies is implied by F.
Let W = (T_{1} ∩ T_{2})^{+}, Y_{1} = T_{1} − W and Y_{2} = T_{2} − W. Y_{1} and Y_{2} are not empty by hypothesis, and W, Y_{1} and Y_{2} are a partition of T.
For each A_{i} ∈ T, 1 ≤?? i ≤?? k, we consider two values a_{i}, a_{i}′ ∈ dom(A_{i}), such that a_{i} ≠ a_{i}′. Let’s build a relation *r* with attributes WY_{1}Y_{2} constituted by the two tuples:

e_{1}[A_{i}] = a_{i}, 1 ≤? i ≤?? k ?

e_{2}[A_{i}] = a_{i} if A_{i} ∈ W; a_{i}′ if A_{i} ∈ Y_{1}Y_{2}

*r* satisfies each dependency V → Z ∈ F. In fact, if V ⊈ W, then e_{1}[V] ≠ e_{2}[V], and *r* obviously satisfies the dependency. If V ⊆ W, then (T_{1} ∩ T_{2}) → V, so (T_{1} ∩ T_{2}) → Z for transitivity, from which Z ⊆ W, and so e_{1}[Z] = e_{2}[Z], an this implies that *r* satifies the dependency. Moreover, since Y_{1} and Y_{2} 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

- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?
- Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP