Types and Properties of Functional Dependencies

Functional dependencies are the cornerstone of relational database theory. They describe constraints between attributes in a relation, capturing the idea that knowing the value of one set of attributes uniquely determines the value of another set. To work effectively with functional dependencies — whether you are designing a schema, performing normalization, or verifying data integrity — you need to understand not just what a functional dependency is, but what kind it is and what rules govern how dependencies can be derived, combined, and reasoned about. This topic builds that understanding in full, covering the distinction between trivial and non-trivial dependencies, the foundational axioms introduced by William Armstrong, the derived rules that follow from those axioms, and the practical techniques used to reason about attribute relationships in a schema.

Trivial Functional Dependencies

A functional dependency X → Y is called trivial when Y is a subset of X, written Y ⊆ X. In plain terms, this means Y is already contained within the determinant side, so the dependency tells you nothing new about the data. For example, consider a relation with attributes {StudentID, CourseID, Grade}. The dependency {StudentID, CourseID} → {StudentID} is trivial because StudentID is already part of the left-hand side. Knowing a student's ID and a course ID obviously tells you the student's ID — no real-world constraint is being expressed here.

More examples of trivial dependencies:

• {A, B, C} → {A} — trivial, since A is in the left-hand set.
• {A, B} → {A, B} — trivial, since the right-hand side equals the left-hand side exactly (and equality means Y ⊆ X).
• {EmployeeID, Department} → {Department} — trivial, since Department appears on the left.

Although trivial dependencies carry no new information, they are important to recognize for two reasons. First, when you enumerate a set of all functional dependencies holding in a schema, trivial ones will always appear; filtering them out helps you focus on meaningful constraints. Second, they serve as the formal grounding for the Reflexivity axiom discussed below. A trivial dependency is universally valid — it holds in every possible instance of every relation, regardless of what actual data is stored, because it is a matter of pure logic rather than empirical observation.

Non-Trivial Functional Dependencies

A functional dependency X → Y is non-trivial when Y is not a subset of X — that is, Y contains at least one attribute that does not already appear in X. These are the dependencies that actually say something meaningful about the real-world constraints embedded in your data model.

Consider a university enrollment table with attributes {StudentID, CourseID, InstructorID, Grade, CourseName}. Some non-trivial dependencies might include:

• StudentID → {StudentName, Major} — knowing the student ID tells you the student's name and major. Neither of those attributes is part of StudentID.
• CourseID → CourseName — a course ID uniquely determines the course name.
• {StudentID, CourseID} → Grade — together, a student and a course determine the grade earned.

Non-trivial dependencies are the ones that drive key identification and normalization. When you identify that a non-key attribute depends only on part of a composite key (a partial dependency), or that a non-key attribute determines another non-key attribute (a transitive dependency), you have found violations that motivate moving from one normal form to a higher one. All the practical work of schema refinement is grounded in reasoning about non-trivial dependencies.

There is also a stricter category sometimes called a completely non-trivial dependency, where X and Y share no attributes at all (Y ∩ X = ∅). For most practical purposes, the simpler definition — Y ⊄ X — is what matters.

Armstrong's Axioms: The Foundation for Deriving Dependencies

In 1974, William W. Armstrong published a set of inference rules that form a complete and sound axiomatic system for functional dependencies. "Sound" means the rules never derive a false dependency — every dependency they produce genuinely holds. "Complete" means that if a dependency logically follows from a given set F of functional dependencies, these rules are sufficient to derive it. These three axioms are the bedrock from which all further reasoning about functional dependencies is built.

Axiom 1 — Reflexivity

The Reflexivity axiom states: if Y ⊆ X, then X → Y. This is the formal axiom that captures trivial dependencies. If a set of attributes Y is already contained within X, then X trivially determines Y, because any two tuples that agree on every attribute in X certainly agree on every attribute in Y (which is just a subset of X).

Example: In a relation with schema R(A, B, C, D):

{A, B, C} → {A, B}    — holds by Reflexivity since {A,B} ⊆ {A,B,C}
{A, B}    → {A}       — holds by Reflexivity since {A} ⊆ {A,B}
{A}       → {A}       — holds by Reflexivity since {A} ⊆ {A}

The critical insight is that Reflexivity requires no evidence from the data. You do not need to look at any rows in the table; the dependency is guaranteed purely by the logical structure of sets. This is why trivial dependencies are universally valid.

Axiom 2 — Augmentation

The Augmentation axiom states: if X → Y, then XZ → YZ for any set of attributes Z. Here XZ means the union of X and Z (written X ∪ Z), and similarly for YZ. In words: if X determines Y, then adding the same set of attributes Z to both sides of the dependency produces another valid dependency.

Why does this hold? Suppose two tuples t1 and t2 agree on every attribute in X ∪ Z. Because they agree on X, and X → Y holds, they must also agree on Y. They already agree on Z by assumption. So they agree on Y ∪ Z. Therefore XZ → YZ.

Examples, continuing with R(A, B, C, D, E):

Given:  A → B
Derive: AC → BC   (augment both sides with C)
Derive: AD → BD   (augment both sides with D)
Derive: ACD → BCD (augment both sides with CD)

Augmentation is especially useful when building up from simple dependencies toward more complex ones. It is also used in proving other derived rules and in computing attribute closures. One practical caution: augmenting adds attributes to both sides simultaneously, keeping the dependency balanced. You cannot use Augmentation to add an attribute to only one side.

Axiom 3 — Transitivity

The Transitivity axiom states: if X → Y and Y → Z, then X → Z. This rule captures the idea that determinacy is transitive — if X pins down Y, and Y pins down Z, then X indirectly pins down Z as well.

Formal justification: Take any two tuples t1 and t2 that agree on X. Since X → Y, they agree on Y. Since Y → Z, they agree on Z. Therefore X → Z.

This is perhaps the most practically significant axiom because it surfaces hidden dependencies. Consider a staffing relation with attributes {EmployeeID, DepartmentID, DepartmentBudget}:

EmployeeID → DepartmentID
DepartmentID → DepartmentBudget
---
By Transitivity: EmployeeID → DepartmentBudget

This transitive dependency — EmployeeID determining DepartmentBudget through DepartmentID — is exactly the kind of indirect relationship that causes update anomalies and motivates Third Normal Form (3NF). Transitivity is the tool that makes such hidden chains visible.

Derived Rules: Union, Decomposition, and Pseudotransitivity

Armstrong's three axioms are complete on their own, but for practical work it is convenient to derive additional rules that make reasoning faster and more direct. Each of these derived rules can be proven using only Reflexivity, Augmentation, and Transitivity.

Union Rule: If X → Y and X → Z, then X → YZ.

This rule says that if a single determinant X determines two separate sets of attributes Y and Z, you can combine the right-hand sides. Proof sketch:

1. X → Y                    (given)
2. X → Z                    (given)
3. X → XZ                   (Augmentation on step 2: X → Z, augment with X)
4. XZ → YZ                  (Augmentation on step 1: X → Y, augment with Z)
5. X → YZ                   (Transitivity on steps 3 and 4)

Practical use: if you know {OrderID → CustomerID} and {OrderID → OrderDate}, you can immediately write {OrderID → CustomerID, OrderDate} without separate steps.

Decomposition Rule: If X → YZ, then X → Y and X → Z.

This is the inverse of Union. If X determines a combined set of attributes, it determines each attribute (or subset) individually. Proof sketch:

1. X → YZ                   (given)
2. YZ → Y                   (Reflexivity, since Y ⊆ YZ)
3. X → Y                    (Transitivity on steps 1 and 2)
Similarly, YZ → Z by Reflexivity, giving X → Z by Transitivity.

Decomposition is invaluable when checking whether a particular individual attribute is determined by some set X. You decompose the known dependency into its atomic parts and examine each one. It is also heavily used when computing attribute closures.

Pseudotransitivity Rule: If X → Y and WY → Z, then WX → Z.

Pseudotransitivity generalizes Transitivity by allowing an extra set of attributes W to appear on the left. It captures situations where Y is only part of the determinant for Z, and W supplies the remaining needed attributes. Proof sketch:

1. X → Y                    (given)
2. WY → Z                   (given)
3. WX → WY                  (Augmentation on step 1: X → Y, augment with W)
4. WX → Z                   (Transitivity on steps 3 and 2)

Example: Suppose you know {CourseID → InstructorID} and {InstructorID, Semester} → Classroom. By Pseudotransitivity with W = {Semester}, you can derive {CourseID, Semester} → Classroom — a useful composite dependency that neither of the original rules alone could produce.

These derived rules do not extend the power of the axiom system; they are strictly shortcuts. Any dependency derivable with the Union, Decomposition, or Pseudotransitivity rules could also be derived, more laboriously, using only the three axioms.

Using These Properties to Reason About Data: Attribute Closure

The most direct application of all the rules above is the computation of an attribute closure. Given a set of functional dependencies F and a set of attributes X, the closure X⁺ (read "X-plus") is the complete set of all attributes that are functionally determined by X under F. To compute it, you start with X itself and repeatedly apply every dependency in F whose left-hand side is already contained in the current closure, adding the right-hand side each time, until no more attributes can be added.

Algorithm outline:

closure = X
repeat:
    for each dependency (L → R) in F:
        if L ⊆ closure:
            closure = closure ∪ R
until closure does not change
return closure

Worked example: Let R = (A, B, C, D, E, F) with F = {A → BC, BC → DE, D → F}. Compute {A}⁺:

Start:       closure = {A}
Apply A→BC:  closure = {A, B, C}
Apply BC→DE: closure = {A, B, C, D, E}
Apply D→F:   closure = {A, B, C, D, E, F}
No more rules apply.
Result: {A}+ = {A, B, C, D, E, F}

Because {A}⁺ contains every attribute in R, A is a superkey. If no proper subset of A is also a superkey, then A is a candidate key. This is how attribute closure connects directly to key identification — one of the most fundamental tasks in schema design.

Attribute closure also answers the question of whether a specific functional dependency X → Y follows from a set F: simply compute X⁺ under F, and check whether Y ⊆ X⁺. If yes, X → Y is entailed by F; if no, it is not. This test replaces the need to manually trace chains of axiom applications.

Soundness and Completeness of Armstrong's System

A critical theoretical property of Armstrong's axioms is that they are both sound and complete with respect to functional dependencies:

• Soundness means that every dependency derivable using the axioms genuinely holds in every relation that satisfies F. The axioms never generate false dependencies. This is why you can trust the closure computation: if X → Y appears in X⁺, it truly holds.
• Completeness means that if a dependency X → Y logically follows from F (i.e., it holds in every relation satisfying F), then it can be derived using the axioms. Nothing is missed. If X → Y does not appear in X⁺, then there exists some valid relation satisfying F in which X → Y is violated.

Together, soundness and completeness mean that the axioms give you an exact characterization of logical consequence for functional dependencies. This makes them not just a convenient toolkit but a theoretically complete foundation — a rare and powerful property in any formal system.

Understanding these types and properties of functional dependencies — trivial vs. non-trivial, the three axioms, the derived rules, and closure computation — equips you to work rigorously with any relational schema. Whether you are identifying keys, checking whether a proposed decomposition is lossless, or deciding whether a relation violates a particular normal form, all of those tasks reduce, at bottom, to reasoning about functional dependencies using exactly these tools.