Functional Dependencies (FD)
A functional dependency is a constraint that describes the relationship between attributes in a relation. Formally, a functional dependency α → β holds on a relation R if, for any two tuples (rows) t1 and t2 in R, t1[α] = t2[α] implies t1[β] = t2[β].
Simply put: If you know the value of the attribute set α, it uniquely determines the value of the attribute set β.
Trivial vs Non-Trivial Dependencies
- Trivial Dependency: A functional dependency α → β is trivial if and only if the right-hand side is a subset of the left-hand side (β ⊆ α). For example, {Employee_ID, Name} → {Name} is trivial because Name is already part of the determinant.
- Non-Trivial Dependency: A dependency is non-trivial if there is at least one attribute in the right-hand side that is not part of the left-hand side (β ⊄ α).
Attribute Closure (X⁺)
The closure of an attribute set X, denoted as X⁺, is the set of all attributes functionally determined by X under a given set of functional dependencies. Computing X⁺ is a fundamental step in database design.
Example: Computing Attribute Closure
Given Relation R(A, B, C, D) and Functional Dependencies: { A → B, B → C }. Let's find the closure of A (denoted as A⁺):
- Start with A⁺: Initialize the closure: A⁺ = { A }
- Apply A → B: Since we have A in our closure, we can determine B. Add B: A⁺ = { A, B }
- Apply B → C: Since we now have B in our closure, we can determine C. Add C: A⁺ = { A, B, C }
Final Result: A⁺ = { A, B, C }
Relation Decomposition
Decomposition is the process of splitting a single relation into two or more sub-relations to eliminate redundancy and prevent anomalies (insert, update, delete anomalies). A valid decomposition must satisfy two critical criteria: Lossless-join and Dependency preservation.
- Lossless-Join Decomposition: Joining the sub-relations back together reconstructs the original relation exactly, without losing or generating fake data. If the join produces extra, invalid records (spurious tuples), the decomposition is strictly lossy.
- Dependency Preservation: Ensures that all functional dependencies defined on the original relation can be checked and enforced within the sub-relations individually, without requiring expensive table joins.
| Decomposition Property | Core Structural Objective | Practical System Impact |
|---|---|---|
| Lossless-Join | Ensures joining sub-relations exactly reconstructs original relation. | Prevents the generation of invalid, spurious records. |
| Dependency Preservation | Keeps all original functional dependencies within sub-relations. | Allows database to validate integrity rules without performing joins. |
Placement Takeaways: Armstrong's Axioms
During interviews, you may be asked how functional dependencies are deduced. You can infer new FDs from existing ones using Armstrong's Axioms:
- Reflexivity: If β is a subset of α, then α → β. (This is the definition of a trivial dependency).
- Augmentation: If α → β, then α,γ → β,γ. (You can add the same attributes to both sides).
- Transitivity: If α → β and β → γ, then α → γ. (The most frequently tested axiom!).
Example: Lossless vs Lossy Decomposition
Given Relation R(A, B, C) and Functional Dependency: A → B.
- Decomposition 1: R1(A, B) and R2(B, C): The common attribute is B. Is B a super key for R1? No (B → A is not given). Is B a super key for R2? No (B → C is not given). Because the intersection is not a super key for either relation, this decomposition is Lossy.
- Decomposition 2: R1(A, B) and R2(A, C): The common attribute is A. Is A a super key for R1? Yes, because A → B! Because the intersection forms a super key for one of the decomposed tables, this decomposition is Lossless.