Database 1
Database Design

Prof. dr. Paul M.E. De Bra

Dept. of Computer Science

Eindhoven Univ. of Technology

Lossless Join Decomposition

Lossless Join means:

Let { R1 , R2 } be a decomposition of R (meaning that R1  R2 = R); the decomposition is lossless if for every legal instance r of R: r = R1(r)  R2(r)

We have proved that a decomposition is lossless if R1  R2  R1 or R1  R2  R2

This is a sufficient condition, but not a necessary condition.

Multivalued dependencies

Example

Database:

course book lecturer

DB1	Silberschatz	debra

DB1	logica	debra

DB1	Silberschatz	voorhoeve

DB1	logica	voorhoeve

ISO	Silberschatz	houben

ISO	MSmanual	houben

Is this a good design??

What is going on in this example:

For each course a number of books are prescribed

For each course there are a number of lecturers

A lecturer cannot choose different books for a course

Multivalued dependency {course} {book}

If lecturer A1 and book B1 and lecturer A2 and book B2

belong to course C, then A1 must also use book B2 for

course C and A2 must also use book B1.

(t1, t2  r : t1[course]=t2[course] :

(t3  r : t3[course]=t1[course] : t3[lecturer]=t1[lecturer] 

t3[book]=t2[book]))

Note that {course} {book} and {course} {lecturer}

have the same meaning

MVD and lossless join decomposition

Let X, Y be sets of attributes of R.

X  Y means that for all instances r of R:
(t1, t2  r : t1[X]=t2[X] :
(t3  r : t3[X]=t1[X] : t3[Y]=t1[Y]  t3[R-Y]=t2[R-Y]))

A decomposition of R into (X,Y), (X,R-Y) is a lossless-join decomposition if and only if
X  Y holds in R

Inference Rules for FDs and MVDs

The following set of rules for fd's and mvd's is complete:
Let X, Y, Z, V, W be sets of attributes of R:

F1: if Y  X then X  Y

F2: if X  Y then XZ  YZ

F3: if X  Y and Y  Z then X  Z

M1: if X  Y then X  R  Y

M2: if X  Y and V  W then XW  YV

M3: if X  Y and Y  Z then X  Z  Y

FM1: if X  Y then X  Y

FM2: if X  Y and Y  Z then X  Z  Y

Fourth Normal Form

A relation scheme R with set of FDs and MVDs FM is in 4NF if (and only if) for every non-trivial mvd X  Y  FM+ X is a superkey (for R).

A database scheme D = {R1,..., Rn} is in 4NF if (and only if) i  {1,...,n}: Ri is in 4NF.

Decomposition into 4NF is done in the same way as decomposition into BCNF (but with X  Y or X  Y instead of just X  Y in every decomposition step).

In this colstruction we look at multivalued and join dependencies.

De bovenstaande decompositie is niet lossless-join. (Ze is overigens wel in BCNF.)

Je toont niet-lossless-join zijn aan met een tegenvoorbeeld: een tabel waarbij

r = R1(r)  R2(r)

niet waar is:

A B C

===========

0 0 0

1 0 0

0 0 1

Bij deze voorbeeldtabel geldt dat hij niet lossless gedecomponeerd wordt door te projecteren op {A,B} en op {B,C} want in de join van die twee komt een tupel (1,0,1) voor.

Databases 1, Colstructie 14

Database Design, (vertical) decomposition

Paul De Bra

2003-04-01T22:52:54

Paul De Bra