Chương 6: Phụ thuộc hàm và dạng chuẩn

Cơ sở khoa học để tối ưu cấu trúc bảng khi thiết kế cơ sở dữ liệu, tổ chức dữ liệu hợp lý, loại bỏ sự trùng lặp và đảm bảo tính toàn vẹn thông tin xuyên suốt trong các mô hình cơ sở dữ liệu.

---

1. Các khái niệm liên quan đến phụ thuộc hàm

1.1. Ví dụ mở đầu

Phụ thuộc hàm (function dependency) là một công cụ dùng để biểu diễn hình thức một cách hình thức các ràng buộc toàn vẹn. Đây là một công cụ cực kỳ quan trọng, gắn chặt với lý thuyết thiết kế cơ sở dữ liệu.

Ta có thể xem một ví dụ về Ràng buộc toàn vẹn sau:

Cho một quan hệ $\text{MONAN}$ sau:

MONANID	TENMONAN	GIATIEN
01	Banh My	10000
02	Bun Rieu Cua	50000
03	Xoi Thit	20000

Một số ràng buộc có thể kể đến trong quan hệ trên: Mỗi món ăn phải có một mã số duy nhất để phân biệt (PRIMARY KEY CONSTRAINT - $MonAnID$), $TenMonAn$ không được phép để trống (NOT NULL CONSTRAINT), $GiaTien$ không được phép bé hơn 0... Tất cả đều là các ràng buộc toàn vẹn, giúp dữ liệu trong bảng luôn thống nhất và hợp lệ.

Phụ thuộc hàm được ứng dụng trong việc giải quyết các bài toán tìm kiếm khóa cho bài toán.

Cho quan hệ $\text{TRUYENHINH}$ - cho biết các chương trình được phát sóng trên kênh truyền hình A

NHANVIEN	CHUONGTRINH	NGAY	GIO
An	Kamen Rider Zeztz	10/11	7:30a
Toan	Em Yeu Khoa Hoc	12/11	6:30p
Hung	The Gioi Dong Vat	12/11	2:00p
Nga	Buoi Trua Vui Ve	13/11	13:00p
An	Kamen Rider Zeztz	15/11	7:30a
Nga	The Gioi Dong Vat	15/11	2:00p
Hung	Em Yeu Khoa Hoc	16/11	6:30p
Nhi	Nguoi Ta Noi	18/11	10:00a
An	Code Khuya Cung An	19/11	00:00a

Quan hệ $\text{TRUYENHINH}$ diễn tả nhân viên nào sẽ phụ trách chương trình nào, và chương trình đó sẽ phát sóng vào thời gian nào. Không phải sự phối hợp bất kỳ nào giữa Nhân Viên, Chương trình, và Giờ Phát Sóng nào cũng đều được chấp thuận mà chúng có các điều kiện ràng buộc qui định sau:

• Mỗi chương trình có một giờ phát sóng duy nhất
  Ví dụ Kamen Rider Zeztz luôn chiếu vào lúc 7g30a, Code Khuya Cung An luôn chiếu vào lúc 00:00a...
• Nếu biết nhân viên phụ trách, ngày, giờ phát sóng thì biết được tên chương trình
  Ví dụ Biết được {Hung, 16/11 , 6:30p} thì biết được chương trình đó là Em Yeu Khoa Hoc
• Nếu biết tên chương trình, ngày, giờ phát sóng thì biết được nhân viên phụ trách chương trình đó
  Ví dụ Biết được {Buoi Trua Vui Ve, 13/11, 13:00p} thì biết được nhân viên phụ trách là Nga.

Các ràng buộc này là các ví dụ về phụ thuộc hàm và được phát biểu lại như sau:

• $ChuongTrinh$ xác định $Gio$
• $\{NhanVien, Ngay, Gio\}$ xác định $\{ChuongTrinh\}$
• $\{ChuongTrinh, Ngay, Gio\}$ xác định $\{NhanVien\}$

hay:

• $Gio$ phụ thuộc hàm vào $ChuongTrinh$
• $ChuongTrinh$ phụ thuộc hàm vào $\{NhanVien, Ngay, Gio\}$
• $NhanVien$ phụ thuộc hàm vào $\{ChuongTrinh, Ngay, Gio\}$

và được kí hiệu như sau:

• $\{ChuongTrinh\} \rightarrow \{Gio\}$
• $\{NhanVien, Ngay, Gio\} \rightarrow \{ChuongTrinh\}$
• $\{ChuongTrinh, Ngay, Gio\} \rightarrow \{NhanVien\}$

1.2. Phụ thuộc hàm

1.2.1. Khái niệm

Cho $X, Y$ là hai tập thuộc tính trên quan hệ $\text{R}$. $t_1, t_2$ là 2 bộ bất kỳ trên $\text{R}$. Ta nói $X$ xác định $Y$, kí hiệu $X \rightarrow Y$, nếu và chỉ nếu $t_1[X] = t_2[X]$ thì $t_1[Y] = t_2[Y]$

Ta nói $X$ xác định $Y$ hay $Y$ phụ thuộc hàm vào $X$. ($X$ là vế trái của phụ thuộc hàm, $Y$ là vế phải của phụ thuộc hàm).

Ví dụ: cho quan hệ $\text{SINHVIEN}$ như sau:

$\text{SINHVIEN}(MSSV, Ten, Mon, SoDT, ChuyenNganh, GiangVien, Diem)$

MSSV	TEN	MON	SODT	CHUYENNGANH	GIANGVIEN	DIEM
245200	Huy	CSDL	0913157875	HTTT	Thuy	5
245206	Hoang	CTRR	0913154521	CNPM	Lan	4
201293	Tinh	CSDL	0166397547	CNPM	Thuy	3
211234	Minh	NMLT	012145475	MangMT	Viet	1

Một số tính chất sau:

• Với mỗi Tên, xác định được duy nhất một số điện thoại và chuyên ngành
• Với mỗi Môn học, có duy nhất một Giảng viên
• Với mỗi Tên, Môn học có duy nhất một điểm

Kí hiệu:

• $\{Ten\} \rightarrow \{SoDT, ChuyenNganh\}$
• $\{Mon\} \rightarrow \{GiangVien\}$
• $\{Ten, Mon\} \rightarrow \{Diem\}$

1.2.2. Phụ thuộc hàm hiển nhiên (Trivial Dependencies)

Nếu $Y \subseteq X$ thì $X \rightarrow Y$ : Nếu $X$ bao hàm $Y$ (tức $Y$ là một thành phần của $X$) thì $X$ sẽ luôn xác định $Y$

Ví dụ: $X = \{MSSV, HoTen\}$, $Y = \{Ten\}$ thì $X \rightarrow Y$. Hiển nhiên đúng vì biết MSSV + Tên thì tất nhiên biết Tên

1.2.3. Tập phụ thuộc hàm

Tập phụ thuộc hàm ($F$) là một tập hợp gồm nhiều phụ thuộc hàm của một lược đồ quan hệ $\text{R}$. Nó mô tả các ràng buộc về mối quan hệ giữa các thuộc tính trong quan hệ đó. Ta có thể đánh số các phụ thuộc hàm của $F$ là $f_1, f_2, \ldots, f_m$.

Ký hiệu:

$$F = \{ X_1 \rightarrow Y_1, X_2 \rightarrow Y_2, ... \} = \{ f_1, f_2, \ldots, f_m \}$$

1.3. Luật dẫn Armstrong

1.3.1. Khái niệm

Gọi $F$ là tập các phụ thuộc hàm, ta nói phụ thuộc hàm $X \rightarrow Y$ được suy diễn logic từ $F$, nếu một quan hệ đã thỏa mãn tất cả các phụ thuộc hàm của $F$ thì cũng thỏa mãn phụ thuộc hàm $X \rightarrow Y$.

Kí hiệu:

$$F \vdash X \rightarrow Y$$

1.3.2. Tính chất

Với mọi tập thuộc tính $X, Y, Z$. Phụ thuộc hàm có các tính chất sau:

• F1. Tính phản xạ: Nếu $Y \subseteq X$ thì $X \rightarrow Y$
• F2. Tính tăng trưởng: $\{X \rightarrow Y\}$ $\models$ $XZ \rightarrow YZ$
• F3. Tính bắc cầu: $\{ X \rightarrow Y , Y \rightarrow Z \}$ $\models$ $X \rightarrow Z$
• F4. Tính kết hợp: $\{ X \rightarrow Y , X \rightarrow Z \}$ $\models$ $X \rightarrow YZ$X
• F5. Tính phân rã: $\{ X \rightarrow YZ$, $X \rightarrow Y \}$ $\models$ $X \rightarrow Z$
• F6. Tính tựa bắc cầu: $\{ X \rightarrow Y , WY \rightarrow Z \}$ $\models$ $WX \rightarrow Z$

Ví dụ: Cho $F = \{ A \rightarrow B, A \rightarrow C, BC \rightarrow D$. Chứng minh $A \rightarrow D$

Lời giải

• $\{ A \rightarrow B , A \rightarrow C \} \models A \rightarrow BC$ (tính kết hợp) (F4)

• $\{ A \rightarrow BC , BC \rightarrow D \} \models A \rightarrow D$ (tính bắc cầu) (F3)

Ví dụ: Cho $F = \{ A \rightarrow C, B \rightarrow D$. Chứng minh $AB \rightarrow ABCD$

Lời giải

• $\{ A \rightarrow C \} \models AB \rightarrow ABC$ (thêm vào $AB$ - Tính tăng trưởng) (F2)

• $\{ B \rightarrow D \} \models ABC \rightarrow ABCD$ (thêm vào $ABC$ - Tính tăng trưởng) (F2)

• $\{ AB \rightarrow ABC, ABC \rightarrow ABCD \} \models AB \rightarrow ABCD$ (Tính bắc cầu) (F3)

1.4. Bao đóng

1.4.1. Khái niệm

Bao đóng của tập phụ thuộc hàm: Bao đóng của tập phụ thuộc hàm $F$, kí hiệu là $F^+$, là tập tất cả các phụ thuộc hàm được suy ra từ $F$. Nếu $F = F^+$ thì $F$ là họ đầy đủ của các phụ thuộc hàm

Bao đóng của tập thuộc tính: Bao đóng của tập thuộc tính $X$ đối với tập phụ thuộc hàm $F$, kí hiệu là $X^+$ là tập tất cả các thuộc tính có thể suy dẫn từ $X$ nhờ tập bao đóng của các phụ thuộc hàm.

Ta sẽ chủ yếu quan tâm đến cách tìm bao đóng của một tập thuộc tính, sẽ được trình bày thông qua Thuật toán dưới đây.

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

Bài toán 1: Tìm bao đóng
Chúng ta sẽ cùng nghiên cứu thuật toán thông qua một bài toán minh họa:

Bài tập 1: Cho lược đồ quan hệ $\text{R}(A,B,C,D,E,F,G,H)$ và tập phụ thuộc hàm

$$F = {f_1: B \rightarrow A, f_2: DA \rightarrow CE, f_3: D \rightarrow H, f_4: GH \rightarrow C, f_5: AC \rightarrow D }$$

Hãy tìm bao đóng của $AC$ (Kí hiệu: $AC^+$)

Bước 1: $X_0 = AC$
Gọi bao đóng cần tìm là $X_0$, đầu tiên chắc chắn $X_0$ luôn bằng tập thuộc tính mà đề bài yêu cầu chúng ta tìm $X_0 = AC$

Bước 2: Lặp qua các phụ thuộc hàm của $f_i$ mà đề bài cho

Ta đang có: $X_0 = AC$. Ở đây, tôi sẽ tạm gọi vế bên phải là $X_0$, vế bên trái là $AC$ để dễ dàng truyền đạt.

Giả sử ta đang xét một phụ thuộc hàm có dạng $X \rightarrow Y$ thì điều kiện để thêm tập thuộc tính $Y$ vào vế trái của $X_0$ là tập thuộc tính $X$ phải xuất hiện ở vế bên trái của bao đóng cần tìm.

Hãy lần lượt xét các phụ thuộc hàm của đề bài cho theo thứ tự từ trái sang phải:

• Xét $f_1: B \rightarrow A$
  Vế trái của chúng ta hiện tại là $AC$, chưa xuất hiện $B$ nên không thể thêm $A$ vào bao đóng.

• Xét $f_2: DA \rightarrow CE$
  Vế trái của chúng ta hiện tại là $AC$, chưa xuất hiện $DA$ nên không thể thêm $CE$ vào bao đóng.

• Xét $f_3: D \rightarrow H$
  Vế trái của chúng ta hiện tại là $AC$, chưa xuất hiện $D$ nên không thể thêm $H$ vào bao đóng.

• Xét $f_4: GH \rightarrow C$
  Vế trái của chúng ta hiện tại là $AC$, chưa xuất hiện $GH$ nên không thể thêm $C$ vào bao đóng.

• Xét $f_5: AC \rightarrow D$
  Lúc này, vế trái trong bao đóng hiện tại đã có đủ thuộc tính $AC$ nên ta có thể thêm thuộc tính $D$ vào bao đóng. Lúc này $X_0 = ACD$

Bước 3. Lặp lại việc xét tập phụ thuộc hàm (lặp lại bước 2)

Việc lặp lại này sẽ kết thúc cho đến khi ta không thể thêm bất cứ thuộc tính nào vào bao đóng nữa.

Hiện tại: $X_0 = ACD$

• Xét $f_2: DA \rightarrow CE$
  Vế trái của chúng ta hiện tại đã có $AD$ nên có thể thêm $CE$ vào bao đóng. $X_0 = ACDE$

• Xét $f_3: D \rightarrow H$
  Vế trái của bao đóng đã có $D$ nên ta có thể thêm $H$ vào bao đóng. $X_0 = ADCEH$

• Xét $f_4: GH \rightarrow C$
  Vế trái của chúng ta chưa có $GH$ nên không thể thêm $C$ vào bao đóng. $X_0$ vẫn giữ nguyên.

Phụ thuộc hàm $f_5$ đã xét ở Bước 2 rồi nên ta không cần xét lại nữa.

Tiếp tục lặp lại việc xét các phụ thuộc hàm, bắt đầu lại từ $f_1...f_m$, … . Bao đóng cuối cùng thu được là: $AC^+_F = ACDEH$

Lưu ý: Các thuộc tính không cần phải viết theo thứ tự, chỉ cần đủ số lượng là được.

Bài toán 2: Cho biết $X \rightarrow Y$ có là phụ thuộc hàm thành viên của $F$ không?

Bài tập 2: Cho lược đồ quan hệ $\text{R}(A,B,C,D,E,F,G,H,I)$ và tập phụ thuộc hàm

$$F = {f_1: B \rightarrow E, f_2: BD \rightarrow IG, f_3: GE \rightarrow CH, f_4: DE \rightarrow BC, f_5: G \rightarrow A }$$

a) Phụ thuộc hàm $BG \rightarrow AI$ có là phụ thuộc hàm thành viên của $F$ không? Giải thích

Kiến thức: Cho tập thuộc tính $Q$, tập phụ thuộc hàm $F$ trên $Q$ và một phụ thuộc hàm $X \rightarrow Y$ trên $Q$. Ta có:

$$X \rightarrow Y \in F^+ \iff Y \subseteq X^+$$

Nghĩa là nếu ta tính ra được bao đóng của $X$ và kết luận được $Y$ thuộc vào bao đóng đó, thì ta có thể kết luận $X \rightarrow Y$ là một phụ thuộc hàm thành viên của $F$.

Bước 1: Tìm bao đóng của $X$

$BG^+_F = X_0 = BG$

• Xét $f_1: B \rightarrow E \Longrightarrow X_0 = BGE$
• Xét $f_2: BD \rightarrow IG \Longrightarrow BGE$ (Vế phải của bao đóng chưa xuất hiện $BD$ nên không thể thêm $IG$ vào bao đóng)
• Xét $f_3: GE \rightarrow CH \Longrightarrow X_0 = BGECH$
• Xét $f_4: DE \rightarrow BC \Longrightarrow X_0 = BGECH$ (Vế phải của bao đóng chưa xuất hiện $DE$ nên không thể thêm $CH$ vào)
• Xét $f_5: G \rightarrow A \Longrightarrow X_0 = BGECHA$

Tiếp tục lặp lại việc xét các phụ thuộc hàm của $f_i$. Cuối cùng, ta thu được bao đóng: $BG^+_F = \{ BGECH \}$

Bước 2: Xét điều kiện thành viên

Nếu như $AI \subseteq BG^+_F$ mà ta đã tính được ở trên thì ta có thể kết luận $BG \rightarrow AI \in F^+$, hay đây là một phụ thuộc hàm thành viên của $F$.

Tuy nhiên, ở ví dụ này ta có thấy: $AI \nsubseteq BG^+_F (AI \nsubseteq BGECHA)$

2. Khóa

2.1. Khái niệm

Cho lược đồ quan hệ $Q(A_1, A_2, A_3, ... , A_n)$, $A^+$ là tập thuộc tính của quan hệ $Q$. Khi đó, $K$ được gọi là một khóa của $Q$ nếu:

• $K^+ = A^+$
• Không tồn tại $K' \subset K$ sao cho $K^+_F = Q^+$

2.2. Thuật toán tìm khóa

Ta sẽ xét lại Bài tập 2 ở Phần 1 để nghiên cứu thuật toán tìm khóa

Bài tập 2: Cho lược đồ quan hệ $\text{R}(A,B,C,D,E,F,G,H,I)$ và tập phụ thuộc hàm

$$F = {f_1: B \rightarrow E, f_2: BD \rightarrow IG, f_3: GE \rightarrow CH, f_4: DE \rightarrow BC, f_5: G \rightarrow A }$$

b) Tìm tất cả các khóa của lược đồ quan hệ trên. Giải thích?

Bước 1. Tìm tập nguồn và tập trung gian

Xét một phụ thuộc hàm: $f_i: X \rightarrow Y$, ta sẽ quy ước $X$ là vế trái, $Y$ là vế phải của phụ thuộc hàm.

Tập nguồn: Tập hợp các thuộc tính chỉ xuất hiện ở vế bên trái của các phụ thuộc hàm (Kí hiệu $D$)

$$N = \{D\}$$

Tập trung gian: Tập hợp các thuộc tính xuất hiện ở cả vế bên trái và vế bên phải của phụ thuộc hàm (Kí hiệu $TG$)

Xét các phụ thuộc hàm $f_1,f_2, ... m f$. Các thuộc tính của tập trung gian là:

• $B$: xuất hiện ở vế trái của $f_2$, vế phải của $f_4$
• $G$: xuất hiện ở vế trái của $f_3$, vế phải của $f_2$
• $E$: xuất hiện ở vế trái của $f_4$, vế phải của $f_1$

$$TG = \{BGE\}$$

Bước 2. Tìm bao đóng của tập nguồn

$D_F^+ = D$

Mẹo xét nhanh: Nếu bao đóng của nguồn chứa tất cả thuộc tính của quan hệ, hay $D^+_F = \{ABCDEFGHI\}$ thì tập nguồn chính là khóa.

Nếu như bao đóng của tập nguồn không chứa tất cả thuộc tính của quan hệ, ta tiếp tục thuật toán với các bước bên dưới.

Bước 3. Xác định tất cả tập con (khác rỗng) của tập trung gian

Gọi tập hợp con của tập trung gian là:

$M = \{B, G, E, BG, GE, BE, BGE\}$

Bước 4. Xét các tổ hợp của tập nguồn $\cup$ $M_i$ để kết luận khóa

Lần lượt lấy tổ hợp của tập nguồn với từng phần tử con của tập $M$ hay $N \cup M_i$ để kết luận khóa.

Ta sẽ kẻ dạng bảng dưới đây để dễ dàng giải quyết bài toán:

$N$	$M_i$	$N \cup M_i$	$(N \cup M_i)^+_F$	Kết luận

Giải thích:

• Cột $N$: Nguyên cả tập nguồn
• Cột $M_i$: Các phần tử trong tập $M$ (tập hợp các tập con khác rỗng của tập trung gian)
• Cột $N \cup M_i$: Tính $N \cup M_i$
• Cột $(N \cup M_i)^+$: Tính bao đóng của ($N \cup M_i$)
• Kết luận: Kết luận xem $S \cup I_i$ có phải là khóa của quan hệ hay không

Bây giờ xét bài toán trên. Ta hãy xét $S \cup \{B\}$. Ta sẽ có một phần của bảng như sau:

$N$	$M_i$	$N \cup M_i$	$(N \cup M_i)^+_F$	Kết luận
D	B	DB	$DB^+ = DBEIGCHA = U^+$	DB là một khóa của quan hệ

Vì $DB$ đã là một khóa của quan hệ nên ta sẽ bỏ đi tất cả các tập con của $M$ mà có chứa $B$ (Tập con $M_1$ đã xét ở trên). Lúc này, tập còn lại là:

M = {B , G , E , BG , GE , BE , BGE } = $\{G , E , GE \}$

Xét tập con tiếp theo với $S \cup \{G\}$

$N$	$M_i$	$N \cup M_i$	$(N \cup M_i)^+_F$	Kết luận
D	B	DB	$DB^+ = DBEIGCHA = U^+$	DB là một khóa của quan hệ
D	G	DG	$DG^+ = DGA$	DG không phải là khóa

Vì $DG$ không phải là khóa nên ta không bỏ đi các tập con của $M$ có chứa $G$. Tập $M$ hiện tại còn cái phần tử:

$M = \{E , GE \}$

Xét tập con tiếp theo với $M_3 = \{E\}$

$N$	$M_i$	$N \cup M_i$	$(N \cup M_i)^+_F$	Kết luận
D	B	DB	$DB^+ = DBEIGCHA = U^+$	DB là một khóa của quan hệ
D	G	DG	$DG^+ = DGA$	DG không phải là khóa
D	E	DE	$DE^+ = DEIBCGHA$	DE là một khóa của quan hệ

Vì $DE$ đã là một khóa của quan hệ nên ta sẽ bỏ đi tất cả các tập con của $M$ mà có chứa $E$. Lúc này, tập còn lại là: $\varnothing$

Kết luận: Khóa của quan hệ là $DB$ và $DE$.

Chú ý:

• Phải xét theo thứ tự 1 thuộc tính, 2 thuộc tính, 3 thuộc tính… (Ví dụ: $\{A, B , C\}$, sau đó mới đến $\{AB , AC , BC\}$, cuối cùng mới đến $\{ABC\}$),... không được xét ngược lại.
• Nếu một tập thuộc tính đã là khóa thì ta có thể bỏ đi các tập con $M_i$ chứa tập thuộc tính đó. (Ví dụ: $AB$ là khóa thì ta có thể bỏ đi $ABC, ABD, AB$; không được bỏ đi tập con $M_i$chỉ chứa mỗi $$ hay chỉ chứa mỗi $B$, ví dụ: $AC, BC, AD$ )

2.3. Siêu khóa. Thuộc tính khóa

2.3.1. Siêu khóa

Tập thuộc tính $X$ được gọi là siêu khóa (superkey) nếu tồn tại một khóa $K$ của quan hệ sao cho: $K \subseteq X$. Nghĩa là tập thuộc tính này có chứa khóa

Xét ở Bài toán 2, ta có $K = \{DE, DB\}$ (đã tính được ở 2.2), ta có thể nêu một số siêu khóa như sau: $S = \{ADE, ADB, CEDB, IDB, ...\}$

Một khóa cũng được coi là một siêu khóa.

2.3.1. Thuộc tính khóa

Thuộc tính $A$ được gọi là thuộc tính khóa nếu: $A \in K$, với $K$ là một khóa bất kỳ của quan hệ $R$. Ngược lại, $A$ được gọi là thuộc tính không khóa.

Xét ở ví dụ trên, với khóa $DE$ thì thuộc tính khóa là $D, E$. Khóa $DB$ thì thuộc tính khóa là $D, B$. Ngược lại, các thuộc tính $A,B,C,G,H,I$ là thuộc tính không khóa.

3. Các dạng chuẩn

Trong thực tế, một ứng dụng cụ thể được thiết kế thành nhiều lược đồ cơ sở dữ liệu khác nhau, và tất nhiên chất lượng thiết kế của các lược đồ CSDL này cũng khác nhau. Chất lượng thiết kế của một lược đồ CSDL có thể được đánh giá dựa trên nhiều tiêu chuẩn, trong đó có sự trùng lắp thông tin và chi phí kiểm tra các ràng buộc toàn vẹn là hai tiêu chuẩn quan trọng.

Sau đây, ta sẽ tìm hiểu một số tiêu chí để đánh giá độ tốt / xấu của một lược đồ quan hệ. Trước tiên, ta hãy tìm hiểu sơ lược về một số khái niệm liên quan.

3.1. Khái niệm về xác định dạng chuẩn

Trong chương trình, ta sẽ tìm hiểu qua 4 loại dạng chuẩn: Dạng chuẩn 1 🡪 Dạng chuẩn 2 🡪 Dạng chuẩn 3 🡪 Dạng chuẩn BC.

Một lược đồ muốn đạt được dạng chuẩn thì trước hết phải đạt được dạng chuẩn trước đó.
Ví dụ: Muốn kiểm tra lược đồ đạt dạng chuẩn 3 không, trước tiên ta phải chứng minh được lược đồ đó đã đạt được dạng chuẩn 2. Nhưng để đạt được dạng chuẩn 2 trước hết lược đồ đó phải đạt được dạng chuẩn 1. Giả sử ở dạng chuẩn 3, lược đồ không đạt thì dạng chuẩn cao nhất lược đồ có thể đạt được là dạng chuẩn 2.

Ta sẽ tiếp tục xét Bài toán 2 để minh họa:

Bài tập 2: Cho lược đồ quan hệ $R = (U, F)$ trong đó $U$ là tập thuộc tính và $F$ là tập phụ thuộc hàm

$$U = \{A , B , C , D , E , F ,G , H , I\}$$ $$F = \{f_1: B \rightarrow E , f_2: BD \rightarrow IG , f_3: GE \rightarrow CH , f_4: DE \rightarrow BC , f_5: G \rightarrow A\}$$

c) Hãy tìm dạng chuẩn cao nhất mà lược đồ có thể đạt được. Giải thích?

Chú ý: Với bài tập tìm dạng chuẩn, bắt buộc phải tìm khóa của lược đồ trước.

Sau đây ta sẽ đi qua tìm hiểu các dạng chuẩn

3.2. Dạng chuẩn 1

Lược đồ ở dạng chuẩn 1 nếu mọi thuộc tính đều mang giá trị nguyên tố

Giá trị nguyên tố là giá trị không phân nhỏ được nữa. Ngược lại, các thuộc tính đa trị (multi-valued), đa hợp (composite) không là nguyên tố.

Ví dụ 1: Thuộc tính DIACHI của một quan hệ:
DIACHI: Số 7, Nguyễn Bỉnh Khiêm, TDP, Phường Ninh Hiệp, Ninh Hòa, Khánh Hòa 🡪 (Số nhà, Đường, Phường, Thị xã, Tỉnh). Đây không là thuộc tính nguyên tố.

Ví dụ 2: Cho quan hệ DONHANG

MAHD	MAKH	Tên hàng	Số lượng	ĐVT	SỐ TIỀN
HD01	KH02	Chuột gaming	1	Cái	200.000
HD02	KH04	Bàn phím cơ	1	Cái	905.000
HD03	KH03	RAM	4	Thanh	1.600.000

CHITIETMUA không là nguyên tố nên không thỏa dạng chuẩn 1

Trong thực tế, dạng chuẩn 1 rất hiếm khi xảy ra nên khi làm bài, ta có thể mặc định lược đồ cho đã thỏa mãn dạng chuẩn 1.

3.3. Dạng chuẩn 2

Lược đồ $Q$ thỏa dạng chuẩn 2 nếu:

• $Q$ đạt dạng chuẩn 1
• Mọi thuộc tính không khóa của đều phụ thuộc đầy đủ vào khóa

Kiểm tra dạng chuẩn 2

Bước 1: Tìm bao đóng của tất cả thuộc tính khóa

Xét Bài toán 2, ta có thuộc tính khóa là $DB, DE$ $\Longrightarrow$ Thuộc tính khóa: $D,B,E$.

• $B_F^+ = BE$
• $D_F^+ = D$
• $E_F^+ = E$

Bước 2: Xét tất cả các vế bên phải là $BE, D, E$, không có bất cứ thuộc tính không khóa nào xuất hiện. Vì vậy, lược đồ đạt dạng chuẩn 2.

Ngược lại, sau khi tính bao đóng, nếu xuất hiện một thuộc tính không khóa ở vế bên phải thì lược đồ sẽ không đạt dạng chuẩn 2.

3.4. Dạng chuẩn 3

Lược đồ $Q$ thỏa dạng chuẩn 3 nếu:

• $Q$ đạt dạng chuẩn 2
• Mọi thuộc tính không khóa của không phụ thuộc bắc cầu vào khóa chính của $Q$

Hoặc:

Lược đồ $Q$ ở dạng chuẩn 3 nếu mọi phụ thuộc hàm $X \rightarrow A \in F^+$, với $A \subseteq X$ đều có:

1. $X$ là siêu khóa, hoặc
2. $A$ là thuộc tính khóa

Kiểm tra dạng chuẩn 3

Bước 1: Tìm mọi khóa của $Q$

Xét lược đồ quan hệ trong Bài toán 2, các khóa là $BD$, $BE$.

Bước 2: Phân rã vế phải

Phân rã vế phải của mọi phụ thuộc hàm trong $F$ để tập $F$ trở thành tập phụ thuộc hàm có vế phải một thuộc tính.

Ta có:

$$H = \left\{f_1: B \rightarrow E , \begin{matrix}f_{21}: BD \rightarrow I \\ f_{22}: BD \rightarrow G\end{matrix}, \begin{matrix}f_{31}: GE \rightarrow C\\ f_{32}: GE \rightarrow H \end{matrix}, \begin{matrix}f_{41}: DE \rightarrow B \\ f_{42}: DE \rightarrow C \end{matrix}, f_5: G \rightarrow A\right\}$$

Bước 3: Kiểm tra vế trái - vế phải

Xét tập phụ thuộc hàm đã phân rã ở Bước 2, nếu ta tìm được một phụ thuộc hàm $X \rightarrow Y$ mà $X$ không là siêu khóa, $Y$ không là thuộc tính khóa thì lược đồ này KHÔNG ĐẠT dạng chuẩn 3.

Xét tập phụ thuộc hàm đã phân rã, ta có $f_{31}$ có vế trái $GE$ (không phải siêu khóa), vế phải $AH$ (không phải thuộc tính khóa). Lược đồ không đạt dạng chuẩn 3.

3.5. Dạng chuẩn BC (Boyce – Codd)

Lược đồ ở dạng chuẩn BC nếu mọi phụ thuộc hàm $X \rightarrow A \in F^+$, với $A \notin X$ đều có $X$ là siêu khóa.

Kiểm tra dạng chuẩn BC

Bước 1: Tìm mọi khóa của $Q$

Thực hiện thuật toán tìm khóa của một lược đồ quan hệ đã được trình bày ở Phần 2.2

Bước 2: Phân rã vế phải

Thực hiện tương tự việc Kiểm tra dạng chuẩn 3. Phân rã vế phải của mọi phụ thuộc hàm trong $F$ để tập $F$ trở thành tập phụ thuộc hàm có vế phải một thuộc tính.

Bước 3. Kiểm tra siêu khóa ở vế trái

Nếu mọi phụ thuộc hàm $X \rightarrow Y$ đã phân rã ra đều thỏa điều kiện $X$ là siêu khóa (vế trái chứa một khóa), thì lược đồ $Q$ đạt dạng chuẩn BC, ngược lại $Q$ không đạt dạng chuẩn BC.