Một thuật toán mới tính bao đóng của tập thuộc tính đối với một tập phụ thuộc hàm - Hồ Thuần

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 109 MỘT THUẬT TOÁN MỚI TÍNH BAO ĐÓNG CỦA TẬP THUỘC TÍNH ĐỐI VỚI MỘT TẬP PHỤ THUỘC HÀM Hồ Thuần1, Vũ Quốc Tuấn2* Tóm tắt: Trong lĩnh vực trí tuệ nhân tạo và cơ sở dữ liệu quan hệ, bao đóng của một tập thuộc tính đối với một tập phụ thuộc hàm có vai trò quan trọng và được sử dụng trong nhiều bài toán như tối ưu hóa truy vấn, tìm kiếm khóa, loại bỏ ràng buộc dư thừa, Do đó, độ phức tạp của thuật toán tìm bao đóng là vấn đề luôn được quan tâm. Trong vài năm gần đây, vấn đề này được xới lại với hàng loạt các công trình mới [6, 7, 8, 9, 10, 11, 12, 13, 14, 15] nhằm giải quyết bài toán tính bao đóng và tìm tập các khóa của lược đồ quan hệ một cách hiệu quả hơn theo nhiều tiếp cận khác nhau. Trong bài báo này, trên cơ sở một thuật toán của A. Mora và cộng sự [1], chúng tôi đề xuất một thuật toán cải tiến tính bao đóng nhằm nâng cao hiệu năng tính toán khi giải quyết các bài toán có liên quan. Từ khóa: Cơ sở dữ liệu quan hệ, Lược đồ quan hệ, Phụ thuộc hàm, Bao đóng của tập thuộc tính. 1. MỞ ĐẦU Cơ sở dữ liệu là một hướng nghiên cứu quan trọng của công nghệ thông tin và đã được ứng dụng thành công trong nhiều lĩnh vực. Phụ thuộc hàm là một loại ràng buộc dữ liệu giữa các thuộc tính trong một quan hệ. Tính nhất quán dữ liệu có thể được bảo đảm nhờ sử dụng các phụ thuộc hàm để loại bỏ dữ liệu dư thừa, phụ thuộc hàm cũng thể hiện ngữ nghĩa giữa các thuộc tính và có thể tồn tại cả trong các tập dữ liệu độc lập với mô hình quan hệ. Bao đóng của tập thuộc tính liên quan chặt chẽ đến các phụ thuộc hàm trong lược đồ quan hệ. Nghiên cứu về bao đóng cũng là một hướng được sử dụng nhiều trong lĩnh vực trí tuệ nhân tạo và cơ sở dữ liệu, đồng thời là một trong những vấn đề quan trọng trong nhiều bài toán: phát hiện tri thức, loại bỏ dữ liệu dư thừa, tối ưu hóa truy vấn, tìm kiếm khóa,... Sử dụng bao đóng có thể biết được một phụ thuộc hàm có được suy diễn từ một tập phụ thuộc hàm cho trước hay không (bài toán thành viên). Bài báo này trình bày một thuật toán mới tính bao đóng của một tập thuộc tính, là một cải tiến của thuật toán tính bao đóng của nhóm tác giả A. Mora và cộng sự được trình bày trong [1]. Ưu điểm của thuật toán này là hiệu quả hơn các thuật toán tính bao đóng đã được đề xuất. 2. CÁC KHÁI NIỆM CƠ BẢN Phần này nhắc lại một số khái niệm quan trọng trong lý thuyết cơ sở dữ liệu quan hệ nhằm mục đích sử dụng cho các phần tiếp theo. Quan hệ. Một quan hệ r xác định trên tập thuộc tính  = {A1, A2,..., An} được định nghĩa như sau: r  {(a1, a2,..., an)  ai  Dom(Ai), i = 1, 2,..., n}, trong đó, Dom(Ai) là miền trị của thuộc tính Ai, i = 1, 2,..., n. 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 Công nghệ thông tin & Cơ sở toán học cho tin học H. Thuần, V. Q. Tuấn, “Một thuật toán mới đối với một tập phụ thuộc hàm.” 110 thuộc tính. Một ràng buộc trên tập thuộc tính {A1, A2,..., An} là một tính chất trên tập tất cả các quan hệ xác định trên tập thuộc tính này. 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(A1, A2,..., An) hoặc 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 . 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ý hiệu là X  Y, nếu với mọi quan hệ r trên lược đồ S(), với hai bộ bất kỳ t1, t2  r mà t1[X] = t2[X] thì 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 với mọi bộ t1, t2  r, t1[X] = t2[X] kéo theo t1[Y] = t2[Y]. Cho F là tập phụ thuộc hàm trên lược đồ quan hệ S(). Ta nói X  Y được suy diễn logic từ F, ký hiệu là F | (X  Y), nếu với mọi quan hệ r trên S(), r thỏa F (r thỏa mọi phụ thuộc hàm trong F) thì r thỏa X  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. Ta gọi bao đóng của tập phụ thuộc hàm F, ký hiệu là F*, là tập tất cả các phụ thuộc hàm được suy diễn logic từ F. F* = {X  Y  F | (X  Y)} 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à Ai1, Ai2,..., Aij thay cho {Ai1, Ai2,..., Aij}. 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. Trong [5], Armstrong đã chứng minh rằng hệ quy tắc Armstrong là xác đáng (sound) và đầy đủ (complete), có nghĩa là F+ = F*. 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. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 111  FX = {A    (X  A)  F +}. 3. MỘT SỐ THUẬT TOÁN ĐÃ BIẾT TÍNH BAO ĐÓNG CỦA MỘT TẬP THUỘC TÍNH Thuật toán 1. Thuật toán chuẩn tính bao đóng X+ Input: , F, X   Output: X+ Begin X+ = X; Repeat For each (Y  B)  F do If Y  X+ and B  X+ then X+ = X+  {B}; End if; End for each; Until không còn thuộc tính nào được thêm vào X+; Return X+; End; Dễ chứng minh rằng độ phức tạp thời gian của thuật toán 1 là O(n.p.min{n,p}) trong đó n là số thuộc tính trong  và p là số phụ thuộc hàm trong F. Như vậy thuật toán 1 không là tuyến tính theo tích np. Các thuật toán 2, 3, 4 sau đây sử dụng một số cấu trúc dữ liệu nhằm giảm chi phí của việc duyệt các tập F và  và như vậy giảm chi phí của việc tính X+. Các chiến lược rút gọn bao gồm: (i). Dùng một tập để lưu giữ các thuộc tính còn phải thêm vào bao đóng. (ii). Dùng một mảng được đánh chỉ số bởi các thuộc tính Ai để lưu giữ các phụ thuộc hàm có vế trái chứa Ai. (iii). Lưu giữ số thuộc tính thuộc vế trái của mỗi phụ thuộc hàm còn chưa có mặt trong bao đóng. Các chiến lược này đã giúp các nhóm tác giả xây dựng được các thuật toán tuyến tính tính bao đóng, tức có độ phức tạp thời gian là O(n.p). Thuật toán 2. Thuật toán tuyến tính tính bao đóng X+ của Beeri [2] Input: , F, X   Output: X+ Begin For i = 1 to n do AttrList[i] = NIL; For j = 1 to m do If Ai  FDj.lsh then AttrList[i] = AttrList[i]  {j}; End if; End for; End for; For j = 1 to m do Công nghệ thông tin & Cơ sở toán học cho tin học H. Thuần, V. Q. Tuấn, “Một thuật toán mới đối với một tập phụ thuộc hàm.” 112 Counter[j] = || FDj.lhs ||; End for; X+, AddedAttr = X; While (AddedAttr  ) do AddedAttr = AddedAttr - Ai; For each FDj  AttrList[i] do Counter[j] = Counter[j] - 1; If (Counter[j] = 0) then AddedAttr = AddedAttr  (FDj.rhs - X +); X+ = X+  FDj.rsh; End if; End for each; End while; Return X+; Thuật toán 3. Thuật toán tuyến tính tính bao đóng X+ của Diederich [3] Input: , F, X   Output: X+ Begin X+ := X; UPDATE := X; For each A B do COUNT[A B] := |A|; End for each; For each thuộc tính Ai Xây dựng LIST[Ai]; End for each; While UPDATE   do Chọn và loại bỏ một thuộc tính Ai từ UPDATE; For each A B  LIST[Ai]; Giảm COUNT[A B]; If COUNT[A B] = 0 then Bổ sung B vào UPDATE và X+ nếu B chưa có trong X+; End if; End for each; End while; Return X+; Thuật toán 4. Thuật toán tuyến tính tính bao đóng X+ của Paredaens [4] Input: , F, X   Output: X+ Begin X+ = ; XWAIT = X; For each XY  F do NOTIN(VY) = |V|; Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 113 If X =  then XWAIT = XWAIT  Y; End if; For each A  X do INLFD[A] = INLFD[A]  {XY}; End for each; End for each; While XWAIT   do For each Ak  XWAIT do XWAIT = XWAIT - {Ak}; X+ = X+  {Ak}; For each XY  INLFD(Ak) do NOTIN(XY) = NOTIN(XY) - 1; If NOTIN(XY) = 0 then XWAIT = XWAIT  {Y - X+}; End if; End for each; End for each; End while; Return X+; 4. THUẬT TOÁN TÍNH BAO ĐÓNG CỦA NHÓM A.MORA VÀ CỘNG SỰ Thuật toán 5. Thuật toán tính bao đóng X+ [1] Input: , F, X   Output: X+ Begin Xnew := X; Xold := X; Repeat Xold := Xnew; For each A B  F do If A  Xnew then Xnew := Xnew  B; (I) F = F - {A B}; elseif B  Xnew then F = F - {A B}; (II) else F = F - {A B}; (III) F = F  {A-Xnew  B-Xnew}; (III) End if; End for each; Until ((Xnew = Xold) or (|F| = 0)); Return X+ = Xnew; Công nghệ thông tin & Cơ sở toán học cho tin học H. Thuần, V. Q. Tuấn, “Một thuật toán mới đối với một tập phụ thuộc hàm.” 114 End; Thuật toán 5 và một số thuật toán tính bao đóng đã được thử nghiệm trong [1], cụ thể như sau: sinh ngẫu nhiên tập thuộc tính , tập phụ thuộc hàm F và tập con X  ; các tập phụ thuộc hàm được sinh ngẫu nhiên lần lượt có 25, 50, 75, 100, 125, 150, 175 và 200 phụ thuộc hàm, số lượng các thuộc tính ở vế trái và vế phải của các phụ thuộc hàm biến đổi từ 1 đến 300, kích thước của các tập phụ thuộc hàm từ 50 đến 61770 thuộc tính (kích thước của một tập phụ thuộc hàm F được định nghĩa là tổng các kích thước của các phụ thuộc hàm trong F; kích thước của X Y là |X| + |Y|); thực hiện thử nghiệm các thuật toán 1817 lần. Kết quả thử nghiệm cho thời gian tính toán của 1817 lần thực hiện được cho trong bảng sau (thời gian trung bình tính theo đơn vị 1/100 giây): Bảng 1. Kết quả thử nghiệm các thuật toán tính bao đóng. Thuật toán Trung bình Thuật toán tính bao đóng X+ của Diederich 4593,48 Thuật toán tính bao đóng X+ của Beeri 7013,56 Thuật toán tính bao đóng X+ của Paredaens 5863,35 Thuật toán tính bao đóng của nhóm A. Mora và cộng sự (Thuật toán 5) 1262,41 Từ bảng kết quả trên, ta thấy thuật toán 5 tiêu tốn ít thời gian hơn bốn thuật toán còn lại. 5. THUẬT TOÁN MỚI TÍNH BAO ĐÓNG CỦA MỘT TẬP THUỘC TÍNH Thuật toán 6. Tính bao đóng X+ INPUT: , X  , F OUTPUT: X+ Begin Xnew = X; Repeat Xold = Xnew; For each Y  Z  F do If (Z  Xnew) then F = F - {Y  Z } (I) else If (Y  Xnew) then begin Xnew = Xnew  Z; F = F - {Y  Z } end (II) else begin F = F - {Y  Z }; F = F  {Y-Xnew  Z-Xnew }; end; (III) End if; End for each; Until (Xnew = Xold) or (|F| = 0); Return Xnew; End; Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 115 Chứng minh. Ta chỉ cần chỉ ra rằng việc thay thế Y  Z bởi Y-Xnew  Z-Xnew (1) không có ảnh hưởng gì đến quá trình tính bao đóng. Thật vậy, thuật toán 6 sẽ thay thế Y  Z bởi Y-Xnew  Z-Xnew trong trường hợp cả Y và Z đều không phải là tập con của Xnew. Do đó, từ (1) ta suy ra Y-Xnew ≠  vì nếu Y-Xnew =  thì Y là tập con của Xnew (mâu thuẫn). Mặt khác, ta luôn có (Y-Xnew)  (Y  Xnew) = Y (2) Giả sử sau phép thay thế (1), Xnew thay đổi và nhận giá trị mới là Xnew1 với Xnew  Xnew1. Bây giờ ta phải chứng minh (Y-Xnew)  Xnew1 khi và chỉ khi Y  Xnew1 (3). + Từ Y  Xnew1 ta có Y-Xnew  Xnew1 (i) + Do (Y-Xnew)  Xnew1, (Y  Xnew)  Xnew  Xnew1 và (2) nên Y = (Y-Xnew)  (Y  Xnew)  Xnew1 (ii) Từ (i) và (ii) ta suy ra (3) được chứng minh. Tính đúng đắn trong thuật toán 5 không được chứng minh. Hơn nữa, nhược điểm của nó là mỗi lần duyệt tập F, tất cả các FD có vế trái và vế phải cùng chứa trong Xnew vẫn được sử dụng để tính Xnew (điều này làm mất thời gian không cần thiết vì giá trị Xnew thực chất không thay đổi). Thuật toán 6 tránh được sự không cần thiết này vì thực hiện loại bỏ ngay các FD có vế phải chứa trong Xnew nên thời gian thực hiện nhanh hơn so với thuật toán 5. Ví dụ. Cho F = {d  a, ad  c, e  bi, ke  m, ce  ik, d  bei, h  cde}. Tính bao đóng của tập thuộc tính X = acd theo thuật toán 6. Giải Bảng 2. Minh họa thuật toán 6. F d  a ad  c e  bi ke  m ce  ik d  bei h  cde Xnew F acd (I)  (I)  e  bi ke  m (III) eik acdbei (II)  (I)  Xnew F acdbei (I)  (III) k  m acdbeik (II)  Xnew F acdbeik acdbeikm (II)  Trong bảng 2, kí hiệu (I), (II), (III) tương ứng với (I), (II), (III) trong thuật toán 6 được áp dụng; kí hiệu  là phụ thuộc hàm trong cột tương ứng bị loại bỏ khỏi F. Kết quả ta được X+ = acdbeik. So với thuật toán 5, ta thấy có 4 vị trí (các ô có màu xám) chứng tỏ thuật toán 6 thực hiện hiệu quả hơn. Chẳng hạn, với (d  a) hoặc (ad  c) hoặc (e  bi) thì thuật toán 6 chỉ cần kiểm tra vế phải và loại bỏ ngay trong khi thuật toán 5 phải kiểm tra vế trái rồi hợp vế phải vào Xnew (nhưng thực sự Xnew không thay đổi) sau đó mới loại bỏ. Như vậy, chỉ với 3 phụ thuộc hàm trên, thuật toán 6 đã tiết kiệm được 6 thao tác tính toán vô ích so với thuật toán 5. Công nghệ thông tin & Cơ sở toán học cho tin học H. Thuần, V. Q. Tuấn, “Một thuật toán mới đối với một tập phụ thuộc hàm.” 116 6. KẾT LUẬN Bằng thực nghiệm, thuật toán 5 đã chứng tỏ có thời gian thực hiện nhanh hơn 4 thuật toán tính bao đóng đã biết. Thuật toán 6 rõ ràng là hiệu quả hơn thuật toán 5 vì quá trình tính toán có sự thay thế các FD bởi các FD đơn giản hơn (như thuật toán 5); đặc biệt là trong nhiều trường hợp, quá trình tính bao đóng và tập F được đơn giản đi rất nhiều vì tất cả các FD có vế phải chứa trong Xnew đều bị loại bỏ trước khi xây dựng bao đóng (đây chính là điểm mới của thuật toán 6 so với thuật toán 5). Ngoài ra, tính đúng đắn của thuật toán 5 không được nhóm tác giả A.Mora và cộng sự chứng minh khi thực hiện phép thay thế các phụ thuộc hàm bằng các phụ thuộc hàm đơn giản hơn, chúng tôi cũng đã thực hiện sự chứng minh tính đúng đắn này trong thuật toán 6. TÀI LIỆU THAM KHẢO [1]. A. Mora, G. Aguilera, M. Enciso, P. Cordero, I.P. de Guzmán, "A new closure algorithm based in logic: SLFD-Closure versus classical closures", Inteligencia Artificial Vol. 10, No31, pp. 31-40, 2006. [2]. C. Beeri and P. A. Bernstein. "Computational Problems related to the design of normal form relational schemas". ACM Transactions on Database Systems, 4 (1): 30-59, 1979. [3]. Jim Diederich and Jack Milton. "New methods and fast algorithms for database normalization". ACM Transactions on Database Systems, 13 (3):339-365, 1988. [4]. Jan Paredaens, Paul De Bra, Marc Gyssens, and Dirk Van Van Gucht. "The structure of the relational database model". EATCS Monographs on Theoretical Computer Science. Ed. Springer-Verlag New York, Inc.,1989. [5]. William W. Armstrong. "Dependency structures of data base relationships". Proc. IFIP Congress. North Holland, Amsterdam, pages 580-583, 1974. [6]. P. Cordero, A. Mora, I.P. de Guzmán, M. Enciso, "Non-deterministic ideal operators: An adequate tool for formalization in Data Bases", Discrete Applied Mathematics 156 (2008) 911-923. [7]. 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, June 2011, 1860–1868. [8]. A. Mora and P. Cordero and M. Enciso and I. P. de Guzmán and G. Aguilera, "Closure via Functional Dependence Simplication" - special issue CMMSE 2010, International Journal of Computer Mathematics Vol. 00, No. 00, January 2008,1-13. [9]. P. Cordero, M. Enciso, A. Mora, "Automated Reasoning to Infer all Minimal Keys", Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pages 817-823, 2013. [10].Cotelea Vitalie, "An approach for testing the primeness of attributes in relational schemas", Computer Science Journal of Moldova, vol.17, no.1(49), 2009. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 117 [11].Amir Hassan Bahmani, Mahmoud Naghibzadeh, Behnam Bahmani, "Automatic database normalization and primary key generation", Electrical and Computer Engineering, pages 000011-000016, 2008. [12]. P. Cordero, M. Enciso, A. Mora and I. Pérez de Guzmán, "A tableaux-like method to infer all minimal keys", DOI:10.1093/jigpal/jzu025, Advance Access published 24 September 2014. [13]. Zhang Yi-Shun, "Determining All Candidate Keys Based on Karnaugh Map", International Conference on Information Management, Innovation Management and Industrial Engineering, pages 226-229, 2009. [14].Ali Muhammad Ali Rushdi and Omar Mohammed Ba-Rukab, "Map Derivation of the Closures for Dependency and Attribute Sets and all Candidate Keys for a Relational Database", JKAU: Eng. Sci., Vol. 25 No.2, pp: 3- 33 (2014 A.D. / 1435 A.H.). [15].Subhrajyoti Bordoloi and Bichitra Kalita, "A graph based approach to find candidate keys in a relational database scheme", International Journal of Computer Engineering and Technology (IJCET), Volume 4, Issue 6, pp. 219- 231, 2013. ABSTRACT A NEW ALGORITHM FOR COMPUTING THE CLOSURE OF A SET OF ATTRIBUTES UNDER A SET OF FUNCTIONAL DEPENDENCIES In an artificial intelligence and relational databases, the closure of a set of attributes under a set of functional dependencies plays an important role and is used in several problems such as query optimization, key finding, removing redundant constraints,... Therefore, the complexity of closure computing algorithms is always an interesting problem. In recent years, this problem has been renewed with a series of new works [6, 7, 8, 9, 10, 11, 12, 13, 14, 15] in order to solve more efficiently the closure computing problem and find the set of all keys of a relation schema in several different approaches. In this paper, based on an algorithm of the authors A. Mora et al [1], we propose an improved closure computing algorithm to enhance performance in the process of solving related problems. Keywords: Relational database, Relation schema, Functional dependency, Closure of a set of attibutes. Nhận bài ngày 20 tháng 09 năm 2016 Hoàn thiện ngày 24 tháng 10 năm 2016 Chấp nhận đăng ngày 26 tháng 10 năm 2016 Địa chỉ: 1 Viện Công nghệ thông tin- Viện HLKH-CNVN; 2 Trường Cao đẳng Hải Dương. * Email: vqtuanhd@gmail.com