Lossless Join Decompostion | Database Management System
Lossless Join Decompostion | Database Management System
Lossless Join Decompostion : For the case of R = (R1,R2), we require that for all possible relations r on schema R.
A decomposition of R into R1 and R2 is lossless join if and only if at least one of the following dependencies is in F+.
Example:
R = (A, B, C)
F = {A- B, B – C}
Can be decomposed in two different ways
R1 = (A, B), R2 = (B, C)
Lossless-join decomposition:
R1 r R2 = {B} and B – BC
Dependency preserving
R1 = (A, B), R2 = (A, C)
Lossless-join decomposition.
R1 r, R2 = A and A-2 A5 Not dependency preserving (Cannot check B – C without computing R1XR2)
Relational Database Design and Normalisation
Dependency Preservation
Let Fibe the set of dependencies F+ that include only attributes in Ri. A decomposition is dependency preserving, if
if it is not, then checking updates for violation of functional dependencies may require computing joins, which is expensive.
Testing for Dependency Preservation
To check if a dependency is preserved in a decomposition of R into R1, R2, …, Rn we apply the following test (with attribute closure done with respect to F). result = 0. while (changes to result) do for each Ri in the decomposition t = (resultry Ri) + r. Ri result = result Ut if result contains all attributes in B, then the functional dependency O – B is preserved.
We apply the test on all dependencies in Fto check if a decomposition is dependency preserving This procedure takes polynomial time, instead of the exponential time required to compute F+ and(F1 U F2 U … U Fn)+
Example
R = (A, B, C) F = A- B B – C Key = {A} R is ngt in BCNF Decomposition R1 = (A, B), R2 = (B, C) R1 and R2 in BCNF Lossless-join decomposition Dependency preserving
Testing Decomposition for BCNF
To check if a relation Riina decomposition of R is in BCNF,
Either test Rifor BCNF with respect to the restriction of F to Ri (that is, all FDs in F+ that contain only attributes from Ri) or use the original set of dependencies F that hold on R, but with the following test: for every set of attributes O. CRi, check that O + (the attribute closure of O.) either includes no attribute of Ri-O, or includes all attributes of Ri. If the condition is violated by some a -> b in F, the dependency
Ri can be shown to hold on Ri, and Riviolates BCNF. We use above dependency to decompose Ri.
BCNF Decomposition Algorithm
result := {R }; COI) ε : = falε ε : compute F +;
while (not done) do
if there is a schema Riin result that is not in BCNF)
then begin
let be a nontrivial functional dependency that holds on Risuch that  is not in F
end
else done: = true;
Note: each Riis in BCNF, and decomposition is lossless-join.
Example of BCNF Decomposition
R=(A,B,C)
F = (A -> B B -> C Key = {A}
R is not in BCNF (B->C but B is not superkey)
Decomposition
R1 = (B, C)
R2 = (A,B)
BCNF and Dependency Preservation
It is not always possible to get a BCNF decomposition that is dependency preserving
Two candidate keys = JK and JL.
R is not in BCNF
Any decomposition of R will fail to preserve JK-> L
This implies that testing for JK-> L requires a join.
Decomposition of Table Structure to Meet BCNF
3NF solves the problem
Prime attributes: An attribute that is contained in a candidate key for R
Relational Database Design and Normalisation
Example 1.
Example 2
Candidate keys = EJL, JL3
Prime attributes; J, K, L
Observation/intuition:
- A key has no redundancy (is not repeated in a relation)
- A prime attribute has limited redundancy
Given a relation schema R, and a set of functional dependencies F, if every FD, A → B, is either:
- Trivia, or
- A is a superkey of R, or 3.
- All attributes in (B – A) are prime. Then, R is in 3 NF (3rd Normal Form)
Normalization into 3rd Normal form
3NF and redundancy
Why does redundancy arise?
Given a FD, A- B, if A is repeated (B-A) has to be repeated
- If rule 1 is satisfied, (B-A) is empty, so not a problem.
- If rule 2 is satisfied, then A can’t be repeated, so this doesn’t happen (in BCNF)
- If not, rule 3 says (B – A) must contain only prime attributes. This limits the redundancy Somewhat.
So 3NF relaxes BCNF somewhat by allowing for some (hopefully limited) redundancy. Why? There always exists a dependency-preserving lossless decomposition in 3 NF.