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

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.
Nội dung trích xuất từ tài liệu:
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àmNghiên cứu khoa học công nghệ 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àngbuộ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ả trongcá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 tronglược đồ quan hệ. Nghiên cứu về bao đóng cũng là một hướng được sử dụng nhiềutrong 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àitoá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ậttoá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ệuquan 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 địnhnghĩ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ácTạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 109 Công nghệ thông tin & Cơ sở toán học cho tin họcthuộ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 đồ quanhệ 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ủabộ 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  rmà 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ộchà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 suydiễ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 s ...