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ệ

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