*Projecting Functional Dependencies*

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

Views (3710)

When we learn design of relation schemas, we shall also have need to answer the following question about FD's. Assume we have a relation R with some FD's F, and we "project" R by removing certain attributes from the schema. Consider S is the relation that results from R if we remove the elements corresponding to the dropped attributes, in all R's tuples. Since S is a set, duplicate tuples are replaced by one copy. What FD's hold in S?

The answer is acquired in principle by computing all FD's that:

a) Follow from F, and

b) Involve only attributes of S.

As there may be a large number of such FD's, and many of them may be unneeded (i.e., they follow from other such FD's), we are free to simplify that set of FD's if we wish. However, generally, the calculation of the FD's for S is in the worst case exponential in the number of attributes of S.

**Example :**Assume R(A, B, C, D) has FD's A → B, B → C, and C → D. Assume also that we wish to project out the attribute B, leaving a relation S(A,C, D). Technically, to find the FD's for S, we need to take the closure of all eight subsets of {A, C, D}, using the full set of FD's, including those involving B. However, there are some clear simplifications we can make.

● Closing the empty set and the set of all attributes cannot yield a nontrivial FD.

● If we already know that the closure of some set X is all attributes, then we cannot discover any new FD's by closing supersets of X.

Therefore, we may start with the closures of the singleton sets, and then move on to the doubleton sets if required. For each closure of a set X, we add the FD X → E for each attribute E that is in X

^{+}and in the schema of S, but not in X.

First, {A}

^{+}= {A, B, C, D). Thus, A → C and A → D hold in S. Note that A → B is true in R, but makes no sense in S because B is not an attribute of S.

Next, we suppose {C}

^{+}= {C,D}, from which we get the additional FD C → D for S. Since {D}

^{+}= {D}, we can add no more FD's, and are done with the singletons.

Since {A}

^{+}contains all attributes of S, there is no point in considering any superset of {A}. The reason is that whatever FD we could discover, for instance AC → D, follows by the rule for augmenting left sides from one of the FD's we already discovered for S by considering A alone as the left side. Therefore, the only doubleton whose closure we need to take is {C,D}

^{+}= {C,D}. This observation allows us to add nothing. We are done with the closures, and the FD's we have discovered are A → C, A → D, and C → D.

If we wish, we can observe that A → D follows from the other two by transitivity. Thus a simpler, equivalent set of FD's for S is A → C and C → D.

### Tags

- relation
- schema
- attributes
- 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
- Closing Sets of Functional Dependencies
- The Transitive Rule
- Why the Closure Algorithm Works
- 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
- 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