Luận văn Thu gọn lược đồ quan hệ và ứng dụng

F Output: - Một phủ thu gọn trái G của F i) GF ii) g: LR  G, A L: G\{g}{L\{A}R} ! G Method U : = Attr (F) ; // Tập thuộc tính của F G := F; For each FD g: LR in F do X := L; For each attribute A in X do If R Closure (U, G, L\{A}R) then Delete A from L in G; Endif Endfor Endfor Return G; End Left_Reduced 1.5.3.2 Phủ thu gọn phải Cho hai tập PTH F và G trên tập thuộc tính U, G được gọi là phủ thu gọn phải của F nếu: i) G là một phủ của F, và ii) (LR  G, AR) : G\{LR}{LR\A}  G  Thuật toán tìm phủ thu gọn phải của tập PTH Ta thấy rằng g: LR  G, A  R : G╞ g’: LR \ {A}, vì R\{A}  R , do đó ta chỉ cần kiểm tra G \ {g}  {g’}╞ g ? Algorithm Right_Reduced Function : Tính phủ thu gọn phải của tập PTH Format: Right_Reduced (F) Input: - Tập PTH F Output: - Một phủ thu gọn phải G của F i) GF ii) g: LR  G, A R: G\{g} {LR\A} ! G Method U : = Attr (F) ; // Tập thuộc tính của F G := F; For each FD g: LR in F do X:=R; For each attribute A in X do If A in Closure (U, G\{g}  {LR\{A}},L) then Delete A from R in G; Endif; Endfor; If R =  then Delete LR from G; Endif; Endfor; Return G; End Right_Reduced. 1.5.4 Phủ tối tiểu Cho hai tập F và G trên tập thuộc tính U. G được gọi là phủ tối tiểu của F nếu : i) G là một phủ của F ii) Vế phải của PTH trong G chỉ chứa một thuộc tính.  Thuật toán tìm phủ tối tiểu của tập PTH Algorithm MinCover Function: Tính phủ tối tiểu của tập PTH Format: MinCover (F) Input: - Tập PTH F Output: - Một phủ tối tiểu G của F Method // Tách mỗi PTH LR trong F thành các PTH LA, AR G := ; For each FD LR in F do For each attribute A in R\L do If LA not_in G then Add LA to G; Endif; Endfor; Endfor; G := Reduced (G); Return G; End Mincover. 1.6 Khóa của lược đồ quan hệ Cho LĐQH p = (U, F). Tập thuộc tính K  U được gọi là khóa của LĐQH p nếu: (i) K+ = U (ii) AK: (K\{A})+  U Hai điều kiện trên tương đương với (i) K  U (ii) AK: (K\{A}) ! U Nếu K thỏa mãn điều kiện (i) thì K được gọi là một siêu khóa. Thuộc tính A  U được gọi là thuộc tính khóa (nguyên thủy hoặc cơ sở) nếu A có mặt trong một khóa nào đấy. A được gọi là thuộc tính không khóa (phi nguyên thủy hoặc thứ cấp) nếu A không có mặt trong bất kỳ khóa nào. Ký hiệu UK là tập các thuộc tính khóa của LĐQH p và U0 là tập các thuộc tính không khóa của p. Chú ý: Trong một số tài liệu, thuật ngữ khoá được dùng theo nghĩa siêu khoá và thuật ngữ khoá tối tiểu được dùng theo nghĩa khoá.  Thuật toán tìm khoá của LĐQH Tư tưởng: Xuất phát từ một siêu khoá K tuỳ ý của LĐQH, duyệt lần lượt các thuộc tính A của K, nếu bất biến (K\{A})+ = U được bảo toàn thì A loại khỏi K. Có thể thay kiểm tra (K\{A})+ = U bằng kiểm tra A  (K\{A})+ . Algorithm Key Function: Tìm một khoá của LĐQH Format: Key (U,F) Input: - Tập thuộc tính U - Tập PTH F Output: Khoá K  U thoả i) K+ = U ii) AK : (K\{A})+  U Method K := U; For each attribute A in U do If A  (K\{A})+ then K := K \ {A} Endif; Endfor; Return K; End key. Độ phức tạp tính toán: Thuật toán duyệt n thuộc tính, với mỗi thuộc tính thực hiện phép lấy bao đóng với độ phức tạp n2m. Tổng hợp lại, độ phức tạp tính toán của thuật toán là O(n3m). Ví dụ 1: Cho LĐQH p = (U,F), trong đó : U = {A, B, C, D, E} F = { D  E AB  CD C  AB } Hãy tìm một khoá của p. Dễ thấy rằng, LĐQH p có khoá K = C, vì thoả mãn hai điều kiện: (i) K+ = C+ = ABCDE = U (ii) C tối tiểu ( theo nghĩa (K \ {C})+  U ). Ví dụ 2: Cho P = (U,F), trong đó : U = ABCDE F = { C B DE  AC A  DE } Tìm khoá của LĐQH đã cho ? Ta thấy, LĐQH P có khoá K = A, vì thoả mãn 2 điều kiện : (i) K+ = A+ = ABCDE = U (ii) A tối tiểu ( theo nghĩa (K \ {A})+  U ). Mặt khác, tương tự như trên, ta cũng dễ thấy rằng LĐQH P còn khoá thứ 2, đó là K = DE. Để trả lời cho câu hỏi: Lược đồ có trên một khoá hay không, ta đi tìm giao các khoá. 1.6.1 Cách tính giao các khoá Những phần tử không xuất hiện ở vế phải thì nó có mặt ở mọi khoá, đó chính là giao các khoá. Vậy giao các khoá chính là những thuộc tính không xuất hiện ở vế phải. Giả sử M là giao các khoá. Nếu M+ = U thì lược đồ chỉ có đúng 1 khoá, nếu M+  U thì lược đồ có trên 1 khoá. Gọi M là giao các khoá khi và chỉ khi : M+ = U. Cho LĐQH p = (U,F) với n thuộc tính trong U và m PTH trong F. Gọi M là giao các khoá của p. Khi đó có thể xác định giao các khoá bằng một thuật toán tuyến tính theo mn qua công thức:  FRL LRUM   )\(\ .  Thuật toán xác định giao các khoá trong LĐQH Algorithm KeyIntersec Format: KeyIntersec(U,F) Input: - Tập thuộc tính U - Tập PTH F Output: - Giao các khoá  FRL LRUM   )\(\ Method M:=U; For each FD LR in F do M:=M\(R\L); Endfor; Return M; End KeyIntersec. 1.6.2 Thuật toán tìm 2 khoá của LĐQH Bước 1: Tính giao các khoá Bước 2: Lấy M+. Nếu M+ = U  Lược đồ có 1 khoá M là duy nhất M+  U  Lược đồ có trên 1 khoá Gọi thuật toán Key – Tìm khoá 1 Gọi thuật toán Key 2 – Tìm khoá 2 Tư tưởng: Xuất phát từ tập thuộc tính M = U, trước hết duyệt các thuộc tính A của K, nếu bất biến (M\{A})+ = U được bảo toàn thì loại A khỏi M. Sau đó duyệt tương tự với các thuộc tính trong U\K. Algorithm Key 2 Function: Tìm một khoá thứ 2 của LĐQH Format: Key 2 (U,F) Input: - Tập thuộc tính U - Tập PTH F - Khoá K  U Output: Khoá thứ hai, nếu có, M  U thoả i) M+ = U ii) AM : (M\{A})+  U Nếu không có khoá thứ 2:  Method M := U; For each attribute A in K do If A  (M\{A})+ then M := M \ {A} Endif; Endfor; For each attribute A in U \ K do If A  (M\{A})+ then M := M \ {A} Endif; Endfor; If M = K then return  Else return M; Endif End key 2. Ví dụ: Cho LĐQH P = (U,F) trong đó: U = ABCDE F = { BC  D CD  A D  E A  B } a. Hãy xác định phần giao của các khoá trong P b. Tìm một khoá K1 của P c. P có còn khoá nào khác ngoài K1 không ? Vì sao ? d. Xác định tập các thuộc tính không khoá U0 của P Giải a. Xác định phần giao của các khoá trong P Theo công thức, ta có:  FRL LRUM   )\(\ = ABCDE – ABDE = C b. Tìm một khoá K1 của P Đặt K0 = U = ABCDE K1 = K0 – E = ABCD vì (K0 - E)+ = U và D E K2 = K1 – D = ABC vì (K1 - D)+ = U và BC D K3 = K2 = ABC vì (K2 - C)+  U K4 = K3 – B = AC vì (K3 - B)+ = U và A B K5 = K4 = AC vì (K4 - A)+  U Vậy khoá K1 của P là AC. c. P còn khoá khác ngoài khoá K1 vì: M+ = C+ = C  U nên lược đồ có hơn một khoá. Dễ thấy rằng, ngoài khoá K1, lược đồ còn có khoá K2 = BC vì thoả mãn 2 điều kiện sau: (i) K+ = BC+ = ABCDE = U (ii) BC tối tiểu ( theo nghĩa (K \ {BC})+  U ). Tương tự, ta còn tìm được khoá thứ 3 của lược đồ quan hệ P như sau: K3 = CD. d. Xác định tập các thuộc tính không khoá U0 của P. - Thuộc tính khoá là thuộc tính có mặt trong mọi khoá, ký hiệu là Uk. - Thuộc tính không khoá là thuộc tính không có mặt trong bất cứ khoá nào, ký hiệu U0. Ta có: Uk = ABCD,  U0 = E. 1.7 Chuẩn hóa LĐQH trên cơ sở PTH 1.7.1 Các dạng chuẩn a. Dạng chuẩn 1 (1NF) LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn 1 (1NF) nếu mọi thuộc tính trong U đều không phải là thuộc tính phức hợp (điều này có nghĩa là những thuộc tính này không thể chia nhỏ được nữa bằng các phép toán quan hệ). b. Dạng chuẩn 2 (2NF) LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn 2 (2NF) nếu p là lược đồ 1NF và mọi thuộc tính không khoá phụ thuộc đầy đủ vào mọi khoá.  A  U0, K  Key (p): K+  A c. Dạng chuẩn 3 (3NF) LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn 3 (3NF) nếu p là lược đồ 1NF và mọi thuộc tính không khoá đều phụ thuộc trực tiếp vào mọi khoá.  A  U0, K  Key (p): K*  A LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn 3 (3NF) nếu p là lược đồ 1NF và mọi PTH không tầm thường X  A, A là thuộc tính không khoá đều cho ta X là một siêu khoá.  (X A, A  U0 \ X)  X+ = U d. Dạng chuẩn BCNF (Boyce - Codd) LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn BCNF nếu p là lược đồ 1NF và mọi thuộc tính đều phụ thuộc trực tiếp vào mọi khoá.  A  U, K  Key (p): K*  A LĐQH p = (U,F) được gọi là lược đồ ở dạng chuẩn BCNF nếu p là lược đồ 1NF và mọi PTH không tầm thường X  Y đều cho ta X là một siêu khoá.  (X Y, Y \ X  )  X+ = U 1.7.2 Định nghĩa phép tách Cho lược đồ quan hệ p = (U,F). Một phép tách trên tập thuộc tính U là một họ các tập con của U,  = (X1, X2, ..., Xk) thoả tính chất  K i i UX 1  . Phép tách  = (X1, X2, ..., Xk) trên tập thuộc tính U được gọi là không tổn thất (hoặc không mất thông tin ) đối với tập PTH F nếu : R(U)  SAT(F) : R[X1] * R[X2] * ... * R[Xk] = R. Ngược lại, nếu không tồn tại đẳng thức thì ta gọi  là phép tách tổn thất. 1.7.3 Thuật toán chuẩn hoá 3NF không tổn thất và bảo toàn PTH Algorithm 3NF Function: Chuẩn hoá 3NF không tổn thất và bảo toàn PTH Input: - LĐQH p = (U,F) Output: - Các LĐQH 3NF (U1,K1),(U2,K2),...,(Us,Ks) thoả i) RSAT(F): R[U1] * R[U2] * ... * R[Us] = R ii) K1, K2, ..., Ks là các khoá của các lược đồ tương ứng iii) Tập PTH F được bảo toàn Method 1. Tìm khoá K của p 2. Tìm phủ tối thiểu của F G = {K1A1, K2A2, ..., KmAm } 3. Ghép các PTH có cùng vế trái trong G để thu được phủ G = {K1X1, K2X2, ..., KsXs } 4. Xét phép tách  = (K1X1, K2X2, ..., KsXs). Nếu khóa K không có mặt trong thành phần nào của  thì thêm thành phần K vào . 5. Return {(K1X1,K1), (K2X2, K2), ..., (KsXs, Ks)} End 3NF. 1.7.4 Ví dụ a. Ví dụ 1 : Chuẩn hoá 3NF LĐQH p = (U,F) sau : U = ABCDEGH F = { A  C DH  A DC  H AE  G DE  H } Bước 1: Tìm một khoá Ta có, giao các khoá  FRL LRUM   )\(\ = ABCDEGH \ ACGH = BDE. Tính M+ = (BDE)+ = ABCDEGH = U. Vì M+ = U nên lược đồ p có một khoá duy nhất là K = BDE. Tập các thuộc tính khoá Uk = BDE, tập các thuộc tính không khoá U0 = ACGH Bước 2 : Vì bộ phận thực sự của khoá K là DE và DE  H, H  U0 nên p không ở dạng 2NF và do đó cũng không ở dạng 3NF. Bước 3: Để ý rằng, F đã ở dạng tối tiểu, ta có:  = (AC, DHA, DCH, AEG, DEH) Khoá K = BDE không có trong thành phần nào của  nên ta thêm K vào để thu được kết quả sau: Lược đồ Khoá AC A DHA DH DCH DC AEG AE DEH DE BDE BDE b. Ví dụ 2: Chuẩn hoá 3NF cơ sở dữ liệu sau : SV (SV#, HT, NS, QUE, HL) DT (DT#, TDT, CN, KP) SD (SV#, DT#, NTT, KM, KQ) với các tập PTH sau: FSV = {SV#  HT, NS, QUE, HL} FDT = {DT#  TDT, CN, KP} FSD = {SV#, DT#  NTT, KQ; NTT  KM} Giải: Hai quan hệ SV và DT chỉ có 1 khoá đơn (1 thuộc tính) tương ứng là SV# và DT# và hai tập PTH tương ứng chỉ chứa 1 PTH nên hai quan hệ này ở BCNF. Quan hệ SD có 1 khoá là K = SV# DT#. SD không ở 3NF vì có phụ thuộc bắc cầu của thuộc tính không khoá KM vào khoá K. Ta chuẩn hoá SD như sau: 1. Tách SV#, DT#  NTT SV#, DT#  KQ NTT  KM 2. Tìm phủ tối thiểu G = {SV#, DT#  NTT; SV#, DT#  KQ; NTT  KM} 3. Gộp: Gộp lại ta thu được F. Thành phần thứ nhất chứa khoá {SV#, DT#}. 4. Kết quả:  = ({ SV#, DT#, NTT, KQ}, {NTT, KM}) Ta thu được hai quan hệ : SD ( SV#, DT#, NTT, KQ) với khoá K = SV#, DT# Và NK ( NTT, KM ) với khoá là NTT. c. Ví dụ 3 Xác định và giải thích dạng chuẩn cao nhất của LĐQH sau: p = (U,F), U = ABCD, F = {A C, D B, C ABD} Ta thấy: LĐQH p có hai khoá là A và C vì A+ = C+ = ABCD = U. Tập thuộc tính khoá là UK = AC, tập thuộc tính không khoá Uo = BD. Ta có DB, B là thuộc tính không khoá, D không phải là siêu khoá đó do đó a không ở 3NF đương nhiên không ở BCNF. Vì hai khoá A và C đều chỉ có một thuộc tính nên các thuộc tính không khoá khác là B và D đều phụ thuộc đầy đủ vào hai khoá này. Vậy a ở 2NF. CHƯƠNG II: KỸ THUẬT THU GỌN LƯỢC ĐỒ QUAN HỆ 2.1 Định nghĩa kỹ thuật thu gọn LĐQH Cho hai LĐQH p = (U,F), q = (V,G) và tập thuộc tính M  U. Ta nói LĐQH q nhận được từ LĐQH p qua phép thu gọn theo tập thuộc tính M, nếu sau khi loại bỏ mọi xuất hiện của các thuộc tính của M trong lược đồ p thì thu được lược đồ q. Nếu sau khi thực hiện phép thu gọn theo M cho LĐQH p ta thu được LĐQH q thì ta viết q = p\M. Thao tác loại bỏ M được thực hiện trên lược đồ p = (U,F) để thu được lược đồ q = (V,G) như sau: 1. Tính V = U\M có độ phức tạp O(n) với n là số lượng thuộc tính trong U. 2. Mỗi PTH XY trong F ta tạo ra PTH X\MY\M cho G. Thủ tục này ký hiệu là G = F\M. Tính F\M đòi hỏi độ phức tạp O(mn) với m là số lượng PTH trong F. Như vậy q = p\M = (U\M,F\M) được thực hiện với độ phức tạp O (mn), tức là tuyến tính theo chiều dài dữ liệu vào (của LĐQH p). Sau khi thực hiện thủ tục G = F\M nếu: - G chứa PTH tầm thường (dạng XY, XY) thì ta loại các PTH này khỏi G. - G chứa các PTH trùng lặp thì ta bớt các PTH này.  Ví dụ 1: Cho LĐQH p = (U, F); U = abcdefg F = {abc  de, bcd  ag, de  fc, ce  fg} Với M = cfg, hãy xác định q = (V,G) = p\M. Ta có: V = U \ cfg = abcdefg \ cfg = abde G = { ab  de, bd a, de  , (Loại) e  , (Loại) } = {ab  de, bd a } Ta cũng dễ nhận thấy kỹ thuật thu gọn LĐQH thoả tính hợp thành và giao hoán, cụ thể nếu p là LĐQH trên tập thuộc tính U và X, Y là hai tập con rời nhau của U thì p\XY = (p\X)\Y = (p\Y)\X 2.2 Thuật toán thu gọn LĐQH Algorithm Translation Format: Translation (p,M) Input: - LĐQH p = (U,F) - Tập thuộc tính M U Output: - LĐQH q = (V,G) = p\M, V = U\M, G = F\M. Method V := U\M; G :=  For each FD LR in F do G := G  {L\MR\M}; Endfor; G := Natural_Reduced(G); Return (V,G); End Translation. Thủ tục Natural_Reduced(G) đưa tập PTH G về dạng thu gọn tự nhiên bằng cách loại khỏi G những PTH tầm thường (có vế trái chứa vế phải), chuyển đổi mỗi PTH có hai vế trái phải rời nhau và gộp các PTH có cùng vế trái.  Ví dụ 2: Cho LĐQH p = (U,F), U = ABCDEH F={ AE  D, A  DH, BC  E, E  BC} Với M = ADH, hãy xác định q = (V,G) = p\M ? Ta có: V = U\ADH = ABCDEH\ADH = BCE, G = {E   (loại) ,    (loại), BC  E, E  BC} = {BC  E, E  BC} Ta nhận thấy phép thu gọn thoả tính hợp thành và giao hoán, cụ thể nếu p là LĐQH trên tập thuộc tính U và X, Y là hai tập con rời nhau của U thì p\XY = (p\X)\Y = (p\Y)\X  Ví dụ 3 : Cho LĐQH p = (U,F), U = ABCDEH F= {AE  D, BC  E, E  BC } Để tìm tập khoá Key (p) của lược đồ p chúng ta xây dựng một lược đồ q bằng cách xoá khỏi lược đồ p các thuộc tính A,D,H. Ta thu được lược đồ q = (V,G) trong đó: V = U \ ADH = ABCDEH \ ADH = BCE, G = { E (loại), BCE, EBC} = { BCE, EBC} Ta dễ dàng tìm được Key (q) = {BC,E}. Để thu được Key (p) ta chỉ việc thêm tập thuộc tính AH (không thêm D) vào mỗi khoá của lược đồ q. Vậy Key (p) = {AHBC, AHE}. Dù F đã là tập PTH tối ưu theo nghĩa chứa ít ký hiệu nhất, nhưng G còn chứa ít ký hiệu hơn F.  Ví dụ 4 : Cho LĐQH p = (U,F), Với tập thuộc tính U = ABCDEIH. Tập thuộc tính F = {AD, ABDE, CEI, EH} Tính Key (p)? Để tìm tập khoá của p bằng cách thu gọn LĐQH p theo M= ABC. Ta thu được LĐQH q = p\M = (V,G). V= U \ M = ABCDEIH \ ABC = DEIH. G = F \ M = {D, DE, EI, EH} = {DE, EIH} Ta dễ dàng suy ra Key (q) = . Để thu được Key (p), ta chỉ cần thêm vào Key (q) các thuộc tính vừa thu gọn ABC. Ta được Key (p) =ABC.  Ví dụ 5 : Cho LĐQH p = (U,F). Với tập thuộc tính U =ABCDEH. Tập PTH F = {AB  C, C  A, BC  D, ACD  B, D  EH, BE  C, CH  BD, CE  CH}. Tìm Key(p)? Ta thu gọn lược đồ quan hệ p theo thuộc tính C. Thu được LĐQH: q = p\C = (V,G). V = ABDEH. G = {AB   (loại),   A, B  D, AD  B, D  EH, BE   (loại), H  BD, EH } = {   A, BD, ADB, DEH, HBD, EH}. Ta tìm được khóa của lược đồ q Key (q)={B,D,E,H}. Để thu được Key(p), ta thêm thuộc tính C vào khoá của lược q. Ta được Key (p) = {BC, DC, EC, HC}. 2.3 Định lý thiết lập công thức biểu diễn bao đóng của tập thuộc tính theo phép thu gọn lược đồ quan hệ Cho LĐQH a=(U,F) và hai tập con rời nhau X và Y trong U. Khi đó (XY)+F = XY+F\X . Chứng minh Đặt V=U\X và G=F\X. Do XY= và X không xuất hiện trong V và G nên theo định nghĩa bao đóng của tập thuộc tính ta có XY+G = . Chứng minh bằng quy nạp theo số bước xây dựng các dãy (XY)(h) và Y(h), h =0,1, ... theo thuật toán bao đóng của các tập thuộc tính XY và Y tương ứng với các tập PTH F và G. Cụ thể ta chứng minh bất biến (XY)(h) = XY(h), h = 0,1,... - Cơ sở: h = 0. Ta có (XY)(0) = XY và Y(0) = Y, do đó (XY)(0) = XY(0) = XY - Quy nạp: Giả sử với h0 ta có (XY)(h) = XY(h). Ta cần chứng minh: (XY)(h+1) = XY(h+1) - Ta sẽ chỉ ra rằng khi chuyển từ bước h sang bước h+1 thì hai tập (XY)(h) và XY(h) sẽ được bổ sung thêm cùng một số thuộc tính. Đầu tiên, do XY= và X không có mặt trong LĐQH p = p\X = (V,G) nên với mọi h = 0,1,2,... ta luôn có XY(h) = . Ngoài ra do dãy (XY)(h) đơn điệu không giảm và (XY)(0) = XY X nên với mọi h = 0,1,2,... ta luôn có (XY)h  X. Từ các nhận xét này và từ giả thiết quy nạp (XY)(h)=XY(h) ta suy ra LU: L(XY)(h) = XY(h)  L\X  Y(h) và ZU\X: ZY(h)  XZXY(h)=(XY)(h) Giả sử PTH LRF thoả tính chất L(XY)(h). Khi đó L\XR\XG và L\XY(h). Từ (XY)(h) = XY(h) ta suy ra R(XY)(h) = RXY(h) = (R\X)XY(h). Ngược lại, giả sử ZPG và ZY(h). Theo định nghĩa của phép thu gọn theo X, trong F, tồn tại một PTH LR để Z=L\X và P=R\X. Khi đó ta có L XZXY(h)=(XY)(h) và do đó: R(XY)(h) = RXY(h) = (R\X)XY(h) = PXY(h). Ta thấy, với mọi tập X, ta có X=X và X = . Từ nhận xét này ta suy ra hệ quả sau: Cho LĐQH p = (U,F) và tập XU. Khi đó X+F =X()+F/X.  Ví dụ 6: Cho LĐQH a = (U,F). U=ABCDEH. F = {AED, BCE, EBC}. Tính: (CE)+, (AHE)+ và E+ ? Áp dụng hệ quả về công thức tính bao đóng cho mọi tập thuộc tính, ta có: 1. (CE)+F = CE()+F\CE. G = F\CE={AD, B (loại), B}  {AD, B}. Từ đây ta tính được ()+G = B. Do đó (CE)+ = BCE 2. (AHE)+F = AHE()+F\AHE. G = F\AHE={D, BC (loại), BC}  {BCD}. Từ đây ta tính được ()+G = BCD. Do đó (AHE)+ = U 3. E+ = E()+F\E G = F\E={AD, BC (loại), BC}{AD, BC}. Từ đây ta tính được ()+G = BC. Do đó E+ = EBC.  Ví dụ 7: Cho LĐQH a= (U,F). U =ABCDEHKIL F = {ABC, DEH, HKI, EAB} Tính (DHE)+ , (ABDE)+ ? 1. Tính (DHE)+ Áp dụng hệ quả của công thức bao đóng ta có: (DHE)+ = DHE()+F\DHE . G = F\DHE = {ABC, , KI, AB} Suy ra ()+F\DHE = ABKI Vậy (DHE)+ = DHEABKI. 2. Tính (ABDE)+ Áp dụng hệ quả của công thức bao đóng: X+ = X()+F\X Ta có (ABDE)+ = ABDE()+F\ABDE G = F\ABDE = {C, H, HKI,  (loại)} = {CH, HKI}. Suy ra ()+F\X = CH Vậy (ABDE)+ = ABCDEHKI. 2.4 Bổ đề về siêu khoá trong phép thu gọn LĐQH Cho hai LĐQH p = (U,F), q = (V,G) và X  U. Biết q = p\X. Khi đó: i) Nếu M là siêu khóa của p thì M \ X là siêu khoá của q. ii) Nếu Z là siêu khoá của q thì ZX là siêu khoá của p. Nói riêng nếu XUo và Z là siêu khoá của q thì Z là siêu khoá của p. Chứng minh i) Giả sử M là siêu khoá của a. Đặt P = M\X, ta có XP =  và M  XP. Vì M là siêu khoá của p, vận dụng tính đồng biến của bao đóng và công thức biểu diễn bao đóng ta có, U = XV = M+F  (XP)+F = XP+F\X. Từ đẳng thức XV = XP+F\X, XV= và XP+F\X =  ta suy ra P+F\X = V. Vậy P = M\X là siêu khoá của q. ii) Đảo lại, giả sử Z là siêu khóa của q = p\X. Khi đó ZX =  và Z+G = V. Đặt M = XZ, ta có M+F = (XZ)+F = XZ+F\X = XZ+G = XV = U. Vậy XZ là siêu khoá của p. Nếu XUo thì ta có thể loại bỏ XZ bộ phận thuộc tính không khoá X để thu được Z là siêu khoá của p.  Ví dụ 8: Cho LĐQH p = (U,F). Với U = ABCDEHKI. F = {ABC, CDEH, HK}  Ta có siêu khoá Key(p) = ABI. Ta thu gọn p theo X = BI ta được lược đồ q = p\BI = (V,G) V = ABCDEHKI\BI = ACDEHK G = {AC, CDEH, HK}  Ta có siêu khoá Key(q) = A Ta kiểm tra Key(p)\BI = ABI\BI = A = Key(q) Hay nói cách khác Key(p) = Key(q)X = ABI. 2.5 Hệ quả về siêu khoá trong phép thu gọn LĐQH Cho LĐQH p = (U,F) và tập thuộc tính X  U. Khi đó nếu Z là siêu khoá của lược đồ p\X+ thì XZ là siêu khoá của lược đồ p.  Ví dụ 9: Cho LĐQH p = (U,F). Với U = ABCDEHKI F = {ABC, CDEH, HK} Ta dễ dàng tính được siêu khoá Key(p) = ABI. Cho X = AB suy ra X+ = (AB)+ = ABCDEHK. Ta thu gọn lược đồ p theo X+ = ABCDEHK ta thu được lược đồ q = p\X+ = p\ABCDEHK = (V,G). V = U\BI = ABCDEHKI\ABCDEHK = I. G = F\ABCDEHK = { (loại) ,  (loại) ,  (loại)} Ta tính được siêu khoá Key(q) = I. Như vậy Key(p) = Key(q)X = ABI. 2.6 Bổ đề về khoá trong phép thu gọn LĐQH Cho hai LĐQH p = (U,F), q = (V,G) và tập thuộc tính X  Uo. Biết q = p\X. Khi đó Key(p) = Key(q). Chứng minh Giả sử K Key(p). Khi đó nói riêng K là siêu khoá của p. Do K  UK, X  Uo, UK Uo =  nên theo bổ đề về siêu khóa trong phép thu gọn LĐQH, K = K\X là siêu khoá của q. Giả sử K chứa siêu khoá M của q. Khi đó lại theo bổ đề về siêu khoá trong phép thu gọn LĐQH ta có M là siêu khoá của p. Do K là khoá của p, M là siêu khoá của p chứa trong K, nên theo tính chất tối thiểu của khoá ta phải có M = K. Vậy K là khoá của q. Đảo lại, nếu K là khóa của q thì KX= và theo bổ đề về siêu khoá trong phép thu gọn LĐQH ta có M\X là siêu khoá của q. Do K là khoá của q và K chứa M nên M = K . Vậy K là khoá của p.  Ví dụ 10: Cho LĐQH p = (U,F). Với U = ABCDEHIK. F={ABC, CEH, HAB} Ta có Key(p) = HDIK. Ta tính được UK = HDIK suy ra Uo = U\UK = ABCE. Ta thu gọn lược đồ p theo ABCE được lược đồ q = (V,G) với V = U\ABCE = DHIK. G = F\ABCE = { (loại), H, H(loại)} Ta tính được Key(q) = HDIK. Vậy Key(p) = Key(q). 2.7 Định lý thứ nhất về cách biểu diễn khoá Nếu thu gọn LĐQH p = (U,F) theo tập XU để nhận được LĐQH q = p\X thì: 1. Key(p) = Key(q) khi và chỉ khi XUo 2. Key(p) = XKey(q) khi và chỉ khi XUI Chứng minh 1. Giả sử Key(p) = Key(q), AX và AUo. Theo phân hoạch của các thuộc tính trong U, AUK thì phải tồn tại một khoá K trong Key(p) để AK. Do Key(p) = Key(q) nên K = Key(q). Từ đây ta suy ra K  U\X hay là KX = . Điều chỉnh mâu thuẫn với AK và AX. Vậy ta phải có XUo (Suy từ bổ đề về khoá trong phép thu gọn LĐQH). 2. Đẳng thức Key(p) = XKey(q) cho biết X có mặt trong mọi khoá của p, tức là XUI. Giả sử XUI. Ta sẽ chứng minh rằng mọi khoá KKey(p) đều được biểu diễn dạng XM, trong đó MKey(q) và ngược lại, nếu MKey(q) thì MXKey(p). Cho K=Key(p). Khi đó , vì XUI nên X phải có trong mọi khoá của p, nói riêng X K. Đặt M=K\X, ta có MX= và K=XM. Theo bổ đề về siêu khoá trong phép thu gọn LĐQH ta suy ra M=K\X là siêu khoá của q. Giả sử M chứa một siêu khoá P của q. Khi đó XP lại là siêu khoá của p và XPK. Vì K là khoá của p nên XP = K = XM. Để ý rằng XP = XM = , ta suy ra P = M. Vậy M là khoá của q. Cho MKey(q). Ta có XM = . Theo bổ đề về siêu khoá trong phép thu gọn LĐQH thì XM là siêu khoá của p. Gọi K là khoá của p chứa trong siêu khoá XM. Lại theo bổ đề về siêu khoá trong phép thu gọn LĐQH, K\X là siêu khoá của q. Vì K là khoá của p và X  UI nên X  K. Từ đây suy ra K\X=M, hay K = XM. Điều này chứng tỏ XM là khoá của p.  Ví dụ 11: 1. Cho LĐQH p = (U,F). Với U = ABCDEH. F={AED, BCE} Gọi UI là giao các khoá. Ta có: UI = ABCDEH\DE = ABCH. Đặt q = (V,G) với V=U\ABCH = DE, G=F\ABCH={ED, E}. Ta tính được Key(q) = {}. Vậy Key(p) = ABCH  Key(q) = {ABCH} 2. Với lược đồ đã cho ta tính được UK = ABCH, suy ra Uo=U\UK =ABCDEH\ABCH = DE. Đặt c = p\DE = (P,W). P = U\DE = ABCH. W = F\DE = {A(loại), BC(loại)}  . Do đó Key(c) = ABCH. Theo định lý thứ nhất về cách biểu diễn khoá, vì Uo = DE nên Key(p) = Key(c) = ABCH.  Ví dụ 12: 1. Cho LĐQH p = (U,F). Với U = ABCDEHIK. F={ABC, CEH, HAB} Ta tính được UI = U\ABCEH = DIK. Ta thu gọn lược đồ a theo DIK ta được: LĐQH q = (V,G). V=U\DIK=ABCEH. G = {ABC, CEH, HAB} Ta tính được Key(q) = H. Vậy Key(p) = DIKKey(q) = DHIK. 2. Với lược đồ trên ta tính được UK = DHIK  Uo = U\UK = ABCDEHIK\DHIK = ABCE. Đặt c = p\ABCE =(P,W) ta có P = U\ABCE = DHIK. W=F\ABCE = { (loại) , H, H (loại)}  . Suy ra Key(c) = DHIK. Theo định lý thứ nhất về cách biểu diễn khoá, vì Uo = ABCE nên: Key(p) = Key(c) = DHIK. 2.7.1 Hệ quả về phép thu gọn LĐQH theo các bộ phận không khoá và các giao khoá Cho LĐQH p = (U,F) và các tập thuộc tính XUo, YUI. Nếu thực hiện phép thu gọn theo XY để nhận được LĐQH q = p\XY thì: Key(p) = Y  Key(q) Chứng minh Do XUo, YUI nên XY = . Đặt c = p\X, ta có q = p\XY = (p\X)\Y = c\Y. Áp dụng dạng biểu diễn thứ nhất của khoá ta thu được: Vì XUo nên Key(p) = Key(c) và do giao các khoá của c vẫn là UI Xét trong c nên Key(c) = YKey(q). Vậy Key(p) = Y  Key(q).  Ví d