Functional Dependencies & Normalization

Functional Dependency

In any relation, a functional dependency α → β holds if- Two tuples having same value of attribute α also have same value for attribute β.

• Trivial Functional Dependencies – A functional dependency X → Y is said to be trivial if and only if Y ⊆ X. Thus, if RHS of a functional dependency is a subset of LHS, then it is called a trivial functional dependency.
• Non-Trivial Functional Dependencies – A functional dependency X → Y is said to be non-trivial if and only if Y ⊄ X. Thus, if there exists at least one attribute in the RHS of a functional dependency that is not a part of LHS, then it is called a non-trivial functional dependency.

Decomposition of a Relation

The process of breaking up or dividing a single relation into two or more sub relations is called the decomposition of a relation.

• Lossless Decomposition - Lossless decomposition ensures no information is lost from the original relation during decomposition. When the sub relations are joined back, the same relation is obtained that was decomposed.
• Dependency Preservation - Dependency preservation ensures none of the functional dependencies that hold on the original relation are lost. The sub relations still hold or satisfy the functional dependencies of the original relation.
• Lossless Join Decomposition: R1 ⋈ R2 ⋈ R3 ……. ⋈ Rn = R where ⋈ is a natural join operator.
• Lossy Join Decomposition: R1 ⋈ R2 ⋈ R3 ……. ⋈ Rn ⊃ R.

Normalization & Normal Forms

Database normalization is a process of making the database consistent by reducing redundancies and ensuring integrity through lossless decomposition.

• First Normal Form (1NF) - A given relation is called in First Normal Form (1NF) if each cell of the table contains only an atomic value i.e. if the attribute of every tuple is either single valued or a null value.
• Second Normal Form (2NF) - A given relation is called in Second Normal Form (2NF) if and only if Relation already exists in 1NF and no partial dependency exists in the relation. A → B is called a partial dependency if and only if- A is a subset of some candidate key and B is a non-prime attribute.
• Third Normal Form (3NF) - A given relation is called in Third Normal Form (3NF) if and only if Relation already exists in 2NF and no transitive dependency exists for non-prime attributes. A → B is called a transitive dependency if and only if- A is not a super key and B is a non-prime attribute.
• Boyce-Codd Normal Form (BCNF) - A given relation is called in BCNF if and only if Relation already exists in 3NF and for each non-trivial functional dependency ‘A → B’, A is a super key of the relation.