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
Slide 4
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).