Bài giảng Cơ sở dữ liệu - Chương 7: Phụ thuộc hàm và chuẩn hóa cơ sở dữ liệu

Phụ thuộc hàm vàChuẩn hóa cơ sở dữ liệu 
Chương 7 
Nội dung trình bày 
Nguyên tắc thiết kế các lược đồ quan hệ. 
Phụ thuộc hàm. 
Các dạng chuẩn. 
Một số thuật toán chuẩn hóa. 
Nguyên tắc thiết kế 
Nhìn lại vấn đề thiết kế csdl 
Dựa trên trực quan của người thiết kế. 
Thiếu một tiêu chuẩn hình thức để đánh giá. 
Đánh giá chất lượng thiết kế 
Ngữ nghĩa của các thuộc tính. 
Giảm các giá trị thừa trong các bộ. 
Giảm các giá trị null trong các bộ. 
Không để xuất hiện các bộ không có thực. 
Ngữ nghĩa của các thuộc tính (1) 
p.k. 
MaPhong 
DChi 
NgSinh 
MaNV 
Ten 
f.k. 
NHANVIEN 
p.k. 
TrPhong 
MaPB 
Ten 
f.k. 
PHONGBAN 
p.k. 
Truso 
MaPB 
f.k. 
f.k. 
TRUSO_PHONG 
p.k. 
PhongQly 
Diadiem 
MaDA 
Ten 
f.k. 
DUAN 
SoGio 
MaDA 
MaNV 
p.k. 
f.k. 
f.k. 
THAMGIA 
Ngữ nghĩa của các thuộc tính (2) 
Ý nghĩa của các thuộc tính càng dễ hiểu thì lược đồ thiết kế càng tốt. 
Tránh tổ hợp các thuộc tính của nhiều kiểu thực thể vào cùng một lược đồ. 
TenPB 
MaPB 
p.k. 
TrPhong 
DChi 
NgSinh 
MaNV 
TenNV 
f.k. 
NHANVIEN_PHONGBAN 
TenDA 
TenNV 
p.k. 
Diadiem 
Gio 
MaDA 
MaNV 
f.k. 
NHANVIEN_DUAN 
Thông tin thừa trong các bộ (1) 
4 
19/01/1968 
999887777 
Vuong 
5 
08/12/1955 
333445555 
Nghia 
5 
09/01/1965 
123456789 
Hung 
MaPhong 
DChi 
NgSinh 
MaNV 
Ten 
NHANVIEN 
333445555 
5 
Nghien cuu 
TrPhong 
MaPB 
Ten 
PHONGBAN 
333445555 
Nghien cuu 
5 
09/10/1965 
123456789 
Hung 
Nghien cuu 
TenPB 
5 
MaPB 
333445555 
... 
08/12/1965 
333445555 
Nghia 
TrPhong 
DChi 
NgSinh 
MaNV 
TenNV 
NHANVIEN_PHONGBAN 
Dữ liệu bị trùng lặp 
Thông tin thừa trong các bộ (2) 
Dị thường khi thêm bộ 
Dị thường khi xóa bộ 
999887777 
Nghien cuu 
5 
09/10/1965 
123456789 
Hung 
333445555 
Nghien cuu 
5 
08/12/1965 
333445555 
Nghia 
Hanh chinh 
TenPB 
4 
MaPB 
987654321 
null 
null 
null 
null 
TrPhong 
DChi 
NgSinh 
MaNV 
TenNV 
NHANVIEN_PHONGBAN 
333445555 
Nghien cuu 
5 
09/10/1965 
123456789 
Hung 
333445555 
Nghien cuu 
5 
08/12/1965 
333445555 
Nghia 
TenPB 
MaPB 
TrPhong 
DChi 
NgSinh 
MaNV 
TenNV 
NHANVIEN_PHONGBAN 
Thông tin thừa trong các bộ (3) 
Dị thường khi sửa bộ 
Tránh xảy ra các dị thường cập nhật dữ liệu. 
Có thể vi phạm nguyên tắc này để tăng hiệu quả truy vấn dữ liệu. Khi đó các dị thường cần được ghi chú cẩn thận. 
333445555 
Nghien cuu 
5 
09/10/1965 
123456789 
Hung 
333445555 
Nghien cuu 
5 
08/12/1965 
333445555 
Nghia 
TenPB 
MaPB 
TrPhong 
DChi 
NgSinh 
MaNV 
TenNV 
NHANVIEN_PHONGBAN 
123456789 
123456789 
Giá trị null trong các bộ 
Nếu nhiều thuộc tính trong lược đồ nhận giá trị null sẽ 
Lãng phí không gian lưu trữ. 
Khó khăn trong thực hiện các phép toán kết. 
Khó khăn khi sử dụng các hàm tập hợp. 
Tránh lưu trữ các thuộc tính nhận nhiều giá trị null. 
Phát sinh các bộ không có thực (1) 
Thu Duc 
San pham Y 
Hung 
7.5 
2 
123456789 
Tan Binh 
San pham X 
Hung 
32.5 
1 
123456789 
Diadiem 
TenDA 
TenNV 
Gio 
MaDA 
MaNV 
San pham Y 
Nghia 
Thu Duc 
10 
2 
333445555 
NHANVIEN_DUAN 
p.k. 
Diadiem 
TenNV 
NHANVIEN_DIADIEM 
SoGio 
MaDA 
p.k. 
MaNV 
NHANVIEN_DUAN1 
Diadiem 
TenDA 
Phát sinh các bộ không có thực (2) 
Thu Duc 
Hung 
Tan Binh 
Hung 
Diadiem 
TenNV 
Thu Duc 
Nghia 
NHANVIEN_DIADIEM 
Thu Duc 
San pham Y 
7.5 
2 
123456789 
Tan Binh 
San pham X 
32.5 
1 
123456789 
Diadiem 
TenDA 
SoGio 
MaDA 
MaNV 
10 
2 
333445555 
NHANVIEN_DUAN1 
Thu Duc 
San pham Y 
Hung 
Thu Duc 
San pham Y 
10 
2 
333445555 
Nghia 
Thu Duc 
San pham Y 
7.5 
2 
123456789 
Thu Duc 
Thu Duc 
Tan Binh 
Diadiem 
Nghia 
Hung 
Hung 
TenNV 
San pham Y 
7.5 
2 
123456789 
San pham X 
32.5 
1 
123456789 
TenDA 
Gio 
MaDA 
MaNV 
San pham Y 
10 
2 
333445555 
Kết tự nhiên 
Phát sinh các bộ không có thực (3) 
Xây dựng các lược đồ quan hệ sao cho việc thực hiện phép kết bằng giữa chúng chỉ áp dụng trên các thuộc tính khóa chính hoặc khóa ngoại. 
Nội dung trình bày 
Nguyên tắc thiết kế các lược đồ quan hệ. 
Phụ thuộc hàm. 
Các dạng chuẩn. 
Một số thuật toán chuẩn hóa. 
Phụ thuộc hàm (1) 
Xét lược đồ quan hệ gồm n thuộc tính 
R(U), U={A 1 , A 2 ,, A n } 
PTH giữa hai tập thuộc tính X, Y  U 
Ký hiệu: X Y. 
 r R,  t 1 , t 2 r nếu t 1 [X] = t 2 [X] thì t 1 [Y] = t 2 [Y]. 
X là vế trái và Y là vế phải của PTH. 
7 
3 
5 
1 
4 
1 
B 
A 
r(R) 
r không thỏa A B, nhưng thỏa B A 
Phụ thuộc hàm (2) 
r R thỏa các ràng buộc PTH được gọi là trạng thái hợp lệ của R. 
Nhận xét 
Các PTH xuất phát từ các ràng buộc trong thế giới thực. 
 r R,  t r, t [X] là duy nhất thì X là một khóa của R. 
Nếu K là một khóa của R thì K xác định hàm tất cả các tập thuộc tính của R. 
PTH dùng để đánh giá một thiết kế CSDL. 
TrPhong 
TenPB 
MaPB 
Diachi 
NgSinh 
MaNV 
TenNV 
NHANVIEN_PHONGBAN 
MaNV MaPB 
MaPB {TenPB, TrPhong} 
MaNV TenNV 
Bao đóng của tập PTH 
F là tập PTH trên R 
F = {MaNV TenNV, MaPB {TenPB, TrPhong}, MaNV MaPB}. 
 r  R thỏa F và MaNV {TenPB, TrPhong} cũng đúng với r thì MaNV {TenPB, TrPhong} gọi là được suy diễn từ F. 
Bao đóng của F, ký hiệu F + , gồm 
F và 
Tất cả các PTH được suy diễn từ F. 
F gọi là đầy đủ nếu F = F + . 
Luật suy diễn 
Luật suy diễn dùng để suy diễn một PTH mới từ một tập PTH cho trước. 
Hệ luật suy diễn Armstrong 
Phản xạ: Y  X X Y. 
Tăng trưởng: X Y XZ YZ, với XZ = X  Z. 
Bắc cầu: X Y, Y Z X Z. 
Các luật khác: 
Phân rã: X YZ X Y, X Z. 
Hợp: X Y, X Z X YZ. 
Bắc cầu giả: X Y, WY Z WX Z. 
Nhận xét 
Hệ luật Armstrong là đầy đủ. 
Bao đóng của tập thuộc tính 
Làm thế nào để biết một PTH X Y được suy diễn từ tập PTH F cho trước? 
Bao đóng của tập thuộc tính X đối với F, ký hiệu X + , là 
Tập các thuộc tính PTH vào X. 
X + = {A U | X A F + } 
Nhận xét 
X Y F + Y  X + . 
Nếu K là khóa của R thì K + = U. 
Thuật toán tìm X + 
Nhập: U, F và X  U 
Xuất: X + 
Thuật toán 7.1 
B1 : X + = X; 
B2 : Nếu tồn tại Y Z F và Y  X + thì 
	 X + := X +  Z; 
 và tiếp tục B2 . Ngược lại qua B3 . 
B3 : xuất X + . 
Ví dụ tìm X + 
Cho: 
F = {AB C, BC D, D EG}. 
X = BD. 
Tính X + : 
X + = BD. 
Lặp 1: 
Tìm các PTH có vế trái là tập con của X + = BD 
D EG, thêm EG vào X + ta được X + = BDEG. 
Lặp 2: 
Tìm các PTH có vế trái là tập con của X + = BDEG 
Không có PTH nào. 
Vậy X + = BDEG. 
Kiểm tra PTH suy diễn 
Cho F = {AB C, A D, D E, AC B} 
Hai PTH AB E và D C có được suy diễn từ F hay không? 
DE 
D 
ABCDE 
AB 
X F + 
X 
Được suy diễn từ F 
Các tập PTH tương đương 
Tập PTH F được nói là phủ tập PTH G nếu G  F + . 
Hai tập PTH F và G là tương đương nếu 
F phủ G và 
G phủ F. 
Nhận xét 
 X Y G, nếu Y  X F + thì F phủ G. 
F và G tương đương nếu và chỉ nếu F + = G + . 
Tập PTH tối thiểu (1) 
Thừa PTH 
{A B, B C, A C }, vì A C được suy diễn từ {A B, B C} 
A B, B C A C (luật bắc cầu). 
Thừa thuộc tính 
{A B, B C, A C D}, vì A CD được suy diễn từ {A B, B C, A D} 
A B, B C A C (luật bắc cầu) 
A C, A D A CD (luật hợp). 
{A B, B C, A C D}, vì AC D được suy diễn từ {A B, B C, A D} 
A B, A D A BD (luật hợp) 
A BD AC BCD (luật tăng trưởng) 
AC BCD AC D (luật phân rã). 
Tập PTH tối thiểu (2) 
Tập PTH F là tối thiểu nếu thỏa các điều kiện sau 
Mọi PTH của F chỉ có một thuộc tính ở vế phải. 
Không thể thay X A thuộc F bằng Y A với Y  X mà tập mới tương đương với F. 
Nếu bỏ đi một PTH bất kỳ trong F thì tập PTH còn lại không tương đương với F. 
Phủ tối thiểu của tập PTH E là tập PTH tối thiểu F tương đương với E. 
Nhận xét 
Mọi tập PTH có ít nhất một phủ tối thiểu. 
Thuật toán tìm phủ tối thiểu 
Nhập: tập PTH E. 
Xuất: phủ tối thiểu F của E. 
Thuật toán 7.2 
B1 : F :=  . 
B2 : Với mọi X Y E, Y = {A 1 , , A k }, A i U 
F := F  {X {A i }}. 
B3 : Với mỗi X {A} F, X = {B 1 , , B l }, B i U 
Với mỗi B i , nếu A (X - {B i }) F + thì 
	 F := (F - {X {A}})  {(X - {B}) {A}}. 
B4 : Với mỗi X {A} F 
G := F - {X {A}} 
Nếu A X G + thì F := F - {X {A}}. 
Ví dụ tìm phủ tối thiểu 
Tìm phủ tối thiểu của E = {A BC, A B, B C, AB C} 
B1 : F =  . 
B2 : F = {A B, A C, B C, AB C}. 
B3 : Xét AB C 
	(B) F + = BC 
	F = {A B, A C, B C}. 
B4 : A C thừa. 
	F = {A B, B C}. 
Siêu khóa và khóa 
Cho R(U) 
S  U là siêu khóa nếu  r R,  t 1 , t 2 r, t 1 t 2 thì t 1 [S] t 2 [S]. 
K  U là khóa nếu K là siêu khóa nhỏ nhất. 
A K được gọi là thuộc tính khóa. 
Nhận xét 
S xác định hàm tất cả các thuộc tính của R. 
R có thể có nhiều khóa. 
Xác định khóa của lược đồ 
Nhập: tập PTH F xác định trên lược đồ R(U). 
Xuất: khóa K của R. 
Thuật toán 7.3.1 
B1 : 
K = U = {A 1 , , A n }; 
i = 1; 
B2 : 
Nếu U  (K - {A i }) F + thì K = K - {A i }. 
i = i + 1; 
Nếu i > n thì sang B3 . Ngược lại, tiếp tục B2 . 
B3 : 
Xuất K. 
Ví dụ tìm khóa của lược đồ 
Cho R(U), U = {A, B, C, D, E, F, G}. 
F = {B A, D C, D BE, DF G}. 
Tìm khóa của R 
B1: 
K = ABCDEFG. 
B2: 
Lặp 1: (BCDEFG) F + = BCDEFGA K = BCDEFG. 
Lặp 2: (CDEFG) F + = CDEFGBA K = CDEFG. 
Lặp 3: (DEFG) F + = DEFGCBA K = DEFG. 
Lặp 4: (EFG) F + = EFG. 
Lặp 5: (DFG) F + = DFGCBEA K = DFG. 
Lặp 6: (DG) F + = DGCBEA. 
Lặp 7: (DF) F + = DFCBEAG K = DF. 
B3: 
Khóa là K = DF. 
Xác định tất cả khóa của lược đồ 
Nhập: tập PTH F xác định trên lược đồ R(U). 
Xuất: tất cả khóa của R. 
Thuật toán 7.3.2 
B1 : 
Xây dựng 2 n tập con của U = {A 1 , , A n }; 
S = {}; 
B2 : 
Với mỗi tập con X  U 
Nếu U  X F + thì S = S  {X}. 
B3 : 
 X, Y S, nếu X  Y thì S = S - {Y}. 
B4 : 
S là tập các khóa của R. 
Ví dụ tìm tất cả khóa của lược đồ 
Cho R(U), U = {A, B, C, D, E, F}. 
F = {AE C, CF A, BD F, AF E}. 
Tìm tất cả khóa của R 
Tập siêu khóa 
S = {ABD, BCD, ABCD, ABDE, BCDE, ABCDE, ABDF, BCDF, ABCDF, 
 ABDEF, BCDEF, ABCDEF}. 
ABD 
BCD 
ABCD 
ABDE 
BCDE 
ABCDE 
ABDF 
BCDF 
ABCDF 
ABDEF 
BCDEF 
ABCDEF 
Xác định tất cả các khóa của lược đồ 
VT F = Tập hợp các thuộc tính ở vế trái các PTH của F 
VP F = Tập hợp các thuộc tính ở vế phải các PTH của F 
N = U – VP F 
D = U – (N  VT F ) 
L = U – ( N  D) 
Nếu K là khóa của R thì tồn tại L i  L sao cho K = N  L i . 
Nội dung trình bày 
Nguyên tắc thiết kế các lược đồ quan hệ. 
Phụ thuộc hàm. 
Các dạng chuẩn. 
Một số thuật toán chuẩn hóa. 
Chuẩn hóa lược đồ CSDL 
Chuẩn hóa là gì? 
Các dạng chuẩn là gì? 
Các dạng chuẩn 
Dạng 1 (1 Normal Form - 1NF). 
Dạng 2 (2 Normal Form - 2NF). 
Dạng 3 (3 Normal Form - 3NF). 
Dạng Boyce - Codd (Boyce - Codd Normal Form - BCNF). 
Dạng chuẩn 1 (1) 
Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 1 nếu và chỉ nếu mọi thuộc tính của R là thuộc tính đơn. 
Go Vap 
987654321 
4 
Hanh chinh 
Tan Binh, 
Thu Duc 
333445555 
5 
Nghien cuu 
CacTruso 
TrPhg 
MaPB 
TenPB 
PHONGBAN 
Thu Duc 
333445555 
5 
Nghien cuu 
Go Vap 
987654321 
4 
Hanh chinh 
Tan Binh 
333445555 
5 
Nghien cuu 
Truso 
TrPhg 
MaPB 
TenPB 
PHONGBAN 
Không thuộc 
dạng chuẩn 1 
Thuộc dạng chuẩn 1 
Dạng chuẩn 1 (2) 
Nhận xét 
Mọi lược đồ quan hệ đều thuộc dạng chuẩn 1. 
Dạng chuẩn 1 có thể dẫn đến sự trùng lặp dữ liệu. Do đó gây ra các dị thường về cập nhật dữ liệu. 
Dạng chuẩn 2 theo khóa chính (1) 
Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 2 nếu mọi thuộc tính không khóa của R phụ thuộc đầy đủ vào khóa chính của R. 
R(U), K  U là khóa của R 
A U là thuộc tính không khóa nếu A  K. 
X Y là PTH đầy đủ nếu  A X thì (X - {A}) Y không đúng trên R. Ngược lại X Y là PTH bộ phận. 
Ví dụ 
FD2 
FD1 
Diadiem 
TenDA 
TenNV 
SoGio 
MaDA 
MaNV 
FD3 
NVIEN_DUAN 
Thuộc tính không khóa 
PTH đầy đủ 
PTH bộ phận 
Dạng chuẩn 2 theo khóa chính (2) 
FD2 
FD1 
Diadiem 
TenDA 
TenNV 
SoGio 
MaDA 
MaNV 
FD3 
NVIEN_DUAN 
FD1 
SoGio 
MaDA 
MaNV 
NV_DA1 
FD2 
TenNV 
MaNV 
NV_DA2 
FD3 
Diadiem 
TenDA 
MaDA 
NV_DA3 
3 lược đồ NV_DA1, NV_DA2, NV_DA3 thuộc dạng chuẩn 2 
Dạng chuẩn 2 theo khóa chính (3) 
Nhận xét 
Mọi lược đồ quan hệ thuộc dạng chuẩn 2 cũng thuộc dạng chuẩn 1. 
Nếu R chỉ có một khóa K và card(K) = 1 thì R thuộc dạng chuẩn 2. 
Còn xuất hiện sự trùng lặp dữ liệu. Do đó gây ra các dị thường về cập nhật dữ liệu. 
FD2 
FD1 
TenPB 
MaPB 
TrPhong 
DChi 
NgSinh 
MaNV 
TenNV 
NHANVIEN_PHONGBAN 
Thuộc dạng 
chuẩn 2 
Dạng chuẩn 3 theo khóa chính (1) 
Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 3 nếu 
R thuộc dạng chuẩn 2. 
Mọi thuộc tính không khóa của R không phụ thuộc bắt cầu vào khóa chính của R. 
Cho R(U) 
X Y là PTH bắt cầu nếu  Z  U, Z không là khóa và cũng không là tập con của khóa của R mà X Z và Z Y đúng trên R. 
Ví dụ 
FD2 
FD3 
FD1 
TenPB 
MaPB 
TrPhong 
DChi 
NgSinh 
MaNV 
TenNV 
NHANVIEN_PHONGBAN 
PTH bắt cầu 
Dạng chuẩn 3 theo khóa chính (2) 
Nhận xét 
Mọi lược đồ quan hệ thuộc dạng chuẩn 3 cũng thuộc dạng chuẩn 2. 
PTH bắt cầu là nguyên nhân dẫn đến trùng lặp dữ liệu. 
Dạng chuẩn 3 là dạng chuẩn tối thiểu trong thiết kế CSDL. 
MaPB 
Diachi 
NgSinh 
MaNV 
TenNV 
NV_PB1 
TrPhg 
TenPB 
MaPB 
NV_PB2 
Thuộc dạng 
chuẩn 3 
Dạng chuẩn 2 tổng quát 
Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 2 nếu mọi thuộc tính không khóa của R phụ thuộc đầy đủ vào các khóa của R. 
Cho R(ABCDEF) có 2 khóa là A và BC. 
FD3 
FD2 
FD1 
F 
E 
D 
C 
B 
A 
FD4 
R 
FD5 
Lược đồ R không thuộc dạng chuẩn 2 
Dạng chuẩn 3 tổng quát 
Lược đồ quan hệ R được gọi là thuộc dạng chuẩn 3 nếu PTH không hiển nhiên X A đúng trên R thì 
X là siêu khóa của R, hoặc 
A là thuộc tính khóa của R. 
R1(ABCDE) có 2 khóa là A và BC. 
Nhận xét 
Định nghĩa tổng quát cho phép kiểm tra dạng chuẩn 3 mà không cần kiểm tra dạng chuẩn 2. 
FD2 
FD1 
E 
D 
C 
B 
A 
FD4 
R1 
Lược đồ bên 
thuộc dạng 
chuẩn 2, 
nhưng không 
thuộc dạng 
chuẩn 3 
FD5 
Dạng chuẩn Boyce - Codd (1) 
Lược đồ quan hệ R được gọi là thuộc dạng chuẩn BC nếu PTH không hiển nhiên X Y đúng trên R thì X là siêu khóa của R. 
R11(ABCD) 
FD2 
FD5 
FD1 
D 
C 
B 
A 
R11 
Lược đồ R11 thuộc dạng chuẩn 3,nhưng không thuộc dạng chuẩn BC 
Dạng chuẩn Boyce - Codd (2) 
1 
b 
a 
2 
2 
a 
b 
3 
2 
b 
b 
4 
1 
a 
a 
1 
D 
C 
B 
A 
R11 
1 
b 
2 
2 
a 
3 
2 
b 
4 
1 
a 
1 
D 
C 
A 
R111 
b 
2 
a 
1 
B 
D 
R112 
Trùng lặp dữ liệu 
Dạng chuẩn Boyce - Codd (3) 
Nhận xét 
Mọi lược đồ quan hệ thuộc dạng chuẩn BC cũng thuộc dạng chuẩn 3. 
Dạng chuẩn BC đơn giản và chặt chẽ hơn dạng chuẩn 3. 
Mục tiêu của quá trình chuẩn hóa là đưa các lược đồ quan hệ về dạng chuẩn 3 hoặc BC. 
FD1 
D 
C 
A 
R111 
FD5 
D 
B 
R112 
2 lược đồ trên thuộc dạng chuẩn BC 
Thiết kế Top-Down 
Các bước thực hiện 
Thiết kế lược đồ mức khái niệm với mô hình dữ liệu cấp cao (EER). 
Chuyển lược đồ khái niệm thành tập hợp các quan hệ. 
Với mỗi quan hệ xác định tập PTH. 
Áp dụng các quy tắc chuẩn hóa để loại bỏ các PTH bộ phận và bắt cầu trong các quan hệ. 
Nội dung trình bày 
Nguyên tắc thiết kế các lược đồ quan hệ. 
Phụ thuộc hàm. 
Các dạng chuẩn. 
Một số thuật toán chuẩn hóa. 
Phân rã lược đồ quan hệ 
Lược đồ quan hệ chung R(A 1 , , A n ) 
Tập hợp tất cả các thuộc tính của các thực thể. 
Xác định tập PTH F trên R. 
Phân rã 
Sử dụng các thuật toán chuẩn hóa để tách R thành tập các lược đồ D = {R 1 , , R m }. 
Yêu cầu 
Bảo toàn thuộc tính. 
Các lược đồ R i phải ở dạng chuẩn 3 hoặc Boyce-Codd. 
Phân rã bảo toàn PTH (1) 
Tính chất bảo toàn PTH 
Xét lược đồ R và tập PTH F. Giả sử R được phân rã thành D = {R 1 , , R m }. 
Đặt Ri (F) = {X Y F + : X  Y  R i }. 
D được gọi là phân rã bảo toàn phụ thuộc hàm đối với F nếu ( R1 (F)    Rm (F)) + = F + . 
Ví dụ 
FD2 
FD5 
FD1 
D 
C 
B 
A 
R11 
FD1 
D 
C 
A 
R111 
FD5 
D 
B 
R112 
Phân rã bảo toàn PTH (2) 
2 
 
3 
3 
 
 
2 
2 
 
1 
D 
C 
B 
A 
R11 
2 
 
3 
4 
 
4 
3 
 
2 
2 
 
1 
D 
C 
A 
R111 
 
3 
4 
2 
D 
B 
R112 
4 
 
4 
2 
 
1 
D 
C 
B 
A 
Thêm bộ (4,  , 4) vào R111 
và (4, ) vào R112 
thì trạng thái csdl sẽ không 
thỏa PTH FD2 
Phân rã bảo toàn PTH (3) 
Định lý 7.1 
Tồn tại một phân rã bảo toàn PTH D = {R 1 , , R m } của lược đồ R đối với tập PTH F sao cho các R i ở dạng chuẩn 3. 
Thuật toán 7.4 
Nhập: R(U), U = {A 1 , , A n } và tập PTH F. 
Xuất: D = {R 1 , , R m }, R i ở dạng chuẩn 3. 
B1 : 
Tìm phủ tối thiểu G của F. 
B2 : 
Với mỗi X A i G, xây dựng lược đồ R i (U i ), U i = X  {A j }. Khóa chính của R i là X. 
Phân rã bảo toàn PTH (4) 
B3 : 
Giả sử xong B2 ta có các lược đồ R 1 , , R m . Nếu U 1    U m U thì xây dựng thêm lược đồ R m+1 (U m+1 ), U m+1 = U - (U 1    U m ). Khóa chính của R m+1 là U m+1 . 
B4 : 
Xuất các lược đồ R i . 
Ví dụ phân rã bảo toàn PTH (1) 
Cho 
R(ABCDEFG) 
F = {B A, D C, D EB, DF G} 
Tách về dạng chuẩn 3, bảo toàn PTH 
B1 : 
Phủ tối thiểu G = {B A, D C, D B, D E, DF G}. 
B2 : 
B3 : 
Xuất D = {R 1 , R 2 , R 3 }. 
R(ABC D E F G) 
R 1 ( B A) 
R( D C) 
R 3 ( DF G) 
R( D B) 
R( D E) 
R 2 ( D BCE) 
Ví dụ phân rã bảo toàn PTH (2) 
Cho 
R(ABCDEFGHI) 
F = {B A, D C, D EB, DF G} 
Tách về dạng chuẩn 3, bảo toàn PTH 
B1 : 
Phủ tối thiểu G = {B A, D C, D B, D E, DF G}. 
B2 : 
B3 : 
Vì U 1  U 2  U 3 = {ABCDEFG} nên đặt R 4 (HI). 
B4 : 
D = {R 1 , R 2 , R 3 , R 4 }. 
R(ABC D E F G) 
R 1 ( B A) 
R 3 ( DF G) 
R 2 ( D BCE) 
Phân rã không mất thông tin (1) 
Tính chất không mất thông tin 
Xét lược đồ R và tập PTH F. Giả sử R được phân rã thành D = {R 1 , , R m }. 
D được gọi là phân rã không mất thông tin đối với F nếu với mọi trạng thái r R thì ( R1 (r) *  * Rm (r)) = r. 
Định lý 7.2 
Phân rã D = {R 1 (U 1 ), R 2 (U 2 )} của R(U) không mất thông tin đối với tập PTH F nếu và chỉ nếu: 
(U 1  U 2 ) (U 1 – U 2 ) F + , hoặc 
(U 1  U 2 ) (U 2 – U 1 ) F + . 
Định lý 7.3 
Nếu phân rã D = {R 1 , , R m } của R không mất thông tin đối với F và phân rã D i = {Q 1 , , Q k } của R i không mất thông tin đối với Ri (F) thì D’ = {R 1 , , R i-1 , Q 1 , , Q k , R i+1 , , R m } của R cũng không mất thông tin. 
Phân rã không mất thông tin (2) 
Thuật toán 7.5 
Nhập: R(U), U = {A 1 , , A n } và tập PTH F. 
Xuất: D = {R 1 , , R m }, R i ở dạng chuẩn Boyce-Codd. 
B1 : 
D = {R}; 
B2 : 
Nếu có lược đồ Q(U Q ) D không ở dạng chuẩn BC thì 
Tìm X Y  Q (F) làm Q vi phạm điều kiện BC. 
D = (D - {Q})  Q 1 (U Q1 )  Q 2 (U Q2 ) với U Q1 = U Q - Y và U Q2 = X  Y. 
Quay lại B2. 
Ngược lại, chuyển sang B3. 
B3 : 
Xuất D. 
Ví dụ phân rã không mất thông tin (1) 
Cho: 
R(ABCDEFG) 
F = {B A, D C, D EB, DF G} 
Tách về dạng chuẩn BC, không mất thông tin. 
D BCE 
B A 
R(ABCDEFG) 
R 1 (BA) 
R 2 (BCDEFG) 
R 3 (DBCE) 
R 4 (DFG) 
F, K R = DF 
{B A}, 
K R1 = B 
{D C, D EB, DF G }, 
K R2 = DF 
{D C, D EB }, 
K R3 = D 
{DF G}, 
K R4 = DF 
Ví dụ phân rã không mất thông tin (2) 
D A 
D BCE 
R(ABCDEFG) 
R 1 (DBCE) 
R 2 (ADFG) 
R 3 (DA) 
R 4 (DFG) 
F, K R = DF 
{D BCE}, 
K R1 = D 
{D A, DF G }, 
K R2 = DF 
{D A}, 
K R3 = D 
{DF G}, 
K R4 = DF