Bài giảng Cơ sở dữ liệu - Bài 7: Phụ thuộc dữ liệu trong mô hình quan hệ - Vũ Văn Định

Bài 7. PHỤ THUỘC DỮ LIỆU TRONG 
MÔ HÌNH QUAN HỆ
I. Phụ thuộc hàm (Functional Dependencies : FD)
1. Định nghĩa :
Cho R(U) là một lược đồ quan hệ với U = { A1, .. 
,An} là tập thuộc tính. X và Y là tập con của U.
Nói rằng X Y (đọc là X xác định hàm Y hoặc Y 
phụ thuộc hàm vào X) nếu r là một quan hệ xác định
trên R (U) sao cho bất kỳ hai bộ t1, t2 r mà
t1[X]= t2[X] thì t1[Y] = t2[Y]
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
 Ví dụ : Trong quan hệ SV, mỗi thuộc tính
DIACHI, NS, KETQUA đều phụ thuộc hàm (pth ) vào
thuộc tính SV#. Mỗi giá trị SV# xác định duy nhất
một giá trị tương ứng đối với từng thuộc tính đó. Khi
đó , có thể viết :
SV# DIACHI 
SV# NS
SV# KETQUA
 Nếu Y X thì hiển nhiên X Y
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
2. Hệ tiên đề cho phụ thuộc hàm
2.1. K/n bao đóng của một tập phụ thuộc hàm
• Gọi F là tập tất cả các pth đối với lược đồ quan hệ
R(U) và X Y là một pth, X, Y  U.
• Nói rằng X Y được suy diễn logic từ F nếu mỗi
quan hệ r trên R( U) đều thoả các pth của F thì cũng
thoả X Y.
• Chẳng hạn F = { A B, B C} thì A C
• Tập tất cả các pth được suy diễn logic từ F được gọi
là bao đóng của F. Kí hiệu là F+. 
• Nếu F+ = F thì F là họ đầy đủ của các pth
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
2.2. Hệ tiên đề Amstrong
 Năm 1974, Amstrong đưa ra hệ luật dẫn
hay các tính chất của phụ thuộc hàm, gọi
là hệ tiên đề Amstrong:
 Cho X, Y, Z, W  U . Ta có các luật sau :
A1. Luật phản xạ :
Nếu Y  X thì X Y
A2. Luật bổ sung :
X Y thì XZ YZ
A3. Luật bắc cầu :
Nếu X Y và Y Z thì X Z
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
 Hệ tiên đề Amstrong được chứng minh
là đúng đắn và đầy đủ thông qua 3 bổ
đề sau:
 Bổ đề 1 : Hệ tiên đề Astrong là đúng. 
Có nghĩa là, với F là một tập các pth
đúng trên quan hệ r. Nếu X Y là một
pth được suy dẫn từ F nhờ hệ tiên đề
Amstrong thì X Y là đúng trên quan
hệ r
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
 Bổ đề 2: Từ hệ tiên đề Amstrong ta suy
ra một số luật sau đây:
a. Luật hợp : Nếu X Y và X Z thì
X YZ
b. Luật tách : Nếu X Y và Z  Y thì
X Z
c. Luật tựa bắc cầu :
Nếu X Y và WY Z thì XW Z
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
 Khái niệm bao đóng của tập các thuộc
tính đối với tập các phụ thuộc hàm.
Gọi F là tập các pth trên tập thuộc
tính U, X U . X + là bao đóng của X 
(đối với F ) được định nghĩa như sau :
X + = { A | X A F+ }
Nói cụ thể : X + là tập tất cả các
thuộc tính A mà pth X A có thể được
suy diễn logic từ F nhờ hệ tiên đề
Amstrong
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
 Bổ đề 3 : X Y suy dẫn từ hệ tiên đề
Amstrong khi và chỉ khi Y  X +
Như vậy : 
(1). X  X+
(2). f: X Y F+ Y  X+
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
2.3 Thuật toán tìm bao đóng của tập thuộc
tính
Thuật toán CLOSURE.
Input : Tập thuộc tính X và tập phụ thuộc hàm F
Output : Bao đóng X của F 
CLOSURE (X,F)
Begin olddep:= ; newdep:=olddep
While newdep olddep do 
Begin
olddep:= newdep
For each W Z F do 
if W  newdep then newdep:= newdep  Z
End 
Return ( newdep)
End.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
VD: Cho U = ABCDEG
F = {
AB C (f1)
D EG (f2)
C A (f3)
BE C (f4)
BC D (f5)
CG BD (f6)
ADC B (f7)
CE AG (f8)
}
Cho X= BD. Tính ( BD)+F
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Giải:
X(0): = BD
X(1): = BD  EG ( do (f2) )
X(2): = BDEG  C ( do (f4) )
X(3): = BDEGC  { A ( do (f2) ) 
C ( do (f4) ) 
D ( do ( f5) ) 
BD ( do (f6) ) 
AG ( do (f8))
}
X(4): = BDEGCA = U => X+F = X (4)
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
3. Tập phụ thuộc hàm tương đương
3.1 Định nghĩa
Hai tập pth F và G được gọi là
tương đương nếu F+ = G+. Khi đó ta
nói F phủ G ( hay G phủ F). Kí hiệu : 
F G
 Bổ đề 1: Mỗi tập các pth F đều được
phủ bằng tập các pth G mà vế phải
các pth đó bao gồm không quá một
thuộc tính.
 Bổ đề 2: F G F suy dẫn
được ra G và G suy dẫn được ra F
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Ví dụ : Cho quan hệ Q (ABCDE) với:
F = {A BC , A D,CD E }
G = {A BCE , A ABD, CD E}
* F suy dẫn được ra G vì :
A C, A D => A CD
CD E 
=> A BCE.
Tương tự, dễ dàng chứng minh : A ABD.
Vậy F suy dẫn được ra G.
* Ngược lại, ta nhận thấy F  G , do đó hiển nhiên
G suy dẫn được ra F.
Kết luận : F  G
A E
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
3.2 Phủ tối thiểu
Định nghĩa : Một tập phụ thuộc hàm F được
gọi là tối thiểu nếu : 
 Mỗi vế phải của một phụ thuộc hàm F chỉ có
một thuộc tính.
 F gồm toàn những pth đầy đủ, nghĩa là
không tồn tại một phụ thuộc hàm X A 
thuộc F và một tập con Z của X mà :
F+ = ( F - { X A }  { Z A}) +
 Không tồn tại một phụ thuộc hàm X A 
thuộc F mà : 
F+ = ( F - { X A }) +
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
3.3 Thuật toán MINIMALCOVER tìm phủ tối
thiểu của tập phụ thuộc hàm F
Input: Tập phụ thuộc hàm F 
Output : G- là phủ tối thiểu của F
MINIMALCOVER (G, F)
G:=F
Thay thế từng phụ thuộc hàm X { A1, A2,..,An} trong
G bằng các phụ thuộc hàm X A1, X A2, .., X 
An
For each X A trong G 
For each B X 
If ( G - { X A })  ( X- {B}) A) tương
đương với G Then 
Thay X A bằng ( X- { B}) A trong G 
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
For each X A trong G
If ( G - { X A }) tương đương
với G Then 
Loại X A ra khỏi G
Return (G)
End.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Ví dụ 1: Cho F = { A B , B A, B C, 
A C, C A}. Tìm phủ tối thiểu G của F
Giải : Tất cả các pth của F đều thoả mãn
điều kiện 1 vì vế trái chỉ có một thuộc tính.
Vế phải của mỗi pth chỉ có một thuộc tính
nên không cần xét đk2.
Xét đk 3, ta thấy : Nếu koại bỏ pth B A 
và A C ta được một tập pth G
G={A B , B C, A C }  F
Không thể loại bỏ thêm một pth nào nữa
vì tập pth còn lại sẽ không tương đương với
F. Vậy G là tập pth tối thiểu của F.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Ví dụ 2: Cho F = { AB C, A B, B A}.
Tìm phủ tối thiểu G của F
Giải : Tất cả các pth của F đều thoả mãn
điều kiện 1 vì vế trái chỉ có một thuộc tính.
Xét đk2: ta thấy pth là không đầy đủ vì
: (F- {AB C} {A C})  F
Vậy loại bỏ pth AB C và thay bằng pth
A C ta được tập pth G:
G={A C , A B, B A }  F
Nhận thấy, không thể loại bỏ thêm một pth
nào nữa vì tập pth còn lại sẽ không tương
đương với F. Vậy G là tập pth tối thiểu của F.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
4. Bài toán tìm khoá của quan hệ
4.1 Thuật toán tìm khoá dựa trên đồ thị
Định nghĩa khoá được viết lại bằng pth.
Cho Q là lược đồ quan hệ định
nghĩa trên tập các thuộc tính U = { 
A1, A2, .. , An} với tập các pth F= { 
f1, f2, .. ,fn} xác định trên Q. K  U 
là khoá của R nếu thoả mãn hai điều
kiện sau :
(1): K U
(2):  K'  K mà K' U 
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Biểu diễn lược đồ quan hệ Q(U) 
bằng đồ thị có hướng như sau:
- Mỗi nút của đồ thị là tên của một thuộc tính
thuộc Q
- Cung nối hai thuộc tính A và B thể hiện cho
pth A B 
- Thuộc tính chỉ có các mũi tên đi ra, tức là
chỉ ở vế trái của pth gọi là nút gốc
- Thuộc tính mà chỉ có mũi tên đi vào, tức là
chỉ nằm ở vế phải của pth gọi là nút lá.
- Khoá của lược đồ quan hệ phải bao phủ tập
nút gốc và không được chứa bất cứ nút lá
nào của đồ thị
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Thuật toán tìm khoá:
-B1: Vẽ đồ thị của lược đồ quan hệ
-B2: Xác định tập các nút gốc ( G) và tập các nút lá ( 
L)
-B3: Xuất phát từ tập các nút gốc(G), đặt K bằng G ( 
khởi đầu ta đặt khoá là tập các nút gốc)
-B4: Dựa trên tập các pth F, tìm bao đóng của tập K 
( tìm K+F)
+ Nếu K+F = U thì K chính là khoá . Dừng lại.
+ Ngược lại thì bổ sung một thuộc tính không thuộc
tập nút lá (L) vào K. Khi đó K = K+1 nút không
thuộc tập L.
Trở lại B4.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
4.2 Thuật toán tìm khoá dựa trên bao
đóng của tập thuộc tính
* Ý tưởng : Bắt đầu từ tập R vì R+ = R. Ta bớt dần
các phần tử của R để nhận được tập bé nhất mà
bao đóng của nó vẫn bằng R.
Vào : r(R), F
Ra : K ( Khoá )
B1: gán K = R 
B2: Lặp lại các bước sau :
Loại khỏi K phần tử A mà ( K \A)+ =R
Nhận xét: Thuật toán trên chỉ tìm được một khoá
trong sơ đồ quan hệ. Nếu cần tìm nhiều khoá, ta
thay đổi trật tự loại bỏ các phần tử của K.
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
Ví dụ : Cho R = { ABCDEGHI}
F = { AC B , BI ACD, ABC D, H I, ACE 
 BCG, CG AE}. 
Tìm khoá K ?
Giải : 
B1: Gán K= R = { ABCDEGHI}
B2: Lần lượt loại bỏ các phần tử khỏi K.
-Loại phần tử A : ta có : {BCDEGHI}+ = R vì pth CG 
 AE nên A thuộc về {BCDEGHI}+ nên K 
={BCDEGHI}
-Loại phần tử B : ta có : {CDEGHI}+ = R vì pth CG 
 AE khiến A thuộc về {CDEGHI}+ và pth AC B 
khiến B thuộc về {CDEGHI}+ nên K ={CDEGHI}
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí
-Loại phần tử C : ta có : {DEGHI}+ R nên K vẫn là
{CDEGHI}
-Loại phần tử D : ta có : {CEGHI}+ = R 
vì CG AE, AC B, ABC D nên D có trong
{CEGHI}+ . Nên K ={CEGHI}
-Loại phần tử E : ta có : {CGHI}+ = R 
vì CG AE khiến E thuộc về {CGHI}+ nên K 
={CGHI}
-Loại phần tử H : ta có : {CGI}+ R nên K vẫn là
{CGHI}
-Loại phần tử I : ta có : {CGH}+ = R 
vì H I, khiến I thuộc về {CGH}+ nên K 
={CGH}
Kết luận : K= { CGH } là một khoá của r (R)
TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí