*Why the Closure Algorithm Works*

On May 25, 2013, In The Relational Data Model by Admin

Views (2743)

In this section, we shall show why the closure algorithm correctly decides whether or not a FD A_{1}A_{2} . . . A_{n} → B follows from a given set of FD's S. There are two parts to the proof:

1. We must prove that the closure algorithm does not claim too much. That is, we must show that if A_{1}A_{2} . . . A_{n} → B is asserted by the closure test (i.e., B is in {A_{1}, A_{2}, . . . , A_{n}}^{+}), then A_{1}A_{2} . . . A_{n} → B holds in any relation that satisfies all the FD's in S.

2. We must prove that the closure algorithm does not fail to discover a FD that truly follows from the set of FD's S.

### Why the Closure Algorithm Claims only True FD's

We can prove by induction on the number of times that we apply the growing operation of step 2 that for every attribute D in X, the FD A_{1}A

_{2}. . . A

_{n}→ D holds (in the special case where D is among the As, this FD is trivial). That is, every relation R satisfying all of the FD's in S also satisfies A

_{1}A

_{2}. . . A

_{n}→ D.

**BASIS:**The basis case is when there are zero steps. Then D must be one of A

_{1}, A

_{2}. . . , A

_{n}, and surely A

_{1}A

_{2}. . . A

_{n}→ D holds in any relation, because it is a trivial FD.

**INDUCTION:**For the induction, suppose D was added when we used the FD B

_{1}B

_{2}. . . B

_{m}→ D. We know by the inductive hypothesis that R satisfies A

_{1}A

_{2}. . . A

_{n}→ B

_{i}for all i = 1,2, . . . , m. Put another way, any two tuples of R that agree on all of A

_{1}, A

_{2}, . . . , A

_{n}also agree on all of B

_{1}, B

_{2}, . . , B

_{m}. Since R satisfies B

_{1}B

_{2}. . . B

_{m}→ D, we also know that these two tuples agree on D. Thus, R satisfies A

_{1}A

_{2}. . . A

_{n}→ D.

### Why the Closure Algorithm Discovers All True FD's

Suppose A_{1}A

_{2}. . . A

_{n}→ B were a FD that the closure algorithm says does not follow from set S. That is, the closure of {A

_{1}, A

_{2}, . . . , A

_{n}} using set of FD's S does not include B. We must show that FD A

_{1}A

_{2}. . . A

_{n}→ B really doesn't follow from S. That is, we must show that there is at least one relation instance that satisfies all the FD's in S, and yet does not satisfy A

_{1}A

_{2}. . . A

_{n}→ B.

This instance I is actually quite simple to construct; it is shown in the following figure. I has only two tuples t and s. The two tuples agree in all the attributes of {A

_{1}, A

_{2}, . . . , A

_{n}}

^{+}, and they disagree in all the other attributes. We must show first that I satisfies all the FD's of S, and then it does not satisfy A

_{1}A

_{2}. . . A

_{n}→ B.

_{1}C

_{2}. . . C

_{k}→ D in set S that instance I does not satisfy. Since I has only two tuples, t and s, those must be the two tuples that violate C

_{1}C

_{2}. . . C

_{k}→ D. That is, t and s agree in all the attributes of {C

_{1}, C

_{2}, . . . , C

_{k}}, yet disagree on D. If we examine the above figure, we see that all of C

_{1}, C

_{2}, . . . , C

_{k}must be among the attributes of {A

_{1}, A

_{2}, . . . , A

_{n}}

^{+}, because those are the only attributes on which t and s agree. Likewise, D must be among the other attributes, because only on those attributes do t and s disagree.

But then we did not compute the closure correctly. C

_{1}C

_{2}. . . C

_{k}→ D should have been applied when X was {A

_{1}, A

_{2}, . . . , A

_{n}} to add D to X. We conclude that C

_{1}C

_{2}. . . C

_{k}→ D cannot exist; i.e., instance I satisfies S.

Second, we must show that I does not satisfy A

_{1}A

_{2}. . . A

_{n}→ B. However, this part is easy. Surely, A

_{1}, A

_{2}, . . . , A

_{n}are among the attributes on which t and s agree. Also, we know that B is not in {A

_{1}, A

_{2}, . . . , A

_{n}}

^{+}, so B is one of the attributes on which t and s disagree. Thus, I does not satisfy A

_{1}A

_{2}. . . A

_{n}→ B. We conclude that the closure algorithm asserts neither too few nor too many FD's; it asserts exactly those FD's that do follow from S.

### Tags

- algorithm
- attributes
- tuples
- Scrolling Cursors
- Protecting Against Concurrent Updates
- Modifications by Cursor
- Cursors
- Instead-Of Triggers
- Triggers in SQL
- Schema-Level Constraints and Triggers
- Tuple-Based CHECK Constraints
- Constraints on Attributes and Tuples
- Declaring Foreign-Key Constraints
- Keys Declared With UNIQUE
- Constraints and Triggers
- Modifying Views
- View Definitions
- Introduction to Selection of Indexes
- Default Values / Indexes
- Simple Table Declarations
- Defining a Relation Schema in SQL
- Deletion / Updates
- Database Modifications
- Grouping / HAVING Clauses
- Full-Relation Operations
- Natural Joins / Outerjoins
- Subqueries in FROM Clauses
- Conditions Involving Tuples
- Subqueries
- Union, Intersection, and Difference of Queries
- Interpreting Multirelation Queries
- Tuple Variables
- Disambiguating Attributes
- Queries Involving More Than One Relation
- Null Values and Comparisons Involving NULL
- Selection in SQL
- Projection in SQL
- The Database Language SQL
- Additional Constraint Examples
- Extending the Projection Operator
- Grouping
- Extended Operators of Relational Algebra
- Selection on Bags / Product of Bags / Joins of Bags
- Union, Intersection, and Difference of Bags
- Relational Operations on Bags
- A Linear Notation for Algebraic Expressions
- Dependent and Independent Operations
- Renaming
- Combining Operations to Form Queries
- Selection / Cartesian Product
- Set Operations on Relations
- An Algebra of Relational Operations
- Relational Algebra
- Attribute Lists
- Information Integration Via Semistructured Data
- Semistructured Data Representation
- Object-Oriented Versus Object-Relational
- Nested Relations
- The Object-Relational Model
- What If There Is No Key
- Representing ODL Relationships
- Representing Other Type Constructors
- Representing Set-Valued Attributes
- Nonatomic Attributes in Classes
- Declaring Keys in ODL
- Subclasses in ODL / Multiple Inheritance in ODL
- Types in ODL
- Methods in ODL
- Multiplicity of Relationships
- Relationships in ODL / Inverse Relationships
- Attributes in ODL
- Introduction to ODL
- The Type System
- Relationships Among Normal Forms
- Decomposition into Fourth Normal Form
- Fourth Normal Form
- Reasoning About Multivalued Dependencies
- Definition of Multivalued Dependencies
- Multivalued Dependencies
- Third Normal Form
- Recovering Information from a Decomposition
- Decomposition into BCNF
- Boyce-Codd Normal Form
- Decomposing Relations
- Projecting Functional Dependencies
- Closing Sets of Functional Dependencies
- The Transitive Rule
- Computing the Closure of Attributes
- Trivial Functional Dependencies
- The Splitting/Combining Rule
- Rules About Functional Dependencies
- Keys of Relations
- Using Null Values to Combine Relations - Comparison of Approaches
- An Object-Oriented Approach
- Converting Subclass Structures to Relations
- Handling Weak Entity Sets
- Combining Relations
- From E/R Relationships to Relations
- From Entity Sets to Relations
- From E/R Diagrams to Relational Designs
- Relation Instances
- Equivalent Representations of a Relation
- Tuples / Domains
- Attributes / Schemas
- The Relational Data Model
- Summary of The Entity-Relationship Data Model
- Weak Entity Set Notation
- Requirements for Weak Entity Sets
- Representing Keys in the E/R Model
- Keys in the E/R Model
- The Modeling of Constraints
- Picking the Right Kind of Element
- Design Principles
- Subclasses in the E/R Model
- Converting Multiway Relationships to Binary
- Attributes on Relationships
- Multiway Relationships
- Elements of the E/R Model
- Database System Implementation
- Database Design
- Multimedia Data
- Relational Database Systems