When testing for normal forms, it is not sufficient to consider the given set of functional dependencies; rather, we need to consider all functional dependencies that hold on the schema.
We can use the following three rules to find all of functional dependencies that hold on the schema.
Reflexivity rule : If α is a set of attributes and β ⊆ α,then α → β holds.
Augmentation rule : If α → β holds and γ is a set of attributes, then γα → γβ holds.
Transitivity rule : If α → β holds and β → γ holds, then α → γ holds.
Union rule : If α → β holds and α → γ holds, then α → βγ holds.
Decomposition rule : If α → βγ holds, then α → β holds and α → γ holds.
Pseudotransitivity rule : If α → β holds and γβ → δ holds, then αγ → δ holds.
Q. R = ( A, B, C, G, H, I ) and the set F of functional dependencies { A → B, A → C, CG → H, CG → I , B → H}.
A → H. Since A → B and B → H hold, we apply the transitivity rule.
CG → HI . Since CG → H and CG → I , the union rule implies that CG → HI.
AG → I .Since A → C and CG → I , the pseudo-transitivity rule implies that AG → I holds.
Q. Find the possible functional dependencies in relation R, if n is the number of attributes in R.
A set of size 'n' has 2n subsets.
There are a total of 2n * 2n = 22n possible subsets.
Attribute Closure Algorithm
Given FD set of a Relation R, The attribute closure set S be the set of A.
Add A to S.
Recursively add attributes which can be functionally determined from attributes of the set S until done.
Q. For schema R = ( A, B, C, G, H, I ) and the set F of functional dependencies { A → B, A → C, CG → H, CG → I , B → H}. Compute (AG)+ which is closure of α under F .
Create an empty set S = {} and add all the attributes that are functionally determined by AG.
As AG → AG we add AG to the empty set to get S = {AG}
Then we have A → B, A → C so we can add B and C to the set to get S = {ABCG}. We choose to consider functional dependencies of both A as well as G as both are subsets of Set S.
Now the set contains S = {ABCG}, we consider the subsets of the set elements and check their functional dependencies :
One such subset is CG (As CG ⊂ ABCG) and the functional dependencies are CG → H and CG → I.
Thus, we can add H and I to the set to get S = {ABCGHI}.
As all elements are covered in S we can stop.
Canonical Cover
A canonical cover Fc for F is a set of dependencies such that Fc logically implies all dependencies in F, and F logically implies all dependencies in Fc. Furthermore, Fc must have the following properties:
No functional dependency in Fc contains an extraneous attribute.
Each left side of a functional dependency in Fc is unique. That is, there are no two dependencies α1 → β1 and α2 → β2 in Fc such that α1 = α2.
An attribute of a functional dependency is said to be extraneous if we can remove it without changing the closure of the set of functional dependencies. The formal definition of extraneous attributes is as follows: Consider a set F of functional dependencies and the functional dependency α → β in F.
Attribute A is extraneous in α if A ∈ α, and F logically implies (F −{α → β}) ∪{(α − A) → β}.
Attribute A is extraneous in β if A ∈ β, and the set of functional dependencies (F − {α → β}) ∪{α → (β − A)} logically implies F.
Q. F contains AB → CD, A → E, and E → C. Check if C is extraneous in AB → CD.
Step 1 : We compute the attribute closure of AB under F' = { AB → D, A → E, E → C}. Thus, we remove C from RHS of AB → CD.
(AB)+ = {ABCDE} which includes CD.
Therefore, we infer that C is extraneous.
Q. Consider that F contains AB → C, A → C. Check if B is extraneous in AB → C.
We remove B from LHS of AB → C to make A → C. B is extraneous attribute as A rarr; C exists which means that A can determine C without B.
Q. F contains A → BC, B → C, and AB → D. What extraneous attributes are present in F.
Step 1 : C is extraneous in RHS of A → BC as A → B and B &arr; C so by transitive rule A → C.
Step 2 : B is extraneous in AB → D as A → B and A → C (Decomposition rule on A → BC). So AB → D can also be written as A → D.
Q. F contains A → BC, B → C, and AB → D. What extraneous attributes are present in F.
Step 1 : C is extraneous in RHS of A → BC as A → B and B → C so by transitive rule A → C.
Step 2 : B is extraneous in AB → D as A → B and A → C (Decomposition rule on A → BC). So AB → D can also be written as A → D.
Q. Consider two sets of FD's such as F = {A → B, AB → C; D → AC; D → E} and G = {A → BC; D → AB}
Step 1: Obtain Singleton (only one attribute) left hand side Step 2: Removal of extraneous attributes Step 3: Removal of Redundant FD's.
In F we have four FD's but D → AC is not singleton on RHS; So we make it singleton by using decomposition rule; Hence we get D → A; D → C.
Next we move to AB → C. However, since A+ = {ABC}. Hence B is extraneous in AB → C. We change this FD to A → C.
Now all attributes in the FD's are singleton.
Currently FD's are, F = {A → B, A → C; D → A; D → E; D → C}. We begin second step.
In all FD's of F, B is determined uniquely by A (A → B) then A is determined uniquely by D (D → A), E is determined uniquely by D (D → E) and also C is determined uniquely by D (D → C). The only attribute that has two FD's is C (A → C / D → C)
Hence we check which of those two FD's is redundant leaving all others safe.
To compute this we consider A → C and take A+. We have to remove A → C from set of FD's for purpose of finding closure of A.
A+ = {AB}
Thus we conclude that A → C is essential as without it C cannot be determined by A.
Repeating these steps for D → C we get it as redundant as D+ = {DACBE}. Hence D → C is redundant and we remove it.
Next we find same steps for G.
At the end we get G = {A → B; A → C; D → A; D → B}. Although B is determined twice but D → B is redundant.
Comparing F and G we say that F covers G but G does not covers F.
Lossless decomposition
Say we have relations R1 and R2 which we are decomposing from parent relation R. Then such a decomposition is said to be lossless if
R1 ∩ R2 → R1
R1 ∩ R2 → R2
Which means that the common attribute between R1 and R2 is the super-key of either R1 or R2.
We have parent relation as inst_dept {ID, name, dept name, salary, building, budget} instructor (ID, name, dept name, salary) department (dept_name, building, budget)
Consider the intersection of these two schemas, which is dept_name. We see that because {dept_name → dept_name, building, budget} the lossless - decomposition rule is satisfied.
Test for checking 3NF
Definition : A relation is in 3NF if for every non-trivial FD X → A, X is a superkey or A is part of some key for R.
First find the candidate key. This is the set of attributes whose closure is the entire set of attributes.
Then check all FD's one by one and see if the RHS of FD is either a superkey or part of candidate key.
If all FD's meet this condition then relation is in 3NF.
Q. R(ABCD) = F {AB → CD}
(AB)+ = {ABCD} so AB is candidate key.
All FD's satisfy the rule so relation is in 3NF.
Q. R(ABCDE) = {AB → CD; E → A; D → A}
Candidate key is BE as (BE)+ = {ABCDE}
E → A : this is not ok, because E is not a candidate key, and A is not part of BE.
D → A : this is not ok, because D is not a candidate key, and A is not part of BE.
Q. R(ABCD) = {ABC → D; D → A}
Here candidate key is ABC and BCD.
Both FD's satisfy the conditions so relation is in 3NF.
However; D → A : D is not a candidate key, so it is not in BCNF.
A database is in second normal form if it satisfies the following conditions:
It is in first normal form
All non-key attributes are fully functional dependent on the primary key i.e. have no partial-key dependencies.
If attribute B is functionally dependent on A, but is not functionally dependent on a proper subset of A, then B is considered fully functional dependent on A. Hence, in a 2NF table, all non-key attributes cannot be dependent on a subset of the primary key.
Note that if the primary key is not a composite key, all non-key attributes are always fully functional dependent on the primary key. A table that is in 1st normal form and contains only a single key as the primary key is automatically in 2nd normal form.
Q. R(ABCD) = {ABC → D; D → A}
Here candidate key is ABC and BCD.
Both FD's satisfy the conditions so relation is in 2NF.
Q. In a relation R(STUD_NO, COURSE_NO, COURSE_NAME) we have FD set: {COURSE_NO -> COURSE_NAME} and Candidate Key: {STUD_NO, COURSE_NO}
In FD {COURSE_NO -> COURSE_NAME}, COURSE_NAME is a non key attribute however it is functionally dependent on a subpart of the candidate key {STUD_NO, COURSE_NO}.
Hence 2NF condition is not satisfied.
Q. R (A, B , C, D ) has FD set as AB -> C; BC -> D
Candidate key is obtained as AB since (AB)+ = {ABCD}
AB → C satisfied condition of 2NF and BC → D also does as BC is not a subset of the candidate key. 2NF is satisfied.