Bao đóng và bài toán thành viên

Cho lược đồ quan hệ trên tập thuộc tính U và tập phụ thuộc hàm F, cùng phụ thuộc hàm f = X ® Y Ï F. Bài toán thành viên  giúp xác định  các quan hệ r của lược đồ có thoả f hay không?

   Để giải quyết bài toán trên ta có hai phương án:

Phương án 1: Sử dụng định nghĩa phụ thuộc hàm, khi đó ta phải kiểm tra tất cả các quan hệ có thể có trên lược đồ quan hệ, nhưng số lượng các quan hệ là vô cùng lớn (có thể vô hạn) vì vậy không thể kiểm tra được

Phương án 2: Sử dụng hệ tiên đề AMSTRONG để biến đổi F, nếu sau một số hữu hạn bước biến đổi ta nhận được f thì kết luận các quan hệ r trên lược đồ thoả mãn f. Tuy nhiên với phương án này trong trường hợp các quan hệ trên lược đồ  không thoả mãn f thì không thể chứng minh được.

Như vậy cả hai phương án trên đều chưa đủ giải quyết bài toán đặt ra.

Khái niệm bao đóng sẽ giúp ta giải quyết triệt để bài toán.

5.2.1. Bao đóng

a. Bao đóng của tập phụ thuộc hàm

Cho R(U), U là tập thuộc tính và F là tập các phụ thuộc hàm trên tập thuộc tính U, tập tất cả các phụ thuộc hàm được suy dẫn ra từ tập F được gọi là bao đóng của tập phụ thuộc hàm và kí hiệu là F+, F+ được viết là:

 

Nếu F+ = F thì F được gọi là họ đầy đủ của các phụ thuộc hàm.

     Ý nghĩa của bao đóng tập phụ thuộc hàm: Bao đóng của tập phụ thuộc hàm F là tập tất cả các phụ thuộc hàm có thể nhận được sau khi áp dụng các luật phản xạ, bắc cầu và gia tăng đối với các phụ thuộc hàm trong F.

Để giải quyết bài toán thành viên ta chỉ cần xác định phụ thuộc hàm f_i : X->Y có thuộc  F⁺  hay không?

b. Bao đóng của tập thuộc tính X

Tập tất cả các thuộc tính có thể suy diễn ra từ X nhờ hệ tiên đề Amstrong gọi là bao đóng của tập thuộc tính X, kí hiệu là X+.

Định nghĩa: Cho một lược đồ quan hệ trên tập thuộc tính U, tập phụ thuộc hàm F và một tập thuộc tính XÍU. Bao đóng của 1 tập thuộc tính X (ký hiệu X⁺) là tập tất cả các thuộc tính A thuộc U sao cho phụ thuộc hàm X->AÎ F⁺ .

X⁺_F = { A | AÎ U , X ® A Î F⁺ }

Các tính chất :

1. (Phản xạ) X Í X⁺
2. (Đơn điệu ) Nếu X Í Y Þ X⁺ Í Y⁺
3. (Luỹ đẳng) X⁺⁺ = X⁺
4. X⁺ Y⁺ Í (XY)⁺
5. (X⁺ Y)⁺ = (XY⁺)⁺ = (XY)⁺

6 . X ® Y Î F⁺ & Y ® X Î F⁺  Û X⁺ = Y⁺

7. X ® Y Î F⁺ Û Y Í X⁺

Ý nghĩa của tính chất 7: Để giải quyết bài toán thành viên ta chỉ cần xác định phụ thuộc hàm f_i : X->Y có thuộc  F⁺  hay không và tương đương với việc xác định Y Í X⁺  hay không?

Để giải quyết yêu cầu này ta phải xác định được X⁺ (bao đóng của tập thuộc tính X).

c.      Thuật toán xác định bao đóng của tập thuộc tính X (Closure(X,F)):

Input: Tập thuộc tính X và tập phụ thuộc hàm F

Output: Bao đóng của X+?

Thực hiện: lần lượt tính các X⁰, X¹,… theo các bước:

• Bước 1: Đặt X⁰ = X
• Bước 2: Lần lượt xét các phụ thuộc hàm của F nếu tồn tại pth Y ®ZÎF mà YÌXⁱ thì Xⁱ⁺¹ = Xⁱ È {Z}, ngược lại, đặt Xⁱ⁺¹ = Xⁱ
• Bước 3: Nếu ở bước 2 mà không tính được Xⁱ⁺¹ thì Xⁱ chính là bao đóng của tập thuộc tính X, ngược lại lặp lại bước 2.

 

Giả mã của thuật toán CLOSURE(X,F)

Begin

            X⁺  = X;

Do

Old X⁺ = X⁺ ;

với mỗi phụ thuộc hàm Y → Z trong F thực hiện

nếu X⁺⊃ Y thì  X⁺= X⁺∪ Z;

While ( X⁺ = Old X⁺ );

End

Ví dụ 1: Xét lược đồ quan hệ

R = {MãsốNV, HọtênNV, MãsốDA, TênDA, ĐịađiểmDA, Sốgiờ}

và tập phụ thuộc hàm

F = {MãsốNV → HọtênNV,

MãsốDA → TênDA, ĐịađiểmDA,

MãsốNV, MãsốDA → Số giờ}

Tính bao đóng {MãsốNV}⁺, {MãsốNV, MãsốDA}⁺

Giải: Áp dụng thuật toán ta có:

{MãsốNV}⁺ = { MãsốNV}

Xét F1: MãsốNV → HọtênNV nên có {MãsốNV}⁺ = {MãsốNV}⁺∪ HọtênNV

Và kết luận: {MãsốNV}⁺ = {MãsốNV, HọtênNV}

• {MãsốNV, MãsốDA}⁺= {MãsốNV, MãsốDA}
• Xét F1: MãsốNV → HọtênNV nên có

{MãsốNV, MãsốDA}⁺= {MãsốNV, MãsốDA}∪ HọtênNV= {MãsốNV, MãsốDA, HọtênNV}

• Xét F2: MãsốDA → TênDA, ĐịađiểmDA nên có

{MãsốNV, MãsốDA}⁺={MãsốNV, MãsốDA HọtênNV}∪ {TênDA, ĐịađiểmDA}

={MãsốNV, MãsốDA, HọtênNV, TênDA, ĐịađiểmDA}

• Xét F3: MãsốNV, MãsốDA → Số giờ nên có:

{MãsốNV, MãsốDA}⁺={MãsốNV, MãsốDA, HọtênNV, TênDA, ĐịađiểmDA} ∪ Số giờ

={MãsốNV, MãsốDA, HọtênNV, TênDA, ĐịađiểmDA, Số giờ}

Kết luận:

{MãsốNV, MãsốDA}⁺={MãsốNV, MãsốDA, HọtênNV, TênDA, ĐịađiểmDA, Số giờ}

Ví dụ 2: Xét lược đồ quan hệ

Cho R = (A, B, C, D, E, G) và tập phụ thuộc hàm

F = {AB ®C, C ®A, BC ®D, ACD ®B, D ®EG, BE ®C,   CG ®BD, CE ®AG}. Tính: (BD)⁺

Giải:

X⁰ = BD

• Xét phụ thuộc hàm D ® EG => thêm E và G vào X⁰ ó X¹ = X⁰ ∪ EG= BDEG
• Phụ thuộc hàm BE ® C => thêm C vào X¹ ó X² = X¹ ∪ C =BCDEG
• Phụ thuộc hàm CE ® AG => thêm A vào X² ó X³ = X² ∪ A = ABCDEG

Áp dụng tất cả các phụ thuộc hàm không làm thay đổi X⁺, nên (BD)⁺ = ABCDEG

 

 

---

 Bài toán thành viên

Định nghĩa: Một phụ thuộc hàm X®Y là thành viên của F nếu X®YÎ F+

Về nguyên tắc ta sẽ tìm bao đóng F+ sau đó kiểm tra xem phụ thuộc hàm X®Y có thuộc F+ hay không nhưng việc tìm F+ là một việc tốn nhiều thời gian và công sức vì thế thay vì tìm F+ chúng ta có thể dùng thuật toán sau để kiểm tra phụ thuộc hàm X®Y có là thành viên của F hay không.

Input: phụ thuộc hàm cần kiểm tra X®Y và tập phụ thuộc hàm F

Output: X®Y là thành viên của F đúng hay sai

Các bước thực hiện:

• Bước 1: Tính X⁺
• Bước 2: So sánh X⁺ với Y nếu Y ÍX⁺ thì khẳng định X ® Y là thành viên của tập phụ thuộc hàm F, ngược lại không là thành viên của F.

Ví dụ 1:

Cho R(ABCDE) và tập phụ thuộc hàm F= { A ® CD; C ® E; D ® BC }

Xác định xem A ® B có là thành viên của F.

Giải:

• Tính A+={ACDEBC}
• Nhận thấy B Í A+ nên khẳng định phụ thuộc hàm A ® B là thành viên của F.

 

Ví dụ 2:

Cho R(ABEGHI) và tập phụ thuộc hàm F= { AB ® E; AG ® I; BE ® I; E ® G; BE ® I; GI ® H; }

Xác định xem AB ® GH có là thành viên của F.

Giải:

• Tính AB+={ABEIGH}
• Nhận thấy GH Í AB+ nên khẳng định phụ thuộc hàm AB ® GH là thành viên của F.