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. | 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ệ 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
