First page Back Continue Last page Graphics
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?
Notes:
- 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