Một số kết quả về thuật toán tính bao đóng và rút gọn bài toán tìm khóa của lược đồ quan hệ
Abstract
Trong lĩnh vực trí tuệ nhân tạo và cơ sở dữ liệu quan hệ, khóa của lược đồ quan hệ và 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, chuẩn hóa lược đồ quan hệ, loại bỏ ràng buộc dư thừa, v.v. Do đó, độ phức tạp của thuật toán tìm bao đóng và việc rút gọn bài toán tìm khóa là các vấn đề luôn được quan tâm. Trong vài năm gần đây, các vấn đề này được xới lại với hàng loạt các công trình mới 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, chúng tôi đề xuất một thuật toán cải tiến tính bao đóng và đưa ra một số kết quả về rút gọn bài toán tìm khóa nhằm nâng cao hiệu năng tính toán khi giải quyết các vấn đề có liên quan.References
C. Beeri and P. A. Bernstein, “Computational problems related to the design of normal form relational schemas,” ACM Transactions on Database Systems (TODS), vol. 4, no. 1, pp. 30–59, 1979.
J. Diederich and J. Milton, “New methods and fast algorithms for database normalization,” ACM Transactions on Database Systems (TODS), vol. 13, no. 3, pp. 339–365, 1988.
J. Paredaens, P. De Bra, M. Gyssens, and D. Van Gucht, “The Structure of the Relational Database Model,” EATCS Monographs on Theoretical Computer Science, vol. 17, 1989.
A. Mora, G. Aguilera, M. Enciso, P. Cordero, and I. P. de Guzmán, “A new closure algorithm based in logic: SLFDClosure versus classical closures,” Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial, vol. 10, no. 31, pp. 31–40, 2006.
H. Thuan and L. V. Bao, “Some results about key of relational schemas,” Acta Cybernetica, vol. 7, no. 1, pp. 99–113, 1985.
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, pp. 1860–1868, 2011.
P. Cordero, M. Enciso, and A. Mora, “Automated reasoning to infer all minimal keys,” in Proceedings of the TwentyThird International Joint Conference on Artificial Intelligence (IJCAI), 2013, pp. 817–823.
