Một số kết quả về rút gọn bài toán tìm khóa - Vũ Quốc Tuấn

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