›
›

Giáo trình Cơ sở dữ liệu - Phần 2 - Huỳnh Văn Đức

pdf 115 trang hoanguyen 4220
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cơ sở dữ liệu - Phần 2 - Huỳnh Văn Đức", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_co_so_du_lieu_phan_2_huynh_van_duc.pdf

Nội dung text: Giáo trình Cơ sở dữ liệu - Phần 2 - Huỳnh Văn Đức

  1. 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ính44, 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.
  2. 120 Giáo trình cơ sở dữ liệu r ( A B C D) 1 -2 4 0 1 -2 4 0 2 3 9 1 2 3 9 1 3 2 4 2 4 -2 4 3 5 1 1 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 B C D) a u x 1 a u x 2 b v y 1 b v y 3 c w x 2 d u x 1 Quan sát thấy 45 SELECT A, B, B*B AS C, A – 1 AS D FROM r (xem chƣơng 3)
  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 r3: 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.
  4. 122 Giáo trình cơ sở dữ liệu 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 B C D) a1 b1 c1 d1 a1 b1 c1 d2 a2 b1 c3 d2 a3 b2 c1 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.
  5. 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.
  6. 124 Giáo trình cơ sở dữ liệu r ( S N K D H T L G) 1 12 a aa x xx 4 12 1 12 a cc y yy 3 11 2 14 a bb x zz 2 11 2 14 b bb y yy 4 12 2 15 b bb x xx 1 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
  7. 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 (F2); E E ⊨ AE E (F2); { AE E, E C} ⊨ AE C (F5); {AE D, AE C} ⊨ AE CD (F3); { AE CD, CD I} ⊨ AE I (F5); {AE D, AE I} ⊨ AE DI (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.
  8. 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.
  9. 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)+.
  10. 128 Giáo trình cơ sở dữ liệu 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 AE AEDC AEDCI A D * AB E BI E CD I * E C * 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
  11. Chƣơng 4: Phụ thuộc hàm 129 Ví dụ 4.11 Phân rã phụ thuộc hàm AB CDE đƣợc ba phụ thuộc hàm có vế phải chỉ gồm 1 thuộc tính là { AB C, AB D, AB E} Ví dụ 4.12 Làm phụ thuộc hàm ABCD E trở nên đầy đủ với F = { ABCD E, G ABD, ABC G, CD G } Giải: Tính bao đóng của 14 tập con thật sự và khác rỗng của nó và tìm thấy 4 tập con xác định E là CD, ABC, ACD và BCD. Trong đó chỉ có 2 tập con không có tập con thật sự nào có tính chất này là CD và ABC. Thay phụ thuộc hàm không đầy đủ ABCD E bởi một trong hai phụ thuộc hàm đầy đủ ABC E hoặc CD E 1 A+ = A 2 B+ = B 3 C+ = C 4 D+ = D 5 AB+ = AB 6 AC+ = AC 7 AD+ = AD 8 BC+ = BC 9 BD+ = BD 10 CD+ = CDGABE * 11 ABC+ = ABCGDE * 12 ABD+ = ABD 13 ACD+ = ACDGBE * 14 BCD+ = BCDGAE * Bằng cách loại dần từng thuộc tính, chúng ta có cách duyệt sau cho phép giảm bớt độ phức tạp tính toán. Loại A BCD+ = BCDGAE * Loại AB CD+ = CDGABE * Loại ABC D+ = D Loại ABD C+ = C
  12. 130 Giáo trình cơ sở dữ liệu Cách làm này thu đƣợc phụ thuộc đầy đủ nhƣng không chắc ít thuộc tính nhất, chẳng hạn Loại D ABC+ = ABCGDE * Loại DA BC+ = BC Loại DB AC+ = AC Loại DC AB+ = AB Ví dụ 4.13 Cho F = { A BC, CD E, E C, D AEG, ABG D, DG AB } Kiểm tra tính dƣ thừa của phụ thuộc hàm CD E. Giải: Loại CD E khỏi F, F = { A BC, E C, D AEG, ABG D, DG AB } Tính bao đóng với F mới: CD+ = CDAEGB. Vậy CD E dƣ thừa. Bây giờ chúng ta sẵn sàng phát biểu thuật toán Thuật toán 2: MinimalCover(F) Vào : Tập phụ thuộc hàm F. Ra : Một phủ tối tiểu G của F. Các bước : 1. G =  2. foreach (X Y) F do foreach A Y do G = G  {X A}
  13. Chƣơng 4: Phụ thuộc hàm 131 3. foreach (X A) G DO Z = X while (U  Z, U X, G ⊨ (U A)) do Z = U G = G\{ X A }  { Z A} 4. foreach f G do if (G\{f}  G) G = G\{f} 5. RETURN(G) Ví dụ 4.14 Tìm một phủ tối tiểu của F, với tập phụ thuộc hàm F nhƣ sau: F = { AB C, C A, BC D, ACD B, D EG, BE C, CG BD, CE AG } Giải: Thực hiện thuật toán ta có: Bƣớc 2 (phân rã): G = { AB C, C A, BC D, ACD B, D E, D G, BE C, CG B, CG D, CE A, CE G } Bƣớc 3 (làm đầy đủ hay rút gọn vế trái): Chỉ làm việc với những phụ thuộc hàm có vế trái nhiều hơn một thuộc tính Vế trái Loại Bao đóng Chọn AB A B+ = B B A+ = A BC B C+ = CA C B+ = B ACD A CD+ = CDABEG * AC D+ = D
  14. 132 Giáo trình cơ sở dữ liệu AD C+ = CA BE B E+ = E E B+ = B CG C G+ = G G C+ = CA CE C E+ = E E C+ = CA * Thay ACD B bởi CD B và CE A bởi C A (đã có trong F): G = { AB C, C A, BC D, CD B, D E, D G, BE C, CG B, CG D, CE G } Bƣớc 4 (loại phụ thuộc hàm dƣ thừa hay rút gọn tập phụ thuộc hàm): Chỉ làm việc với những phụ thuộc hàm có cùng vế phải (lƣu ý bao đóng tính trên F đã loại phụ thuộc hàm đang xét và những phụ thuộc hàm đã loại trƣớc đó) Vế phải Vế trái Bao đóng Loại C AB AB+ = AB BE BE+ = BE D BC BC+ = BCA CG CG+  CGABD * B CD CD+  CDAEGB * CG G D D+ = DE CE CE+ = CEA Kết quả sau bƣớc 4 là một phủ tối tiểu của F G = { AB C, C A, BC D, D E, D G, BE C, CG B, CE G }
  15. Chƣơng 4: Phụ thuộc hàm 133 3. Khảo sát tình huống Chúng ta đã mở đầu chƣơng bằng lƣợc đồ quan hệ với ràng buộc phụ thuộc hàm dẫn đến có sự dƣ thừa khi lƣu trữ dữ liệu trong các bảng nhƣ vậy. Chúng ta cũng đã chỉ ra cách giải quyết khi xác định đƣợc tập phụ thuộc hàm là không dƣ thừa. Cách giải quyết này sẽ phân rã lƣợc đồ ban đầu thành các lƣợc đồ con. Giờ đây chúng ta đang đối diện trƣớc bài toán phân rã bảo toàn thông tin đã đƣợc đề cập trong chƣơng mô hình cơ sở dữ liệu quan hệ. Trong mục này chúng ta sẽ khảo sát một tình huống. Chúng ta sẽ xét một lƣợc đồ quan hệ với tập phụ thuộc hàm, tìm phủ tối tiểu, cho trƣớc một quan hệ thỏa tập phụ thuộc hàm này, đƣa ra các phân rã có thể bảo toàn thông tin hoặc không. 3.1. Tình huống Quan hệ sau lƣu lịch mổ của bệnh nhân: Lịch mổ MãNV Tên bác sĩ MãBN TênBN Ngày Giờ Phòng D1011 Nguyễn A B100 Lê V 12/5/08 10:00 P15 D1011 Nguyễn A B105 Lý S 12/5/08 12:00 P15 D1024 Phạm B B108 Trần X 12/5/08 10:00 P10 D1024 Phạm B B108 Trần X 14/5/08 14:00 P10 D1032 Trần C B105 Lý S 14/5/08 16:30 P15 D1032 Trần C B110 Lê X 15/5/08 18:00 P13 Ký hiệu tên các thuộc tính MãNV, Tên bác sĩ, MãBN, TênBN, Ngày, Giờ và Phòng theo thứ tự bởi các chữ cái M, T, B, E, N, G và P, chúng ta viết lại lƣợc đồ quan hệ dƣới dạng đơn giản dễ làm việc, R = (MTBENGP). Trong lƣợc đồ này dễ nhận ra có các phụ thuộc hàm M T, B E. Thêm một chút khó khăn, chúng ta còn nhận ra thêm các phụ thuộc hàm MNG PB, BNG PM. Nhƣ vậy tập các phụ thuộc hàm là F = { M T, B E, MNG PB, BNG PM } Giải bài toán tìm phủ tối tiểu, chúng ta thấy F đã tối tiểu.
  16. 134 Giáo trình cơ sở dữ liệu 3.2. Giải quyết Lƣu các quan hệ hàm M T và B E ở các bảng riêng và đặt tên thích hợp, ta có: Bác sĩ MãNV Tên bác sĩ D1011 Nguyễn A D1024 Phạm B D1032 Trần C Bệnh nhân MãBN TênBN B100 Lê V B105 Lý S B108 Trần X B110 Lê X Lịch mổ MãNV MãBN Ngày Giờ Phòng D1011 B100 12/5/08 10:00 P15 D1011 B105 12/5/08 12:00 P15 D1024 B108 12/5/08 10:00 P10 D1024 B108 14/5/08 14:00 P10 D1032 B105 14/5/08 16:30 P15 D1032 B110 15/5/08 18:00 P13 Có thể kiểm tra trực tiếp phân rã này bảo toàn thông tin (xem chƣơng 2). 4. Kỹ thuật tableaux Tableaux là một quan hệ với các dòng gồm 2 loại biến. Loại thứ nhất không thể thay thế gồm các biến ai chỉ xuất hiện trên cột thứ i và loại thứ
  17. Chƣơng 4: Phụ thuộc hàm 135 hai có thể thay thế gồm các biến bj. Quá trình biến đổi T thành T* thoả tập phụ thuộc hàm bằng cách thay thế các biến bj đƣợc gọi là kỹ thuật tableaux. Ví dụ 4.15 Xét bảng T(A B C D) a1 a2 b1 b2 b3 a2 b4 a4 a1 b6 a3 a4 Với F = {B C, A D}. Bắt đầu với B C, ta thấy dòng 1 và 2 có B giống nhau do đó C phải giống nhau thay b4 bởi b1: T(A B C D) a1 a2 b1 b2 b3 a2 b1 a4 a1 b6 a3 a4 Tiếp tục với A D, ta thấy dòng 1 và 3 có A giống nhau do đó D phải giống nhau thay b2 bởi a4: T(A B C D) a1 a2 b1 a4 b3 a2 b1 a4 a1 b6 a3 a4 Đến đây bảng đã thỏa tập phụ thuộc hàm, ta có kết quả thay thế cuối cùng là T* (A B C D) a1 a2 b1 a4 b3 a2 b1 a4 a1 b6 a3 a4 Tuy kỹ thuật tableaux đòi hỏi tính toán nhiều, nhƣng do tính trực quan, nó đƣợc sử dụng trong nhiều trƣờng hợp. 4.1. Áp dụng giải bài toán thành viên + Để kiểm tra (X Y) F , ta xây dựng bảng TX, áp dụng kỹ thuật tableaux * đƣợc T X, kiểm tra các cột của Y xem có chứa toàn biến loại a không. 1. TX gồm 2 dòng, một dòng tồn a và dòng còn lại với các biến a nằm trên các cột của X, các cột còn lại chứa các biến b
  18. 136 Giáo trình cơ sở dữ liệu 2. Tính T*X 3. Kiểm tra cột A có chứa toàn các biến loại a hay không Ví dụ 4.16 Kiểm tra (B D) F+, với F = {B C, C D} và R = {ABCDE}. Giải: Ta có TB (A B C D E) a1 a2 a3 a4 a5 b1 a2 b2 b3 b4 Tính T*B (A B C D E) a1 a2 a3 a4 a5 b1 a2 a3 a4 b4 Kiểm tra cột D và kết luận B D là thành viên của F+ 4.2. Áp dụng giải bài toán bao đóng Để tính X+, ta thực hiện 1. Xây dựng TX 2. Tính T*X 3. Tập hợp các cột toàn a Ví dụ 4.17 Giải: Tính B+, với F = {B C, C D} và R = {ABCDE}. Giải: Thực hiện giống ví dụ trên, ta có B+=BCD
  19. Chƣơng 4: Phụ thuộc hàm 137 TÓM TẮT Phụ thuộc hàm là một quan hệ hàm; Việc xuất hiện phụ thuộc hàm dẫn đến lƣu trữ dƣ thừa; Lƣu riêng các quan hệ hàm là một giải pháp; Phân rã một quan hệ có thể dẫn đến không bảo toàn thông tin; Với tập phụ thuộc hàm, cần bảo đảm tính tối tiểu để khi phân rã không làm dƣ thừa các quan hệ con; Thuật toán tìm phủ tối tiểu dựa trên kỹ năng xác định tính thành viên của một phụ thuộc hàm; Kiểm tra tính thành viên của một phụ thuộc hàm dựa trên bộ luật dẫn; Kỹ thuật tính bao đóng là một kỹ thuật đơn giản kiểm tra tính thành viên; Kỹ thuật tableaux là một kỹ thuật khác cũng cho phép kiểm tra tính thành viên.
  20. 138 Giáo trình cơ sở dữ liệu BÀI TẬP 1. Cho quan hệ: r A B C 1 4 2 3 5 6 3 4 6 7 3 8 9 1 0 r thoả phụ thuộc hàm nào sau đây: A B, A C, AB C, BC A 2. Cho một phản ví dụ chứng tỏ luật { AB C, C A } ⊨ { A B } là sai. 3. Cho tập phụ thuộc hàm F = { AB C, C D, D A }. Hãy: a. Chỉ ra một khoá; b. Chỉ ra một siêu khoá; 4. Cho tập phụ thuộc hàm F = { A B, BC D }. Dùng bộ luật, cho biết phụ thuộc hàm sau đây là thành viên của F+: AC D, B D và AD B. 5. Dùng bộ luật, chứng tỏ {XY W, Y Z, WZ P, WP QR, Q X} ⊨ XY P. 6. Kiểm tra tính tƣơng đƣơng giữa hai tập phụ thuộc hàm F = { A BC, A D, CD E} và G = { A BCE, A ABD, CD E }. 7. Loại các thuộc tính dƣ thừa trái khỏi các phụ thuộc hàm của F = { X YW, XW Z, Z Y, XY Z } 8. Loại các phụ thuộc hàm dƣ thừa ra khỏi F = { X Y, Y X, Y Z, Z Y, X Z, Z X } 9. Cho tập phụ thuộc hàm F ={ AB C, B D, CD E, CE GH, G A } Tính AB+ suy ra AB E.
  21. Chƣơng 4: Phụ thuộc hàm 139 F ⊨ (BG C) đúng hay sai (dùng cả luật dẫn lẫn kỹ thuật bao đóng và kỹ thuật tableaux). 10. Tìm một phủ tối tiểu của F = { A C, AB C, C DI, CD I, EC AB, EI C } 11. Tìm một tập phụ thuộc hàm có hai phủ tối tiểu với số phụ thuộc hàm khác nhau. 12. Xét lƣợc đồ quan hệ R của quan hệ thời khoá biểu, lƣu thông tin về lịch giảng trong một trƣờng đại học (xem case study 2) trong học kỳ hiện tại: R = (LMGTBP) Trong đó L, M, G, T, B và P theo thứ tự là viết tắt của Mã-lớp, Mã- môn, Mã-giảng-viên, Thứ, Buổi và Mã-phòng. Hãy xác định tập phụ thuộc hàm. 13. Một đại lý chuyên cung cấp lao động theo thời vụ cho các khách sạn trong thành phố. Quan hệ sau lƣu thông tin về hợp đồng giữa đại lý với khách sạn. Vì số lao động nhƣ vậy rất đông và mang tính thời vụ nên một hợp đồng có nhiều lao động và xác định tổng số giờ làm việc của mỗi lao động. Hợp đồng SốBHXH Số HĐ Giờ Tên NV MãKS TênKS 1135 C1024 16 Lê V K25 Rex 1057 C1024 24 Lý S K25 Rex 1068 C1025 28 Trần X K04 Royal 1135 C1025 15 Lê V K04 Royal a. Xác định tập phụ thuộc hàm b. Tìm phủ tối tiểu c. Phân rã và kiểm tra tính bảo toàn thông tin
  22. Chƣơng 5 DẠNG CHUẨN Mục tiêu của chƣơng. Trong chƣơng này chúng ta sẽ học về: Khái niệm dạng chuẩn; Khái niệm thuộc tính khoá, thuộc tính không khoá; Bài toán tìm tập tất cả các khoá; Giá trị nguyên tố và dạng chuẩn 1; Phụ thuộc đầy đủ và dạng chuẩn 2; Phụ thuộc bắc cầu và dạng chuẩn 3; Phụ thuộc không tầm thƣờng và dạng chuẩn BC; Phân rã và chiếu của tập phụ thuộc hàm; Phân rã bảo toàn tập phụ thuộc hàm; Phân rã đặc trƣng đầy đủ tập phụ thuộc hàm. Các thao tác trên quan hệ có thể ảnh hƣởng đến tính toàn vẹn dữ liệu. Phụ thuộc hàm là một dạng ràng buộc toàn vẹn. Với ràng buộc phụ thuộc hàm, chúng ta sẽ tìm hiểu các dạng chuẩn của lƣợc đồ quan hệ nhƣ là một tiêu chuẩn cho việc thiết kế cơ sở dữ liệu quan hệ nhằm bảo đảm giảm tối đa việc lƣu trữ dƣ thừa. Nhƣ vậy dạng chuẩn là một khái niệm cho phép đánh giá sự dư thừa trong lưu trữ. Ví dụ 5.1 Cho quan hệ r ( A B C D ) a1 b1 c1 d1 a1 b2 c2 d1 a2 b3 c1 d2 Quan sát thấy r thoả phụ thuộc hàm A D. Giả sử đây là ràng buộc mà r phải thỏa, tức r đƣợc định nghĩa trên lƣợc đồ với R = (ABCD) và F
  23. 142 Giáo trình cơ sở dữ liệu = {A D}. Rõ ràng với việc sử dụng lƣợc đồ trên đã gây ra nguy cơ lƣu trữ dƣ thừa. Chẳng hạn nếu chúng ta thay đổi dòng 1 bằng câu lệnh cập nhật CH(r; a1, b1, c1, d1; C = c1, D = d3), r sẽ vi phạm phụ thuộc hàm A D. Ví dụ 5.2 Dùng lại ví dụ trên, bổ sung thêm phụ thuộc hàm AB C, tức F = {AB C, A D}. Chúng ta lƣu r trong 2 lƣợc đồ50 , nhƣ sau: r1 ( A B C) r2 ( A D ) a1 b1 c1 a1 d1 a1 b2 c2 a2 d2 a2 b3 c1 Với AB là một khoá chỉ định của R1 = ABC, và A là một khoá chỉ định của R2 = AD. Thật ra đây là kết quả của 2 phép chiếu. Bây giờ muốn xây dựng lại r chỉ cần dùng phép kết (bài toán bảo toàn thông tin). Cách lƣu trữ này tránh đƣợc sự dƣ thừa. Trong ví dụ trên chúng ta thấy các phụ thuộc hàm đã chuyển thành các phụ thuộc khoá. Một trong các bài toán quan trọng trong chƣơng này là bài toán tìm tất cả các khoá của lƣợc đồ . Khái niệm dạng chuẩn nói chung đều liên quan đến khoá. Mục tiêu của chƣơng này là xác định dạng chuẩn của lƣợc đồ quan hệ dạng . Lược đồ được gọi là không đạt chuẩn nếu tìm thấy phụ thuộc hàm X A với X không chứa khoá và A không thuộc X. Khi ấy quan hệ định nghĩa trên R có nguy cơ xuất hiện dƣ thừa. Chẳng hạn, trong 2 ví dụ trên, r là dƣ thừa trong lúc r1 và r2 thì không. 1. Bài toán tìm tất cả khoá Trong chƣơng 2 chúng ta đã định nghĩa khoá của một lƣợc đồ quan hệ, là khoá của tất cả các quan hệ thuộc SATR(F). Phụ thuộc hàm X Y đƣợc gọi là phụ thuộc khoá nếu X là một khoá của . 50 xem chƣơng 4,
  24. Chƣơng 5: Dạng chuẩn 143 Cho , ta có các nhận xét sau: 1. Khoá phải chứa các thuộc tính có ở vế trái của một phụ thuộc hàm nào đó nhƣng không có ở vế phải của tất cả các phụ thuộc hàm 2. Khoá không chứa các thuộc tính chỉ có ở vế phải các phụ thuộc hàm 3. Xét tập con X, chƣa là khoá, với thuộc tính A không nằm trong X có trong vế trái của một phụ thuộc hàm nào đó, ta có khoá không thể chứa XA nếu một trong hai điều sau đúng a. A X+ b. Xuất hiện một thuộc tính dƣ thừa trong XA Ví dụ 5.3 Tìm tất cả các khoá của với R=(DSMG) và F={M D, D M, DS G, MS G}. Giải: Gọi K là tập các khoá ta có: K  {D, S, M, G, DS, DM, DG, SM, SG, MG, DSM, DSG, DMG, SMG}; S là thuộc tính không có ở vế phải (của bất kỳ phụ thuộc hàm thuộc F), còn G là thuộc tính chỉ có ở vế phải (ở một phụ thuộc hàm nào đó thuộc F). Theo nhận xét 1 và 2, khoá phải chứa S và không chứa G, suy ra K  {S, DS, SM, DSM} Xét S, vì S chƣa là khoá, loại S, K  {DS, SM, DSM}. Với S vừa loại ta quan tâm đến 2 thuộc tính bổ sung cho S là M và D: o Với M, MS là khoá, loại các siêu khoá K  {DS, SM} o Với D, DS là khoá, K  {DS, SM} Vậy K = {DS, SM} Ví dụ 5.4 Tìm tất cả các khoá của với R=(ABCDE) và F={AB B, CB D, AE C}. Giải: Gọi K là tập các khoá: Khoá phải chứa AE và không chứa D, K  {AE, AEB, AEC, AEBC} Vì AE chƣa là khoá, AE+ = AEC, theo nhận xét 3 ta có K  {AEB} Còn duy nhất 1 ứng viên, vậy K = {AEB}
  25. 144 Giáo trình cơ sở dữ liệu Nếu F là phủ tối tiểu, việc tìm khoá sẽ đỡ phức tạp hơn. Xét ví dụ sau: Ví dụ 5.5 Làm lại ví dụ trên với F = {CB D, AE C} tối tiểu. Khoá phải chứa AEB và không chứa D, tập ứng viên chỉ còn lại 2 {AEB, AEBC}. Do AEB là khoá cho nên nó là khoá duy nhất. Với các quan hệ phức tạp gồm nhiều thuộc tính chúng ta cần đến thuật toán. Dựa vào các nhận xét đã nêu chúng ta sẽ phát triển một cây tìm tập các khoá với gốc là các thuộc tính buộc phải có trong khoá và các nhánh đƣợc phát triển bằng các thuộc tính còn lại sau khi đã loại bỏ các thuộc tính không thể tham gia vào khoá. Các nút đƣợc phát triển chỉ khi chúng bảo đảm tìm thấy khoá do đó cây nên đƣợc phát triển theo chiều rộng và lệch trái. Trong thuật toán sau, chúng ta xây dựng cây theo chiều rộng dựa trên các nguyên tắc: 1. Gốc là tập thuộc tính gồm các thuộc tính có ở vế trái của một phụ thuộc hàm nào đó, nhƣng không có ở vế phải của tất cả các phụ thuộc hàm. 2. Với mỗi nút lá của cây, xác định tập bổ sung là tập bổ sung của nút cha loại đi các thuộc tính nằm trong bao đóng của nó (tập bổ sung ở nút gốc là những thuộc tính không nằm trong bao đóng của nút gốc). 3. Phát triển cây theo mỗi thuộc tính bổ sung 4. Loại các nút con là siêu khoá 5. Dừng ở các nút con là khoá 6. Phát triển các nút con còn lại Thuật toán 3: Tìm tất cả các khoá Vào : Lƣợc đồ quan hệ Ra : tập các khoá K Các bước : 1. Xây dựng cây theo các nguyên tắc đã nêu 2. Tập hợp các khoá trên cây vào K 3. RETURN(K)
  26. Chƣơng 5: Dạng chuẩn 145 Ví dụ 5.6 Cho lƣợc đồ với R = (ABC) và F = { A B, B C } ta có cây chỉ gồm gốc A và đây là khoá duy nhất. Ví dụ 5.7 Cho lƣợc đồ với R = (ABC) và F = { AB C, C A, A B } ta có  ABC A B C Nếu F tối tiểu thì cây sẽ gọn hơn, chẳng hạn với F = {A BC, C A}  ABC A C Ví dụ 5.8 Xét lƣợc đồ quan hệ R = (DSMG) với F = { M D, D M, DS G, MS G }. S MD SM SD 2. Các dạng chuẩn Trƣớc hết chúng ta cần một định nghĩa. Cho lƣợc đồ quan hệ . Giả sử K là tập tất cả các khoá. Thuộc tính khoá là thuộc tính tham gia vào một khoá bất kỳ trong K. Ngƣợc lại gọi là thuộc tính không khoá. 2.1. Dạng chuẩn 1 Thuộc tính A được gọi là nguyên tố nếu v dom(A), v không phải là tập các giá trị hoặc là một giá trị phức hợp. Một cách tổng quát, về mặt logic, một giá trị có thể là một giá trị phức, nhƣng nếu không thể truy xuất trực tiếp các giá trị thành phần vẫn xem giá trị này là nguyên tố51. 51 E.F.Codd (1990) phát biểu giá trị là nguyên tố nếu không thể phân rã bởi hệ quản trị cơ sở dữ liệu, kể cả khi dùng các hàm. Về sau, H.Darwen và C.J.Date (1992) cho rằng phát
  27. 146 Giáo trình cơ sở dữ liệu Ví dụ 5.9 Thuộc tính ngày sinh có kiểu DATE là nguyên tố, còn nếu có kiểu cấu trúc {day, month, year} thì không còn nguyên tố nữa. Thuộc tính điểm có kiểu INTEGER là nguyên tố, còn nếu có kiểu mảng gồm nhiều số thì không nguyên tố.52 Định nghĩa 5.1 1. Lược đồ quan hệ đạt dạng chuẩn 1 nếu mọi thuộc tính của nó đều nguyên tố. 2. Lược đồ cơ sở dữ liệu đạt chuẩn 1 nếu mọi lược đồ quan hệ con đều đạt chuẩn 1 Khi làm việc với mô hình quan hệ, chúng ta thừa nhận các lƣợc đồ cơ sở dữ liệu đều đạt chuẩn 153 vì miền giá trị của các thuộc tính đƣợc coi là nguyên tố. Ví dụ 5.10 Quan hệ KH ( MãKH TênKH SốĐT) k02 Lan {08123456, 0912999999} Không đạt chuẩn 1, vì kiểu của SốĐT là kiểu mảng. Nếu đổi kiểu của SốĐT thành kiểu xâu ký tự thì quan hệ trên đạt chuẩn 1, nhƣng không thể truy xuất trực tiếp một trong số các số điện thoại của khách hàng đƣợc. biểu của Codd là không rõ ràng. Theo C.J.Date, một bảng đạt chuẩn 1 nếu nó đẳng cấu với một quan hệ. Theo đó, giao giữa mỗi dòng và mỗi cột của một bảng đạt chuẩn 1, nếu khác trống, chỉ chứa một giá trị duy nhất. Thuật ngữ nguyên tố đƣợc dùng trong tài liệu này đƣợc hiểu theo nghĩa của C.J.Date. Để tránh nhập nhằng, một số tài liệu sử dụng thuật ngữ repeating group thay cho thuật ngữ nguyên tố. 52 Xét việc gán hai số 5 và 7 vào biến x. Nếu kiểu của x là mảng, gán x[0] = 5 và x[1] = 7, kiểu mảng không là nguyên tố. Nếu kiểu của x là nguyên, chúng ta không thể gán hai giá trị trên vào x đƣợc. Tuy nhiên nếu biểu diễn (5, 7) = 5*12 + 7 = 67, thì có thể gán (gián tiếp) hai giá trị trên qua giá trị mới là 67 vào biến x. Rõ ràng kiểu nguyên là nguyên tố. 53 có quan điểm cho rằng quan hệ [chi tiết hoá đơn](HDSố, MãHG, SốL, ĐGiá, TTiền) có thuộc tính dẫn xuất TTiền = SốL ĐGiá đƣợc cho là không nguyên tố. Quan điểm của chúng tôi ở đây chỉ chú trọng đến kiểu của thuộc tính có là nguyên tố hay không mà thôi.
  28. Chƣơng 5: Dạng chuẩn 147 2.2. Dạng chuẩn 2 Cho tập phụ thuộc hàm F, phụ thuộc hàm (X Y) F+ đƣợc gọi là không dƣ thừa trái nếu Y là phụ thuộc đầy đủ vào X dƣới F. Ví dụ 5.11 Cho lƣợc đồ với R = (ABCD) và F = {AB C, A D}. Vì AB là khoá duy nhất suy ra C và D là hai thuộc tính không khoá còn A và B là hai thuộc tính khoá. Ngoài ra C phụ thuộc đầy đủ vào khoá duy nhất AB còn D thì không. Ví dụ 5.12 Xét lƣợc đồ cơ sở dữ liệu { , }. Với lƣợc đồ quan hệ trƣớc, ta có A và B là hai thuộc tính khoá còn C là thuộc tính không khoá, hơn nữa C phụ thuộc đầy đủ vào khoá duy nhất AB. Với lƣợc đồ quan hệ sau, ta có là A thuộc tính khoá còn D là thuộc tính không khoá và D phụ thuộc đầy đủ vào khoá duy nhất A. Định nghĩa 5.2 1. Lược đồ quan hệ R đạt dạng chuẩn 2 dưới F nếu R đạt dạng chuẩn 1 và mọi thuộc tính không khoá của R đều phải phụ thuộc đầy đủ vào tất cả các khoá của R. 2. Một lược đồ cơ sở dữ liệu D đạt dạng chuẩn 2 dưới F nếu mọi lược đồ quan hệ Rj của D đều đạt dạng chuẩn 2 dưới F. Nói cách khác, mỗi khi tìm thấy vi phạm, tức tìm thấy phụ thuộc hàm X A mà X không chứa khoá, nếu A là thuộc tính không khoá còn X là tập con thực sự của một khoá nào đó thì vi phạm này là vi phạm chuẩn 2. Ví dụ 5.13 Lƣợc đồ không đạt chuẩn 2 vì tìm thấy vi phạm A D với D không khoá còn A thuộc khoá AB. Ví dụ 5.14 Lƣợc đồ cơ sở dữ liệu { , } đạt chuẩn 2 vì các lƣợc đồ quan hệ đều đạt chuẩn 2. Dạng chuẩn 2 vẫn còn ẩn chứa sự dƣ thừa dữ liệu, nghĩa là vẫn còn tìm thấy các vi phạm, do đó vẫn còn đó sự bất ổn. Xét ví dụ sau.
  29. 148 Giáo trình cơ sở dữ liệu Ví dụ 5.15 Cho quan hệ r định nghĩa trên lƣợc đồ : r ( A B C D ) a1 b1 c1 d1 a1 b2 c2 d2 a2 b3 c1 d1 Lƣợc đồ này đạt chuẩn 2 nhƣng lƣu trữ trên r vẫn dƣ thừa, tức các thao tác trên r có khả năng gây ra bất ổn. Thao tác CH(r; a1, b1, c1, d1; C=c3, D=d1) làm cho r không thỏa phụ thuộc hàm D C. 2.3. Dạng chuẩn 3 Cho tập phụ thuộc hàm F, phụ thuộc hàm dẫn xuất (X Z) F+ đƣợc gọi là phụ thuộc hàm bắc cầu, nếu có Y sao cho X Y (Y ↛ X) và Y Z (Z ∉ XY). Với phụ thuộc hàm bắc cầu X Z, ta còn nói Z là phụ thuộc bắc cầu vào X (qua Y) Ví dụ 5.16 Trong lƣợc đồ , phụ thuộc hàm AB D là phụ thuộc hàm bắc cầu vì AB C và C D (C ↛ AB và D ∉ ABC).). Định nghĩa 5.3 1. Lược đồ quan hệ R đạt dạng chuẩn 3 dưới F nếu R đạt chuẩn 1 và mọi thuộc tính không khoá của R đều không phụ thuộc bắc cầu vào bất kỳ khoá nào của R. 2. Lược đồ cơ sở dữ liệu D là đạt dạng chuẩn 3 dưới F nếu mọi lược đồ quan hệ Rj của D đều đạt dạng chuẩn 3 dưới F. Nói cách khác, mỗi khi tìm thấy vi phạm, tức tìm thấy phụ thuộc hàm X A mà X không chứa khoá, nếu A là thuộc tính không khoá thì vi phạm này là vi phạm chuẩn 3. Rõ ràng một vi phạm chuẩn 2, cũng vi phạm chuẩn 3 do đó nếu một lƣợc đồ đạt chuẩn 3 thì nó đạt chuẩn 2. Ví dụ 5.17 Lƣợc đồ không đạt dạng chuẩn 3 vì tìm thấy vi phạm C D với D là thuộc tính không khoá.
  30. Chƣơng 5: Dạng chuẩn 149 Ví dụ 5.18 Lƣợc đồ cơ sở dữ liệu { , } đạt chuẩn 3 (do đó đạt chuẩn 2) vì các lƣợc đồ quan hệ đều đạt chuẩn 3. Ngay cả dạng chuẩn 3 vẫn còn ẩn chứa sự dƣ thừa dữ liệu, nghĩa là vẫn còn có các vi phạm, do đó vẫn còn tiếp tục có sự bất ổn. Xét ví dụ sau. Ví dụ 5.19 Cho quan hệ r định nghĩa trên lƣợc đồ . Lƣợc đồ này đạt chuẩn 3 vì không có thuộc tính không khoá. r ( A B C) a1 b1 c1 a1 b2 c2 a2 b1 c1 Tuy nhiên thao tác cập nhật CH(r; a1, b1, c1; B = b2, C = c1) làm nó vi phạm C B. 2.4. Dạng chuẩn BC (Boyce-Codd) Đây là dạng chuẩn cao nhất khi làm việc với các ràng buộc phụ thuộc hàm. Với lƣợc đồ quan hệ đạt chuẩn này chúng ta sẽ không tìm thấy bất kỳ một vi phạm nào. Nhắc lại, trong chƣơng này, khi nói tới việc tìm thấy một vi phạm nghĩa là tìm thấy một phụ thuộc hàm không tầm thƣờng mà lƣợc đồ cơ sở dữ liệu đang xét phải thỏa. Một phụ thuộc hàm không tầm thƣờng là phụ thuộc hàm hoặc vế phải không có phần giao với vế trái hoặc hợp của hai vế là tập con thật sự của R. Định nghĩa 5.4 1. Lược đồ quan hệ R đạt dạng chuẩn BC dưới F nếu R đã đạt dạng chuẩn 1 và mọi thuộc tính của R đều không phụ thuộc bắc cầu vào bất kỳ khoá nào của R. 2. Lược đồ cơ sở dữ liệu D đạt dạng chuẩn BC dưới F nếu mọi lược đồ quan hệ Rj của D đều đạt dạng chuẩn BC dưới F. Nói cách khác, mỗi khi tìm thấy vi phạm, tức tìm thấy phụ thuộc hàm X A mà X không chứa khoá thì vi phạm này là vi phạm chuẩn BC. Rõ ràng một vi phạm chuẩn 3, cũng vi phạm chuẩn BC do đó nếu một lƣợc đồ đạt chuẩn BC thì nó đạt chuẩn 3. Ta có:
  31. 150 Giáo trình cơ sở dữ liệu Cho lược đồ . Gọi NF1R(F), NF2R(F), NF3R(F) và NFBCR(F) thứ tự là các quan hệ thuộc SATR(F) đạt chuẩn 1, 2, 3 và BC, ta có NF1 ⊃ NF2 ⊃ NF3 ⊃ NFBC Ví dụ 5.20 Lƣợc đồ không đạt dạng chuẩn BC, vì có vi phạm C B. Ví dụ 5.21 Lƣợc đồ cơ sở dữ liệu { , } đạt dạng chuẩn BC, vì các lƣợc đồ quan hệ con đều đạt chuẩn BC54. 2.5. Xác định dạng chuẩn Ngoài trừ dạng chuẩn BC, khi xét một lƣợc đồ có đạt dạng chuẩn 2 hoặc 3 hay không chúng ta phải xét một thuộc tính nào đó có là thuộc tính khoá hay không. Nói cách khác, muốn xác định dạng chuẩn của một lƣợc đồ quan hệ trƣớc hết chúng ta cần tìm tập các khoá. Sau đây là các bƣớc xác định dạng chuẩn của lƣợc đồ quan hệ : 1. Nếu không tìm thấy bất kỳ vi phạm nào, đạt chuẩn BC, kết thúc; 2. Tìm tập khoá; 3. Nếu không tìm thấy vi phạm chuẩn 3, đạt chuẩn 3, kết thúc; 4. Nếu không tìm thấy vi phạm chuẩn 2, đạt chuẩn 2, kết thúc; 5. đạt chuẩn 1. Ví dụ 5.22 Xác định dạng chuẩn của lƣợc đồ = . Giải: 1. Tìm thấy vi phạm C D, vì C+ = CD R, không đạt chuẩn BC. 2. Ta có AB là khoá duy nhất. 3. Tìm thấy vi phạm C D, C là thuộc tính không khoá, không đạt chuẩn 3. 4. Không tìm thấy bất kỳ vi phạm chuẩn 2 nào, đạt chuẩn 2. 54 Với điều kiện bổ sung ràng buộc tồn tại r(ABC)[BC]  s(BC).
  32. Chƣơng 5: Dạng chuẩn 151 Chúng ta chấp nhận kết quả sau (xem bài tập): Nếu có một vi phạm vi phạm dạng chuẩn, thì vi phạm dạng này có thể tìm thấy trong F. Với kết quả này chúng ta có cách xác định dạng chuẩn nhƣ sau: 1. Tìm tập khoá; 2. Liệt kê các vi phạm của F; 3. Xác định vế trái thuộc khóa; 4. Xác định các thuộc tính không khóa; 5. Kết luận dạng chuẩn. Sử dụng bảng dạng sau để trình bày quá trình xác định dạng chuẩn X Y X+ X ⊊ K A ∊ Y Vi phạm Ví dụ 5.23 Xác định dạng chuẩn của lƣợc đồ = . Giải: Biết khóa duy nhất là AB. Lập bảng X Y X+ X ⊊ K A ∊ Y Vi phạm C D CD D Chuẩn 3 D C CD C Chuẩn 3 Vậy đạt chuẩn 2. Ví dụ 5.24 Xác định dạng chuẩn của lƣợc đồ = . Giải: Biết khóa duy nhất là A. Lập bảng X Y X+ X ⊊ K A ∊ Y Vi phạm B C BC C Chuẩn 3 Vậy đạt chuẩn 2.
  33. 152 Giáo trình cơ sở dữ liệu Ví dụ 5.25 Xác định dạng chuẩn của lƣợc đồ = . Giải: Biết khóa duy nhất là AD. Lập bảng X Y X+ X ⊊ K A ∊ Y Vi phạm A B ABC AD B Chuẩn 2 B C BC C Chuẩn 3 Vậy đạt chuẩn 1. 3. Chiếu của tập phụ thuộc hàm Muốn xác định dạng chuẩn của lƣợc đồ cơ sở dữ liệu ta phải xác định dạng chuẩn của các lƣợc đồ quan hệ thành phần. Trong trƣờng hợp ràng buộc phụ thuộc hàm đƣợc cho trên cơ sở dữ liệu chúng ta không có cơ sở để xác định dạng chuẩn của các lƣợc đồ quan hệ thành phần cho đến khi tìm thấy các tập phụ thuộc hàm thành phần. 3.1. Khái niệm Cho tập phụ thuộc hàm F và tập con các thuộc tính S. Xét f F+, f = (X → Y). Tập phụ thuộc hàm S(f) = {X → A | XA  S} đƣợc gọi là chiếu của f xuống R. Định nghĩa 5.5 Cho tập phụ thuộc hàm F và tập thuộc tính S. Trong ngữ cảnh của F, chiếu của F lên S, ký hiệu S(F), là tập các phụ thuộc hàm hệ quả định nghĩa trên S. Thật ra chúng ta chỉ quan tâm đến vế trái của phụ thuộc hàm, do đó với X là tập con của S, ký hiệu 푆 = 푆 퐹, = → : ∈ 푆 Ký hiệu SF gồm họ các tập con thực sự của S là hội của các vế trái nằm trong S, ta có: 푆 퐹 = 푆 ∈푆퐹
  34. Chƣơng 5: Dạng chuẩn 153 Sau đây là các bƣớc tìm S(F): 1. Tìm SF 2. Tính bao đóng của tất cả các phần tử của SF 3. Giao các bao đóng này với S, xác định S(F) 4. Rút gọn, hay tìm phủ tối tiểu, nếu cần. Ví dụ 5.26 Cho F = {AB CD, C D, D C}, tính ABC(F) và CD(F). Giải: Tính ABCF = {AB, C}, CDF = {C, D}; Tính AB+ = R, C+ = D+ = CD; Suy ra ABC(F) = {AB C} và CD(F) = {C D, D C} Ví dụ 5.27 Cho F = {A C, B D, CD H}, tính ABH(F) Giải: Tính ABHF = {A, B, AB}; Tính A+ = AC, B+ = BD, AB+ = R; Suy ra ABH(F) = {AB H} Ví dụ 5.28 Xác định dạng chuẩn của lƣợc đồ cơ sở dữ liệu {ABC, CD} với ràng buộc là tập phụ thuộc hàm F = {AB CD, C D, D C}. Giải: Tính ABC(F) = {AB C} CD(F) = {C D, D C}, Ta có lƣợc đồ cơ sở dữ liệu { , } = { , } đạt chuẩn BC vì các lƣợc đồ thành phần đều đạt chuẩn BC.
  35. 154 Giáo trình cơ sở dữ liệu 3.2. Tính chất đặc trƣng đầy đủ F Khoá cũng là một dạng ràng buộc phụ thuộc hàm, nói cách khác khoá sinh ra một phụ thuộc hàm. Một lƣợc đồ quan hệ mà tập phụ thuộc hàm đƣợc sinh ra từ tập khoá sẽ rất có ý nghĩa trong thực hành. Định nghĩa 5.6 1. Một phụ thuộc hàm f = X Y được gọi là phụ thuộc hàm được in trong lược đồ quan hệ R nếu XY = R. 2. Một phụ thuộc hàm f = X Y được gọi là phụ thuộc hàm được in trong lược đồ cơ sở dữ liệu D={ R1, R2, , Rp } nếu có j sao cho f được in trong Rj. Định nghĩa 5.7 Cho lược đồ cơ sở dữ liệu D. Gọi G là tập các phụ thuộc hàm được in trong D. Cho tập F các phụ thuộc hàm. Ta nói D là đặc trưng đầy đủ F, hay F được đặc trưng đầy đủ trong D, nếu F  G. Ví dụ 5.29 Xét lƣợc đồ D = {(ABC), (BD)} với ràng buộc phụ thuộc hàm F = {AC BD, B D}. Lƣợc đồ D‟ = {(ACB), (BD)} với các phụ thuộc hàm đƣợc in G = {AC B, B D} đƣợc cảm sinh từ tập khoá. Kiểm tra G  F suy ra D‟ đặc trƣng đầy đủ F. Nhƣ vậy thay vì làm việc với lƣợc đồ D, ta làm việc với lƣợc đồ tƣơng đƣơng D‟. Ví dụ 5.30 Cho tập phụ thuộc hàm : F = { B1B2 A, D1D2 B1, D1D2 B2, B1 C1, B2 C2, D1 A, D2 A, AB1C2 D2, AB2C1 D1} Xét lƣợc đồ cơ sở dữ liệu : D = { , , , , } ta có F đƣợc đặc trƣng đầy đủ trong D.
  36. Chƣơng 5: Dạng chuẩn 155 3.3. Tính chất ép thỏa F Thực tế không dễ dàng đạt đƣợc tính đặc trƣng đầy đủ F, chúng ta chỉ cần hội của tất cả các tập phụ thuộc hàm chiếu từ F tƣơng đƣơng với F là đủ. Tính chất này đƣợc gọi là tính ép thỏa F. Định nghĩa 5.8 1. Một phụ thuộc hàm f = (X Y) được gọi là được bao trong lược đồ R nếu XY  R. 2. Một phụ thuộc hàm f = (X Y) được gọi là được bao trong lược đồ cơ sở dữ liệu D = { R1, R2, , Rp } nếu có j sao cho f được bao trong Rj. Định nghĩa 5.9 Cho lược đồ cơ sở dữ liệu D và G là tập các phụ thuộc hàm được bao trong D. Cho tập F các phụ thuộc hàm, ta nói D ép thỏa F, hay F bị ép thỏa trong D, nếu F  G. Ví dụ 5.31 Cho lƣợc đồ cơ sở dữ liệu D = { , , } Ta thấy lƣợc đồ này ép thỏa tập phụ thuộc hàm sau F = {A BC, C A, A D, D E, A E} Tính ép thỏa ở đây và tính đặc trƣng đầy đủ ở mục trƣớc cho phép ta chỉ cần kiểm tra các ràng buộc phụ thuộc hàm trên từng quan hệ là đủ55. 55 Nhất quán cục bộ suy ra nhất quán toàn cục. Trong thực hành, điều này cho phép triển khai hệ thống một cách hiệu quả.
  37. 156 Giáo trình cơ sở dữ liệu Ví dụ 5.32 Cho cơ sở dữ liệu với các ràng buộc F = {A BC, C A, A D, D E, A E} r1 ( A B C ) r2 ( B C D) r3 (D E) a1 b1 c1 b1 c1 d1 d1 e1 a2 b1 c2 b2 c2 d2 d2 e2 a3 b3 c5 b3 c3 d3 d3 e1 a4 b4 c2 b4 c1 d1 a5 b1 c4 b5 c2 d2 Ta thấy F bị ép thoả trong D với các lƣợc đồ thành phần D = { , , } Giờ đây chỉ cần kiểm tra các ràng buộc trên mỗi quan hệ là đủ. Quan sát thấy r1 vi phạm phụ thuộc hàm C A, suy ra cơ sở dữ liệu là không nhất quán. Ví dụ 5.33 Lƣợc đồ = không đạt dạng chuẩn BC. Xét R1 = ABC, R2 = CD, tìm các tập phụ thuộc hàm chiếu, ta có lƣợc đồ cơ sở dữ liệu { , } đạt chuẩn BC và ép thỏa F (thật ra đặc trƣng đầy đủ F). 3.4. Vấn đề với dạng chuẩn BC Với dạng chuẩn BC, không còn tìm thấy các phụ thuộc hàm có nguy cơ dẫn đến mâu thuẫn, tính dƣ thừa đã đƣợc loại bỏ triệt để (dĩ nhiên chỉ đối với phụ thuộc hàm). Tuy nhiên, lại nảy sinh vấn đề khác đó là tính ép thỏa tập phụ thuộc hàm. Không có gì bảo đảm tìm thấy một lƣợc đồ cơ sở dữ liệu đạt chuẩn BC ép thoả F. Ví dụ 5.34 Cho lƣợc đồ quan hệ R =(ABC) và tập phụ thuộc hàm F = {AB C, C B}56. Lƣợc đồ này đạt dạng chuẩn 3 nhƣng ta không thể tìm đƣợc một lƣợc đồ cơ sở dữ liệu D đạt dạng chuẩn BC mà F bị ép thỏa trong D57 56 đây là một lƣợc đồ thực tế, lƣợc đồ cơ sở dữ liệu cho một trung tâm luyện thi đại học, ở đây A: Lớp, B: Môn và C: Giảng viên. Theo đó, lớp và môn xác định giảng viên, còn giảng viên xác định môn.
  38. Chƣơng 5: Dạng chuẩn 157 TÓM TẮT Với dạng chuẩn chúng ta có một cách đo mức độ dƣ thừa trong lƣu trữ với ràng buộc là các phụ thuộc hàm; Nếu tìm thấy bất kỳ một phụ thuộc hàm không tầm thƣờng nào đó, thì lƣợc đồ quan hệ là vi phạm chuẩn BC; Tìm thấy phụ thuộc hàm dạng X A với A là thuộc tính không khoá, thì lƣợc đồ quan hệ là vi phạm chuẩn 3; Tìm thấy phụ thuộc hàm dạng X A với A là thuộc tính không khoá còn X là tập con thật sự của một khoá nào đó, thì lƣợc đồ quan hệ là vi phạm chuẩn 2; Giải bài toán tìm tất cả các khoá là cơ sở để xác định chuẩn 2 hoặc 3; Kiểm tra một lƣợc đồ có vi phạm chuẩn BC hay không, chúng ta không cần giải bài toán tìm tất cả các khoá; Giải bài toán tìm tất cả các phụ thuộc hàm chiếu là bƣớc đi đầu tiên để xác định chuẩn 2 hoặc 3 của một phân rã; Kiểm tra dạng chuẩn BC của một phân rã không cần phải tìm các tập chiếu của tập phụ thuộc hàm gốc; Tính ép thỏa cho phép chỉ kiểm tra tính nhất quán cục bộ; Tính đặc trƣng đầy đủ rất có ý nghĩa trong thực hành; Không phải luôn luôn phân rã đƣợc một lƣợc đồ cơ sở dữ liệu đạt chuẩn BC và ép thoả tập phụ thuộc hàm; Bằng cách bổ sung các ràng buộc tồn tại có thể đạt đƣợc một phân rã đạt chuẩn BC và đặc trƣng đầy đủ phụ thuộc hàm. 57 tuy nhiên, luôn tìm đƣợc một lƣợc đồ cơ sở dữ liệu đạt dạng chuẩn 3 và đặc trƣng đầy đủ F. Riêng cơ sở dữ liệu đạt dạng chuẩn BC và đặc trƣng đầy đủ F phải cần một chút điều chỉnh, bằng cách bổ sung một ràng buộc tồn tại chẳng hạn (xem ví dụ 21).
  39. 158 Giáo trình cơ sở dữ liệu BÀI TẬP 1. Tìm tập các khoá của lƣợc đồ quan hệ sau: a. R = XYZW; F = { Y W, W Y, XY Z }; b. R = ABCDEF; F = { A B, C DF, AC E, D F }; 2. Xác định dạng chuẩn của các lƣợc đồ quan hệ sau: a. b. 3. Xác định dạng chuẩn của các lƣợc đồ cơ sở dữ liệu D sau a. D = {AC, AB} với F = {A C, B C} b. D = {(AB), (ACDE)} với F = {A B, B A, AC DE, BC DE} c. D = {(AB), (ACD), (BCE)} với F = {A B, B A, AC DE, BC DE} 4. Cho lƣợc đồ quan hệ = Xét tập thuộc tính R1 = GHCDA, R2 = AGB, R3 = CA và R4 = BHC. a. Tìm các tập phụ thuộc hàm chiếu Fi = Ri(F); b. Kiểm tra tính ép thoả F của lƣợc đồ cơ sở dữ liệu { , , , }; c. Kiểm tra tính đặc trƣng đầy đủ F của lƣợc đồ cơ sở dữ liệu { , , , } 5. Xác định dạng chuẩn cho mỗi lƣợc đồ sau: a. R = ABCD, F = {AB C, A D, BD C} b. R = ABCD, F= {A C, D C, BD A}
  40. Chƣơng 5: Dạng chuẩn 159 c. R = (Store, Department, Item, Manager), F = {SI D, SD M} với S, D, I và M là viết tắt của Store, Department, Item và Manager tƣơng ứng. d. R = (Flight, frOm, To, Depart, Arrives, dUration, Plane type, first cLass, Coach, total Seats, #Meal), F={ P LCS, DU M, AU M, LC S, LS C, CS L} cùng tập các khoá chỉ định {F, OTD, OTA}. Trong đó F, O, T, D, A, U, P, L, C, S và M theo thứ tự là viết tắt của Flight, frOm, To, Depart, Arrives, dUration, Plane type, first cLass, Coach, total Seats và #Meal tƣơng ứng. 6. Cho quan hệ: Hợp đồng SốBHXH Số HĐ Giờ Tên NV MãKS TênKS 1135 C1024 16 Lê V K25 Rex 1057 C1024 24 Lý S K25 Rex 1068 C1025 28 Trần X K04 Royal 1135 C1025 15 Lê V K04 Royal a. Xác định tập phụ thuộc hàm; b. Xác định dạng chuẩn; c. Cho một phân rã hợp lý. Xác định dạng chuẩn và kiểm tra tính ép thoả tập phụ thuộc hàm của phân rã này. 7. Cho quan hệ: Lịch mổ MãNV Tên bác sĩ MãBN TênBN Ngày Giờ Phòng D1011 Nguyễn A B100 Lê V 12/5/08 10:00 P15 D1011 Nguyễn A B105 Lý S 12/5/08 12:00 P15 D1024 Phạm B B108 Trần X 12/5/08 10:00 P10 D1024 Phạm B B108 Trần X 14/5/08 14:00 P10 D1032 Trần C B105 Lý S 14/5/08 16:30 P15 D1032 Trần C B110 Lê X 15/5/08 18:00 P13
  41. 160 Giáo trình cơ sở dữ liệu a. Xác định tập phụ thuộc hàm; b. Xác định dạng chuẩn; c. Cho một phân rã hợp lý. Xác định dạng chuẩn và kiểm tra tính đặc trƣng đầy đủ tập phụ thuộc hàm của phân rã này. 8. Chứng minh khẳng định “Nếu có một vi phạm vi phạm dạng chuẩn, thì vi phạm dạng này có thể tìm thấy trong F”
  42. Chƣơng 6 CHUẨN HOÁ LƢỢC ĐỒ QUAN HỆ Mục tiêu của chƣơng. Trong chƣơng này chúng ta sẽ học về: Bài toán chuẩn hoá lƣợc đồ quan hệ với ràng buộc phụ thuộc hàm; Các mục tiêu của chuẩn hoá: dạng chuẩn cao, bảo toàn thông tin, bảo toàn phụ thuộc, đặc trưng đầy đủ, tối thiểu số lược đồ con; Kiểm tra tính bảo toàn thông tin trực tiếp trên lƣợc đồ; Kiểm tra tính bảo toàn phụ thuộc mà không cần phải chiếu tập phụ thuộc hàm lên các lƣợc đồ con; Tiếp cận bảo toàn thông tin và tính bảo toàn phụ thuộc; Thuật toán phân rã; Tiếp cận bảo toàn phụ thuộc và tính bảo toàn thông tin; Sát nhập các lƣợc đồ quan hệ và bài toán khử thuộc tính bắc cầu; Thuật toán tổng hợp và lƣợc đồ đầy đủ; Phụ thuộc đa trị và dạng chuẩn 4. Khi gặp một lƣợc đồ quan hệ hoặc một lƣợc đồ cơ sở dữ liệu có dạng chuẩn thấp, chúng ta phải tìm một lƣợc đồ mới có dạng chuẩn cao hơn. Có thể lƣợc đồ mới không tƣơng đƣơng với lƣợc đồ cũ, nhƣng với dạng chuẩn cần đạt là dạng chuẩn 3, chúng ta hy vọng có đƣợc sự tƣơng đƣơng. Trong chƣơng này, chúng ta sẽ làm việc với lƣợc đồ quan hệ có dạng chuẩn thấp. Để đạt chuẩn cao hơn chúng ta sẽ phải phân rã nó thành các lƣợc đồ con. Các tiêu chuẩn của phân rã bao gồm: 1. Tối thiểu đạt chuẩn 3; 2. Bảo toàn thông tin; 3. Bảo toàn phụ thuộc (tính ép thỏa) hoặc đặc trƣng đầy đủ F.
  43. 162 Giáo trình cơ sở dữ liệu Trong đó 2 tiêu chuẩn đầu là quan trọng nhất. Tiêu chuẩn 3 có thể không đạt đƣợc nếu đòi hỏi phân rã phải đạt chuẩn BC. Ngoài ra số lƣợng các lƣợc đồ con cũng là một tiêu chuẩn đáng quan tâm, càng ít càng tốt. Chúng ta có hai vấn đề cần giải quyết. Thứ nhất, kiểm tra một phân rã có đạt các tiêu chuẩn đã nêu không. Thứ hai, đƣa ra một phân rã thỏa mãn các tiêu chuẩn đã nêu. 1. Kiểm tra các tiêu chuẩn Cho lƣợc đồ quan hệ và một phân rã = {Ri}i=1 m. Ở đây các tập phụ thuộc hàm chiếu chƣa đƣợc xác định. Bài toán xác định dạng chuẩn đã đƣợc giải quyết hoàn toàn trong chƣơng 5. Trong chƣơng 5, chúng ta cũng có một cách kiểm tra tính bảo toàn phụ thuộc, bằng cách tìm các tập phụ thuộc hàm chiếu. Chúng ta cũng đã kiểm tra tính bảo toàn thông tin bằng những tính toán trực tiếp trên một quan hệ cụ thể trong chƣơng 2. Mục này sẽ giải các bài toán kiểm tra tính bảo toàn thông tin trên lƣợc đồ thay vì trên các quan hệ cụ thể; bài toán kiểm tra tính bảo toàn phụ thuộc mà không cần chiếu. 1.1. Kiểm tra tính bảo toàn thông tin Cho quan hệ r(R). Xét R1, R2  R sao cho R = R1R2. Chiếu r xuống R1, R2 đƣợc 2 quan hệ r1 = r[R1] và r2 = r[R2]. Kết tự nhiên r1 và r2 lại, đƣợc r‟= r1 ⋈ r2. Ta luôn có r  r‟. Câu hỏi đặt ra là khi nào chiều ngƣợc lại cũng đúng, r‟  r, nghĩa là r = r‟. Câu hỏi tƣơng tự cũng đƣợc đặt ra với phân rã . Cho r(R), đặt ri = r[Ri], với điều kiện gì thì r‟ = r1 ⋈ r2 ⋈ ⋈ rm = r. Định nghĩa 6.1 Phân rã là bảo toàn thông tin (Lossless Join decomposition) nếu mọi r SATR(F) ta luôn có r = r’. Bài toán 3 Xác định có là phân rã bảo toàn thông tin có hay không. Nếu phân rã là bảo toàn phụ thuộc, ta có định lý sau giúp giải bài toán 1 hiệu quả. Định lý 1 Một phân rã đã bảo toàn phụ thuộc sẽ bảo toàn thông tin nếu có một lược đồ con chứa khoá của lược đồ gốc.
  44. Chƣơng 6: Chuẩn hoá lƣợc đồ quan hệ 163 Ví dụ 6.1 Với F = {A D, B C}, kiểm tra tính bảo toàn thông tin của = {AB, BC, AD}. Giải: Kiểm tra trực tiếp thấy phân rã trên bảo toàn phụ thuộc. Vì AB là khoá của suy ra phân rã là bảo toàn thông tin. Một định lý khác cũng giúp chúng ta kiểm tra tính bảo toàn thông tin Định lý 2 + Cho và phân rã = {R1, R2}. Phân rã bảo toàn thông tin nếu F chứa ít một trong 2 phụ thuộc hàm (R1  R2) → R1 hoặc (R1  R2) → R2. Sử dụng tính kết hợp của phép kết tự nhiên ta có cách kiểm tra tính bảo toàn thông tin nhƣ đƣợc minh hoạ trong ví dụ sau. Ví dụ 6.2 Với F = {A D, B C}, kiểm tra tính bảo toàn thông tin của = {AB, BC, AD}. Giải: Phân rã theo phụ thuộc hàm A D, đƣợc phân rã58 {ABC, AD} bảo toàn thông tin. Ta có B C đƣợc bao trong lƣợc đồ con ABC. Phân rã lƣợc đồ con này theo B C, đƣợc phân rã {AB, BC} bảo toàn thông tin. Kết hợp lại ta đƣợc phân rã {AB, BC, AD} bảo toàn thông tin. Phân rã kết hợp này chính là . Vậy bảo toàn thông tin. Trƣờng hợp tổng quát chúng ta sử dụng kỹ thuật tableaux với T gồm m dòng mỗi dòng ứng với một lƣợc đồ con. Các biến loại a ứng với các thuộc tính trong lƣợc đồ con. Phân rã là bảo toàn thông tin nếu T * chứa một dòng toàn biến loại a Các bƣớc 1. T gồm m dòng, dòng thứ i với các biến a nằm trên các cột của Ri, các cột còn lại chứa các biến b 58 Chúng ta có hai ngữ nghĩa khi dùng cụm từ phân rã: phân rã trong phân rã một lược đồ quan hệ là động từ còn phân rã trong thu được phân rã {AB, BCD} là danh từ.
  45. 164 Giáo trình cơ sở dữ liệu 2. Tính T* 3. Kiểm tra xem có dòng nào toàn a không Ví dụ 6.3 Với F = {A D, B C}, kiểm tra tính bảo toàn thông tin của = {AB, BC, AD}. Giải: Lập bảng T T (A B C D) a1 a2 b1 b2 b3 a2 a3 b4 a1 b5 b6 a4 * Tính T : T* (A B C D) a1 a2 a3 a4 b3 a2 a3 b4 a1 b5 b6 a4 Quan sát thấy dòng 1 toàn các biến loại a. Vậy bảo toàn thông tin. 1.2. Bảo toàn phụ thuộc Phân rã là bảo toàn tập phụ thuộc hàm F nếu F bị ép thoả trong với tƣ cách lƣợc đồ cơ sở dữ liệu. Bài toán 4 Xác định xem phân rã có bảo toàn phụ thuộc hay không. Trong chƣơng 5, chúng ta đã giải bài toán này bằng cách chiếu tập phụ thuộc hàm xuống các lƣợc đồ con Ri, đƣợc Fi. Gọi F‟ là hợp của các tập phụ thuộc hàm này: ′ 퐹 =∪ 퐹푖 Theo cách làm ở chƣơng 5, chúng ta sẽ kiểm tra tính tƣơng đƣơng giữa F và F‟. Thật ra chỉ cần kiểm tra 퐹′ ⊨ 퐹 vì ta luôn có 퐹 ⊨ 퐹′. Để kiểm tra 퐹′ ⊨ 퐹 ta phải kiểm tra xem mỗi f thuộc F có là thành viên của F‟+ hay + không. Theo cách làm thông thƣờng chúng ta phải tính 퐹′ .
  46. Chƣơng 6: Chuẩn hoá lƣợc đồ quan hệ 165 Thƣờng thì ta phải tính F‟ (chƣơng 5). Mục này sẽ giới thiệu một cách làm khác. Thuật toán sau tính bao đóng của X dƣới F‟ mà không cần tính F‟. Thuật toán 4: EClosure(X, F, ) Vào : tập thuộc tính X, tập phụ thuộc hàm F, phân rã + Ra : X F‟ Các bước : 1. do Y = X foreach Ri do + X = X  (X  Ri) F  Ri while (Y != X) 2. return(X) Ví dụ 6.4 Cho F = {A B, B C, C D, D A} và ={(AB), (BC), (CD)}. Tính + D F‟. Giải: Ta có X = D. + Trong lần lặp thứ 1, với lƣợc đồ con CD: X F = DABC, suy ra X = CD + Trong lần lặp thứ 2, với lƣợc đồ con BC: X F = DABC, suy ra X = CDB + Trong lần lặp thứ 3, với lƣợc đồ con BC: X F = DABC, suy ra X = CDB + Vậy D F‟ = ABCD. Dùng bao đóng dƣới F‟ chúng ta có thể kiểm tra F có bị ép thỏa hay không. Ví dụ 6.5 Cho F = {A B, B C, C D, D A}. Kiểm tra tính bảo toàn phụ thuộc của phân rã = {(AB), (BC), (CD)}. Giải: Chỉ cần kiểm tra phụ thuộc hàm D A. + Ta có D F‟ = ABCD, suy ra F‟ ⊨ (D A), suy ra F‟ ⊨ F.
  47. 166 Giáo trình cơ sở dữ liệu Vậy F bị ép thoả trong , tức bảo toàn phụ thuộc hàm F. + Dùng kỹ thuật tableaux tính X F’. Xây dựng T , X(R) = T (R)  {t} với t.Aj là biến loại a nếu Aj X. * Tính T , X(R), nhưng không thay đổi các dòng của T (R) + Quan sát các cột toàn a, X F‟ = {Aj | t(Aj) = a} Ví dụ 6.6 Cho F = {AD C, CD A, B D} và phân rã ={(ABC), (CD)}. Tính + AB F‟. Giải: Lập bảng T ,[AB](R) ( A B C D ) a a a b1 b2 b3 a a a a b4 b5 Đƣờng đứt nét phân biệt các dòng của T với t. Tính: * T ,[AB](R) ( A B C D ) a a a b1 b2 b3 a a a a a b1 + Suy ra CB F‟ = ABC 2. Chuẩn hoá Quá trình chuẩn hoá một lƣợc đồ quan hệ là đƣa ra một phân rã (trong bối cảnh này có thể đƣợc hiểu là một lƣợc đồ cơ sở dữ liệu) thỏa một hoặc nhiều tiêu chuẩn sau: 1. Bảo toàn thông tin (nếu không phân rã sẽ trở nên vô nghĩa) 2. Dạng chuẩn cao (là mục tiêu) 3. Bảo toàn phụ thuộc (đặc trƣng đầy đủ F thì tốt hơn)
  48. Chƣơng 6: Chuẩn hoá lƣợc đồ quan hệ 167 2.1. Tiếp cận phân rã Trong tiếp cận này59, mỗi khi tìm thấy một vi phạm, chúng ta sẽ thực hiện thủ tục phân rã theo định lý 2. Nhƣ vậy, nếu dạng chuẩn đích là chuẩn 3, chúng ta cần phải xác định tập các khoá của lƣợc đồ quan hệ (trong ứng dụng, đôi khi tập khóa đƣợc cho sẵn đƣợc gọi là khóa chỉ định). Ví dụ 6.7 Cho lƣợc đồ quan hệ R = (FROPADTLCSM)60 với các khoá chỉ định {F, ROD, ROA} và tập phụ thuộc hàm F = {T LCS, PD M, AD M, LC S, LS C, CS L}. Tìm một phân rã đạt chuẩn 3 theo tiếp cận phân rã. Giải: Tập các khoá chỉ định cũng chính là tập tất cả các khoá. Với PD M, = {R1(PDM), R2(FROPADTLCS)}. Với T LCS trong R2, = {R1(PDM), R21(TLCS), R22(FROPADT)}. Với LC S trong R21, = {R1(PDM), R211(LCS), R212(TLC), R22(FROPADT)}. (FROPADTLCSM ) PD M (PDM) (FROPADTLCS) T LCS (FROPADT) (TLCS) LC S (LCS) (TLC) 59 Về ngữ nghĩa cần phân biệt: tiếp cận phân rã, phân rã một lược đồ và xét phân rã ρ 60 FROPADTLCSM là viết tắt của FLIGHT, FROM, TO, DEPARTS, ARRIVES, DURATION, PLANE-TYPE, FIRST-CLASS, COACH, TOTAL-SEATS, #MEALS
  49. 168 Giáo trình cơ sở dữ liệu Nhận xét 1. Sƣ phức tạp tăng khi tăng số thuộc tính của R và số phụ thuộc hàm của F, đặc biệt nếu phải tìm các khoá của lƣợc đồ con 2. Số lƣợc đồ quan hệ con không tối ƣu 3. Số các thuộc tính trên các lƣợc đồ quan hệ con không tối ƣu. 4. F có thể không bị ép thỏa 5. Ngầm che dấu một số phụ thuộc bắc cầu Nếu lƣợc đồ không quá phức tạp, bằng cách chọn phụ thuộc bắc cầu thích hợp chúng ta có thể đạt đƣợc tiêu chuẩn thứ 3 bảo toàn phụ thuộc hoặc đặc trƣng đầy đủ F. Ví dụ 6.8 Xét lƣợc đồ quan hệ bán hàng với tập thuộc tính R(HNKDMTSG)61 và tập phụ thuộc hàm F = {H NK, K D, M T, HM SG}. Tìm một phân rã thoả ba tiêu chuẩn: bảo toàn thông tin, chuẩn BC và đặc trƣng đầy đủ F. Giải: Chọn các phụ thuộc hàm bắc cầu thứ tự là K D, H NK và M T ta có R(HNKDMTSG) K D R1(KD) R2(HNKMTSG) H NK R21(HNK) R22(HMTSG) M T R221(MT) R222(HMSG) Đƣợc phân rã = {R1(KD), R21(HNK), R221(MT), R222(HMSG)} bảo toàn thông tin, đạt chuẩn BC và đặc trƣng đầy đủ F. 61 HNKDMTSG là viết tắt của Hoá đơn, Ngày lập, Khách hàng, Địa chỉ, Mã hàng, Tên hàng, Số lượng, đơn Giá.
  50. Chƣơng 6: Chuẩn hoá lƣợc đồ quan hệ 169 2.2. Tiếp cận tổng hợp Tiếp cận này lƣu các phụ thuộc hàm trong các bảng riêng. Cách làm nhƣ vậy sẽ bảo đảm thu đƣợc phân rã đạt dạng chuẩn cao và đặc trƣng đầy đủ F. Để tránh dƣ thừa các lƣợc đồ con chúng ta sẽ phải tìm phủ tối tiểu của F trƣớc. Tuy nhiên số lƣợc đồ có thể không tối ƣu, ngoài ra không bảo đảm phân rã là bảo toàn thông tin. Ví dụ 6.9 Cho lƣợc đồ quan hệ . Với phủ tối tiểu {A B, B A, AC DE} ta có phân rã = {(AB), (BA), (ACDE)}. Phân rã này có thể sát nhập hai lƣợc đồ con đầu thành = {(A B), (ACDE)}. Chúng ta dùng định lý 1 để bảo đảm tính bảo toàn thông tin. Ví dụ 6.10 Cho lƣợc đồ quan hệ . Kiểm tra trực tiếp thấy tập phụ thuộc hàm đã tối tiểu. Bằng tiếp cận tổng hợp chúng ta thu đƣợc phân rã = {(BCD), (CH), (DEH), (GC)}. Theo định lý 1, phân rã này không bảo toàn thông tin. Bây giờ tìm thấy khoá duy nhất BGE, bổ sung lƣợc đồ quan hệ (BGE) vào phân rã trên, ta thu đƣợc phân rã = {(BCD), (CH), (DEH), (GC), (BGE)} bảo toàn thông tin, chuẩn BC, đặc trƣng đầy đủ tập phụ thuộc hàm. Để tìm phân rã với ít lƣợc đồ con, chúng ta phải sát nhập một số lƣợc đồ con lại. Gọi khoá của các lƣợc đồ con là khoá thiết kế, rõ ràng sát nhập những lƣợc con có các khoá thiết kế tƣơng đƣơng nhau (cùng bao đóng) sẽ vẫn bảo đảm tính đặc trƣng đầy đủ. Tuy nhiên còn đó bài toán dạng chuẩn. Bằng cách loại bỏ các thuộc tính bắc cầu trên các lƣợc đồ sát nhập, chúng ta đƣợc dạng chuẩn 3. Ví dụ 6.11 Xem lại ví dụ 9 để ý tình huống sát nhập. Ví dụ 6.12 Cho lƣợc đồ quan hệ , với R = (GHCDAB) và F = {GH AD, AG B, CD GH, C A, BH C} tối tiểu. Tìm một phân rã có ít lƣợc đồ con nhất thoả: bảo toàn thông tin, dạng chuẩn ít nhất bằng 3, đặc trƣng đầy đủ F.
  51. 170 Giáo trình cơ sở dữ liệu Giải: Bằng tiếp cận tổng hợp = {(GHAD), (AGB), (CDGH), (CA), (BHC)} thoả chuẩn BC, đặc trƣng đầy đủ F; Quan sát thấy lƣợc đồ con (GHAD) chứa khoá, bảo toàn thông tin; Sát nhập = {(GH CDA), (AGB), (CA), (BHC)} không đạt chuẩn 3, loại thuộc tính bắc cầu A khỏi lƣợc đồ đầu tiên, = {(GH CD), (AGB), (CA), (BHC)} đạt chuẩn BC. Vậy = {(GH CD), (AGB), (CA), (BHC)} là phân rã có ít lƣợc đồ con nhất thoả: bảo toàn thông tin, dạng chuẩn BC, đặc trƣng đầy đủ F. Nhƣ vậy, chúng ta có một thuật toán tìm một phân rã thỏa 4 tính chất: 1. F đƣợc đặc trƣng đầy đủ; 2. Đạt tối thiểu chuẩn 3; 3. Không tồn tại lƣợc đồ khác với ít lƣợc đồ con hơn mà vẫn thỏa 1 và 2; 4. Bảo toàn thông tin. Chúng ta gọi lƣợc đồ cơ sở dữ liệu thỏa 3 tính chất đầu là lược đồ cơ sở dữ liệu đầy đủ. Với lƣợc đồ đầy đủ, nếu chƣa bảo toàn thông tin ta sẽ bổ sung một lƣợc đồ con gồm các thuộc tính của một khoá nào đó của R. Thuật toán 5 Vào : Lƣợc đồ quan hệ R, tập phụ thuộc hàm F. Ra : Lƣợc đồ cơ sở dữ liệu D đầy đủ và bảo toàn thông tin. Các bước : 1. Tìm một phủ tối tiểu 2. Xây dựng các lược đồ con với mỗi phụ thuộc hàm đều được in trong một lược đồ con nào đó, ta được một phân rã đặc trưng đầy đủ F; 3. Nhóm các lược đồ con có khoá thiết kế tương đương nhau, rồi khử các thuộc tính bắt cầu, nếu có, ta được một phân rã đầy đủ; 4. Bổ sung, nếu cần, một lược đồ với các thuộc tính là các thuộc tính của một khoá bất kỳ của R, ta được một phân rã D đầy đủ và bảo toàn thông tin; 5. Return D.
  52. Chƣơng 6: Chuẩn hoá lƣợc đồ quan hệ 171 Ví dụ 6.13 Cho các thuộc tính với các ký tự tắt kèm theo Subject : S, Teacher : T, Class : C. Xét lƣợc đồ quan hệ . Áp dụng thuật toán: Bƣớc 1: F đã tối tiểu Bƣớc 2: Phát sinh D = {(TS), (CST) Bƣớc 3: Không nhóm Bƣớc 4: Không bổ sung Ví dụ 6.14 Cho lƣợc đồ . Áp dụng thuật toán: Bƣớc 1: F đã tối tiểu Bƣớc 2: Phát sinh D = {(GHAD), (AGB), (CDGH), (CA), (BHC)} Bƣớc 3: Nhóm 2 lƣợc đồ con thứ 1 và 3 lại, khử thuộc tính bắc cầu A trong lƣợc đồ kết quả, D = {(GH CD), (AGB), (CA), (BHC)} Bƣớc 4: Không bổ sung Ví dụ 6.15 Cho lƣợc đồ . Bƣớc 1: Tập phụ thuộc hàm đã tối tiểu Bƣớc 2: Phát sinh D = {(AB), (BA), (ACD), (BCE)} Bƣớc 3: Nhóm lƣợc đồ con 1 và 2, 3 và 4 lại, khử thuộc tính bắc cầu B khỏi lƣợc đồ kết quả thứ 2, D = {(A B), (ACDE)} Bƣớc 4: Không bổ sung 3. Dạng chuẩn 4 Trong thực tế, xuất hiện nhiều ràng buộc toàn vẹn không thuộc dạng phụ thuộc hàm nhƣ ví dụ sau đây. Ví dụ 6.16 Với các trƣờng đại học tổ chức đào tạo theo niên chế, sinh viên đƣợc xếp vào một lớp nhất định. Vào đầu học kỳ, phòng đào tạo xếp lịch học theo lớp và sinh viên cùng lớp phải học các môn giống nhau. Ký hiệu S, L và M là viết tắt của Sinh viên, Lớp và Môn tƣơng ứng. Lƣợc đồ quan hệ (SLM)
  53. 172 Giáo trình cơ sở dữ liệu không phải thỏa bất kỳ phụ thuộc hàm nào, nhƣng quan hệ sau là vi phạm quy tắc quản lý trên r ( S M L) 1 a x 2 b x 1 a x Thật vậy, trong quan hệ này hai sinh viên 1 và 2 học cùng lớp nhƣng lại học các môn không giống nhau. Dạng ràng buộc nhƣ ví dụ trên đƣợc gọi là ràng buộc phụ thuộc đa trị. Theo đó, với lớp học cho trƣớc, quan hệ giữa sinh viên và môn học ở trên có dạng tích Descartes. Lúc này ta nói S (cũng vậy, M) phụ thuộc đa trị vào L, ký hiệu L ↠ S (L ↠ M) trong lƣợc đồ SML (cách nói này là bắt buộc đối với phụ thuộc đa trị) Định nghĩa 6.2 Ta nói quan hệ r(XYZ) thỏa phụ thuộc đa trị X ↠ Y nếu mỗi khi tìm thấy trên r có hai bộ (x, y1, z1) và (x, y2, z2) thì sẽ tìm thấy hai bộ (x, y1, z2) và (x, y2, z1) Lƣu ý một phụ thuộc hàm cũng là một phụ thuộc đa trị. Với các lƣợc đồ tập F các ràng buộc gồm phụ thuộc hàm và phụ thuộc đa trị ta có một dạng chuẩn mới. Định nghĩa 6.3 Ta nói đạt dạng chuẩn 4 nếu mỗi phụ thuộc đa trị X ↠ Y được suy từ F, X phải chứa một khoá của . Trong phạm vi tài liệu, chúng tôi không đi vào chi tiết của các bài toán giống nhƣ trƣờng hợp F chỉ gồm các phụ thuộc hàm. Để hỗ trợ khi giải quyết các bài toán thực tế, kết quả sau giúp nhiều cho bài toán thiết kế cơ sở dữ liệu.
  54. Chƣơng 6: Chuẩn hoá lƣợc đồ quan hệ 173 Quan hệ r(XYZ) thỏa phụ thuộc đa trị X ↠ Y nếu và chỉ nếu phân rã {(XY), (XZ)} bảo toàn thông tin. Với kết quả này, tiếp cận phân rã cho phép chúng ta đƣa ra lƣợc đồ đạt chuẩn 4. Nhƣ đã biết tiếp cận phân rã bảo đảm dạng chuẩn mong muốn trong khi vẫn bảo toàn thông tin62. Ví dụ 6.17 Trở lại ví dụ 16, lƣợc đồ không đạt chuẩn 4. Phân rã thành lƣợc đồ mới {(LS) , (LM)} đạt chuẩn 4. Ví dụ 6.18 Lƣợc đồ quan hệ không đạt chuẩn 4. Phân rã theo phụ thuộc đa trị đƣợc {(CDE), (ABC)} đạt chuẩn 4. 62 Riêng mục tiêu bảo toàn phụ thuộc là một chủ đề riêng nằm ngoài phạm vi của tài liệu này.
  55. 174 Giáo trình cơ sở dữ liệu TÓM TẮT Chuẩn hoá là quá trình phân rã một lƣợc đồ quan hệ; Kết quả chuẩn hoá là một phân rã, đƣợc xét nhƣ là một lƣợc đồ cơ sở dữ liệu, sao cho các lƣợc đồ con có dạng chuẩn cao hơn lƣợc đồ gốc; Khoá của các lƣợc đồ con gọi là các khoá thiết kế; Kết quả chuẩn hoá phải bảo đảm bảo toàn thông tin; Có nhiều cách kiểm tra tính bảo toàn thông tin dựa trên lƣợc đồ mà không phải thao tác trên các quan hệ cụ thể; Kết quả chuẩn hoá nếu bảo toàn phụ thuộc sẽ rất có ý nghĩa trong thực hành; Có một cách kiểm tra tính bảo toàn phụ thuộc mà không cần chiếu tập phụ thuộc hàm lên các lƣợc đồ con; Tiếp cận phân rã cho phép đạt dạng chuẩn cao nhƣ mong muốn trong lúc vẫn bảo đảm tính bảo toàn thông tin, nhƣng không chắc bảo toàn phụ thuộc; Việc lựa chọn thích hợp phụ thuộc hàm trong từng bƣớc của quá trình phân rã cho phép bảo toàn phụ thuộc nhƣng dạng chuẩn đạt đƣợc có thể chỉ đến chuẩn 3; Tiếp cận tổng hợp cho phép đặc trƣng đầy đủ F và đạt chuẩn BC, nhƣng không chắc bảo toàn thông tin và có thể có nhiều lƣợc đồ con; Có thể gộp các lƣợc đồ con có khoá thiết kế tƣơng đƣơng nhau lại thành một lƣợc đồ chung, nhƣng dạng chuẩn có thể bị giảm; Khử các thuộc tính bắc cầu trong lƣợc đồ sát nhập cho ta một lƣợc đồ với tối thiểu số lƣợc đồ con và đƣợc gọi là lƣợc đồ đầy đủ; Lƣợc đồ đầy đủ nếu chƣa bảo toàn thông tin, chỉ cần thêm vào một lƣợc đồ con gồm các thuộc tính của một khoá nào đó, sẽ bảo toàn thông tin; Với việc xuất hiện thêm các loại ràng buộc tổng quát hơn phụ thuộc hàm, nhƣ phụ thuộc đa trị chẳng hạn, chúng ta có các dạng chuẩn cao hơn.
  56. Chƣơng 6: Chuẩn hoá lƣợc đồ quan hệ 175 BÀI TẬP 1. Chuẩn hoá các lƣợc đồ quan hệ sau, dùng thuật toán phân rã: a. R =(ABCDE, {DA, DBC, DBE}); F = { A BC, BC A, BCD E, E C } b. R = (ABCDE, {AB, AC}); F = { AB CDE, AC BDE, B CE, C BD } c. R = (ABCDE,{A}); F = { A BCDE, CD E, EC B } 2. Chuẩn hoá các lƣợc đồ quan hệ sau, dùng thuật toán tổng hợp: a. R = ABCDE; F = { A BC, BC A, BCD E, E C } b. R = ABCDE; F = { A B, B AE, AC D } c. R = AB1B2C1C2DEI1I2I3J; F = { A B1B2C1C2DEI1I2I3J, B1B2C1 AC2DEI1I2I3J, B1B2C2 AC1DEI1I2I3J, E I1I2I3, C1D J, C2D J, I1I2 I3, I2I3 I1, I1I3 I2 } 3. Chuẩn hoá các lƣợc đồ sau, thỏa bảo toàn thông tin và đạt chuẩn BC: a. R = ABCD; F = { AB C, A D, BD C } b. R = (Store, Department, Item, Manager); F = { SI D, SD M } 4. Chuẩn hoá các lƣợc đồ sau, thỏa bảo toàn thông tin và đạt chuẩn BC và đặc trƣng đầy đủ F, nếu đƣợc: a. R = ABCD; F = { A C, D C, BD A } b. R = ({Flight, frOm, To, Depart, Arrives, dUration, Plane type, first cLass, Coach, total Seats, #Meal}, {F, OTD,
  57. 176 Giáo trình cơ sở dữ liệu OTA}); F = { P LCS, DU M, AU M, LC S, LS C, CS L } 5. Cho tập thuộc tính {STUDENT#, NAME, BIRTHDAY, AGE, ADVISOR, DEPARTMENT, SEMETER, COURSE, GRADE}. Dùng các ký tự in đậm thay thế cho tên đầy đủ, xét lƣợc đồ thoả tập phụ thuộc hàm F = { S NBAVD, B A, V D }. a. Bằng trực giác chỉ ra một phân rã rồi xác định dạng chuẩn của nó; b. Có hay không một phân rã đạt chuẩn BC, bảo toàn thông tin và bảo toàn phụ thuộc. 6. Cho lƣợc đồ , R = ABCDE và F = { AB C, C E, E C, C D, AB E } a. Xác định dạng chuẩn của ; b. Xác định dạng chuẩn và kiểm tra tính bảo toàn thông tin, bảo toàn phụ thuộc của phân rã = { ABC, ADE, CE }. 7. Cho lƣợc đồ R = {Broker, Office, Investor, Stock, Quantity, Dividend} = BOISQD và tập phụ thuộc hàm F = {S D, I B, IS Q, B O }. Hãy: a. Tìm tập các khoá; b. Bằng trực giác chỉ ra một phân rã rồi xác định dạng chuẩn của nó và kiểm tra tính bảo toàn thông tin, bảo toàn phụ thuộc; c. Xác định dạng chuẩn và kiểm tra tính bảo toàn thông tin, bảo toàn phụ thuộc của phân rã = {ISQS, IBO} 8. Cho R = {Ship name, Voyage indentifier, Type of ship, Cargo carried by one ship on one voyage, Port, Day} = SVTCPD và F = { S T, V SC, SD PV }. Hãy tìm một phân rã đạt chuẩn BC, bảo toàn thông tin và đặc trƣng đầy đủ F. 9. Cho lƣợc đồ quan hệ R = {Nhân viên, Chức danh, Bậc lương, Hệ số lương, hệ Số chức danh} = NCBHS. Giả sử R thoả BC H, ngoài ra tại một thời điểm bất kỳ R còn thoả N BC và C S. Với mỗi câu hỏi sau, xác định tập phụ thuộc hàm F và đƣa ra một lược đồ đầy đủ.
  58. Chƣơng 6: Chuẩn hoá lƣợc đồ quan hệ 177 a. Trong bối cảnh thời điểm đƣợc xác định trƣớc (chẳng hạn cơ sở dữ liệu chỉ lƣu thông tin cho thời điểm hiện tại mà thôi). b. Trong bối cảnh thời điểm là tùy ý, bằng cách dùng thuộc tính Mốc thời gian (viết tắt là M) để lƣu thời điểm khi tiếp nhận nhân viên, trong những lần đƣợc nâng bậc lương hoặc đổi chức danh, và những lần điều chỉnh hệ số chức danh. 10. Cho tập thuộc tính R = {Hàng hoá, Đơn vị tính, Phiếu xuất, lượng Toàn, trị gIá tồn, Lượng xuất, Giá xuất}. Dùng các ký tự đƣợc in đậm làm chữ viết tắt, xét lƣợc đồ R = HĐPTILG. Giả sử R thoả H Đ và PH LG, ngoài ra tại một thời điểm bất kỳ trƣớc khi lập phiếu, R còn phải thỏa H TI. Với mỗi câu hỏi sau, hãy xác định tập phụ thuộc hàm F và đƣa ra một lược đồ đầy đủ a. Trong bối cảnh thời điểm đƣợc xác định trƣớc (chẳng hạn cơ sở dữ liệu chỉ lƣu thông tin cho thời điểm hiện tại mà thôi) b. Trong bối cảnh thời điểm là tùy ý. Bằng cách dùng thuộc tính Ngày lập (viết tắt là N) để lƣu thời điểm lập phiếu, giả sử khi ấy ta quan sát thấy R còn phải thỏa thêm các phụ thuộc hàm P N và N P. 11. Cho lƣợc đồ R = {Nhân viên, Phòng, chức Vụ, nGạch} = NPVG. Giả sử R thoả phụ thuộc N GP. Tại thời điểm xác định, R còn thoả N V. Ngoài ra với thể hiện chỉ có các trƣởng phòng, R còn thoả thêm P N (khi ấy trƣởng phòng đóng hai vai trò: vừa quản lý vừa là thành viên của phòng). Với mỗi câu hỏi sau, hãy xác định tập phụ thuộc hàm F và đƣa ra một lược đồ đầy đủ a. Trƣờng hợp cơ sở dữ liệu chỉ lƣu thông tin hiện tại b. Trƣờng hợp tổng quát, dùng hai thuộc tính Q (Quyết định) và K (ngày Ký) để lƣu quyết định và ngày ký quyết định chức vụ cho nhân viên, khi ấy ta quan sát thấy R thoả thêm các phụ thuộc hàm Q NKV và KN Q. 12. Tìm một lƣợc đồ quan hệ có ràng buộc đa trị. Chuẩn hoá nó đến dạng chuẩn 4. 13. Thử bàn về tiếp cận tổng hợp khi tập phụ thuộc có các phụ thuộc đa trị.
  59. 178 Giáo trình cơ sở dữ liệu
  60. Chƣơng 7 MÔ HÌNH THỰC THỂ KẾT HỢP Mục tiêu của chƣơng. Trong chƣơng này chúng ta sẽ học về: Phƣơng pháp luận thiết kế cơ sở dữ liệu mức quan niệm; Mô hình thực thể kết hợp (ER); Cách sử dụng mô hình ER thiết kế cơ sở dữ liệu mức quan niệm; Các ký hiệu mô hình của Power Designer (PD); Chuyển mô hình mức quan niệm về mô hình mức logic; Vấn đề của việc xuất hiện chu trình trong mô hình; Tính xác định của phụ thuộc hàm và ngữ cảnh; Vai trò của ngƣời dùng cuối trong quá trình thiết kế; Vai trò của mô hình ngoài trong quá trình thiết kế. Chúng ta đã biết mô hình dữ liệu mức quan niệm tập trung vào tính logic của biểu diễn dữ liệu. Trong chƣơng này chúng tôi giới thiệu một mô hình rất phù hợp để lập mô hình dữ liệu mức quan niệm, mô hình thực thể kết hợp (Entity Relationship63, viết tắt là ER). 1. Khái niệm Mô hình thực thể kết hợp là một tiếp cận mô hình hoá dữ liệu dựa trên các khái niệm thực thể (entity), thuộc tính (attribute) và mối kết hợp (relationship). Nó đƣa ra các lƣợc đồ quan niệm trực quan và dễ hiểu. 63 Thuật ngữ mối kết hợp (relationship) đã quen đƣợc xử dụng
  61. 180 Giáo trình cơ sở dữ liệu 1.1. Thực thể Trong hệ thống có các đối tƣợng, các sự vật, các khái niệm mà sự tồn tại của chúng đóng vai trò quan trọng trong việc lập mô hình. Chúng tạo thành những nhóm và đƣợc mô tả trong mô hình thực thể kết hợp dƣới thuật ngữ thực thể64. Ví dụ 7.1 Với công ty điện lực, các thực thể có thể là Khách hàng, Mức tiêu thụ, Với một trƣờng đại học, các thực thể có thể là Sinh viên, Giảng viên, Môn học, Chương trình đào tạo Với một siêu thị, các thực thể có thể là Khách hàng thân thiết, Nhà cung cấp, Hàng hoá, Hoá đơn, Phiếu nhập, Biên bản kiểm kê, Với công ty Mỹ Gia, các thực thể có thể là Chi nhánh, Nhân viên, Người thân, Nhà cho thuê, Chủ nhà, Khách hàng, Hợp đồng Mô hình hoá có nhiều cấp độ trừu tƣơng từ tổng quát đến chi tiết. Ban đầu, ở mức trừu tƣợng cao, chỉ một số thực thể quan trọng đƣợc đƣa ra. Càng về sau, mô hình càng cụ thể, xuất hiện các thực thể mới nhằm mô tả các đối tƣợng, sự vật và khái niệm trong hệ thống đƣợc chi tiết hơn. Ví dụ 7.2 Với công ty điện lực, thực thể Khách hàng có thể chi tiết thành các thực thể nhƣ Hộ gia đình, Cơ sở kinh doanh, Với một trƣờng đại học, thực thể Môn học có thể chi tiết thành các thực thể nhƣ Môn tự chọn, Môn bắt buộc Với công ty Mỹ Gia, thực thể Nhân viên có thể chi tiết thành các thực thể nhƣ Quản lý, Thư ký, Giám sát, Chuyên viên Có những thực thể mà sự tồn tại của nó phụ thuộc vào sự tồn tại của một hoặc nhiều thực thể khác. Chúng đƣợc gọi là thực thể phụ thuộc hay thực thể yếu Ví dụ 7.3 Với công ty Mỹ Gia, thực thể Người thân không thể tồn tại nếu không có thực thể Nhân viên. Ta có, Người thân là thực thể yếu phụ thuộc vào Nhân viên 64 Lƣu ý: những ngƣời thiết kế khác nhau có thể đƣa ra các thực thể khác nhau
  62. Chƣơng 7: Mô hình thực thể kết hợp 181 Ta có: “Thực thể là là một phần tử mô hình trong mô hình thực thể kết hợp, dùng để mô tả các đối tượng, sự vật hoặc khái niệm cùng loại. Các đối tượng, sự vật hoặc khái niệm65 mà thông tin của nó có vai trò quan trọng trong việc việc xây dựng cơ sở dữ liệu cho một tổ chức, cần được mô tả trong các thực thể. Thông tin cụ thể về một đối tượng, hay trạng thái của chúng, được gọi là một thể hiện của chúng trong hệ thống đang xét”. Chúng ta dùng một hình chữ nhật để ký hiệu thực thể, hình chữ nhật có viền đôi để ký hiệu thực thể yếu. Bên trong hình chữ nhật có gắn nhãn là tên của thực thể. Ví dụ 7.4 Ký hiệu thực thể Nhân viên, Chi nhánh và thực thể yếu Người thân Nhân Viên Ngƣời thân Chi nhánh Các ký hiệu này cho biết trong hệ thống có một tập các nhân viên, tập các chi nhánh và tập các người thân của nhân viên mà thông tin về họ có vai trò nào đó trong cơ sở dữ liệu của công ty Mỹ Gia. Thông tin của một đối tƣợng nhân viên cụ thể có thể là mã nhân viên, chi nhánh làm việc, họ, tên, địa chỉ, số điện thoại, giới tính, ngày sinh, số của sổ bảo hiểm, chức vụ, lương, ngày vào làm và tốc độ đánh máy (xem chƣơng 1). Một số thông tin dùng để mô tả, số khác cho biết các liên kết với các đối tƣợng khác. 1.2. Thuộc tính Chúng ta dùng danh sách thuộc tính để mô tả các đối tượng. Các giá trị thuộc tính của các đối tƣợng cho ta một thể hiện của chúng trong hệ thống. Một thực thể có bao nhiêu thuộc tính phụ thuộc vào mục tiêu của cơ sở dữ liệu, thƣờng là đủ để chúng ta có thể làm việc. Ký hiệu thuộc tính trong mô hình là một hình oval có nhãn và đƣợc gắn với thực thể chủ nhân duy nhất của nó. 65 Kể từ đây chúng ta sẽ dùng thuật ngữ đối tƣợng thay cho các thuật ngữ đối tƣợng, sự vật hoặc khái niệm
  63. 182 Giáo trình cơ sở dữ liệu Ví dụ 7.5 Ngày Sinh Họ Tên Địa chỉ Sinh Viên Nhờ các giá trị thuộc tính chúng ta quan sát đƣợc đối tƣợng, nhận diện và làm việc với chúng. Tập giá trị của thuộc tính đƣợc gọi là miền giá trị của thuộc tính. Thuộc tính có các thuộc tính con đƣợc gọi là thuộc tính phức. Chúng ta có thể tách các thuộc tính phức để tạo thành một thực thể mới, nếu thấy cần thiết. Ví dụ 7.6 Với thuộc tính địa chỉ, giả sử chúng ta quan tâm đến các thông tin riêng nhƣ tỉnh thành phố, quận huyện và số nhà, ta có: Họ Tên Ngày Sinh Thành Phố Quận Địa chỉ Sinh Viên Số Nhà Trong thực tế, một đối tƣợng đƣợc hoàn toàn xác định qua một vài giá trị thuộc tính nào đó. Chẳng hạn, mã sinh viên xác định duy nhất một sinh viên trong trƣờng đại học. Một tập con tối tiểu các thuộc tính cho phép phân biệt các đối tƣợng với nhau đƣợc gọi là khoá. Một thực thể có thể có nhiều khoá (candidate key), chúng ta sẽ chọn một trong chúng làm khoá chính (primary key) và gạch chân chúng trong lƣợc đồ. Thật lý tƣởng nếu chọn đƣợc khoá chính chỉ gồm một thuộc tính66. 66 Trong thực tế, chúng ta thƣờng bổ sung cho thực thể một thuộc tính để làm khoá chính
  64. Chƣơng 7: Mô hình thực thể kết hợp 183 Ví dụ 7.7 Họ Tên Ngày Sinh Mã SV Sinh Viên Mô hình cho phép đặc tả các thuộc tính có nhiều trị, khi ấy nó đƣợc gọi là thuộc tính đa trị và đƣợc nối với thực thể bằng đƣờng kẻ đôi. Thuộc tính mà giá trị của nó hoàn toàn xác định qua giá trị của các thuộc tính khác đƣợc gọi là thuộc tính dẫn xuất đƣợc nối với thực thể bằng đƣờng đứt nét. Ví dụ 7.8 Họ Tên Ngày Sinh Mã SV Địa chỉ Sinh Viên Tuổi 1.3. Mối kết hợp Mối kết hợp trong mô hình ER biểu diễn một kết hợp giữa các thực thể, là tập các liên kết giữa các đối tƣợng của các thực thể thành phần, mỗi liên kết đƣợc gọi là một thể hiện kết hợp. Số thực thể tham gia vào mối kết hợp đƣợc gọi là bậc của mối kết hợp, mối kết hợp bậc một còn đƣợc gọi là kết hợp đệ quy. Chúng ta dùng một hình thoi có gắn nhãn để biểu diễn mối kết hợp. Vì các liên kết đƣợc hình thành trong quá trình hệ thống hoạt động nên nhãn của mối kết hợp thƣờng là tên của các hoạt động này67. 67 Tuy nhiên, dù dữ liệu đƣợc phát sinh từ các hoạt động của hệ thống, chúng vẫn là danh từ do vậy việc dùng các loại từ khác với danh từ để đặt tên cho mối kết hợp cũng chỉ nhằm mục đích nhấn mạnh đến bản chất của việc phát sinh ra chúng. Thực chất dữ liệu là danh từ và mối kết hợp giữa chúng, nếu có, vẫn nên thuần tuý ở tính logic và có thể dùng các loại từ biểu diễn mối quan hệ (xem thêm phần hƣớng dẫn mô hình hố), còn muốn biết các hoạt động làm phát sinh dữ liệu chúng ta cần đến các biểu đồ khác.
  65. 184 Giáo trình cơ sở dữ liệu Ví dụ 7.9 Giảng Viên Dạy Môn Thành Phố Kề với Nhân Viên Lập Khách Hàng Hóa Đơn Trong một mối kết hợp, một đối tƣợng có thể không có trong bất kỳ liên kết nào nhƣng cũng có thể tham gia trong nhiều liên kết với các đối tƣợng khác. Để đặc tả số lần một đối tƣợng có thể tham gia vào mối kết hợp chúng ta dùng hai số min và max cho biết số liên kết tối thiểu và tối đa mà một đối tƣợng của nó đƣợc phép thực hiện với các đối tƣợng của các thực thể còn lại. Cặp [min:max] đƣợc gọi là bản số của thực thể tham gia vào mối kết hợp. Ví dụ 7.10 [1:1] [4:30] Giảng Viên Thuộc Khoa [0:6] [1:2] Dạy Giảng Viên Môn [0:n] [1:n] Nhân Viên Lập Khách Hàng [1:1] Hóa Đơn
  66. Chƣơng 7: Mô hình thực thể kết hợp 185 Trong lƣợc đồ đầu, giảng viên thuộc về một khoa duy nhất còn khoa có ít nhất 4 giảng viên và nhiều nhất 30 giảng viên. Ở lƣợc đồ tiếp theo, giảng viên dạy tối đa 6 môn còn mỗi môn phải có giảng viên giảng nhƣng không quá hai. Lƣợc đồ cuối, nhân viên đƣợc phép lập nhiều hoá đơn; khách hàng phải nhận ít nhất một hoá đơn (phải mua hàng mới có dữ liệu trong cơ sở dữ liệu); hoá đơn chỉ đƣợc lập một lần duy nhất68. Bản số của mối kết hợp có thể dùng để biểu diễn các ràng buộc phụ thuộc hàm và ràng buộc khác rỗng. Theo đó, bản số max bằng 1 cho biết có ràng buộc phụ thuộc hàm, bản số min khác 0 cho biết có ràng buộc khác rỗng. Ví dụ 7.11 Giảng Viên Thuộc Khoa [1:1] [4:30] Trong mối kết hợp này, ta có một ràng buộc phụ thuộc hàm Giảng viên → Khoa và hai ràng buộc tồn tại: thông tin liên kết với khoa của giảng viên và thông tin liên kết với giảng viên của khoa phải đƣợc lƣu trong cơ sở dữ liệu ngay khi có đối tƣợng69. 1.4. Nhiều hơn về mối kết hợp Thực thể yếu (thực thể phụ thuộc) Một thực thể đƣợc gọi là thực thể yếu nếu Nó đóng vai trò phụ thuộc tồn tại trong một hoặc nhiều mối kết hợp Khoá chính của nó thực hiện đƣợc vai trò chỉ trong bối cảnh các thể hiện của các thực thể bị phụ thuộc là xác định. Nói cách khác, một mình nó là không đủ để phân biệt các đối tƣợng của chính nó mà phải có sự tham gia của các khoá chính của các thực thể bị phụ thuộc. Mô hình ER dùng một hình tròn nhỏ để biểu diễn vai trò phụ thuộc của thực thể yếu cần đến khoá chính của thực thể bị phụ thuộc để phân biệt các đối tƣợng của nó. 68 Bản số thể hiện một số quy tắc quản lý của hệ thống. Lƣu ý mô hình không biểu diễn đƣợc tất cả các quy tắc quàn lý. Tuỳ vào mức trừu tƣợng mà một số quy tắc đƣợc đặc tả trong mô hình cụ thể. 69 Đây thực là một nghịch lý logic. Tuy nhiên, các lập trình viên có kinh nghiệm đề có thể cài đặt các ràng buộc loại này.
  67. 186 Giáo trình cơ sở dữ liệu Ví dụ 7.12 Câu Lạc Bộ Lập Đội Lƣợc đồ này ngụ ý khoá chính của đội chỉ dùng để phân biệt giữa các đội trong cùng một câu lạc bộ, hơn nữa đội là phụ thuộc tồn tại vào câu lạc bộ. Thực thể kết hợp Trong mô hình ban đầu của Chen, mối kết hợp không có thuộc tính. Để đặc tả các mối kết hợp có thuộc tính, chúng ta sẽ chuyển mối kết hợp thành thực thể và gọi là thực thể kết hợp. Thực thể kết hợp là một thực thể yếu phụ thuộc vào các thực thể thành phần của mối kết hợp (bình thƣờng nó phụ thuộc vào tất cả các thực thể thành phần, nhƣng trong một số trƣờng hợp thì không phải lúc nào cũng vậy, khi ấy ta phải đặc tả cho rõ ràng). Thực thể kết hợp đƣợc ký hiệu bởi một hình chữ nhật bao một hình thoi. Ví dụ 7.13 Giảng Viên Dạy Môn Lớp Lƣợc đồ ngụ ý mối kết hợp dạy (tên đầy đủ của nó nên là được phân công dạy) đƣợc chuyển thành thực thể kết hợp để nó có thuộc tính riêng cũng nhƣ cho phép nó tham gia vào các kết hợp khác, hơn nữa chỉ có khoá chính của môn và lớp tham gia phân biệt các sự kiện phân công giảng dạy này70 Thực thể cha, thực thể con Chúng ta có thể phân hoạch tập các đối tƣợng của thực thể để đƣợc các tập con. Nhƣ vậy ta đã tạo ra các thực thể mới. Thực thể ban đầu đóng vai trò thực thể cha, còn các thực thể đƣợc sinh ra đóng vai trò thực thể con. Quá trình nhƣ vậy có thể đƣợc tiếp tục, khi ấy chúng ta có những thực thể đóng cả hai vai trò. 70 trong trƣờng hợp bỏ qua đặc tả chi tiết này, chúng ta xem thực thể kết hợp phụ thuộc vào tất cả các thực thể thành phần.
  68. Chƣơng 7: Mô hình thực thể kết hợp 187 Cách làm này cho phép ta mô tả một số đối tƣợng đƣợc chi tiết hơn về các thuộc tính riêng cũng nhƣ các mối quan hệ riêng khác mà các đối tƣợng khác không có. Quan hệ cha con giữa thực thể cha và thực thể con là một mối kết hợp đặc biệt và có bản số 1:1. Trong trƣờng hợp tổng quát, họ các thực thể con không nhất thiết là một phân hoạch của thực thể cha. Mô hình ER dùng ký hiệu G để biểu diễn sự không giao nhau của các thực thể con (nếu đầy đủ nó sẽ là một phân hoạch), và dùng ký hiệu Gs để biểu diễn có những thực thể con có phần giao khác rỗng. Ví dụ 7.14 Một phân hoạch thực thể sinh viên Sinh Viên G G Chính Quy Tại Chức Bằng 2 Ví dụ 7.15 Một mô tả chi tiết nhân viên, có những nhân viên vừa là giảng viên vừa là quản lý. Nhân Viên Gs Giảng Viên Quản Lý
  69. 188 Giáo trình cơ sở dữ liệu 1.5. Tìm phụ thuộc hàm từ mô hình E-R Phụ thuộc hàm là các ràng buộc, chúng có thể đúng trong ngữ cảnh này nhƣng không đúng trong ngữ cảnh khác. Phụ thuộc hàm xác định một quan hệ hàm, nếu ngữ cảnh làm quan hệ hàm không xác định thì ràng buộc phụ thuộc hàm không còn tác dụng. Trên từng thực thể hoặc từng mối kết hợp Phụ thuộc hàm cảm sinh từ khoá chính Ví dụ 7.16 Thực thể Sinh viên với khoá chính Mã SV Sinh viên Mã SV Họ tên Ngày sinh Giới tính Xác định phụ thuộc hàm S HNG Phụ thuộc hàm cảm sinh từ mối kết hợp 1-n Ví dụ 7.17 Mối kết hợp 1-n giữa hai thực thể Sinh viên và Lớp Sinh viên 1:1 0:n Lớp Mã SV Mã Lớp Xác định phụ thuộc hàm S L Phụ thuộc hàm cảm sinh từ mối kết hợp n-n Ví dụ 7.18 Mối kết hợp n-n giữa hai thực thể Hoá đơn và Hàng hoá Hoá đơn 1:n 0:n Hàng hoá Số lƣợNg Mã SV Mã Lớp Xác định phụ thuộc hàm SL N
  70. Chƣơng 7: Mô hình thực thể kết hợp 189 Thật ra phụ thuộc hàm này đƣợc phát sinh từ khoá khi chuyển về mô hình quan hệ. Tuy nhiên không phải tất cả các phụ thuộc hàm đều có thể nhận đƣợc từ mô hình ER. Ví dụ 7.19 Trong mối kết hợp phân công giảng là mối kết hợp 3 ngôi giữa các thực thể Lớp, Giảng viên và Môn ta không thể nhận ra phụ thuộc hàm LM G. Bằng cách biến đổi mô hình ER đƣa các quan hệ phức tạp về các mối kết hợp hai ngôi đơn giản ta có thể phát hiện nhiều phụ thuộc hàm. Ví dụ 7.20 Trong mối kết hợp phân công giảng giữa Lớp, Giảng viên và Môn ta phân tích bộ 3 (g,m,l) thành (g,(m,l)) trong đó kết hợp kế hoạch học giữa Lớp và Môn là n-n; chuyển kết hợp này thành thực thể và nhận ra phân công giảng là kết hợp giữa Giảng viên và kế hoạch học có bản số 1-n suy ra có phụ thuộc hàm LM G. Tuy nhiên lạm dụng cách làm này có thể dẫn đến việc đánh mất một số ràng buộc. Giả sử thêm thực thể phòng (P) vào mối kết hợp. Coi (g, m, l, p) = ((g, (m, l)), p)) chúng ta phát hiện phụ thuộc hàm LM G nhƣng việc bổ sung thực thể kết hợp giữa môn và lớp rồi thực thể kết hợp giữa môn- lớp và giảng viên vào mô hình, theo cách làm này, sẽ ngăn cản việc phát hiện ra phụ thuộc hàm khác nhƣ LP MG hay GP LM71. Trên lƣợc đồ Các phụ thuộc hàm tìm thấy không thể đơn giản hợp lại thành một tập phụ thuộc hàm đƣợc72. Ví dụ 7.21 Xét hai kết hợp Nợ và Có giữa Nhật ký và Tài khoản nhƣ sau 71 Trong nhiều trƣờng hợp, việc tìm đầy đủ các phụ thuộc hàm nên để lại bƣớc sau, khi đã đƣa ra đƣợc mô hình cơ sở dữ liệu quan hệ. Với tập phụ thuộc hàm này chúng ta sẽ chuẩn hoá bằng các kỹ thuật đã học ở những chƣơng trƣớc. 72 Một cách tổng quát, phụ thuộc hàm xác định tồn tại quan hệ hàm. Với dữ liệu cụ thể quan hệ hàm này phải hoàn toàn đƣợc xác định.
  71. 190 Giáo trình cơ sở dữ liệu Nhật ký 1:1 0:n Tài khoản Nợ NK ID TK Số Có 1:1 0:n Ở đây có hai quan hệ hàm giữa Nhật ký và Tài khoản. Việc mô tả bằng phụ thuộc hàm là không xác định. Thay đổi ngữ cảnh Chỉ quan tâm đến lƣợc đồ con. Trong ví dụ trên nếu xét trên ngữ cảnh ghi nợ cho tài khoản ta có Ví dụ 7.22 Trong ngữ cảnh ghi nợ cho tài khoản: Nhật ký 1:1 0:n Tài khoản Nợ NK ID TK Số Lúc này ta có quan hệ hàm giữa Nhật ký và Tài khoản, cụ thể Nhật ký → Tài khoản. Nhân bản thực thể Ví dụ 7.23 Nhân bản tài khoản Nhật ký 1:1 0:n Tài khoản Nợ NK ID TK Nợ Ta có Nhật ký → Tài khoản Nợ. Chuyên biệt hoá thực thể Ví dụ 7.24 Xét quy tắc quản lý: nhân viên (N) thuộc về một phòng (P); phòng phải có trƣởng phòng (T); trƣởng phòng phải là nhân viên thuộc phòng.
  72. Chƣơng 7: Mô hình thực thể kết hợp 191 Giải Mặc dù quan sát thấy có các phụ thuộc hàm N P, P T, T N nhƣng không thể xếp chúng thành một tập phụ thuộc hàm đƣợc. Trong ngữ cảnh toàn bộ nhân viên: Ta có N P là đúng. Nhân viên 1:1 0:n Phòng Mã NV Mã PG Trong ngữ cảnh toàn bộ trưởng phòng: Ta có N P, P T, T N đúng. Cần nhắc lại mỗi phụ thuộc hàm là một quan hệ hàm xác định. Chẳng hạn, với tập phụ thuộc hàm {A B, B C, A C} chúng ta có hai quan hệ hàm từ A vào C, một trực tiếp và một bắc cầu qua B. Do tính xác định, chúng là một và chúng ta loại bỏ quan hệ hàm đƣợc cho trực tiếp73. Nhƣ vậy chúng ta cần lƣu ý đến bản chất của các phụ thuộc dẫn xuất. Trong mô hình trên, tích giữa N P, P T và T N xác định N N hiểu là trưởng phòng của nhân viên và không là hàm đồng nhất, nhƣng tích giữa P T, T N và N P, xác định hàm đồng nhất P P và tích giữa T N, N P và P T xác định hàm đồng nhất T T. Theo đó, cơ sở dữ liệu sau là mâu thuẫn. nv (N P) pb (P T) tp (T N) a 1 1 u u a b 1 2 v v b c 2 d 2 vì (v b 1 u) và (2 v b 1) không là các quan hệ đồng nhất Bây giờ nếu chuyên biệt hoá, thì tập luật đúng theo ngữ cảnh và không còn mâu thuẫn. Xét lƣợc đồ sau: 73 Khi mô hình có chu trình thƣờng phải chú ý điều này. Thực tế có tồn tại nhiều quan hệ hàm giữa 2 tập thuộc tính và chúng ta cần đến ngữ cảnh.
  73. 192 Giáo trình cơ sở dữ liệu Nhân viên 1:1 0:n Phòng Mã NV Mã PG 1:1 G 1:1 NV Thường Trưởng phòng 1.6. Các ký hiệu trong Power Designer Trong chƣơng này chúng tôi sử dụng công cụ phần mềm hỗ trợ thiết kế (CASE, Computer-Aided Sofware Engineering) là Power Designer để lập mô hình quan niệm. Mục này nhằm giới thiệu các khái niệm và ký hiệu liên quan đến mô hình ER Thực thể, thuộc tính và miền giá trị Sử dụng ký hiệu hình chữ nhật có ba ngăn để mô tả thực thể: Ngăn trên chứa tên thực thể. Ngăn giữa là danh sách thuộc tính kèm miền giá trị74. Các thuộc tính tham gia khoá chính đƣợc gạch chân. Ngăn cuối là các ràng buộc (có thể bỏ nếu không cần phải mô tả). Thực thể Sinh Viên sau đây minh họa các điều trên. 74 ở mức trừu tƣợng cao, chƣa cần phải mô tả miền giá trị của thuộc tính
  74. Chƣơng 7: Mô hình thực thể kết hợp 193 Thực thể yếu Ta có ký hiệu thể hiện sự phụ thuộc, nhƣ sau Mối quan hệ (relationship) Dùng để đặc tả mối kết hợp không quá 2 ngôi và không có thuộc tính75. Hình sau minh họa mối kết hợp 1 ngôi và 2 ngôi: Mối kết hợp (association) Mối kết hợp cho phép có thuộc tính. Hình sau minh họa mối kết hợp 3 ngôi cho phép thêm thuộc tính. 75 cần lƣu ý bản số ghi trong ký hiệu mối quan hệ ngƣợc với bản số ghi trong mối kết hợp
  75. 194 Giáo trình cơ sở dữ liệu Nếu cần thiết chuyển thành thực thể (thực thể kết hợp) ta có Lƣu ý đến ký hiệu phụ thuộc. Trong mô hình trên ta quan sát thấy Lich Giang phụ thuộc vào hai thực thể Mon và Lop. Thật ra, trong mô hình này, ngƣời thiết kế muốn nhấn mạng đến ràng buộc phụ thuộc hàm. Thật vậy, gọi K là khoá của lịch giảng còn M, L và G là khoá của các thực thể Mon, Lop và Giang Vien tƣơng ứng, theo mô hình Lich Giang là thực thể yếu, ta có KML G. Trong thực tế, ngƣời thiết kế không đặc tả khoá cho lịch giảng, do đó phụ thuộc hàm thực sự là ML G. Thực thể cha và thực thể con Thực thể cha và các thực thể con với các ký hiệu giao bằng rỗng hoặc cho phép giao khác rỗng nhƣ đƣợc minh hoạ trong hình sau.
  76. Chƣơng 7: Mô hình thực thể kết hợp 195 Nhan Vien Inheritance_1 Quan Tri Giang Vien Inheritance_2 GV Moi GV Co Huu Ví dụ minh họa Trong mục này, chúng ta thử khảo sát các yêu cầu của hệ thống quản lý đào của một trƣờng đại học (không phải từ case study 2 ở chƣơng 1) để đƣa ra mô hình E-R nhƣ là một mô hình dữ liệu mức quan niệm. Từ các yêu cầu, chúng ta sẽ lần lƣợt đƣa ra các thực thể và các mối kết hợp để cuối cùng tích hợp lại thành mô hình. Đại học X có nhiều khoa, mỗi khoa tổ chức đào tạo một số ngành Để hoàn tất việc đào tạo khoa phải xây dựng một hệ thống các môn học. Các môn học này đƣợc thiết kế phù hợp với từng ngành và thứ tự học là quan trọng.
  77. 196 Giáo trình cơ sở dữ liệu Khoa cần các giảng viên có khả năng giảng dạy các môn này. Giảng viên phải thuộc về một khoa và đƣợc yêu cầu dạy ít nhất một môn nhƣng không quá 3 môn. Môn phải có giảng viên dạy và không quá 2 giảng viên Mỗi năm khoa đều mở ra một số lớp cho mỗi ngành Và phân công giảng dạy phù hợp với mục tiêu đào tạo Ta có mô hình dữ liệu mức quan niệm nhƣ sau
  78. Chƣơng 7: Mô hình thực thể kết hợp 197 1.7. Chuyển sang mô hình quan hệ Khi mô hình E-R đã đủ chi tiết, sẵn sàng cho việc xây dựng mô hình dữ liệu mức logic76, chúng ta dùng các quy tắc sau để chuyển mô hình E-R sang mô hình quan hệ. Quy tắc 1. Phát sinh lƣợc đồ quan hệ duy nhất cho các thực thể có tồn tại mối kết hợp 1:1 với tập khoá là các khoá chính của các thực thể gốc. 2. Mỗi thực thể chuyển thành một lƣợc đồ quan hệ với khoá chính là khoá chính của thực thể; 76 Trong kiến trúc 3 mức ANSI-SPARC, mức trong là mức gần với cài đặt. Thực tế khi thiết kế cơ sở dữ liệu chúng ta thƣờng xem mức trong theo hai cấp độ trừu tƣợng. Thiết kế cơ sở dữ liệu mức logic là xây dựng mô hình độc lập với hệ quản trị cơ sở dữ liệu và các quan tâm về mặt vật lý khác. Trong lúc Thiết kế cơ sở dữ liệu mức vật lý là quá trình đƣa ra các mô tả cài đặt cơ sở dữ liệu trên bộ nhớ thứ cấp; nó mô tả cấu trúc lƣu trữ và các phƣơng pháp truy xuất hiệu quả. Trong tài liệu này khi nói đến mô hình mức trong, chúng tôi nhấn mạnh đến mô hình cơ sở dữ liệu mức logic.
  79. 198 Giáo trình cơ sở dữ liệu 3. Mỗi thực thể phụ thuộc chuyển thành lƣợc đồ quan hệ với khoá chính là tổ hợp của khoá chính của thực thể với khoá chính của các thực thể bị phụ thuộc; 4. Với các mối kết hợp 1 ngôi: a. Mỗi mối kết hợp 1:n, mở rộng lƣợc đồ quan hệ thêm một lần nữa các thuộc tính của khóa chính (nhớ đổi tên) cùng với các thuộc tính của mối kết hợp; b. Mỗi mối kết hợp n:n chuyển thành lƣợc đồ quan hệ, bổ sung thêm gấp đôi các thuộc tính khoá chính (hình thành các ràng buộc khoá ngoại) và xác định ràng buộc khoá chính từ các thuộc tính này. 5. Với các kết hợp 2 ngôi: a. Mỗi mối kết hợp 1:n, mở rộng lƣợc đồ quan hệ bên bản số 1 để thêm các thuộc tính khóa chính của quan hệ bên bản số n (hình thành ràng buộc khoá ngoại) cùng với các thuộc tính của mối kết hợp; b. Mỗi mối kết hợp n:n chuyển thành lƣợc đồ quan hệ, thêm các thuộc tính khoá chính của các thực thể thành phần (hình thành các ràng buộc khoá ngoại) và xác định ràng buộc khoá chính từ các thuộc tính này. 6. Với các kết hợp nhiều hơn 2 ngôi chuyển thành lƣợc đồ quan hệ, thêm các thuộc tính khoá chính của các thực thể thành phần (hình thành các ràng buộc khoá ngoại) và xác định ràng buộc khoá chính từ các ràng buộc phụ thuộc. 7. Với mỗi lƣợc đồ quan hệ có đƣợc, dựa vào các quy tắc quản lý: a. Xác định tập phụ thuộc hàm; b. Phân rã lƣợc đồ bằng quá trình chuẩn hoá; c. Dùng view dựng lại lƣợc đồ gốc. Ví dụ 7.25 Xét mô hình dữ liệu quản lý nhân sự lƣu thông tin của nhân viên, của phòng và của các liên kết gồm liên kết nhân viên thuộc phòng và liên kết nhân viên làm trưởng phòng, với các quy tắc quản lý: Nhân viên thuộc về một phòng; Phòng phải có trƣởng phòng; Trƣởng phòng là nhân viên thuộc phòng.
  80. Chƣơng 7: Mô hình thực thể kết hợp 199 Biểu đồ ER sau cho ta ý niệm về mô hình dữ liệu. Theo đó, giữa thực thể nhân viên và thực thể phòng có một mối kết hợp 1:n. Thực thể trưởng phòng là một thực thể con của thực thể nhân viên, và có một mối kết hợp 1:1 giữa thực thể trưởng phòng và thực thể phòng. Biểu đồ này đã mô tả hai quy tắc đầu. Quy tắc thứ 3 sẽ đƣợc cài đặt thành ràng buộc toàn vẹn trong mô hình cơ sở dữ liệu mức logic. Thuộc tính khoá của trƣởng phòng vẫn là N. Ở đây chúng ta nên đổi lại tên. Gọi T là thuộc tính khoá của trƣởng phòng, ta có kết quả áp dụng các quy tắc nhƣ sau. Dùng các quy tắc 1 và 2: Phát sinh 2 lƣợc đồ quan hệ nv(N) và p(P T) Dùng quy tắc 5: Bổ sung P vào nv(NP) và ràng buộc khoá ngoại Cài đặt các quy tắc quản lý khác: Phụ thuộc tồn tại p[T] ⊂ nv[N] cài đặt trƣởng phòng là nhân viên; Phụ thuộc tồn tại p[TP] ⊂ nv[NP] cài đặt trƣởng phòng là nhân viên thuộc phòng. Vậy mô hình cơ sở dữ liệu mức logic gồm Hai lƣợc đồ quan hệ nv(NP) và p(P T); Và một ràng buộc tồn tại p[TP] ⊂ nv[NP].
  81. 200 Giáo trình cơ sở dữ liệu Ví dụ 7.26 Xét mô hình dữ liệu quản lý đào tạo với mô hình dữ liệu quan niệm đƣợc xây dựng bằng biểu đồ ER sau, không có các quy tắc quản lý nào khác ngoài các quy tắc quản lý đã đƣợc mô tả trên biểu đồ. Ký hiệu K, G, M, N và L là các thuộc tính khoá (khoá chính) của các thực thể Khoa, Giang Vien, Mon, Nganh và Lop tƣơng ứng, ta có kết quả áp dụng các quy tắc: Dùng các quy tắc 2 và 3: Phát sinh 5 lƣợc đồ quan hệ k(K), gv(G), m(MN), n(N) và l(L) Dùng quy tắc 4: Phát sinh lƣợc đồ tq(MNM‟N‟), trong đó M‟N‟ là tiên quyết của MN Dùng quy tắc 5:
  82. Chƣơng 7: Mô hình thực thể kết hợp 201 Mở rộng gv(GK), m(MNK), n(NK), n(LN), lƣu ý đến quan hệ đồng nhất Phát sinh gm(GMN) Dùng quy tắc 6: Phát sinh pc(GMNL), lƣu ý các quan hệ đồng nhất và ràng buộc tồn tại Kết quả ta có lƣợc đồ cơ sở dữ liệu {k(K), gv(GK), m(MNK), tq(MNM‟N‟), n(NK), l(LN), gm(GMN), pc(GMNL)} 2. Lập mô hình dữ liệu mức quan niệm Quá trình xây dựng mô hình dữ liệu mức quan niệm là một quá trình lặp. Sau mỗi vòng lặp mô hình đƣợc đặc tả đầy đủ hơn, gần với thực tế hơn. Mô hình ban đầu với những thực thể và các mối kết hợp chung nhất, tổng quát và chủ yếu nhất. Mô hình cuối cùng là mô hình đạt đƣợc sự thỏa thuận giữa ngƣời dùng cuối và ngƣời thiết kế. Phƣơng pháp luận Chúng ta làm quen với quy trình 5 bƣớc sau: 1. Thu thập thông tin về tổ chức đáp ứng yêu cầu của hệ thống: a. Phương pháp: phỏng vấn để hiểu yêu cầu hệ thống, phân tích các nghiệp vụ để phát hiện tất cả dữ liệu vào ra hệ thống; b. Công cụ: sơ đồ dòng dữ liệu, sơ đồ dòng công việc; c. Mục tiêu: xác định dòng công việc và thông tin liên quan tới tổ chức. 2. Lập mô hình quan niệm: a. Phương pháp: đọc tài liệu phỏng vấn, phân tích tập dữ liệu, xác định các yêu cầu xử lý và các quy tắc quản lý; b. Công cụ: mô hình thực thể kết hợp; c. Mục tiêu: tìm thực thể, mối kết hợp và các ràng buộc 3. Chuẩn hoá
  83. 202 Giáo trình cơ sở dữ liệu a. Phương pháp: với mỗi lƣợc đồ quan hệ từ mô hình ER, xác định tập phụ thuộc hàm, phụ thuộc đa trị; b. Công cụ: dùng lý thuyết thiết kế; c. Mục tiêu: dạng chuẩn 3, đặc trƣng đầy đủ F, bảo toàn thông tin. 4. Xây dựng các biểu đồ thể hiện của bảng (Table Instance Charts) a. Phương pháp: quan sát tập dữ liệu và thử đặt chúng vào bảng; b. Công cụ: dùng mẫu; c. Mục tiêu: sẵn sàng cho cài đặt. 5. Cài đặt a. Phương pháp: với lƣợc đồ cơ sở dữ liệu vừa xây dựng xong, từ các quy tắc quản lý, xây dựng các ràng buộc toàn vẹn; b. Công cụ: dùng ngôn ngữ SQL; c. Mục tiêu: cơ sở dữ liệu nhất quán. Với quy trình trên, trong phạm vi tài liệu này chúng ta quan tâm đến các bƣớc 2 và 3. Các bƣớc 1, 4 và 5 đƣợc giới thiệu trong các môn khác. Do các kỹ năng ở bƣớc 3 đã đƣợc giới thiệu trong các chƣơng trƣớc, chƣơng này chúng ta tập trung vào bƣớc 2. Mục sau khảo sát một tình huống nhằm minh hoạ các công việc của bƣớc 2. 2.1. Khảo sát tình huống Cửa hàng C kinh doanh hai mặt hàng a và b cung cấp chủ yếu cho hai khách hàng u và v. Cửa hàng có hai nhân viên bán hàng x và y và một kế toán c. Trong ngày hôm nay nhân viên x bán cho khách hàng u cả 2 mặt hàng a và b với số lƣợng tƣơng ứng là 3 và 2. Hoá đơn đƣợc chuyển đến kế toán c để ghi sổ kế toán. Công việc kế toán của cửa hàng chỉ liên quan đến các tài khoản 111, 511, 156, 632, 331 và 911. Đầu ngày, kế toán c đã tính toán các dữ liệu liên quan công nợ khách hàng, giá bán, giá vốn và lượng tồn kho hàng hoá. Theo đó, khách hàng u nợ 40, khách hàng v nợ 20, hàng a còn lại 17 giá bán 14 giá vốn 12, hàng b còn lại 8 giá bán 22 giá vốn 19.
  84. Chƣơng 7: Mô hình thực thể kết hợp 203 Khi lập hoá đơn, nhân viên bán hàng phải ghi lại số hoá đơn, ngày lập, tiền trả trước của khách, ai bán, bán cho ai, bán những mặt hàng nào, số lượng bán và số lượng còn lại của từng mặt hàng. Ở đây, sau khi bán hàng cho u, nhân viên x ghi lại các dữ liệu cụ thể là: hoá đơn số 7, lập ngày 13, trả trƣớc 40, x bán, bán cho u, bán mặt hàng x số lƣợng 3 còn lại 14 và mặt hàng y số lƣợng 2 còn lại 6. Khi nhận hoá đơn kế toán phải ghi các bút toán gồm : bút toán thứ mấy, ngày ghi sổ, ghi cho hoá đơn nào, tài khoản ghi nợ, tài khoản ghi có và số tiền. Trong trƣờng hợp này, kế toán c ghi 3 bút toán với dữ liệu giống nhau là ghi sổ ngày 13, ghi cho hoá đơn số 7 và các dữ liệu khác nhau nhƣ sau: bút toán 20 ghi nợ 111 ghi có 511 số tiền 40, bút toán số 21 ghi nợ 331 ghi có 511 số tiền 46, bút toán 22 ghi nợ 632 ghi có 156 số tiền 74. Hình sau mô tả tất cả dữ liệu hiện có qua các cấu trúc và các liên kết: a b x y c 17 8 14 22 u v 7 12 19 2 6 13 40 20 3 40 14 2 14 14 111 14 911 511 14 331 156 632
  85. 204 Giáo trình cơ sở dữ liệu 2.2. Tìm thực thể Bắt đầu từ việc quan sát một số dữ liệu mẫu. Các thao tác tổ chức dữ liệu đơn giản thƣờng liên quan đến quan hệ nội tại giữa dữ liệu và các yêu cầu chức năng của hệ thống. Việc quan sát nên bắt đầu từ các chức năng vì khi phân tích chức năng chúng ta nhìn thấy dữ liệu77. Ở đây, chúng ta có hai chức năng: lập hoá đơn và ghi sổ nhật ký kế toán. Theo định nghĩa, thực thể dùng để mô tả các đối tƣợng cùng loại. Đặc biệt, chúng thƣờng tồn tại độc lập. Với sơ đồ trên, chúng ta đã gom dữ liệu của một đối tƣợng lại, qua đó xác định đƣợc các đối tƣợng cùng loại. Chúng ta thu đƣợc danh sách các thực thể 2.3. Tìm mối kết hợp Các thực thể có các quan hệ nội tại. Tuy nhiên, việc xem xét các chức năng chúng ta sẽ thấy rõ hơn quá trình sinh ra các kết hợp. Chẳng hạn, với chức năng lập hoá đơn chúng ta sinh ra hoá đơn cùng các kết hợp giữa nó với nhân viên, với khách hàng và với hàng hoá 77 Giống nhƣ khi xét thao tác cộng hai số, chúng ta thấy có 3 mục dữ liệu.