Tugas I dan II Basis Data

TUGAS I

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

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

     R2 = (C,D,F,G,H)

     FD : C --> (A,B,D)

              F -->(G,H)

               D --> (E,F)

    

     Jawab :

Uji Dekomposisi

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

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

                 = R

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

Uji Lossless / Lossy

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

                 = (C, D)

R1 n R2 --> R1

(A, B, C, D, E) n (C, D, F, G, H) --> (A, B, C, D, E)

CD --> ABCDE

(1) C --> ABD

(4) CD --> ABD (augmentasi)

(3) D --> EF

(5) D --> E

(6) D --> F (dekomposisi)

(5) D --> E

(7) CD --> CE (augmentasi)

(4) CD --> ABD

(7) CD --> CE

CD --> ABCDE (union)

“Terbukti LOSSLESS”

Uji Dependency Preservation

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

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 U F2 = { C --> ABD, F --> GH }

Sehingga (F1 U 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)

R2 = (C,D,E),

FD :

(1) A --> B

(2) (C,D) --> E

(3) B --> D

(4) E --> A

     Jawab :

Uji Dekomposisi

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

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

                 = R

“Terbukti ! {R1,R2} adalah dekomposisi dari .

Uji Lossless / Lossy

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

                 = (C, D)

R1 n R2 --> R1

(A, B, C, D) n (C, D, E) --> (A, B, C, D)

CD --> ABCD

(2) CD --> E

(4) E --> A

(5) CD --> A (transitif)

(5) CD --> A

(1) A --> B

(6) CD --> B (transitif)

 (7) CD --> CD (refleksif)

 (5) CD --> A

(6) CD --> B

(7) CD --> CD

CD --> ABCD (union)

“Terbukti LOSSLESS”

Uji Dependency Preservation

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

A à B

B à D bisa dibentuk A à D (transitif)

 CD à E

E à A bisa dibentuk CD à A (transitif)

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 U F2 = { A --> B, B --> D, CD --> E }

 A --> B dan B --> D bisa dibentuk A --> D (transitif)

Sehingga (F1 U 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 U R2 = (X, Y, Z, W) U (W, U, V)

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

                 = R

“Terbukti ! {R1,R2} adalah dekomposisi dari R”

Uji Lossless / Lossy

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

                 = (W)

R1 n R2 --> R1

(X, Y, Z, W) n (W, U, V) --> (X, Y, Z, W)

W --> XYZW

(1) W --> X

(2) X --> Z

(3) W --> Z (transitif)

(4) W --> W (refleksif)

(1) W --> X

(3) W --> Z

(4) W --> W

W --> XZW (union)

W --> XZW ¹ W --> XYZW

“Terbukti LOSSY”

Uji Dependency Preservation

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

W -->X

X --> Z bisa dibentuk W --> Z (transitif)

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 U F2 = { W --> X, X --> Z }

 W --> X dan X --> Z bisa dibentuk W --> Z (transitif)

Sehingga (F1 U F2 )⁺    = { W --> X, X --> Z, W --> Z }

                                      = F⁺

“Jadi dekomposisi tersebut memenuhi Dependency Preservatio”.

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 U R2 U R3  = (A, B, C) U (A, D, F) U (E, D)

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

                          = R

“Terbukti ! {R1,R2} adalah dekomposisi dari R”

Uji Lossless / Lossy

R1 n R2 n R3    = (A, B, C) n (A, D, F) n (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 }

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 U F2 = { A --> BC, D --> FA }

Sehingga (F1 U F2 )⁺    = { A --> BC, D --> FA }

                                      = F⁺

“Jadi dekomposisi tersebut memenuhi Dependency Preservation”

TUGAS II

1.    Diberikan R(A,B,C,D) dengan FD : A-->B, A-->C, A-->D

     Apakah A candidate key dari R ?

Jawab :

(4) A --> A (refleksif)

 (1) A-->B

(2) A-->C

(3) A-->D

(4) A --> A

A --> ABCD

“A --> R, jadi A adalah superkey”

“Jika A adalah superkey dan hanya sendiri, maka A juga adalah candidate key”

2.    Diberikan R(A,B,C,D) dengan FD : A-->B

a.    Apakah ACD superkey dari R

b.    Apakah A candidate key dari R

Jawab :

a.     (1) A-->B

(2) ACD --> BCD (augmentasi)

(3) ACD --> ACD (refleksif)

(1) A-->B

(3) ACD --> ACD

ACD --> ABCD (union)

“ACD --> R, ACD adalah superkey”

b.    A --> A (refleksif)

A-->B, dan A-->A   A --> AB (union)

A --> AB ¹ A --> ABCD / A --> R

“A bukan superkey, bukan candidate key”

3.    Diberikan R(A,B,C,D,E,F) dengan FD : C--> (AB), B--> (DE), E-->F, A-->BC

a.    Carilah superkey dari R

b.    Carilah candidate key dari R

Jawab :

a.    Untuk mencari superkey, maka dari FD yang diketahui semua harus dibuktikan

Untuk C--> (AB)

C-->AB

C --> A

C --> B (dekomposisi)

C --> B

B --> DE

C --> DE (transitif)

C --> DE

C --> D

C --> E (dekomposisi)

C --> E, dan E --> F   C --> F (transitif)

C --> C (refleksif)

C --> A

C --> B

C --> DE

C --> F

C --> C

 C --> ABCDEF (union)

“Terbukti. C --> R, C adalah superkey”

Untuk FD (2) : B--> (DE)

B-->DE

B --> D

B --> E (dekomposisi)

B --> E

E --> F

B --> F (transitif)

B --> D

B --> E

B --> F

B --> DEF (union)

“tidak terbukti. B --> DEF ¹ B --> R, maka B bukan superkey”

Untuk FD (3) :

 E --> F

“tidak terbukti. E --> F ¹ E --> R, E bukan superkey”

Untuk FD (4) : A --> BC

 A --> BC

A --> B

A --> C (dekomposisi)

A --> C, diketahui bahwa C adalah superkey C --> R,   A --> R (transitif)

“terbukti. A --> R, maka A adalah superkey”

A & C adalah superkey

b.   “A dan C masing-masing sendirian, maka A & C juga adalah candidate key”

4.    Diberikan R(A,B,C,D,E)  dengan FD : A--> (BC), (CD) -->E, B-->D, E-->A

a.    Carilah superkey dari R

b.    Carilah candidate key dari R

Jawab :

a.    Semua FD dibuktikan :

Untuk A--> (BC)

 A-->BC

A --> B

A --> C (dekomposisi)

A --> B

B --> D

A --> D (transitif)

A --> A (refleksif)

A --> B

A --> C

A --> D

A --> A

jadi A --> ABCD (union)

tidak terbukti. A --> ABCD ¹ A --> R, maka A bukan superkey

Untuk FD (2) : (CD) -->E

CD-->E

E-->A

CD --> A (transitif)

CD --> A

A-->BC

CD --> BC (transitif)

CD --> CD (refleksif)

CD-->E

CD --> A

CD --> BC

CD --> CD

CD --> ABCDE (union)

“terbukti. CD --> R, maka CD adalah superkey”

Untuk B-->D

“tidak terbukti. B-->D ¹ B-->R, maka B bukan superkey”

Untuk E-->A

E-->A

A-->BC

E --> BC (augmentasi)

A-->BC

A --> B

A --> C (dekomposisi)

A --> B

B-->D   A --> D (transitif)

E --> E (refleksif)

E-->A

E --> BC

A --> D

E --> E

E --> ABCDE (union)

“terbukti. E --> R, maka E adalah superkey”

CD dan E adalah superkey

b.    “ada 2 superkey yaitu CD dan E, maka E yang diambil sebagai candidate key”

5.    Diberikan R(A,B,C) dengan FD : A-->B, B-->C, C-->A

Apakah A merupakan satu-satunya candidate key dari R

Untuk FD (1) : A-->B

(1) A-->B

(2) B-->C

(4) A --> C (transitif)

(5) A --> A (refleksif)

(1) A-->B

(4) A --> C

(5) A --> A

A --> ABC (union)

“terbukti. A --> R, maka A superkey”

Untuk B-->C

B-->C

C-->A

B --> A (transitif)

B --> B (refleksif)

B-->C

B --> A

B --> B

B --> ABC (union)

“terbukti. B --> R, maka B superkey”

Untuk C-->A

C-->A

A-->B

C --> B (transitif)

C --> C (refleksif)

C-->A

C --> B

C --> C

C --> ABC (union)

“FD terbukti. C --> ABC = C --> R, maka C superkey”

A, B, dan C adalah superkey. A, B, dan C juga candidate key. A tidak satu-satunya candidate key dari R