Giáo trình Cơ sở dữ liệu: Phần 2 - Đại học Kinh tế TP. HCM

pdf
Số trang Giáo trình Cơ sở dữ liệu: Phần 2 - Đại học Kinh tế TP. HCM 115 Cỡ tệp Giáo trình Cơ sở dữ liệu: Phần 2 - Đại học Kinh tế TP. HCM 2 MB Lượt tải Giáo trình Cơ sở dữ liệu: Phần 2 - Đại học Kinh tế TP. HCM 3 Lượt đọc Giáo trình Cơ sở dữ liệu: Phần 2 - Đại học Kinh tế TP. HCM 1
Đánh giá Giáo trình Cơ sở dữ liệu: Phần 2 - Đại học Kinh tế TP. HCM
4.1 ( 14 lượt)
Nhấn vào bên dưới để tải tài liệu
Đang xem trước 10 trên tổng 115 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

Chƣơng 4 PHỤ THUỘC HÀM Mục tiêu của chƣơng. Trong chƣơng này chúng ta sẽ học về:         Khái niệm phụ thuộc hàm; Lƣu trữ dƣ thừa và phụ thuộc hàm; Lƣợc đồ quan hệ với ràng buộc phụ thuộc hàm; Khoá và phụ thuộc hàm; Bộ luật dẫn; Phụ thuộc hàm hệ quả, bài toán thành viên; Phủ tối tiểu của một tập phụ thuộc hàm; Kỹ thuật tableaux. Một quan hệ có thể có tính chất nào đó cho phép chúng ta lƣu trữ hiệu quả. Chẳng hạn, để lƣu một quan hệ có tính đối xứng ta chỉ cần lƣu một bên, so với đƣờng chéo chính 44, và phục hồi toàn bộ quan hệ này bằng phép hợp. Chƣơng này sẽ khảo sát một loại quan hệ quan trọng: quan hệ hàm. Việc phát hiện ra các quan hệ hàm giữa các thuộc tính trong lƣợc đồ quan hệ cho phép chúng ta đƣa ra các cấu trúc lƣu trữ không dƣ thừa. Ví dụ 4.1 Cho quan hệ 44 quan hệ r(X,Y) đối xứng nếu (x,y) thuộc r thì (y,x) cũng vậy; bằng cách biểu diễn r trong mặt phẳng XY ta quan sát thấy nó đối xứng qua đƣờng chéo chính (x,x). Một ví dụ về quan hệ có tính đối xứng là sổ cái tài khoản. Khi lƣu trữ ngƣời ta không lƣu sổ cái tài khoản mà chỉ cần lƣu các sổ chi tiết, tại đó không còn tồn tại tính đối xứng nữa. Một ví dụ khác khi lƣu đƣờng nối giữa các thành phố, nếu có tính đối xứng, chúng ta chỉ cần lƣu một cho mỗi cặp đối xứng nhau. Giáo trình cơ sở dữ liệu 120 r (A 1 1 2 2 3 4 5 B -2 -2 3 3 2 -2 1 C 4 4 9 9 4 4 1 D) 0 0 1 1 2 3 4 Quan sát thấy C = B2, D = A – 1 và B là một hàm của A. Giả sử điều này luôn đúng. Rõ ràng cách lƣu nhƣ vậy là dƣ thừa, vừa lãng phí không gian lƣu trữ vừa phải thƣờng xuyên kiểm tra tính đúng đắn của bảng. Câu hỏi đặt ra là nên lƣu dữ liệu này nhƣ thế nào: cần bao nhiêu bảng và liệu có phục hồi lại bảng gốc bằng SQL không? Ở đây quan hệ giữa C và B, giữa D và A là hoàn toàn xác định, chúng ta không cần lƣu trữ; quan hệ giữa A và B cũng là một quan hệ hàm nhƣng không xác định, chúng ta nên lƣu riêng. Kết quả ta có một quan hệ lƣu trữ không dƣ thừa sau: r ( A B) 1 -2 2 3 3 2 4 -2 5 1 Giờ đây chỉ cần một câu truy vấn, chúng ta hoàn toàn có thể phục hồi lại quan hệ gốc45. Ví dụ 4.2 Cho quan hệ r (A a a b b c d B u u v v w u C x x y y x x D) 1 2 1 3 2 1 Quan sát thấy 45 SELECT A, B, B*B AS C, A – 1 AS D FROM r (xem chƣơng 3) Chƣơng 4: Phụ thuộc hàm 121  B là một hàm của A;  C là một hàm của A;  C là một hàm của B. Nếu lƣu riêng các quan hệ hàm này, ta có r1 ( A D ) r2 ( A B ) r3 ( A C ) r4 ( B C ) a 1 a u a x u x a 2 b v b y v y b 1 c w c x w x b 3 d u d x c 2 d 1 Tuy nhiên quan hệ hàm có tính bắt cầu, việc lƣu riêng quan hệ hàm giữa A và C là thừa và chúng ta loại bớt bảng r 3: r1 ( A D ) r2 ( A B ) r4 ( B C ) a 1 a u u x a 2 b v v y b 1 c w w x b 3 d u c 2 d 1 Những quan hệ hàm nhƣ vậy tồn tại rất nhiều trong thực tế và đƣợc gọi là các phụ thuộc hàm. Việc lƣu các quan hệ hàm trong các bảng riêng biệt giúp tránh dƣ thừa trong lƣu trữ, vốn tiềm ẩn những hậu quả đe dọa nghiêm trọng đến tính toàn vẹn của dữ liệu. Không phải bất kỳ quan hệ hàm nào đƣợc tìm thấy đều phải đƣợc lƣu trong một bảng riêng. Có những quan hệ hàm là hệ quả của các quan hệ hàm khác, nhƣ đã đƣợc thấy trong ví dụ 2. Vì các quan hệ hàm hệ quả đều đƣợc phục hồi qua ngôn ngữ cơ sở dữ liệu quan hệ nên không cần lƣu riêng. Chƣơng này sẽ tìm hiểu khái niệm phụ thuộc hàm và tập trung giải quyết bài toán quan trọng: cho tập F các phụ thuộc hàm, tìm tập G tương đương F không chứa các phụ thuộc hàm hệ quả. Tập G nhƣ vậy đƣợc gọi là phủ tối tiểu46 của F. 46 Một số tài liệu dùng thuật ngữ phủ tối thiểu. Giáo trình cơ sở dữ liệu 122 1. Khái niệm Về cơ bản, để tránh dƣ thừa chúng ta sẽ lƣu riêng mỗi khi tìm thấy phụ thuộc hàm. Tuy nhiên việc lƣu những phụ thuộc hàm dẫn xuất lại gây ra dƣ thừa bảng. Trọng tâm của chƣơng này là tìm một tập phụ thuộc hàm không dƣ thừa gọi là phủ tối tiểu47. Để làm điều này chúng ta phải kiểm tra đƣợc tính thành viên của một phụ thuộc hàm. Nhƣng trƣớc hết chúng ta phải biết phụ thuộc hàm là gì. 1.1. Phụ thuộc hàm Định nghĩa 4.1 Cho quan hệ r trên lược đồ quan hệ R và X, Y là các tập thuộc tính của R. Ta nói r thỏa phụ thuộc hàm X  Y, nếu ∀𝑡 ∈ 𝑟 ∀𝑡 ′ ∈ 𝑟 (𝑡. 𝑋 = 𝑡 ′ . 𝑋 ⟹ 𝑡. 𝑌 = 𝑡 ′ . 𝑌) Để có thể dùng SQL kiểm tra xem một quan hệ có thỏa một phụ thuộc hàm nào hay không, chúng ta có thể thực hiện bằng cách tìm ra 2 dòng vi phạm hoặc đơn giản bằng cách đếm số dòng nhƣ ví dụ sau Ví dụ 4.3 Cho quan hệ r(ABC) r (A a1 a1 a2 a3 B b1 b1 b1 b2 C c1 c1 c3 c1 D) d1 d2 d2 d1 Để kiểm tra r có thỏa phụ thuộc hàm AB không, chúng ta có thể:  Hoặc đếm r[A] và r[AB], rồi so sánh  Hoặc kết r với chính nó, tìm ra các dòng vi phạm Với cách thứ 1, ta có câu SQL: SELECT C1 = C2 FROM (SELECT COUNT(*)AS C1 FROM (SELECT DISTINCT A FROM r)), SELECT COUNT(*)AS C2 FROM (SELECT DISTINCT A, B FROM r)) 47 Nếu bạn đọc không quan tâm đến phủ tối tiểu hoặc tập phụ thuộc hàm đã tối tiểu, thì chỉ cần đọc khái niệm phụ thuộc hàm và bỏ qua mục này. Chƣơng 4: Phụ thuộc hàm 123 Với cách thứ 2, ta có câu SQL: SELECT r.A, r.B FROM r INNER JOIN r AS r1 ON ((r.A = r1.A) AND (r.B <> r1.B)) 1.2. Tập phụ thuộc hàm Trong cơ sở dữ liệu, chúng ta luôn có các quy tắc mà dữ liệu phải thỏa. Trong chƣơng này, các quy tắc chúng ta quan tâm chính là các phụ thuộc hàm. Cho lƣợc đồ quan hệ R, xét tập F các phụ thuộc hàm định nghĩa trên R48, ký hiệu: SATR(F) = {r(R) | r thỏa F } Nếu không sợ nhầm lẫn, viết SAT(F) thay cho SATR(F). Trƣờng hợp R không tƣờng minh, coi R là hợp của tất cả các thuộc tính trên cả hai vế phải và trái của tất cả các phụ thuộc hàm thuộc F. Ví dụ 4.4 Cho quan hệ r(ABCDE) r (A B C D E) a1 b1 c1 d1 e1 a1 b2 c2 d2 e1 a2 b1 c3 d3 e1 a2 b1 c4 d3 e1 a3 b2 c5 d1 e1 Ta có r  SAT(F), với F = {A  D, AB  D, C  BDE, E  A, A  E}. Ví dụ 4.5 Xét quan hệ [hoá đơn](HDSố, NLập, MãKH, DChỉ, MãHG, TênHG, SốL, DGiá), viết tắt r(SNKDHTLG). Một cách tự nhiên r thỏa F = { S  NK, K  D, H  TG, SH  L }. Quan hệ r cụ thể dƣới đây không thỏa F (thật ra, r không thỏa bất cứ một phụ thuộc hàm nào của F) 48 là các phụ thuộc hàm dạng XY, với X và Y là các tập con của R. Giáo trình cơ sở dữ liệu 124 r (S 1 1 2 2 2 N 12 12 14 14 15 K a a a b b D aa cc bb bb bb H x y x y x T xx yy zz yy xx L 4 3 2 4 1 G) 12 11 11 12 12 Kể từ đây, mỗi khi cho cặp chúng ta ngụ ý sẽ chỉ làm việc với các quan hệ định nghĩa trên R và thỏa F, tức SATR(F). Trƣờng hợp R không đƣợc cho tƣờng minh, R đƣợc xác định theo cách đã biết. Định nghĩa 4.2 Cho tập phụ thuộc hàm F. Phụ thuộc hàm f = XY được gọi là phụ thuộc hàm hệ quả của F, nếu r thỏa f với mọi r thuộc SAT(F). Việc đƣa ra các ràng buộc phụ thuộc hàm có thể dẫn đến dƣ thừa: có những phụ thuộc hàm là hệ quả của những cái khác. Gọi tập tất cả các phụ thuộc hàm hệ quả của F là bao đóng của F, ký hiệu F+, bài toán kiểm tra f  F+ đƣợc gọi là bài toán thành viên. 1.3. Luật dẫn - Hệ tiên đề Armstrong Thật không tƣởng nếu muốn kiểm tra xem mọi r  SAT(F) có thoả f hay không. Chúng ta cần một tiếp cận khác thay cho việc kiểm tra trực tiếp. Bộ luật dẫn F1. Tính phản xạ XX F2. Tính thêm vào Nếu XY thì XZY F3. Tính hội Nếu XY và XZ thì XYZ F4. Tính phân rã Nếu XYZ thì XY và XZ F5. Tính bắc cầu Nếu XY và YZ thì XZ F6. Tính bắc cầu giả Nếu XY và YZW thì XZW Chƣơng 4: Phụ thuộc hàm 125 Mệnh đề 1 Xét các luật F1, F2, F6 ta có : 1. Chúng suy ra ba luật còn lại và 2. Không có hai luật nào trong chúng là có thể suy ra luật thứ ba49. Định nghĩa 4.3: Hệ tiên đề Armstrong Tập gồm ba luật dẫn {F1, F2, F6} được gọi là hệ tiên đề Armstrong Ta nói f là đƣợc suy dẫn từ F, ký hiệu F ⊨ f, nếu f đƣợc suy ra từ F bằng các luật dẫn. Ví dụ 4.6 Kiểm tra F ⊨ AEDI, với F = { A  D, AB  E, BI  E, CD  I, E  C }. Giải: Ta có: AD ⊨ AED EE ⊨ AEE { AEE, EC} ⊨ AEC {AED, AEC} ⊨ AECD { AECD, CDI} ⊨ AEI {AED, AEI} ⊨ AEDI (F2); (F2); (F5); (F3); (F5); (F3). Vậy F ⊨ AEDI, Mệnh đề 2 Cho tập phụ thuộc hàm F và f là phụ thuộc hàm tuỳ ý. Ta có f là được suy dẫn từ F nếu và chỉ nếu f là thành viên của F+. Rõ ràng F  F+. 1.4. Phủ của phụ thuộc hàm Cho 2 tập phụ thuộc hàm F và G. Nếu G+ = F+ ta nói G tƣơng đƣơng F, ký hiệu F  G. Nếu G+ F+ ta nói G đƣợc suy dẫn từ F, ký hiệu F ⊨ G. 49 F5 là trƣờng hợp riêng của F6; F3 đƣợc chứng minh bằng cách dùng F1 cho YZ sau đó dùng F6 hai lần, lần 1 đƣợc XZYZ và lần 2 đƣợc XYZ; với F4 để chứng minh XY trƣớc hết ta dùng F1 cho Y rồi dùng F2 đƣợc YZY và cuối cùng dùng F5. 126 Giáo trình cơ sở dữ liệu Định nghĩa 4.4 Cho F, tập phụ thuộc hàm G được gọi là một phủ của F, nếu G  F. Rõ ràng G là một phủ của F thì F cũng là một phủ của G. Việc gọi G là một phủ của F ngụ ý G tốt hơn F theo một nghĩa nào đó, ở đây G là đơn giản hơn F. Ví dụ 4.7 Cho F={AB, BC, AC, ABC, ABC } và G={AB, BC}. Ta có G là một phủ của F, hơn nữa G đơn giản hơn F. Việc tìm ra những phủ đơn giản hơn rõ ràng là có ý nghĩa. Giả sử XY là thành viên của F+ thì XAY cũng vậy, nhƣng một phủ nên chứa XY hơn chứa XAY. Định nghĩa 4.5 Cho lược đồ . Ta nói X  Y là phụ thuộc hàm đầy đủ dưới F, nếu XY là thành viên của F+ và nếu với mọi A thuộc X, (X – A)  Y không là thành viên của F+. Phụ thuộc hàm đầy đủ đóng vai trò quan trọng trong thực hành. Xét lƣợc đồ và quan hệ r  SATR(F). Với XY là thành viên của F+ quan hệ r[XY] nhận X làm siêu khoá. Tuy nhiên, nếu XY là phụ thuộc hàm đầy đủ dƣới F, thì X là khoá trong r[XY]. Định nghĩa 4.6 Tập phụ thuộc hàm F được gọi là tối tiểu nếu thoả: 1. Tất cả f F có dạng X A; 2. Tất cả f F đều đầy đủ dưới F; 3. Bỏ bớt một phụ thuộc hàm khỏi F sẽ không còn tương đương F. Định nghĩa 4.7: Phủ tối tiểu Cho tập phụ thuộc hàm F. Tập phụ thuộc hàm G được gọi là một phủ tối tiểu của F nếu: 1. G là một phủ của F. 2. G tối tiểu. Ví dụ 4.8 Tập phụ thuộc hàm F = {AB, AC, BA, BC, CA} không tối tiểu nhƣng có phủ G = { AB, AC, BA, CA } thì phủ tối tiểu. Chƣơng 4: Phụ thuộc hàm 127 Chú ý rằng số phụ thuộc hàm trong phủ tối tiểu không chắc là ít nhất. Xét lại F nhƣ trên ta thấy {AB, BC, CA} cũng là một phủ tối tiểu của F nhƣng có ít phụ thuộc hàm hơn phủ tối tiểu G ở trên. 2. Tìm phủ tối tiểu Chúng ta đƣa ra thuật ngữ bao đóng của tập thuộc tính, làm cơ sở giải bài toán thành viên, tiếp sau là bài toán tìm phủ tối tiểu. 2.1. Giải bài toán thành viên Định nghĩa 4.8 Cho lược đồ quan hệ (R, F) và X  R, tập X+F = {A  R | X  A } được gọi là bao đóng của X dưới F. Trong trƣờng hợp không sợ nhầm lẫn ta sẽ viết X+ thay cho X+F. Rõ ràng X+ xác định tất cả các phụ thuộc hàm suy dẫn dạng XY. Thuật toán tìm X+ rất đơn giản: bắt đầu với X+ = X, với bất cứ phụ thuộc hàm nào nếu vế trái nằm trong X+, hợp vế phải vào X+. Thuật toán 1: Closure(X, F) Vào : Tập các phụ thuộc hàm F và tập thuộc tính X  R. Ra : X+ Các bước : 1. X+ = X 2. do 2.1 T = X+ 2.2 foreach (L → R)  F do if (L  X+) X+ = X+  R while (T != X+) 3. return X+ Chú ý khi tính X+, mỗi phụ thuộc hàm chỉ dùng tối đa 1 lần. Ví dụ 4.9 Cho F = {A  D, AB  E, BI  E, CD  I, E  C }. Tính (AE)+. Giáo trình cơ sở dữ liệu 128 Giải: Bƣớc 1: (AE)+ = AE Bƣớc 2 lần 1: dùng A  D và E  C, (AE)+ = AEDC Bƣớc 2 lần 2: dùng CD  I và E  C, (AE)+ = AEDCI Bƣớc 2 lần 3: không dùng đƣợc phụ thuộc hàm nào Vậy (AE)+ = AEDCI Một cấu trúc dạng bảng sẽ dễ quan sát hơn AD AB  E BI  E CD  I EC AE * AEDC AEDCI * * Giờ đây muốn kiểm tra tính thành viên của phụ thuộc hàm X  Y, chỉ cần tính XF+. Mệnh đề 3 Cho tập phụ thuộc hàm F, ta có (XY)  F+  Y  X+ Ví dụ 4.10 Cho F = {AD, ABE, BIE, CDI, EC }, ta có (AE  DI)  F+ vì DI  (AE)+. 2.2. Giải bài toán tìm phủ tối tiểu Dựa vào bài toán thành viên và vào định nghĩa của tập phụ thuộc hàm tối tiểu, ngƣời ta xây dựng thuật toán tìm phủ tối tiểu. Về tổng thể các bƣớc của thuật toán theo đúng thứ tự của định nghĩa tập phụ thuộc hàm tối tiểu: 1. Phân rã một phụ thuộc hàm để vế phải chỉ có một thuộc tính (luật F4) 2. Rút gọn vế trái để đƣợc phụ thuộc hàm đầy đủ (luật F2) 3. Rút gọn tập phụ thuộc hàm để đạt tính không dƣ thừa Trong mỗi bƣớc đều phải kiểm tra tính thành viên thông qua việc tính bao đóng của vế phải. Trƣớc khi đƣa ra thuật toán, chúng ta xét qua vài ví dụ minh họa cho mỗi bƣớc
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.