Uji Dekomposisi, Uji Lossless/Lossy, Uji Depedency Preservation

SOAL LATIHAN --Uji Dekomposisi, Uji Lossless/Lossy, Uji Depedency Preservation !!!

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 :

v 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.

v 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

v 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 :

v 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.

v 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

v 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 :

v 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.

v 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

v 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 :

v 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.

v Uji Lossless / Lossy

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

                     = ( )

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

v 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.