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

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

Bài 2 là dạng bài tập tìm kiếm tất cả các khóa của một lược đồ quan hệ. Bài toán cho lược đồ quan hệ, các thuộc tính và các phụ thuộc hàm sau đó yêu cầu chúng ta tìm kiếm tất cả các khóa.

Đề bài

Cho lược đồ quan hệ $R(A, B, C, D, E, F, G, H)$ và các phụ thuộc hàm $F = \{D \to A, E \to BAH, A \to FC, B \to FC, H \to E, F \to G\}$. Hãy tìm tất cả các khóa của R.

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 $U$ của lược đồ quan hệ $R$
  • Tập phụ thuộc hàm $F$

Output: Tập $K$ bao gồm tất cả các khóa của $R$

Để hiểu rõ hơn về giải thuật, chúng ta sẽ thực hiện 1 ví dụ đơn giản trước khi giải bài tập nha. Xét ví dụ: Cho lược đồ quan hệ $R(A, B, C, D, E, F,)$ và tập phụ thuộc hàm $F = \{ D \to B, A \to C, AD \to E, C \to F\}$. Tìm tất cả các khóa của $R$ chúng ta thực hiện như sau:

Bước 1: Tính $N = U – \cup_{\forall f \in F^{\text{right}(f)}}$ – Nhìn giải thuật và công thức các bạn thấy rất phức tạp đúng không, nhưng thực sự mọi thứ rất dễ. Chúng ta phân tích sơ qua như sau:

$N$ sẽ được tính bằng hiệu của $U$ (tất cả các thuộc tính) trừ (-) đi tất cả các thuộc tính nằm ở vế phải phải (phụ thuộc hàm). Các bạn lưu ý, đây là phép toán trên tập hợp nha.

Vậy ta có $N = \{ABCDEF\} – \{BCEF\} = {AD}$

Bước 2: Tính $N^+_F = {ABCDEF} = U$. Suy ra, lược đồ $R$ có một khóa là $\{AD\}$

Gợi ý giải

Bước 1: Tính $N = \{ABCDEFGH\} – \{ABCEFGH\} = \{D\}$

Bước 2: Tính $N^+_F = \{D\}^+_F = \{ACDFG\} \ neq U$

Bước 3: Thực hiện tính các giá trị:

  • Tính $D$ bằng cách lấy các thuộc tính vế phải, trừ đi các thuộc tính ở về trái: $D = \{ABCEFGH\} – \{ABDEFH\} = \{CG\}$
  • Tính $L$ bằng cách lấy $U$ (tất cả các thuộc tính) trừ đi $N^+_F$ (đã tính được ở bước 2): $L = \{ABCDEFGH\} – \{ACDFG\} = \{BEH\}$
  • Liệt kê tất cả các tập con của $L$: $\{B\}, \{E\}, \{H\}, \{BE\}, \{BH\}, \{EH\}, \{BEH\}$

Bước 4: Hợp (hội – union) lần lượt các tập con của $L$ vừa tìm được ở bước 3 với $N$ (ở bước 1). Sau đó tìm bao đóng của từng tập thuộc tính mới tìm được. Ta có:

  • $\{BD\}^+_F = \{ABCDFG\} \neq U$. Ta lấy tập con đầu tiên của $L$ là $\{B\} \cup \{D\} = \{BD\}$ (Do $N = \{D\}$ đã tính được ở bước 1).
  • $\{DE\}^+_F = \{ABCDEFGH\} = U$. Vậy $\{DE\}$ là một khóa của quan hệ $R$. Loại bỏ các tập cha của $\{E\}$ là $\{BE\}, \{EH\}, \{BEH\}$
  • $\{DH\}^+_F = \{ABCDEFGH\} = U$. Vậy $\{DH\}$ là một khóa của quan hệ $R$. Loại bỏ các tập cha của $\{H\}$ là $\{BH\}$

Vậy là sau khi duyệt được 3 tập con (của $L$) và loại bỏ được 4 tập con khác, thì tập con $L$ đã trống. Chúng ta có thể đưa ra kết luận là quan hệ $R$ có 2 khóa là $\{DE\}$ và $\{DH\}$.

Các bài tập làm thêm

Bài tập 1

Cho lược đồ quan hệ $R(A, B, C, D, E, F, G, H)$ và các phụ thuộc hàm:

  • $B \to E$
  • $D \to AEF$
  • $E \to CG$
  • $A \to CG$
  • $F \to D$
  • $C \to H$

Tìm tất cả các khóa của $R$.

Đáp án các bài tập

  1. $R$ có 2 khóa là $\{BD\}, \{BF\}$