Gợi ý giải bài 1 – chuẩn hóa dữ liệu

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:

1. $\{AE\}$
2. $\{ADE\}$ ($A \to D$)
3. $\{ACDE\}$ ($E \to C$)
4. $\{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

1. $\{AD\}^+_F = \{ABCDEF\}$
2. $\{AB\}^+_F = \{ABCDE\}$
3. $\{AG\}^+_F = \{ABCGHI\}$