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

lời giải bài tập chuẩn hóa CSDL

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\}$