Bài tập về bao đóng cơ sở dữ liệu

Giả sử tập các phụ thuộc hàm F = {Lj → Rj | Lj, Rj ⊆ Ω} thoả trên các quan hệ của lược đồ quan hệ s = <Ω, F>. Cho X ⊆ Ω , tính bao đóng X+ .

Thiết lập chuỗi T1 , T2 , T3 , T4 ,.. , Tk , .. .. sao cho

T1 ⊆, T2 ⊆ T3 ⊆ T4 ⊆ .. ⊆ Tk ⊆. ..

Thuật Toán :

Bước 1:

Chúng ta gán G: = F .

Bước 2:

Sau đó gán T1 = X.

Bước 3:

Kiểm tra phụ thuộc A → B ∈ G .

• Nếu A ⊆ Ti

Nếu B ⊄ Ti khi đó Ti = Ti-1 ∪ B, i = 2,3….., Ngược lại B ⊆ Ti , Ti không thay đổi. G:= G – {A → B}. Lập lại bước 3.

• Thuật toán dừng kiểm tra nếu G = ∅ hoặc không tồn tại A → B ∈ G, sao cho A ⊆ Ti . Nếu B ⊆ Ti , khi đó A → B là phụ thuộc dư thừa.

1: Cho lược đồ quan hệ R(A,B,C,D,E) và tập phụ thuộc hàm F như sau: F={AC, BCD, DE, EA}. a. CM : ABF+ = {ABCDE} b. Từ kết quả câu a), có thể rút ra kết luận gì? 2. Xét lược đồ quan hệ R(A,B,C,D,E) và tập phụ thuộc hàm F={ABC, CDE, DEB }. Tìm một khóa của lược đồ quan hệ R. 3. Cho lược đồ quan hệ R(A,B,C,D) và tập phụ thuộc hàm F như sau: F={BACD, CA, DB}; biết rằng R có 2 khóa là B và D. Hãy xác định dạng chuẩn cao nhất của lược đồ quan hệ R. 4 một lược đồ quan hệ W=<Q,F> , Q là tập các thuộc tính với Q={A,B,C,D,E,G} và tập F các phụ thuộc hàm với F={A→BCEG ; C→AD; G→A} Câu hỏi : Hãy tìm một khóa của lược đồ quan hệ W. 5 một lược đồ quan hệ W=<R,F> , R là tập các thuộc tính với R={A,B,C,D} và tập F các phụ thuộc hàm với F={AB, BC, DC, AD} Câu hỏi : Hãy tìm một khóa của lược đồ quan hệ W. 6. Cho quan hệ R (A B C D E ), với tập phụ thuộc hàm F như sau: F = { AB->C, AC->B, BC->DE} a/ Tìm 1 khóa của R b/ Tìm tất cả các khóa của R 7 quan hệ R (A B C D E H), với tập phụ thuộc hàm F như sau: F = { AB ->C , CD ->E , EC ->A , CD ->H , H ->B } Tìm 1 khóa của R

1. Kiểm tra 1 PTH X  Y có được suy diễn từ tập phụ thuộc hàm cho trước Cách làm: - Tính tập bao đóng X+ trên tập PTH - Nếu Y Ì X+ thì X Y được suy diễn từ tập PTH Ví dụ: Cho

CM: B G Î F+

8 một lược đồ quan hệ W=<Q,F> , Q là tập các thuộc tính với Q={A,B,C,D,E,G,H,K} và tập phụ thuộc hàm F như sau F = {C → AD; E→ BH; B→ K; CE→ G} Kiểm tra xem các phụ thuộc hàm E→ K; E→G có được suy từ F hay không? 9 một lược đồ quan hệ W=<Q,F> , Q là tập các thuộc tính với Q={A,B,C,D,E,G}và tập F các phụ thuộc hàm với F={AG→E; A→B; C→A; C→D; AG→C } Xác định phụ thuộc hàm CG→BE Î F+? 10. Cho F = {AB→C,B→D,CD→E,CE→GH,G→A} Hãy chứng tỏ phụ thuộc hàm AB→E, AB→G được suy diễn từ F nhờ luật dẫn Armstrong

Cho lược đồ quan hệ Q ( A B C D E G) vôùi: F = { AE-> C, CG -> A , BD -> G, GA->E} CM: BDC+F = {BDCGAE}

Kiểm tra lần lượt từng phụ thuộc hàm fi = a®b, nếu a Í X+ thì kết nạp vế phải (tức b) vào vào X+: X+ := X+ Èb.

Lặp lại cho đến khi nào X+ = Const.

Thuật toán 1

CònThayĐổi := True;X+ := X;

While Còn_Thay_Đổi Do

Begin

Còn_Thay_Đổi := False;

For mỗi fi = a®b Do

Begin

If a Í X+ Then

Begin

X+ := X+ È b;

Còn_Thay_Đổi := True;

End;

End;

End;

*** Lưu ý: Việc cài đặt chi tiết thuật toán xin xem trong phụ lục

Bài tập áp dụng:

Bài tập 1:

Cho lược đồ quan hệ R = (U, F)

U= {A,B,C,D,E,G,H}

F= {ABàC, DàEG, ACDàB, CàA, BEàC, CEàAG, BCàD, CGàBD, Gà H}

1. Tính (D)+

2. Tính (DE)+

3. Tính (BE)+

4. Tính (CG)+

Giải:

1. Tính (D)+

X0 = D

1. X1 = DEG (áp dụng D®EG)

2. X2 = DEGH (áp dụng G®H) (= Constant)

Vậy (D)+ = DEGH

2. Tính (DE) +

X0 = DE

1. X1 = DEG (áp dụng D®EG)

2. X2 = DEGH (áp dụng G®H) (= Constant)

Vậy (DE)+ = DEGH

3. Tính (BE)+

X0 = BE

1. X1 = BEC (áp dụng BE®C)

2. X2 = BECAG (áp dụng CE®AG)

3. X3 = BECAGD (áp dụng BC®D)

4. X4 = BECAGDH (áp dụng G®H) (= Constant)

Vậy (BE)+ = ABCDEGH

4. Tính (CG)+

X0 = CG

1. X1 = CGA (áp dụng C®A)

2. X2 = CGABD (áp dụng CG®BD)

3. X3 = CGABDH (áp dụng G®H)

4. X4 = CGABDHE (áp dụng D®EG) (= Constant)

Vậy (CG)+ = ABCDEGH

Bài tập 2: Cho lược đồ quan hệ R = (U, F)

U = {A,B,C,D,E,G}

F = {CàG, BG à CD, AEG à BC, CG à AE, B à CG }

1. Tính C+

2. Tính (B)+

3. Tính (AEG)+

Giải:

1. Tính C +

X0 = C

1. X1 = CG (áp dụng C®G)

2. X2 = CGAE (áp dụng CG®AE)

3. X3 = CGAEB (áp dụng AEG®BC)

4. X4 = CGAEBD (áp dụng BG®CD) (= Constant)

Vậy (C)+ = ABCDEG

2. Tính (B)+

X0 = B

1. X1 = BCG (áp dụng B®CG)

2. X2 = BCGD (áp dụng BG®CD)

3. X3 = BCGDAE (áp dụng CG®AE) (= Constant)

Vậy (B)+ = ABCDEG

3. Tính (AEG)+

X0 = AEG

1. X1 = AEGBC (áp dụng AEG®BC)

2. X2 = AEGBCD (áp dụng BG®CD) (= Constant)

Vậy (AEG)+ = ABCDEG

** Chú ý: Tương tự như bao đóng của tập thuộc tính, người ta cũng định nghĩa bao đóng của tập phụ thuộc hàm. Tuy nhiên việc tính bao đóng của tập phụ thuộc hàm nói chung là phức tạp, nó thuộc loại bài toán NP – Khó. Hơn nữa việc tính bao đóng của tập phụ thuộc hàm ít được ứng dụng do vậy xin không đề cập trong tài liệu này.

Một ví dụ về tính bao đóng của tập phụ thuộc hàm.

Tính (BG à CD)+ với R cho ở bài tập 2.

X0 = BG à CD

X1 = (BGàC, BG à D) (Theo luật tách trong hệ tiên đề Amstrong)

X2 = (BG à C, BG à D, BG à B, BG à G) (Theo luật phản xạ)

X3 = (BG à B, BG à G, BG à C, BG à D, BG à CG) (Luật hợp)

X4 = (BG à B, BG à G, BG à C, BG à D, BG à CG, CG à AE) …..

CHƯƠNG II

TÌM PHỦ TỐI THIỂU CỦA TẬP PHỤ THUỘC HÀM

Với mỗi tập phụ thuộc hàm F đã cho, rất có thể có nhiều phụ thuộc hàm là dư thừa, tức là ta có thể suy dẫn ra các phụ thuộc hàm này thông qua tập phụ thuộc hàm còn lại trong F. Vấn đề đặt ra là phải làm sao thu gọn số phụ thuộc hàm F thành tối thiểu (gọi là G) để sao cho G vẫn tương đương với F.

Ví dụ về phụ thuộc hàm dư thừa:

F = {A à B, B à C, A à C. ở đây phụ thuộc hàm A à C là dư thừa bởi vì ta có thể dễ dàng có được phụ thuộc hàm này thông qua A à B, B à C

Như vậy tập phụ thuộc hàm tương đương với F là G = { A à B, B à C }

Định nghĩa phụ thuộc hàm dư thừa:

Cho lược đồ R = {U, F}, một phụ thuộc hàm trong F có dạng a®b được gọi là dư thừa nếu như bao đóng của a trong tập phụ thuộc hàm F – { a®b } có chứa b. Tức là : (a)+(F – {a®b}) É b.

Định nghĩa phủ tương đương:

Một tập phụ thuộc hàm G được gọi là tương đương với tập phụ thuộc hàm F của lược đồ R nếu như : F+ = G+. Khi đó ta nói F phủ G hay G phủ F.

Định nghĩa phủ tối thiểu:

Một phủ tối thiểu của tập phụ thuộc hàm F là một tập phụ thuộc hàm G, Trong đó:

+ G tương đương với F (tức là G+ = F+)

+ Tất cả các phụ thuộc hàm trong G đều có dạng X à A Trong đó A là một thuộc tính.

+ Không thể làm cho G nhỏ hơn được nữa. (Tức là không thể xoá thêm bất kỳ phụ thuộc hàm nào trong G hay xoá đi bất kỳ một thuộc tính nào bên phía phải, phía trái của mỗi phụ thuộc hàm mà G vẫn tương đương với F).

Lưu ý : Các phụ thuộc hàm hay các thuộc tính xoá được theo cách trên mà vẫn đảm bảo G tương đương với F thì ta gọi đó là phụ thuộc hàm hay thuộc tính dư thừa.

Phương pháp tìm phủ tối thiểu:

Bước 1: Tách mỗi phụ thuộc hàm trong F có dạng X à A1A2A3…An thành các phụ thuộc hàm mà vế phải (RH – Right Hand) chỉ có một thuộc tính:

X à A1

X à A2

………

X à An

Bước 2: Loại bỏ các thuộc tính dư thừa bên phía trái của mỗi phụ thuộc hàm.

Bước 3: Duyệt từng phụ thuộc hàm và kiểm tra xem có dư thừa không, nếu dư thừa thì thì xoá đi.

Lưu ý: Trình tự bước 2 và 3 là KHÔNG THỂ thay đổi !!!

Ở đây ta cần giải thích rõ thế nào thuộc tính dư thừa, phụ thuộc hàm dư thừa ?

Định nghĩa 1: Một phụ thuộc hàm có dạng aAàb, với A là một thuộc tính đơn lẻ. Ta nói A là thuộc tính dư thừa nếu có thể suy dẫn ra b từ a, Tức là a+Êb.

Ví dụ: Cho F = {AC à B, C à B, ABDE à GH, A à E, A à D}

+ Xét phụ thuộc hàm ACà B:

Rõ ràng thuộc tính A trong AC à B là dư thừa vì C+ = (CB) É B.

+ Xét phụ thuộc hàm ABDE à GH

– Thuộc tính A : Không dư thừa vì (BDE)+ = BDE không chứa GH

– Thuộc tính B : Không dư thừa vì (ADE)+ = ADE không chứa GH

– Thuộc tính D: Dư thừa vì (ABE)+ = ABDE có chứa ABDE

( Loại thuộc tính D khỏi phụ thuộc hàm ABDE à GH ta được ABE à GH

+ Xét phụ thuộc hàm ABE à GH

– Thuộc tính E: Dư thừa vì (AB)+ = ABDE É ABE

+ Các thuộc tính trong các phụ thuộc hàm còn lại đều không dư thừa.

Cuối cùng ta được tập phụ thuộc hàm không có thuộc tính dư thừa gồm:

F = {C à B, AB à GH, A à E, A à D}

Định nghĩa phụ thuộc hàm dư thừa: Một phụ thuộc hàm có dạng a®b, được gọi là dư thừa nếu như xoá bỏ nó khỏi tập F thì ta vẫn có : (a)+ Ê b (tức là vẫn suy dẫn ra b từ a, mặc dù đã xoá bỏ phụ thuộc hàm a®b khỏi F).

Ví dụ: Cho F = {A à B, B à C, A à C, B à DE, A à E, A à D}

+ Kiểm tra xem A à B có dư thừa hay không bằng cách : Thử loại phụ thuộc hàm này khỏi F sau đó tính A+, Nếu A+ Ê B thì nó là dư thừa, trái lại là không dư thừa.

Sau khi loại A à B ta có F = {B à C, A à C, BàDE, A à E, A à D}

Rõ ràng A+ = {AED} nên B Ï A+, chứng tỏ A à B là không dư thừa.

Vậy phụ thuộc hàm này không thể loại khỏi F.

F vẫn là: {A à B, B à C, A à C, B à DE, A à E, A à D}

+ Kiểm tra Bà C có dư thừa ?

– Loại BàC khỏi F, ta có F = {AàB, AàC, BàDE, AàE, AàD}

– B+ = {BDE} không chứa C, chứng tỏ BàC là không dư thừa.

F vẫn là: {AàB, BàC, AàC, BàDE, AàE, AàD}

+ Kiểm tra AàC có dư thừa ?

– Loại AàC khỏi F ta được F = {AàB, BàC, BàDE, AàE, AàD}

– A+ = {ABCDE} có chứa C, chứng tỏ AàC là dư thừa

è F bây giờ là: F = {AàB, BàC, BàDE, AàE, AàD}

+ Kiểm tra BàDE có dư thừa ?

– Loại BàDE khỏi F, ta được F = {AàB, BàC, AàE, AàD}

– B+ = {BC} không chứa DE, chứng tỏ BàDE không dư thừa

è F vẫn là {AàB, BàC, BàDE, AàE, AàD}

+ Kiểm tra AàE có dư thừa ?

– Loại AàE khỏi F, ta được F = {A à B, BàC, BàDE, AàD}

– A+ = {ABCDE} chứa E, chứng tỏ phụ thuộc hàm này dư thừa

è F bây giờ là: {AàB, BàC, BàDE, AàD}

+ Kiểm tra AàD có dư thừa ?

– Loại AàD khỏi F, ta được F = {AàB, BàC, BàDE}

– A+ = {ABCDE} chứa D, chứng tỏ phụ thuộc hàm AàD là dư thừa.

è F bây giờ là {AàB, BàC, BàDE}.

Duyệt lại các phụ thuộc hàm ta thấy không có phụ thuộc hàm nào bị loại thêm nữa (Tức là F = Const). Do vậy tập phụ thuộc hàm cuối cùng sau khi loại các phụ thuộc dư thừa là:

F = {Aà B, B à C, B à DE}

Với phương pháp loại bỏ thuộc tính và phụ thuộc hàm dư thừa đã đề cập ở trên, sau đây ta lấy ví dụ thực hiện việc tìm phủ tối thiểu của tập phụ thuộc hàm F.

Bài tập áp dụng

Ví dụ 2: Tìm phủ tối thiểu của tập phụ thuộc hàm T sau đây :

T = {ABH à CK, A à D, C à E, BGH à F, F à AD, E à F, BH à E}

• Bước 1: Chuyển vế phải của mỗi phụ thuộc hàm thành các thuộc tính đơn lẻ, ta được:

– ABH à C

– ABH à K

– A à D

– BGH à F

– F à A

– F à D

– E à F

– BH à E

• Bước 2: Loại bỏ các thuộc tính dư thừa bên phía trái của mỗi phụ thuộc hàm (Sử dụng phương pháp loại giống như ví dụ 1).

+ Xét phụ thuộc hàm ABHàC

– A dư thừa vì (BH)+ = {BHEFDAKC} có chứa C.

– B Không dư thừa vì (AH)+ = {AHD} không chứa C

– H không dư thừa vì (AB)+ = {ABD} không chứa C

è Kết quả sau lần thứ nhất:

T = {BH à C, ABH à K, A à D, BGH à F, F à A, F à D, E à F, BH à E}

+ Tương tự: A dư thừa trong ABHàK vì (BH)+ = {BHCEFDAK} chứa K và G dư thừa trong BGHàF vì (BH)+ = {BHEFDAKC} có chứa F.

è Kết quả cuối cùng:

T = {BH à C, BH à K, A à D, BH à F, F à A, F à D, E à F, BH à E}

Đển đây ta không thể loại thêm được thuộc tính nào nữa.

• Bước 3: Loại bỏ các phụ thuộc hàm dư thừa

Hiện tại T = {BHàC, BHàK, AàD, BHàF, FàA, FàD, EàF, BHàE}

+ Thử loại BH à C, Ta có (BH)+ = {BHFADEK} không chứa C => không dư thừa.

+ Thử loại BHàK, Ta có (BH)+ = {BHCFADE} không chứa K => không dư thừa.

+ Thử loại Aà D, Ta có (A)+ = {A} không chứa D => không dư thừa.

+ Thử loại BHà F, Ta có (BH)+ = {BHCKEFAD} có chứa F => luật này dư thừa, loại ra khỏi T, ta được: T = {BHàC, BHàK, AàD, FàA, FàD, EàF, BHàE}

+ Thử loại Fà A, Ta có F+ = {FD} không chứa A => không dư thừa

+ Thử loại Fà D, ta có F+ = {FAD} có chứa D nên luật này dư thừa. Loại khỏi T ta được : T = {BHàC, BHàK, AàD, FàA, EàF, BHàE}

+ Thử loại EàF, ta có E+ = {E} không chứa F => Không dư thừa.

+ Thử loại BHàE, ta có (BH)+ = {BHCK} không chứa E nên không dư thừa.

Đến đây ta đã thử xong tất cả các phụ thuộc hàm trong lược đồ. Kết quả cuối cùng ta có phủ tối thiểu T = {BHàC, BHà K, AàD, FàA, EàF, BHàE}.

Ví dụ 2: Tìm phủ tối thiểu của lược đồ cho dưới đây:

R = <U, F>, Với:

U = {ABCDEGH}

F = {Aà BC, BE à G, E à D, D à G, A à B, AG à BC}

Bước 1 Tách vế phải thành 1 thuộc tính:

AàB AàC BE®G E®D D®G A®B AG®B AG®C

Bước 2 Xoá thuộc tính dư thừa

B dư thừa trong BE®G. Vì (E)+ = {DEG} chứa G

G dư thừa trong AG®B. Vì (A)+ = {ABC} chứa B

G dư thừa trong AG®C. Vì (A)+ = {ABC} chứa C

Bước 3 Xoá phụ thuộc hàm dư thừa:

A®B dư thừa. Vì nếu xoá khỏi F, ta vẫn có (A)+ = {ABC} Chứa B

A®C dư thừa. Vì nếu xoá khỏi F, ta vẫn có (A)+ = {ABC} Chứa C

A®B dư thừa. Vì nếu xoá khỏi F, ta vẫn có (A)+ = {ABC} Chứa B

E®G dư thừa. Vì nếu xoá khỏi F, ta vẫn có (E)+ = {DEG} Chứa G

Phủ tối thiểu của F là :

1. A®B

2. A®C

3. D®G

4. E®D

Ví dụ 3: Tìm phủ tối thiểu của lược đồ cho dưới đây:

R = <U, F>

U = (ABCDEGHIJ)

F = {A à BDE, DE à G, H à J, J à HI, E à DG, BCà GH, HGàJ, EàG}

Bước 1 Tách vế phi thành 1 thuộc tính:

A®B A®D A®E DE®G H®J J®H J®I E®D E®G BC®G BC®H HG®J E®G

Bước 2 Xoá thuộc tính dư thừa

D dư thừa trong DE®G. Vì (E)+ = {DEG} chứa G

G dư thừa trong HG®J. Vì (H)+ = {HIJ} chứa J

Bước 3 Xoá phụ thuộc hàm dư thừa:

A®D dư thừa. Vì nếu xoá khỏi F, ta vẫn có (A)+ = {ABDEG} Chứa D

E®G dư thừa. Vì nếu xoá khỏi F, ta vẫn có (E)+ = {DEG} Chứa G

H®J dư thừa. Vì nếu xoá khỏi F, ta vẫn có (H)+ = {HIJ} Chứa J

E®G dư thừa. Vì nếu xoá khỏi F, ta vẫn có (E)+ = {DEG} Chứa G

Phủ tối thiểu của F là :

A®B BC®H A®E BC®G H®J J®H J®I E®D E®G

CHƯƠNG III

TÌM KHOÁ TỐI THIỂU CỦA LƯỢC ĐỒ QUAN HỆ

1. Định nghĩa khoá tối thiểu:

Cho lược đồ R = <U,F>, trong đó U là tập thuộc tính, F là tập phụ thuộc hàm. K được gọi là khoá tối thiểu của R nếu như số thuộc tính trong K là ít nhất nhưng vẫn thoả mãn K+ =U .

2. Phát biểu bài toán tìm khoá tối thiểu:

Cho lược đồ quan hệ R = <U, F>

Hãy tìm một khoá (tối thiểu) của quan hệ R.

3. Thuật toán tìm khoá tối thiểu (Lưu ý, từ nay nếu không có sự nhầm lẫn thì ta gọi tắt khoá tối thiểu là Khoá).