Một số kết quả liên quan đến rút gọn bài toán tìm khóa của lược đồ quan hệ - Vũ Quốc Tuấn

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 54, 04 - 2018 157 MỘT SỐ KẾT QUẢ LIÊN QUAN ĐẾN RÚT GỌN BÀI TOÁN TÌM KHÓA CỦA LƯỢC ĐỒ QUAN HỆ Vũ Quốc Tuấn1*, Hồ Thuần2 Tóm tắt: Trong [1] đã đưa ra một điều kiện cần để một tập thuộc tính là khóa của lược đồ quan hệ. Trong [2], các tác giả cũng đưa ra một điều kiện cần khác để một tập thuộc tính là khóa của lược đồ quan hệ. Trong [3] đã chỉ ra rằng chỉ cần cải tiến điều kiện cần trong [1] theo một cách tiếp cận đơn giản hơn thì có thể suy ra được điều kiện cần trong [2]. 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] thực sự là trùng với kết quả đã được công bố trong [4]. 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 [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 là khóa. 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 (ideal 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. Trong [3] đã chỉ ra rằng chỉ cần cải tiến điều kiện cần trong [1] theo một cách tiếp cận khác đơn giản hơn thì có thể suy ra được điều kiện cần trong [2]. 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] thực sự là trùng với kết quả đã được công bố trong [4]. Bài báo được tổ chức như sau: phần thứ hai nhắc lại một số khái niệm và kết quả quan trọng của mô hình quan hệ. Phần thứ ba trình bày lại một số kết quả và nhận xét trong [1, 2, 3, 4] để tiện so sánh, đồng thời chứng minh điều kiện cần trong [2] trùng với kết quả trong [4]. Kết luận được giới thiệu trong phần thứ tư. 2. MÔ HÌNH QUAN HỆ Phần này nhắc lại một số khái niệm quan trọng trong mô hình dữ liệu quan hệ nhằm mục đích sử dụng cho các phần tiếp theo. 2.1. Lược đồ quan hệ Lược đồ quan hệ. Một lược đồ quan hệ S là một cặp có thứ tự S = , trong đó  là tập hữu hạn các thuộc tính của quan hệ, F là tập các ràng buộc giữa các thuộc tính. Cho lược đồ quan hệ S = với  = {A1, A2,..., An}. Nếu không quan tâm đến tập các ràng buộc F thì ta sẽ dùng ký hiệu S() thay cho S = . Ta dùng ký hiệu r(S) để chỉ một quan hệ r (hay một thể hiện r) của lược đồ quan hệ S. Với một bộ t của r(S) và X   , ta ký hiệu t[X] là bộ chỉ chứa các giá trị của bộ t tại các thuộc tính trong X. 2.2. Phụ thuộc hàm Phụ thuộc hàm. Cho  là tập thuộc tính và S() là một lược đồ quan hệ trên . Giả sử X, Y  . Khi đó Y được gọi là phụ thuộc hàm vào X trên lược đồ S(), ký 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ả liên quan tìm khóa của lược đồ quan hệ.” 158 hiệu là X  Y, nếu với mọi quan hệ r trên lược đồ S() và  t1, t2  r, t1[X] = t2[X]  t1[Y] = t2[Y] Nếu Y phụ thuộc hàm vào X thì ta cũng nói "X xác định hàm Y". Với mỗi quan hệ r trên lược đồ S(), ta nói r thỏa mãn (hay thỏa) phụ thuộc hàm X  Y (hay phụ thuộc hàm X  Y đúng trên r) nếu và chỉ nếu  t1, t2  r, t1[X] = t2[X]  t1[Y] = t2[Y] Trong bài báo này, ta hạn chế F (của lược đồ S = ) chỉ gồm các phụ thuộc hàm. 2.3. Hệ quy tắc suy diễn Armstrong Hệ quy tắc suy diễn Armstrong. Với lược đồ quan hệ S = và X, Y  , ta ký hiệu XY thay cho X  Y. Với mọi X, Y, Z  , hệ quy tắc suy diễn Armstrong đối với các phụ thuộc hàm gồm ba quy tắc sau đây: A1. (Phản xạ): Nếu Y  X thì X  Y. A2. (Gia tăng): Nếu X  Y thì XZ  YZ. A3. (Bắc cầu): Nếu X  Y và Y  Z thì X  Z. Ký hiệu F+ là tập tất cả các phụ thuộc hàm được suy diễn từ F bằng cách áp dụng một số hữu hạn lần các quy tắc của hệ quy tắc suy diễn Armstrong. 2.4. Bao đóng của một tập thuộc tính Bao đóng của một tập thuộc tính. Cho tập phụ thuộc hàm F xác định trên tập thuộc tính  (phụ thuộc hàm Y  Z xác định trên tập thuộc tính  nếu Y, Z  ) và X  . Ta gọi bao đóng của tập thuộc tính X đối với tập phụ thuộc hàm F, ký hiệu là FX , là tập tất cả các thuộc tính A của  sao cho X  A được suy diễn từ F nhờ hệ quy tắc suy diễn Armstrong.  FX = {A    (X  A)  F +}. 2.5. Khóa của lược đồ quan hệ Khóa của lược đồ quan hệ. Cho lược đồ quan hệ S = và K  . Ta nói K là một khóa của S nếu hai điều kiện sau đây đồng thời được thỏa mãn: (i). (K  )  F+ (ii). Nếu K'  K thì (K'  )  F+. Nếu K thỏa mãn điều kiện (i) thì K được gọi là một siêu khóa. Như vậy, mọi khóa của S = đều là siêu khóa của S = . 3. MỘT SỐ KẾT QUẢ 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   Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 54, 04 - 2018 159 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. 3.1. Một số kết quả đã biết Định lý 1 (Định lý 1 trong [1]). Cho S = là một lược đồ quan hệ và K là một khóa của S. Khi đó: ( \ R)  K  ( \ R)  (L  R) (1) 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. Thêm vào đó, nếu ( \ R)  (L  R)   thì 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 'S 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). Định lý 2 (Định lý 2 trong [4]). Cho S = là một lược đồ quan hệ và K là một khóa của S. Khi đó: ( \ R)  K  ( \ R)  [(L  R) \ ( \ R)+] (2) Dễ thấy rằng (2) là một dạng cải tiến của (1). Ví dụ 1 sau đây cho thấy [(L  R) \ ( \ R)+]  (L  R) Ví dụ 1 (Ví dụ trong [4]). Cho S = là một lược đồ quan hệ, trong đó tập 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ả liên quan tìm khóa của lược đồ quan hệ.” 160 thuộc tính  = {a, b, c, g, h} và tập phụ thuộc hàm F = {a  b, b  c, g  h, h g}. Ta có: L = abgh R = bcgh  \ R = a ( \ R)+ = abc (L  R) = bgh (L  R) \ ( \ R)+ = gh  (L  R) Mệnh đề 1 (Trong chứng minh của Định lý 2 trong [4]). Cho S = là một lược đồ quan hệ. Khi đó ( \ R)+ \ ( \ R)  H , có nghĩa các thuộc tính trong ( \ R)+ \ ( \ R) đều là các thuộc tính không khóa. Nhận xét 4. Ở đây để dễ theo dõi, chúng tôi trình bày chi tiết hơn cách thức suy ra (2) từ (1). Thật vậy, từ (1) và kết quả trong mệnh đề 1, ta có: ( \ R)  K  ( \ R)  [(L  R) \ [( \ R)+ \ ( \ R)]] (a) Sử dụng hệ thức quen thuộc giữa ba tập hợp A, B, C bất kỳ A \ (B \ C) = (A \ B)  (A  C) ta suy ra [(L  R) \ [( \ R)+ \ ( \ R)]] = [(L  R) \ ( \ R)+]  [(L  R)  ( \ R)] = [(L  R) \ ( \ R)+] vì [(L  R)  ( \ R)] =  (b) Kết hợp (a) và (b) ta nhận được (2). Trong [2, 5], 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 (Định nghĩa 3.3 trong [5]). 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          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 body(, F) = L  [ \ ( \ R)+] Ví dụ 2 (Ví dụ 3.1 trong [5]). 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}. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 54, 04 - 2018 161 Ta có: L = abcefgh R = cdefgh  \ R = ab ( \ R)+ = abcdgh L  [  \ ( \ R)+] = ef Từ đó: core(, F) = ab body(, F) = ef. Định lý 3 (Định lý 3.4 trong [2, 5]). 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)+] ] (3) Mệnh đề 2 (Nhận xét 4 trong [3]). Cho S = là một lược đồ quan hệ. Khi đó L  [ \ ( \ R)+ ] = L \ ( \ R)+ 3.2. So sánh hai điều kiện cần (2) và (3) Rõ ràng (2) và (3) đều là các điều kiện cần để một tập thuộc tính là khóa của lược đồ quan hệ. Điều kiện (2) được công bố năm 1996, trong khi điều kiện (3) được công bố năm 2011. Định lý sau chỉ rõ mối quan hệ giữa (2) và (3). Định lý 4. 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. Từ kết quả trong mệnh đề 2, điều kiện cần (3) được viết lại thành:  \ R  K  ( \ R)  [L \ ( \ R)+] Để chứng minh (2) và (3) chỉ là một, ta sẽ chỉ ra rằng [(L  R) \ ( \ R)+] = [L \ ( \ R)+] Thật vậy, rõ ràng ta có (L  R)  L nên [(L  R) \ ( \ R)+]  [L \ ( \ R)+] Ta chỉ cần chứng minh điều ngược lại là L \ ( \ R)+  (L  R) \ ( \ R)+ Giả sử x là một thuộc tính bất kỳ thuộc [L \ ( \ R)+]  x  L, x  ( \ R)+  x  L, x  ( \ R), x  ( \ R)+  x  L, x  R, x  ( \ R)+  x  (L  R) \ ( \ R)+. 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ả liên quan tìm khóa của lược đồ quan hệ.” 162 4. KẾT LUẬN Trong bài báo này, với việc rút gọn bài toán tìm khóa, chúng tôi đã trình bày chi tiết hơn cách thức suy ra (2) từ (1), đồng thời đã chứng minh được điều kiện cần (2) trùng với điều kiện cần (3). Đây là những điều kiện cần để một tập con của  là khóa của lược đồ 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]. Vũ Quốc Tuấn và Hồ thuần, "Một số kết quả về thuật toán tính bao đóng và rút gọn bài toán tìm khóa của lược đồ quan hệ", Kỷ yếu Hội thảo Quốc gia lần thứ XX, Một số vấn đề chọn lọc của CNTT và TT, Quy Nhơn-Bình Định 23- 24/11/2017, tr.174-180. [4]. Ho Thuan, Souafi Souad and Mohamed Benkada Djamila, "Some more properties and remarks about keys for relation scheme", Tạp chí Tin học và Điều khiển học, T.12, S.4 (1996) (101-113). [5] P. Cordero, M. Enciso and 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. ABSTRACT SOME RESULTS RELATED TO REDUCING THE KEY FINDING PROBLEM OF A RELATION SCHEMA In [1], it has proposed a necessary condition for a set of attributes to be a key of a relation schema. In [2], A. Mora et al. have proposed another necessary condition for a set of attributes to be a key of a relation schema. In [3], it has been shown that we could get the necessary condition in [2] by improving the necessary condition in [1] in a simpler approach. In this paper, we will prove that the necessary condition in [2] actually coincides with the result published in [4]. Keywords: Relational database, Relation schema, Functional dependency, Key for a relation schema. Nhận bài ngày 18 tháng 11 năm 2017 Hoàn thiện ngày 31 tháng 12 năm 2017 Chấp nhận đăng ngày 10 tháng 4 năm 2018 Đị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.