Desirable Properties of Decomposition

Desirable Properties of Decomposition – If we apply the normal forms or normalization or schema refinement technique – Decomposition to the universal table, then it may be splitted up into different fragments. At any stage, if we combine the fragments (denormalization), it should give the original table in terms of columns and rows and it will be described as the following properties :

• Losless Join Decomposition Property – Click
• Dependency Preserving Property – Click

Lossless Join Decomposition 

Let R be the relational schema with instance r is decomposed into R₁,R₂,….,R_n with instance r₁,r₂,…..,r_n.  If r₁ ⋈ r₂ ⋈ ……. ⋈ r_n = r , then it is called Lossless Join Decomposition. i.e. if natural joins of all the decompositions gives the original relation, then it is said to be Lossless Join Decomposition.

Another Definition  or To check whether a Decomposition is a lossless or lossy decomposition – 

Let R be a relation schema, F be a set of functional dependencies on R. Let R is decomposed in R₁, R₂,….,R_n. The decomposition is a lossless-join decomposition of R  if

(a) R1 ∪ R2 ∪ ......∪ Rn ≡ R

and
(b) Let Ri and Rj be the any two subrelations, Ri and Rj can be merge into single relation Rij with attribute set Ri ∪ Rj only if
(i) Ri ∩ Rj ≠ Φ


(ii) Ri ∩ Rj → Rj {Ri and Rj should be super key of Ri} and
     Ri ∩ Rj → Ri {Ri and Rj should be super key of Rj}

(c) Repeat (a) untin N relations become single relation. If is possible to merge into single relation, then decomposition is losless, otherwise lossy.

Example : How to Find Lossless Join Decomposition – 

Method 1 :  (Not Useful for Gate Students)

Consider the previous example Supplier_Parts which is decomposed into supplier and parts relation but doing the decomposition in a different way :

Supplier_Parts : S# Sname City P# Qty 3 Smith London 301 20 5 Nick NY 500 50 2 Steve Boston 20 10 5 Nick NY 400 40 5 Nick NY 301 10
⇓
Parts : S# P# Qty 3 301 20 5 500 50 2 20 10 5 400 40 5 301 10	Supplier : S# Sname City Qty 3 Smith London 20 5 Nick NY 50 2 Steve Boston 10 5 Nick NY 40 5 Nick NY 10

The above decomposition is a Lossless join Decomposition. Because, Let us apply natural join operation on the decomposed relations.

                            Parts  ⋈ Supplier

Parts  ⋈ Supplier : S# Sname City P# Qty 3 Smith London 301 20 5 Nick NY 500 50 2 Steve Boston 20 10 5 Nick NY 400 40 5 Nick NY 301 10

= Supplier_Parts

Hence the Decomposition is lossless join decomposition.

Method 2 : (Useful for Gate Students)

The above method is very time consuming for the gate students. The method 2 is very simple and fast. → Consider again the relation Supplier_Parts. Try to decompose the relation so that the common attribute in the tables is a key for atleast one table. Here,

In Supplier relation Supplier(S#,Sname,City):
S# → Sname
S# → City

In parts relation Parts(S#,P#,Qty) :
(S#,P#) → Qty

]]>