# 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.