
Dạng bài tập tính bao đóng của một tập thuộc tính X dựa trên một tập phụ thuộc hàm F (closure of X under F).
Đề bài
Cho một lược đồ CDDL quan hệ với các thuộc tính $A, B, C, D, E, I$. Giả sử lược đồ có các phụ thuộc hàm sau:
- $A \to D$
- $AB \to E$
- $BI \to E$
- $CD \to I$
- $E \to C$
Tính bao đóng của tập thuộc tính $\{A, E\}$
Giải thuật
Có nhiều phương án để giải bài toán này, tuy nhiên mình sử dụng giải thuật sau để giải:
Input:
- Tập thuộc tính $X$
- Tập phụ thuộc hàm $F$
Output: Bao đóng của $X$ dựa trên $F$

Để hiểu rõ hơn về giải thuật, chúng ta sẽ thực hiện 1 ví dụ đơn giản sau: Cho lược đồ quan hệ $R(A, B, C, D, E, F)$ và tập phụ thuộc hàm $F = \{f_1: D \to B, f_2: A \to C, f_3: AD \to E, f_4: C \to F\}$. Nhìn vào giải thuật chúng sẽ thấy rất khó hiểu và phức tạp, nhưng một cách đơn giản hơn, các bạn có thể hình dung các bước làm như sau:
- Duyệt qua tất cả các phụ thuộc hàm.
- Nếu vế trái đang nằm trong bao đóng, thì thêm vế phải vào bao đóng.
- Nếu không còn có thể thêm vào nữa thì dừng.
Tìm $A^+_F$: Sau đây là các bước thực hiện:
- Chúng ta duyệt lần thứ nhất, từ $f_2$ chúng ta có $A^+_F = \{AC\}$. Do A nằm sẵn trong bao đóng, và $f_2 = A \to C$ mà $C$ chưa thuộc bao đóng, nên ta thêm $C$ vào.
- Tương tự, dựa vào $f_4$ ta tiếp tục thêm F vào bao đóng, lúc này $A^+_F = \{ACF\}$
- Tiếp tục duyệt và thử các phụ thuộc hàm, chúng ta thấy tập $A^+_F$ không thể thay đổi nữa. Dừng và kết luận $A^+_F = \{ACF\}$
Gợi ý giải
Sau đây là các bước lặp và các phụ thuộc hàm tương ứng:
- $\{AE\}$
- $\{ADE\}$ ($A \to D$)
- $\{ACDE\}$ ($E \to C$)
- $\{ACDEI\}$ ($CD \to I$)
Vậy $\{A, E\}^+_F = \{ACDEI\}$
Các bài tập làm thêm
Bài tập 1
Với đề bài trong mục giải thuật, tính $\{AD\}^+_F$.
Bài tập 2
Cho lược đồ CSDL quan hệ với các thuộc tính $A, B, C, D, E, F$. Giả sử lược độ có các phụ thuộc hàm sau:
- $AB \to C$
- $BC \to AD$
- $D \to E$
- $CF \to B$
Tính bao đóng của tập thuộc tính $\{A, B\}$
Bài tập 3
Cho lược đồ CSDL quan hệ với các thuộc tính $A, B, C, G, H, I$. Giả sử lược đồ có các phụ thuộc hàm sau:
- $A \ to B$
- $A \to C$
- $CG \to H$
- $CG \to I$
- $B \to H$
Tính bao đóng của tập thuộc tính $\{A, G\}$
Đáp án các bài tập
- $\{AD\}^+_F = \{ABCDEF\}$
- $\{AB\}^+_F = \{ABCDE\}$
- $\{AG\}^+_F = \{ABCGHI\}$