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)

What is wrong with the following decomposition?

R = {A,B,C} and F = { A  B, C  B} and we replace R by { R1 , R2 } where R1 {A,B} and R2 = {C,B}.

Boyce-Codd Normaalvorm

A relation scheme R is in BCNF if (and only if) for every non-trivial fd X  Y  F+ X is a superkey (for R).

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

Let R = {A,B,C} and F = { A  B, C  B} and let us decompose R into by { R1 , R2 } where R1 {A,B} and R2 = {C,B}. Is this decomposition in BCNF? Is this the “best” decomposition in BCNF? (Can you find a better one?)

Sufficient Condition for Lossless Join

Lossless Join means:

Let { R1 , R2 } be a decomposition of R (meaning that R1  R2 = R);

Prove that for all legal instances r: r  R1(r)  R2(r)

Prove that this decomposition is lossless if R1  R2  R1 or R1  R2  R2

Can you give an example of a lossless join decomposition (instance) when neither R1  R2  R1 nor R1  R2  R2 hold?

Dependencies in a decomposition

Which dependencies hold in the R1 and R2?

R = {A,B,C} and F = { A  B, B  C} and we replace R by { R1 , R2 } where R1 {A,B} and R2 = {B,C}.

R = {A,B,C} and F = { A  B, C  B} and we replace R by { R1 , R2 } where R1 {A,B} and R2 = {A,C}.

R = {A,B,C} and F = { A  B, B  C} and we replace R by { R1 , R2 } where R1 {A,B} and R2 = {A,C}

Preparation for colstruction 7

Study chapter 7 up to and including section 7.7

This deals with third normal form and dependency preserving decomposition

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.

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.

De decompositie is in BCNF, maar ze is niet lossless join.

Laat ook met het algoritme een decompositie maken. (7.21)

- als t  r dan is t[r1]  r1 en t[r2]  r2, en t = t[r1]  t[r2]

(we beschouwen t[r1] hier als een functie)

voor elke t  r geldt dat de twee projecties van t in r1 resp. r2 voorkomen, en omdat

t[r1] en t[r2] dezelfde waarde hebben op r1  r2 worden ze ook in de join gematcht.

- om het lossless zijn te bewijzen moeten we laten zien dat R1(r)  R2(r)  r.

stel dat R1  R2  R1 en neem t1 en t2 uit r zodat t1[r1  r2] = t2[r1  r2]

(dus t1 en t2 worden gematcht in de join). Het nieuwe tupel t1[r1]  t2[r2]

is hetzelfde als t2[r1]  t2[r2] en dus als t2 en dus zit dat tupel gewoon in r.

- de truuk is om een tabel te maken die bestaat uit twee disjuncte stukjes

zodat in het ene stukje R1  R2 R1 en in het andere R1  R2 R2 geldt.

Neem { A, B, C } en B  A en B  C gelden allebei niet en toch is

{A,B} en {B,C} een lossless join decompositie

A B C

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

0 0 0

0 0 1

1 1 2

2 1 2

The first example is trivial.

The second example shows that we lose the ability to express C->B without taking a join.

The third example shows that we lose B->C but we do have A->C in R2. This illustrates that we must take F+ before projecting it on the subrelations.

Databases 1, Colstructie 11

Database Design, (vertical) decomposition

Paul De Bra

2003-04-01T22:52:54

Paul De Bra