Functional Dependencies Definition and Rules of Axioms
Definition
A functional dependency is a constraint between two sets of attributes in a relation. If an attribute set X functionally determines another attribute set Y, it is written as:
X → Y
This means that for any two tuples in a relation, if they have the same value for X, then they must have the same value for Y.
Formal Definition
In a relation R, a functional dependency X → Y holds if and only if for every pair of tuples t1 and t2 in R:
- if t1[X] = t2[X], then t1[Y] = t2[Y]
Here:
X
- is called the determinant
Y
- is called the dependent
X
- and Y are sets of attributes
Example
Consider a relation:
Student(RollNo, Name, Dept)
If each roll number belongs to exactly one student, then:
RollNo → Name, Dept
This means:
- knowing the RollNo is enough to determine the Name and Dept,
- but knowing the Name may not uniquely determine the RollNo.
Important Notes
- A functional dependency does not mean arithmetic dependence.
- It means uniqueness of determination.
- FDs are about the entire relation schema, not just one sample table instance.
- They are used to capture semantic rules of the real-world data.
Main Content
1. Functional Dependency Concept
Meaning and interpretation
- A functional dependency expresses a rule of the form “if two rows agree on X, they must agree on Y.”
- It captures business logic or real-world constraints rather than just data values.
- Example: In an employee table, EmpID → EmpName, Salary, DeptNo because each employee ID identifies only one employee.
- This relationship is foundational for finding keys and removing redundancy.
Types of functional dependency relationships
- Trivial FD: An FD is trivial if the dependent is a subset of the determinant.
- Example: {A, B} → A
- Non-trivial FD: The dependent is not a subset of the determinant.
- Example: A → B
- Completely non-trivial FD: The determinant and dependent have no attribute in common.
- Example: A → B where A and B are disjoint.
- These categories are important because they help classify the strength and usefulness of dependencies.
2. Axioms of Functional Dependencies
Axioms are inference rules
- Axioms are formal rules used to derive all valid functional dependencies from a given set.
- They are also called Armstrong’s Axioms.
- These rules are:
- Reflexivity
- Augmentation
- Transitivity
- Using these, we can derive additional rules such as union, decomposition, and pseudotransitivity.
Why axioms matter
- They provide a logical method for reasoning about dependencies.
- They help compute attribute closure, candidate keys, and minimal covers.
- They are used in normalization and schema design.
- Without axioms, dependency inference would be informal and error-prone.
3. Armstrong’s Axioms and Derived Rules
Reflexivity
- If Y is a subset of X, then X → Y
- Example: {A, B} → A
- This is always true because a set of attributes can determine any subset of itself.
Augmentation
- If X → Y, then XZ → YZ for any attribute set Z
- Example: If A → B, then AC → BC
- This means adding the same attributes to both sides preserves the dependency.
Transitivity
- If X → Y and Y → Z, then X → Z
- Example: If StudentID → DeptNo and DeptNo → DeptName, then StudentID → DeptName
- This is the most intuitive rule and is widely used in dependency derivation.
Derived rules from Armstrong’s axioms
- Union: If X → Y and X → Z, then X → YZ
- Decomposition: If X → YZ, then X → Y and X → Z
- Pseudotransitivity: If X → Y and WY → Z, then WX → Z
- These derived rules are extremely helpful in solving FD-based problems in normalization.
4. Closure of Attributes and Its Use
Attribute closure
- The closure of a set of attributes X, written as X⁺, is the set of all attributes functionally determined by X using the given FDs.
- It is computed by repeatedly applying functional dependency rules until no new attributes can be added.
- If X⁺ contains all attributes of a relation, then X is a superkey.
Example
- Relation: R(A, B, C, D)
- FDs:
- A → B
- B → C
- AC → D
- Compute A⁺:
- Start: A⁺ = {A}
- From A → B, add B
- From B → C, add C
- Now A⁺ = {A, B, C}
- Since A and C are in closure, use AC → D, add D
- Final: A⁺ = {A, B, C, D}
- Therefore, A is a superkey.
Importance
- Closure is used to test whether an FD is implied by others.
- It helps find candidate keys.
- It supports normalization and minimal cover computation.
Working / Process
1. Identify the relation schema and business rules
- Start by understanding the table structure and the real-world meaning of attributes.
- Determine which attributes uniquely identify others.
- Example: In Student(RollNo, Name, Dept, Hostel), RollNo may determine all other attributes.
2. Write the functional dependencies
- Express the discovered relationships in FD notation.
- Example:
- RollNo → Name, Dept
- Dept → Hostel
- Separate direct and indirect dependencies carefully.
- Ensure dependencies reflect actual constraints, not accidental data patterns.
3. Apply axioms to infer new dependencies and analyze keys
- Use reflexivity, augmentation, and transitivity to derive all needed dependencies.
- Compute attribute closure to check keys and validity of dependencies.
- Use the results to identify redundancy and prepare for normalization.
Advantages / Applications
- Helps in identifying candidate keys and superkeys accurately.
- Reduces data redundancy and prevents update, insert, and delete anomalies.
- Forms the theoretical basis for normalization in database design.
- Supports dependency inference using Armstrong’s axioms.
- Useful in computing attribute closure, minimal cover, and lossless decomposition.
- Helps enforce data integrity by capturing real-world rules.
Summary
- Functional dependencies describe how one set of attributes determines another in a relation.
- Armstrong’s axioms provide the basic rules for deriving valid dependencies.
- These concepts are essential for key finding, closure computation, and normalization.
- Important terms to remember: determinant, dependent, closure, superkey, Armstrong’s axioms