Chuẩn hóa dữ liệu – phụ thuộc hàm

Phụ thuộc hàm

Phụ thuộc hàm (functional dependency) mô tả mối liên hệ giữa các thuộc tính và là một trong các khái niệm chính được sử dụng trong quá trình chuẩn hóa. Dựa vào các phục thuộc hàm này, mà chúng ta có thể thiết kế lại các lược đồ CSDL để loại bỏ phần nào sự dư thừa dữ liệu tồn tại trong CSDL.

Một số khái niệm

Cho một lược đồ quan hệ $R(U), r$ là một quan hệ bất kỳ trên lược đồ $R, X, \text{và } Y$ là hai tập thuộc tính con của $U$. Phụ thuộc hàm (FD – Functional Dependency) $X \to Y$ trên lược đồ quan hệ $R$, đọc là “$X$ xác định hàm $Y$” hoặc “$Y$ phụ thuộc hàm $X$”, nếu:

$$\forall t_1, t_2 \in r(R): t_1[X] = t_2[X] \implies t_1[Y] = t_2[Y]$$

tức là mỗi giá trị của $X$ trong $r$ chỉ tương ứng với một giá trị của $Y$.

Trong phụ thuộc hàm $f: X \to Y, X$ được gọi là vế trái (left side) của $f$, ký hiệu là $left(f)$ và $Y$ được gọi là vế phải (right side) của $f$, ký hiệu là $right(f)$.

Phụ thuộc hàm là một đặc điểm ngữ nghĩa của các thuộc tính trong một lược đồ quan hệ. Ngữ nghĩa của các thuộc tính cho thấy các thuộc tính liên quan với nhau như thế nào và xác định các phụ thuộc giữa các thuộc tính này. Phụ thuộc hàm được xem là một ràng buộc giữa các thuộc tính.

Định thuộc (determinant), tức là thuộc tính xác định, của một phụ thuộc hàm là tập thuộc tính bên vế trái của phụ thuộc hàm này. Trong phụ thuộc hàm $X \to Y$ thì $X$ là định thuộc.

Phụ thuộc hàm đầy đủ: $X \to A$ được gọi là phụ thuộc hàm đầy đủ (full functional dependency) nếu không tồn tại $Y \subset X$ để cho $Y \to A$.

Phụ thuộc hàm riêng phần: $X \to A$ được gọi là phụ thuộc hàm riêng phần (partial functional dependency) nếu tồn tại $Y \subset X$ để cho $Y \to A$.

Hệ tiên đề Armstrong

Tập các phụ thuộc hàm trên lược đồ quan hệ $R(U)$ là hữu hạn vì số lượng tập con của $U$ là hữu hạn. Do đó, chúng ta luôn tìm được tập các phụ thuộc hàm mà $r(R)$ thỏa mãn, bằng cách kiểm tra tất cả các phụ thuộc hàm có thể có, nhưng cách này rất tốn thời gian.

Phụ thuộc hàm $X \to Y$ được suy diễn luận lý từ $F$, ký hiệu là $F |= X \to Y$, nếu mọi quan hệ thỏa mãn tất cả các phụ thuộc hàm trong $F$ thì cũng thỏa mãn $X \to Y$.

$F |= X \to Y$ còn được gọi là $F$ bao hàm (implies) $X \to Y$ hoặc $X \to Y$ được suy diễn theo quan hệ từ F.

Quy tắc suy diễn (inference rule) là một quy tắc nếu một quan hệ thỏa mãn một số phụ thuộc hàm nào đó thì quan hệ này cũng thỏa mãn một số phụ thuộc hàm khác. Quy tắc suy diễn còn được gọi là luật suy diễn hoặc tiên đề suy diễn.

Tập các quy tắc suy diễn đã được Armstrong nêu ra vào năm 1974 và được gọi là hệ tiên đề Armstrong (Armstrong’s axioms) hoặc hệ quy tắc suy diễn Armstrong.

Cho lược đồ quan hệ $R(U)$ và $X, Y, Z, W$ là các tập con của $U$. Hệ tiên đề Armstrong bao gồm các tiên đề suy diễn sau đây:

  • F1, Phản xạ (reflexivity): $Y \subseteq X \implies X \to Y$
  • F1, Gia tăng (augmentation): $X \to Y \implies XZ \to YZ$
  • F3, Bắc cầu (transitivity)$X \to Y \text{và } Y \to Z \implies X \to Z$

Từ hệ tiên đề Armstrong, chúng ta có thể suy ra các quy tắc suy diễn sau dây:

  • F4, Hợp (additivity): $X \to Y \text{và } X \to Z \implies X \to YZ$
  • F5, Chiếu (projectivity): $X \to YZ \implies Z \to Y$
  • F6, Bắc cầu giả (pseudotransitivity): $X \to Y \text{và } YZ \to W \implies XZ \to {W}$

Bao đống của tập thuộc tính dựa trên tập phụ thuộc hàm

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$), ký hiệu là $X^+_F$, là một tập thuộc tính $Y$ sao cho:

  1. $\exists X \to Y \in F^+$
  2. $\forall X \to Z \in F^+: Z \subseteq Y$

Với một tập thuộc tính $X$ bất kỳ thì $X \subseteq X^+_F$ vì $X \to X \in F^+$

Khóa quan hệ

Để đánh giá một lược đồ quan hệ có tồn tại những bất thường hay không khi chúng ta muốn thêm vào các bộ mới, sửa đổ hay xóa bỏ các bộ cũ. Chúng ta phải dựa vào các khóa của lược đồ quan hệ này. Do đó, bài toán tìm tất cả các khóa của một lược đồ quan hệ là một bài toán rất quan trọng cho quá trình chuẩn hóa dữ liệu.