2. Give a necessary and sufficient condition for a decomposition of R into R1 an

Question

2. Give a necessary and sufficient condition for a decomposition of R into R1 and R2 to be lossless join. Very briefly explain why the condition is necessary and sufficient. a. [10 points] b. Given F IA- B, A-C, CG->H, CG>I, B-H), set of functional dependencies on R(A, [10 points] c. Identify possible functional dependencies from the following schema of car-sell relation B, C, G, H, I), check if A is a candidate key of R. used by a Toyota dealer, Car-sell (transactionID customerlD, CustomerName, customerAddress, carModel, 15 points] [10 points] MakeYear, carPrice, NoOfSeats) d. Check if the schema car-sell of (c) is in BCNF form. Explain your answer.

Explanation / Answer

If we decompose a relation R into relations R1 and R2,

Decomposition is lossless if R1 ? R2 = R //R1 Join R2 equal to R
To check for lossless join decomposition using FD(functional dependency) set, following conditions must hold:

Union of Attributes of R1 and R2 must be equal to attribute of R. Each attribute of R must be either in R1 or in R2.
Att(R1) U Att(R2) = Att(R)
Intersection of Attributes of R1 and R2 must not be NULL.
Att(R1) ? Att(R2) ? ?
Common attribute must be a key for at least one relation (R1 or R2)
Att(R1) ? Att(R2) -> Att(R1) OR Att(R1) ? Att(R2) -> Att(R2)
For Example, A relation R (A, B, C, D) with FD set{A->BC} is decomposed into R1(ABC) and R2(AD) which is a lossless join decomposition as:

First condition holds true as Att(R1) U Att(R2) = (ABC) U (AD) = (ABCD) = Att(R).
Second condition holds true as Att(R1) ? Att(R2) = (ABC) ? (AD) ? ?
Third condition holds true as Att(R1) ? Att(R2) = A is a key of R1(ABC) because A->BC is given.
Dependency Preserving Decomposition

If we decompose a relation R into relations R1 and R2, All dependencies of R either must be a part of R1 or R2 or must be derivable from combination of FD’s of R1 and R2.
For Example, A relation R (A, B, C, D) with FD set{A->BC} is decomposed into R1(ABC) and R2(AD) which is dependency preserving because FD A->BC is a part of R1(ABC).

-----------------------------------------------------------------------------------------------------------

Given a set F set of functional dependencies, there are certain other functional dependencies that are logically implied by F.

+ E.g. If A ? B and B ? C, then we can infer that A ? C

The set of all functional dependencies logically implied by F is the closure of F.

We denote the closure of F by F+.

We can find all of F+ by applying Armstrong’s Axioms:

if ? ? ?, then ? ? ? (reflexivity)

if ? ? ?, then ??? ? ? (augmentation)

if ? ? ?, and ? ? ?, then ?? ? (transitivity)

These rules are + sound (generate only functional dependencies that actually hold) and

complete (generate all functional dependencies that hold).

some members of F+.

A --> H

• by transitivity from A --> B and B --> H

AG --> I

•by augmenting A --> C with G, to get AG --> CG and then transitivity with CG --> I

– CG --> HI

•by augmenting CG --> I to infer CG --> CGI, and augmenting of CG --> H to infer CGI --> HI, and then transitivity.

To compute the closure of a set of functional dependencies F:

F+ = F

repeat for each functional dependency f in F+

apply reflexivity and augmentation rules on f

add the resulting functional dependencies to F+

for each pair of functional dependencies f1and f2 in F+

if f1 and f2 can be combined using transitivity

then add the resulting functional dependency to F+

until F+ does not change any further

We can further simplify manual computation of F+ by using the following additional rules.

If ? ? ? holds and ??? holds, then ? ? ? ? holds (union)

If ? ? ? ? holds, then ? ? ? holds and ??? holds (decomposition)

If ? ? ? holds and ? ? ? ? holds, then ???? holds (pseudotransitivity)

The above rules can be inferred from Armstrong’s axioms.

Given a set of attributes ?, define the closure of ? under F

(denoted by ?+) as the set of attributes that are functionally

determined by ? under F: ??? is in F+ ? ???+

Algorithm to compute ?+, the closure of ? under F

result := ?;

while (changes to result) do

for each ??? in F do

begin

if ? ? result then result := result ? ?

end

R = (A, B, C, G, H, I)

F = {A ? B A ? C CG ? H CG ? I B ? H}

(AG)+

1. result = AG

2. result = ABCG (A ? C and A ? B)

3. result = BCGH (CG ? H and CG ? AGBC)

4. result = ABCGHI (CG ? I and CG ? AGBCH)

Is AG a candidate key? 1. Is AG a super key?

1. Does AG ? R? == Is (AG)+ ? R

2. Is any subset of AG a superkey?

1. Does A ? R? == Is (A)+ ? R

2. Does G ? R? == Is (G)+ ? R

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.