We have three algorithms for creating a relational decomposition
from a universal relation as follows,
- Dependency-Preserving
Decomposition into 3NF Schemas
- Non-additive Join Decomposition into BCNF Schemas
- Dependency-Preserving and Nonadditive (Lossless) Join Decomposition
into 3NF Schemas
Dependency-Preserving Decomposition into 3NF Schemas
Dependency Preservation
A Decomposition D = { R1, R2, R3....Rn } of R is dependency preserving wrt a set F of Functional dependency if,
(F1 ∪ F2 ∪ ... ∪ Fm)+ = F+.
Consider a relation R,
R ---> F{...with some functional dependency(FD)....}
R is decomposed or divided into R1 with FD { f1 } and R2 with { f2 }, then
there can be three cases:
1. f1 U f2 = F -----> Decomposition is dependency preserving.
2. f1 U f2 is a subset of F -----> Not Dependency preserving.
3. f1 U f2 is a superset of F -----> This case is not possible.
- A dependency-preserving decomposition D = {R1, R2, ..., Rm} of a universal relation R based on a set of functional dependencies F, such that each Ri in D is in 3NF.
- It guarantees only the dependency-preserving property; it does not guarantee the nonadditive join property.
Relational Synthesis into 3NF with Dependency Preservation
Input: A universal relation R and a set of functional dependencies F on the attributes of R.
- The first step of the algorithm is to find a minimal cover for F.
Note that multiple minimal covers may exist for a given set F
Minimal cover
Definition 1:
A minimal cover of a set of FDs F is a minimal set of functional dependencies Fmin that is equivalent to F. There can be many such minimal covers for a set of functional dependencies F.
Definition 2:
A set of FDs F is minimum if F has as few FDs as an equivalent set of FDs.
Properties/Steps of minimal cover
1. Right Hand Side (RHS) of all FDs should be a single attribute.
2. Remove extraneous attributes (an attribute which can remove it without changing the closure of the set of functional dependencies).
3. Eliminate redundant functional dependencies.
Example
Let us apply these properties to F = {A → C, AB → C, C → DI, CD → I, EC → AB, EI → C}
Step 1:
According to the property, there should be only a single attribute on the RHS.
so we can write,
F= {A → C, AB → C, C → D, C → I, CD → I, EC → A, EC → B, EI → C}
Step 2:
We can remove AB --> C & CD --> I as these both are extraneous because C can be derived from A itself and I can be derived from C alone. Therefore,
F= { F2 = {A → C, C → D, C → I, EC → A, EC → B, EI → C}
Step 3:
None of the FDs is redundant. Hence, F is the minimal cover.
Nonadditive Join Decomposition into BCNF Schemas
The algorithm decomposes a universal relation schema R = {A1, A2, ..., An} into a decomposition D = {R1, R2, ..., Rm} such that each Ri is in BCNF and the decomposition D has the lossless join property with respect to F.
Relational Decomposition into BCNF with Nonadditive Join Property
Input: A universal relation R and a set of functional dependencies F on the attributes of R.
Set D := {R} ;
While there is a relation schema Q in D that is not in BCNF do
{
choose a relation schema Q in D that is not in BCNF;
find a functional dependency X → Y in Q that violates BCNF;
replace Q in D by two relation schemas (Q – Y) and (X ∪ Y);
} ;
Each time through the loop, we decompose one relation schema Q that is not in BCNF into two relation schemas. According to Property NJB for binary decompositions, the decomposition D has the nonadditive join property. At the end of the algorithm, all relation schemas in D will be in BCNF.
It is necessary to determine whether a relation schema Q is in BCNF or not. One method for doing this is to test, for each functional dependency X → Y in Q, whether X+ fails to include all the attributes in Q, thereby determining whether or not X is a (super)key in Q. Another technique is based on an observation that whenever a relation schema Q has a BCNF violation, there exists a pair of attributes A and B in Q such that {Q – {A, B} } → A; by computing the closure {Q – {A, B} }+ for each pair of attributes {A, B} of Q, and checking whether the closure includes A (or B), we can determine whether Q is in BCNF.
Example:
Given R = {A, B, C} and the functional dependencies F = {AB → C, C → B}
Dependency-Preserving and Nonadditive (Lossless) Join Decomposition into 3NF Schemas
Relational Synthesis into 3NF with Dependency Preservation and Nonadditive Join Property
As we know, it is not possible to have all three of
the following:
(1) guaranteed non-lossy design
(2) guaranteed dependency
preservation
(3) all relations in BCNF
Now we give an alternative algorithm
where we achieve conditions 1 and 2 and only guarantee 3NF which, Preserves dependencies & has the nonadditive join property such that each resulting relation schema in the
decomposition is in 3NF.
Input: A universal relation R and a set of functional dependencies F on the attributes of R.
Algorithm:
- Find a minimal cover G for F
- For each left-hand-side X of a functional dependency that appears in G, create a relation schema in D with attributes {X ∪ {A1} ∪ {A2} ... ∪ {Ak} }, where X → A1, X → A2, ..., X → Ak are the only dependencies in G with X as left-hand-side (X is the key of this relation).
- If none of the relation schemas in D contains a key of R, then create one more relation schema in D that contains attributes that form a key of R.
