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

0 Asked on October 28, 2021 by user8440261

1 Asked on October 28, 2021 by girish

1 Asked on October 28, 2021 by jyao

1 Asked on October 28, 2021

1 Asked on October 28, 2021

0 Asked on October 28, 2021

0 Asked on October 28, 2021 by anony-mous

1 Asked on October 28, 2021

2 Asked on October 28, 2021 by malazzar

0 Asked on October 28, 2021 by dev_etter

2 Asked on October 28, 2021

1 Asked on October 28, 2021 by viktor-vsk

2 Asked on October 28, 2021 by deepan-kaviarasu

2 Asked on October 28, 2021 by lvaro-gonzlez

1 Asked on October 28, 2021 by fakipo

1 Asked on October 28, 2021 by hikari

Get help from others!

Recent Answers

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

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- 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?

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