Database 1
Database Design

Prof. dr. Paul M.E. De Bra

Dept. of Computer Science

Eindhoven Univ. of Technology

Canonical Cover Exercise

Let {A,B,C,D,E} be the attributes of R and let F={AB, ABC, DEC, EBCD}. Compute Fc.

Completeness for Subset Constraints

A relation scheme R satisfies the subset constraint Y X if and only if in for every instance r of R and AY and  t1r BX and t2r such that t1(A)=t2(B). Prove that the following rules are complete for subset constraints:

D1: if Y  X then Y X

D2: if Y X and Z is a set of attributes of R then YZ XZ

D3: if Y X and Z Y then Z X

Note that these rules closely resemble the Armstrong rules for functional dependencies. (use this similarity!)

Preparation for labsession 4

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

Section 7.4 explains (vertical) decomposition.

Section 7.5 explains desirable properties of decomposition: the lossless-join property and the dependency preservation property.

In this colstruction we are going to futrher discuss properties of constraints. We are going to play with canonical covers and with completeness of rules.

Following the algorithm of Figure 7.8 we perform the following steps:

1. Initially we cannot apply the union rule

2. We check whether B is extraneous in ABC.

From AB we deduce AAB by augmentation.

From AAB and ABC we deduce AC by transitivity.

We can thus replace ABC by AC without making F stronger.

3. We can now apply the union rule to replace AB and AC by ABC.

4. We now check whether D is extraneous in DEC.

From EBCD and the trivial BCDD we deduce ED by transitivity.

From ED we deduce EDE by augmentation.

From EDE and DEC we deduce EC by transitivity.

We can thus replace DEC by EC without making F stronger.

5. We can now apply the union rule to replace EC and EBCD by EBCD.

The resulting set is {ABC, EBCD}. It can not be reduced any further.

In the proof we may also use D4, D5 and D6 from labsession 2 of course. (Since they have been proven by using on ly D1, D2 and D3.

We're using  here because the square subset symbol doesn't exist in a font. (Sorry)

First we define the closure of X with respect to the set D of subset constraints as:

X+ = { A | A  X can be deduced from D by D1,D2,D3 }

Suppose that Y  X cannot be deduced from D. We are going to create an instance r in which Y  X does not hold but in which all the subset constraints of D hold.

Note that when Y  X cannot be deduced from D then Y  X+. (Same argument as for fd's: apply union D4 and decomposition D5 rules.)

attributes of X+ | other attributes

-----------------------------------

0 0 0 ... 0 0 0 | 0 0 0 ... 0 0 0

0 0 0 ... 0 0 0 | 1 1 1 ... 1 1 1

1. Clearly Y  X does not hold in r because value 1 occurs in Y and not in X.

2. Let W  V be a subset dependency in D.

If V  X+ then W  V holds because the values 0 and 1 occur under V.

If V  X+ then both V  X and W  X can be deduced from D by D1, D2, D3. This means that W is a subset of X+ and thus only the value 0 occurs under W, and then the instance r satisfies W  V.

Databases 1, Colstructie 7

Database Design, Functional Dependencies, Inclusion Dependencies

Paul De Bra

2003-04-01T22:52:54

Paul De Bra