1
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
CƠ SỞ LÝ THUYẾT
PHỤ THUỘC HÀM VÀ PHỦ CỰC TIỂU
Cơ sở dữ liệu nâng cao
GV hướng dẫn: TS. Hoàng Quang
2
Nhóm thực hiện:
1. Lê Bá Minh Phong
2. Nguyễn Thị Thanh Tâm
3. Trần Thị Thành
4. Trần Như Đăng Tuyên
5. Nguyễn Vũ Cát Tường
3
1. Qui ước về các ký hiệu
2. Phụ thuộc hàm (Functional Dependency)
3. Hệ tiên đề Amstrong
4. Bao đóng của tập thuộc tính (X
+
)
5. Thuật toán (thuật toán tính bao đóng của X).
Phần I: Cơ sở lý thuyết phụ thuộc hàm
Phần II: Phủ cực tiểu (Phủ tối thiểu)
1. Tập phụ thuộc hàm tương đương
2. Phủ cực tiểu của một lược đồ quan hệ
3. Phủ cực tiểu của tập phụ thuộc hàm
4. Thuật toán (tìm một phủ tối thiểu của F).
Nội dung
4
5

1
, t
2
∈ r sao cho:
t
1
[X] = t
2
[X] ⇒ t
1
[Y] = t
2
[Y]
Do đó, r không thoả X→Y
⇔ ∃ t
1
,t
2
∈ r : t
1
[X] = t
2
[X] và t
1
[Y] ≠ t
2
[Y]
2. Phụ thuộc hàm (Functional Dependency)
Phần I: CƠ SỞ LÝ THUYẾT PHỤ THUỘC HÀM


r thỏa?
* Thuật toán: Kiểm tra quan hệ r = {t
1
, t
2
, …, t
n
} có thoả
mãn phụ thuộc hàm X → Y không?
Function Ktra(r, X, Y);
Begin
temp := true ;
for i := 1 to n-1 do
for j := i+1 to n do
if (t
i
[X]= t
j
[X] and t
i
[Y]< > t
j
[Y]) then
begin
temp:= false;
break;
end;
Ktra:= temp;
End;
2. Phụ thuộc hàm (Functional Dependency)

X→Y được suy ra từ F, thì ký hiệu: F╞ X→Y, hay ta
nói rằng X→Y là phụ thuộc hàm hệ quả của F.
2. Phụ thuộc hàm (Functional Dependency)
10
Phần I: CƠ SỞ LÝ THUYẾT PHỤ THUỘC HÀM
Định nghĩa: (Bao đóng của tập phụ thuộc hàm)
Cho R = <U, F>. Khi đó: bao đóng của F, ký hiệu là F
+
, là tập
tất cả các phụ thuộc hàm của R, kể cả hệ quả của F. Tức là:
F
+
= {X→Y | X, Y ⊆ U và R thoả X→Y}
Ví dụ: Cho R = <ABC, {A → B, B → C}>
Ta có:
F
+
= {A → B, B → C, A → C, AB → C, A → A, }
2. Phụ thuộc hàm (Functional Dependency)
11
Phần I: CƠ SỞ LÝ THUYẾT PHỤ THUỘC HÀM
* Lưu ý:

F ⊆ F
+


R = <U, F> thoả X → Y có thể ký hiệu: F |= X → Y
(đọc là: F suy dẫn X xác định Y hay X xác định Y là phụ
thuộc hàm hệ quả của F).

Khoá của một lược đồ quan hệ là không duy nhất.

Một lược đồ quan hệ luôn tồn tại khoá.
14
Phần I: CƠ SỞ LÝ THUYẾT PHỤ THUỘC HÀM
Cho R = <U, F>, Amstrong đã đưa ra ba qui tắc (tiên đề, luật) sau:
- Luật phản xạ:
Nếu X, Y ⊆ U và X ⊆ Y thì Y→X ∈ F
+
- Luật gia tăng (tăng trưởng):
Nếu X, Y, Z ⊆ U và X→Y ∈ F
+
thì XZ→YZ ∈ F
+

- Luật bắc cầu:
Nếu X, Y, Z ⊆ U và X→Y ∈ F
+
, Y→Z ∈ F
+
thì X→Z ∈ F
+
3. Hệ tiên đề Amstrong
15
Phần I: CƠ SỞ LÝ THUYẾT PHỤ THUỘC HÀM
Định lý:
Hệ tiên đề Amstrong là đúng đắn và đầy đủ.

Tính đúng đắn.


* Lưu ý:

Để chỉ rõ bao đóng của X được xác định trên tập phụ thuộc
hàm F, ta ký hiệu: X
+
F
.

X là siêu khoá ⇔ X → U ∈ F
+
⇔ X
+
= U.

X ⊆ X
+
.
4. Bao đóng của tập thuộc tính (X
+
)
Phần I: CƠ SỞ LÝ THUYẾT PHỤ THUỘC HÀM
18
4. Bao đóng của tập thuộc tính (X
+
)
Định lý:
(Bài toán thành viên: điều kiện cần và đủ để X
→
Y
∈

If X’ ⊆ OLD then
NEW:=NEW ∪ Y’;
Until (NEW = OLD);
Return NEW;
End;
20
Phần I: CƠ SỞ LÝ THUYẾT PHỤ THUỘC HÀM
Ví dụ:
Cho R = <U, F>, trong đó:
U = ABCDEG
F = {AB→C, C→A, BC→D, D→EG,
BE→C, CG→BD, CE→AG}
Tính (BD)
+
:
X
(0)
= BD
X
(1)
= BD ∪ {EG} = BDEG
X
(2)
= BDEG ∪ {C} = BDEGC
X
(3)
= BDDEGC ∪ {A, AG} = BDEGCA
X
(4)
= BDEGCA = X


Ra: Yes/No
Function Khoa(X,U,F):Boolean;
Begin
If X
+
<> U then
Return False
else
For each A ∈ X do
If (X − A)
+
= U then
Return False;
Return True;
End;
23
Phần I: CƠ SỞ LÝ THUYẾT PHỤ THUỘC HÀM
24
Định nghĩa:
Cho 2 tập phụ thuộc hàm F và G. Khi đó: F được gọi là tương
đương với G, ký hiệu: F ⇔ G, nếu và chỉ nếu F
+
= G
+
* Ví dụ:
Cho F = {A→B, B→C}
G = {A→B, B→C, A→C}
⇒ F ⇔ G
* Ý nghĩa: