1
PHÂN TÍCH THIẾT KẾ THỐNG THÔNG TIN
LÝ THUYẾT CHUẨN HÓA DỮ LIỆU
Chương 7
Phụ thuộc hàm.
Bao đóng.
Khóa của lược đồ quan hệ.
Phủ tối thiểu.
Dạng chuẩn.
Chuẩn hóa cơ sở dữ liệu.
Phép tách lược đồ quan hệ.
Bài tập
Nội dung
Xt hóa đơn bn hng như sau
2
Số HD NgyHD TênKH TênNV TênHH
SL
DG TT
001
01/02/19
Nuy
nNgc
Nga
Tr
nThLan
Coca
2
8.000
16.000
001
01/02/19
Nuy
nNgc
Nga
Tr
nThLan
Pepsi
1
7.000
7.000
001
01/02/19
Nuy
nNgc
Nga
Tr
nThLan
Ken
3
15.000
45.000
002
01/02/19
Nguy
nThAn
Linh
G
o 1
20.000
20.000
002
01/02/19
Nguy
nThAn
Linh
Đư
ng 2
21.000
42.000
003
01/02/19
Nguy
nThAn
Linh
S
a 1
25.000
25.000
V dụ
Nu thêm một hóa đơn mi ???
Nu thêm một kt quả thi của sinh viên mi ???
7.1 Phụ thuộc hm (functional dependence-FD)
Định nghĩa:
Phụ thuộc hàm là ràng buộc gia 2 tập thuộc tính của 01 lược
đồ quan hệ
R(A1, A2,…, An) là lược đồ quan hệ.
X, Y là hai tập con của tập thuộc tính ={A1, A2,…, An}.
Ta nói Y phụ thuộc hàm vào X: X →Y
Với mỗi giá trị tại X trong R xác định duy nhất một giá trị của Y trong R
7.1 Phụ thuộc hm (functional dependence-FD)
Một thể hiện của R thỏa phụ thuộc hàm X Ynếu
t1, t2 R
t1.X = t2.X t1.Y = t2.Y
Nếu t1.X = t2.X t1.Y t2.Y thì lược đồ vi phm phụ thuộc
hàm XY
3
MONHOC →DIEMTHI ???
HOTEN →DIEMTHI ???
MASV →DIEMTHI ???
Ví dụ ABCDE
1 2 3 4 5
1 4 3 4 5
1 2 4 4 1
Kí hiệu nào là phụ thuộc hàm
I. AB →C
II. B→D
III. DE →A
(T)
(T)
sai
Phụ thuộc hàm hiển nhiên
Nu X Y thì X →Y.
Vi r l quan hệ bất kỳ, F l tập phụ thuộc hàm
thỏa trên r, ta luôn có
F {cc phụ thuộc hm hiển nhiên}
7.2 Hệ luật dẫn Armstrong
Phụ thuộc hàm được suy din logic từ F
Phụ thuộc hàm X Yđược suy din logic từ Fnếu một quan hệ r
bất kỳ thỏa mãn tất cả các phụ thuộc hàm của Fthì cũng thỏa phụ
thuộc hàm XY
.
Ký hiệu F|= X Y.
Bao đóng của F
Bao đóng của F là tập tất cảcác phụ thuộchàm
được suy din logic từ F.
Ký hiệu: F+
Nếu F=F+ thì F là họ đầy đủ của các PTH
4
Thuật toán tìm bao đóng F+
“Áp dụng hệ tiên đề Armstrong cho đn khi
không tìm ra thêm phụ thuộc hm mi”
Các tính chất của tập F+
Tnh phản xạ: F F+
Tính đơn điệu: Nu F G thì F+ G+
Tính lũy đẳng: (F+)+ = F+.
Phần phụ của F: F-= G - F+
(G -tập tất cả cc PTH có thể có của r)
7.2 Hệ luật dẫn Armstrong
7.2 Hệ luật dẫn Armstrong
Hệ luật dẫn Amstrong: Gọi R()là lược đồ quan hệ
vi ={A1, A2,…, An}là tập thuộc tính và X,Y,Z,W là
tập con của .(Kí hiệu:XY=XY)
Ba luật của tiên đề Amstrong:
1. Luật phản xạ (reflexive rule):
Nu YXthì XY
2. Luật tăng trưởng (augmentation rule):
Nu X Y, Zthì XZ YZ
3. Luật bắc cầu (Transivity Rule)
Nu X Y và Y Z thì X Z
Giả sử quan hệ r thoả mãn X Y.
Tồn ti hai bộ t, u r sao cho t[XZ] = u[XZ] mà t[YZ] u[YZ]
Vì t[Z] = u[Z] nên để có t[YZ] u[YZ] thì t[Y] u[Y] (1)
Mà ta có t[XZ] = u[XZ] nên t[X] = u[X] (2)
Từ (1) và (2) ta có t[X] = u[X] và t[Y] u[Y] điều này là trái với
giả thiết quan hệ r thoả mãn X Y.
Vậy t[YZ] = u[YZ] hay XZ YZ là đúng trên quan hệ r.
CM: Tiên đề tăng trưởng
5
7.2 Hệ luật dẫn Armstrong
Ba hệ quả của tiên đề Amstrong:
1. Luật hợp (Union Rule)
Nu X Y và X Z thì X YZ
2. Luật bắc cầu giả (Pseudotransivity Rule)
Nu X Y và WY Z thì XW Z
3. Luật phân rã (Decomposition Rule)
Nu X Y và Z Y thì X Z
Đnh nghĩa
Gi F là tập các phụ thuộc hàm trên tập thuộc tính
Bao đóng của F là tất cả các phụ thuộc hàm có thể
suy ra từ F dựa trên các tiên đề Armstrong
7.3 Bao đóng của tập thuộc tính X
(closures of attribute sets)
Thuật toán tìm bao đóng:
Tính liên tiếp tập các tập thuộc tính X0,X1,X2,... theo phương
pháp sau:
Bước 1: X0 = X
Bước 2: ln lượt xét các phụ thuộc hàm của F
Nếu YZ có Y Xi thì Xi+1 = XiZ
Loi phụ thuộc hàm Y Z khỏi F
Bước 3: Nếu ở bước 2 không tính được Xi+1 thì Xi chính là
bao đóng của X
Ngược li lặp li bước 2.
7.3 Bao đóng của tập thuộc tính X
(closures of attribute sets)
Ví dụ 1: Cho lược đồ quan hệ R(A,B,C,D,E,G,H) và
tập phụ thuộc hàm
F={BA; DACE; DH; GHC; ACD}.
Tìm bao đóng của X = {A,C} trên F? bao đóng
Giải: X(0) = {A,C} , {A,C}{D}
X(1) = {A,C,D}, {A, D}{C,E}
X(2) = {A,C,D,E}, {D}{H}
X(3) = {A,C,D,E,H}
X+= X(3)
Cho X = {B, D} ->X+?
7.3 Bao đóng của tập thuộc tính X
(closures of attribute sets)