LOSSY atau LOSSLESS

Dekomposisi relasi

• Dekomposisi : memecah relasi/tabel menjadi relasi/tabel yang lebih kecil untuk mendapatkan skema yang tidak mengandung anomali dan redundansi
• Diketahui skema relasi R. Gugus relasi {R1, R2, ,…, Rn} disebut

            Dekomposisi dari R jika :

• Artinya {R1, R2, …, Rn} à dekomposisi dari R jika setiap atribut dalam R muncul paling sedikit di salah satu Ri untuk 1 £ i £ n

Dekomposisi relasi R menjadi gugus relasi {R1, R2, …, Rn} yang tidak menyebabkan hilangnya informasi disebut  Lossless-Join Decomposition. Lossless Join digunakan untuk menjamin keutuhan data untuk operasi gabungan (join) dan merupakan fokus dalam desain basis data relasional. Dalam penentuan Lossless biasanya digunakan parameter yang biasa disebut FD atau Fungsional Dependencies.

FD :

A1. Reflexive

                         Jika y Í x maka x à y

A2. Augmentation

                         Jika x à y maka (x,z) à (y,z)

A3. Transitive

                         Jika x à y dan y à z maka x à z

A4. Decomposition

                         Jika x à (y,z) maka x à y dan x à z

A5. Union

                         Jika x à y dan x à z maka  x à (y,z)

A6. Pseudotranstivity

                         Jika x à y dan (z,y) à w maka (x,z) à w

                                   

Contoh :

Diketahui skema relasi R=(A,B,C) dengan FD : A à B ; B à C

Didekomposisi menjadi R1=(A,B) dan R2=(B,C)

1. Apakah dekomposisi tsb Lossless-Joint ?
2. Apakah dekomposisi tsb memenuhi Dependency Preservation ?

Jawab :

a.       R1 È R2 = (A,B) È (B,C) = (A,B,C) = R

R1 Ç R2 = (A,B) Ç (B,C) = B

Lossless jika B à (A,B) atau B à (B,C).

Karena diketahui B à C maka BB à BC atau B à BC (Augmentasi). 

Jadi dekomposisi tsb Lossless.

b.      R=(A,B,C) dan F = {AàB, BàC}

Karena AàB dan BàC maka AàC. Maka dapat dibentuk closure

F⁺={AàB, BàC,AàC}.

R1=(A,B) dan F1={AàB}. Karena hanya AàB yang berlaku di R1.

R2=(B,C) dan F2={BàC}. Karena hanya BàC yang berlaku di R2.

F1 È F2 = {AàB,BàC}. Karena AàB dan BàC maka AàC.

Sehingga (F1 È F2 )⁺={AàB,BàC,AàC}=F⁺

Jadi dekomposisi tsb memenuhi Dependency Preservation.

Setelah melihat latihan nya coba kita lihat soal dan penyelesaiannya :

1.  R = (A,B,C,D,E,F,G,H) didekomposisi menjadi :

    R1 = (A,B,C,D,E) dan R2 = (C,D,F,G,H), dengan FD : C à (A,B,D), F à (G,H), D à (E,F)

   

    Jawab :

Ø Uji Dekomposisi

R1 È R2         = (A, B, C, D, E) È (C, D, F, G, H)

             = (A, B, C, D, E, F, G, H)

             = R

Terbukti bahwa {R1,R2} adalah dekomposisi dari R.

Ø Uji Lossless / Lossy

R1 Ç R2         = (A, B, C, D, E) Ç (C, D, F, G, H)

             = (C, D)

R1 Ç R2 à R1

(A, B, C, D, E) Ç (C, D, F, G, H) à (A, B, C, D, E)

CD à ABCDE

Dari     (1) C à ABD, maka (4) CD à ABD (augmentasi)

Dari     (3) D à EF, maka (5) D à E dan (6) D à F (dekomposisi)

Dari     (5) D à E, maka (7) CD à CE (augmentasi)

Dari     (4) CD à ABD dan (7) CD à CE, maka CD à ABCDE (union)

Terbukti LOSSLESS

R1 Ç R2 à R2

(A, B, C, D, E) Ç (C, D, F, G, H) à (C, D, F, G, H)

CD à CDFGH

Dari     (3) D à EF, maka (4) D à E dan (5) D à F (dekomposisi)

Dari     (5) D à F dan (2) F à GH maka (6) D à GH (transitif)

Dari     (6) D à GH, maka (7) CD à CGH (augmentasi)

Dari CD, maka (8) CD à CD (refleksif)

Dari     (5) D à F, maka (9) CD à CF (augmentasi)

Dari     (7) CD à CGH dan (8) CD à CD dan (9) CD à CF maka CD à CDFGH (union)

Terbukti LOSSLESS

Ø Uji Dependency Preservation

R = (A,B,C,D,E,F,G,H) dan F = { C à ABD, F à GH, D à EF }

Maka dapat dibentuk closure :

F⁺ = { C à ABD, F à GH, D à EF }

R1 = (A,B,C,D,E) dan F1 = { C à ABD }, karena hanya C à ABD yang berlaku di R1

R2 = (C,D,F,G,H) dan F2 = { F à GH }, karena hanya F à GH yang berlaku di R2

F1 È F2 = { C à ABD, F à GH }

Sehingga (F1 È F2 )⁺          = { C à ABD, F à GH }

                              ¹ F⁺

Jadi dekomposisi tersebut tidak memenuhi Dependency Preservation.

2.  R = (A,B,C,D,E) didekomposisi menjadi :

    R1 = (A,B,C,D) dan R2 = (C,D,E),

dengan FD :

(1) A à B

(2) (C,D) à E

(3) B à D

(4) E à A

    Jawab :

Ø Uji Dekomposisi

R1 È R2         = (A, B, C, D) È (C, D, E)

             = (A, B, C, D, E)

             = R

Terbukti bahwa {R1,R2} adalah dekomposisi dari R.

Ø Uji Lossless / Lossy

R1 Ç R2         = (A, B, C, D) Ç (C, D, E)

             = (C, D)

R1 Ç R2 à R1

(A, B, C, D) Ç (C, D, E) à (A, B, C, D)

CD à ABCD

Dari     (2) CD à E dan (4) E à A, maka (5) CD à A (transitif)

Dari     (5) CD à A dan (1) A à B, maka (6) CD à B (transitif)

Dari CD, maka (7) CD à CD (refleksif)

Dari     (5) CD à A dan (6) CD à B dan (7) CD à CD, maka CD à ABCD (union)

Terbukti LOSSLESS

R1 Ç R2 à R2

(A, B, C, D) Ç (C, D, E) à (C, D, E)

CD à CDE

Dari CD, maka (5) CD à CD (refleksif)

Dari     (2) CD à E dan (5) CD à CD, maka CD à CDE (union)

Terbukti LOSSLESS

Ø Uji Dependency Preservation

R = (A,B,C,D,E) dan F = { A à B, CD à E, B à D, E à A }

Dari A à B dan B à D bisa dibentuk A à D (transitif)

Dari CD à E dan E à A bisa dibentuk CD à A (transitif)

Maka dapat dibentuk closure :

F⁺ = { A à B, CD à E, B à D, E à A, A à D,  CD à A }

R1 = (A,B,C,D) dan F1 = { A à B, B à D }, karena A à B dan B à D yang berlaku di R1

R2 = (C,D,E) dan F2 = { CD à E }, karena hanya CD à E yang berlaku di R2

F1 È F2 = { A à B, B à D, CD à E }

Dari A à B dan B à D bisa dibentuk A à D (transitif)

Sehingga (F1 È F2 )⁺          = { A à B, B à D, CD à E, A à D }

                              ¹ F⁺

Jadi dekomposisi tersebut tidak memenuhi Dependency Preservation.

3.  R = (X,Y,Z,W,U,V) didekomposisi menjadi :

    R1 = (X,Y,Z,W) dan R2 = (W,U,V),

dengan FD :

(1) W à X

(2) X à Z

    Jawab :

Ø Uji Dekomposisi

R1 È R2         = (X, Y, Z, W) È (W, U, V)

             = (X, Y, Z, W, U, V)

             = R

Terbukti bahwa {R1,R2} adalah dekomposisi dari R.

Ø Uji Lossless / Lossy

R1 Ç R2         = (X, Y, Z, W) Ç (W, U, V)

             = (W)

R1 Ç R2 à R1

(X, Y, Z, W) Ç (W, U, V) à (X, Y, Z, W)

W à XYZW

Dari     (1) W à X dan (2) X à Z, maka (3) W à Z (transitif)

Dari CD, maka (4) W à W (refleksif)

Dari     (1) W à X dan (3) W à Z dan (4) W à W, maka W à XZW (union)

W à XZW ¹ W à XYZW

Terbukti LOSSY

R1 Ç R2 à R2

(X, Y, Z, W) Ç (W, U, V) à (W, U, V)

W à WUV

Dari CD, maka (4) W à W (refleksif)

W à W ¹ W à XYZW

Terbukti LOSSY

Ø Uji Dependency Preservation

R = (X,Y,Z,W,U,V) dan F = { W à X, X à Z }

Dari W à X dan X à Z bisa dibentuk W à Z (transitif)

Maka dapat dibentuk closure :

F⁺ = { W à X, X à Z, W à Z }

R1 = (X,Y,Z,W) dan F1 = { W à X, X à Z }, karena W à X dan X à Z yang berlaku di R1

R2 = (W,U,V) dan F2 = { }, karena tidak ada FD berlaku di R2

F1 È F2 = { W à X, X à Z }

Dari W à X dan X à Z bisa dibentuk W à Z (transitif)

Sehingga (F1 È F2 )⁺          = { W à X, X à Z, W à Z }

                              = F⁺

Jadi dekomposisi tersebut memenuhi Dependency Preservation.

4.  R = (A,B,C,D,E,F) didekomposisi menjadi :

    R1 = (A,B,C), R2 = (A,D,F) dan R3 = (E,D),

dengan FD :

A à (B,C)

D à (F,A)

    Jawab :

Ø Uji Dekomposisi

R1 È R2 È R3 = (A, B, C) È (A, D, F) È (E, D)

                     = (A, B, C, D, E, F)

                     = R

Terbukti bahwa {R1,R2} adalah dekomposisi dari R.

Ø Uji Lossless / Lossy

R1 Ç R2 Ç R3 = (A, B, C) Ç (A, D, F) Ç (E, D)

                     = ( )

R1, R2, R3 tidak memiliki irisan, maka tidak dapat diuji.

Ø Uji Dependency Preservation

R = (A,B,C,D,E,F) dan F = { A à BC, D à FA }

Maka dapat dibentuk closure :

F⁺ = { A à BC, D à FA }

R1 = (A, B, C) dan F1 = { A à BC }, karena hanya A à BC yang berlaku di R1

R2 = (A, D, F) dan F2 = { D à FA }, karena hanya D à FA yang berlaku di R2

R3 = (E, D) dan F3 = { }, karena tidak ada FD berlaku di R3

F1 È F2 = { A à BC, D à FA }

Sehingga (F1 È F2 )⁺          = { A à BC, D à FA }

                              = F⁺

Jadi dekomposisi tersebut memenuhi Dependency Preservation.