Luận văn Một số vấn đề liên quan đến dạng chuẩn trong hệ cơ sở dữ liệu

a là một thuộc tính cơ bản của r nếu tồn tại một khoá tối tiểu K (K Î Kr ) để a là một phần tử của K. Nếu a không là thuộc tính cơ bản, a sẽ được gọi là thuộc tính thứ cấp. Nhận xét: Thuộc tính cơ bản và thuộc tính thứ cấp đóng một vai trò quan trọng trong việc chuẩn hóa các sơ đồ quan hệ và các quan hệ. Đinh lý 26. Cho trước một sơ đồ quan hệ s = và một thuộc tính a. Bài toán xem a có phải là thuộc tính cơ bản hay không là bài toán NP - đầy đủ. 1.14 Một số thuật toán liên quan Thuật toán 1. (Tìm tập các thuộc tính cơ bản của một quan hệ trên R) Input: r = { h1, h2, ..., hm} là một quan hệ trên R Output: V là tập tất cả các thuộc tính cơ bản của r Phương pháp: Bước 1: Từ r = { h1, h2,.., hm } ta xây dựng một tập Er Er = {Eij : 1£ i < j £ m } Trong đó Eij = { a : a Î R và hi(a) = hj(a) } Bước 2: Từ Er ta xây dựng tập M M = { B Î P(R): Tồn tại Eij Î Er: Eij = B } Bước 3: Từ M xây dựng tập Mr Mr = { B Î P(R) : "B' Î M : B Ë B' } Bước 4: Xây dựng tập V = R\ Ç Mr Nhận xét: Ta thấy m( m-1) ³ êEr êM ê³ êMr ê) Do vậy Mr được tính bằng thuật toán thời gian đa thức. Suy ra V tính được bằng thời gian đa thức theo số hàng và số cột của r Ví dụ: Xét quan hệ ( A B C D ) 1 0 1 1 0 1 1 0 1 1 0 1 0 2 0 0 Bước 1: Tính Er E12 = {C} E13 = {A, D} E14 = {Æ} E23 = {B} E24 = {A, D} E34 = {C} Bước 2: Tính M = {{A, D},{B},{C},{Æ}} Bước 3: Tính Mr = {{A, D},{B},{C}} Bước 4: V = R\ Ç Mr = {A, B, C, D }\ {Æ} = {A, B, C, D } suy ra V = R. Như thế mọi thuộc tính của r đều là cơ bản. Định lý 27. Tồn tại một thuật toán để xác định một thuộc tính bất kỳ của một quan hệ có là cơ bản hay không với thời gian đa thức theo số hàng và số cột của r. Một vấn đề thường xuyên xảy ra là đối với một sơ đồ quan hệ cho trước (s = ), và một phụ thuộc hàm A ® B, chúng ta muốn biết A ®B có là phần tử của F+ hay không. Để trả lời câu hỏi này chúng ta cần tính bao đóng F+ của tập các phụ thuộc hàm F. Tuy nhiên tính F+ trong trường hợp tổng quát là rất khó khăn và tốn kếm thời gian vì các tập phụ thuộc hàm thuộc F+ là rất lớn cho dù F có thể là nhỏ. Chẳng hạn, F = {A ® B1, A ® B2,.... A ® Bn }, khi đó F+ bao gồm cả những phụ thuộc hàm A ® Y với Y Í {B1 È B2 È ... È Bn}, như vậy ta sẽ có 2n tập con Y. Trong khi đó việc tính bao đóng của tập thuộc tính A lại không khó. Theo kết quả đã trình bầy ở trên thì việc kiểm tra A ® B Î F+ không khó hơn việc tính A+. Ta có thể tính bao đóng của sơ đồ quan hệ (A+) theo thuật toán sau: Thuật toán 2. (Tính bao đóng của một tập các thuộc tính trên tập các phụ thuộc hàm đối với sơ đồ quan hệ) Input : s = là một sơ đồ quan hệ trong đó R = (a1, a2,.., an) là tập hữu hạn các thuộc tính. F là tập các phụ thuộc hàm và A Í R Output : A+ là bao đóng của A đối với F. Phương pháp: Lần lượt tính các tập thuộc tính Ao, A1 như sau: 1). A0 = A 2). Ai = Ai-1 È {a} nếu $ (C ® D) Î F, {a} Î D và C Í Ai-1 3). Rõ ràng A = A0 Í A1 Í ... Í Ai Í R và R hữu hạn nên tồn tại i sao cho Ai = Ai+1 Khi ấy thuật toán dừng và Ai chính là A+ Ví dụ: Xét sơ đồ quan hệ s = trong đó {c} ® {t} R = {c, t, h, r, s, g} {h, r}® {c} F = {h, t}® {r} {c, s} ® {g} {h, s} ® {r} Tính {h, r}+ ? A0 = {h, r} A1 = {h, r, c}+ do {h, r}® {c}ÎF A2 = {h, r, c, t}+ do {c}® {t}Î F A3 = {h, r, c, t}+ = A2 Vậy {h, r}+ = {h, r, c, t} Nhận xét: Độphức tạp thời gian của thuật toán này là đa thức theo kích thước của s. Định lý 28. Thuật toán 2 tính chính xác A+ . Như vậy để xác định một phụ thuộc hàm A B có thuộc F+ hay không chúng ta chỉ cần kiểm tra B Í A+ ? Bây giờ chúng ta xây dựng một thuật toán tìm bao đóng cho một tập các thuộc tính trên một quan hệ bất kỳ. Đối với một quan hệ bất kỳ theo định lý 17 chúng ta đã chứng minh với mọi A Í R A Í Eij Ç Eij Nếu tồn tại Eij Î Er : A Í Eij LFr(A) = R ngược lại ở đây LFr (A) = {a Î R: (A, {a}) Î F) và Er là hệ bằng nhau của r. Có thể thấy LFr(A) = A+r . Do vậy chúng ta có ngay thuật toán sau để tính bao đóng cho một tập bất kỳ trên quan hệ r. Thuật toán 3. (Tính bao đóng cho một tập bất kỳ trên quan hệ r) Input : r = {h1, h2,.., hm} là một quan hệ trên R = { a1, a2,.., an }, A Í R Output : A+r Bước 1: Từ r xây dựng một tập Er = { Eij : 1 £ i < j £ m } Eij = { a : a Î R và hi(a) = hj(a) } Bước 2: Từ Er xây dựng một tập M = { B Î P(R) : Tồn tại Eij Î Er : Eij = B} ở đây P(R) là tập chứa tất cả các tập con của R Bước 3: A+r được tính như sau: A Í B Ç B nếu tồn tại B Î M : A Í B A+r = R ngược lại . Dễ thấy độ phức tạp thời gian của thuật toán này là đa thức theo kích thước r. Có thể thấy rằng Eij = Æ (trong trường hợp hai dòng i và j không có cột nào trùng nhau về giá trị, có nghĩa rằng chúng khác nhau hoàn toàn, có thể xẩy ra một số các tập bằng nhau trùng nhau. Không bao giờ có Eij = R ( có nghĩa rằng Eij = toàn bộ không gian), vì nếu xẩy ra thì có hai dòng trùng nhau, theo định nghĩa quan hệ thì không cho phép có hai dòng trùng nhau. Ví dụ: xét quan hệ r A B C D E 1 1 0 0 0 0 1 0 1 1 0 0 2 0 2 2 0 2 0 2 Tính {B, C}+r E12 ={ B, C }, E13 = {D}, E14 = {D} E23 = {A}, E24 ={Æ} E34 = {B, C, D} M = { (A), (B, C), (B, C, D), (D) } Vậy { B, C}+r = (B, C) Ç (B, C, D) ={B, C} Thuật toán 4. (Kiểm tra hai quan hệ có tương đương nhau không) Input: r1, r2 là hai quan hệ trên R. Output: Kết luận r1, r2 có tương đương nhau không. Phương pháp: Bước 1: Tính Nr1 Bước 2: Tính Nr2 Bước 3: So sánh Nr1 và Nr2 . Nếu Nr1 = Nr2 thì kết luận hai quan hệ tương đương. Nếu Nr1 ¹ Nr2 : hai quan hệ không tương đương. Ví dụ: Xét hai quan hệ r1 ( A B C D E ) r2 ( A B C D E ) 1 0 2 0 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 2 0 0 Đối với quan hệ r1 E12 = ( A ), E13 =( D, E ) E14 = ( A, D, E ) E23 = ( B ) E24 = ( A, B, C ) E34 = ( B, D, E ) Nr1 = {{ A, D, E }, { A, B, C }, { B, D, E }} Đối với quan hệ r2 E12 = { C, E } E13 = { A, D, E } E14 = { A, B } E23 = { B, E} E24 = { D } E34 = { A } Nr2 = {{ A, B }, { A, D, E }, { B, E }, { C, E }} Như vậy Nr1 ¹ Nr2. Hai quan hệ r1 và r2 là không tương đương. Định nghĩa 29. Chúng ta nói một sơ đồ quan hệ s = là chính tắc nếu: - Vế phải của mỗi phụ thuộc hàm trong F là thuộc tính đơn. - Không có X ® a nào ở trong F để F \ {X ® a} tương đương với F. - Không có X ® a và một tập con Z của X để F \ { X ® A} È {Z ® a} tương đương với F. Chúng ta sẽ chỉ ra rằng có thuật toán để tìm một phủ chính tắc cho một sơ đồ quan hệ bất kỳ. Trước tiên chúng ta đưa ra mệnh đề sau Mệnh đề 30. Mỗi một sơ đồ quan hệ s = đều có một phủ tương đương t = sao cho vế phải của mỗi phụ thuộc hàm trong G không có hơn một thuộc tính. Ta đặt G là tập phụ thuộc hàm có dạng X ® a, với X ® Y nằm trong F và a là một phần tử của Y. Trên cơ sở hệ tiên đề của Armstrong, ta dễ thấy t tương đương với s. Thuật toán dưới đây để tìm phủ chính tắc cho một sơ đồ quan hệ cho trước. Thuật toán 5. Input: s = , F = {A1 ® B1, A2 ® B2,..., Am ® Bm} Output: t = là chính tắc và tương đương với s. Phương Pháp: Bước1: Đặt Fo = F, với i =1, 2..., m Fi = Fi-1 \ {Ai ® Bi} nếu Fi-1 \ {Ai ® Bi} tương đương với Fi . Trong trường hợp ngược lại thì Fi = Fi-1. Bước 2: Nhờ thuật toán tính bao đóng, từ Fm chúng ta lần lượt loại bỏ các thuộc tính thừa trong mỗi vế trái của từng phụ thuộc hàm thuộc Fm . Kết quả nhận được chính là G. Dễ thấy thuật toán trên có độ phức tạp thời gian là đa thức theo kích thước của s. Chúng ta đưa ra một khái niệm sau Định nghĩa 31. Giả sử s = là một sơ đồ quan hệ trên R. Khi đó chúng ta nói rằng s là sơ đồ quan hệ tối tiểu nếu với mọi sơ đồ quan hệ t = tương đương với s có | F | £ | G |, ở đây | F | là số lượng các phụ thuộc hàm trong F. David Maier đã chứng minh định lý sau Định lý 32. Tồn tại một thuật toán có độ phức tạp thời gian đa thức để tìm phủ tối tiểu cho một sơ đồ quan hệ cho trước. Ví dụ: Chúng ta xem xét tập các phụ thuộc hàm F sau {c} ® {a,d} {h, r}® {c} F = {h, t}® {r,g} {c} ® {g} {h, s}®{r,d} Ban đầu chúng ta tách vế phải ra thành các thuộc tính đơn: {c} ® {a} {c} ® {d} {h, r}® {c} {h, t}® {r} {h, t}® {g} {c} ® {g} {h, s}®{r} {h, s}®{d} Rõ ràng {h,s}®{d} là không cần thiết bởi vì nó suy ra được từ {c}®{d} {h, t}® {g} là dư thừa bởi vì có {c} ® {g}. Ngoài ra không còn có một phụ thuộc hàm nào dư thừa nữa. Vậy chúng ta có một phủ chính tắc là: {c} ® {a} {c} ® {d} {h, r}® {c} {h, t}® {r} {c} ® {g} {h, s}®{r} Thuật toán 6. (Tìm một khóa tối tiểu của sơ đồ quan hệ) Input: Sơ đồ quan hệ s = trong đó R = {a1, a2,.., an} là tập các thuộc tính F là tập các phụ thuộc hàm Output: K là một khoá tối tiểu của R. Phương pháp: Tính liên tiếp các tập thuộc tính K0 , K1 ,.., Kn như sau: K0 = R Ki-1\ {ai} nếu Ki-1\ {ai} ® R Ki = Ki-1 nếu ngược lại. K= Kn là khoá tối tiểu Nhận xét: Thuật toán này sàng lọc từng cột một bắt đầu từ cột a1 đến cột an, việc sàng lọc này là bỏ đi những cột thừa với điều kiện bỏ đi những phần còn lại bao đóng của nó bằng R. Nếu bỏ đi mà bao đóng phần còn lại không là khóa thì không bỏ đi được ( vì nó không đảm bảo tính khóa). Vì vậy muốn tính được một khóa tối tiểu thì chúng ta tính A+ Vì thuật toán tính A+ có độ phức tạp là đa thức cho nên thuật toán này cũng có độ phức tạp là đa thức. Có thể thấy rằng thay đổi thứ tự các thuộc tính của R ta lại có thể tìm được một khoá tối tiểu khác. Nếu đã biết một khoá A ( không chắc chẵn là khoá tối tiểu ) tại bước một có thể đặt K0 = A và áp dụng các bước tiếp theo ta vẫn tính được một khoá tối tiểu khác và rõ ràng số bước tính là ít hơn so với cách đặt K0 = R. Ví dụ: Giả sử s = là một sơ đồ quan hệ trong đó R = {c, t, h, r, s, g} { c } ® {t} {h È r}® {c} F = {h È t}® {r} {c È s}® {g} {h È s}® {r} Dùng thuật toán trên để tìm một khoá tối tiểu của s. K0 = R = {c, t, h, r, s, g} Tính K1 K0 \ {c} = {t, h, r, s, g} áp dụng thuật toán 2 ta tính được {t, h, r, s, g}+ ={c, t, h, r, s, g}= R Tức là {t, h, r, s, g} ® R Î F+ Vậy K1 = K0 \ {c} = {t, h, r, s, g} Tính K2 K1 \ {t} = {h, r, s, g} {h, r, s, g}+ = {c, t, h, r, s, g} = R Vậy K2 = K1 \ {t} = {h, r, s, g} Tính K3 K2 \ {h} = {r, s, g} {r, s, g}+ = {r, s, g} Vậy K3 = K2 = {h, r, s, g} Tính K4 K3 \ {r} = {h, s, g} {h, s, g}+ = {c, t, h, r, s, g} = R Vậy K4 = K3 \ {r} = {h, s, g} Tính K5 K4 \ {s} = {h, g} {h, g}+ = {h, s, g} Vậy K5 = {h, s, g} Tính K6 K5 \ {g} = {h, s} {h, s}+ = {c, t, h, r, s, g} = R Vậy K6 = K5 \ {g} = {h, s} Khóa của sơ đồ quan hệ s = là {h, s}. Thuật toán 7. (Tìm một khoá tối tiểu của một quan hệ) Input: r = {h1, h2,.., hm} là một quan hệ trên tập các thuộc tính R (R = {a1, a2,.., an}) Output: K là một khoá tối tiểu của r Phương pháp: Bước 1: Từ r = {h1, h2,.., hm}, tính Er = {Eij : 1£ i < j £ m } là hệ bằng nhau Bước 2: Từ Er tính Mr là hệ bằng nhau cực đại Mr = {B : có Eij để Eij = B và không có Est : B Ë Est ( Eij, Est Î Er)} Bước 3: Lần lượt tính các tập thuộc tính K0 , K1, ... , Kn theo quy tắc: K0 = R = { a1 , a2 ,.., an } hoặc K0 là một khóa ( chưa chắc tối tiểu) đã biết. Ki = Ki-1\ { ai} nếu không tồn tại B Î Mr sao cho Ki-1\ { ai} Ì B hoặc Ki = Ki-1 trong trường hợp còn lại. Bước 4: Đặt Ki = Ki-1 . Khi ấy Kn là một khóa tối tiểu. Nhận xét: - Việc tính Mr là dễ dàng vì số lượng phần tử của Mr nhỏ hơn rất nhiều so với Er - Thuật toán này nếu thay đổi thứ tự các thuộc tính của R ta có thể tìm thấy một khoá tổi tiểu khác. Ví dụ: Xét quan hệ chuyen_hang trong bảng sau: shh: Số hiệu của hãng cung cấp shmh: Số hiệu của mặt hàng được cung cấp sluong: Số lượng hàng cung cấp trong chuyển hàng n ngày shh shmh sluong 10/04/2000 C1 P1 200 12/04/2000 C1 P2 200 12/04/2000 C2 P2 100 16/04/2000 C2 P1 600 Bước 1: Tính Er : E12 = { shh, sluong }, E13 = {Æ}, E14 = { shmh } E23 = { ngay, shmh }, E24 = {Æ} E34 = { shh } Bước 2: Tính Mr = {{ shh, sluong },{ ngay, shmh }} Bước 3: K0 = R = { ngay, shh, shmh, sluong } K1 = K0 \ { ngay } = { shh, shmh, sluong } vậy K1 = { shh, shmh, sluong } K2 = K1 \ { shh } = { shmh, sluong } K3 = K2 \ { shmh } = { shh, sluong }Î Mr K4 = K3 \ { sluong } = { shh, shmh } Vậy khoá tối tiểu của quan hệ chuyen_hang: K={shmh, sluong } Thuật toán 8. (Tìm tập các phản khoá xuất phát từ một hệ Sperner) Input: K = {B1, B2,.., Bm} là một hệ Sperner trên R Output: K-1 Phương pháp; Bước 1: Đặt K1 = { R\ {a}: a Î B1} Rõ ràng K1 = {B1}-1. Bước q+1: (q < m). Giả thiết rằng Kq = Fq È { X1, X2,.., Xtq} ở đây Xi, i = 1, 2,..., tq, chứa Bq+1 và Fq = {A Î Kq: Bq+1 Í A}. với mỗi i = 1,..,tq ta xây dựng các phản khoá của {Bq+1} trên Xi theo cách tương tự như khi xây dựng K1. Ký hiệu đó là A1i,...,Arii (i =1,..., tq). Đặt Kq+1 = Fq È { Api : A Î Fq Þ Aqi Ë A, 1 £ i £ tq , 1 £ p £ ri } Ta đặt K-1 = Km Ví dụ: Giả sử R = {d, e, f, g} K = {{d, e}, {d, f}} = {B1, B2}. K1 = {R\ {d}, R\ {e}} = {{e, f, g}, {d, f, g}}. F1 = {{e, f, g}, X1 = {d, f, g}. Xây dựng tập các phản khóa của B2 = {d, f} trên X1 = {d, f, g} theo bước 1 ta được {{f, g}, {d, g}}, trong đó có tập {d, g} không là tập con của Fq . Vậy K2 = {{e, f, g}, {d, g}}. Đây chính là tập K-1. Định lý 33. Với mọi q (1 £ q £ m-1), Kq = {B1 ,..., Bq}-1, tức là Km = K-1. Nhận xét: Có thể thấy rằng K và K-1 được xác định duy nhất từ nhau và việc xác định K-1 theo thuật toán của ta không phụ thuộc vào thứ tự của B1,..., Bm. Ký hiệu Kq = Fq {X1,...,Xtq} và lq (1 £ lq £ m-1) là số phần tử của Kq. Mệnh đề 34. m-1 Trong trường hợp sấu nhất độ phức tạp của thuật toán 8 là q=1 O(|U|2å tq.uq ) ở đây lq - tq nếu lq > tq uq= 1 nếu lq = tq. Nhận xét: Rõ ràng tại mỗi bước của thuật toán ta có Kq là hệ Sperner trên R. Đã có kết quả rằng kích cỡ của một hệ Sperner trên R không thể lớn hơn Cn[n/2] , ở đây n = |R| có thể xấp xỉ 2n+1/2/ ( p. n1/2). Từ đó, trong trường hợp sấu nhất độ phức tạp của thuật toán không lớn hơn một hàm số mũ theo số lượng các thuộc tính. Trong trường hợp lq £ lm (q = 1,..., m-1) dễ thấy rằng độ phức tạp của thuật toán không lớn hơn O(|R|2 |K| |K-1|2). Do vậy trong các trường hợp này, thuật toán 8 tìm ra K-1 với thời gian đa thức theo |R|, |K|, |K-1|. Có thể thấy rằng nếu số lượng các phần tử của K nhỏ thì thuật toán 8 rất hiệu quả. Nó chỉ đòi hỏi thời gian đa thức theo |R|. CHƯƠNG II DẠNG CHUẨN ĐỐI VỚI QUAN HỆ VÀ SƠ ĐỒ QUAN HỆ Việc chuẩn hoá các quan hệ cũng như các sơ đồ quan hệ đóng một vai trò quan trọng trong việc thiết kế các hệ quản trị cơ sở dữ liệu trên mô hình dữ liệu của E.F.Codd. Nhờ có chuẩn hoá các quan hệ và các sơ đồ quan hệ chúng ta tránh được việc dư thừa dữ liệu và tăng tốc độ các phép toán xử lý quan hệ. 2.1. Các khái niệm cơ bản Chúng ta định nghĩa các dạng chuẩn như sau: Định nghĩa 1. (Dạng chuẩn 1 - 1NF) Giả sử r = {h1, h2,.., hm} là file dữ liệu trên tập cột R = {a1, a2,.., an} Khi đó r là 1NF nếu các giá trị hi(aj) là sơ cấp với mọi i, j Khái niệm sơ cấp hiểu ở đây là giá trị hi(aj) (i = 1,...,m ; j = 1,...n ) không phân chia được nữa. Ví dụ: Xét quan hệ - Trình độ ngoại ngữ TDNN MNS HOTEN NGOAINGU TH001 Phạm Ngọc Thạch Anh,Pháp,Nhật TH002 Bùi Lan Hương Anh, Trung TH003 Lê Thị Thanh Pháp,Đức TH004 Nguyễn Văn Trính Anh, Nga, Đức TH005 Hoàng Thị Anh Anh, Pháp TH006 Trần Khắc Toản Pháp Có thể thấy rằng thuộc tính NGOAINGU còn có thể được chia nhỏ hơn ra thành từng ngoại ngữ một và sau đó có thể phân thành hai bộ phận là tên ngoại ngữ và trình độ ngoại ngữ. Do vậy quan hệ ngoại ngữ chưa ở dạng chuẩn 1. Định nghĩa 2. (Dạng chuẩn 2 - 2NF) Quan hệ r được gọi là dạng chuẩn 2 nếu: - Quan hệ r là dạng chuẩn 1 - Với mọi khoá tối tiểu K không tồn tại phụ thuộc hàm A ®{a}Î Fr với A Ì K và a là thuộc tính thứ cấp . Định nghĩa 3. (Dạng chuẩn 3 - 3NF) Quan hệ r là dạng chuẩn 3 nếu: A ®{a}Ï Fr đối với A mà A+ ¹ R, a Ï A, a Ï È K Có nghĩa là: K là một khóa tối tiểu a là thuộc tính thứ cấp A không là khóa A ® {a} không đúng trong r. Định nghĩa 4. ( Dạng chuẩn Boyce-Codd - BCNF) Quan hệ r = { h1, h2,..., hm} được gọi là dạng chuẩn Boyce - Codd nếu: A® {a} Ï Fr , đối với những tập thuộc tính A mà A+ ¹ R, a Ï A. Nhận xét: Qua định nghĩa ta có thể thấy dạng chuẩn BCNF là 3NF và 3NF là 2NF. Tuy vậy, chúng ta có thể đưa ra các ví dụ chứng tỏ quan hệ là 2NF nhưng không là 3NF và có quan hệ là 3NF nhưng không là BCNF. Nói cách khác, lớp các quan hệ BCNF là lớp con thực sự của lớp các quan hệ 3NF và lớp các quan hệ 3NF này lại là lớp con thực sự của lớp các quan hệ 2NF. Đối với s = thì các dạng chuẩn 2NF, 3NF, BCNF trong đó ta thay Fr = F+. Chú ý: Đối với sơ đồ quan hệ chúng ta không có dạng chuẩn 1NF. Ví dụ 1: Cho s = là sơ đồ quan hệ, với R = (a1, a2, a3, a4) F = { { a1}® {a2},{ a3} ® {a4},{ a2} ® {a1, a3, a4}} Dễ thấy a1, a2 là các khóa tối tiểu của s, a4 là thuộc tính thứ cấp. Do đó, s là 2NF, nhưng không là 3NF. Ví dụ 2: Cho t = là sơ đồ quan hệ, với R = (a1, a2, a3, a4) F = { { a1, a3} ®{ a2},{ a4}® {a3},{a2}® {a1, a3, a4}} Ta nhận thấy { a1, a3}, {a2} là các khóa tối tiểu của t. Hiển nhiên t là 3NF vì có { a4}® {a3}, nên t không là BCNF. Như vậy việc phân lớp các dạng chuẩn có thể được thể hiện qua hình vẽ sau: BCNF 3NF 1NF 2.2 . Dạng chuẩn 2NF. Bây giờ chúng ta nêu ra loại phụ thuộc hàm đặc biệt, mà phụ thuộc dữ liệu này đóng vai trò quan trọng trong dạng chuẩn 2 Định nghĩa 1. Một phụ thuộc hàm A ® B được gọi là sơ cấp nếu không tồn tại một tập hợp A' Ì A sao cho A' ® B. Trong trường hợp này ta cũng nói B phụ thuộc hoàn toàn vào A. Như vậy nếu A là một thuộc tính sơ cấp thì phụ thuộc hàm A ® B cũng là sơ cấp. Trong trường hợp ngược lại, ta nói B phụ thuộc bộ phận vào A. Định lý 2. Cho r là một quan hệ trên R. Khi đó r là 2NF khi và chỉ khi r là 1NF Mỗi thuộc tính thứ cấp của r đều phụ thuộc hoàn toàn vào mọi khóa tối tiểu. Vì sơ đồ quan hệ không có dạng chuẩn 1NF, từ định nghĩa 2 ta có mệnh đề sau Mệnh đề 3. Cho s là một sơ đồ quan hệ trên R. Khi đó s là 2NF khi và chỉ khi mọi thuộc tính thứ cấp của s đều phụ thuộc hoàn toàn vào khóa tối tiểu bất kỳ. Có thể thấy, bản chất dạng chuẩn 2NF là loại bỏ các phụ thuộc bộ phận giữa các thuộc tính thứ cấp với các khóa tối tiểu. Định lý 4. Giả sử s = là sơ đồ quan hệ. Đặt Ms = { A- a ; a Î A, A Î Ks}, và Fn là tập tất cả các thuộc tính thứ cấp của s. Đặt ls = {B : B = C+ , C Î Ms}. Khi đó ta có các tương đương sau: s là 2NF Với mỗi C Î Ms : C+ Ç Fn = Æ; Với mỗi B Î ls và a Î Fn : (B - a)+ = B - a. Chứng minh: Giả sử s là 2NF. Nếu Fn = Æ thì (2) là rõ ràng. Giả thiết rằng Fn ¹ Æ . Do định nghĩa của Fn và của Ms, (3) là hiển nhiên. Giả sử rằng chúng ta có (2) và Fn ¹ Æ. Nếu có B Î ls, và a Î Fn : B - a Ì (B - a)+. Từ định nghĩa của ls có C Î Ms : C+ = B. Rõ ràng rằng a Î ( B - a)+. Phù hợp với định nghĩa của bao đóng chúng ta có (B - a)+ = C+ = B. Từ đó ta thu được a Î C+. Do vậy, C+ Ç Fn ¹ Æ. Điều này là vô lý. Do đó ta thu được (3). Bây giờ, giả sử chúng ta có (3) và Fn ¹ Æ. Giả thiết rằng tồn tại D Ì A, A Î Ks (*) và a Î Fn, a Ï D, nhưng D ® {a}Î F+. Do (*) và phù hợp với việc xây dựng của Ms và ls thì có C Î Ms : D Í C. Hiển nhiên rằng a Ï C. Rõ ràng, D+ Í C+ và a Î C+. Đặt B = C+. Có thể thấy C Í B - a. Do đó, B - a Ì C+ = ( B -a)+. Điều này mâu thuẫn với (B - a)+ =B - a. Như vậy chúng ta có (1). Từ định lý 4 suy ra kết quả sau: Hệ quả 5. Giả sử s = là một sơ đồ quan hệ. Ký pháp Fn là tập tất cả những thuộc tính thứ cấp của s, và Gs = {B - Fn : B ÎKs-1}. Khi đó nếu đối với mọi C Î Gs : C+ = C thì s là 2NF. Cho s = là một sơ đồ quan hệ trên R. Đặt Z(s) = {X+: X Í R}. Chúng ta nói rằng s là đơn nếu F chứa chỉ các phụ thuộc hàm dạng {a} ® {b}. Biết rằng [6] s là đơn nếu và chỉ nếu đối với mọi A, B Î Z(s) : A È B Î Z(s). Rõ ràng, từ điều đó ta có (A È B)+ = A+ È B+. Mệnh đề 6. Cho s = là một sơ đồ quan hệ đơn. Đặt Fn là tập tất cả những thuộc tính thứ cấp của s, và Gs = {B - Fn : B Î Ks-1}. Khi đó s là 2NF nếu và chỉ nếu với mọi C Î Gs : C+ = C. Chứng minh: Giả sử rằng s là 2NF. Nếu Fn = Æ thì bởi định nghĩa của phản khóa ta có C+ = C. Nếu Fn ¹ Æ thì giả thiết rằng có C Î Gs : C+ ¹ C. Bởi định nghĩa của Gs thì tồn tại B Î Ks-1: C È Fn = B. Biết rằng [9] Fn là giao của tất cả các phản khóa chúng ta có C Ì B. Do đó, C+ Í B, C+ Ç Fn = Æ. Ta ký hiệu các phần tử của C là c1, c2,..., cl. Bởi vì s là đơn chúng ta thu được {c1}+ È ... È {cl}+ = C+. Do đó tồn tại c1 Î C sao cho {c1}+ Ç Fn =Æ. Hiển nhiên c1 là thuộc tính cơ bản. Điều này trái với việc s có 2NF. Do đó, C+ = C. f Ngược lại bởi hệ quả 5 nếu ta có C+ = C đối với mọi C Î Gs, thì s là 2NF. r Cho r là một quan hệ trên R. Đặt A+r = {a : a Î R, A {a}}, r là quan hệ đơn nếu đối với mọi A, B Í R: (A È B)+r = A+r È B+r. Biết rằng đối với một quan hệ r cho trước thì tập hợp tất cả các phản khóa của r được xây dựng trong thời gian đa thức. Trong [9] chúng ta đã chỉ ra rằng giao của tất cả các phản khóa đúng bằng tập tất cả các thuộc tính thứ cấp. Mặt khác biết rằng [6] nếu sơ đồ quan hệ s = là đơn thì độ phức tạp thời gian tìm quan hệ r sao cho F+ = Fr là đa thức. Từ điều này và mệnh đề 6 ta có Mệnh đề 7. Cho s là một sơ đồ quan hệ đơn và r là một quan hệ đơn trên R. Khi đó tồn tại một thuật toán đa thức xác định rằng s ( r, tương ứng) có là 2NF. 2.3. Dạng chuẩn 3NF. Trong mục này chúng ta đưa ra khái niệm quan trọng để mô tả dạng chuẩn 3NF. Định Nghĩa 1. Một phụ thuộc hàm A ® C được gọi là trực tiếp nếu không có B ( B ¹ A và B ¹ C ) sao cho A ® B và B ® C nhưng B không phụ thuộc hàm vào A hoặc C không phụ thuộc hàm vào B. Trong trường hợp nếu có B như vậy thì B được gọi là tập thuộc tính bắc cầu và A ® C là phụ thuộc bắc cầu. Định lý 2. Giả sử r = { h1, h2,.., hm} là một quan hệ trên R = {a1, a2,..., an}. Khi ấy r ở dạng chuẩn 3NF nếu và chỉ nếu: - Quan hệ r đã ở dạng chuẩn 2NF. - Không có thuộc tính thứ cấp nào của r phụ thuộc bắc cầu vào một khoá tối tiểu. Mệnh đề 3. Giả sử s là một sơ đồ quan hệ trên R. Khi đó s là 3 NF nếu và chỉ nếu s là 2NF Mọi thuộc tính thứ cấp của s phụ thuộc trực tiếp vào mỗi khoá tối tiểu. Trong dạng chuẩn 3NF chúng ta loại bỏ các phụ thuộc bộ phận, phụ thuộc bắc cầu giữa các thuộc tính thứ cấp với các khoá tối tiểu. Một số đặc trưng của các sơ đồ quan hệ dạng 3NF Cho s = là một sơ đồ quan hệ trên R. Từ s chúng ta xây dựng Z(s) = {X+ : X Í R}, và tính hệ sinh Ns của Z(s). Chúng ta đặt Ts = {A Î Ns: $ B Î Ns : A Ì B} Biết rằng [1] đối với một sơ đồ quan hệ s cho trước thì tồn tại một quan hệ r là quan hệ Armstrong của s. Mệnh đề 4. S là một sơ đồ quan hệ. Khi đó Ks-1 = Ts Định lý 5. Cho s = là một sơ đồ quan hệ. Đặt Fn là tập tất cả các thuộc tính thứ cấp của s. Khi đó s là 3NF nếu và chỉ nếu "B Î Ks-1, a Î Fn : (B - a)+ = B - a. Chứng minh: Giả sử Fn ¹ Æ . Có thể thấy rằng s là 3NF thì đối với mỗi B Î Ks-1, a Î Fn: B - a = (B - a)+. Ngược lại, nếu s không là 3NF thì tồn tại một tập A và a Î Fn : a Ï A sao cho A ®{a}Î F+ và A+ ¹ R. Phù hợp với Mệnh đề 4 có B Î K-1r sao cho A+ Í B. Từ a Î A+ chúng ta có a Î B. Do a Ï A ta có A Í B - a. Do đó ta thu được B - a Ì (B - a)+. Định lý 6. Giả sử r là một quan hệ trên R. Khi đó r là 3NF nếu và chỉ nếu với mọi A Î Er, a ÎA và a là thuộc tính thứ cấp thì {A - a}r+ = A - a, ở đây Er là hệ bằng nhau cực đại của r. Từ định lý 5 ta có hệ quả sau Hệ quả 7. Giả sử s là một quan hệ trên R. Khi đó s là 3NF nếu và chỉ nếu với mọi A : A+ = A, a Î A và a là thuộc tính thứ cấp thì {A - a}+ = A - a. 2.4 Dạng chuẩn BCNF Trong mục này, chúng ta đưa ra một số các đặc trưng của dạng chuẩn BCNF cho sơ đồ quan hệ và quan hệ. Định nghĩa 1. Giả sử r là một quan hệ trên R, A, B Í R và A ® B. Khi đó ta nói A là tập sinh của B nếu |A| < |B|, Không tồn tại tập con thực sự của A mà xác định hàm cho B Tập C là tập sinh của quan hệ r nếu có một tập D nào đó để C là tập sinh của D. Định lý 2. Giả sử r là quan hệ trên R. Khi đó r là BCNF khi và chỉ khi mọi tập sinh của r đều là khóa. Mệnh đề 3. Cho s = là một sơ đồ quan hệ. Đặt Fn là tập tất cả các thuộc tính thứ cấp của s. Khi đó s là BCNF nếu và chỉ nếu "B Î Ks-1, a Î B : (B - a)+ = B - a. Chứng minh: Dễ thấy nếu s là BCNF thì (B - a)+ = B - a đối với B Î Ks-1 và a Î B. Ngược lại, giả thiết s không là BCNF. Khi đó tồn tại A ®{a}ÎF+ ở đây A+ ¹ R và a Ï A. Bởi mệnh đề 4 ở mục trên, ta có B Î K-1 sao cho A+ÏB. Rõ ràng a Î B và A Í B - a. Từ đó, ta có (B - a)+ = B. Định lý 4. Giả sử r là một quan hệ trên R. Khi đó r là BCNF nếu và chỉ nếu với mọi A Î Mr, a Î A thì {A - a}r+ = A - a, ở đây Mr là hệ bằng nhau cực đại của r. Giả sử A ® B là một phụ thuộc hàm. Chúng ta gọi phụ thuộc hàm này là tầm thường nếu B Í A. Ngược lại trong trường hợp này, chúng ta gọi nó là phụ thuộc hàm không tầm thường. Định lý 5. Giả sử s = là một sơ đồ quan hệ trên R. Khi đó s là BCNF nếu và chỉ nếu với mọi A®B ÎF và A®B không tầm thường thì A+ = R. 2.5 Các thuật toán liên quan Trên cơ sở các định lý đã trình bầy ở trên, ta xây dựng các thuật toán để xác định dạng chuẩn cho các quan hệ và sơ đồ quan hệ cho trước. Thuật toán 1. (kiểm tra một quan hệ có là 3N