Database 1
Database Design

Prof. dr. Paul M.E. De Bra

Dept. of Computer Science

Eindhoven Univ. of Technology

Redundancy of Inference Rules

An inference rule r in a set of inference rules R for a type of constraints C is redundant if for all sets F of constraints of type C: F+{R-{r}} = F+

Prove that none of the Armstrong rules are redundant in the set of (3) Armstrong rules.

Prove that adding the union rule, the decomposition rule or the pseudotransitivity rule would make the set of rules redundant.

Inclusion Dependencies

Let X = (A1, ..., An) and Y = (B1, ... , Bn) be sequences of attributes of R. The inclusion dependency X Yholds in R if and only if in each legal instance r for R:

t1 r, t2r, i in 1..n: t1[Ai] = t2[Bi]

A simple inclusion dependency A B met A, B R holds in R if and only if in each legal instance r for R:

t1r, t2r: t1[A] = t2[B]

Give inference rules for ids and sids and prove that they are correct.

Preparation for labsession 2

Study chapter 7 of the database book, up to and including section 7.3.4.

Section 7.3.4 explains the notion of canonical cover. It deals with reducing the size of sets of functional dependencies to verify.

In this colstruction we are going to futrher discuss properties of functional dependencies. We are going to practice with inference rules some more, by defining another type of constraints..

Redundancy means that all the (logical) consequences we can deduce from a given set of constraints can be deduced using just a subset of the given inference rules. Note that it is important that we only consider constraints of a certain type. There may be logical consequences that cannot be deduced using the rules because they are of a different type.

Proving that a set of rules is not redundant is done by giving a small counterexample. We take a set of constraints and calculate all the consequences through the subset of rules. We then show that there is another consequence that is generated using the extra rule.

Example: to show that the reflexivity rule is not redundant we take the empty set of functional dependencies over a table with zero (or more) attributes. With augmentation and transitivity we cannot generate any fds because there are no fds to start from. With reflexivity however we can create the fd Ø  Ø.

For augmentation it is easiest to start from two attributes A and B and show that augmentation is needed to generate A  AB from A  B.

For transitivity it is easiest to start from three attributes.

Using the smallest possible number of attributes keeps the size of F+ down!

Proving the redundancy of the union and other rules is done by proving these rules using the other rules. This has been done in the homework already. It is just important to note that this is the way to prove redundancy.

The inclusion dependencies are something special because the order of the attributes plays an important role. In simple inclusion dependencies we do not yet see this.

For sid's the rules are reflexivity and transitivity.

For id's reflexivity and transitivity also hold, but then there is also the projection and permutation rule (which can be given as one rule or as two rules).

An attribute with the same index may be omitted on both sides, and the order of the attributes may be changed in the same way on the left and right sides.

We can only prove the correctness of the rules today as we are going to see the proofs of completeness later.

Databases 1, Colstructie 3

Database Design, Functional Dependencies, Inclusion Dependencies

Paul De Bra

2003-04-01T22:52:54

Paul De Bra