Phụ thuộc hàm

Định nghĩa

Cho $R (U)$ là một quan hệ trên tập thuộc tính $U$ .
- $X, Y \subseteq U$ là hai tập thuộc tính con của $U$
- Ta gọi $X$ xác định hàm $Y$ hoặc $Y$ phụ thuộc hàm vào $X$ nếu với mọi quan hệ xác định trên $U$ và hai bộ $t_{1}$ , $t_{2}$ bất kì ta có $$t_1.X = t_2.X \Rightarrow t_1.Y = t_2.Y$$với $t_{1} . X$ là bộ giá trị các thuộc tính trong $X$ của $t_{1}$
- Khi đó ta có phụ thuộc hàm $X \to Y$
Hệ tiên đề Amstrong định nghĩa các tính chất của phụ thuộc hàm:
- Tính phản xạ: nếu $Y \subseteq X$ thì $X \to Y$
- Tính tăng trưởng: nếu $X \to Y$ thì $X Z \to Y Z$ (trong đó $X Z = X \cup Z$ )
- Tính bắc cầu: nếu $X \to Y$ và $Y \to Z$ thì $X \to Z$
Hệ quả:
- Luật hợp: Nếu $X \to Y$ , $X \to Z$ thì $X \to Y Z$
- Luật tựa bắc cầu: Nếu $X \to Y$ và $W Y \to Z$ thì $X W \to Z$
- Luật tách: Nếu $X \to Y$ và $Z \subseteq Y$ thì $X \to Z$

Các phép toán

Bao đóng của tập phụ thuộc hàm

F

là tập lớn nhất của các phụ thuộc hàm có thể được suy diễn logic từ $F$

$X \to Y$ được suy diễn logic từ $F$ nếu với mỗi quan hệ $r$ xác định trên $R (U)$ thỏa mãn các phụ thuộc hàm trong $F$ thì cũng thỏa mãn $X t o Y$

Kí hiệu bao đóng tập phụ thuộc hàm: $F^{+}$
Nếu $F = F^{+}$ , $F$ được gọi là một họ đầy đủ

Bao đóng của tập thuộc tính

X

là tập tất cả các thuộc tính được xác định bởi $X$ thông qua $F$

Kí hiệu: $X^{+}$ , ta có $$X^+ = {A\in U | X \to A \in F^+}$$
Nhận xét:

X \to Y \Leftrightarrow Y \subseteq X^{+}

Thuật toán tìm bao đóng của tập thuộc tính của $X$

Bước 1: Khởi tạo $X^{0} = X$ , $i = 1$
Bước 2: Tìm phụ thuộc hàm $Y_{i} \to Z_{i}$ sao cho $Y_{i} \subseteq X^{i - 1}$ , nếu không tìm được, chuyển đến bước 5
Bước 3: Duyệt các thuộc tính $A$ trong $Z_{i}$ , nếu $A \notin X^{i - 1}$ thì $X^{i} = X^{i - 1} \cup {A}$
Bước 4: Tăng $i$ thêm 1, chuyển đến bước 2
Bước 5: Kết thúc $X^{+} = X^{i}$

Khóa tối thiểu

$K \subseteq U$ được gọi là khóa tối thiểu nếu cả hai điều kiện sau thỏa mãn

$K \to U \in F^{+}$
$\forall K^{'} \subset K, K^{'} \to U \notin F^{+}$

Vậy nếu $K$ là khóa tối thiểu thì $K$ là (các) tập thuộc tính có số thuộc tính nhỏ nhất mà $K^{+} = U$

Thuật toán tìm khóa tối thiểu bằng loại trừ thuộc tính ( $n$ là số thuộc tính, chỉ số $A_{i}$ tính từ 1)

Bước 1: Khởi tạo $K^{0} = U$ , $i = 1$
Bước 2: Duyệt từng thuộc tính $A_{i}$ trong $U$ , nếu:
- $K^{i - 1} ∖ {A_{i}} \to U$ thì $K^{i} = K^{i - 1} ∖ {A_{i}}$
- ngược lại $K^{i} = K^{i - 1}$
Bước 3: Tăng $i$ thêm 1, nếu $i \leq n$ thì chuyển đến bước 2
Bước 4: Kết luận khóa tối thiểu $K = K^{n}$

Thuật toán tìm khóa tối thiểu bằng phân tích tập phụ thuộc hàm
Giả sử $F = {T_{i} \to P_{i}}$
Gọi $V T = {A \in U | A \in T_{i}}$
$V P = {A \in U | A \in P_{i}}$
$X = U ∖ V P$ là tập thuộc tính chắc chắn nằm trong $K$
$Y = V P ∖ V T$ là tập thuộc tính chắc chắn không nằm trong $K$
$Z = V P \cap V T$ là tập thuộc tính có thể nằm trong $K$

Qua đó sử dụng thuật toán loại trừ với $K^{0} = X \cup Z$ hoặc lần lượt thêm các thuộc tính của $Z$ vào $X$ cho đến khi $X^{+} = U$

Phủ của phụ thuộc hàm

Tập phụ thuộc hàm $F$ được gọi là một phủ của tập phụ thuộc hàm $G$ nếu mọi phụ thuộc hàm trong $G$ nếu có thể được suy diễn logic từ $F$ , hay $G^{+} \subseteq F^{+}$ .

Hai tập phụ thuộc hàm $F$ và $G$ được gọi là tương đương nếu $F$ là một phủ của $G$ và $G$ là một phủ của $F$ , hay $F^{+} = G^{+}$ . Kí hiệu $F \approx G$

Để kiểm tra $F \approx G$ , ta kiểm tra $f \in G^{+} \forall f \in F$ và $g \in F^{+} \forall g \in G$

$F$ được gọi là không dư thừa nếu $∄ f \in F, F ∖ {f} \approx F$

Thuật toán tìm phủ không dư thừa của một tập phụ thuộc hàm

Bước 1: Khởi tạo $F^{0} = F$ , $i = 1$ , $n = | F |$
Bước 2: Xét $f_{i}$ là phụ thuộc hàm thứ $i$ của $F$ . Nếu $F^{i - 1} ∖ {f_{i}} \approx F^{i - 1}$ thì đặt $F^{i} = F^{i - 1} ∖ {f_{i}}$ . Ngược lại, đặt $F^{i} = F^{i - 1}$
Bước 3: Tăng $i$ thêm 1, nếu $i \leq n$ thì chuyển đến bước 2
Bước 4: Kết luận phủ không dư thừa $F^{'} = F^{n}$

Phủ tối thiểu của tập phụ thuộc hàm

Phủ tối thiểu

$F_{c}$ được gọi là phủ tối thiểu của $F$ nếu thỏa mãn 3 điều kiện sau:

$\forall f \in F_{c}, f = X \to A | X \subset U, A \in U$
$\forall f = X \to A \in F_{c}, ∄ B \in X, (F_{c} ∖ {f} \cup {(X ∖ {B} \to A} \approx F_{c})$
$∄ f \in F_{c}, F ∖ {f} \approx F$

Thuật toán tìm phủ tối thiểu của tập phụ thuộc hàm $F$

Bước 1: Biến đổi $F$ về dạng $F_{1} = {L \to A | L \subset U, A \in U}$
Bước 2: Loại bỏ thuộc tính dư thừa ở vế trái: Xét phụ thuộc hàm $f_{i} = L_{i} \to A_{i}$ và các thuộc tính $A_{j} \in L_{i}$ , nếu $f_{i} = L_{i j} A_{j} \to A_{i}$ và $A_{i} \in L_{i j}^{+}$ , $A_{j}$ là thuộc tính dư thừa và cần bị loại bỏ. Sau khi loại bỏ tất cả các thuộc tính dư thừa ở vế trái của $F_{1}$ , ta được $F_{2}$
Bước 3: Loại bỏ phụ thuộc hàm dư thừa sử dụng thuật toán tìm phủ không dư thừa của tập phụ thuộc hàm $F_{2}$ cho ra $F_{3}$
Bước 4: Kết luật $F_{c} = F_{3}$ là phủ tối thiểu cần tìm