›
›

Giáo trình Thiết kế cơ sở dữ liệu 2 (Phần 1)

pdf 59 trang hapham 2030
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Thiết kế cơ sở dữ liệu 2 (Phần 1)", để 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_thiet_ke_co_so_du_lieu_2_phan_1.pdf

Nội dung text: Giáo trình Thiết kế cơ sở dữ liệu 2 (Phần 1)

  1. Chương I: MÔ HÌNH QUAN HỆ I. MÔ HÌNH QUAN HỆ I.1. Các khái niệm cơ bản Khái niệm toán học của mô hình quan hệ là quan hệ hiểu theo nghĩa lý thuyết tập hợp : là tập của con của tích Đề - Các của các miền; miền (domain) là một tập các giá trị. Ví dụ tập các số nguyên là một miền; tập các xâu ký tự tạo thành tên người trong tiếng Anh có độ dài không quá 30 ký tự là một miền; tập hai số {0,1} cũng là một miền v.v Gọi D1, D2 , , Dn là n miền. Tích Đề - Các của n miền ký hiệu : D1xD2x xDn là tập tất cả n -bộ (n- tuples) (v1, v2, vn ) sao cho vi Di , với i = 1 n Thí dụ: Với n= 2, D1 = {0,1}, D2 = {a,b,c}, khi đó D1 x D2 = {( 0,a), (0,b), (0,c), (1,a), (1,b), (1,c)}. Quan hệ : Quan hệ là một tập con của tích Đề - Các của một hoặc nhiều miền. Như vậy mỗi quan hệ có thể là vô hạn. Ở đây luôn luôn giả thiết rằng, quan hệ là một tập hữu hạn. Mỗi hàng của quan hệ gọi là bộ (tuples), quan hệ là tập con của tích Đề - Các D1 x D2 x x Dn gọi là quan hệ n ngôi. Khi đó mỗi bộ của của quan hệ có n thành phần (n cột). Các cột của quan hệ gọi là thuộc tính (attributes). Định nghĩa quan hệ một cách hình thức như sau: Trang 1
  2. I.1.1. Định nghĩa I.1 Gọi R = {A1,A2, , An } là tập hữu hạn các thuộc tính, mỗi thuộc tính Ai với i = 1,2, , n có miền giá trị tương ứng là dom(Ai). Quan hệ r được định nghĩa trên tập thuộc tính R là tập con của tích Đề - Các của các miền. r  dom (A1) x dom(A2) x x dom(An) Khi đó ký hiệu là r(R) hoặc r (A1, An ). Thí dụ: Hình I.1 cho thấy quan hệ NHANVIEN bao gồm các thuộc tính HOTEN, NAMSINH, NOILAMVIEC là một quan hệ 3 ngôi. NHANVIEN (HoTen, NamSinh, NoiLamViec ) t1 Lê Văn A 1960 Trường ĐHVL t2 Hoàng Thị B 1970 Trường ĐHBK - Hình I.1 - quan hệ NHANVIEN - t1=(Lê Văn A ,1960, Trường DHVL) là một bộ của quan hệ NHANVIEN Lược đồ quan hệ là sự trừu tượng hóa của quan hệ, một sự trừu tượng hóa ở mức độ cấu trúc của một bảng 2 chiều. Khi nói đến lược đồ quan hệ tức là đề cập đến cấu trúc tổng quát của một quan hệ, đó là các thuộc tính và mối liên hệ ngữ nghĩa giữa chúng. Ký hiệu : lược đồ quan hệ R Trang 2
  3. Thể hiện (còn gọi là tình trạng) của quan hệ là tập hợp các bộ giá trị của quan hệ vào một thời điểm. Tại những thời điểm khác nhau quan hệ sẽ có những thể hiện khác nhau. Ký hiệu : thể hiện r Lưu ý: Khi cho quan hệ r, ta muốn nói đến một thể hiện cụ thể của quan hệ đó. Nghĩa là r là tập hợp gồm các bộ cụ thể. Thí dụ: Cho lược đồ quan hệ R = {A1,A2, , An }, với Ai là các thuộc tính, gọi r là một quan hệ (thể hiện) của lược đồ quan hệ R. Quan hệ r gồm có các bộ sau : t1=(a11,a21, ,an1) t2=(a12,a22, ,an2) Ta có: quan hệ r lược đồ quan hệ R; bộ t1 quan hệ r I.2. Khoá I.2.1. Định nghĩa I.2 Cho lược đồ quan hệ R định nghĩa trên tập các thuộc tính U={A1, An }. K  U là khoá (key) của lược đồ quan hệ R nếu thoả 2 điều kiện sau đây : (i) K xác định đươc mọi giá trị của Aj , với j=1, 2, , n (ii) Không tồn tại K’  K(K’<>K )màK’cũng thỏa (i) Điều kiện (i) nghĩa là: với một quan hệ bất kỳ r lược đồ R, và với bất kỳ hai bộ t1, t2 quan hệ r đều tồn tại một thuộc tính A K sao cho t1[A] t2[A]. Nói cách khác, không tồn tại hai bộ mà có giá trị bằng nhau trên mọi thuộc tính của K. Điều kiện này có thể viết t1[K] t2[K]. Do vậy mỗi giá trị của K là xác định duy nhất. Trang 3
  4. Giả sử K là khóa thì mọi tập K”  U mà K”  K thì K” cũng thoả (i). Các tập K” thoả điều kiện (i) được gọi là siêu khoá (super key) còn gọi là khoá bao hàm. Điều kiện (ii) xác định khoá là tập nhỏ nhất trong một họ các siêu khoá. Trong lược đồ quan hệ có thể có nhiều khoá. Khi cài đặt trên một hệ quản trị cơ sở dữ liệu ta phải chọn một để làm khóa chính (primary key). HANGHOA (MSMH TENHANG SOLUONG) 10101 sắt phi 6 1000 10102 sắt phi 8 2000 20001 xi măng 1000 - Hình I.2 - quan hệ HANGHOA - Trong hình I.2 biểu diễn quan hệ HANGHOA trong đó mã số mặt hàng (MSMH) là khoá. Mỗi giá trị MSMH đều xác định duy nhất một loại mặt hàng trong quan hệ HANGHOA. I.3. Các phép tính trên CSDL quan hệ Các phép tính cơ bản mà nhờ đó một cơ sở dữ liệu được thay đổi là chèn (INSERT). loại bỏ (DELETE) và cập nhật (UPDATE). Trong mô hình CSDL quan hệ được nêu trên, các phép tính này được áp dụng cho từng bộ phận của các quan hệ lưu trữ trong máy - việc tổ chức các quan hệ và các bộ của nó có thể được xem như biểu diễn tương ứng một - một qua các tệp (file) và các bản ghi (record). I.3.1. Phép chèn (INSERT) Phép chèn thêm một bộ t vào quan hệ r của lược đồ R= {A1, ,An } có dạng r= r  {t} INSERT (r ; A1=d1,A2=d2, ., An=dn). Trang 4
  5. Trong đó Ai với i= 1, , n là tên các thuộc tính và di dom (Ai) là các giá trị thuộc miền trị tương ứng của thuộc tính Ai. Thí dụ: Thêm một bộ t3 = (Vũ Văn Tần, 1960, trường ĐHBK) vào quan hệ NHANVIEN trong hình I.1: INSERT (NHANVIEN ; HOTEN = Vũ Văn Tần, NAMSINH = 1960, NOILAMVIEC = trường ĐHBK) Nếu xem thứ tự trường là cố định, khi đó có thể biểu diễn phép chèn dưới dạng không tường minh như sau: INSERT (r ; d1, d2, ., dn). Mục đích của phép chèn là thêm một bộ mới vào một quan hệ nhất định. Kết quả của phép tính này có thể gây ra một số sai sót với những lý do sau đây: 1. Bộ mới được thêm vào là không phù hợp với lược đồ quan hệ cho trước; 2. Một số giá trị của một số thuộc tính nằm ngoài miền giá trị của thuộc tính đó; 3. Giá trị khoá của bộ mới có thể là giá trị đã có trong quan hệ đang lưu trữ. Do vậy, tuỳ từng trường hợp cụ thể sẽ có những cách khắc phục riêng. I.3.2. Phép loại bỏ (DELETE) Phép loại bỏ là phép xoá một bộ ra khỏi một quan hệ cho trước. Giống như phép chèn, phép loại bỏ có dạng: r = r – {t} DELETE (r ; A1=d1,A2=d2, ., An=dn) hoặc DELETE (r ; d1, d2, ., dn). Trang 5
  6. Thí dụ: Cần loại bỏ bộ t1 từ quan hệ NHANVIEN trong hình I.1: DELETE (NHANVIEN ; Lê Văn A, 1960, Trường DHVL) Tất nhiên không phải lúc nào phép loại bỏ cũng cần đầy đủ thông tin về cả bộ. Nếu có giá trị về bộ đó tại các thuộc tính khoá K = {B1 , Bi } khi đó phép loại bỏ chỉ cần viết: DELETE ( r; B1 =e1,B2 =e2, Bi = ei ) Thí dụ: Cần loại bỏ sắt phi sáu ra khỏi quan hệ HANGHOA trong hình I.2, khi đó chỉ cần viết: DELETE (HANGHOA; MSMH = 10101) I.3.3. Phép cập nhật (UPDATE) Trong thực tế không phải lúc nào cũng chỉ dùng phép chèn hoặc loại bỏ đi một bộ mà nhiều khi chỉ cần sửa đổi một số giá trị nào đó tại một số thuộc tính, lúc đó cần thiết phải sử dụng phép cập nhật. Gọi tập {C1, , Cp}  {A1, , An} là tập các thuộc tính mà tại đó các giá trị của bộ cần thay đổi, khi đó phép cập nhật có dạng : r = (r \ {t})  {t’}. UPDATE (r; A1=d1,A2=d2, , An=dn ;C1=e1 ,C2=e2 , , Cp=ep) Nếu K= {B1, , Bm} là khoá của quan hệ, khi đó chỉ cần viết: UPDATE (r; B1=d1,B2=d2, , Bm=dm ;C1=e1 ,C2=e2 , , Cp=ep) Thí dụ: Cần thay đổi số lượng của sắt phi 8 trong quan hệ HANGHOA trong hình I.2, còn 150 tấn UPDATE (HANGHOA; MSMH=10102; SOLUONG =150) Trang 6
  7. Phép cập nhật là phép tính rất thuận lợi, hay dùng. Cũng có thể không dùng phép cập nhật mà dùng tổ hợp của phép loại bỏ và phép chèn một bộ mới. Do vậy những sai sót của phép cập nhật cũng sẽ xảy ra tương tự như phép chèn và phép loại bỏ. II. ĐẠI SỐ QUAN HỆ Trong chương này trình bày nguyên tắc tiếp cận để thiết kế các ngôn ngữ biểu diễn câu hỏi về các quan hệ. Đối tượng của ngôn ngữ thao tác dữ liệu quan hệ hay còn gọi là “ngôn ngữ hỏi” (query language), thường liên quan chặt chẽ với các phép tính chèn , loại bỏ, cập nhật các bộ của quan hệ. Mặt khác các câu hỏi có thể xem trong trường hợp tổng quát là những hàm số áp dụng lên các quan hệ. Ngôn ngữ hỏi cho mô hình quan hệ được chia hai lớp : - Ngôn ngữ đại số, trong đó câu hỏi được biểu diễn nhờ áp dụng các phép tính đặc bịêt đối với quan hệ và - Ngôn ngữ tính toán tân từ, trong đó câu hỏi được biểu diễn là một tập hợp các bộ thoả mãn các tân từ xác định. Dưới đây sẽ trình bày chi tiết ngôn ngữ đại số quan hệ như là cơ sở của một ngôn ngữ bậc cao để thao tác trên quan hệ. Gọi r là quan hệ trên tập thuộc tính R = {A1, , An} . Ở đây luôn giả thiết rằng quan hệ r là tập hữu hạn các bộ. Đối với các phép hợp, giao và trừ, hai quan hệ tham gia phải là khả hợp. Hai quan hệ được gọi là khả hợp nếu chúng giống nhau đôi một các thuộc tính. Các thuộc tính có thể khác tên gọi nhưng phải cùng miền giá trị. Trang 7
  8. II.1. Phép hợp Hợp của hai quan hệ r và s khả hợp, ký hiệu là r  s là tập các bộ t thuộc quan hệ r hay thuộc quan hệ s. Biểu diến hình thức phép hợp có dạng: r  s = { t / t r hay t s} Thí dụ: r ( A B C ) s ( A B C ) r  s = (ABC) a1 b1 c1 a1 b1 c1 a1 b1 c1 a2 b1 c2 a2 b2 c2 a2 b1 c2 a2 b2 c1 a2 b2 c1 a2 b2 c2 II.2. Phép giao Giao của hai quan hệ r và s khả hợp, ký hiệu là r  s là tập hợp các bộ t thuộc cả quan hệ r và s. Biểu diễn hình thức phép giao có dạng: r  s = {t / t r và t s } Thí dụ: Với r và s là hai quan hệ ở ví dụ trên, giao của chúng là: r  s = (A B C ) a1 b1 c1 II.3. Phép trừ Hiệu của hai quan hệ r và s khả hợp, ký hiệu là r-s, là tập các bộ t thuộc r nhưng không thuộc s. Biểu diễn hình thức phép có dạng: r - s = {t / t r và t s } Trang 8
  9. Thí dụ: Cũng với r, s ở ví dụ trên: r - s = (A B C ) a2 b1 c2 a2 b2 c1 Chú ý: Phép giao của 2 quan hệ r  s có thể biểu diễn qua phép trừ: r  s = r-(r - s ) II.4. Tích Đề-Các Gọi r là quan hệ xác định trên tập thuộc tính {A1,A2, ,An} và s là quan hệ xác định trên tập thuộc tính {B1,B2, ,Bm}. Tích Đề-Các của quan hệ r và s, ký hiệu r x s, là tập (n+m) –bộ với n thành phần đầu có dạng một bộ thuộc r và n thành phần sau có dạng một bộ thuộc s. Biểu diễn hình thức có dạng r x s = {t / t có dạng (a1,a2, ,an,b1,b2, ,bm), trong đó (a1,a2, ,an) r và (b1,b2, ,bm) s } Thí dụ: r ( A B C ) s ( D E F ) r x s = (ABCDEF) a1 b1 c1 d e f a1 b1 c1 d e f a2 b2 c2 d’ e’ f’ a1 b1 c1 d’ e’ f’ a2 b2 c2 d e f a2 b2 c2 d’ e’ f’ Trang 9
  10. II.5. Phép chiếu Phép chiếu trên một quan hệ thực chất là loại bỏ đi một số thuộc tính và giữ lại những thuộc tính khác của quan hệ đó. Giả sử r là một quan hệ n ngôi (gồm n thuộc tính): R = {A1, , An }, Viết  Ai1Ai2 Aim ( r), {Ai1, , Aim } R. Khi đó hiểu rằng phép chiếu trên các thuộc tính Ai1, , Aim của quan hệ r sẽ được tập các bộ có dạng ai1 aim. Để thuận tiện cho việc biểu diễn hình thức phép chiếu, từ đây quy định một số ký hiệu như sau: Gọi t là một bộ thuộc r, A R. t[A] là giá trị của bộ t tại thuộc tính A. X  R. Với X={B1, , Bm}thì t[X] = (t[B1], t[B2], , t[Bn]). Gọi X là tập con của thuộc tính R. Phép chiếu trên tập X của quan hệ r, ký hiệu là X(r) (hoặc ký hiệu r[X]) được định nghĩa như sau: X(r) ={t[X] / t r} Thí dụ: R = {A, B, C,D},X={A,B};Y={A,C} r (A, B, C, D) X(r) = (A, B) ; Y(r) = (A, C) a1 b1 c1 d1 a1 b1 a1 c1 a1 b1 c1 d2 a2 b2 a2 c2 a2 b2 c2 d2 a2 c3 a2 b2 c3 d3 Trang 10
  11. II.6. Phép chọn Phép chọn là phép tính để xây dựng một tập con các bộ của quan hệ đã cho, thoả mãn biểu thức F xác định. Biểu thức F được diễn tả bằng một tổ hợp Boolean của các toán hạng, mỗi toán hạng là một phép so sánh đơn giản giữa hai biến là hai thuộc tính hoặc giữa một biến là một thuộc tính và một hằng, cho giá trị “đúng” hoặc “sai” đối với mỗi bộ đã cho khi kiểm tra riêng bộ ấy. Các phép so sánh trong biểu thức F là =. <= và ; Các phép logic là  (và)  (hoặc)  (không). Gọi F(t) là một biểu thức logic có biến là các bộ t. Phép chọn các bộ của quan hệ r dựa theo điều kiện F, ký hiệu là F(r) (hoặc ký hiệu r:(F)) được định nghĩa như sau: F (r ) = { t r  F (t) = đúng } F(t) được biểu thị là giá trị của các thuộc tính xuất hiện trong biểu thức F tại bộ t thoả các điều kiện của F. Thí dụ: Cho quan hệ ở hình sau. Các phép chọn r (A, B, C, D) a1 b1 c1 d1 a1 b1 c1 d2 a2 b2 c2 d2 a2 b2 c3 d3 A = a1 (r ) = (A B C D) a1 b1 c1 d1 a1 b1 c1 d2 A = a1  D=d2 (r ) = (A B C D) a1 b1 c1 d2 Trang 11
  12. II.7. Phép kết nối Để định nghĩa phép kết nối của các quan hệ, trước hết làm quen với khái niệm xếp cạnh nhau. Giả sử cho bộ t = (t1, t2, ., tn) và bộ u= (u1, u2, .um), phép xếp cạnh nhau của d và e định nghĩa qua (t,u)= (t1, t2, ., tn, u1, u2, .um) Gọi  là một trong các phép so sánh { =,>, >=, < s = (A B C C D E) B C a1 1 1 1 d1 e1 a1 1 1 1 d1 e1 a1 2 1 2 d2 e2 a2 2 1 1 d1 e1 a1 2 2 3 d3 e3 a2 2 1 2 d2 e2 a1 2 2 1 d1 e1 a1 2 2 2 d2 e2 Trang 12
  13. Kết quả nối tự nhiên: r(ABC) *s(CDE) = (A B C D E) a1 1 1 d1 e1 a2 2 1 d1 e1 a2 2 2 d2 e2 II.8. Phép chia Gọi r là quan hệ n – ngôi và s quan hệ m – ngôi (n>m, s  ). Phép chia r  s là tập của tất cả (n-m) bộ t sao cho với mọi bộ u s thì bộ (t,u) r. Thí dụ: r(A B C D) s(C D ) r  s = (A B ) a b c d c d a b a b e f e f e d b c e f e d c d e d e f a b d e II.9. Các ví dụ về tìm kiếm bằng đại số quan hệ Thí dụ: Cho ba quan hệ: S (S, SNAME, STATUS, CITY): các hãng cung ứng P (P, PNAME, COLOR, WEIGHT, CITY):các mặt hàng SP ( S,P, QTY): các mặt hàng đã cung cấp. Trang 13
  14. - Tìm số hiệu của những hãng đã cung ứng mặt hàng P2. S (P = ’P2’ (SP)) - Tìm số hiệu của những hãng cung ứng ít nhất là một mặt hàng màu đỏ S (COLOR = ’RED’ (P*SP)) hoặc S (COLOR = ’RED’ (P))*SP) Trang 14
  15. Chương II: CÁC PHỤ THUỘC DỮ LIỆU TRONG MÔ HÌNH QUAN HỆ I. MỞ ĐẦU I.1. Thế nào là một thiết kế cơ sở dữ liệu kém Trước khi bàn về cách thiết kế một lược đồ cơ sở dữ liệu tốt, chúng ta phải phân tích xem tại sao trong một số lược đồ lại tồn tại những vấn đề rắc rối. Ví dụ cho lược đồ về thông tin cung cấp như sau: TT_CUNGCAP(NHACC, DIACHI, MATHANG, GIA) XMHT , 123 , P400 ,50000 XMHT , 123 , P500 ,52000 XMSM , 456 , P400 ,49000 - Hình II.1 - quan hệ TT_CUNGCAP - Lược đồ này chứa tất cả các thông tin về nhà cung cấp như: tên nhà cung cấp, địa chỉ nhà cung cấp, mặt hàng mà họ có thể cung cấp và giá. Chúng ta có thể nhận thấy nhiều vấn đề trong đó: 1. Dư thừa (redundancy). Địa chỉ của nhà cung cấp được lập lại mỗi lần cho mỗi mặt hàng được cung cấp. 2. Mâu thuẫn tiềm ẩn (potential inconsistancy) hay bất thường khi cập nhật. Do hậu quả của dư thừa, chúng ta có thể thay đổi địa chỉ của một nhà cung cấp trong một bộ nhưng vẫn để lại địa chỉ cũ trong một bộ khác. Vì vậy chúng ta có thể không có một địa chỉ duy nhất đối với mỗi nhà cung cấp như chúng ta tưởng. Trang 15
  16. 3. Bất thường khi chèn (insertion anomaly). Chúng ta không thể biết địa chỉ của nhà cung cấp nếu hiện tại họ không cung cấp ít nhất một mặt hàng. Chúng ta có thể đặt những giá trị null trong các thành phần MATHANG và GIA của một bộ cho người đó, nhưng khi chúng ta nhập một mặt hàng cho nhà cung cấp đó, chúng ta có nhớ xoá đi bộ mang giá trị null hay không? Điều tệ hại là MATHANG và NHACC cùng tạo ra một khoá cho quan hệ đó, và có lẽ không thể tìm ra các bộ nhờ chỉ mục sơ cấp được nếu có những giá trị null trong trường khoá MATHANG. 4. Bất thường khi xoá (deletion anomaly). Ngược lại với vấn đề (3) là vấn đề chúng ta có thể xoá tất cả các mặt hàng được cung cấp bởi một người, vô ý làm mất dấu vết để tìm ra địa chỉ của nhà cung cấp này. Bạn đọc cần nhớ rằng vấn đề dư thừa và mâu thuẩn tiềm ẩn là những vấn đề chúng ta đã từng phân tích và giải quyết trong các mô hình khác. Trong mô hình mạng, các trường ảo được đưa ra nhằm mục đích loại bỏ các dư thừa và mâu thuẩn. Trong mô hình phân cấp, chúng ta đã dùng kiểu mẫu tinh ảo với mục đích tương tự. Mô hình đối tượng được tạo ra bằng các con trỏ chứ không phải bằng việc sao chép các đối tượng. Trong thí dụ hiện tại, tất cả các vấn đề nêu trên sẽ biến mất khi chúng ta thay TT_CUNGCAP bằng hai lược đồ quan hệ sau: NHACUNGCAP (NHACC, DIACHI) XMHT , 123 XMSM , 456 CUNGCAP(NHACC, MATHANG, GIA) XMHT , P400 ,50000 XMHT , P500 ,52000 XMSM , P400 ,49000 - Hình II.2 - quan hệ NHACUNGCAP và CUNGCAP - Trang 16
  17. Giống như trong hình II.1. Ở đây, quan hệ NHACUNGCAP cung cấp địa chỉ của mỗi nhà cung cấp đúng một lần; do vậy không có dư thừa. Ngoài ra chúng ta cũng có thể nhập địa chỉ của nhà cung cấp dù hiện tại họ không cung cấp một mặt hàng nào. Tuy vậy vẫn còn một số câu hỏi còn bỏ ngõ. Chẳng hạn phân rã ở trên vẫn còn một khiếm khuyết: đó là để tìm địa chỉ của nhà cung cấp mặt hàng P400, bây giờ chúng ta phải thực hiện một phép nối có chi phí cao, còn với một quan hệ duy nhất TT_CUNGCAP chúng ta có thể dễ dàng trả lời bằng cách thực hiện một phép chọn rồi chiếu. Hoặc giả làm sao đế xác định được rằng cách thay thế ở trên có nhiều ưu điểm hơn? Liệu có tồn tại trong hai lược đồ quan hệ mới những vấn đề thuộc bốn loại đã nêu ở trên không? Làm thế nào để có được một cách thay thế tốt cho một lược đồ quan hệ chưa tốt? I.2. Phụ thuộc và dư thừa Chúng ta còn nhấn mạnh đến mối quan hệ giữa các phụ thuộc và dư thừa. Tổng quát, một phụ thuộc là một khẳng định rằng chỉ một tập con của các quan hệ khả hữu là “hợp lệ”, nghĩa là chỉ có một số quan hệ phản ảnh đúng tình trạng khả hữu của thế giới thực. Nếu không phải tất cả các quan hệ đều hợp lý, chúng ta có thể suy ra rằng tồn tại một số loại dư thừa trong những quan hệ hợp lệ. Nghĩa là cho trước khẳng định R là một quan hệ hợp lệ, nghĩa là thoả một số phụ thuộc nào đó, và cho trước các thông tin về gía trị hiện tại của R, chúng ta sẽ có thể suy ra được một số thông tin khác về giá trị hiện tại của R. Trong trường hợp phụ thuộc hàm, hình thái của dư thừa khá rõ ràng. Trong quan hệ TT_CUNGCAP nếu chúng ta gặp hai bộ: Trang 17
  18. TT_CUNGCAP(NHACC, DIACHI, MATHANG, GIA) XMHT , 123 , P400 ,50000 XMHT , ??? , P500 ,52000 Chúng ta có thể cho rằng DIACHI phụ thuộc hàm vào NHACC và suy ra rằng ba chấm hỏi ??? biểu thị cho chuỗi « 123 ». Vì vậy đối với nhà cung cấp đã cho, phụ thuộc hàm làm cho tất cả các giá trị của DIACHI trở nên dư thừa ngoại trừ giá trị của DIACHI ở hàng đầu tiên : ta biết được điều đó mà không cần phải thấy được nó. Ngựơc lại, nếu chúng ta không cho rằng phụ thuộc hàm của DIACHI vào NHACC là đúng, thế thì không có lý do gì để tin rằng ??? biểu thị một giá trị cụ thể nào, và trường hợp đó sẽ không phải là dư thừa. Khi phân tích một số loại phụ thuộc tổng quát hơn, hình thái của dư thừa không rõ ràng như trong phụ thuộc hàm. Tuy nhiên trong tất cả mọi trường hợp, dường như là căn nguyên và cách điều trị dư thừa luôn đi song hành. Nghĩa là phụ thuộc không chỉ gây ra dư thừa, chẳng hạn như phụ thuộc của DIACHI vào NHACC, nhưng nó cũng cho phép phân rã quan hệ TT_CUNGCAP thành các quan hệ NHACC và CUNGCAP bằng một cách để có thể khôi phục lại quan hệ gốc TT_CUNGCAP từ các quan hệ NHACC và CUNGCAP. Chúng ta sẽ thảo luận những vấn đề này một cách đầy đủ hơn trong phần sau. I.3. Phụ thuộc hàm là gì Gọi R (A1, ,An) là một lược đồ quan hệ,X,Y là các tập con của {A1, ,An}. Ta nói X Y, đọc là « X xác định Y theo kiểu hàm » hoặc « Y phụ thuộc hàm vào X » nếu, với bất kỳ mọi quan hệ r nào đó là giá trị hiện hành (thể hiện) của R, không thể tồn tại hai bộ giống nhau ở các thành phần cho tất cả các thuộc tính trong tập X nhưng lại khác nhau ở một hay nhiều thành phần cho các thuộc tính trong tập Y. Vì vậy phụ Trang 18
  19. thuộc hàm của thuộc tính địa chỉ nhà cung cấp (DIACHI) vào tên nhà cung cấp (NHACC) có thể đựoc diễn tả bằng (NHACC) (DIACHI) I.4. Quy ước về ký hiệu Để nhắc bạn đọc về ý nghĩa các ký hiệu được sử dụng, chúng ta thừa nhận các quy ước dưới đây : 1. Các chữ hoa ở đầu bộ chữ cái A,B, C, biểu thị một thuộc tính đơn. 2. Các chữ hoa ở cuối bộ chữ cái U, V, Z, biểu thị cho tập các thuộc tính, có thể là tập chỉ một thuộc tính. 3. R đựoc dùng để biểu thị một lược đồ quan hệ. Chúng ta cùng đặt tên các quan hệ bằng lược đồ của chúng, chẳng hạn một quan hệ có các thuộc tính A,B,C có thể được viết là ABC. 4. Chúng ta sử dụng r cho một quan hệ, là thể hiện hiện hành của lược đồ R. 5. Ký hiệu nối kết chuỗi được dùng biểu thị phép hợp. Do vậy, A1 .An được dùng để biểu diễn tập các thuộc tính {A1 .An} và XY viết tắt của X  Y. trường hợp XA hay AX cũng được viết thay cho X  {A}, với X là tập các thuộc tính và A là một thuộc tính đơn. II. PHỤ THUỘC HÀM II.1. Ý nghĩa của phụ thuộc hàm Các phụ thuộc hàm nảy sinh tự nhiên trong nhiều tình huống. Chẳng hạn nếu R biểu diễn cho một thực thể có các thuộc tính là A1 .An và X là tập các thuộc tính tạo ra một khoá cho tập thực thể này thì chúng ta có thể khẳng định rằng X Y với mọi tập con thuộc tính Y, kể cả khi tập Y có các thuộc tính chung với X. Lý do là các bộ phận của mỗi quan hệ khả hữu r biểu diễn các thực thể, và các thực thể được nhận dạng bằng giá trị của các thuộc tính khoá. Vì vậy hai bộ có giá Trang 19
  20. trị giống nhau ở các thuộc tính trong X phải biểu diễn cho cùng một thực thể và do đó chỉ là một bộ. Cũng cần nhấn mạnh rằng phụ thuộc hàm là những khẳng định về tất cả quan hệ khả hữu của lược đồ quan hệ R. chúng ta không xem xét một quan hệ r cụ thể của lược đồ R nhằm suy ra các phụ thuộc đúng trong R. Thí dụ, nếu r là một tập rỗng thì tất cả các phụ thuộc đều đúng, nhưng nó không đúng trong trường hợp tổng quát, khi gía trị của quan hệ biểu thị bởi R thay đổi. Tuy nhiên, chúng ta có thể xem xét một quan hệ cụ thể của R để khám phá ra một sự phụ thuộc không đúng. Cách duy nhất để xác định đúng các phụ thuộc thích hợp cho một lược đồ R là xem xét cẩn thận xem các thuộc tính mang ý nghĩa gì. Theo cách này, các phụ thuộc thực sự là những khẳng định về thế giới thực, dù không thể chứng minh được, nhưng chúng ta hy vọng rằng chúng sẽ được quản lý, kiểm tra bởi DBMS nếu các nhà thiết kế CSDL đưa ra yêu cầu cho DBMS. Trong quan hệ TT_CUNGCAP (hình II.1) có các phụ thuộc hàm sau: NHACC DIACHI và NHACC, MATHANG GIA Chúng ta có thể nhận xét rằng có nhiều phụ thuộc tầm thường như: NHACC NHACC Và một số ít tầm thường hơn như NHACC, MATHANG DIACHI, GIA Lý do khiến chúng ta tin rằng các phụ thuộc này là hợp lý vì nếu cho trước tên nhà cung cấp và mặt hàng, chúng ta có thể xác định một địa chỉ duy nhất; chúng ta bỏ qua mặt hàng và lấy địa chỉ này, chúng ta cũng có thể xác định được một giá duy nhất, là giá bán sỉ mặt hàng của nhà cung cấp này. Trang 20
  21. Tuy nhiên bạn đọc nên biết rằng phụ thuộc ở trên, không giống như các phụ thuộc khác chúng ta đã nói trong thí dụ này là, nó không đi kèm với một quan hệ cụ thể nào, chúng được nhận ra do chúng ta hiểu rõ ngữ nghĩa của “nhà cung cấp”, “mặt hàng”, “địa chỉ”, và “giá”. Chúng ta hy vọng rằng phụ thuộc này sẽ có ảnh hưởng trong các quan hệ có liên qua đến các thuộc tính đó, nhưng bản chất của ảnh hưởng này thường rất mơ hồ. Chúng ta cũng có thể tự hỏi rằng không biết một phụ thuộc như DIACHI NHACC Có đúng hay không? Xem xét dữ liệu mẫu của hình II.1 chúng ta không tìm thấy có hai bộ nào giống nhau ở địa chỉ lại không giống nhau ở tên, chỉ đơn giản vì không có hai bộ nào có cùng địa chỉ. Tuy nhiên về nguyên tắc, không có gì để loại trừ khả năng hai nhà cung cấp có cùng địa chỉ, vì vậy chúng ta không dám khẳng định phụ thuộc này đúng, dù rằng nó dường như hợp lý trong quan hệ mẫu chúng ta vừa xem. II.2. Một số định nghĩa II.2.1. Phụ thuộc hàm : Cho lược đồ quan hệ xác định trên tập các thuộc tính R = {A1,A2, , An}. Một phụ thuộc hàm trên R là công thức có dạng : f: X Y; với X, Y  R Nếu f: X Y là một phụ thuộc hàm trên R thì ta nói tập thuộc tính Y phụ thuộc vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm tập thuộc tính Y. Trang 21
  22. II.2.2. Thể hiện thỏa phụ thuộc : Với một lược đồ R có thể có nhiều thể hiện (quan hệ) r khác nhau. Đó là một tập gồm các bộ là tình trạng của dữ liệu tại một thời điểm nào đó. Chúng ta nói rằng một quan hệ r thoả phụ thuộc hàm X Y nếu với mỗi hai bộ  và v trong r sao cho: nếu [X] = v[X] thì [Y] = v[Y]. Chú ý rằng giống như mọi câu lệnh “if .then”, khẳng định trên có thể được thoả bởi [X] khác với v[X] hoặc bởi [Y] giống với v[Y]. Nếu r không thoả phụ thuộc X Y thì ta nói r vi phạm phụ thuộc đó. Cho F là một tập các phụ thuộc hàm, ta nói quan hệ r thỏa F, nghĩa là r thỏa tất cả các phụ thuộc hàm trong F. II.2.3. Phụ thuộc hàm định nghĩa trên lược đồ : Nếu với mọi quan hệ r của lược đồ R, r thoả X Y thì ta nói X Y được định nghĩa trên lược đồ R. Giả sử chúng ta khai báo rằng X Y được định nghĩa trên lược đồ R thì chúng ta biết rằng mọi quan hệ r của lược đồ R sẽ thoả X Y. Tuy nhiên nếu X Y không được định nghĩa trên lược đồ R thì một quan hệ r nào đó vẫn có thể ngẫu nhiên thoả X Y hay có thể vi phạm X Y. Cho F là một tập các phụ thuộc hàm, ta nói F được định nghĩa trên lược đồ R, nghĩa là tất cả các phụ thuộc hàm trong F được định nghĩa trên R. Trang 22
  23. II.3. Phụ thuộc hàm hệ quả Giả sử R là một lược đồ quan hệ và A, B, C là một số thuộc tính của nó. Cũng giả sử rằng các phụ thuộc hàm A B và B C được định nghĩa trong R. Chúng ta mong muốn rằng phụ thuộc hàm A C cũng được định nghĩa trong R. Thật vậy, giả sử r là một quan hệ thoả A B và B C , nhưng có hai bộ  và v trong r giống nhau ở thành phần A nhưng không giống nhau ở thành phần C. Thế thì chúng ta phải đặt câu hỏi liệu  và v có giống nhau ở thuộc tính B hay không. Nếu không, r vi phạm phụ thuộc hàm A B. Nếu có, thì bởi vì chúng giống nhau ở B nhưng không giống nhau ở thành phần C, nên r vi phạm B C . Do vậy, r buộc phải thoả A C. Tổng quát, gọi F là tập các phụ thuộc hàm cho lược đồ quan hệ R và gọi X Y là một phụ thuộc hàm. Ta nói X Y là hệ quả của F, và viết là F ╞ X Y, nếu mỗi quan hệ r của R thoả các phụ thuộc trong F thì cũng thoả X Y. Ở trên chúng ta thấy rằng nếu F chứa A B và B C thì A C là hệ quả của F. Nghĩa là {A B, B C ╞ A C} II.4. Bao đóng của các tập phụ thuộc Chúng ta định nghĩa F+, bao đóng (closure), là tập các phụ thuộc hàm hệ quả của F, nghĩa là + F = {X Y  F╞ X Y} Trang 23
  24. Thí dụ II.1: Gọi R=ABC và F= {A B, B C} thế thì bao đóng F+ chứa tất cả các phụ thuộc dạng X Y sao cho : 1. Hoặc X chứa A, chẳng hạn, ABC AB,AB BC, hay A C. 2. Hoặc X chứa B nhưng không chứa A, và Y không chứa A, chẳng hạn BC B, B C hay B , 3. Hoặc X Y là mọt trong ba phụ thuộc C C, C  hay   . Lưu ý : F, F  F+ II.5. Phụ thuộc hàm suy dẫn Ta gọi f là một phụ thuộc hàm được suy dẫn từ tập các phụ thuộc hàm cho trước F nhờ vào một tập các luật dẫn, ký hiệu F ┝ f , nếu tồn tại một chuỗi các phụ thuộc hàm : f1, f2, , fn sao cho fn = f và mỗi fi là một phụ thuộc hàm trong F hay được suy dẫn từ những phụ thuộc hàm j = 1,2, ,i-1 trước đó nhờ vào luật dẫn. Ký hiệu F*, tập các phụ thuộc hàm được suy dẫn từ F nhờ vào các luật dẫn. Điều ta mong muốn là F+ = F* Nói một cách khác, tập các luật dẫn là đúng đắn (hợp lệ) và đầy đủ : - Tập các luật dẫn là đúng đắn nếu và chỉ nếu : * + F  F , nghĩa là : f, nếu F┝ f thì F╞ f Tức là: nếu ta dùng các luật dẫn để suy dẫn ra một phụ thuộc f nào đó từ tập các phụ thuộc hàm F cho trước, thì f cũng là phụ thuộc hàm hệ quả của F. - Tập các luật dẫn là đầy đủ nếu và chỉ nếu : + * F  F , nghĩa là : f, nếu F╞ f thì F┝ f Trang 24
  25. Tức là: nếu f cũng là phụ thuộc hàm hệ quả của F, thì ta có thể dùng các luật dẫn để suy dẫn ra f từ tập các phụ thuộc hàm F. II.6. Các tiên đề cho phụ thuộc hàm Để xác định khoá và hiểu được các phép suy dẫn cho các phụ thuộc hàm nói chung, chúng ta cần tính được F+ từ F, hoặc ít nhất khẳng định được X Y có thuộc F+ hay không nếu biết tập phụ thuộc hàm F và phụ thuộc hàm X Y. Muốn vậy, chúng ta phải có những qui tắc suy dẫn cho biết làm sao có thể suy ra một hay nhiều phụ thuộc từ các phụ thuộc khác. Thực tế chúng ta còn có nhiều hơn thế: chúng ta có một tập các quy tắc suy dẫn đầy đủ, theo nghĩa là từ một tập các phụ thuộc F đã biết, những qui tắc này cho phép chúng ta suy ra được tất cả các phụ thuộc thực sự, nghĩa là những phụ thuộc trong F+.Hơn nữa, những qui tắc này là đúng đắn, theo nghĩa là khi sử dụng chúng, chúng ta không thể suy ra từ F một phụ thuộc sai, nghĩa là một phụ thuộc không thuộc F+. Tập các qui tắc (luật dẫn) này thường được gọi là hệ tiên đề Armstrong (Armstrong’s axioms), do Armstrong đưa ra lần đầu vào năm 1874. Trong những phần dưới đây, giả sử rằng chúng ta đã có một lược đồ quan hệ với tập các thuộc tính U, là tập gồm đầy đủ các thuộc tính của R, và tập các phụ thuộc hàm F chỉ chứa các thuộc tính trong U. Chúng ta có các qui tắc suy dẫn sau: A1: Tính phản xạ (Relexivity) Nếu Y  X  U, thì X Y. Qui tắc này đưa ra những phụ thuộc tầm thường (trivial dependency) là những phụ thuộc mà vế trái được hàm chứa trong vế phải. Những phụ thuộc tầm thường đều đúng trong Trang 25
  26. mọi quan hệ, chúng nói lên rằng việc sử dụng qui tắc này chỉ phụ thuộc vào U, không phải vào F. A2: Tính tăng trưởng (Augmentation). Nếu X Y , và Z  U thì XZ YZ Để ý rằng X,Y và Z là các tập thuộc tính, và XZ là dạng viết tắt của XZ. Một điều quan trọng khác cũng cần phải nhớ rằng phụ thuộc X Y đã cho có thể thuộc F hoặc nó có thể được suy dẫn từ các phụ thuộc trong F bằng cách sử dụng các tiên đề đang mô tả ở đây. A3: Tính bắc cầu (Transitivity) Nếu X Y và Y Z thì X Z Thí dụ II.2: Xét lược đồ quan hệ ABCD với các phụ thuộc hàm A C và B D. Chúng ta có thể chứng minh rằng AB là khoá của ABCD (sự thực nó là khoá duy nhất). Chúng ta có thể chứng minh rằng AB là một khoá bao hàm bằng các bước sau đây: 1. A C(đã cho) 2. AB ABC [tính tăng trưởng của (1) từ AB] 3. B D(đã cho) 4. ABC ABCD [tính tăng trưởng của (3) từ ABC] 5. AB ABCD [tính bắc cầu được áp dụng cho (2) và (4)] Để chứng minh AB là một khoá, chúng ta cũng phải chứng minh rằng bản thân mỗi thuộc tính A và B không thể suy diễn logic ra tất cả các thuộc tính. Chúng ta có thể chứng minh A không phải là khoá bao hàm bằng cách đưa ra một quan hệ thoả các phụ thuộc đã biết (1) và (3) ở trên nhưng không thoả A ABCD và có thể tiến hành tương tự với B. Tuy nhiên chúng ta cũng sẽ xây dựng một thuật toán nhằm Trang 26
  27. kiểm tra xem một tập thuộc tính có phải là khoá hay không, vì thế chúng ta tạm bỏ qua bước này. II.7. Tính đúng đắn của hệ tiên đề Armstrong Tương đối dễ chứng minh rằng hệ tiên đề Armstrong là đúng đắn; nghĩa là chúng chỉ dẫn đến những kết luận đúng. Còn tính đầy đủ khó chứng minh hơn. Chúng có thể được dùng để thực hiện các phép suy diễn có giá trị về các phụ thuộc. Trước tiên chúng ta chứng minh tính đúng đắn của hệ tiên đề Armstrong. II.7.1. Bổ đề II.1: Hệ tiên đề Armstrong là đúng. Nghĩa là nếu X Y được suy dẫn ra từ F nhờ hệ tiên đề này thì phụ thuộc X Y đúng trong mọi quan hệ mà các phụ thuộc của F đúng. Nghĩa là nếu r là một quan hệ thỏa F thì r cũng thỏa X Y. Chứng minh: A1, tiên đề về tính phản xạ rõ ràng là đúng đắn. chúng ta không thể có một quan hệ r với hai bộ giống nhau ở các thành phần trong X nhưng lại không giống nhau ở một tập con nào đó của X. A2, tính tăng trưởng, giả sử rằng chúng ta có quan hệ r thoả X Y, thế thì có hai bộ  và v giống nhau ở các thuộc tính của XZ nhưng khác nhau ở các thuộc tính của YZ. Bởi vì chúng không thể khác nhau ở các thuộc tính của Z,  và v phải khác nhau ở một số thuộc tính của Y. Nhưng vì  và v giống nhau ở phần X nhưng không giống nhau ở phần Y nên mâu thuẫn với giả thiết rằng X Y đúng đối với r. A3, tiên đề về tính bắc cầu, là sự mở rộng của lập luận trước đây về A B và B C suy ra A C. Chúng tôi để phần này lại cho bạn đọc tự chứng minh. Trang 27
  28. II.8. Các qui tắc suy dẫn bổ sung Có nhiều qui tắc được suy ra từ hệ tiên đề Arsmtrong. Trong bổ đề kế tiếp, chúng ta trình bày ba trong số các qui tắc này. Bởi vì chúng ta đã chứng minh tính đúng đắn của A1,A2,và A3 nên chúng ta được quyền sử dụng chúng trong các phép chứng minh sau. II.8.1. Bổ đề II.2 : a) Qui tắc hợp (The union rule) Nếu X Y và X Z thì X YZ. b) Qui tắc giả bắc cầu (The pseudotransitivity rule) Nếu X Y và WY Z thì WX Z. c) Qui tắc phân rã (The decomposition rule) Nếu X Y và Z  Y thì X Z. Chứng minh : a) Chúng ta đã có X Y nên dùng qui tắc tăng trưởng với X chúng ta có X XY . Chúng ta cũng có X Z nên suy ra XY YZ. Nhờ tính chất bắc cầu, từ X XY và XY YZ suy ra X YZ . b) Sử dụng tính tăng trưởng X Y thành WX WY. Bởi vì chúng ta đã có WY Z, tính bắc cầu cho phép suy ra WX Z. c) Từ tính phản xạ ta có Y Z, nên nhờ tính bắc cầu ta có X Z. Một hệ quả quan trọng của các qui tắc hợp và phân rã là nếu A1, An là các thuộc tính thì X A1, An đúng nếu và chỉ nếu X A1 đúng với mọi i. Vì vậy chúng ta chỉ cần sử dụng các phụ thuộc mà vế phải chỉ có một thuộc tính duy Trang 28
  29. nhất. Chúng ta sẽ thảo luận vấn đề này chi tiết hơn khi phân tích về “phủ cực tiểu” của các phụ thuộc hàm. II.9. Bao đóng của tập thuộc tính Trước khi chứng minh tính đầy đủ, chúng ta cần định nghĩa bao đóng (closure) của một tập các thuộc tính ứng với một tập phụ thuộc hàm. Gọi F là tập phụ thuộc hàm trên tập thuộc tính U. Cho X là một tập con của U. Ta gọi bao đóng của X ( ứng với F), ký + + hiệu X F (hay X ), là tập các thuộc tính A sao cho X A có thể suy dẫn ra từ F nhờ hệ tiên đề Arsmtrong. + * X F = { A / X A F } Điểm cốt lõi của bao đóng của tập thuộc tính là nó cho phép chúng ta khẳng định rằng một phụ thuộc X Y có thể suy ra từ F bằng hệ tiên đề Arsmtrong được hay không . Bổ đề sau đây khẳng định điều này. II.9.1. Bổ đề II.3 : X Y suy ra được từ một tập phụ thuộc F đã cho bằng cách sử dụng hệ tiên đề Arsmtrong nếu và chỉ nếu Y  X+ (ở đây bao đóng của X được lấy ứng với F). Chứng minh: Đặt Y=A1, An cho tập các thuộc tính A1, An và giả sử + + Y  X ; . Theo định nghĩa của X ,X Ai , được suy ra từ hệ tiên đề Arsmtrong với mọi i. Bằng qui tắc hợp ta có X Y đúng. Ngược lại, giả sử rằng X Y được suy ra từ hệ tiên đề này. Đối với mỗi i, X Ai đúng theo qui tắc phân rã, vì vậy Y  X+. Trang 29
  30. II.10. Tính đầy đủ của hệ tiên đề Armstrong Bây giờ chúng ta đã sẳn sàng để có thể chứng minh tính đầy đủ (completeness) của hệ tiên đề Arsmtrong. Chúng ta sẽ chứng minh rằng nếu F là tập các phụ thuộc đã cho, và không thể suy ra X Y đúng bằng hệ tiên đề Arsmtrong thì phải có một quan hệ trong đó tất cả các phụ thuộc của F đều đúng nhưng X Y không đúng; nghĩa là không khẳng định logic X Y. II.10.1. Định lý II.1 : hệ tiên đề Arsmtrong là đúng đắn và đầy đủ. Chứng minh: Tính đúng đắn đã được chứng minh qua Bổ đề II.1, vì vậy chúng ta chỉ còn phải chứng minh tính đầy đủ. Gọi F là tập các tập các phụ thuộc trên tập thuộc tính U và giả sử X Y không thể suy ra được từ hệ tiên đề này. Xét một quan hệ r có hai bộ được trình bày trong Hình II.3. Trước tiên chúng ta chứng minh rằng tất cả các phụ thuộc trong F đều được thoả bởi r. Về trực quan, một phụ thuộc V W bị r phạm cho phép chúng ta “đẩy” X+ vượt quá giá trị mà nó có khi được cho tập các phụ thuộc F. Giả sử V W thuộc F nhưng không được thoả bởi r. Thế thì V  X+, nếu không thì hai bộ của r không giống nhau ở các thuộc tính của V, vì vậy không vi phạm V W. Cũng vậy W không thể là một tập con của X+.Bởi vì V  X+, nên X V được suy ra từ hệ tiên đề Armstrong nhờ Bổ đề II.3. Phụ thuộc V W thuộc F, vì thế do tính bắc cầu chúng ta có X W. Do tính phản xạ, W A, vậy do tính bắc cầu X A được suy ra từ các tiên đề này. Nhưng nếu vậy thì theo định nghĩa của bao đóng. A thuộc X+, mâu thuẩn với giả thiết. Do vậy có thể kết luận rằng r thoả mọi phụ thuộc V W trong F. Trang 30
  31. Các thuộc tính của X+ Các thuộc tính khác 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 . 0 - Hình II.3 - một quan hệ chứng minh F không khẳng định logic X Y - Bây giờ chúng ta chứng minh rằng X Y không được thoả bởi r. Giả sử rằng nó được thoả. Hiển nhiên là X  X+ nên suy ra rằng Y  X+ , nếu không hai bộ của r sẽ có các giá trị trong X giống nhau nhưng các giá trị trong Y lại không giống nhau. Thế nhưng bổ đề II.3 lại khẳng định rằng X Y có thể được suy ra từ các tiêu đề, là điều trái với giả thiết là X Y không thể suy ra từ các tiên đề. Vì thế X Y không được thoả bởi r, mặc dù mỗi phụ thuộc F đều thoả. Chúng ta kết luận rằng khi X Y không suy ra được từ tập phụ thuộc F bằng hệ tiên đề Armstrong, X Y cũng không là hệ quả của F. Điều này khẳng định rằng hệ tiên đề này là đầy đủ. Định lý II.1 có một số hệ quả sau: Như đã đề cập trong phần II.5 và kết quả của định lý II.1 ta có F+ = F* . Chúng ta đã định nghĩa X+ là tập các thuộc tính sao cho X A được suy dẫn từ tập các phụ thuộc F đã cho bằng cách dùng các tiên đề này. Bây giờ chúng ta có một định nghĩa tương đương cho X+, đó là một tập các thuộc tính A sao cho X A là hệ quả của F. + * X F = { A / X A F } = { A / X A F+ } Một hệ quả khác là mặc dù chúng ta định nghĩa F+ là tập các phụ thuộc là hệ quả của F, chúng ta có thể xem F+ là tập các phụ thuộc được suy dẫn từ F bằng hệ tiên đề Armstrong. Trang 31
  32. + F = {X Y  F╞ X Y} = {X Y  F┝ X Y} II.10.2. Bài toán thành viên Cho trước tập phụ thuộc hàm F và f : X Y là một phụ thuộc hàm mới được nhận diện. Bài tóan đặt ra là f có phải là thành viên của F, nghĩa là f có thuộc bao đóng của F không ? f là thành viên của F  f F+  f F* do F+ = F* (định lý II.1)  Y  X+ do bổ đề II.3 Cho nên để giải quyết bài tóan thành viên, ta chỉ cần tính X+ đối với F, sau đó xét xem Y  X+ ? II.11. Tính các bao đóng Rõ ràng là việc tính F+ cho một tập phụ thuộc F nói chung tốn rất nhiều thời gian, đơn giản là vì tập các phụ thuộc của F+ có thể rất lớn dù rằng tập phụ thuộc F nhỏ. Chẳng hạn xét tập phụ thuộc: F = (A B1, A B2 ., A Bn ) Thế thì F+ bao gồm tất cả các phụ thuộc A Y, trong n đó Y là một tập con của (B1, B2 ., Bn ). Bởi vì có có đến 2 tập Y như thế, chúng ta không hy vọng liệt kê hết được tập F+ ngay cả với kích thước n vừa phải. Ngược lại, việc tính X+ cho tập các thuộc tính X thì không khó; chi phí thuật toán này tỷ lệ với chiều dài của tất cả các phụ thuộc trong F. Nhờ Bổ đề II.3 và định lý II.1 về tính đúng đắn và đầy đủ của hệ tiên đề Armstrong, chúng ta có thể biết được X Y có thuộc F+ hay không bằng cách tính X+ ứng với F. Cách tính X+ đơn giản như sau. Trang 32
  33. II.11.1. Thuật toán II.1: tính các bao đóng một tập thuộc tính ứng với môt tập phụ thuộc hàm. NHẬP: Tập thuộc tính hữu hạn U, tập phụ thuộc hàm F trên U, và tập X  U. XUẤT: X+, bao đóng của X ứng với F. PHƯƠNG PHÁP: chúng ta tính chuỗi các tập thuộc tính X(0),X(1), . bằng các qui tắc: 1. X(0) chính là X. 2. X(i+1) là hợp của X(i) với tập các thuộc tính A sao cho có một phụ thuộc Y Z thuộc F, A thuộc Z và Y  X(i). Bởi vì X= X(0)  X(1)  .  X(i) U, và U là hữu hạn, cuối cùng chúng ta phải đạt đến một trị số i sao cho X(i) =X(i+1).Bởi vì mỗi X(j+1) chỉ được tính theo X(j) , suy ra rằng X(i) =X(i+1) =X(i+2) Chúng ta không cần phải tính tiếp khi đã phát hiện ra rằngX(i) =X(i+1) , và có thể chứng minh rằng X+ chính là X(i) với trị số i này. Trang 33
  34. Thí dụ II.3: Gọi F là tập gồm 8 phụ thuộc sau: AB C D EG C A BE C BC D CG BD ACD B CE AG Và cho X= BD. Hãy tính X+ Để áp dụng Thuật toán II.1, khởi đầu chúng ta đặt X(0) = BD. Muốn tính X(1) , chúng ta tìm các phụ thuộc có vế phải là B,D hoặc BD. Chỉ có một phụ thuộc D EG, vì thế chúng ta nối E và G với X(1), kết quả là X(1) = BDEG. Đối với X(2) chúng ta tìm các vế trái được chứa trong X(1) và tìm được hai phụ thuộc D EG và BE C. Vì vậy X(2) =BCDEG. Tiếp tục với X(3), chúng ta tìm các vế trái được chứa trong BCDEG và tìm ra các phụ thuộc mới C A, BC D, CG BD, và CE AG. Vì vậy X(3) = ABCDEG, là tập hợp gồm tất cả mọi thuộc tính đã cho. Do đó không có gì ngạc nhiên là X(3) = X(4) = . Do vậy (BD)+ = ABCDEG. Bây giờ chúng ta phải chứng minh tính đúng đắn của Thuật toán II.1. Chúng ta có thể dễ dàng chứng minh được rằng mỗi thuộc tính được đặt vào một tập X(j) đều thuộc X+ , nhưng chứng minh rằng mỗi thuộc tính trong X+ đều được đặt trong một X(j) nào đó thì khó hơn. Trang 34
  35. II.11.2. Định lý II.2: Thuật toán II.1 tính đúng X+. Chứng minh: Trước tiên chúng ta chứng minh bằng qui nạp trên j rằng nếu A được đặt trong X(j ) trong khi “chạy” thuật toán II.1 thì A thuộc X+; nghĩa là nếu A thuộc tập X(j ) được trả về bởi thuật toán II.1 thì A thuộc X+. Bước cơ sở: j = 0. Thế thì A thuộc X, vì vậy do tính phản xạ, X A. Qui nạp: Với j > 0 và giả sử rằng X(j-1 ) chỉ chứa các thuộc tính X+. Giả sử A được đặt trong X(j ) do A thuộc Z, Y Z thuộc F, và Y  X(j-1 ) .Bởi vì Y  X(j-1 ) chúng ta biết rằng Y  X+ theo giả thiết qui nạp . Vì vậy X Y theo Bổ đề II.3. Nhờ tính chất bắc cầu, X Y và Y Z suy ra X Z. Nhờ tính chất phản xạ, Z A nên X A lại do tính bắc cầu. Vì vậy A thuộc X+. Bây giờ chúng ta chứng minh phần đảo: nếu A thuộc X+ thì A là phần tử của tập được trả về bởi thuật toán II.1. Giả sử A thuộc X+ nhưng A không thuộc tập X(j ) được trả về bởi Thuật toán II.1. Chú ý rằng X(i ) = X(i+1 ) bởi vì đó là điều kiện để Thuật toán II.1 kết thúc. Xét quan hệ r tương tự như Hình II.3: r có hai bộ giống nhau ở các thuộc tính của X(i ) nhưng khác nhau ở tất cả các thuộc tính khác. Chúng ta khẳng định rằng r thoả F. Thật vậy, gọi U V là một phụ thuộc trong F bị vi phạm bởi r. Thế thì U  X(i ) và V không thể là một tập con của X(i ) nếu xảy ra vi phạm (lập luận tương tự như trong phần chứng minh Định lý II.1). Vì vậy không thể bằng với X(i ) như đã giả định. Trang 35
  36. Do đó, quan hệ r cũng phải thoả X A. Lý do là A được giả thiết là thuộc X+ , và vì thế X A được suy ra từ F bởi hệ tiên đề Armstrong. Vì các tiên đề này là đúng đắn nên bất kỳ quan hệ nào thoả F cũng thoả X A. Nhưng cách duy nhất X A có thể đúng trong r là A thuộc X(i ) bởi vì nếu không thì hai bộ của r, chắc chắn rằng giống nhau ở X, sẽ không giống nhau ở A và vì vậy vi phạm X A. Chúng ta kết luận rằng A thuộc tập X(i ) được trả về bởi Thuật toán II.1. II.12. Tính tương đương của các tập phụ thuộc Định nghĩa : Gọi F và G là các tập phụ thuộc hàm. Ta nói F và G là tương đương, ký hiệu F ≡ G , nếu: F+ = G+ Khi F và G tương đương, ta nói F phủ G, hay G phủ F Bổ đề II.4: F và G tương đương nếu và chỉ nếu G là tập con của F+ và F là tập con của G+ F ≡ G  G  F+ và F  G+ Chứng minh: a. Điều kiện đủ: giả thiết F tương đương G Lưu ý (i): với mọi tập phụ thuộc hàm G, ta có G  G+ a.1. phải chứng minh G  F+ hay g G ==> g F+ Gọi g là một phụ thuộc hàm bất kỳ thuộc G, ta có g thuộc G+ (do Lưu ý (i) nên G  G+). Hơn nữa ta cũng có G  F+ (do giả thiết F tương đương với G). Nên g cũng thuộc F+ . Trang 36
  37. a.2. phải chứng minh F  G+ hay f F ==> f G+ Tương tự chứng minh trên. b. Điều kiện cần: giả thiết G  F+ và F  G+ Phải chứng minh F tương đương G hay F+ = G+ Lưu ý (ii):với mọi tập phụ thuộc hàm G,ta có (G+)+ = G+ Lưu ý (iii):với các tập phụ thuộc hàm F,G bất kỳ, ta có nếu F  G thì F+  G+ b.1. ta chứng minh G+  F+ Do giả thiết G  F+ và do lưu ý (ii) nên G+ (F+)+ Hơn nữa do lưu ý (iii) ta có (F+)+ = (F+)+ nên G+ F+ b.2. ta chứng minh F+  G+ Tương tự chứng minh trên. b.3. do (b.1) và (b.2) ta có F+ = G+ Nhận xét : Áp dụng kết quả của bổ đề II.4, chúng ta dễ dàng kiểm tra tính tương đương của F và G theo các bước sau: Với mỗi phụ thuộc Y Z thuộc F, kiểm tra xem Y Z có thuộc G+ hay không bằng cách dùng thuật toán II.1 để tính Y+ ứng với G rồi kiểm chứng lại xem có phải Z  Y+ hay không . Nếu một phụ thuộc Y Z nào đó thuộc F nhưng không thuộc G+ thì chắc chắn F+ G+ .Nếu mỗi phụ thuộc của F đều thuộc G+ thì ta có được kết quả F  G+. Để chứng minh rằng mỗi phụ thuộc trong G cũng thuộc F+ chúng ta sử dụng phương pháp tương tự và nếu được kết quả G  F+. Áp dụng bổ đề II.4 ta có F ≡ G. Trang 37
  38. II.13. Phủ cực tiểu Đối với một tập phụ thuộc đã cho, chúng ta có thể tìm một tập tương đương có một số đặc tính hữu ích. Một đặc tính đơn giản và quan trọng là các vế phải của những phụ thuộc này được tách thành những thuộc tính độc nhất. II.13.1. Bổ đề II.5 Mỗi tập phụ thuộc F tương đương với một tập phụ thuộc G trong đó các vế phải không có quá một thuộc tính. Chứng minh: Gọi G là tập phụ thuộc X A sao cho với một phụ thuộc X Y thuộc F, A thuộc Y. Thế thì X A được suy ra từ X Y bằng qui tắc phân rã. Do đó G  F+ . + Nhưng ta cũng có F  G bởi vì nếu Y = A1 .An thì X Y được suy ra từ X A1 ,X An nhờ qui tắc hợp. Vì vậy F và G tương đương Rõ ràng chúng ta cần một lý thuyết thiết kế lược đồ CSDL đưa ra nhiều hạn chế hơn là chỉ yêu cầu vế phải chỉ có một thuộc tính. II.13.2. Tập phụ thuộc cực tiểu Một tập phụ thuộc F là cực tiểu nếu: 1. Vế phải của mỗi phụ thuộc trong F chỉ có một thuộc tính. 2. Không tồn tại bất kỳ một phụ thuộc X A nào trong F mà tập F - {X A} tương đương với F. 3. Không tồn tại bất kỳ một phụ thuộc X A nào trong F sao cho có một tập con thực sự Z của X mà (F - {X A})  {Z A} tương đương với F. Trang 38
  39. Về trực quan, (2) bảo đảm rằng không có phụ thuộc nào trong F là dư thừa. Chúng ta có thể kiểm tra xem X A có dư thừa hay không bằng cách tính X+ ứng với F - {X A} rồi so sánh kết quả với X+ ứng với F. Điều kiện (3) bảo đảm rằng không có thuộc tính nào ở vế trái là dư thừa. Chúng ta có thể kiểm tra các phụ thuộc dư thừa ở vế trái như sau: Thuộc tính B trong X đối với phụ thuộc X A là dư thừa nếu và chỉ nếu A thuộc (X - {B})+ khi bao đóng được lấy ứng với F. Bởi vì theo (1), mỗi vế phải chỉ có một thuộc tính nên chắc chắn rằng không có thuộc tính nào ở vế phải là dư thừa. Thí dụ : Tập phụ thuộc F = {AB C; C DE} không phải là tập phụ thuộc cực tiểu vì phụ thuộc hàm C DE có vế phải gồm 2 thuộc tính (vi phạm điều kiện 1) Tập phụ thuộc F = {AB C; C D; AB D} thỏa điều kiện 1 nhưng vi phạm điều kiện 2 vì ta có thể bỏ phụ thuộc hàm AB D. II.13.3. Phủ cực tiểu Cho trước tập phụ thuộc hàm F. Một tập phụ thuộc hàm G được gọi là phủ cực tiểu (minimal cover) của F nếu: - G là một tập phụ thuộc cực tiểu - và G tương đương F (G phủ F). Trang 39
  40. II.13.4. Định lý II.3 Mỗi tập phụ thuộc F đều có ít nhất một phủ cực tiểu. Chứng minh: Nhờ Bổ đề II.5, chúng ta có thể giả sử rằng các vế phải trong F đều có một thuộc tính. Chúng ta sẽ tìm kiếm lặp đi lặp lại các vi phạm điều kiện (2) [các phụ thuộc dư thừa] và điều kiện (3) [các thuộc tính dư thừa ở vế trái], và sửa đổi tập phụ thuộc cho thích ứng. Bởi vì mỗi khi sửa đổi, chúng ta xoá một phụ thuộc (2) hoặc xoá một thuộc tính trong một phụ thuộc (3), quá trình này không thể tiếp tục mãi, cuối cùng chúng ta sẽ thu được một tập phụ thuộc không vi phạm các điều kiện (1), (2), hoặc (3). Đối với điều kiện (2), chúng ta xét mỗi phụ thuộc X Y trong tập phụ thuộc hiện tại F, và nếu F - {X Y }tương đương với F thì xoá X Y ra khỏi F. Chú ý rằng thứ tự xét các phụ thuộc có thể loại bỏ các tập phụ thuộc khác nhau. Chẳng hạn với tập F: A BA C B AC A B C Chúng ta có thể loại bỏ cả B A lẫn A C hoặc có thể loại bỏ B C nhưng không thể loại bỏ cả ba được. Đối với điều kiện (3), chúng ta xét mỗi phụ thuộc A1 .Ak B trong tập phụ thuộc F, và mỗi thuộc tính Ai ở vế trái theo một thứ tự nào đó. Nếu (F - {A1 Ai-1 Ai Ai+1 .Ak B} )  {Ai Ai-1Ai+1 .Ak B} tương đương với F thì xoá Ai ra khỏi vế trái của A1 .Ak B. Một lần nữa, thứ tự các thuộc tính bị loại bỏ có thể ảnh hưởng đến kết quả. Trang 40
  41. Chẳng hạn cho tập phụ thuộc AB CA BB A Chúng ta có thể loại bỏ A hoặc B ra khỏi AB C nhưng không thể loại cả hai. Bạn đọc hãy chứng minh rằng khi loại bỏ tất cả các vi phạm của (3) trước rồi đến tất cả các vi phạm của (2), chúng ta sẽ có được phủ cực tiểu nhưng thực hiện ngược lại thì không chắc. Thí dụ II.4: Xét tập phụ thuộc F của Thí dụ II.3. Nếu dùng thuật toán của Bổ đề II.5 để tách vế phải, chúng ta thu được: AB CD E CG B C AD G CG D BC D BE C CE A ACD B CE G Rõ ràng CE A là dư thừa bởi vì nó được suy ra từ C A. CG B cũng dư thừa do các phụ thuộc CG D, C A và suy ra CG B . Ngoài ra không còn phụ thuộc nào dư thừa nữa. Tuy nhiên, chúng ta có thể thay ACD B bằng CD B, vì có thể suy ra CD B từ ACD B và C A. Bây giờ không còn rút gọn các phụ thuộc được nữa. Kết quả là một phủ cực tiểu của F được trình bày như trong Hình II.4 (a). Một phủ cực tỉểu khác, được xây dựng từ F bằng cách loại bỏ các phụ thuộc CE A,CG D, và ACD B được trình bày trong Hình II.4 (b). Chú ý rằng hai phủ cực tiểu này có số lượng phụ thuộc khác nhau. Trang 41
  42. AB C AB C C AC A BC D BC D CD BD E D ED G D G BE C BE C CG B CG D CE G CE G (a) (b) - Hình II.4 – Hai phủ cực tiểu – II.14. Tính chất của phụ thuộc hàm Cho lược đồ quan hệ R xác định trên tập thuộc tính U. Cho f : X Y là một phụ thuộc hàm trên U. Gọi r là một quan hệ của R. Ta có các tính chất sau: II.14.1. Tính chiếu Lấy W  U sao cho X  W và Y  W <> 0 ta có : Nếu r thỏa X Y thì r[W] cũng thỏa X (Y  W) Thí dụ: Cho R(ABC), với U=ABC, gọi r là một quan hệ của R. Ta có : Nếu r thỏa f : A BC thì r[AB] cũng thỏa f : A B Ở đây ta lấy W = AB r = (A B C) r[AB] = (A B) a1 b1 c1 a1 b1 a2 b1 c2 a2 b1 Bạn hãy chứng minh tính chất trên Trang 42
  43. II.15. Ứng dụng khái niệm phụ thuộc hàm vào khóa Khi nói đến các tập thực thể, chúng ta đã giả sử rằng tồn tại một khoá, đó là tập các thuộc tính xác định duy nhất một thực thể. Cũng có một khái niệm tương tự cho các quan hệ có các phụ thuộc hàm. Ta có định nghĩa về khóa sau. II.15.1. Định nghĩa khóa : dùng phụ thuộc hàm Cho R là một lược đồ quan hệ với các thuộc tính A1A2 An và cho trước tập các phụ thuộc hàm F. Gọi X là một tập con của A1A2 An chúng ta nói X là một khoá của (R,F) nếu: + (i) Phụ thuộc hàm X A1A2 An thuộc F . Nghĩa là có sự phụ thuộc của tất cả các thuộc tính vào tập thuộc tính X được cho trước hoặc được suy ra từ những phụ thuộc đã cho, và (ii)Không có tập Y nào là tập con thực sự của X, mà có + phụ thuộc Y A1A2 An thuộc F . Thí dụ : Trong Thí dụ II.1. Gọi R=ABC và F= {A B, B C} Ta thấy chỉ có một khoá duy nhất là A, bởi vì A ABC thuộc F+ và không có bất kỳ tập thuộc tính X nào không chứa A mà X ABC đúng. II.15.2. Thuật toán tìm khoá : vét cạn Từ định nghĩa trên, ta có thể xây dựng một thuật toán tìm khóa của một lược đồ quan hệ một cách hệ thống hơn. Đã có nhiều thuật toán được xây dựng, tư tưởng chính của những thuật toán đó dựa trên các bước sau: Trang 43
  44. NHẬP: tập các thuộc tính R, tập các phụ thuộc hàm F XUẤT: các khóa của (R,F) PHƯƠNG PHÁP: 1. Xây dựng các tập con khác rỗng của R 2. Với mỗi tập K  R đã xây dựng ở bước 1: Nếu K thỏa điều kiện (i) Thì K là một siêu khóa Cuối nếu Cuối mọi Gọi S là tập các siêu khóa 3. Tìm siêu khóa nhỏ nhất (điều kiện ii) Với mỗi tập K S đã xây dựng ở bước 1: Nếu  K’ S sao cho K’ K (K’ K) Thì loại bỏ K khỏi S Cuối nếu Cuối mọi S chính là tập chứa các khóa của (R,F) Trang 44
  45. II.15.3. Thuật toán tìm khoá dựa trên đồ thị Vấn đề của thuật toán trên là kết quả của bước 1 có thể là một tập rất lớn các tập con của R. Nếu R có n thuộc tính thì số lượng các tập con khác rỗng của R là 2n. Do đó cần giới hạn số tập con cần khảo sát dựa vào các tính chất sau: a) Mỗi nút của đồ thị là tên một thuộc tính của R b) Mỗi phụ thuộc hàm được thể hiện trên 1 cung có hướng của đồ thị c) Nút lá: B là nút (thuộc tính) lá nếu: - tồn tại một phụ thuộc hàm thuộc F sao cho B xuất hiện bên vế phải của phụ thuộc hàm nầy. - và không tồn tại một phụ thuộc hàm thuộc F sao cho B xuất hiện bên vế trái của phụ thuộc hàm nầy. Trên đồ thị phụ thuộc hàm, nút thuộc tính lá có cung vào mà không có cung ra. Nhận xét: Thuộc tính lá không xuất hiện trong khóa a) Nút gốc: A là nút (thuộc tính) gốc nếu: - không tồn tại một phụ thuộc hàm thuộc F sao cho A xuất hiện bên vế phải của phụ thuộc hàm nầy. Trên đồ thị phụ thuộc hàm, nút thuộc tính gốc không có cung vào (và không bắt buộc phải có cung ra). Nhận xét: mọi thuộc tính gốc phải xuất hiện trong mọi khóa Như vậy khóa của lược đồ quan hệ phải bao phủ tập các nút gốc, đồng thời không chứa bất kỳ nút lá nào của đồ thị. Trang 45
  46. CÁC BƯỚC: 1. Vẽ đồ thị phụ thuộc hàm và xác định các tập: - GOC: tập gồm các nút gốc - LA : tập gồm các nút lá - TG = R - (GOC  LA) : tập gồm các nút trung gian 2. Xuất phát từ tập X=GOC, ta tính bao đóng X+ dựa vào các phụ thuộc hàm trong F. Nếu X+ = R Thì : (R,F) chỉ có duy nhất 1 khóa là GOC Ngược lại :bổ sung từng tập con klhác rỗng của tập TG vào X (theo thứ tự từ tập gồm 1 phần tử, 2 phần tử, ). Tính X+ cho tới khi tìm được X sao cho X+ = R Cuối nếu Trang 46
  47. III. PHỤ THUỘC ĐA TRỊ III.1. Phụ thuộc đa trị Trong những phần trước chúng ta đã giả thiết rằng chỉ có một loại phụ thuộc là phụ thuộc hàm. Thật ra có nhiều loại phụ thuộc, và ít nhất có một loại phụ thuộc rất thường gặp trong thế giới thực là phụ thuộc đa trị (multivalued dependency). III.1.1. Định nghĩa Giả sử chúng ta có một lược đồ quan hệ R , và X, Y là các tập con của R. Về trực quan, ta nói rằng X Y, đọc là “X đa xác định Y” hoặc “có một phụ thuộc đa trị của Y vào X” , nếu với những giá trị đã biết cho các thuộc tính của X, tồn tại một tập gồm zero hoặc nhiều giá trị cho các thuộc tính của Y, và tập giá trị Y này không liên hệ gì với những giá trị của các thuộc tính trong R - X - Y. Về hình thức, ta nói X Y là một phụ thuộc đa trị được định nghĩa trên R nếu với r là một quan hệ của R, và q1 và q2 là hai bộ trong r, với q1[X] = q2[X] (nghĩa là q1 và q2 giống nhau ở các thuộc tính của X) thì r cũng chứa các bộ q3 và q4 , trong đó : 1. q3[X] = q4[X] = q1[X] = q2[X] 2. q3[Y] = q1[Y] và q3[Z] = q2[Z] ; với Z=R - X - Y 3. q4[Y] = q2[Y] và q4[Z] = q1[Z] Trang 47
  48. Nghĩa là chúng ta có thể trao đổi các giá trị Y của q1 và q2, thu được hai bộ mới q3 và q4 thuộc r. Chú ý rằng chúng ta không giả thiết X và Y là tách biệt trong định nghĩa trên. Lưu ý: ta có thể loại bỏ mệnh đề (3). Tồn tại của bộ q4 suy ra từ bộ q3 khi đảo vị trí của q1 và q2 trong định nghĩa. Thí dụ II.6: Chúng ta hãy xét lược đồ gồm các thuộc tính CTHRSG. Hình II.5 trình bày một quan hệ của lược đồ này. Ở trường hợp đơn giản này chỉ có một khóa học và hai sinh viên, nhưng có nhiều đặc điểm mà chúng ta hy vọng sẽ đúng trong mọi quan hệ của lược đồ. Một khoá học (lớp học, Course) có thể học trong nhiều buổi (giờ học, Hours), mỗi buổi ở một phòng (Room) khác nhau. Mỗi sinh viên (Student) có một bộ cho mỗi lớp (khóa học) và mỗi buổi học của lớp đó. Điểm (Grade) được lập lại ở mỗi bộ. C T H R S G CS101 Minh T.hai 9 P.222 Dung B+ CS101 Minh T.tu 9 P.333 Dung B+ CS101 Minh T.sau 9 P.222 Dung B+ CS101 Minh T.hai 9 P.222 Lan C CS101 Minh T.tu 9 P.333 Lan C CS101 Minh T.sau 9 P.222 Lan C -Hình II.5 Một quan hệ mẫu cho lược đồ CTHRSG- Vì thế trong trường hợp tổng quát, chúng ta hy vọng rằng phụ thuộc đa trị C HR đúng: nghĩa là có một tập các cặp giờ học-phòng kèm với mỗi khoá học và không có liên quan gì với những thuộc tính khác. Chẳng hạn trong định Trang 48
  49. nghĩa hình thức của phụ thuộc đa trị, chúng ta có thể xem X Y là C HR và chọn. q1 = CS101, Minh, T.hai 9, P.222, Dung, B+ q2 = CS101, Minh, T.tu 9, P.333, Lan , C nghĩa là q1 là bộ đầu tiên, q2 là bộ thứ năm trong Hình II.5. Thế thì chúng ta hy vọng rằng có thể trao đổi q1[HR] = (M9, 222) với q2[HR] = (W9, 333) để thu được hai bộ q3 = CS101, Minh, T.hai 9, P.222, Lan , C q4 = CS101, Minh, T.tu 9, P.333, Dung, B+ Nhìn thoáng qua, Hình II.5 cho thấy rằng q3 và q4 thực sự thuộc r , tương ứng là bộ thứ tư và thứ hai. Cần phải nhấn mạnh rằng C HR đúng không phải do nó đúng trong quan hệ của Hình II.5. Nó đúng bởi vì một khoá học c bất kỳ, nếu nó được dạy vào giờ h1 trong phòng 1 với giảng viên t1 và sinh viên s1 có điểm g1, và nó cũng được dạy vào giờ h2 trong phòng 2 với giảng viên t2 và sinh viên s2 có điểm g2, thì nó cũng được dạy vào giờ h1 trong phòng 1 với giảng viên t2 và sinh viên s2 có điểm g2. Cũng chú ý rằng C H không đúng, và C R cũng thế. Thật vậy, hãy xét quan hệ r của Hình II.5 với các bộ q1 và q2 ở trên. Nếu C H đúng, chúng ta hy vọng rằng sẽ tìm được bộ CS101, Minh , T.tu 9, P.333, Lan , C trong r, mà chúng ta không tìm thấy. Cũng nhận xét tương tự cho C R. Trang 49
  50. Tuy nhiên còn có một số phụ thuộc đa trị khác như: C SG và HR SG. Ngoài ra cũng có những phụ thuộc đa trị tầm thường như HR R. Bạn hãy tự kiểm chứng. III.2. Các tiên đề cho phụ thuộc hàm, phụ thuộc đa trị Bây giờ chúng ta sẽ trình bày một tập các tiên đề đúng đắn và đầy đủ dùng để suy diễn về tập phụ thuộc hàm và tập phụ thuộc đa trị trên tập thuộc tính U. Ba tiên đề đầu tiên chính là các tiên đề Armstrong cho phụ thuộc hàm được lập lại ở đây. A1: Tính phản xạ phụ thuộc hàm. Nếu Y  X  U thì X Y A2: Tính tăng trưởng của phụ thuộc hàm. Nếu X Y và Z  U thì XZ YZ A3: Tính bắc cầu của phụ thuộc hàm. Nếu X Y và Y Z thì X Z Ba tiên đề sau áp dụng cho các phụ thuộc đa trị. A4: Tính bù của phụ thuộc đa trị. Nếu X Y} thì X (U - X – Y) A5: Tính tăng trưởng của phụ thuộc đa trị. Nếu X Y và V  W thì WX VY A6: Tính bắc cầu của phụ thuộc đa trị: Nếu X Y và Y Z thì X (Z – Y) Cũng nên so sánh A4-A6 với A1-A3. Tiên đề A4, là qui tắc bù, không có đối tác ở phụ thuộc hàm. Tiên đề A1, là tính phản xạ, dường như cũng không có đối tác tương ứng ở phụ thuộc đa trị, nhưng có thể suy ra X Y khi YX từ A1 và tiên đề A7 (bên dưới) là nếu có phụ thuộc X Y thì cũng có phụ thuộc X Y. A6 bị hạn chế nhiều hơn so với đối tác của nó là A3. Khẳng định tổng quát hơn, X Y và Y Z suy ra Y Z. Chẳng hạn trong Thí dụ II.6, C HR đúng, Trang 50
  51. và chắc chắn HR H cũng đúng, nhưng C H sai. Bù lại, A5 mạnh hơn so với tiên đề tăng trưởng tương ứng là A2. Chúng ta có thể thay A2 bằng: X Y và VW suy ra WX VY, nhưng đối với phụ thuộc hàm, qui tắc này dễ dàng chứng minh các tiên đề A1, A2 và A3. Hai tiên đề cuối cùng liên quan đến phụ thuộc hàm và phụ thuộc đa trị. A7: Nếu X Y thì X Y A8: Nếu X Y và Z  Y, và tập W tách biệt với Y mà chúng ta có W Z thì X Z III.3. Tính đúng đắn và đầy đủ của các tiên đề Chúng ta không chứng minh rằng các tiên đề A1-A8 là đúng đắn và đầy đủ. Thực ra, chúng ta sẽ chứng minh rằng một số tiên đề là đúng đắn, nghĩa là chúng được suy ra từ định nghĩa của phụ thuộc hàm và phụ thuộc đa trị, dành cho bạn đọc chứng minh tính đúng đắn của các tiên đề còn lại, cũng chứng minh rằng mọi suy diễn có giá trị đều có thể thực hiện bằng cách sử dụng các tiên đề này (Tính đầy đủ của các tiên đề). Chúng ta sẽ chứng minh tiên đề A6, là tính bắc cầu của phụ thuộc đa trị. Giả sử một quan hệ  trên tập các thuộc tính U thoả X Y và Y Z, nhưng không thoả phụ thuộc X (Z-Y). Thế thì tồn tại các bộ µ và  trong  với µ[X] = [X], nhưng bộ  với [X] = µ[X], [Z-Y] = µ[Z-Y], và [U-X-(Z-Y)] = [U-X-(Z-Y)] không thuộc .Bởi vì X Y đúng, suy ra rằng bộ , trong đó [X] = µ[X], [Y] =  [Y] và [U-Y-Z] =  [U-Y-Z] Trang 51
  52. thuộc . Bây giờ  và  giống nhau ở Y, thế nên do Y Z, suy ra rằng  có bộ , trong đó [Y] = [Y], [Z] = [Z], và  [U-Y-Z] =  [U-Y-Z] Chúng ta khẳng định rằng [X] = µ[X], bởI vì ở các thuộc tính trong ZX,  gống với , mà  lại giống với µ. Ở các thuộc tính của X-Z,  giống với , và  giống với µ ở X. Chúng ta cũng khẳng định rằng [Z-Y] = µ[Z-Y], bởi vì  giống với  ở Z-Y, mà  giống với µ ở Z-Y. Cuối cùng, chúng ta khẳng định rằng [V] = [V], với V=U-X-(Zx-Y). Thật vậy, chắcchắn rằng  giống với  ở V-Z, và nhờ các phép biến đổi tập hợp, chúng ta có thể chứng minh VZ=(YZ)-X. Nhưng  giống với  ở Z, mà  giống với  ở Y, vì thế  giống với  ở VZ cũng như ở V-Z. Do đó  giống với  ở V.Nếu xem lại định nghĩa của , chúng ta thấy rằng  = . Nhưng chúng ta đã khẳng định rằng  thuộc , vì vậy  cũng thuộc , mâu thuẫn với giả thiết của chúng ta. Vì thế cuối cùng X Z-Y đúng, khẳng định A6 đúng. Bây giờ chúng ta sẽ chứng minh A8. Giả sử điều ngược lại là chúng ta có một quan hệ  thoả X Y và W Z, với Z Y và WY là tập trống, nhưng X Z không đúng. Thế thì tồn tại các bộ  và µ trong  sao cho [X] = µ[X], nhưng [Z] µ[Z]. Áp dụng X Y cho  và µ, chúng ta phải có một bộ  trong  sao cho [X] = µ[X]=  [X], [Y] = µ[Y], và [U-X-Y] =  [U-X-Y]. Bởi vì WY trống, nên  và  giống nhau ở W. Vì ZY,  và µ giống nhau ở Z.Bởi vì  và µ không giống nhau ở Z, suy ra rằng  và  không giống ở Z. Chúng ta kết luận rằng X Z không thể không đúng, đó chính là khẳng định của qui tắc A8. Phần chứng minh còn lại của định lý sau dành cho bạn đọc. Trang 52
  53. Lưu ý: nên nhớ rằng trong định nghĩa của phụ thuộc đa trị thực sự chỉ cần tồn tại q3, không nhất thiết phải có q4 như trong mệnh đề thứ 3 của định nghĩa. Vì thế vi phạm phụ thuộc đa trị có thể được xác định bằng sự vắng mặt của q3 (không cần phải q3 hoặc q4 ) trong quan hệ r. III.3.1. Định lý II.4 (been, ragin, floward 1997) Các tiên đề A1-A8 là đúng đắn và đầy đủ cho các phụ thuộc hàm và phụ thuộc đa trị. Nghĩa là nếu D là tập các phụ thuộc hàm và phụ thuộc đa trị trên một tập thuộc tính U, và D’ là tập các phụ thuộc hàm và đa trị hệ quả của D (nghĩa là mỗi quan hệ trên U thỏa D cũng thỏa những phụ thuộc trong D’) thì D’ chính là tập các phụ thuộc suy ra từ D bởi các tiên đề A1-A8. III.4. Các qui tắc suy diễn bổ sung cho phụ thuộc đa trị Một số qui tắc khác cũng có ích trong các suy diễn về các phụ thuộc hàm và đa trị. Dĩ nhiên các qui tắc hợp, phân rã và giả bắc cầu đã đề cập trong Bổ đề II.2 vẫn áp dụng được cho các phụ thuộc hàm. Một số qui tắc khác là: 1. Qui tắc hợp của phụ thuộc đa trị. Nếu X Y và X Z thì X YZ 2. Qui tắc giả bắc cầu của phụ thuộc đa trị. Nếu X Y và WY Z thì WX (Z-WY) 3. Qui tắc giả bắc cầu pha trộn. Nếu X Y và XY Z thì X (Z-Y) 4. Qui tắc phân rã và phụ thuộc đa trị. Nếu X Y, và X Z thì X (YZ) và X (Y-Z) và X (Y-Z) Trang 53
  54. Chúng tôi để phần chứng minh này cho bạn đọc; phương pháp chứng minh cũng tương tự như phương pháp đã được dùng để chứng minh các quy tắc A6 và A8 ở trên, hoặc có thể chứng minh từ các tiên đề A1-A8. Chúng ta cần chú ý rằng qui tắc phân rã của phụ thuộc đa trị không mạnh bằng qui tắc tương ứng của phụ thuộc hàm. Quy tắc của phụ thuộc hàm cho phép chúng ta suy ra trực tiếp từ X Y rằng X A đúng với mọi các thuộc tính A trong Y. Qui tắc của phụ thuộc đa trị chỉ cho phép chúng ta kết luận X A từ X Y nếu chúng ta có thể tìm được Z sao cho X Z, hoặc Z Y=A hoặc Y – Z = A III.5. Bao đóng của phụ thuộc hàm và phụ thuộc đa trị Cho trước tập các phụ thuộc hàm và phụ thuộc đa trị D, chúng ta muốn tìm bao đóng của D, ký hiệu D+, là tập chứa tất cả các phụ thuộc hàm và phụ thuộc đa trị được suy ra từ D. Chúng ta có thể tính D+ bằng cách khởi đầu với D và áp dụng các tiên đề A1-A8 đến khi không còn suy ra được một phụ thuộc mới nào nữa. Tuy nhiên quá trình này có chi phí thời gian là hàm mũ theo kích thước của D. Thông thường chúng ta chỉ muốn biết xem một phụ thuộc hàm X Y hoặc phụ thuộc đa trị X Y nào đó có suy ra được từ D hay không. III.5.1. Cơ sở phụ thuộc Như đã trình bày khi nói về phụ thuộc hàm, để kiểm tra một phụ thuộc hàm X Y có thuộc D+ hay không, ta tính X+ là bao đóng của tập thuộc tính X đối với tập các phụ thuộc hàm trong D, sau đó xem Y có phải là tập con của X+ hay + không, nghĩa là Y = A1A2 Ak ,với Ai là thuộc tính thuộc X Trang 54
  55. Tương tự, để kiểm tra xem một phụ thuộc đa trị X Y có đúng hay không (thuộc D+ hay không), chúng ta chỉ cần xác định cơ sở phụ thuộc của X và xem Y –X có phải là hợp của một số tập trong cơ sở đó hay không. Nhận xét: - Bao đóng của X = A1A2 Ak ,với Ai là thuộc tính - Cơ sở phụ thuộc của X = Y1Y2 Yk ,với Yi là tập các thuộc tính Với qui tắc phân rã của phụ thuộc đa trị, cùng với quy tắc hợp, dẫn đến khẳng định sau đây về các tập Y sao cho X Y đúng với một tập X đã cho. III.5.2. Định lý II.4 : Nếu U là tập chứa tất cả các thuộc tính thì chúng ta có thể phân hoạch U-X thành các tập thuộc tính Y1 , ,Yk sao cho nếu Z  U-X thì X Z đúng nếu và chỉ nếu Z là hợp của một số Yi. Nhận xét: - Mỗi Yi là không rỗng, với i=1, 2, , k - Mỗi cặp các Yi,Yj là phân biệt (có giao là rỗng), với i,j=1, 2, , k - U-X là hợp của các tập Y1 ,Y2 , ,Yk - Z là con của U-X Trang 55
  56. Chứng minh: Khởi đầu phân hoạch toàn bộ U-X thành một khối (W1=U-X). Ta có thể phân họach như trên bởi vì do tiên đề A1 (tính phản xạ của phụ thuộc hàm) ta có phụ thuộc hàm hiển nhiên X X, hơn nữa do tiên đề A7 (liên hệ giữa phụ thuộc hàm và phụ thuộc đa trị) ta có X X đúng. Áp dụng tiên đề A4 (tính bù của phụ thuộc đa trị) ta có X (U-X-X) tức là X (U-X) đúng. Giả sử rằng tại một điểm nào đó chúng ta có các phân hoạch W1, ,Wn và X Wi với i = 1,2, .n. Nếu X Z đúng và Z không phải là hợp của một số Wi, hãy thay mỗi Wi có Wi  Z và Wi - Z đều không trống bởi Wi  Z và Wi - Z . Áp dụng qui tắc phân rã cho X Wi và X Z, ta có X (Wi  Z) và X (Wi - Z) đúng. Bởi vì chúng ta không thể phân hoạch vô hạn một tập các thuộc tính hữu hạn, cuối cùng chúng ta thấy rằng mỗi Z có X Z đúng đều là hợp của một số phân hoạch. Nhờ qui tắc hợp, X đa xác định hợp của một tập phân hoạch bất kỳ. Chúng ta gọi tập Y1 Yk được xây dựng cho X từ tập các phụ thuộc hàm và đa trị D là cơ sở phụ thuộc (dependency basis) của X (ứng với D). Trang 56
  57. Thí dụ II.7.: Trong Thí dụ II.6 chúng ta đã nhận xét rằng C HR. Vì thế theo qui tắc bù, C TSG. Chúng ta cũng biết rằng C T. Vì thế nhờ tiên đề A7, C T. Theo quy tắc phân rã, C SG. Cũng có thể kiểm chứng rằng không có một thuộc tính đơn nào trừ T hoặc C được xác định đa trị bởi C. Vì thế cơ sở phụ thuộc cho C là {T, HR, SG}. Về trực quan chúng ta thấy rằng, đi kèm với mỗi khoá học là các tập giảng viên (chỉ có duy nhất một tập), các cặp giờ học – phòng cho biết thời gian và địa điểm khoá học, và các cặp sinh viên - điểm, là danh sách sinh viên của khoá học. Nhận xét: Trong trường hợp tổng quát với X Z mà Z  U-X, tức là Z  X không rỗng. Áp dụng qui tắc phân rã cho X Z và X X ta có các phụ thuộc đa trị X (Z-X) và X (Z  X) cũng đúng. Với X (Z - X), vì (Z - X)  (U - X) nên do định lý trên (U - X) là hợp của một số các Yi là cơ sở phụ thuộc của X. Với X (Z  X), vì (Z  X)  X nên do tiên đề A1 và tiên đề A7 ta có X Ai với (Z  X) = A1 A2 Am Trang 57
  58. III.5.3. Thuật toán II.2: Tính Cơ sở phụ thuộc Để tính cơ sở phụ thuộc của X đối với D ta chỉ cần tính cơ sở phụ thuộc của X đối với tập các phụ thuộc đa trị M trong D là đủ. Khi đó đòi hỏi M phải bao gồm: 1. Tất cả các phụ thuộc đa trị thuộc D và 2. Với mỗi phụ thuộc hàm X Y thuộc D thì thay bằng tập các phụ thuộc đa trị X A1,X A2, X An, trong đó Y= A1A2 An, tức là Ai thuộc Y và mỗi Ai là một thuộc tính đơn. Một định lý khác của Beeri [1980] cho chúng ta cách lấy ra những phụ thuộc hàm không tầm thường từ cơ sở phụ thuộc được tính ứng với tập các phụ thuộc đa trị M. Beeri đã chứng minh được rằng nếu X không chứa A thì X A đúng nếu và chỉ nếu: 1. A là tập độc nhất trong cơ sở phụ thuộc cho X ứng với tập phụ thuộc đa trị M, và 2. Có một tập thuộc tính Y không chứa A, sao cho Y Z là một trong những phụ thuộc của D và A thuộc Z. Ta có thuật tóan tính cơ sở phụ thuộc sau: NHẬP: Tập phụ thuộc đa trị M trên tập các thuộc tính U và tâp X  U. XUẤT: Cơ sở phụ thuộc cho X ứng với M. Trang 58
  59. PHƯƠNG PHÁP: Chúng ta khởi đầu với một tập các tập hợp S mà cuối cùng sẽ trở thành cơ sở phụ thuộc. Lúc ban đầu, S chỉ chứa một tập là U-X; nghĩa là S = {U-X}. Chúng ta tìm lập đi lập lại các phụ thuộc V W trong M và một tập Y trong S sao cho Y có giao với W nhưng không giao với V cho đến khi không còn thay đổi nào đối với S. Sau đó thay Y bằng Y  W và Y-W trong S.Tập các tập hợp S cuối cùng cũng là cơ sở phụ thuộc cho X. Bởi vì thuật toán II.2 chỉ tách các tập trong S, và nó sẽ kết thúc khi không thể tách được các tập nữa nên dễ thấy rằng nó có chi phí thời gian và hàm đa thức theo kích thước của M và U. Thực tế nếu được cài đặt cẩn thận, Thuật toán sẽ chạy trong thời gian tỉ lệ với số lượng phụ thuộc trong M nhân với luỹ thừa ba của số lượng thuộc tính trong U. Phép chứng minh khẳng định này và chứng minh tính đúng đắn của Thuật toán 7.6 có thể tham khảo trong Beeri [1890] Trang 59