Một số kết quả về rút gọn bài toán tìm khóa

Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> MỘT SỐ KẾT QUẢ VỀ RÚT GỌN BÀI TOÁN TÌM KHÓA<br /> Vũ Quốc Tuấn1*, Hồ Thuần2<br /> Tóm tắt: Cho S = là một lược đồ quan hệ, trong đó,  = {A1, A2,..., An}<br /> là tập hữu hạn các thuộc tính và F = {L1 R1,...,Lm  Rm | Li, Ri  , i = 1,...,m}<br /> là tập hữu hạn các phụ thuộc hàm đúng trên S. Trong [1], dựa trên ngữ nghĩa quen<br /> thuộc của các phụ thuộc hàm trong mô hình cơ sở dữ liệu quan hệ và thuật toán<br /> tính bao đóng của một tập thuộc tính, các tác giả đã xây dựng được một điều kiện<br /> cần để một tập thuộc tính X   là khóa (theo nghĩa tối tiểu) của S. Tiếp đó, một số<br /> hướng cải tiến cho điều kiện cần thu được cũng đã được xem xét. Trong [2], dựa<br /> trên việc nghiên cứu các toán tử iđêan không tất định (idean non-deterministic<br /> operators) trong khuôn khổ của lý thuyết dàn, các tác giả của [2] cũng đưa ra một<br /> điều kiện cần để một tập thuộc tính là khóa. Như vậy, chúng ta có hai kết quả cho<br /> cùng một bài toán được công bố cách nhau 26 năm mà thoạt nhìn dường như khác<br /> nhau. Trong bài báo này, chúng tôi sẽ chứng minh rằng điều kiện cần trong [2]<br /> chính là một dạng cải tiến của điều kiện cần trong [1]. Mối quan hệ giữa các dạng<br /> của điều kiện cần để một tập thuộc tính là khóa của một lược đồ quan hệ với việc<br /> rút gọn bài toán tìm khóa cũng được chỉ ra.<br /> Từ khóa: Cơ sở dữ liệu quan hệ, Lược đồ quan hệ, Phụ thuộc hàm, Khóa của lược đồ quan hệ.<br /> <br /> 1. MỞ ĐẦU<br /> Trong mục này, một số kết quả trong [1] và [2] được nhắc lại để tiện so sánh.<br /> Lưu ý rằng thuật ngữ khóa dùng ở đây được hiểu theo nghĩa khóa tối tiểu.<br /> Cho S = là một lược đồ quan hệ, trong đó  = {A1, A2,..., An} là tập<br /> hữu hạn các thuộc tính và F = {L1 R1,...,Lm  Rm | Li, Ri  , i = 1,...,m} là tập<br /> hữu hạn các phụ thuộc hàm đúng trên S.<br /> m m<br /> Kí hiệu: L   Li , R   Ri , S là tập tất cả các khóa của S, S = {Kj | Kj là<br /> i 1 i 1<br /> <br /> khóa của S}, G  <br /> K j S<br /> K j là giao của tất cả các khóa của S, H  <br /> K j S<br /> K j là tập tất<br /> <br /> cả các thuộc tính khóa của S, H = \H là tập tất cả các thuộc tính không khóa của S.<br /> Trong [1] đã chứng minh các kết quả sau:<br /> Định lý 1 (Định lý 1 trong [1]). Cho S = là một lược đồ quan hệ và X là<br /> một khóa của S. Khi đó:<br />  \ R  X  ( \ R)  (L  R) (1)<br /> Định lý 2 (Định lý 4 trong [1]). Cho S = là một lược đồ quan hệ. Khi đó<br /> G =  \ R.<br /> Mệnh đề 1 (Trong chứng minh của Định lý 1 trong [1]). Ta có R \ L  H , có<br /> nghĩa các thuộc tính trong R \ L đều là các thuộc tính không khóa.<br /> Từ (1), ta dễ dàng suy ra:<br /> Nhận xét 1. ( \ R)  (L  R) là siêu khóa chứa tất cả các khóa của S. Lưu ý là<br /> trong phân tích  = ( \ R)  (L  R)  (R \ L), chỉ tập L  R có khả năng chứa<br /> cả hai loại thuộc tính là thuộc tính khóa và thuộc tính không khóa. Thêm vào đó,<br /> <br /> <br /> 102 V. Q. Tuấn, H. Thuần, “Một số kết quả về rút gọn bài toán tìm khóa.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> nếu có R \ L ≠  thì siêu khóa ( \ R)  (L  R)   và việc tìm tập tất cá các<br /> khóa chứa trong một siêu khóa nhỏ hơn thực sự  sẽ ít tốn kém hơn. Điều này rõ<br /> ràng liên quan đến việc rút gọn bài toán tìm khóa của một lược đồ quan hệ. Thật<br /> vậy, giả sử đã xác định được Z   là tập chứa tất cả các khóa của lược đồ quan hệ<br /> S = . Khi đó, việc rút gọn bài toán cho việc tìm khóa của S được tiến hành<br /> qua các bước sau:<br /> 1) Xác định lược đồ quan hệ S' = , trong đó, ' = Z \ ( \ R) và<br /> F' = {Li  '  Ri  ' | (Li  Ri)  F, i = 1, 2,..., m}.<br /> 2) Tìm K S ' theo một thuật toán nào đó.<br /> 3) Dễ thấy rằng S = {( \ R)  K | K  S ' }.<br /> Nhận xét 2. Các khóa K j  S không chứa nhau và có cấu trúc chung là K j = ( \<br /> R)  Z j với Z j  L  R<br /> Điều này tạo thuận lợi cho việc xác định các khóa của S.<br /> Nhận xét 3. Trường hợp tồn tại tập Z  H sao cho (L  R)  Z ≠  thì ( \ R) <br /> [(L  R) \ Z] sẽ là một siêu khóa chứa tất cả các khóa của S và siêu khóa này rõ<br /> ràng chứa thực sự trong siêu khóa ( \ R)  (L  R).<br /> Khi đó: ( \ R)  K j  ( \ R)  [(L  R) \ Z],  K j  S<br /> <br /> sẽ là một dạng cải tiến của điều kiện cần (1).<br /> Trong [2, 3], có đưa ra định nghĩa và định lý sau (các ký hiệu được sửa lại cho<br /> phù hợp với hệ thống ký hiệu đã dùng ở trên):<br /> Định nghĩa 1 (Định nghĩa 3.3 trong [3]). Cho S = là một lược đồ quan hệ.<br /> Khi đó lõi (core) và thân (body) của S được định nghĩa như sau:<br />      [ \ core(, F)+]<br /> core(, F) =  \   Ri  và body(, F) = <br />   L <br /> ( Li  Ri )F  ( Li  Ri )F <br /> i<br /> <br /> <br /> <br /> Bằng những tính toán đơn giản, ta nhận được:<br /> core(, F) =  \ R và body(, F) = L  [ \ ( \ R)+]<br /> Ví dụ 1 (Ví dụ 3.1 trong [3]). Cho S = là một lược đồ quan hệ, trong đó,<br /> tập thuộc tính  = {a, b, c, d, e, f, g, h} và tập phụ thuộc hàm F = {ab  c, a  g,<br /> g  c, b  h, bh  d, c  d, e  f, f  e}.<br /> Ta có: L = abcefgh, R = cdefgh,  \ R = ab, ( \ R)+ = abcdgh, L  [  \ ( \<br /> R)+] = ef. Từ đó core(, F) = ab và body(, F) = ef.<br /> Định lý 3 (Định lý 3.4 trong [2, 3]). Cho S = là một lược đồ quan hệ và K<br /> là một khóa (tối tiểu) của S. Khi đó, ta có:<br /> core  K  (core  body), có nghĩa<br />  \ R  K  ( \ R)  [L  [ \ ( \ R)+] ] (2)<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 47, 02 - 2017 103<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> Rõ ràng (2) là phát biểu của một điều kiện cần để K là khóa của S. Chứng minh<br /> của (2) được cho trong [2] cùng với một số ví dụ minh họa.<br /> 2. MỘT DẠNG CẢI TIẾN CHO ĐIỀU KIỆN CẦN (1)<br /> Trong [1] có chứng minh bổ đề sau:<br /> Bổ đề 1 (Bổ đề 3 trong [1]). Cho S = là một lược đồ quan hệ và X là một<br /> khóa của S. Khi đó<br /> X  R  (L \ R)+ = <br /> Bổ đề 1 dễ dàng được mở rộng thành bổ đề 2 dưới đây:<br /> Bổ đề 2. Cho S = là một lược đồ quan hệ. Khi đó<br /> K  R  ( \ R)+ = ,  K  S ,<br /> <br /> có nghĩa R  ( \ R)+  H<br /> Chứng minh. Giả sử ngược lại:  K  K S sao cho K  R  ( \ R)+ ≠ , có nghĩa<br />  A   sao cho A K, A R và theo định nghĩa bao đóng,  \ R  A. Vì A R<br /> nên A   \ R. Từ điều kiện (1) có  \ R  K. Kết hợp với A   \ R, suy ra<br />  \ R  K \ A. Từ đó có K \ A   \ R. Mặt khác  \ R  A. Kết quả là K \ A  A<br /> với A K, chứng tỏ K không là khóa của S. Tóm lại ta đã chứng minh được<br /> K  [R  ( \ R)+] = ,  K  K S ,<br /> <br /> có nghĩa R  ( \ R)+  H<br /> Từ nhận xét 3, định lý sau đây là hiển nhiên.<br /> Định lý 4. Cho S = là một lược đồ quan hệ. Khi đó<br />  \ R  K  ( \ R)  [(L  R) \ (R  ( \ R)+ )],  K  S (3)<br /> Ta xem (3) như một dạng cải tiến của (1).<br /> Sau đây là một ví dụ trong đó (L  R)  (R  ( \ R)+ ) ≠ , có nghĩa<br /> ( \ R)  [(L  R) \ (R  ( \ R)+) ]  ( \ R)  (L  R).<br /> Ví dụ 2. Xét lược đồ quan hệ S = trong đó  = {a, b, c, d, e, f, g, h, i} và<br /> F = {a  b, b  c, d  e, h  i, i  h}.<br /> Với lược đồ quan hệ này, ta có: L = abdhi, R = bcehi, L  R = bhi,  \ R =<br /> adfg;<br /> ( \ R)+ = abcdefg, R  ( \ R)+ = bce. Dễ thấy rằng S = {adfgh, adfgi}. Từ<br /> đó H = {a, d, f, g, h, i} và H = {b, c, e}.<br /> Bổ đề 2 được nghiệm đúng vì R  ( \ R)+ = bce  H .<br /> Hơn nữa, ta còn có (L  R)  [R  ( \ R)+ ] = b ≠ . Và như vậy với lược đồ<br /> quan hệ S được cho trong ví dụ 2, ta có<br /> <br /> <br /> 104 V. Q. Tuấn, H. Thuần, “Một số kết quả về rút gọn bài toán tìm khóa.”<br /> Nghiên cứu khoa học công nghệ<br /> <br />  \ R  K  ( \ R)  [(L  R) \ (R  ( \ R)+ )],  K  S ,<br /> <br /> cụ thể là adfg  K  adfghi với K {adfgh, adfgi}.<br /> 3. SO SÁNH HAI ĐIỀU KIỆN CẦN (2) VÀ (3)<br /> Để dễ so sánh, ta phát biểu lại hai điều kiện cần (2) và (3) như sau:<br /> Cho lược đồ quan hệ S = . Khi đó<br />  \ R  K  ( \ R)  [L  [ \ ( \ R)+ ]],  K  S<br />  \ R  K  ( \ R)  [(L  R) \ (R  ( \ R)+ )],  K  S<br /> <br /> Nhận xét 4. Dễ thấy rằng L  [ \ ( \ R)+ ] = L \ ( \ R)+. Thật vậy, giả sử x  L<br />  [ \ ( \ R)+ ]  x  L, x   \ ( \ R)+  x  L, x  ( \ R)+  x L \ ( \<br /> R)+. Ngược lại, giả sử x L \ ( \ R)+  x  L, x  ( \ R)+  x  L, x   \ ( \<br /> R)+  x  L  [ \ ( \ R)+ ].<br /> Định nghĩa 2. Ta nói rằng điều kiện (2) tốt hơn điều kiện (3) nếu L \ ( \ R)+  (L<br />  R) \ (R  ( \ R)+ ) và tồn tại một lược đồ quan hệ sao cho L \ ( \ R)+  (L <br /> R) \ (R  ( \ R)+ ).<br /> Hiểu theo nghĩa đó, ta thấy điều kiện (3) là một dạng cải tiến của (1). Tương tự,<br /> ta có định nghĩa khi nào thì (3) tốt hơn (2). Để so sánh (2) với (3) ta có định lý sau:<br /> Định lý 5. Hai điều kiện (2) và (3) chỉ là một và được diễn đạt bằng những biểu<br /> thức khác nhau.<br /> Chứng minh. Để chứng minh định lý 5, rõ ràng chỉ cần chứng minh<br /> L \ ( \ R)+ = (L  R) \ (R  ( \ R)+ ) (4)<br /> Giả sử x là một thuộc tính bất kỳ thuộc L \ ( \ R)+.<br />  x  L \ ( \ R)+  (x  L) và x  ( \ R)+  (x  L), x  ( \ R) và x  ( \ R)+<br />  (x  L), x  R và x  ( \ R)+  (x  L  R) và x  [R  ( \ R)+]  x  (L <br /> R) \ [(R  ( \ R)+],<br /> có nghĩa L \ ( \ R)+  (L  R) \ (R  ( \ R)+ ) (5)<br /> Bây giờ ta chứng minh điều ngược lại:<br />  x  (L  R) \ [R  ( \ R)+ ]  (x  L), (x  R) và (x  [R  ( \ R)+])<br />  (x  L), (x  R) và (x  ( \ R)+)  x  L \ ( \ R)+,<br /> có nghĩa (L  R) \ (R  ( \ R)+ )  L \ ( \ R)+ (6)<br /> + +<br /> Kết hợp (5) và (6), ta có: L \ ( \ R) = (L  R) \ (R  ( \ R) ). Định lý 5 được<br /> chứng minh.<br /> Để minh họa cho định lý 5, ta trở lại với ví dụ 1 và 2.<br /> Với ví dụ 1,  = {a, b, c, d, e, f, g, h}, F = {ab  c, a  g, g  c, b  h, bh<br />  d, c  d, e  f, f  e}. Ta có: L = abcefgh, R = cdefgh, L  R = cefgh,  \ R =<br /> ab, ( \ R)+ = abcdgh, R  ( \ R)+ = cdgh.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 47, 02 - 2017 105<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> Từ đó L \ ( \ R)+ = ef và (L  R) \ (R  ( \ R)+ ) = ef.<br /> Với ví dụ 2,  = {a, b, c, d, e, f, g, h, i}, F = {a  b, b  c, d  e, h  i, i  h}.<br /> Ta có: L = abdhi, R = bcehi, L  R = bhi,  \ R = adfg; ( \ R)+ ) = abcdefg, R<br />  ( \ R)+ = bce.<br /> Từ đó: L \ ( \ R)+ = hi và (L  R) \ (R  ( \ R)+ ) = hi.<br /> Liên quan tới các điều kiện cần để một tập thuộc tính K   là khóa của lược<br /> đồ quan hệ S = , ta có thể xem xét và giải quyết bài toán sau.<br /> 4. MỘT BÀI TOÁN QUYẾT ĐỊNH<br /> Cho S = là một lược đồ quan hệ và cho Z  . Bài toán đặt ra là quyết<br /> định xem Z có phải là tập chứa tất cả các khóa của S không?<br /> Giả sử Z chứa tất cả các khóa của S. Điều đó có nghĩa là:<br /> Z H <br /> K j K S<br /> Kj<br /> <br /> <br /> Từ đó  \ Z   \ H = H .<br /> Bổ đề 3. Cho S = là một lược đồ quan hệ và cho Z  . Khi đó Z chứa tất cả<br /> các khóa của S khi và chỉ khi  \ Z chỉ gồm các thuộc tính không khóa, có nghĩa là:<br /> \Z H<br /> Để thấy được ý nghĩa của bổ đề 3, ta trở lại với điều kiện (2), là định lý 3.4<br /> trong [3].<br /> ( \ R)  K  ( \ R)  [L \ ( \ R)+ ],  K  K S<br /> Rõ ràng (2) khẳng định rằng Z = ( \ R)  [L \ ( \ R)+ ] là tập (siêu khóa) chứa<br /> tất cả các khóa của S.<br /> Để kiểm tra tính chất đó, ta có thể dùng bổ đề 3.<br /> Ta có:<br />  \ Z =  \ [( \ R)  (L \ ( \ R)+) ] = R \ (L \ ( \ R)+) = (R \ L)  (R  ( \ R)+)<br /> (Ở đây, với ba tập bất kỳ A, B, C  , ta đã áp dụng một biến đổi quen thuộc<br /> A \ (B \ C) = (A \ B)  (A  C))<br /> Như vậy,  \ Z = R \ (L \ ( \ R)+) = (R \ L)  (R  ( \ R)+)  H (7)<br /> +<br /> Do đã có (R \ L)  H (theo [1]) và R  ( \ R)  H (theo bổ đề 2).<br /> Chứng tỏ Z = ( \ R)  [L \ ( \ R)+ ] là siêu khóa chứa tất cả các khóa của S.<br /> 5. KẾT LUẬN<br /> Trong bài báo này, dựa trên ngữ nghĩa quen thuộc của phụ thuộc hàm trong mô<br /> hình cơ sở dữ liệu quan hệ, chúng tôi đã chứng minh được điều kiện cần (2) (trong<br /> [2, 3]) trùng với điều kiện cần (3) là một dạng cải tiến của điều kiện cần (1) (trong<br /> [1]). Đây là những điều kiện cần để một tập con của  là khóa tối tiểu của lược đồ<br /> <br /> <br /> 106 V. Q. Tuấn, H. Thuần, “Một số kết quả về rút gọn bài toán tìm khóa.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> quan hệ S = . Việc tìm một điều kiện cần tốt hơn (2) hoặc (3) nhằm rút gọn<br /> hơn nữa bài toán tìm khóa là một vấn đề rất đáng quan tâm.<br /> TÀI LIỆU THAM KHẢO<br /> [1]. Ho Thuan and Le Van Bao, "Some results about keys of relational schemas",<br /> Acta Cybernetica, Tom 7, Fasc.1, Szeged, pp. 99-113, 1985.<br /> [2]. A. Mora, I.P. de Guzmán, M. Enciso and P. Cordero, "Ideal non-deterministic<br /> operators as a formal framework to reduce the key finding problem",<br /> International Journal of Computer Mathematics, Vol. 88, No. 9, 1860–1868,<br /> June 2011.<br /> [3]. P. Cordero, M. Enciso, A. Mora, "Automated Reasoning to Infer all Minimal<br /> Keys", In Proceedings of the Twenty-Third International Joint Conference on<br /> Artificial Intelligence, (IJCAI13), F.Rossi ed.,pp.817-823, AAAI Press, 2013.<br /> [4]. Ho Thuan, "Contribution to the theory of relational databases", Tanulmányok<br /> 184/1986, Studies 184/1986, Budapest, Hungary.<br /> ABSTRACT<br /> SOME RESULTS FOR REDUCING THE KEY FINDING PROBLEM<br /> Let S = be a relation schema, where  = {A1, A2,..., An} is a finite<br /> set of attributes and F = {L1 R1,...,Lm  Rm | Li, Ri  , i = 1,...,m} is a<br /> finite set of functional dependencies that hold on S. In [1], using the well-<br /> known semantics of functional dependency in the theory of relational<br /> databases and the algorithm to compute the closure of a subset of attributes, a<br /> necessary condition for which a subset X   is a minimal key for S was<br /> established and some improvements of it were given. In [2], basing on the<br /> study of idean non-deterministic operators in the framework of the lattice<br /> theory, the authors of [2] gave another necessary condition for which a subset<br /> of  is a minimal key for a relation schema S = . Thus, we have two<br /> results for the same problem, the first one was published in 1985 and the last<br /> one, in 2011, and apparently, they seem quite different. In this paper, we show<br /> that the necessary condition in [2] is only an improved version of that one in<br /> [1]. The relationship between the necessary conditions for which a subset of <br /> is a minimal key for the relation scheme S = and the reduction of the<br /> key finding problem was also showed.<br /> Keywords: Relational database, Relation scheme, Functional dependency, Keys for a relation scheme.<br /> <br /> Nhận bài ngày 18 tháng 11 năm 2016<br /> Hoàn thiện ngày 31 tháng 12 năm 2016<br /> Chấp nhận đăng ngày 20 tháng 02 năm 2017<br /> 1<br /> Địa chỉ: Trường Cao đẳng Hải Dương;<br /> 2<br /> Viện Công nghệ thông tin - Viện HLKH-CNVN;<br /> *<br /> Email: vqtuanhd@gmail.com<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 47, 02 - 2017 107<br />