1
Phu
Phu
̣
̣
thu
thu
ộ
ộ
c
c
hà
hà
m
m
 Phụ thuộchàm
 Suy dẫntừ phụ thuộchàm
 Luậtdẫn
 Bao đóng
4/17/2008
Ôn thi cao học 2008
2
Phu
Phu
̣
̣
thu
thu
ộ
ộ
c

{ A ≠ ∅, B ≠∅
{ Mộtthể hiệnr củaR thỏaPTH A→B nếu
⇒
∀
t1, t2
∈
r,
=
t1[A] t2[A]
=
t1[B] t2[B]
Mỗigiá trị tạiA xácđịnh duy nhấtmộtgiá trị tạiB
4/17/2008
Ôn thi cao học 2008
4
Ví
Ví
du
du
̣
̣
 Xét lược đồ quan hệ
 Và thể hiện
Phim(Tênphim, Nămsx, Thờilượng, Loạiphim, Xưởngsx, Diễnviên)
Tênphim Nămsx Thờilượng Loạiphim Xưởngsx Diễnviên
Star Wars 1977 124 color Fox Carrie Fisher
Star Wars 1977 124 color Fox Mark Hamill
Star Wars 1977 124 color Fox Harrison Ford
Mighty Ducks 1991 104 color Disney Emilio Esteves
Wayne’s World 1992 95 color Paramount Dana Carvey

Thỏavớimọithể hiệncủaquanhệ
4/17/2008
Ôn thi cao học 2008
6
PTH
PTH
hi
hi
ể
ể
n
n
nhiên
nhiên
(trivial functional dependency)
(trivial functional dependency)
⇔
X → Y là PTH hiển nhiên
⊆
Y X
 Ví dụ :
{ AB → A, AB → B là các PTH hiển nhiên
 Chỉ quan tâm đến các PTH không hiển nhiên (non trivial FD)
4
4/17/2008
Ôn thi cao học 2008
7
Suy
Suy
dẫn

a
F
F
 Tậphợp các PTH hệ quả từ F đượcgọi là bao đóng củaF
{ Ký hiệuF
+
 Để xác định F
+
từ tậpPTH F chotrước, cầnxácđịnh tấtcả các PTH có
thể suy dẫn đượctừ F
{ Cầnsử dụng các luậtsuydẫn (Amstrong)
 Chi phí tính F
+
là rấtlớn
F ⊆ F
+
5
4/17/2008
Ôn thi cao học 2008
9
Lu
Lu
ậ
ậ
t
t
d
d
ẫ
ẫ

d
ẫ
ẫ
n
n
khá
khá
c
c
 Luậtbắccầugiả
 Luậthội
 Luật phân rã
(FD4)
(FD5)
(FD6)
NếuX → Y và Y, W → Z
Thì X, W → Z
NếuX → Y và X → Z
Thì X → Y, Z
NếuX → Y và Z
⊆
Y
Thì X → Z
6
4/17/2008
Ôn thi cao học 2008
11
Ví
Ví
du

a
F
F
+
+
F
+
= F
repeat
for each PTH f ⊆ F
+
Áp dụng các luậtdẫn Amstrong để tìm ra tậpPTH suydẫn {f’}
F
+ =
F
+
∪{f’}
until F
+
không tăng trưởng nữa
7
4/17/2008
Ôn thi cao học 2008
13
Ví
Ví
dụ
dụ
 Xét lược đồ R(A, B, C, G, H, I)
 Và PTH F định nghĩatrênR

Nh
Nh
ậ
ậ
n
n
xé
xé
t
t
 Bài toán thựctế
{ Cho mộtPTH f: X → Y
{ Xác định f có thuộcbaođóng F
+
hay không
 Giảiquyết
{ Tìm bao đóng F
+
{ Kiểm tra f có nằm trong F
+
không
 Tìm bao đóng F
+
có hiệu quả ???
 Chuyển sang bài toán thành viên
{ Ta chỉ cần tìm bao đóng củatậpthuộctínhX dựatrênF
{ Kiểmtra Y có thuộcbaođóng của X hay không
4/17/2008
Ôn thi cao học 2008
16

 Ký hiệuX
+
F

Định nghĩa
 Ta thấy
X
+
F
=
{ Y | X → Y đượcsuydẫntừ F }
Là tậphợpnhững VP của các PTH có VT là X nằmtrongF
X ⊆ X
+
F
X ⊆ R
+
X
+
F
dùng để xem f có đượcsuydẫntừ F hay không?
9
4/17/2008
Ôn thi cao học 2008
17
Tì
Tì
m
m
bao

∪ V
} cho đếnkhi (X
+
F
= R
+
) hoặc
(không còn thay đổi đượcnữa)
Tìm các PTH trong F
có VT là các thuộctínhnằmtrongX
+
F

có VP không nằmtrongX
+
F
4/17/2008
Ôn thi cao học 2008
18
Ví
Ví
du
du
̣
̣
 R(A, B, C, D, E, F)
 F = { AB→C, BC→AD, D→E, CF→B }
 Tìm AB
+
F

 F = { AB→C, BC→AD, D→E, CF→B }
 Kiểm tra PTH AB→D có suy dẫntừ F không?
 AB
+
F
= {A, B, C, D, E}
 Có D trong bao đóng
 KếtluậnAB→D suy dẫntừ F
4/17/2008
Ôn thi cao học 2008
20
Ví
Ví
du
du
̣
̣
(
(
tt
tt
)
)
 R(A, B, C, D, E, F)
 F = { AB→C, BC→AD, D→E, CF→B }
 KiểmtraPTH D→A có suy dẫntừ F không?
 D
+
F
= {D, E}

4/17/2008
Ôn thi cao học 2008
22
Phủ
Phủ
 Cho F là tập các PTH định nghĩatrênR
 Xét mộttậpPTH G định nghĩatrênR
G là phủ nếuG ≡ F
tương đương
12
4/17/2008
Ôn thi cao học 2008
23
PTH
PTH
đ
đ
ầ
ầ
y
y
đ
đ
u
u
̉
̉
và
và
PTH

25
Ví
Ví
du
du
̣
̣
 R(A, B, C, D)
 F = { A→B, B→A, B→C, A→C, C→A }
 PTT(F) ?
 MọiVP đềucó1 thuộc tính
 Các PTH đều đầy đủ
 Có thể bỏ phụ thuộchàmthừanào?
4/17/2008
Ôn thi cao học 2008
26
Ví
Ví
du
du
̣
̣
(
(
tt
tt
)
)
 Xét A→B
{ A

 F’ ≡ F nên F’=PTT(F)
{ Chỉ cầnxétF đượcsuydẫntừ F’
 NếubỏđiB→C
 F” = { A→B, B→A, A→C, C→A}
 F” ≡ F nên F”=PTT(F)
F’ ≡ F”
4/17/2008
Ôn thi cao học 2008
28
Ví
Ví
du
du
̣
̣
 R(A, B, C)
 F = { AB→C, A→B, B→C }
 PTT(F) ?
 MọiVP đềucó1 thuộc tính
 Có AB→C không là PTH đầy đủ
{ Thay thế bằng các PTH đầy đủ
 Có thể bỏ phụ thuộchàmthừanào?
15
4/17/2008
Ôn thi cao học 2008
29
Ví
Ví
du
du

Ôn thi cao học 2008
31
Ví
Ví
dụ
dụ
 R(A, B, C, D, E)
 F = { f1: A→BC
f2: B→A
f3: AD→E
f4: BD→E
}
 Xem hình trang 16
4/17/2008
Ôn thi cao học 2008
32
Tìm
Tìm
khóa
khóa
 Tìm thuộc tính đích
{ Không xuấthiện trong các khóa
 Tìm thuộc tính nguồn
{ Sẽ xuấthiện trong các khóa
 Tìm các nút thuộc tính còn lại
{ Sao cho tổ hợpcủa chúng + nguồnsuyrađượcnhững thuộc tính còn lại
17
4/17/2008
Ôn thi cao học 2008
33

35
Tính
Tính
chất
chất
của
của
PTH
PTH
 Tính phảnchiếu
 R(AB) và f: A→B
 R’(ABC) thì ta cũng có f’: A→B
Cho R và f: X → Y
Lấy R’(V), W ⊆ V
R’ cũng có f’: X → Y
4/17/2008
Ôn thi cao học 2008
36
Ví
Ví
dụ
dụ
 R(A, B, C, D, E)
 F = { f1: A→BC
f2: B→A
f3: AD→E
f4: BD→E
}
 R’(ABC)
 F’ = ?

luôn
phim
20
4/17/2008
Ôn thi cao học 2008
39
Giới
Giới
thiệu
thiệu
(
(
tt
tt
)
)
 Tìm cách tách quan hệ
Tênphim Nămsx Thờilượng Loạiphim Xưởngsx
Star Wars 1977 124 color Fox
Mighty Ducks 1991 104 color Disney
Wayne’s World 1992 95 color Paramount
Diễnviên
Carrie Fisher
Mark Hamill
Harrison Ford
Emilio Esteves
Dana Carvey
Mike Meyers
Tênphim Nămsx
Star Wars 1977

Ví
dụ
dụ
 Xét quan hệ DSLớp
TênlớpSỉsố
Tênhs1
Điểm11
…
11A2 30 N V A 7 …
12A1 28 V V B 10 …
Điểm21
8
6
Điểm15
8
6
Tênhs2
T T C
P V D
…
…
…
Điểm25
8
6
…
…
…
5 lần
30 lần

1/11/05
ngàyTrả
31/8/04
1/9/05
10/6/03
1/12/04
10/8/06
Giá
350
450
350
375
450
chủID
CO40
CO93
Co40
CO93
Co93
chủTên
X
Y
X
Y
Y
 Xét quan hệ Khách_Thuê_Phòng
Không chuẩn
(giá trị tại1 trường không nguyên tố)
22
4/17/2008

8
6
Tênhs2
T T C
P V D
…
…
…
Điểm25
8
6
…
…
…
TênlớpSỉsố
Tênhs
11A2 30 N V A
11A2 30 T T C
12A1 28 V V B
12A1 28 P V D
Tênlớp
11A2
11A2
Tênhs
N V A
T T C
12A1 V V C
12A1 P V D
Môn
Văn

1NF
1NF
 Tách quan hệ
1NF
1NF
24
4/17/2008
Ôn thi cao học 2008
47
Nhận
Nhận
xét
xét
-
-
1NF
1NF
 Vẫn còn trùng lắp thông tin
Thuê_Phòng
kháchID phòngID
PG04
PG16
CR56 PG04
CR56 PG36
CR56 PG16
phòngĐChỉ
6 NVC Q5
5 NT Q10
6 NVC Q5
2 NTMK Q3

Y
CR76
CR76
4/17/2008
Ôn thi cao học 2008
48
1NF
1NF
→
→
2NF
2NF
 Lượcbỏ những PTH không đầy đủ
 Quan hệđạt2NF
{ Đạt1NF
{ Các thuộc tính không khóa phụ thuộc đầy đủ vào thuộc tính khóa
25
4/17/2008
Ôn thi cao học 2008
49
1NF
1NF
→
→
2NF
2NF
 Xét quan hệ Thuê_Phòng
{ Khóa: kháchID, phòngID
{ Còncó1 PTH
{ Làm xuấthiện PTH không đầy đủ vào khóa

X
Y
Y
Phòng
kháchID phòngID
PG04
PG16
CR56 PG04
CR56 PG36
CR56 PG16
ngàyThuê
1/6/03
1/9/04
1/9/02
10/10/03
1/11/05
ngàyTrả
31/8/04
1/9/05
10/6/03
1/12/04
10/8/06
CR76
CR76
Thuê