*Computing the Closure of Attributes*

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

Views (3486)

Before proceeding to other rules, we shall give a general principle from which all rules follow. Assume {A_{1}, A_{2},. . . ,A_{n}} is a set of attributes and S is a set of FD's. The closure of {A_{1}, A_{2}, . . . ,A_{n}} under the FD's in S is the set of attributes B such that every relation that satisfies all the FD's in set S also satisfies A_{1}, A_{2}, . . . A_{n} → B. That is, A_{1}, A_{2}, . . . A_{n} → B follows from the FD's of S. We denote the closure of a set of attributes A_{1}A_{2}....A_{n} by {A_{1}, A_{2},. . . ,A_{n}}^{+}.

To make the discussion of computing closures simpler, we shall allow trivial FD's, so A

_{1}, A

_{2},. . . ,A

_{n}are always in {A

_{1}, A

_{2}, . . . ,A

_{n}}

^{+}.

Figure (b) demonstrates the closure process. Starting with the given set of attributes, we frequently expand the set by adding the right sides of FD's as soon as we have included their left sides. Ultimately, we cannot expand the set any more, and the resulting set is the closure. The following steps are a more detailed rendition of the algorithm for computing the closure of a set of attributes {A

_{1}, A

_{2},. . .,A

_{n}} with respect to a set of FD's.

1. Let X be a set of attributes that ultimately will become the closure. First, we initialize X to be {A

_{1}, A

_{2}, . . . ,A

_{n}}.

2. Now, we repeatedly search for some FD B

_{1}B

_{2}... B

_{m}→ C such that all of B

_{1}, B

_{2},. . . , B

_{m}are in the set of attributes X, but C is not. We then add C to the set X.

3. Repeat step 2 as many times as necessary until no more attributes can be added to X. Since X can only grow, and the number of attributes of any relation schema must be finite, eventually nothing more can be added to X.

4. The set X, after no more attributes can be added to it, is the correct value of {A

_{1}, A

_{2}, .. . ,A

_{n}}

^{+}.

**Example (a) :**Let us consider a relation with attributes A, B, C, D, E, and F. Suppose that this relation has the FD's AB → C, BC → AD, D → E, and CF → B. What is the closure of {A,B}, that is, {A,B}

^{+}?

We start with X = {A, B}. First, notice that both attributes on the left side of FD AB → C are in X, so we may add the attribute C, which is on the right side of that FD. Thus, after one iteration of step 2, X becomes {A,B,C}.

Next, we see that the left, side of BC → AD is now contained in X, so we may add to X the attributes A and D. A is already there, but D is not, so X next becomes {A, B, C, D}. At this point, we may use the FD D → E to add E to X, which is now {A, B, C, D, E}. No more changes to X are possible. ln particular, the FD CF → B can not be used, because its left side never becomes contained in X. Thus, {A, B}

^{+}= {A,B, C, D, E}.

If we know how to compute the closure of any set of attributes, then we can test whether any given FD A

_{1}A

_{2}A

_{n}→ B follows from a set of FDs S. First compute {A

_{1}, A

_{2},. . . ,A

_{n}}

^{+}using the set of FDs S. If B is in {A

_{1}, A

_{2}, . . . . ,A

_{n}}

^{+}, then A

_{1}A

_{2}.. . A

_{n}→ B does follow from S, and if B is not in {A

_{1}, A

_{2}, .,,, A

_{n}}

^{+}, then this FD does not follow from S. More generally, a FD with a set of attributes on the right can be tested if we remember that this FD is a shorthand for a set of FD's. Thus, A

_{1}A

_{2}. . .A

_{n}→ B

_{1}B

_{2}. . .B

_{m}follows from set of FD's S if and only if all of B

_{1},B

_{2}, ...,B

_{m}are in {A

_{1},A

_{2},...,.A

_{n}}

^{+}.

**Example (b) :**Consider the relation and FD's of Example (a). Suppose we wish to test whether AB → D follows from these FD's. We compute {A, B}

^{+}, which is {A, B, C, D, E}, as we saw in that example. Since D is a member of the closure, we conclude that AB → D does follow.

On the other hand, consider the FD D → A. To test whether this FD follows from the given FD's, first compute {D}

^{+}. To do so, we start with X = {D}. We can use the FD D → E to add E to the set X. However, then we are stuck. We cannot find any other FD whose left side is contained in X = {D, E}, so {D}

^{+}= {D, E}. Since A is not a member of {D, E}, we conclude that D → A does not follow.

### Tags

- attributes
- relation
- schema
- Instead-Of Triggers
- 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
- Disambiguating Attributes
- Queries Involving More Than One Relation
- Null Values and Comparisons Involving NULL
- Selection in SQL
- Projection in SQL
- Additional Constraint Examples
- Extending the Projection Operator
- Extended Operators of Relational Algebra
- 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
- Natural Joins / Theta-Joins
- Selection / Cartesian Product
- Set Operations on Relations
- An Algebra of Relational Operations
- Relational Algebra
- Attribute Lists
- Document Type Definitions
- XML and Its Data Model
- Semistructured Data Representation
- Object-Oriented Versus Object-Relational
- References
- Nested Relations
- 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
- Reasoning About Multivalued Dependencies
- Definition of Multivalued Dependencies
- Multivalued Dependencies
- Third Normal Form
- Boyce-Codd Normal Form
- Projecting Functional Dependencies
- Closing Sets of Functional Dependencies
- The Transitive Rule
- Why the Closure Algorithm Works
- 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
- 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
- Attributes on Relationships
- Elements of the E/R Model
- The Entity-Relationship Data Model
- Relational Database Systems