Bài giảng Cơ sở dũ liệu - Chương 11: Phân rã lược đồ (Decomposition)

ệ r nữa mà chỉ lưu lại các quan hệ chiếu của nó r1,.. , rn. CSDL phải có khả năng khôi phục lại quan hệ gốc r từ các quan hệ chiếu này.Nếu không khôi phục lại được quan hệ r thì việc phân rã không biểu diễn cùng 1 thông tin với CSDL gốc  Phân rã mất mát (lossy decomposition)6Phân rã không mất mát( Lossless decomposition)Phân rã lược đồ R = (U,F) thành 1 tập hợp các lược đồ 	R1 = (U1,F1) R2= (U2, F2). Rn = (Un,Fn)Không mất mát (lossless) nếu với mỗi điển hình (instance) hợp lệ r của lược đồ R thì 	r = r1 r2 .. rn Với r1 = U1(r)	 r2 = U2(r),. 	 rn = Un(r) 7Phân rã không mất mát( Lossless decomposition)Thực tế sẽ nhận được nhiều bộ (tuple) từ phép kết các r1, r2,,rn hơn là các bộ gốc ban đầu  Vậy tại sao lại gọi là mất mát (lossy)??Tuy nhiều bộ hơn nhưng lại thiếu thông tin và không có cách nào biết được bộ nào là đúng, bộ nào là không đúng với bộ gốc.Nhiều bộ hơn nhưng không đúng  mất mát thông tin8Phân rã nhị phân( Binary Decomposition)Cho lược đồ R = (U,F) và R1 = (U1,F1) , R2= (U2, F2) là một phân rã nhị phân của R. Sự phân rã này không mất thông tin nếu và chỉ nếu thỏa mãn một trong các điều kiện sau:(U1  U2)  U1  F+(U1  U2)  U2  F+9Ví dụXét lược đồ quan hệPERSON(SSN, Name, Address,Hobby)SSNNameAddressHobby1111111John123 Main St.Stamps1111111John123 Main St.Coins5556667Mary7 Lake Dr.Hiking5556667Mary7 Lake Dr.Skating9876543SimpsonFox 5 TVActing10Ví dụNếu phân rã lược đồ trên thành 2 lược đồ sau:	PERSON1(SSN, Name, Address)	HOBBY(SSN, Hobby)Việc phân rã này có mất thông tin không??11Ví dụVì PERSON1  HOBBY = {SSN} mà SSN là khóa chính của PERSON1, do đóPERSON1  HOBBY  PERSON1Phân rã này không mất thông tin12Phân rã bảo toàn phụ thuộc hàm(Dependency-Preseving Decomposition)Khảo sát lược đồ quan hệ sau:	HASACCOUNT(ClientId, OfficeId, AccountNumber)Với các FD sau:ClientId, OfficeId  AcountNumberAccountNumber OfficeIdNếu phân rã lược đồ trên thành 2 lược đồ sau:ACCTOFFICE (AccountNumber, OfficeId)ACCTCLIENT (AccountNumber, ClientId)Phân rã trên có mất mát thông tin không???13Phân rã bảo toàn phụ thuộc hàmPhân rã trên không mất mát thông tin vì:ACCTOFFICE  ACCTCLIENT ={AccountNumber}Mà AccountNumber là khóa chính của ACCTOFFICE,nên ACCTOFFICE  ACCTCLIENT  ACCTOFFICENhưng phân rã này không bảo toàn phụ thuộc hàm14Phân rã bảo toàn phụ thuộc hàmPhụ thuộc hàm gốc ClientId, OfficeId  AcountNumber (1) không tồn tại trong các phụ thuộc hàm của các lược đồ phân rã vì:Cả hai phụ thuộc hàm phân rã đều không chứa đủ các thuộc tính của phụ thuộc hàm gốc (1) nên không thể suy diễn lại được phụ thuộc hàm này15Phân rã bảo toàn phụ thuộc hàmCho lược đồ R = (U,F) và R1 = (U1,F1) , R2= (U2, F2),.., Rn= (Un, Fn) là phân rã của R.Phân rã được gọi là bảo toàn phụ thuộc hàm nếu và chỉ nếu F và là tương đương nhau.16Phân rã bảo toàn phụ thuộc hàmNếu 1 phụ thuộc hàm f  F nhưng không thuộc bất kỳ Fi nào không có nghĩa là phân rã không bảo toàn phụ thuộc hàm nếu f có thể được suy diễn từ Chỉ khi nào f không suy diễn được từ thì lúc đó phân rã mới không bảo toàn phụ thuộc  để duy trì f đòi hỏi phải có kết nối các lược đồ phân rã trước, kiểm tra phụ thuộc hàm sau17Ví dụPhân rã quan hệ HASACCOUNTAccountNumberClientIdOfficeIdB123111111SB01A908123456MN08AccountNumberOfficeIdB123SB01A908MN08Account NumberClientIdB123111111A90812345618Ví dụHASACCOUNT và phân rã của nó sau khi chèn thêm 1 hàngAccountNumberClientIdOfficeIdB123111111SB01B567111111SB01A908123456MN08AccountNumberOfficeIdB123SB01B567SB01A908MN08Account NumberClientIdB123111111B567111111A908123456Sau khi join 2 lược đồ phân rã lại, phụ thuộc hàm ClientId, OfficeId  AcountNumber bị vi phạm 19Phép chiếu của tập phụ thuộc hàmKhảo sát lược đồ R =(U,F), một quan hệ r trên R và 1 tập thuộc tính S  UPhép chiếu của tập F lên tập các thuộc tính S được định nghĩa như sau: S(F)={XY|XY F+ and X  Y S} 20Phân rã lược đồ quan hệ2 tính chất của phân rã:Lossless ( không mất thông tin)Dependency-preserving (bảo toàn phụ thuộc hàm)Tính chất nào quan trọng hơn??? Lossless là bắt buộc (mandatory) trong khi dependency-preserving là tùy chọn (optional) 21Giải thuật phân rã BCNFR=(U,F) là 1 lược đồ quan hệ không ở chuẩn BCNF.Giải thuật: thực hiện lặp lại việc phân chia R thành những lược đồ nhỏ hơn sao cho các lược đồ mới có ít FD vi phạm BCNF hơn. Giải thuật kết thúc khi tất cả lược đồ kết quả đều ở dạng BCNF22Giải thuật phân rã BCNFInput R = (U,F)Decomposition = RWhile có lược đồ S= (V,F’) trong Decomposition không phải BCNF	/*Nếu có XY F sao cho X  Y  S và vi phạm BCNF, dùng FD này để phân rã*/Thay S trong Decomposition với S1 = (XY, F1)S2=( (S-Y)  X, F2) với F1,F2 là tất cả các FD của F’EndReturn Decomposition23Ví dụCho R= (U,F), U={ABCDEFGH}, F= {ABH  C, ADE, BGH F, F ADH, BH GE}Tìm FD vi phạm BCNF(ABH)+ = U , ABH là siêu khóa, ABH  C không vi phạm BCNFA+  U, ADE vi phạm BCNFChia R thành R1 =(ADE, {ADE})R2 = (ABCFGH,{ABHC, BGHF, F AH, BHG})24Ví dụSau khi phân rã, chú ý đến 2 phụ thuộc hàm gốc F ADH, BH GEChia FADH thành {FAH, FD}Chia BHGE thành {BHG, BHE}FD, BHE không có chỗ trong các phân rã mới (vì không có ràng buộc nào có đủ thuộc tính cho các FD này)Nhưng FD có thể suy diễn từ FAH  R2 và ADE  R1BH E có thể suy diễn được dựa vào (BH)+ từ R1,R2 Phân rã R1,R2 bảo toàn phụ thuộc hàm25Ví dụR1 là BCNFVới R2:ABH C, BGH  F không vi phạm BCNF (ABH, BGH đều là siêu khóa)F AH vi phạm BCNF Phân rã R2 thành R21=(FAH, {FAH})R22= (FBCG, {}) R21, R22 đều là BCNF nhưng khi đó các FD ABH C, BGH  F và BHG không có mặt nữa và cùng không thể suy dẫn được từ các FD của R21, R22 và R1 Phân rã R2 không bảo toàn phụ thuộc hàm26Nhận xétViệc phân rã R thành R1, R21, R22 không phải là duy nhất.Nếu bắt đầu từ FD F ADH thì sẽ có	R1= (FADH; {F ADH})	R2 = (FBCEG,{})R1,R2 cũng ở chuẩn BCNF và 1 số FD gốc cũng bị mất, không thể suy diễn được27Tính chất của giải thuật phân rã BCNFKhông mất mát thông tinNhưng có thể không bảo toàn phụ thuộc hàmLà giải thuật không xác định (nondeterministic), phụ thuộc vào thứ tự các FD được chọn để xét phân rã	28Phủ tối thiểu – Minimal coverCho 1 tập FD F. Phủ tối thiểu của F là 1 tập FD G có các tính chất sau:G tương đương với FTất cả các FD trong G có dạng X A với A là 1 thuộc tính đơnKhông thể làm cho G nhỏ hơn (mà vẫn còn thỏa mãn 2 tính chất đầu) bằng một trong 2 cách sau:Xóa 1 FDXóa 1 thuộc tính khỏi 1 FD 29Giải thuật tìm phủ tối thiểuInput: tập phụ thuộc hàm FOutput: G là 1 phủ tối thiểu của FBước 1: G:=F, tất cả FD đều được biến đổi thành thuộc tính đơn bên phía phảiBước 2: Xóa tất cả thuộc tính dư thừa khỏi phía trái của FD trong GBước 3: Xóa tất cả các FD dư thừa khỏi GReturn G30Thuật toán để loại các FD có vế trái dư thừaBước 1: lần lượt thực hiện bước 2 cho các FD XY của FBước 2: Với mỗi tập con thật sự X’  của X. Nếu X'Y F+ thì thay XY trong F bằng X'Y, thực hiện lại bước 231Ví dụCho tập thuộc tính ABCDEFGH, và tập phụ thuộc hàm F	ABHC	AD	CE	BGHF	FAD	EF	BHE32Ví dụ (tt)Bước 1: xác định G với tất cả các FD có vế phải thuộc tính đơn	ABHC	AD	CE	BGHF	FA	FD	EF	BHE33Bước 2: Xóa tất cả thuộc tính dư thừa khỏi phía trái của FD trong G	BHC (Loại bỏ A)	AD	CE	BHF (Loại bỏ G)	FA	FD	EF	BHE34Bước 3: Xóa tất cả các FD dư thừa khỏi GLoại bỏ các FD BHF, FD và BH EG còn lại các FD sau:	BHC	AD	CE	FA	EF35Giải thuật phân rã 3NFCho lược đồ R(U,F)Bước 1: Tìm phủ tối thiểu G của FBước 2: Phân hoạch G thành các tập phụ thuộc hàm G1,..,Gn sao cho mỗi Gi chứa các FD có cùng vế tráiBước 3: với mỗi Gi, tạo 1 lược đồ (Ri, Gi) với Ri chứa tất cả thuộc tính có trong GiBước 4: Nếu một trong các Ri là siêu khóa, nghĩa là (Ri)+F = R thì kết thúc, nếu không có Ri nào là siêu khóa thì đặt Ro=(R,{}) là 1 lược đồ mới. Khi đó R0, R1,, Rn là kết quả phân rã 36Tính chất của giải thuật phân rã 3NFBảo toàn phụ thuộc hàmKhông mất thông tin37Ví dụPhủ tối thiểu G của tập F ví dụ trước:G={BHC,AD,CE,FA,EF}Phân rã thành 5 lược đồ:(BHC; {BHC})(AD; {AD})(CE; {CE})(FA; {FA})(EF; {EF})Không có lược đồ phân rã nào là siêu khóa BCGH, nên bổ sung thêm lược đồ thứ 6(BCGH;{})38Phân rã BCNF thông qua phân rã 3NFVì giải thuật phân rã BCNF có thể không bảo toàn phụ thuộc hàm nên phân rã BCNF thông qua phân rã 3NF. Nếu lược đồ sau phân rã là BCNF thì dừng, nếu không thì dùng lúc đó mới dùng giải thuật BCNF để phân rã tiếp39Ví dụXét tập thuộc tính sau: St (Student), C (course), Sem (semester), P (Professor), T (time) và R(room) và tập FD như sau:	St C Sem  P	P Sem  C	C Sem T  P	P Sem T C R	P Sem C T  R	P Sem T  C40Tìm phủ tối thiểu của FBước 1: Tách vế phải thành các thuộc tính đơn	St C Sem  P	P Sem  C	C Sem T  P	P Sem T C 	P Sem T R	P Sem C T  R	P Sem T  C41Tìm phủ tối thiểu của FBước 2: xóa các thuộc tính dư thừa ở vế tráiVì 	(St Sem)+ = {St,Sem}	 	(St C)+ = {St,C}	(C Sem)+ = {C Sem} FD thứ nhất không dư thừa vế trái Tương tự cho các FD còn lạiRiêng P Sem C T  R có C dư thừa42Tìm phủ tối thiểu của FKết quả bước 2:	FD1:	St C Sem  P	FD2:	P Sem  C	FD3:	C Sem T  P	FD4:	P Sem T C 	FD5:	P Sem T R	43Tìm phủ tối thiểu của FBước 3: loại bỏ FD dư thừaVì (ST C Sem)+{F-FD1}={ST C Sem} nên FD1 không dư thừaTương tự cho FD2, FD3, FD4FD5 dư thừa nên bị loại bỏ44Tìm phủ tối thiểu của FPhủ tối thiểu của F:	St C Sem  P	P Sem  C	C Sem T  P	P Sem T R45Phân rã 3NF bảo toàn FDPhân rã thành 4 FD như sau:	(St C Sem P; {St C Sem  P})	(P Sem C; {P Sem  C})	(C Sem T P; {C Sem T  P})	(P Sem T R; {P Sem T R})Vì không có phân rã nào hình thành siêu khóa cho lược đồ gốc, nên bổ sung thêm lược đồ mới (bước 4)	( St T Sem P; {})46Phân rã thành BCNFCác phân rã 1 và 3 không phải là BCNF vì P Sem  C nằm trong phân rã 2Phân rã 1 được tách thành 2 lược đồ mới(P Sem C; {P Sem  C})(St Sem P; {}) Phân rã tuy không mất mát thông tin nhưng không bảo toàn FD St C Sem  P47Phân rã thành BCNFPhân rã lược đồ 3 thành(P Sem C; {P Sem  C})(P Sem T; {}) Không mất mát thông tin nhưng cũng không bảo toàn FD C Sem T  P 48Phân rã thành BCNFKết quả cuối cùng:	(P Sem C; {P Sem  C})	(P Sem St)	(P Sem T)	(P Sem T R; {P Sem T R})	(St T Sem P)49