Bài giảng Cơ sở dữ liệu: Chương 5

CHƯƠNG 5

PHỤ THUỘC HÀM Functional dependency

NỘI DUNG

• PHỤ THUỘC HÀM • BÀI TOÁN TÌM PHỦ TỐI THIỂU • BÀI TOÁN TÌM KHÓA

(cid:1)(cid:1)(cid:1)(cid:1)Pth là m(cid:7)t công c(cid:12) bi(cid:15)u di(cid:18)n m(cid:7)t cách hình th(cid:21)c m(cid:7)t d(cid:22)ng ràng bu(cid:7)c tòan v(cid:27)n (cid:1)(cid:1)(cid:1)(cid:1) Pth ñ(cid:29)(cid:30)c (cid:21)ng d(cid:12)ng trong vi c gi!i quy$t bài tóan tìm khóa, tìm ph* t+i thi(cid:15)u và chu,n hóa c- s/ d0 li u

PHỤ THUỘC HÀM

• Khái niệm phụ thuộc hàm • Bao ñóng của một tập phụ thuộc hàm F • Bộ luật dẫn AMSTRONG • Bao ñóng của tập thuộc tính X • Thuật toán tìm F+

1. KHÁI NIỆM

phanCong

(PHICONG,

MAYBAY,

NGAYKH,

GIOKH)

Cushing

9/8

10:15a

Cushing

116

10/8

1:25p

Clark

281

8/8

5:50a

Clark

301

12/8

6:35p

Clark

11/8

10:15a

Chin

13/8

10:15a

Chin

116

12/8

1:25p

Copely

281

9/8

5:50a

Copely

281

13/8

5:50a

Copely

412

15/8

1:25p 4

Xét ví dụ (sgk) : Cho quan hệ Phân công

Trong thế giới thực luôn có những qui tắc hoạt ñộng : - Mỗi máy bay có một giờ khởi hành duy nhất - Nếu biết phi công, Ngày và giờ khởi hành thì biết ñược máy bay do phi công này lái - Nếu biết máy bay, ngày khởi hành thì biết phi công lái chuyến bay ñó

Những qui tắc hoạt ñộng trên là một loại ràng buộc , ñược gọi là phụ thuộc hàm , và có thể phát biểu lại như sau :

MAYBAY xác ñịnh GIOKH GIOKH phụ thuộc hàm vào MAYBAY

Hay ðược ký hiệu

f1: f2: f3: {MAYBAY}→→→→ GIOKH {PHICONG,NGAYKH,GIOKH}→→→→ MAYBAY {MAYBAY,NGAYKH}→→→→ PHICONG

(cid:2)(cid:2)(cid:2)(cid:2) ðịnh nghĩa phụ thuộc hàm

X →→→→Y ⇔⇔⇔⇔ ( t1.X = t2.X ⇒⇒⇒⇒ t1.Y= t2.Y )

Cho lược ñồ quan hệ Q(A1,A2,…,An) X, Y là hai tập con của Q+ = {A1,A2,…,An} r là quan hệ trên Q t1, t2 là hai bộ bất kỳ trên r

- N$u ∃∃∃∃ t1,t2 ∈∈∈∈r , sao cho t1.X = t2.X và t1.Y ≠ t2.Y pth X →→→→Y không th=a trên r ta nói :

- N$u v?i m@i quan h r ñAu th=a mãn pth X →→→→Y , ta nói pth X →→→→Y ñ(cid:29)(cid:30)c ñCnh nghĩa trên l(cid:29)(cid:30)c ñE quan h Q

Phụ thuộc hàm nào sau ñây thỏa

r (A , B , C , D , E)

A →→→→D , AB→→→→D

AB→→→→C

a1 a1 a2 a2 a3

b1 b2 b1 b1 b2

c1 c2 c3 c4 c5

d1 d1 d3 d3 d1

e1 d1 e1 e1 e1

Phụ thuộc hàm nào sau ñây thỏa q

BC→→→→E , DE→→→→C , A →→→→ BCDE

a1 a2 a3 a4 a5

b1 b2 b1 b2 b1

c1 c2 c1 c2 c1

d1 d2 d1 d2 d3

e1 e2 e1 e2 e1

2.2. Phụ thuộc hàm ñược suy diễn logic từ F Bao ñóng của một tập phụ thuộc hàm F

⇒⇒⇒⇒⇒⇒⇒⇒

1. MB →→→→→→→→ G G 1. MB 2. MB,N →→→→→→→→ PCPC 2. MB,N 3. PC,N,G →→→→→→→→ MBMB 3. PC,N,G

4. MB,N →→→→→→→→ G G 4. MB,N 5. MB,N,G →→→→→→→→ PCPC 5. MB,N,G 6. PC, N, G →→→→→→→→ PCPC 6. PC, N, G …

VVíí duduïï: : phanCong(PC phanCong(PC, MB, N, G) , F ={(1),(2),(3)} , MB, N, G) , F ={(1),(2),(3)}

FF++ FF

ÑÑònhònh nghnghóóaa: : Phụ thuộc hàm X →→→→ Y ñược suy diễn logic từ F nếu một lược ñồ quan hệ Q thỏa mãn tất cả các phụ thuộc hàm của F thì cũng thỏa phụ thuộc hàm X →→→→ Y.

Ký hiệu F |= X →→→→ Y ((GGọọii F |= X →→→→ Y là phphụụ thuthuộộcc hhààmm hhệệ ququảả))

(1) thothoûûaa maõnmaõn ththìì (4) (4) cuõng cuõng ñöñöôôïïcc thothoûûaa maõnmaõn ⇒⇒⇒⇒⇒⇒⇒⇒ chchææ

NX : NX : NeNeááuu (1) cacaàànn kiekieååmm tratra (1)(1)

(cid:3)(cid:3) BaoBao ññooùùngng FF++ cucuûûaa FF : : llàà ttậậpp ttấấtt ccảả ccáácc phphụụ thuthuộộcc hhààmm ñưñượợcc suysuy

(cid:3)(cid:3) LuaLuaäätt daãndaãn ññeeåå suysuy rara phuphuïï thuo

didiễễnn logic logic ttừừ FF

thuoääcc hahaøømm heheää quaquaûû ttöøöø F :F : thuoääcc hahaøømm suysuy ttöøöø FF qua qua lualuaäätt daãndaãn ((kykyùù hiehieääuu F F   ff’’ ) ) neneááuu

j=1,……,i,i--1)1) ff’’ lalaøø phuphuïï thuo ∃∃ ff11, f, f22,,……, f, fnn saosao chocho ffnn=f=f’’ vavaøø ((ffii ∈∈ FF) ) ∨∨ ((ffii ñöñöôôïïcc suysuy dieãndieãn ttöøöø ffjj vôvôùùii j=1,

KyKyùù hiehieääuu F F ’’={f={f’’ | | FF  ff’’} } ⇒⇒ cacaàànn ttììmm lualuaäätt daãndaãn saosao chocho F F ’’= = FF++ ; ; nghnghóóaa lalaøø ∀∀f, f, FF== f f ⇒⇒ FF f f vavaøø FF f f ⇒⇒ FF == f f

3. Bộ Luật Dẫn AMSTRONG (Hệ tiên ñề Amstrong)

Cho quan hệ Q(Q+) . X,Y,Z,W là các tập thuộc tính của Q+ Hệ tiên ñề Amstrong gồm các luật sau (F1) LuIt ph!n x(cid:22) (reflexive rule): N$u Y ⊆⊆⊆⊆X thì X →→→→Y

(F2) LuIt thêm vào (augmentation rule):

N$u X →→→→Y thì XZ →→→→Y trong ñó ký hi u XZ thay cho X∪∪∪∪Z

(F3) LuIt bPc cQu (transitive rule):

N$u X →→→→Y và Y →→→→Z thì X →→→→Z

Armstrong llàà ññúúngng vvàà ññầầyy ññủủ ((xemxem sgksgk) )

CCầầnn chchứứngng minhminh HHệệ tiêntiên ññềề Armstrong : F f f ⇒⇒⇒⇒⇒⇒⇒⇒ F F ======== f f TTíínhnh ññúúngng : F TTíínhnh ññầầyy ññủủ : : ∀∀∀∀∀∀∀∀ F F ======== f f ⇒⇒⇒⇒⇒⇒⇒⇒ F F  ff

(F1), (F2), (F3) CCáácc luluậậtt ddẫẫnn khkháácc suysuy ttừừ (F1), (F2), (F3) (F4) BPc cQu gi! : n$u X →→→→Y và YW →→→→Z thì XW →→→→Z. (F5) LuIt h(cid:7)i : n$u X →→→→Y và X →→→→Z thì X →→→→YZ (F6) LuIt phân rã : n$u X →→→→Y và Z⊆⊆⊆⊆Y thì X →→→→Z

Ví dụ :

Luật phản xạ

Luật thêm vào

B ⊆⊆⊆⊆ AB A →→→→ DE

Luật bắc cầu

AB →→→→ B AB →→→→ DE AB →→→→ DEB ABC →→→→ DEB A →→→→ C

Luật bắc cầu giả

AB →→→→ C

Luật hội

A →→→→ DEB

Luật phân rã

A →→→→ DE DE →→→→ C A →→→→ DE DEB →→→→ C A →→→→ DE A →→→→ B A →→→→ DE

A →→→→ D , A →→→→ E

Chứng minh Luật thêm vào: giả sử có t1.XZ

= t2.XZ (1)

= t2.X = t2.Y (do X →Y) (2)

⇒ t1.X ⇒ t1.Y ⇒ XZ →Y (do (1) ⇒(2)) Luật hợp: giả sử có t1.X = t2.X (1)

= t2.Y và t1.Z = t2.Z = t2.YZ (2)

⇒ t1.Y ⇒ t1.YZ ⇒ X →YZ (do (1) ⇒(2))

Luật phân rã: gỉa sử có t1.X

= t2.X (1)

= t2.YZ (do X →YZ) = t2.Y (2)

⇒ t1.YZ ⇒ t1.Y ⇒ X →Y (do (1) ⇒(2))

Luật bắc cầu: giả sử có t1.X= t2.X (1)

= t2.Y = t2.Z (2)

⇒ ⇒ ⇒

t1.Y t1.Z X →Z (do (1) ⇒(2))

Luật bắc cầu giả: giả sử có t1.XZ = t2.XZ (1)

= t2.X và t1.Z = t2.Z (2) = t2.Y (do X →Y) (3) = t2.YZ (Kết hợp (2) và (3)) = t2.W (do YZ →W) (4)

⇒ ⇒ ⇒ ⇒ ⇒

t1.X t1.Y t1.YZ t1.W XZ →W

Bài tIp 1 : Ch(cid:21)ng t= các pth sau ñ(cid:29)(cid:30)c suy di(cid:18)n tY F nhZ b(cid:7) luIt d[n Amstrong ?

F = { B →→→→→→→→ A ,A ,

AC →→→→→→→→ DADA ? DADA →→→→→→→→ CE ,CE ,

AC →→→→→→→→ DHDH D →→→→→→→→ H , H ,

AC →→→→→→→→ EHEH AC →→→→→→→→ D D }

F = { B →→→→→→→→ A ,A ,

? BDBD →→→→→→→→ CE ,CE , BD →→→→→→→→ EH EH

A →→→→→→→→ CB , CB , B B →→→→→→→→ CGCG

C →→→→→→→→ G ,G ,

GE GE →→→→→→→→ H H }

Ví dụ F = { B →→→→→→→→ A ,A ,

Chứng minh AC →→→→→→→→ DA ?DA ? DADA →→→→→→→→ CE ,CE ,

D →→→→→→→→ H , H ,

f4 : AC →→→→→→→→ DD

AC →→→→→→→→ A (A (theotheo luluậậtt phphảảnn xxạạ))

TaTa ccóó f4 : vvàà => => SuySuy rara AC →→→→→→→→ DA (DA (theotheo luluậậtt hhộộii))

AC →→→→→→→→ D D }

4.Bao ñóng của tập thuộc tính X (closures of attribute sets)

Cho Q là lược ñồ quan hệ Q( Q+), F là tập các phụ thuộc hàm ñịnh nghĩa trên Q , gọi X, Ai ⊆⊆⊆⊆⊆⊆⊆⊆ Q+.

F )

Bao ñóng c*a tIp thu(cid:7)c tính X dba trên F ký hi u là X+ (hodc X+

F = ∪∪∪∪Ai v?i X →→→→Ai là ph(cid:12) thu(cid:7)c hàm ñ(cid:29)(cid:30)c suy di(cid:18)n tY F nhZ h tiên ñA Armstrong (cid:4)(cid:4) NhNhậậnn xxéétt : X

X+

⇒⇒⇒⇒⇒⇒⇒⇒ BBổổ ññềề : : X X →→→→→→→→Y Y ∈∈∈∈∈∈∈∈FF++ ⇔⇔⇔⇔⇔⇔⇔⇔ Y Y ⊆⊆⊆⊆⊆⊆⊆⊆XX++ ChChứứngng minhminh :: (1) X →→→→→→→→ Y Y ⇒⇒⇒⇒⇒⇒⇒⇒ ttồồnn ttạạii k k saosao chocho Y = Y = AAkk ⊆⊆⊆⊆⊆⊆⊆⊆ ∪∪∪∪∪∪∪∪ Ai = X+ Ai = X+ theotheo ññịịnhnh nghnghĩĩaa ccủủaa XX++ (1) X (2) Y ⊆⊆⊆⊆⊆⊆⊆⊆ XX++ ⇒⇒⇒⇒⇒⇒⇒⇒ XX++ = Y = Y ∪∪∪∪∪∪∪∪ (X(X++ -- Y) Y) ⇒⇒⇒⇒⇒⇒⇒⇒ X X →→→→→→→→ Y Y ∪∪∪∪∪∪∪∪ (X(X++ -- Y)Y)⇒⇒⇒⇒⇒⇒⇒⇒ X X →→→→→→→→ Y Y theotheo luluậậtt phânphân (2) Y rãrã

: X ⊆⊆⊆⊆⊆⊆⊆⊆ XX++ , X, X++ ⊆⊆⊆⊆⊆⊆⊆⊆ QQ++

Thuật toán tìm bao ñóng X+: 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:

lQn l(cid:29)(cid:30)t xét các ph(cid:12) thu(cid:7)c hàm c*a F B(cid:29)?c 1: X0 = X B(cid:29)?c 2:

N$u Y→→→→Z có Y ⊆⊆⊆⊆Xi thì Xi+1 = Xi ∪∪∪∪Z Lo(cid:22)i ph(cid:12) thu(cid:7)c hàm Y →→→→Z kh=i F

B(cid:29)?c 3: N$u / b(cid:29)?c 2 không tính ñ(cid:29)(cid:30)c Xi+1 thì Xi chính là bao ñóng c*a X Ng(cid:29)(cid:30)c l(cid:22)i ldp l(cid:22)i b(cid:29)?c 2

Ví d(cid:12) 1: Cho l(cid:29)(cid:30)c ñE quan h Q(ABCDE) và tIp ph(cid:12) thu(cid:7)c hàm F F = {

f1: f2: f3: f4: A →→→→B B →→→→C C →→→→D D →→→→E }

Tìm bao ñóng c*a tIp X = {AB} dba trên F

Gi!i: B(cid:29)?c 1:X0 = AB B(cid:29)?c 2: xét f1 vì A ⊆⊆⊆⊆X0 (cid:5)(cid:5)(cid:5)(cid:5) X1 = AB ∪∪∪∪B = AB , lo(cid:22)i f1 xét f2 vì B ⊆⊆⊆⊆X1 (cid:5)(cid:5)(cid:5)(cid:5) X2 = AB ∪∪∪∪C = ABC , l@ai f2 xét f3 vì C ⊆⊆⊆⊆X2 (cid:5)(cid:5)(cid:5)(cid:5) X3 = ABC ∪∪∪∪D = ABCD , lo(cid:22)i f3 xét f4 vì D ⊆⊆⊆⊆X3 (cid:5)(cid:5)(cid:5)(cid:5) X4 = ABCD ∪∪∪∪E = ABCDE , lo(cid:22)i f4

B(cid:29)?c 3 : X+ = X4 = {ABCDE} là bao ñóng c*a X

Ví d(cid:12) 2: (sgk ) Cho l(cid:29)(cid:30)c ñE quan h Q(ABCDEGH) và tIp ph(cid:12) thu(cid:7)c hàm F F = {

f1: f2: f3: f4: f5: B →→→→A DA →→→→CE D →→→→H GH →→→→C AC →→→→D }

B(cid:29)?c 1: X0 = AC B(cid:29)?c 2: xét f5 vì AC ⊆⊆⊆⊆X0 (cid:5)(cid:5)(cid:5)(cid:5) X1 = AC ∪∪∪∪D = ACD

xét f2 vì AD ⊆⊆⊆⊆X1 (cid:5)(cid:5)(cid:5)(cid:5) X2 = ACD ∪∪∪∪CE = ACDE xét f3 vì D ⊆⊆⊆⊆X2 (cid:5)(cid:5)(cid:5)(cid:5) X3 = ACDE ∪∪∪∪H = ACDEH

Xét f1, f4 :không th=a vì có v$ trái không nlm trong X3 VIy X3 không thay ñmi (cid:5)(cid:5)(cid:5)(cid:5) X+=X3={ACDEH} là bao ñóng c*a X (cid:5)(cid:5)(cid:5)(cid:5) AC →→→→EH ∈∈∈∈ F+

Ch(cid:21)ng minh f= {AC →→→→EH } ñ(cid:29)(cid:30)c suy d[n tY F ? Gi!i:

Bài tIp 2: Cho Q(ABCDEGH) và tIp pth F th=a trên Q.

Tìm bao ñóng c*a AC ?

F = { B →→→→→→→→ A ,A ,

DADA →→→→→→→→ CE ,CE , AC + = ?

D →→→→→→→→ H , H ,

AC →→→→→→→→ D D }

F = { B →→→→→→→→ A ,A ,

BDBD →→→→→→→→ CE ,CE ,

A →→→→→→→→ CB , CB , B + = ?

C →→→→→→→→ G ,G ,

GE GE →→→→→→→→ H H }

5. Thuật toán tìm F+ Thuật toán cơ bản ðể tính bao ñóng F+ của tập các phụ thuộc hàm F ta thực

hiện các bước sau:

• Bước 1: Tìm tất cả tập con của Q+ • Bước 2: Tìm tất cả các phụ thuộc hàm có thể có của Q. • Bước 3: Tìm bao ñóng của tất cả tập con của Q. • Bước 4: Dựa vào bao ñóng của tất cả các tập con ñã tìm

ñể xác ñịnh phụ thuộc hàm nào thuộc F+

Thuật toán cải tiến Dựa vào thuật toán cơ bản trên, ta nhận thấy có thể tính F+ theo các bước sau: Bước 1: Tìm tất cả tập con của Q+ Bước 2: Tìm bao ñóng của tất cả tập con của Q+. Bước 4: Dựa vào bao ñóng của các tập con ñã tìm ñể suy ra các phụ thuộc hàm thuộc F+. 20

Phủ và Phủ tối thiểu

Các khái niệm : • • •

Tập phụ thuộc hàm tương ñương với F Phủ của F Phủ tối thiểu của F

1. Hai tập phụ thuộc hàm tương ñương

Tập phụ thuộc hàm F và G tương ñương nếu F+ = G+

ký hiệu F ≡≡≡≡≡≡≡≡ GG

Bổ ñề : F ≡≡≡≡≡≡≡≡ G G nnếếuu vvàà chchỉỉ nnếếuu F |F |======== G G vvàà G |G |======== FF (cid:6)(cid:6)(cid:6)(cid:6)(cid:6)(cid:6)(cid:6)(cid:6) NNếếuu F F ≡≡≡≡≡≡≡≡ G G ⇒ FF ======== GG và GG ======== FF

∀∀∀∀∀∀∀∀gg∈∈∈∈∈∈∈∈ G +, g: X G +, g: X →→→→→→→→ YY ⇒ gg∈∈∈∈∈∈∈∈ FF + + ⇒ FF ======== gg

Do Do ññóó ∀ ∀ ∀ ∀ ∀ ∀ ∀ ∀gg∈∈∈∈∈∈∈∈ GG ththìì FF======== g hay F g hay F ======== G G

Tương ttựự ∀∀∀∀∀∀∀∀ff∈∈∈∈∈∈∈∈ FF ththìì G G ======== f hay Tương f hay GG ======== FF

(cid:6)(cid:6) NNếếuu F F ======== GG và GG ======== FF ⇒ FF ≡≡≡≡≡≡≡≡ GG

F F ======== GG ⇒ GG ⊆ FF + ⇒ GG +⊆ (FF +)+= FF +

GG ======== F F ⇒ FF ⊆ GG + ⇒ FF +⊆ (GG +)+= GG +

Thuật tóan xác ñịnh F và G có tương ñương không ?

B1 :với mỗi X →→→→→→→→ Y Y ccủủaa F F xxáácc ññịịnhnh xemxem X →→→→→→→→ Y Y ccóó ñưñượợcc không suysuy ddẫẫnn ttừừ G G không

B2 :với mỗi X →→→→→→→→ Y Y ccủủaa G G xxáácc ññịịnhnh xemxem X →→→→→→→→ Y Y ccóó ñưñượợcc không suysuy ddẫẫnn ttừừ F F không

NNếếuu ccảả 2 2 bưbướớcc trêntrên ññềềuu ññúúngng ththìì F F ≡≡≡≡≡≡≡≡ GG

Ví dụ 1: Cho lược ñồ quan hệ Q (ABCDE) và 2 tập pth

F ={A→→→→→→→→BC, BC, A→→→→→→→→D, CDD, CD→→→→→→→→E E } và G ={A→→→→→→→→BCE, BCE, A→→→→→→→→ABD, CD ABD, CD→→→→→→→→E E }

1. F có tương ñương với G không ?

2. F có tương ñương với G’ = { A→→→→→→→→BCDE BCDE }

1. Nhận xét : F ñược suy diễn từ G (1)

+ = {ABCDE} => trong F+ có A→→→→→→→→BCE BCE vvàà A→→→→→→→→ABD (2) ABD (2)

Ta Kiểm tra G có ñược suy diễn từ F không ?

Tính AF

TTừừ (1) (2) : (1) (2) : kkếếtt luluậậnn F F ≡≡≡≡≡≡≡≡ GG

+ = {CD} => G’+ không chứa pth CD →→→→→→→→ EE

2. Ta kiểm tra F có ñược suy diễn từ G’ không ?

Tính CDG

KKếếtt luluậậnn : F : F không không tương tương ñương ñương GG’’

Ví dụ 1: Cho lược ñồ quan hệ Q (ABCDE)

và 2 tập pth

F ={A→→→→→→→→BC, BC, A→→→→→→→→D, CDD, CD→→→→→→→→E E } và G ={A→→→→→→→→BCE,

BCE, A→→→→→→→→ABD, CD

ABD, CD→→→→→→→→E E }

1. F có tương ñương với G không ? 2. F có tương ñương với G’ = { A→→→→→→→→BCDE BCDE }

Cho lược ñồ quan hệ Q (ABCDE) và 2 tập pth

F ={A→→→→→→→→BC, BC, A→→→→→→→→D, CDD, CD→→→→→→→→E E } và G ={A→→→→→→→→DE , DE , A→→→→→→→→BCE, CD

BCE, CD→→→→→→→→E }E }

F ={A→→→→→→→→B, BB, B→→→→→→→→C, CC, C→→→→→→→→D D } và G ={A→→→→→→→→BCD , B

BCD , B→→→→→→→→CD, CCD, C→→→→→→→→D }D }

F ={A→→→→→→→→B, BB, B→→→→→→→→C, CC, C→→→→→→→→D D } và G ={A→→→→→→→→CD , C

CD , C→→→→→→→→D }D }

F ={AB→→→→→→→→C, BC, B→→→→→→→→C, CDC, CD→→→→→→→→E ,DE ,D→→→→→→→→E E } và G ={B→→→→→→→→C , DC , D→→→→→→→→E }E }

F ={AB→→→→→→→→C, BC, B→→→→→→→→C, CDC, CD→→→→→→→→E ,DE ,D→→→→→→→→E E } và G ={AB→→→→→→→→CC, B→→→→→→→→C, CC, C→→→→→→→→B, BDB, BD→→→→→→→→E }E }

Bài tập : xem xét các cặp pth sau có tương ñương không?

BCE, A→→→→→→→→ABD, CD

ABD, CD→→→→→→→→EE }

2. Phủ của F

ABCD, CD→→→→→→→→E }E }

BCD, CD→→→→→→→→E E }

G2 = { A→→→→→→→→E, E, A→→→→→→→→ABCD, CD G3 = { A→→→→→→→→BCD, CD ….

Trong các phủ của F ta quan tâm tới một nhóm phủ gọi là phủ tối thiểu

G là phủ của F nếu G ≡≡≡≡≡≡≡≡ FF Một số phủ của F : G1 = { A→→→→→→→→BCE,

G là phủ tối thiểu của F nếu G là phủ của F ñồng thời thỏa 3 ñiều kiện sau :

- G là tập phụ thuộc hàm có vế trái không dư thừa

(G chỉ chứa những pth ñầy ñủ)

- G là tập phụ thuộc hàm có vế phải một thuộc tính

(G chỉ chứa những pth có vế phải một thuộc tính)

- G là tập phụ thuộc hàm không dư thừa

3. Phủ tối thiểu

3.a. Phụ thuộc hàm có vế trái không dư thừa :

Cho F , f: X→Y∈F. Nói rlng ph(cid:12) thu(cid:7)c hàm f: X→→→→Y có

v$ trái d(cid:29) thYa (ph(cid:12) thu(cid:7)c hàm không ñQy ñ*) n$u tEn t(cid:22)i m(cid:7)t Z∈∈∈∈X sao cho :

F ≡≡≡≡F - {X →→→→Y} ∪∪∪∪{Z →→→→Y}

Ví d(cid:12) 1: cho Q(A,B,C) và F= {AB→→→→C; B→→→→C}

AB →→→→C là ph(cid:12) thu(cid:7)c hàm có v$ trái d(cid:29) thYa vì

F ≡≡≡≡F- {AB→→→→C}∪∪∪∪{B→→→→C}= {B→→→→C}

Nhận xét :

Pth có vế trái một thuộc tính là pth có vế trái không dư thừa

F là Tập pth có vế trái không dư thừa nếu F không chứa những pth có vế trái dư thừa.

Thuật tóan ñể lọai khỏi F các pth có vế trái dư thừa :

Bước 1: LQn l(cid:29)(cid:30)t thbc hi n b(cid:29)?c 2 cho các pth X→→→→Y c*a F

Bước 2: V?i m@i tIp con X’≠≠≠≠∅∅∅∅c*a X.

N$u X'→→→→Y∈∈∈∈F+ thì thay X→→→→Y trong F blng X'→→→→Y

Ví d(cid:12) 2: lọai khỏi F các pth có vế trái dư thừa

cho tIp ph(cid:12) thu(cid:7)c hàm F = {A →→→→BC, B →→→→C, AB →→→→D}

+ = ABCD => A →→→→D ∈∈∈∈F+

+ = BC => B →→→→D ∉∉∉∉F+

- xét pth AB →→→→D :

A →→→→D ∈∈∈∈F+ ? tính AF B →→→→D ∈∈∈∈F+ ? tính BF

Trong F ta thay AB →→→→D blng A →→→→D

VIy F ≡≡≡≡ F’ = {A →→→→ BC, B →→→→C, A →→→→D}

- Các pth còn l(cid:22)i có v$ trái 1 thu(cid:7)c tính _ là pth ñQy ñ*

K$t luIn : F ≡≡≡≡F’ là tIp pth có v$ trái không d(cid:29) thYa

3.b. Tập phụ thuộc hàm có vế phải một thuộc tính

Mỗi tập phụ thuộc hàm F ñều tương ñương với một tập phụ thuộc hàm G mà vế phải của các pth trong G chỉ gồm một thuộc tính.

Ví dụ 3: cho F = {A → BC , B → C , A → D} ta suy ra

F ≡ {A → B, A → C , B → C , A → D} = G

G ñược gọi là tIp ph(cid:12) thu(cid:7)c hàm có v$ ph!i m(cid:7)t thu(cid:7)c tính.

3.c. Tập phụ thuộc hàm không dư thừa

Nói rlng F là tIp ph(cid:12) thu(cid:7)c hàm không d(cid:29) thYa n$u

không tEn t(cid:22)i X→→→→Y ∈∈∈∈F sao cho F ≡≡≡≡F – {X→→→→Y}. Ng(cid:29)(cid:30)c l(cid:22)i F là tIp ph(cid:12) thu(cid:7)c hàm d(cid:29) thYa.

Ví dụ 4: cho F = {A→BC, B→D, AB→D} thì

F dư thừa vì tồn tại AB→D ∈∈∈∈F mà

F ≡ F – {AB→D} = {A→BC, B→D}

Thuật tóan lọai khỏi F các pth dư thừa:

Bước 1: lần lượt lọai từng pth X →→→→ Y trong F , ta có G

Bước 2: kiểm tra X →→→→ Y có ñược suy dẫn từ G không ?

Bước 3: nếu có thì pth X →→→→ Y là dư thừa và lọai khỏi F

quay lại bước 1

Giải theo thuật toán :

cho F = {A→BC, B→D, AB→D}

- Thử loại A→BC , có G = { B→D, AB→D} => A→BC không ñược suy dẫn từ G

- Thử loai B→D , có G = {A→BC, AB→D} => B→D không ñược suy dẫn từ G

- Thử loại AB→D, có G = {A→BC, B→D }

=> AB→D ñược suy dẫn từ G , => F dư thừa AB→D

Từ tập phụ thuộc hàm F cho trước , câu hỏi là tìm phủ tối thiểu của F ?

B(cid:29)?c 1: lo(cid:22)i kh=i F các ph(cid:12) thu(cid:7)c hàm có v$ trái d(cid:29) thYa.

B(cid:29)?c 2: Tách các ph(cid:12) thu(cid:7)c hàm có v$ ph!i trên m(cid:7)t thu(cid:7)c tính thành các ph(cid:12) thu(cid:7)c hàm có v$ ph!i m(cid:7)t thu(cid:7)c tính.

B(cid:29)?c 3: lo(cid:22)i kh=i F các ph(cid:12) thu(cid:7)c hàm d(cid:29) thYa

* Bài tóan trọng tâm

Thuật toán tìm phủ tối thiểu của một tập phụ thuộc hàm *

Nhận xét :

Từ một tập pth F luôn tìm ñược ít nhất một phủ tối thiểu F’

Nếu tập pth F có nhiều phủ tối thiểu thì các phủ tối thiểu tương ñương với nhau F’ ≡≡≡≡ F’’ ≡≡≡≡ F

Ví dụ 1: Cho lược ñồ quan hệ Q(A,B,C,D) và tập pth F như sau:

F = {AB → CD,B → C,C → D} Hãy tìm phủ tối thiểu của F.

Bước 1: AB→CD là phụ thuộc hàm có vế trái dư thừa?

+ = BCD ⇒ B → CD ∈ F+

+ = A ⇒ A → CD ∉ F+

Xét B → CD ∈ F+ ? trả lời: BF Xét A → CD ∈ F+ ? trả lời: AF Vậy AB → CD là phụ thuộc hàm có vế trái dư thừa A

⇒ kết quả của bước 1 là: F ≡≡≡≡ {B →→→→ CD ; B →→→→ C ; C →→→→ D} = F1 Bước 2: kết quả của bước 2 là:

F ≡≡≡≡ {B →→→→ D; B →→→→ C;C →→→→ D} = F1

Bước 3:

trong F1 , B → C là phụ thuộc hàm dư thừa?

xét B → C ∈ G+ ? với G = F1 - {B → C} = {B → D;C → D} Trả lời : BG

+ = BD ⇒ B → C ∉ G+ ⇒ B →→→→ C không dư thừa trong F1

trong F1 , B → D là phụ thuộc hàm dư thừa?

xét B → D ∈ G+ ? với G = F1 - {B → D} = {B → C;C → D} trả lời : BG

+ = BCD ⇒ B → D ∈ G + ⇒ B →→→→ D dư thừa trong F1

trong F1 , C → D là phụ thuộc hàm dư thừa?

xét C → D ∈ G+ ? với G = F1 - {C → D} = {B → D;B → C} trả lời :CG

+ = C ⇒ C → D ∉ G + ⇒ C → D không dư thừa trong F1

Kết quả của bước 3 : cho phủ tối thiểu

F ≡ F1 - {B → D} F ≡≡≡≡ {B →→→→ C;C →→→→ D} = Ftt

Ví dụ 2: Cho lược ñồ quan hệ Q(A,B,C,D) và tập phụ thuộc F như sau:

F= {AB → C , B → A , A → B} Hãy tính phủ tối thiểu của F?

Bước 1 : AB → C có là pth có vế trái dư thừa ?

B → C ∈ F+ ? trả lời: B+ = ABC ⇒ B → C ∈ F+

A → C ∈ F+ ? trả lời: A+ = ABC ⇒ A → C ∈ F+

Kết quả có 2 tập F’ và F” có vế trái không dư thừa :

F ≡≡≡≡ F’ = {B →→→→ C;B →→→→ A;A →→→→ B}

F ≡≡≡≡ F” = {A →→→→ C;B →→→→ A;A →→→→ B}

Bước 2 : F’ và F” là các tập phụ thuộc hàm có vế phải một thuộc tính

Bước 3 :

Xét F’ = {B → C;B → A;A → B} thì thấy F’ không phải là tập pth dư thừa.

Xét F” = {A → C;B → A;A → B} thì thấy F” không phải là tập pth dư thừa

Kết luận : F có 2 tập phủ tối thiểu F’ và F”

Ví dụ 3: Cho lược ñồ quan hệ Q(MSCD,MSSV,CD,HG) và tập phụ thuộc F như sau:

F = {MSCD→ CD;

CD → MSCD;

CD,MSSV → HG;

MSCD,HG → MSSV;

CD,HG → MSSV;

MSCD,MSSV → HG}

Hãy tìm phủ tối thiểu của F ?

Ví dụ 4: Cho lược ñồ quan hệ Q(ABC) ,tìm các phủ tối thiểu của tâp phụ thuộc hàm F

F = { A→ B ; A→ C; B → A; C → A;B → C }

KHÓA CỦA LƯỢC ðỒ QUAN HỆ

• Khái niệm • Thuật toán tìm một khóa • Thuật toán tìm tất cả các khóa

Cho Q(Q+) và F là tập pth ñịnh nghĩa trên Q. Cho K⊆⊆⊆⊆ Q+

+ = Q= Q+))

K là một khóa của Q nếu thỏa 2 ñiều kiện:

(hay KFF (hay K

(1) K →→→→→→→→ QQ+ ∈∈∈∈∈∈∈∈ FF+ (2) ∃∃∃∃ K’ ⊂⊂⊂⊂ K , K’ →→→→→→→→ QQ+ ∈∈∈∈∈∈∈∈ FF+

- Tập thuộc tính S là siêu khóa nếu S ⊇⊇⊇⊇K - Thuộc tính A là thu(cid:7)c tính khóa nếu A ∈∈∈∈∈∈∈∈KK -- Thuộc tính B là thu(cid:7)c tính không khóa nếu B ∉∉∉∉K - Tập thuộc tính không khóa có thể bằng ∅∅∅∅ - Một lươc ñồ quan hệ có thể có nhiAu khóa K

(cid:4) Thuật tóan tìm một khóa của lược ñồ quan hệ Q :

B1 : Gán K = Q+

B2 : Lần lượt thử lọai từng thuộc tính A ∈∈∈∈ K,có K’ = K – A

nếu k’+ = Q+ thì gán K = K’

Thực hiện lại bước 2

Ví dụ_sgk : Cho Q(ABCDEGHI) và F = {AC→→→→ B, BI →→→→ ACD, ABC →→→→ D, H →→→→ I, ACE →→→→ BCG, CG →→→→ AE}

Gán K = Q+ = {A,B,C,D,E,G,H,I}

Xét K’= K - {A} = {BCDEGHI} , tính K’+ = BCDEGHIA = Q+

⇒gán K = K’

Xét K’= K - {B} = {CDEGHI} , tính K’+ = CDEGHIAB = Q+

⇒Gán K= K’

Xét K’= K – {C} = {DEGHI} , tính K’+ = DEGHI ≠ Q+

Xét K’= K – {D} = {CEGHI} , tính K’+ = CEGHIABD = Q+

⇒Gán K = k’

Tiếp tục tương tự … kết quả thu ñược khóa K = {C,G,H}

• Cho Q(ABCDEGHI) và

F = {AC→→→→ B, BI →→→→ ACD, ABC →→→→ D, H →→→→ I, ACE →→→→ BCG, CG →→→→ AE} K’= {DEGHI} K’+= ?

(cid:4) Thuật tóan tìm tất cả các khóa của lược ñồ quan hệ Q Thuật tóan căn bản:

B1: Xây dựng các tập con Xi có thể có của Q+

B2: Tìm bao ñóng của các Xi

B3: Xác ñịnh các siêu khóa Si chính là các Xi có Xi+ = Q+ B4: Xác ñịnh các khóa từ tập siêu khóa SSSS

∀∀∀∀ Si, Sj ∈∈∈∈ SSSS, nếu ∃∃∃∃ Sj ⊂⊂⊂⊂ Si thì SSSS’’’’ = S S S S –––– Si Cuối cùng tập SSSS’’’’ là tIp tvt c! các khóa cQn tìm

Ví dụ -sgk …

Nhận xét : Kết quả của B1 có thể là một tập rất lớn của các tập con của Q+ (2n)

Các khái niệm

-Tập thuộc tính nguồn (TN) gồm tất cả

• Các thuộc tính chỉ xuất hiện ở vế trái và không xuất hiện ở vế phải của các pth • Các thuộc tính không xuất hiện ở cả vế trái và vế phải của các pth

-Tập thuộc tính ñích (TD) gồm tất cả

-Các thuộc tính chỉ xuất hiện ở vế phải của các pth

-Tập thuộc tính trung gian (TG) : gồm tất cả

•Các thuộc tính xuất hiện ở cả vế trái và vế phải của các pth

(cid:4) Thuật tóan tìm tất cả các khóa của lược ñồ quan hệ Q Thuật tóan cải tiến :

Hệ quả : Nếu K là khóa của A thì K ⊇ ⊇ ⊇ ⊇ TN và K ∩ ∩ ∩ ∩ TD = ∅∅∅∅

Thuật tóan cải tiến : Dữ liệu vào : lược ñồ quan hệ Q , tập phụ thuộc hàm F Dữ liệu ra: tất cả các khóa của quan hệ Q

B1: Xác ñịnh tập thụôc tính nguồn TN, tập thuộc tính trung gian TG B2: Nếu TG = ∅ thì Q chỉ có một khóa K = TN kết thúc Ngược lại : Qua bước 3

B3: tìm tất cả các tập con Xi của tập trung gian TG

B4: tìm các siêu khóa Si :

∀∀∀∀ Xi , nếu (TN ∪∪∪∪ Xi)+ = Q+ thì Si = TN ∪∪∪∪ Xi

B5: tìm các khóa từ tập siêu khóa S: