第三章數(shù)據(jù)依賴-文庫(kù)吧
2025-09-13 12:45 本頁(yè)面
【正文】 公理的完備性 定義 (FDs的閉包 F +) 設(shè) F是關(guān)系 r(R)上的 FDs， F所蘊(yùn)含的所有 FD的集合稱為 F的閉包，記作 F +。 F + = { X→Y | 所有 F |= X→Y } 18 例： 設(shè) F={AB→C ， C→B} 。 F+ 為： F+ = {A→A, AB→A, AC→A, ABC→A, B→B, AB→B, BC→B ， ABC→B ， C→C ， AC→C ， BC→C,ABC→C ， AB→AB， ABC→AB ， AC→AC ， ABC→AC ， BC→BC, ABC→BC, ABC→ABC, AB→C, AB→AC, AB→BC, AB→ABC ， C→B, C→BC ， AC→B ， AC→AB} 19 定義 (屬性集的閉包 X + ) 設(shè)關(guān)系模式 R(U, F)， X ? U, 所有用公理推出的 X→A i中 Ai的屬性集合稱 X對(duì)于 F的閉包，記作： X + X +={ Ai | 用公理推出的 X→A i 且 Ai ? U} 20 定理 2 Armstrong公理是完備的。 證明：如果能證明 X→Y 不能由公理推出將不會(huì)被 F所蘊(yùn)涵，則公理得證。為此，構(gòu)造一個(gè)關(guān)系 r(R)。 我們將證明兩點(diǎn)： (1). F中的所有函數(shù)依賴在 r (R)上都成立； (2). X→Y 在 r(R)上不成立。 21 設(shè) R=A1A2 … A n， 關(guān)系 r中僅有二個(gè)元組 t 和 t39。 元組 t=〈 a1a2 … a n〉。 元組 t39。被定義為： ai 若 Ai ? X+ t39。(Ai ) = bi 若 Ai ? X+ X+ U X+ A1 A2 ... Ak Ak+1 ... An t a1 a2 ... ak ak+1 ... an t39。 a1 a2 ... ak bk+1 ... bn 22 證明： (1) 設(shè) W→Z ?F， W在 r中有兩種情況 : (a) W ? X+。 根據(jù)屬性閉包定義，有 X→W ， 又因 W→Z， 根據(jù)公理 A3有 X→Z 。 因此 Z?X+， 即 t[Z]= t’[Z]= ai , 所以， W→Z 在 r上成立。 (b) W ? X+。 則在 r中有 t[W] ? t’[W]， 因此， W→Z在 r上總是成立的。 由 (a)和 (b)得： r(R)滿足 F。 (2) 若 X→Y 不能由公理推出。即 X?X+而 Y?X+， 由 r的構(gòu)造知， X→Y 在 r上不成立，即 X→Y 不被 F所蘊(yùn)涵。 23 函數(shù)依賴集閉包及成員測(cè)試算法 算法 1 計(jì)算屬性集 X的閉包 X+的算法 輸入：屬性集 X和函數(shù)依賴集 F 輸出： X的閉包 X+ While RESULT≠VAR do Begin VAR:=RESULT。 for every FD W→Z in F do if W?RESULT then RESULT:=RESULT∪Z end。 return(RESULT) end. CLOSURE(X, F) Begin VAR:=φ 。 RESULT:=X。 24 例： F={A→D, AB→E, BI→E ， CD→I ， E→C} 求： AE+ 解： AE0 = AE AE1 = AED AE2 = AEDC … AE+ = ACDEI F={A2→A 1, A3→A 2, A4→A 3， ?， Am→A m1} 算法改進(jìn)：每個(gè) FD僅考察一次；每個(gè)屬性僅考察一次 25 計(jì)算屬性閉包的改進(jìn)算法： 1. 構(gòu)造一個(gè) LIST表， 存放含相同左部屬性的 FD。 如 list[A]， 將存放左部含 A的 FD； 2. 構(gòu)造一個(gè)計(jì)數(shù)器 COUNT， 計(jì)數(shù) FD的左部屬性數(shù)。 如 : COUNT[W→Z]=|W| 。 3. 變量 UPDATE記錄未考察的屬性，使每個(gè)屬性僅 考察一次， RESULT放中間和最后結(jié)果。 26 算法 計(jì)算屬性閉包的改進(jìn)算法 LINCLOSURE(X, F) Ⅰ. 初始化 for each FD W→Z in F do begin COUNT[W→Z]:=│W│。 for each attribute A in W do add W→Z to list[A] end。 RESULT:=X。 UPDATE:=X. 27 Ⅱ. 計(jì)算 While UPDATE?φ do begin Choose an A in UPDATE。 UPDATE:=UPDATEA。 for each FD W→Z in LIST[A] do begin COUNT[W→Z]:=COUNT[W→Z] 1。 if COUNT[W→Z]=0 then begin ADD:=ZRESULT。 RESULT:=RESULT∪ADD UPDATE:=UPDATE∪ADD end end end. Ⅲ. return(RESULT). 28 例 : 設(shè) F={A→D ， AB→E ， BI→E ， CD→I ， E→C} 計(jì)算： LINCLOSURE(AE,F)。 解： (1) 初始化： RESULT=AE UPDATE=AE LIST[A]=A→D ， AB→E COUNT[A→D]= 1 LIST[B]=BI→E ， AB→E COUNT[AB→E]= 2 LIST[C]=CD→I COUNT[BI→E]= 2 LIST[D]=CD→I COUNT[CD→I]= 2 LIST[E]=E→C COUNT[E→C]= 1 LIST[I]=BI→E (2) COUNT[A→
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1