zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cơ sở dữ liệu: Chương 4 - Nguyễn Hồng Phương

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:10

Báo xấu

41
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ệ" cung cấp cho người học các kiến thức: Tổng quan về thiết kế CSDLQH, phục thuộc hàm, phép tách các sơ đồ quan hệ,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu: Chương 4 - Nguyễn Hồng Phương

1/30/2012 Nội dung Lý thuyết thiết kế • Tổng quan về thiết kế CSDLQH cơ sở dữ liệu quan hệ • Phụ thuộc hàm • Phép tách các sơ đồ quan hệ (SĐQH) Ng ễn Hồng Phương Nguyễn • Các dạng chuẩn đối với các SĐQH phuongnh@soict.hut.edu.vn http://is.hut.edu.vn/~phuongnh Bộ môn Hệ thống thông tin Viện Công nghệ thông tin và Truyền thông Đại học Bách Khoa Hà Nội 1 2 Tổng quan về thiết kế CSDLQH Các vấn đề đối với CSDL VD • Vấn đề của một sơ đồ quan hệ được thiết • 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 kế chưa tốt: trong bảng (VD S1), mặt hàng được cung ứng bởi Giả sử ta cần một cơ sở dữ liệu lưu trữ thông tin nhiều hãng cũng bị lặp lại (VD Screw) về các hãng cung ứng. Sơ đồ quan hệ được thiết • Dị thường dữ liệu khi thêm: Nếu có một hãng kế trong đó tất cả các thuộc tính cần thiết được chưa cung cấp mặt hàng nào, vậy giá trị cho thuộc lưu trong đúng 1 quan hệ: tính p product và q quantity y trong g bộ ộ dữ liệu ệ mới được ợ Suppliers(sid, sname, city, numofemps, product, quantity) 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 sid sname city NOE product quantity về sự cung cấp này thì ta sẽ mất thông tin về hãng S1 Smith London 100 Screw 50 cung cấp • Dị thường dữ liệu khi sửa đổi: Do thông tin bị S1 Smith London 100 Nut 100 lặp lại nên việc sửa đổi 1 bộ dữ liệu có thể dẫn đến S2 J&J Paris 124 Screw 78 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á S3 Blake Tokyo 75 Bolt 100 3 trị liên quan đến hãng đó 4 Đề xuất giải pháp Mục đích của chuẩn chuẩn hoá hoá • Nếu sơ đồ trên được thay thế bằng • Xác định được 1 tập các lược đồ quan 2 sơ đồ quan hệ hệ cho phép tìm kiếm thông tin một –Supp(sid, sname, city, numofemps) cách dễ dàng, đồng thời tránh được dư thừa dữ liệu –Supply(sid, product,quantity) • Hướng tiếp cận: Một trong những kỹ Thì tất cả các vấn đề nêu ở trên sẽ thuật được sử dụng là Tách các lược được loại bỏ. Tuy nhiên khi tìm đồ quan hệ có vấn đề thành những kiếm dữ liệu thì chúng ta phải thực lược đồ quan hệ chuẩn hơn. Phụ thuộc hiện kết nối 2 bảng chứ không chỉ là hàm có thể được sử dụng để nhân biết chọn và chiếu trên 1 bảng như ở các lược đồ chưa chuẩn và đề xuất cách thiết kết trước hướng cải tiến 5 6 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012 Phụ thuộc hàm Ví dụ • Định nghĩa: Cho R(U) là một sơ đồ • Ví dụ 1: A B C quan hệ với U là tập thuộc tính a1 b1 c1 a2 b2 c2 {A1, A2,…,An}. X, Y là tập con của a3 b1 c1 U. Nói rằng X xác định Y hay Y là a4 b3 c2 phụ h thuộc th ộ hàm hà vào à X ( X  Y) nếu với 1 quan hệ r xác định trên • A  B, A  C, B  C R(U) và 2 bộ bất kỳ t1, t2 thuộc r • Ví dụ 2: trong cơ sở dữ liệu mẫu dùng trong mà t1[X] = t2[X] thì ta có t1[Y] = chương 3, ta có bảng S, với mỗi giá trị của sid đều tồn tại một giá trị tương ứng cho sname, t2[Y] city và status. Do đó ta có sid  sname, sid  city, sid  status 7 8 Hệ tiên đề Amstrong đối với phụ thuộc hàm Hệ quả của hệ tiên đề Amstrong Cho • Luật hợp (union) – R(U) là 1 sơ đồ quan hệ, U là tập các thuộc tính. – X,Y,Z,W  U Nếu XY, XZ thì XYZ. (Ký hiệu: XY = X  Y) • Luật tựa bắc cầu (pseudotransitivity) • Phản xạ (reflexivity) Nếu XY, XY WYZ thì XWZ. XWZ Nếu Y  X thì XY • Luật tách (decomposition) • Tăng trưởng (augmentation) Nếu XY, Z  Y thì XZ Nếu XY thì XZYZ • Bắc cầu (transitivity) Nếu XY, YZ thì XZ 9 10 Ví dụ Bao đóng của một tập phụ thuộc hàm • Ví dụ 1: • Định nghĩa: Cho F là một tập phụ thuộc Cho tập phụ thuộc hàm {ABC, CA} hàm. Bao đóng của F ký hiệu là F+ là tập Chứng minh: BC  ABC lớn nhất chứa các phụ thuộc hàm có thể CA BC  AB được suy ra từ các phụ thuộc hàm trong F AB  C AB  ABC • Bao đóng của một tập phụ thuộc hàm có BC  AB, AB  ABC BC  ABC thể rất lớn, sẽ chi phí rất tốn kém cho việc • Ví dụ 2: tìm kiếm bao đóng của 1 tập phụ thuộc Cho lược đồ quan hệ R(ABEIJGH) và tập hàm. Do đó để thuận tiện cho việc kiểm tra phụ thuộc hàm F = {ABE, AGJ, BEI, xem một phụ thuộc hàm có được suy diễn EG, GIH} từ một tập phụ thuộc hàm có sẵn không, Chứng minh: AB  GH người ta có thể sử dụng Bao đóng của 1 tập 11 thuộc tính 12 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012 Bao đóng của một tập các thuộc tính Thuật toán 1: Tìm bao đóng của một tập thuộc tính đối với tập các phụ thuộc hàm đối với tập phụ thuộc hàm • Định nghĩa: Cho một lược đồ quan hệ • Vào: Tập hữu hạn các thuộc tính U, tập các phụ R(U), F là một tập phụ thuộc hàm trên thuộc hàm F trên U U. X là tập con của U. Bao đóng của tập XU thuộc tính X ký hiệu là X+ là tập tất cả • Ra: X+ các thuộc tính được xác định hàm bởi X • Thuật toán thông qua tập F B0 X0 = X Bi Tính Xi từ Xi-1 X+ = {A  U| X  A F+} Nếu  YZ  F và Y  Xi-1 và A  Z và A  Xi-1 • Ta có thể thấy là định nghĩa về bao đóng thì Xi = Xi-1  A của một tập thuộc tính dựa trên bao ngược lại, Xi = Xi-1 đóng của tập phụ thuộc hàm. Trên thực Nếu Xi  Xi-1 tế, người ta đưa ra một thuật toán để thì lặp Bi giúp xác định bao đóng của một tập ngược lai, chuyển Bn thuộc tính dễ dàng hơn Bn X+ = Xi 13 14 Ví dụ Bổ đề • Cho R(U) , U = {A, B, C, D, E, F} • XY được suy diễn từ hệ tiên đề F = {ABC, BCAD, DE, CFB} Amstrong khi và chỉ khi Y  X+ • Chứng minh: Tính (AB)+ – Giả sử Y=A1...An, với A1,...,An là các • Thực hiện: thuộc tính và YX+ – Bước 0: X0 = AB – Từ định nghĩa X+ ta có XAi. Áp dụng – Bước 1: X1 = ABC ( do AB C) tiên đề Amstrong cho mọi i, suy ra XY nhờ luật hợp. – Bước 2: X2 = ABCD (do BCAD) – Ngược lại, giả sử có XY, áp dụng hệ tiên – Bước 3: X3 = ABCDE (do DE) đề Amstrong cho mỗi i, ta có XAi, AiY – Bước 4: X4 = ABCDE nhờ luật tách. Từ đó suy ra YX+ 15 16 Khoá Thuật toán 2: Tìm khoá tối thiểu • Định nghĩa: Cho lược đồ quan hệ R(U), F là • Vào: U = {A1, A2, …, An} , F một tập các phụ thuộc hàm xác định trên U. K • Ra: khoá tối thiểu K xác định được là một tập con của U, K được gọi là khoá tối trên U và F thiểu của R nếu như – KU là một phụ thuộc hàm trong F+ • Thuật toán – Với mọi tập con thực sự K’ của K thì K’U không B0 K 0= U thuộc F+ Bi Nếu (Ki-1\{Ai})U • Với những gì ta đã đề cập trong phần bao thì Ki= Ki-1\ {Ai} đóng ở trên, ta có thể nói, để thỏa mãn là một khoá tối thiểu thì K+ = U và K là tập ngược lại, Ki= Ki-1 thuộc tính nhỏ nhất có tính chất như vậy Bn+1 K = Kn 17 18 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012 Ví dụ Nhận xét về về ph phụụ thu thuộc ộc hàm • Cho U = {A, B, C, D, E} • F = {ABC, ACB, BCDE}. TÌm một khoá tối thiểu của • Từ một tập các phụ thuộc hàm có thể một quan hệ r xác định trên U và F • Thực hiện suy diễn ra các phụ thuộc hàm khác • B0: K0= U = ABCDE • B1: Kiểm tra xem có tồn tại phụ thuộc hàm (K0\{A})U • Trong một tập phụ thuộc hàm cho sẵn (BCDEU) hay không. Ta cần phải sử dụng thuật toán 1 để kiểm tra điều kiện tương đương là (BCDE)+ có bằng U không. không có thể có các phụ thuộc hàm bị coi là (BCDE)+= BCDE , khác U. Vậy K1 = K0 = ABCDE dư thừa • B2: Tương tự, thử loại bỏ B ra khỏi K1 ta có (ACDE)+ = ABCDE = U. Vậy K2 = K1 \ {B} = ACDE •  Làm thế nào để có được một tập • B3: K3 = ACDE • B4: K4 = ACE phụ thuộc hàm tốt? • B5: K5 = AC • Vậy AC là một khoá tối thiểu mà ta cần tìm 19 20 Tập ph phụ ụ thu thuộc ộc hàm tươ ương ng đươ đương ng Ví dụ • Định nghĩa: Tập phụ thuộc hàm F là phủ • Cho lược đồ quan hệ R(U) với U = {A, B, C, D, E, của tập phụ thuộc hàm G hay G là phủ của F} F hay F và G tương đương nếu F+ = G+. F = {ABC, DEF, CBD} – Ký hiệu là F  G G = {ACB, DEF, BCD} • Kiểm tra tính tương đương của 2 tập phụ Hỏi F và G có phải là 2 tập pth tương đương hay không? th ộ hàm thuộc hà • Thực hiện: B.1. Với mỗi phụ thuộc hàm YZ  F, Z  Y+ (trên G) thì YZ  G+ Đố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 Nếu với phụ thuộc hàm f  F, f  G+ thì F+  G+ G+ – f2= DEF thuộc G nên chắc chắn thuộc G+ B.2. Tương tự, nếu  phụ thuộc hàm g  G, g  F+ – f3= CBD. C+ (đối với G) = C không chứa BD. Vậy f3 thì G+  F+ không thuộc G+ B.3. Nếu F+  G+ và G+  F+ thì F  G – Kết luận F không tương đương với G 21 22 Tập ph phụ ụ thu thuộc ộc hàm kh khô ông d dư ư th thừa ừa Phủ Ph ủ tối thi thiểu ểu của 1 tập tập ph phụụ thu thuộc ộc hàm • Đ/N: Tập phụ thuộc hàm F là không dư • Đ/N: Fc được gọi là phủ tối thiểu của 1 thừa nếu không  XY F sao cho F \ {XY}  F. tập phụ thuộc hàm F nếu thỏa mãn 3 • Thuật toán 3: Tìm phủ không dư thừa của 1 điều kiện sau: tập phụ thuộc hàm Đk1: Với  f  Fc, f có dạng X  A, – Vào: Tập thuộc tính U, F = {Li Ri: i = 1..n} – Ra : Phủ không dư thừa F’ của F trong đó A là 1 thuộc tính – Thuật toán Đk2: Với  f = XY  Fc, ! A X (A là 1 B0 F0= F thuộc tính): Bi Nếu Fi-1\ {LiRi}  Fi-1 thì Fi = Fi-1 \ {LiRi} (Fc \ f) U {(X \ A)Y} Fc ngược lại, Fi = Fi-1 Đk3: ! XA  Fc : Fc \ {XA}  Fc Bn+1 F’ = Fn 23 24 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012 Thuật toán 4: Tìm phủ phủ tối thi thiểu ểu của một tập phụ thuộc hàm Ví dụ 1 • 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 • U = {A,B,C} • Thuật toán F = {ABC, BC, AB, ABC}. Tìm phủ 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) tối thiểu của F? B.2. Loại bỏ thuộc tính thừa trong vế trái của các phụ thuộc hàm – F1 = {AB, AC, BC, ABC} Lần lượt giản ước từng thuộc tính trong vế trái của từng – Xét các pth trong F1 mà vế trái có nhiều hơn 1 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 thuộc tính ABC. Giản ước A thì ta còn BC có Khi không có sự giản ước nào xảy ra nữa ta thu được trong F1, vậy A là thuộc tính thừa. Tương tự ta F2 thỏa mãn đk2 cũng tìm được B là thừa, vậy loại bỏ luôn ABC 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 khỏi F1.F2 = {AB, AC, BC} thì loại bỏ f – Bỏ pth thừa: AC là thừa. Vậy Fc = {AB, 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C} B.4. Fc = F3 25 26 Ví dụ 2 Ví dụ 2 (tiếp) • Tìm phủ tối thiểu của tập phụ thuộc hàm – 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 F = {AB, ABCDE, EFG, ACDFEG} loại bỏ vẫn tương đương với F2 thì pth vừa loại – F1 = {AB, ABCDE, EFG, ACDFE, là thừa ACDFG} A B không thừa vì nếu loại pth này khỏi F2 thì – Loại bỏ thuộc tính thừa trong 3 phụ thuộc từ tập phụ thuộc hàm còn lại A+ không chứa B hàm ABCDE, ACDFE và ACDFG Tương tự , ACDE, EF G không thừa Xét ABCDE: Giả sử giản ước A , ta còn ACDF E là phụ thuộc hàm thừa vì nếu loại bỏ BCDE, kiểm tra BCDE có được suy ra từ F1 pth này, trong tập pth vẫn còn lại ACDE, theo không, ta tính (BCD)+ (đối với F1). (BCD)+ = tiên đề tăng trưởng ta sẽ suy ra được ACDFE 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 ACDFG là thừa vì nếu loại bỏ pth này, trong thừa trong pth đang xét. B là thừa vì từ F1 ta có tập pth còn lại vẫn có ACDE và EFG, do đó AB dẫn đến (ACD)+ = ABCDE có chứa E ta vẫn có (ACDF)+ = ACDEFG có chứa G Làm tương tự ta thấy không có thuộc tính nào là – Vậy Fc = { AB, ACDE, EFG} thừa nữa. F2 = {AB, ACDE, EFG, ACDFE, ACDFG} 27 28 Phép tách các Sơ đồ quan hệ 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 • Mục đích thành các sơ đồ con {R1, R2, …, Rk} được gọi là – Thay thế một sơ đồ quan hệ R(A1, A2, …, 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 An) bằng một tập các sơ đồ con {R1, R2, trên R thỏa mãn F thì: …, Rk} trong đó Ri R và R = R1 U R2 U … r = R1(r)  R2(r)  …   Rk (r) U Rk • Ví dụ: Phép tách mất mát thông tin • Yêu cầu của phép tách Supplier(sid, sname,city,NOE, pid, pname,colour,quantity) S1(sid,sname,city,NOE) và – Bảo toàn thuộc tính, ràng buộc SP1(pid,pname,colour,quantity) – Bảo toàn dữ liệu • 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) 29 30 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012 Thuật toán 5: Kiểm tra tính không mất Định lý tách đôi mát thông tin của 1 phép tách • Cho lược đồ quan hệ R(U), tập pth F , phép tách R • Vào: R(A1, A2, …, An), F, phép tách {R1, R2, …, Rk} thành R1(U1), R2(U2) là một phép tách không mất • Ra: phép tách là mất mát thông tin hay không mát thông tin nếu 1 trong 2 phụ thuộc hàm sau là • Thuật toán B.1. Thiết lập một bảng k hàng, n cột thỏa mãn trên F+: Nếu Aj là thuộc tính của Ri thì điền aj vào ô (i,j). U1 ∩ U2 U1 - U2 Nếu không thì điền bij. U1 ∩ U2 U2 - U1 B.i. Xét f = XY F Nếu  2 hàng t1, t2 thuộc bảng : t1[X] = t2[X] thì đồng • Hệ quả: Cho lược đồ quan hệ R(U) và phụ thuộc nhất hàm XY thỏa mãn trên R(U). Phép tách R thành t1[Y] = t2[Y], ưu tiên về giá trị a 2 lược đồ con R1(U1), R2(U2) là một phép tách Lặp cho tới khi không thể thay đổi được giá trị nào trong không mất mát thông tin với: bảng U1 = XY 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 U2 = XZ ngược lại, phép tách không bảo toàn thông tin Z = U \ XY 31 32 Ví dụ Ví dụ (tiếp) • R = ABCD được tách thành R1=AB, R2 • B.2 & 3: A B C D =BD, R3=ABC, R4=BCD. F = {AC, • Từ A  C, ta có R1 a1 a2 a3 b41 BC, CDB, CD} R2 b12 a2 b32 a4 • B.1: Tạo bảng gồm 4 hàng, 4 cột R3 a1 a2 a3 b43 R4 b14 a2 a3 a4 A B C D A B C D R1 a1 a2 b31 b41 • Từ B  C, ta có R1 a1 a2 a3 b41 R2 b12 a2 b32 a4 R2 b12 a2 a3 a4 R3 a1 a2 a3 b43 R3 a1 a2 a3 b43 R4 b14 a2 a3 a4 R4 b14 a2 a3 a4 33 34 Ví dụ (tiếp) Phép tách bảo toàn tập phụ thuộc hàm • Từ C  D, ta có • Hình chiếu của tập phụ thuộc hàm A B C D Cho sơ đồ quan hệ R, tập phụ thuộc hàm F, phép R1 a1 a2 a3 a4 tách {R1, R2, … , Rk} của R trên F. R2 b12 a2 a3 a4 Hình chiếu Fi của F trên Ri là tập tất cả XY  F+: R3 a1 a2 a3 a4 XY  Ri R4 b14 a2 a3 a4 • 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ụ • Vậy ta có 2 hàng có toàn các giá trị thuộc hàm F nếu a. Chứng tỏ phép tách đã cho là (F1  F2 …  Fk)+ = F+ hay hợp của tất cả các phụ thuộc hàm trong các không mất mát thông tin 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. 35 36 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012 Ví dụ Các dạng chuẩn đối với SĐQH • Ví dụ 1: R = {A, B, C} F = { AB, BC, CA} • Quay lại vấn đề thiết kế cơ sở dữ liệu quan hệ, được tách thành R1 = AB, R2 = BC. Phép tách câu hỏi mà chúng ta đặt ra trong quá trình này này có phải là bảo toàn tập phụ thuộc hàm là Có cần thiết phải tinh chỉnh thiết kế nữa hay không? không, thực sự thiết kế mà chúng ta có được đã • Ví dụ 2: R = {A, B, C} , F = {ABC, CB} 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 được tách thành R1 = AB, R2 = BC. Phép tách chuẩn. Có mộtộ vài dạng ạ g chuẩn đã đượcợ xem xét,, này có bảo toàn tập pth không, không có mất mát khi một quan hệ thuộc vào một dạng chuẩn ẩ nào thông tin không? đó thì ta có thể coi như là một số các vấn đề về • Ví dụ 3: R = { A, B, C, D} , F = {AB, CD} dư thừa dữ liệu hay dị thường dữ liệu đã được được tách thành R1 = AB, R2 = CD. Phép tách ngăn ngừa hay tối thiểu hóa này có bảo toàn tập pth không, có mất mát • Các dạng chuẩn mà chúng ta quan tâm thông tin không? – Dạng chuẩn 1 (1NF) • Vậy một phép tách có bảo toàn tập phụ thuộc – Dạng chuẩn 2 (2NF) 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 – Dạng chuẩn 3 (3NF) 37 – Dạng chuẩn Boye-Code (BCNF) 38 Dạng chuẩn 1 (1NF) Dạng chuẩn 2 (2NF) • Định nghĩa: Một sơ đồ quan hệ R được gọi là ở • Định nghĩa: Một sơ đồ quan hệ R được 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ố coi là ở dạng chuẩn 2 nếu – Giá trị nguyên tố là giá trị mà không thể chia – Sơ đồ quan hệ này ở 1NF nhỏ ra được nữa • Một ộ qquan hệệ r xác định ị trên sơ đồ q quan hệệ ở dạng ạ g – Tất cả các thuộc tính không khoá đều chuẩn 1 thì quan hệ đấy là ở dạng chuẩn 1 phụ h thuộc h ộ hàm hà đầy đầ đủ vàoà khoá kh á chính hí h • Ví dụ: Quan hệ không ở dạng chuẩn 1 và quan hệ (Lưu ý, A là một thuộc tính khoá nếu A sau khi chuẩn hóa về dạng chuẩn 1 thuộc một khoá tối thiểu nào đó của R. sname city product sname city item price Ngược lại A là thuộc tính không khoá) name price Blake London Nut 100 Blake London Nut 100 Blake London Bolt 120 Bolt 120 Smith Paris Screw 75 Smith Paris Screw 75 39 40 Phụ thuộc hàm đầy đủ Ví dụ • Định nghĩa: Cho lược đồ quan hệ • Sales(sid, sname, city, item, price) R(U), F là tập phụ thuộc hàm trên R. • F = {sid(sname,city), X, Y  U. Y được gọi là phụ thuộc đầy (sid,item)price} đủ vào X nếu: • Khoá chính ((sid,item), , ), ta có sname,, - XY thuộc F+ city không phụ thuộc hàm đầy đủ vào - ! X’  X : X’Y  F+ khoá chính => Quan hệ Sales không thuộc 2NF • Các phụ thuộc hàm không đầy đủ còn • S(sid, sname, city) và Sales (sid, gọi là phụ thuộc bộ phận item, price) là quan hệ thuộc 2NF 41 42 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012 Dạng chuẩn 3 (tiếp) Phụ thuộc bắc cầu • Định nghĩa: Một sơ đồ quan hệ R được • Định nghĩa: Cho lược đồ quan hệ coi là ở dạng chuẩn 3 nếu R(U). F là tập phụ thuộc hàm trên – Sơ đồ quan hệ này ở 2NF R(U). X,Y,Z  U. Ta nói Z là phụ – Mọi thuộc tính không khoá đều không thuộc bắc cầu vào X nếu ta có XY phụ h thuộc h ộ bắ bắc cầu ầ vào à khoá kh á chính hí h , 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 43 44 Ví dụ Dạng chuẩn Boye Boye--Codd • Ví dụ 1: Trong ví dụ tách về dạng chuẩn 2 ta • Định nghĩa: Một sơ đồ quan hệ R(U) với có: S (sid, sname, city) và Sales(sid, item, một tập phụ thuộc hàm F được gọi là ở price). dạng chuẩn Boye-Codd (BCNF) nếu với  Xét quan hệ S, pth sid  sname, city tồn tại XA  F+ thì trên S, sid là khoá chính, các thuộc tính – A là thuộc tính xuất hiện trong X hoặc khôngg khoá sname,, cityy đều p phụ ụ thuộc ộ trực ự – X chứa một ộ khoá của q quan hệ ệ R. tiếp vào sid. S thuộc 3NF. Tương tự ta có • Ví dụ Sales cũng thuộc 3NF – R = {A,B,C} ; F = {ABC , CB}. • Ví dụ 2: – R không phải ở BCNF vì  CB, C không phải là – ItemInfo(item, price, discount). F = {itemprice, khoá pricediscount}. Khoá chính là item, thuộc tính • Chú ý: không khoá discount phụ thuộc bắc cầu vào khoá – Một quan hệ thuộc 3NF thì chưa chắc đã thuộc chính item. Vậy quan hệ này không ở 3NF. BCNF. Nhưng một quan hệ thuộc BCNF thì thuộc – ItemInfo(item, price) và Discount(price, 3NF discount) thuộc 3NF. 45 46 Tách bảo toàn tập phụ thuộc hàm về 3NF Ví dụ • Vào: R(U), F (giả thiết F là phủ tối thiểu) Cho R = {A,B,C,D,E,F,G} • Ra: Phép tách bảo toàn tập phụ thuộc hàm về 3NF F = {AB, ACDE, EFG} (đã tối thiểu) • Thuật toán • Xác định phép tách bảo toàn tập phụ thuộc B1. Với các Ai  U, Ai  F thì loại Ai khỏi R và lập 1 hàm về 3NF quan hệ mới cho các Ai B1. Không lập được quan B1 q an hệ nào mới mới. 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 B2. ! f  F: f chứa tất cả các thuộc tính của R B3. Ngược lại, với mỗi X A F, xác định một B3. AB  R1(AB) quan hệ Ri(XA). ACDE  R2(ACDE) Nếu  XAi, XAj thì tạo một quan hệ chung EFG  R3(EFG) R’(XAiAj) 47 48 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012 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 Ví dụ • Cho R(U) trong đó U = {A,B,C,D,E,F,G}. F = • Yêu cầu: {AB, ACDE, EFG} – Bảo toàn tập phụ thuộc hàm (như thuật toán • Tìm một khoá tối thiểu của R: trên) K0 = ABCDEFG – Đảm bảo là có một lược đồ con chứa khoá của K1 = K0 do nếu loại A thì BCDEFG  U không lược đồ được tách thuộc F+ • Các bước tiến hành K2 = K1 \{B} = ACDEFG do ACDEFG  U thuộc F+ B1. Tìm một khoá tối thiểu của lược đồ quan hệ R đã cho K3 = K2 do nếu loại C thì ADEFG  U không thuộc B2. Tách lược đồ quan hệ R theo phép tách bảo toàn tập phụ F+ thuộc hàm. K4 = K3 do nếu loại D thì ACEFG  U không thuộc B3. Nếu 1 trong các sơ đồ con có chứa khoá tối thiểu thì kết F+ quả của B2 là kết quả cuối cùng K5 = K4 \{E} = ACDFG do ACDFG  U thuộc F+ Ngược lại, thêm vào kết quả đó một sơ đồ quan hệ được K6 = K5 do nếu loại F thì ACDG  U không thuộc tạo bởi khoá tối thiểu tìm được ở 1 F+ K7 = K6 \{G} = ACDF do ACDF  U thuộc F+ 49 50 • Vậy khoá tối thiểu cần tìm là ACDF Tách không mất mát thông tin về Ví dụ (tiếp) BCNF • Dùng kết quả của ví dụ ở phần tách bảo • Vào: Sơ đồ quan hệ R, tập phụ thuộc hàm F. toàn tập phụ thuộc hàm ta có một phép • 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 tách R thành 3 sơ đồ con R1 = AB, R2= hàm là hình chiếu của F lên sơ đồ đó. ACDE, R3 = EFG • Cách tiến hành • Do khoá ACDF không nằm trong bất kỳ một B1 KQ = {R}, B1. {R} sơ đồ con nào trong 3 sơ đồ con trên, ta lập B2.Với mỗi S  KQ, S không ở BCNF, xét XA  S, một sơ đồ con mới R4 = ACDF 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 • Kết quả cuối cùng ta có phép tách R thành \ A. 4 sơ đồ con {R1, R2, R3, R4} là một phép B3. Lặp (B2) cho đến khi S KQ đều ở BCNF tách không mất mát thông tin và bảo toàn KQ gồm các sơ đồ con của phép tách yêu cầu tập phụ thuộc hàm 51 52 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 – 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á 53 54 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/30/2012 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." (René Bazin) 55 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.