Database 1
Database Design

Prof. dr. Paul M.E. De Bra

Dept. of Computer Science

Eindhoven Univ. of Technology

Augmentation and Transitivity rules

Prove (using the definition of fd) that if X, Y and Z are sets of attributes of a relation scheme R, and the fd X  Y holds in R, then XZ  YZ also holds in R.

Prove (using the definition of fd) that if X, Y and Z are sets of attributes of a relation scheme R, and the fds X  Y and Y  Z hold in R, then X  Z also holds in R.

Bogus rules

Disprove that if X and Y and Z are sets of attributes of a relation scheme R, and the fd X  Y holds in R, then Y  X also holds in R.

Disprove that if X, Y and Z are sets of attributes of a relation scheme R, and the fds X  Y and Y  Z hold in R, then Z  X also holds in R.

Disprove that if X, Y and Z are sets of attributes of a relation scheme R, and the fds XY  Z holds in R, then X  YZ also holds in R.

Preparation for colstruction 2

The preparation is for colstruction 2 instead of labsession 2 because of a holiday.

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

7.3.2 explains inference rules, and the closure of a set of functional dependencies

7.3.3 explains the closure of attribute sets

In this colstruction we are going to discuss properties of functional dependencies. We are going to see how we prove or disprove properties of functional dependencies.

There are rules through which we can deduce that a set of functional dependencies logically implies some other functional dependencies. This deduction is done through “inference rules”. Before we are allowed to use such rules we must prove that they are correct. We must do this by using the definition of what functional dependencies are.

Example: augmentation:

for simplicity we write r  R to indicate that an instance r is a valid instance for scheme R. We write t  r to indicate that t is a tuple of r. We write X  R to indicate that X is a subset of the set of attributes of R. We write XY to mean X  Y.

The first proof (augmentation) goes as follows:

(r  R,  t1, t2  r : t1[X]=t2[X] : t1[Y]=t2[Y]) (this is the definition of X  Y)

(r  R,  t1, t2  r : t1[Z]=t2[Z] : t1[Z]=t2[Z]) (this is always true)

 (because ((A  B)  (C  D)  (A  C)  (B  D))

(r  R,  t1, t2  r : t1[X]=t2[X]  t1[Z]=t2[Z] : t1[Y]=t2[Y]  t1[Z]=t2[Z])

 (because a function t[X  Z] = t[X]  t[Z])

(r  R,  t1, t2  r : t1[XZ]=t2[XZ] : t1[YZ]=t2[YZ])

(this is the definition of XZ  YZ)

When coming up with inference rules one may “think” that a rule holds when in fact it does not. In order to show that a rule does not hold you must find (using your imagination) at least one instance in which the given functional dependencies hold and in which the “supposedly implied” functional dependencies do not hold.

We study the remainder of chapter 7 upto and including section 7.3.3.

The sections 7.3.2 and 7.3.3 deal with the topic of “closure”.

In section 7.3.2 the closure of a set of functional dependencies is discussed, using inference rules. An important aspect is that when you define a new inference rule you want to verify whether it really adds something to the set of rules you already have. Proving rules by using other rules is something we are going to practice a lot.

In section 7.3.3 the closure of a set of attributes is discussed. These are all the attributes that are functionally dependent on a given set of attributes. Here too the concept of inference rules plays an important role.

Databases 1, Colstructie 1

Database Design, Functional Dependencies

Paul De Bra

2003-04-01T22:52:54

Paul De Bra