Bài giảng Cơ sở dữ liệu - Chương 4: Thiết kế CSDL quan hệ - Vũ Tuyết Trinh

Nội dung text: Bài giảng Cơ sở dữ liệu - Chương 4: Thiết kế CSDL quan hệ - Vũ Tuyết Trinh

1. Nhập môn cơ sở dữ liệu Đặtvấn đề { Mục đích củachuẩn hoá là gi? { Thế nào là chuẩn? Có bao nhiêu chuẩn? 3 Ví dụ { 1 CSDL về các hãng cung ứng. Suppliers(sid, sname, city, NOE, product,quantity) Sids Sname City NOE Product quantity S1 Smith London 100 Screw 50 S1 Smith London 100 Nut 100 S2 J&J Paris 124 Screw 78 S3 Blake Tokyo 75 Bolt 100 ¾ Các vấn đề đặt ra ¾ Đề xuất các giải pháp 4 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 2
2. Nhập môn cơ sở dữ liệu Phụ thuộchàm (Functional dependencies - FD) { Đ/N Phụ thuộc hàm trong 1 quan hệ Cho z R(U) là 1 sơđồquan hệ, U là tậpcácthuộc tính. z X, Y ⊆ U X xác định hàm Y hay Y phụ thuộchàmvàoXnếu z với ∀quan hệ r xác định trên R(U) và với2 bộ t1 và t2 bấtkỳ mà t1[X] = t2[X] thì t1[Y] = t2[Y]. { Ký hiệu: X→Y 7 Ví dụ Supp(sid, sname, city, NOE) { sid→sname { sid→city { sid→NOE Supply(sid, product,quantity) { sid→product { sid→quantity 8 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 4
3. Nhập môn cơ sở dữ liệu Bao đóng của1 tậpphụ thuộc hàm { Đ/N : Bao đóng củatậpphụ thuộc hàm F là tập lớnnhất các phụ thuộc hàm có thểđược suy diễn logic từ F z Ký hiệulàF+ { Suy diễn logic X → Y được suy diễn logic từ Fnếuvớimỗi quan hệ r xác định trên R(U) thoả các phụ thuộc hàm trong F thì cũng thoả X → Y { F là họđầy đủ (full family) nếu F = F+ 11 Khoá { Đ/N: Cho lược đồ quan hệ R(U), tập các phụ thuộc hàm F. K ⊆ U, K đượcgọilàkhóa tốithiểu củaR nếunhư z KÆU ∈ F+ z với ∀ K’ ⊂ K thì K’ÆU ∉ F+ { Nhậnxét: NếuK làmột khóa tổithiểuthì z K+ = U z K là tậpthuộc tính nhỏ nhất có tính chấtnhư vậy. 12 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 6
4. Nhập môn cơ sở dữ liệu Tính bao đóng của1 tậpthuộc tính { Vào: Tậphữuhạncácthuộc tính U tậpcácphụ thuộc hàm F trên U X ⊆ U { Ra: X+ { Thuậttoán B0 X0 = X. Bi Tính Xi từ Xi-1 Nếu ∃ Y→Z ∈ F ^ Y ⊆ Xi-1 ^ A ∈ Z ^ A ∉ Xi-1 thì Xi = Xi-1 ∪ A ngượclại, Xi = Xi-1 . NếuXi ≠ Xi-1 thì thựchiệnBi ngược lai, thựchiệnBn Bn X+ = Xi 15 Tìm khoá tốithiểu { Vào: U = {A1, A2, , An} , F { Ra: khóa tốithiểuK xácđịnh đượctrênU vàF { Thuậttoán B0 K0= U i i-1 B Nếu(K\{Ai})ÆU i i-1 thì K = K \{Ai} ngượclại, Ki= Ki-1 NếuKi≠ Ki-1 thì thựchiệnBi ngược lai, thựchiệnBn Bn K = Ki 16 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 8
5. Nhập môn cơ sở dữ liệu Tậpphụ thuộc hàm tương đương { Đ/N: Tậpphụ thuộchàmF làphủ củatậpphụ thuộc hàm G hay G là phủ của F hay F và G tương đương nếuF+ = G+. z Ký hiệulàF ≈ G { Kiểmtratínhtương đương của2 tậpphụ thuộc hàm B.1. VớimỗiY→Z ∈ F, Z ⊆ Y+ (trên G) thì Y→Z ∈ G+ Nếuvới ∀f ∈ F, f ∈ G+ thì F+ ⊆ G+ B.2. Tương tự, nếu ∀ f ∈ G, f ∈ F+ thì G+ ⊆ F+ B.3. NếuF+ ⊆ G+ và G+ ⊆ F+ thì F ≈ G 19 Tậpphụ thuộc hàm không dư thừa { Đ/N: Tậpphụ thuộchàmF làkhông dư thừa nếu!∃ XÆY∈ F sao cho F \ {XÆY} ≈ F. { Tìm phủ không dư thừacủa1 tậpphụ thuộc hàm z Vào: Tậpthuộc tính U, F = {Li ÆRi: i = 1 n} z Ra : Phủ không dư thừaF’củaF z Thuật toán B0 F0= F i i-1 i-1 B NếuF\{LiÆRi} ≈ F i i-1 thì F = F \{LiÆRi} ngượclại, Fi = Fi-1 NếuFi≠ Fi-1 thì thựchiệnBi ngượclại, thựchiệnBn 20 Bn F’ = Fi Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 10
6. Nhập môn cơ sở dữ liệu Mục đích củathiếtkế CSDL – nhắclại { Xác định được1 tậpcáclược đồ quan hệ cho phép tìm kiếm thông tin mộtcáchdễ dàng, đồng thời tránh đượcdư thừadữ liệu (cf. slide 7) ¾ Phát biểulạimục đích này sử dụng các khái niệmvừahọc? 23 Phép tách các lược đồ quan hệ { Mục đích z Thay thế mộtsơđồquan hệ R(A1, A2, , An) bằng mộttậpcácsơđồcon {R1, R2, , Rk} trong đóRi ⊆R và R = R1 U R2 U U Rk { Yêu cầucủaphéptách z Bảo toàn thuộc tính, ràng buộc z Bảo toàn dữ liệu 24 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 12
7. Nhập môn cơ sở dữ liệu Phép tách bảo toàn tậpphụ thuộchàm { Hình chiếucủatậpphụ thuộchàm Cho sơđồquan hệ R, tậpphụ thuộc hàm F, phép tách {R1, R2, , Rk} của R trên F. Hình chiếu Fi của F trên Ri là tậptấtcả XÆY ∈ F+ : XY ⊆ Ri . { Phép tách sơđồquan hệ R thành {R1, R2, , Rk} là một phép tách bảo toàn tậpphụ thuộc hàm F nếu (F1 ∪ F2 ∪ Fk)+ = F+ hay hợpcủatấtcả các phụ thuộchàmtrongcáchình chiếucủaF lêncácsơđồcon sẽ suy diễnracácphụ thuộc hàm trong F. 27 Bài tập { Kiểmtraxem1 phéptáchcóbảo toàn tậpphụ thuộc hàm không { Kiểm tra xem 1 phép tách có mất mát thông tin không 28 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 14
8. Nhập môn cơ sở dữ liệu Dạng chuẩn2 (2NF) { Đ/N: Mộtsơđồquan hệ R đượccoilàở dạng chuẩn2 nếu z Sơđồquan hệ này ở 1NF z Tấtcả các thuộc tính không khóa đều phụ thuộchàm đầy đủ vào khóa chính (Lưuý, A làmộtthuộc tính khóa nếu A thuộcmột khóa tốithiểu nào đócủaR. Ngượclại A là thuộctính không khóa) 31 Phụ thuộchàmđầy đủ { Đ/N: Cho lược đồ quan hệ R(U), F là tậpphụ thuộc hàm trên R. X, Y ⊆ U. Y đượcgọilàphụ thuộc đầy đủ vào X nếu: -XÆY thuộcF+ -!∃ X’ ⊂ X : X’ÆY ∈ F+ { Các phụ thuộc hàm không đầy đủ còn gọilà phụ thuộcbộ phận 32 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 16
9. Nhập môn cơ sở dữ liệu Ví dụ S (sid, sname, city) Sales(sid, item, price) F = {sid Æ sname, city} ¾ S, Sales thuộcdạng chuẩn3 ItemInfo(item, price, discount). F = {itemÆprice, priceÆdiscount} { thuộc tính không khóa discount phụ thuộcbắccầuvào khóa chính item. ¾ Vậy quan hệ này không ở 3NF. ¾ Chuẩn hoá ItemInfo(item, price) Discount(price, discount) 35 Dạng chuẩn Boye-Codd { Đ/N: Mộtsơđồquan hệ R(U) vớimộttậpphụ thuộc hàm F đượcgọilàở dạng chuẩn Boye-Codd (BCNF) nếuvới ∀ XÆA ∈ F+ thì z A là thuộc tính xuấthiện trong X hoặc z X chứamột khóa củaquanhệ R. { Ví dụ z R = {A,B,C} ; F = {ABÆC , CÆB}. z R không phải ở BCNF vì ∃ CÆB, C không phải là khóa { Chú ý: z Một quan hệ thuộc3NF thìchưachắc đãthuộcBCNF. Nhưng một quan hệ thuộc BCNF thì thuộc3NF 36 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 18
10. Nhập môn cơ sở dữ liệu Tách không mất mát thông tin và bảo toàn tậpphụ thuộc hàm về 3NF { Yêu cầu: z Bảo toàn tậpphụ thuộchàm(như thuật toán trên) z Đảmbảolàcómộtlược đồ con chứa khóa của lược đồ đượctách { Các bướctiến hành B1. Tìm một khóa tốithiểucủalược đồ quan hệ R đã cho B2. Tách lược đồ quan hệ R theo phép tách bảo toàn tậpphụ thuộc B3. Nếu 1 trong các sơđồcon có chứakhóatốithiểu thì kếtquả củaB2 làkếtquả cuối cùng. Ngượclại, thêm vào kếtquảđómộtsơđồquan hệ đượctạobởi khóa tốithiểu tìm được ở 1. 39 Ví dụ Cho R(A,B,C,D,E,F,G). F = {AÆB, ACDÆE, EFÆG} B1. Khóa tốithiểucần tìm là ACDF (xem slide 19) B2. Phép tách bảo toàn tậpphụ thuộc hàm R cho 3 sơđồcon R1(AB), R2(ACDE), R3(EFG) (xem slide 40) B3. Do khóa ACDF không nằm trong bấtkỳ mộtsơđồcon nào trong 3 sơđồcon trên, ta lậpmộtsơđồcon mới R4(ACDF) Kếtquả cuối cùng ta có phép tách R thành 4 sơđồcon {R1, R2, R3, R4} là một phép tách không mất mát thông tin và bảo toàn tậpphụ thuộc hàm 40 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 20
11. Nhập môn cơ sở dữ liệu Hệ tiên đề đốivớicácphụ thuộc hàm và phụ thuộc đatrị Cho R(U), X, Y, Z, W ⊆ U (XY = X ∪ Y) { A1: PhảnxạđốivớiFD(reflexivity): NếuY ⊆ X thì X→Y. { A2: Tăng trưởng đốivớiFD(augmentation): NếuX→Y thì XZ→YZ. { A3: Bắccầu đốivớiFD(transitivity): NếuX→Y, Y→Z thì X→Z. { A4: LuậtbùđốivớiMVD(complementation): NếuX→→Y thì X→→U \ XY. 43 Hệ tiên đề đốivớicácphụ thuộc hàm và phụ thuộc đatrị (2) Cho R(U), X, Y, Z, W ⊆ U (XY = X ∪ Y) { A5: Tăng trưởng đốivớiMVD(augmentation): NếuX→→Y và V⊆W thì WX→→VY. { A6: Bắccầu đốivớiMVD(transitivity): NếuX→→Y, Y→→Z thì X→→Z \Y. { A7: NếuX→Y thì X→→Y. { A8: NếuX→→Y, W→Z vớiZ ⊆ Y và W∩Y=∅ thì X→Z. 44 Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 22
12. Nhập môn cơ sở dữ liệu Tính cơ sở phụ thuộc { Vào: Tậpcácphụ thuộc đatrị M trên tậpthuộctínhU vàtập thuộc tính X ⊆ U. { Ra: Cơ sở phụ thuộccủaX đốivớiM. { Cách tiến hành: B1. ĐặtT làtậpcáctập con Z củaU: vớiW→→Y ∈ M mà W⊆X thì Z là Y \ X hoặc U \ XY. B2.T đượcthiếtlậpchotớikhilàmộttậpcáctậprời nhau, nếucómộtcặp Z1, Z2 không tách rời nhau thì thay chúng bởi Z1\ Z2, Z2 \ Z1, Z1∩ Z2 với điềukiện không ghi nhận tậprỗng. GọiS làtậpthuđượcsaubước này. B3.Tìmcácphụ thuộccódạng V→→W trong M và mộttậpY trong S : Y ∩ W ≠∅, Y ∩ V = ∅ Thay Y bằng Y∩W và Y \ W cho đếnkhikhôngthayđổiS đượcnữa. B4.Tập S thu đượcsaubước này là cơ sở phụ thuộccủaX. 47 Phép tách không mất thông tin { Vào: R(A1, A2, , An), F, M, phép tách {R1, R2, , Rk} { Ra: phép tách là mất mát thông tin hay không { Thuậttoán(tổng quát hoá thuật toán trình bày ở slide 28) B.1. Thiếtlậpmộtbảng k hàng, n cột (xem B1. slide 28) B.i. Xét f = XÆY ∈F: thựchiện đồng nhấtbảng (xem B2. slide 28) Xét X→→Y: nếu ∃ 2 hàng t1, t2 thuộcbảng : t1[X] = t2[X] thì thêm vào bảng đómột hàng mớiu u[X]=t1[X], u[Y]=t1[Y], u[R \ XY] = t2[R \ XY] Lặpchotớikhikhôngthể thay đổi đượcgiátrị nào trong bảng B.n. Nếubảng có 1 hàng gồmcáckíhiệua1, a2, , an thì phép tách là không mất mát thông tin. ngượclại, phép tách không bảo toàn thông48 tin. Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN 24