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

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