Armstrong’s Axioms, Attribute Closure, and Minimal Cover in DBMS

Introduction

A database design may begin with a few known functional dependencies, but those rules can imply additional dependencies. Understanding these consequences helps identify keys, recognize unnecessary rules, and prepare a relation for normalization.

Armstrong’s axioms provide rules for deriving dependencies. Attribute closure finds everything a group of attributes determines, while a minimal cover expresses the same dependency information without unnecessary parts.

An Example Relation

Consider a college database that stores student and department information together in a relation named StudentDepartment.

StudentDepartment : initial data

The example follows these business rules:

• Student identification: Each StudentID identifies one student with one current name and department.

• Department identification: Each DeptID identifies one department with one current name.

• Names: Student names and department names are not required to be unique.

A functional dependency states that rows agreeing on certain attributes must also agree on the attributes those values determine. The notation X → Y means “X determines Y,” where X and Y represent attribute sets.

The business rules establish:

• StudentID → Name, DeptID: A student identifier determines the student’s name and department identifier.

• DeptID → DeptName: A department identifier determines its department name.

A comma groups attributes together. The displayed rows illustrate these rules, but the rules come from the database requirements rather than from accidental patterns in a small sample.

These dependency expressions are formal notation, not executable SQL queries.

Armstrong’s Three Axioms

Armstrong’s axioms are inference rules used to derive functional dependencies that logically follow from known dependencies. Braces such as {StudentID, Name} represent a set of attributes.

• Reflexivity: A set of attributes determines any attributes already contained within it. For example, {StudentID, Name} → Name holds because the starting set already includes Name.

• Augmentation: Adding the same attributes to both sides of a valid dependency preserves its validity. From StudentID → Name, adding DeptID to both sides gives {StudentID, DeptID} → {Name, DeptID}.

• Transitivity: If one attribute set determines a second, and the second determines a third, the first also determines the third. Here, StudentID → DeptID and DeptID → DeptName imply StudentID → DeptName.

These axioms are sound, meaning they produce only valid consequences of the given rules, and complete, meaning repeated application can derive every functional dependency implied by those rules.

Useful Derived Rules

Several convenient rules follow from the three axioms. In the expressions below, X, Y, Z, and W represent attribute sets, and commas combine those sets.

For example, decomposition separates StudentID → Name, DeptID into StudentID → Name and StudentID → DeptID.

The same splitting rule does not apply to the left side. If a dependency requires two attributes together, neither attribute is automatically sufficient on its own.

What Is Attribute Closure?

The attribute closure of a set X, written X⁺, is the set of all attributes that can be determined from X using the given dependencies. The superscript ⁺ means “closure”; it is not arithmetic addition.

To calculate closure, start with the attributes in X. Repeatedly apply any dependency whose entire left side is already available, adding its right-side attributes. Stop when no new attributes can be added.

For StudentID, the calculation is:

The final set contains every attribute in StudentDepartment. Therefore, StudentID is a superkey. It is also a candidate key because no attribute can be removed from this identifier while preserving its identifying ability under the stated rules.

By comparison, DeptID⁺ = {DeptID, DeptName}, where = states the contents of the closure. It does not include the student identifier or name, so DeptID is not a superkey of this relation.

Closure also tests whether a dependency follows from known rules. To test X → Y, calculate X⁺ and check whether it contains every attribute in Y.

Attribute Closure and Dependency Closure

These two uses of “closure” describe different results:

• Attribute closure, X⁺: Contains attributes determined by the starting attribute set X.

• Dependency closure, F⁺: Contains every functional dependency implied by a starting dependency set named F.

For example, if F contains StudentID → DeptID and DeptID → DeptName, then F⁺ also contains StudentID → DeptName.

Two dependency sets are equivalent when they imply exactly the same dependencies. Their written rules can look different while expressing the same constraints.

What Is a Minimal Cover?

A minimal cover is an equivalent version of a dependency set with unnecessary parts removed. It preserves the original rules and all their logical consequences.

Using the single-attribute-right-side convention, a minimal cover has three properties:

• One attribute on each right side: Every dependency determines a single attribute.

• No extraneous left-side attributes: No attribute can be removed from a determinant without changing the meaning of the dependency set.

• No redundant dependencies: No entire dependency can be removed while preserving the same logical consequences.

An extraneous attribute is an unnecessary part of a dependency. A redundant dependency is an unnecessary whole rule. Removing either requires checking that the remaining rules preserve the original meaning.

A dependency set can have more than one valid minimal cover. Minimality means that the stated simplifications are no longer possible; it does not guarantee a unique written answer.

A Compact Example

The same relation is repeated below for reference. This example simplifies its dependency rules; the stored rows remain unchanged.

StudentDepartment : reference data

Suppose the rules are written as the following dependency set:

• StudentID → Name, DeptID

• {StudentID, Name} → DeptName

• DeptID → DeptName

The middle dependency adds no new business requirement: a student identifier already leads to the department name through DeptID.

1. Separate the right-side attributes

Replace StudentID → Name, DeptID with two dependencies:

• StudentID → Name

• StudentID → DeptID

Each resulting dependency now has one attribute on its right side. The other dependencies remain in the set.

2. Remove the extraneous attribute

In {StudentID, Name} → DeptName, Name is unnecessary. Starting with StudentID alone already reaches DeptID, and then DeptName.

Therefore, this dependency can be simplified to StudentID → DeptName without changing the rules expressed by the set.

3. Remove the redundant dependency

Temporarily remove StudentID → DeptName and check the remaining rules. StudentID → DeptID and DeptID → DeptName still imply it through transitivity, so it can be removed permanently.

The resulting minimal cover is:

• StudentID → Name

• StudentID → DeptID

• DeptID → DeptName

Every right side contains one attribute, no left-side attribute is unnecessary, and removing any remaining dependency would lose an original requirement. The final set therefore expresses the same constraints as the starting set.

When simplifying larger sets, make changes one at a time and recheck the current dependencies. A dependency must be tested using the remaining rules, rather than being allowed to justify itself.

Why These Concepts Matter

These tools support several database-design tasks:

• Finding keys: Attribute closure shows whether an attribute set determines the entire relation.

• Checking implied rules: Armstrong’s axioms and closure reveal whether a dependency follows from existing requirements.

• Simplifying design reasoning: A minimal cover removes unnecessary parts of the dependency description.

• Supporting normalization: Clear dependencies help determine how facts should be organized into related tables.

Computing a minimal cover does not itself normalize a table, remove duplicate data, or change stored records. It simplifies the rules used to reason about the design; table decomposition is a separate step.

Summary

Armstrong’s axioms derive valid consequences from known functional dependencies. Attribute closure identifies everything a set of attributes determines and helps test dependencies and candidate keys.

A minimal cover preserves the same dependency information while removing extraneous attributes and redundant rules. Together, these concepts provide a practical foundation for understanding and improving relational database design.