Bài giảng Cơ sở dữ liệu - Chương 4: Lý thuyết thiết kế cơ sở dữ liệu quan hệ - Nguyễn Hồng Phương
Các vấn đề đối với CSDL VD
• Dư thừa dữ liệu: Hãng nào cung ứng nhiều hơn 1
mặt hàng thì thông tin của hãng đó sẽ bị lặp lại
trong bảng (VD S1), mặt hàng được cung ứng bởi
nhiều hãng cũng bị lặp lại (VD Screw)
• Dị thường dữ liệu khi thêm: Nếu có một hãng
chưa cung cấp mặt hàng nào, vậy giá trị cho thuộc
tính product và quantity trong bộ dữ liệu mới được
thêm vào sẽ không được xác định
• Dị thường dữ liệu khi xóa: Nếu một hãng chỉ
cung cấp 1 mặt hàng, nếu ta muốn xóa thông tin
về sự cung cấp này thì ta sẽ mất thông tin về hãng
cung cấp
• Dị thường dữ liệu khi sửa đổi: Do thông tin bị
lặp lại nên việc sửa đổi 1 bộ dữ liệu có thể dẫn đến
việc không nhất quán trong dữ liệu về một hãng
nếu sơ sót không sửa đổi trên toàn bộ các bộ giá
trị liên quan đến hãng đó
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Trang 10
Tóm tắt nội dung tài liệu: Bài giảng Cơ sở dữ liệu - Chương 4: Lý thuyết thiết kế cơ sở dữ liệu quan hệ - Nguyễn Hồng Phương
suy diễn ra các phụ thuộc hàm khác • Trong một tập phụ thuộc hàm cho sẵn có thể có các phụ thuộc hàm bị coi là 20 dư thừa • Làm thế nào để có được một tập phụ thuộc hàm tốt? Tập phụ thuộc hàm tương đương • Định nghĩa: Tập phụ thuộc hàm F là phủ của tập phụ thuộc hàm G hay G là phủ của F hay F và G tương đương nếu F+ = G+. – Ký hiệu là F G • Kiểm tra tính tương đương của 2 tập phụ th ộ hà 21 u c m B.1. Với mỗi phụ thuộc hàm Y Z F, Z Y+ (trên G) thì Y Z G+ Nếu với phụ thuộc hàm f F, f G+ thì F+ G+ B.2. Tương tự, nếu phụ thuộc hàm g G, g F+ thì G+ F+ B.3. Nếu F+ G+ và G+ F+ thì F G Ví dụ • Cho lược đồ quan hệ R(U) với U = {A, B, C, D, E, F} F = {AB C, D EF, C BD} G = {AC B, D EF, B CD} Hỏi F và G có phải là 2 tập pth tương đương hay không? 22 • Thực hiện: Đối với các phụ thuộc hàm trong F – f1= AB C. AB+ (đối với G) = ABCDEF = U. Vậy f1 thuộc G+ – f2= D EF thuộc G nên chắc chắn thuộc G+ – f3= C BD. C+ (đối với G) = C không chứa BD. Vậy f3 không thuộc G+ – Kết luận F không tương đương với G Tập phụ thuộc hàm không dư thừa • Đ/N: Tập phụ thuộc hàm F là không dư thừa nếu không X Y F sao cho F \ {X Y} F. • Thuật toán 3: Tìm phủ không dư thừa của 1 tập phụ thuộc hàm – Vào: Tập thuộc tính U, F = {Li Ri: i = 1..n} 23 – Ra : Phủ không dư thừa F’ của F – Thuật toán B0 F0= F Bi Nếu Fi-1\ {Li Ri} Fi-1 thì Fi = Fi-1 \ {Li Ri} ngược lại, Fi = Fi-1 Bn+1 F’ = Fn Phủ tối thiểu của 1 tập phụ thuộc hàm • Đ/N: Fc được gọi là phủ tối thiểu của 1 tập phụ thuộc hàm F nếu thỏa mãn 3 điều kiện sau: Đk1: Với f Fc, f có dạng X A, 24 trong đó A là 1 thuộc tính Đk2: Với f = X Y Fc, ! A X (A là 1 thuộc tính): (Fc \ f) U {(X \ A) Y} Fc Đk3: ! X A Fc : Fc \ {X A} Fc CuuDuongThanCong.com https://fb.com/tailieudientucntt 1/30/2012 5 Thuật toán 4: Tìm phủ tối thiểu của một tập phụ thuộc hàm • Vào: Tập thuộc tính U, F = {Li Ri: i = 1..n} • Ra: phủ tối thiểu Fc của tập phụ thuộc hàm F • Thuật toán B.1. Biến đổi F về dạng F1={Li Aj} trong đó Aj là 1 thuộc tính bất kỳ thuộc U (thoả mãn đk1) B.2. Loại bỏ thuộc tính thừa trong vế trái của các phụ thuộc hàm Lần lượt giản ước từng thuộc tính trong vế trái của từng 25 phụ thuộc hàm trong F1 thu được F1’. Nếu F1’ F1 thì loại bỏ thuộc tính đang xét Khi không có sự giản ước nào xảy ra nữa ta thu được F2 thỏa mãn đk2 B.3. Loại bỏ phụ thuộc hàm dư thừa Lần lượt kiểm tra từng phụ thuộc hàm f. Nếu F2 \ f F2 thì loại bỏ f Khi không còn phụ thuộc hàm nào có thể loại bỏ thì thu đươc F3 thoả mãn đk3 B.4. Fc = F3 Ví dụ 1 • U = {A,B,C} F = {A BC, B C, A B, AB C}. Tìm phủ tối thiểu của F? – F1 = {A B, A C, B C, AB C} – Xét các pth trong F mà vế trái có nhiều hơn 1 26 1 thuộc tính AB C. Giản ước A thì ta còn B C có trong F1, vậy A là thuộc tính thừa. Tương tự ta cũng tìm được B là thừa, vậy loại bỏ luôn AB C khỏi F1.F2 = {A B, A C, B C} – Bỏ pth thừa: A C là thừa. Vậy Fc = {A B, B C} Ví dụ 2 • Tìm phủ tối thiểu của tập phụ thuộc hàm F = {A B, ABCD E, EF G, ACDF EG} – F1 = {A B, ABCD E, EF G, ACDF E, ACDF G} – Loại bỏ thuộc tính thừa trong 3 phụ thuộc hàm ABCD E, ACDF E và ACDF G 27 Xét ABCD E: Giả sử giản ước A , ta còn BCD E, kiểm tra BCD E có được suy ra từ F1 không, ta tính (BCD)+ (đối với F1). (BCD)+ = BCD, không chứa E, vậy thì BCD E không được suy diễn ra từ F, vậy A không phải là thuộc tính thừa trong pth đang xét. B là thừa vì từ F1 ta có A B dẫn đến (ACD)+ = ABCDE có chứa E Làm tương tự ta thấy không có thuộc tính nào là thừa nữa. F2 = {A B, ACD E, EF G, ACDF E, ACDF G} Ví dụ 2 (tiếp) – Loại bỏ pth thừa trong F2: Lần lượt thử loại bỏ 1 pth ra khỏi F2, nếu tập pth thu đựoc sau khi loại bỏ vẫn tương đương với F2 thì pth vừa loại là thừa A B không thừa vì nếu loại pth này khỏi F2 thì từ tập phụ thuộc hàm còn lại A+ không chứa B Tương tự , ACD E, EF G không thừa 28 ACDF E là phụ thuộc hàm thừa vì nếu loại bỏ pth này, trong tập pth vẫn còn lại ACD E, theo tiên đề tăng trưởng ta sẽ suy ra được ACDF E ACDF G là thừa vì nếu loại bỏ pth này, trong tập pth còn lại vẫn có ACD E và EF G, do đó ta vẫn có (ACDF)+ = ACDEFG có chứa G – Vậy Fc = { A B, ACD E, EF G} Phép tách các Sơ đồ quan hệ • Mục đích –Thay thế một sơ đồ quan hệ R(A1, A2, , An) bằng một tập các sơ đồ con {R1, R2, , Rk} trong đó Ri R và R = R1 U R2 U U R 29 k • Yêu cầu của phép tách –Bảo toàn thuộc tính, ràng buộc –Bảo toàn dữ liệu Phép tách không mất mát thông tin • Đ/N: Cho lược đồ quan hệ R(U) phép tách R thành các sơ đồ con {R1, R2, , Rk} được gọi là phép tách không mất mát thông tin đ/v một tập phụ thuộc hàm F nếu với mọi quan hệ r xác định trên R thỏa mãn F thì: r = R1(r) R2(r) Rk (r) 30 • Ví dụ: Phép tách mất mát thông tin Supplier(sid, sname,city,NOE, pid, pname,colour,quantity) S1(sid,sname,city,NOE) và SP1(pid,pname,colour,quantity) • Ví dụ: Phép tách không mất mát thông tin S1(sid,sname,city,NOE) và SP2(sid,pid,pname,colour,quantity) CuuDuongThanCong.com https://fb.com/tailieudientucntt 1/30/2012 6 Định lý tách đôi • Cho lược đồ quan hệ R(U), tập pth F , phép tách R thành R1(U1), R2(U2) là một phép tách không mất mát thông tin nếu 1 trong 2 phụ thuộc hàm sau là thỏa mãn trên F+: U1 ∩ U2 U1 - U2 U1 ∩ U2 U2 - U1 31 • Hệ quả: Cho lược đồ quan hệ R(U) và phụ thuộc hàm X Y thỏa mãn trên R(U). Phép tách R thành 2 lược đồ con R1(U1), R2(U2) là một phép tách không mất mát thông tin với: U1 = XY U2 = XZ Z = U \ XY Thuật toán 5: Kiểm tra tính không mất mát thông tin của 1 phép tách • Vào: R(A1, A2, , An), F, phép tách {R1, R2, , Rk} • Ra: phép tách là mất mát thông tin hay không • Thuật toán B.1. Thiết lập một bảng k hàng, n cột Nếu Aj là thuộc tính của Ri thì điền aj vào ô (i,j). Nếu không thì điền bij. B.i. Xét f = X Y F 32 Nếu 2 hàng t1, t2 thuộc bảng : t1[X] = t2[X] thì đồng nhất t1[Y] = t2[Y], ưu tiên về giá trị a Lặp cho tới khi không thể thay đổi được giá trị nào trong bảng B.n. Nếu bảng có 1 hàng gồm các kí hiệu a1, a2, , an thì phép tách là không mất mát thông tin ngược lại, phép tách không bảo toàn thông tin Ví dụ • R = ABCD được tách thành R1=AB, R2 =BD, R3=ABC, R4=BCD. F = {A C, B C, CD B, C D} • B.1: Tạo bảng gồm 4 hàng, 4 cột 33 A B C D R1 a1 a2 b31 b41 R2 b12 a2 b32 a4 R3 a1 a2 a3 b43 R4 b14 a2 a3 a4 Ví dụ (tiếp) • B.2 & 3: • Từ A C, ta có A B C D R1 a1 a2 a3 b41 R2 b12 a2 b32 a4 R3 a1 a2 a3 b43 34 • Từ B C, ta có R4 b14 a2 a3 a4 A B C D R1 a1 a2 a3 b41 R2 b12 a2 a3 a4 R3 a1 a2 a3 b43 R4 b14 a2 a3 a4 Ví dụ (tiếp) • Từ C D, ta có A B C D R1 a1 a2 a3 a4 R2 b12 a2 a3 a4 R3 a1 a2 a3 a4 35 • Vậy ta có 2 hàng có toàn các giá trị a. Chứng tỏ phép tách đã cho là không mất mát thông tin R4 b14 a2 a3 a4 Phép tách bảo toàn tập phụ thuộc hàm • Hình chiếu của tập phụ thuộc hàm Cho sơ đồ quan hệ R, tập phụ 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ập tất cả X Y F+: XY Ri 36 • 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ập phụ thuộc hàm F nếu (F1 F2 Fk)+ = F+ hay hợp của tất cả các phụ thuộc hàm trong các hình chiếu của F lên các sơ đồ con sẽ suy diễn ra các phụ thuộc hàm trong F. CuuDuongThanCong.com https://fb.com/tailieudientucntt 1/30/2012 7 Ví dụ • Ví dụ 1: R = {A, B, C} F = { A B, B C, C A}được tách thành R1 = AB, R2 = BC. Phép tách này có phải là bảo toàn tập phụ thuộc hàm không? • Ví dụ 2: R = {A, B, C} , F = {AB C, C B}được tách thành R1 = AB, R2 = BC. Phép tách này có bảo toàn tập pth không có mất mát 37 , thông tin không? • Ví dụ 3: R = { A, B, C, D} , F = {A B, C D}được tách thành R1 = AB, R2 = CD. Phép tách này có bảo toàn tập pth không, có mất mát thông tin không? • Vậy một phép tách có bảo toàn tập phụ thuộc hàm thì không đảm bảo là nó sẽ không mất mát thông tin và ngược lại Các dạng chuẩn đối với SĐQH • Quay lại vấn đề thiết kế cơ sở dữ liệu quan hệ, câu hỏi mà chúng ta đặt ra trong quá trình này là Có cần thiết phải tinh chỉnh thiết kế nữa hay không, thực sự thiết kế mà chúng ta có được đã là tốt hay chưa. Để giúp trả lời câu hỏi này, người ta đưa ra các định nghĩa về các dạng chuẩn. Có một vài dạng chuẩn đã được xem xét,ẩ 38 khi một quan hệ thuộc vào một dạng chu n nàođó thì ta có thể coi như là một số các vấn đề về dư thừa dữ liệu hay dị thường dữ liệu đã được ngăn ngừa hay tối thiểu hóa • Các dạng chuẩn mà chúng ta quan tâm – Dạng chuẩn 1 (1NF) – Dạng chuẩn 2 (2NF) – Dạng chuẩn 3 (3NF) – Dạng chuẩn Boye-Code (BCNF) Dạng chuẩn 1 (1NF) • Định nghĩa: Một sơ đồ quan hệ R được gọi là ở dạng chuẩn 1 nếu tất cả các miền giá trị của các thuộc tính trong R đều chỉ chứa giá trị nguyên tố – Giá trị nguyên tố là giá trị mà không thể chia nhỏ ra được nữa • Một quan hệ r xác định trên sơ đồ quan hệ ở dạng 39 chuẩn 1 thì quan hệ đấy là ở dạng chuẩn 1 • Ví dụ: Quan hệ không ở dạng chuẩn 1 và quan hệ sau khi chuẩn hóa về dạng chuẩn 1 sname city product name price Blake London Nut 100 Bolt 120 Smith Paris Screw 75 sname city item price Blake London Nut 100 Blake London Bolt 120 Smith Paris Screw 75 Dạng chuẩn 2 (2NF) • Định nghĩa: Một sơ đồ quan hệ R được coi là ở dạng chuẩn 2 nếu –Sơ đồ quan hệ này ở 1NF –Tất cả các thuộc tính không khoá đều h h ộ hà đầ đủ à kh á hí h 40 p ụ t u c m y v o o c n (Lưu ý, A là một thuộc tính khoá nếu A thuộc một khoá tối thiểu nào đó của R. Ngược lại A là thuộc tính không khoá) Phụ thuộc hàm đầy đủ • Định nghĩa: Cho lược đồ quan hệ R(U), F là tập phụ thuộc hàm trên R. X, Y U. Y được gọi là phụ thuộc đầy đủ vào X nếu: 41 - X Y thuộc F+ - ! X’ X : X’ Y F+ • Các phụ thuộc hàm không đầy đủ còn gọi là phụ thuộc bộ phận Ví dụ • Sales(sid, sname, city, item, price) • F = {sid (sname,city), (sid,item) price} • Khoá chính (sid,item), ta có sname, 42 city không phụ thuộc hàm đầy đủ vào khoá chính => Quan hệ Sales không thuộc 2NF • S(sid, sname, city) và Sales (sid, item, price) là quan hệ thuộc 2NF CuuDuongThanCong.com https://fb.com/tailieudientucntt 1/30/2012 8 Dạng chuẩn 3 (tiếp) • Định nghĩa: Một sơ đồ quan hệ R được coi là ở dạng chuẩn 3 nếu –Sơ đồ quan hệ này ở 2NF –Mọi thuộc tính không khoá đều không h h ộ bắ ầ à kh á hí h 43 p ụ t u c c c u v o o c n Phụ thuộc bắc cầu • Định nghĩa: Cho lược đồ quan hệ R(U). F là tập phụ thuộc hàm trên R(U). X,Y,Z U. Ta nói Z là phụ thuộc bắc cầu vào X nếu ta có X Y 44 , Y Z thuộc F+. Ngược lại, ta nói Z không phụ thuộc bắc cầu vào X Ví dụ • Ví dụ 1: Trong ví dụ tách về dạng chuẩn 2 ta có: S (sid, sname, city) và Sales(sid, item, price). Xét quan hệ S, pth sid sname, city tồn tại trên S, sid là khoá chính, các thuộc tính không khoá sname, city đều phụ thuộc trực 45 tiếp vào sid. S thuộc 3NF. Tương tự ta có Sales cũng thuộc 3NF • Ví dụ 2: – ItemInfo(item, price, discount). F = {item price, price discount}. Khoá chính là item, thuộc tính không khoá discount phụ thuộc bắc cầu vào khoá chính item. Vậy quan hệ này không ở 3NF. – ItemInfo(item, price) và Discount(price, discount) thuộc 3NF. Dạng chuẩn Boye-Codd • Định nghĩa: Một sơ đồ quan hệ R(U) với một tập phụ thuộc hàm F được gọi là ở dạng chuẩn Boye-Codd (BCNF) nếu với X A F+ thì – A là thuộc tính xuất hiện trong X hoặc – X chứa một khoá của quan hệ R. 46 • Ví dụ – R = {A,B,C} ; F = {AB C , C B}. – R không phải ở BCNF vì C B, C không phải là khoá • Chú ý: – Một quan hệ thuộc 3NF thì chưa chắc đã thuộc BCNF. Nhưng một quan hệ thuộc BCNF thì thuộc 3NF Tách bảo toàn tập phụ thuộc hàm về 3NF • Vào: R(U), F (giả thiết F là phủ tối thiểu) • Ra: Phép tách bảo toàn tập phụ thuộc hàm về 3NF • Thuật toán B1. Với các Ai U, Ai F thì loại Ai khỏi R và lập 1 quan hệ mới cho các Ai 47 B2. Nếu f F, f chứa tất cả các thuộc tính của R (đã bỏ các Ai ở bước trên) thì kết quả là R B3. Ngược lại, với mỗi X A F, xác định một quan hệ Ri(XA). Nếu X Ai, X Aj thì tạo một quan hệ chung R’(XAiAj) Ví dụ Cho R = {A,B,C,D,E,F,G} F = {A B, ACD E, EF G} (đã tối thiểu) • Xác định phép tách bảo toàn tập phụ thuộc hàm về 3NF B1 Không lập được q an hệ nào mới 48 . u . B2. ! f F: f chứa tất cả các thuộc tính của R B3. A B R1(AB) ACD E R2(ACDE) EF G R3(EFG) CuuDuongThanCong.com https://fb.com/tailieudientucntt 1/30/2012 9 Tách không mất mát thông tin và bảo toàn tập phụ thuộc hàm về 3NF • Yêu cầu: – Bảo toàn tập phụ thuộc hàm (như thuật toán trên) – Đảm bảo là có một lược đồ con chứa khoá của lược đồ được tách • Các bước tiến hành 49 B1. Tìm một khoá tối thiểu của lược đồ quan hệ R đã cho B2. Tách lược đồ quan hệ R theo phép tách bảo toàn tập phụ thuộc hàm. B3. Nếu 1 trong các sơ đồ con có chứa khoá tối thiểu thì kết quả của B2 là kết quả cuối cùng Ngược lại, thêm vào kết quả đó một sơ đồ quan hệ được tạo bởi khoá tối thiểu tìm được ở 1 Ví dụ • Cho R(U) trong đó U = {A,B,C,D,E,F,G}. F = {A B, ACD E, EF G} • Tìm một khoá tối thiểu của R: K0 = ABCDEFG K1 = K0 do nếu loại A thì BCDEFG U không thuộc F+ K2 = K1 \{B} = ACDEFG do ACDEFG U thuộc F+ 50 K3 = K2 do nếu loại C thì ADEFG U không thuộc F+ K4 = K3 do nếu loại D thì ACEFG U không thuộc F+ K5 = K4 \{E} = ACDFG do ACDFG U thuộc F+ K6 = K5 do nếu loại F thì ACDG U không thuộc F+ K7 = K6 \{G} = ACDF do ACDF U thuộc F+ • Vậy khoá tối thiểu cần tìm là ACDF Ví dụ (tiếp) • Dùng kết quả của ví dụ ở phần tách bảo toàn tập phụ thuộc hàm ta có một phép tách R thành 3 sơ đồ con R1 = AB, R2= ACDE, R3 = EFG • Do khoá ACDF không nằm trong bất kỳ một 51 sơ đồ con nào trong 3 sơ đồ con trên, ta lập một sơ đồ con mới R4 = ACDF • Kết quả 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ập phụ thuộc hàm Tách không mất mát thông tin về BCNF • Vào: Sơ đồ quan hệ R, tập phụ thuộc hàm F. • Ra: phép tách không mất mát thông tin bao gồm một tập các sơ đồ con ở BCNF với các phụ thuộc hàm là hình chiếu của F lên sơ đồ đó. • Cách tiến hành B1 KQ = {R} 52 . , B2.Với mỗi S KQ, S không ở BCNF, xét X A S, với điều kiện X không chứa khoá của S và A X. Thay thế S bởi S1, S2 với S1=A X, S2 = S \ A. B3. Lặp (B2) cho đến khi S KQ đều ở BCNF KQ gồm các sơ đồ con của phép tách yêu cầu Kết luận • Tầm quan trọng của thiết kế CSDL – ảnh hưởng đến chất lượng dữ liệu lưu trữ – Hiệu quả của việc khai thác dữ liệu • Mục đích của thiết kế CSDL: – Tránh dư thừa dữ liệu 53 – Tránh dị thường dữ liệu khi thêm/xoá/sửa đổi – Hiệu quả trong tìm kiếm Đưa về các dạng chuẩn – 2NF: giản ước sự dư thừa để tránh các dị thuờng khi cập nhật – 3NF: tránh các dị thường khi thêm/xoá 54 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1/30/2012 10 Lời hay ý đẹp "Nếu anh thấy một gia đình hạnh phúc, anh nên tin rằng ở trong gia đình có một người đàn bà biết quên mình." 55 (René Bazin) CuuDuongThanCong.com https://fb.com/tailieudientucntt
File đính kèm:
- bai_giang_co_so_du_lieu_chuong_4_ly_thuyet_thiet_ke_co_so_du.pdf