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:

  1. A key has no redundancy (is not repeated in a relation)
  2. 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:

  1. Trivia, or
  2. A is a superkey of R, or 3.
  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

  1. If rule 1 is satisfied, (B-A) is empty, so not a problem.
  2. If rule 2 is satisfied, then A can’t be repeated, so this doesn’t happen (in BCNF)
  3. 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.