May 2013 Archive

Functional Dependencies

"From E/R Diagrams to Relational Designs" and "Converting Subclass Structures to Relations" showed us how to convert E/R designs into relational schemas. It is also possible for database designers to produce relational schemas directly from application requirements,

Keys of Relations

We say a set of one or more attributes {A1, A2,. . . ,An} is a key for a relation R if: 1. Those attributes functionally determine all other attributes of the relation. That is, because relations are sets, it is impossible for two different tuples of R to agree on all of A1, A2, ... ,An.


A set of attributes that includes a key is called a superkey, short for "superset of a key". In this way, every key is a superkey. However, some superkeys are not (minimal) keys. Note

Rules About Functional Dependencies

In this section, we shall learn how to reason about FD's. That is, suppose we are told of a set of FD’s that a relation satisfies. Sometimes, we can deduce that the relation must satisfy

The Splitting/Combining Rule

Recall that in “Functional Dependencies” we defined the FD: A1A2…An → B1B2..Bm to be a shorthand for the set of FD's:

Trivial Functional Dependencies

A FD A1A2 . . . An → B is said to be trivial if B is one of the A's. For instance, title year → title is a trivial FD. Every trivial FD holds in every relation, since it says that "two tuples that agree in all of A1,

Computing the Closure of Attributes

Before proceeding to other rules, we shall give a general principle from which all rules follow. Assume {A1, A2,. . . ,An} is a set of attributes and S is a set of FD's. The closure of {A1, A2, .

Why the Closure Algorithm Works

In this section, we shall show why the closure algorithm correctly decides whether or not a FD A1A2 . . . An → B follows from a given set of FDs S. There are two parts to the proof:

The Transitive Rule

The transitive rule lets us cascade two FD's. ● If A1A2 . . . An → B1B2 . . . Bm and B1B2 . . . Bm → C1C2 . . . Ck hold in relation R, then A1A2 . . . An → C1C2 . . . Ck also holds in R.

Closing Sets of Functional Dependencies

As we have seen, given a set of FD's, we can sometimes infer some other FD's, including both trivial and nontrivial FD's. We shall, in later sections, want to differentiate between given FD's that are stated initially for a relation and derived FD's that are inferred using one of the

Page 2 of 3 « Previous 1 2 3 Next »