# Decompositions in Database

Let U be a relation schema. A set of relation schemas {R1 , R2 , … , Rn} is a decomposition of U if and only if

U = R1 𝖴 R2 𝖴  …𝖴  Rn

###### Lossless-Join Decomposition

A decomposition {R, T} of U is a lossless-join decomposition (with respect to a set of constraints) if the constraints imply that u = r  t for all possible instances of R, T, and U.

The decomposition is said to be lossy otherwise.

It is always the case for any decomposition {R, T} of U that u⊆ r  t.

### 1. Properties of a Good Decomposition

A relational schema R with a set of functional dependencies F is decomposed into R1 and R2.

###### 1.    Lossless-join decomposition

Test to see if at least one of the following dependencies are in F+

R1 ∩ R2 → R1
R1 ∩ R2 → R2

If not, decomposition may be lossy

###### 2.    Dependency preservation

Let Fi be the set of dependencies in F+ that include only attributes in Ri (Notation: ))

Test to see if (F1 𝖴 F2)+= F+

When a relation is modified, no other relations need to be checked to preserve dependencies.

###### 3.    No redundancy Example.
• R1 = (A, B, C)
• F = {A → B, B → C}
• R1 = (A, B), R2 = (B, C)

Lossless-join decomposition?

R1 ∩ R2 = {B} and B → BC ∈ F+

Dependency preserving?

F+ = {A → B, A → C, A → AB, A → BC, A → AC, A → ABC, AB → C, AB → AC, AB → BC, AB → ABC, AC → BC,

AC → {B, B → C, B → BC} ∪{many trivial dependencies}

F1 = {A → B, A → AB} ∪  (many trivial dependencies}

F2 = {B → C, B → BC} ∪ (many trivial dependencies}

(F1 ∪ F2)+  =  F+

###### Example.
• R = (A, B, C)
• F = {A → B, B → C}
• R1 = (A, B), R2 = (A, C)

Lossless-join decomposition: yes

R1 ∩ R2 = {A} and A → AB

Dependency preserving: no

F+ = {A → B, A → C, A → AB, A → BC, A → AC, A → ABC, AB → C, AB → AC, AB → BC, AB → ABC, AC → BC,

{AC → B, B → C, B → BC} ∪ (many trivial dependencies} F1 = {A ® B, A ® AB}   (many trivial dependencies}

F2 = {A → C, A → AC} ∪ (many trivial dependencies} (F1 ∪ F2)+ #  F+

Cannot check B ® C without computing R1 ∩ R2

• It is always possible to decompose a relation into relations in 3NF such that the decomposition is lossless, and  dependencies are
• It is always possible to decompose a relation into relations in BCNF such that the decomposition is
• It may not be possible to preserve dependencies and BCNF.

Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)