A. GIỚI THIỆU

Chương trình Datalog là một phần quan trọng của cơ sở dữ liệu suy diễn. Nhiều công trình nghiên cứu nhằm tìm kiếm những phương pháp ước lượng hiệu quả đối với những truy vấn.

Tiểu luận nhằm giải quyết vấn đề là bằng cách nào để loại bỏ phần thừa của một chương trình Datalog. Phần thừa của một chương trình là một quy tắc thừa hoặc một nguyên tố thừa trong thân của một quy tắc. Loại bỏ một phần thừa nhằm giảm thời gian cần thiết để lượng giá một truy vấn bởi vì nó giảm số lượng những kết nối trong suốt quá trình lượng giá.

Một chương trình datalog thường nhận dữ liệu vào là những quan hệ đối với vị từ EDB và trả lời là những quan hệ đối với vị từ IDB. Quy trình tối ưu hóa yêu cầu tìm kiếm một chương trình có giá nhỏ nhất tương đương với chương trình gốc, sao cho đối với mọi khả năng của đầu vào, chương trình gốc và chương trình được tối ưu tính toán ra cùng một kết quả. Tiểu luận trình bày một số khái niệm như quan hệ bao hàm, quan hệ tương đương, bao hàm đồng dạng, tương đương đồng dạng. Trong đó, tính tương đương đồng dạng hàm chứa tính tương đương. Để cực tiểu một chương trình trong tính tương đương đồng dạng, ta đưa ra một thuật toán để xóa tất cả những quy tắc thừa và nguyên tố thừa trong những quy tắc trong khi vẫn duy trì tương đương đồng dạng. Thời gian thực hiện của thuật toán, trong trường hợp xấu nhất là theo luật số mũ của kích cở của chương trình. Tuy nhiên nếu số lượng đối số của các vị từ hữu hạn thì thời gian thực hiện là đa thức. Trên thực tế, thường số lượng đối số của các vị từ không lớn nên đây là một thuật toán hiệu quả.

Tiểu luận cũng đưa ra một kỹ thuật để cực tiểu hóa chương trình Datalog trong tính tương đương. Đây là một bài toán bất khả quyết, kỹ thuật này không tìm thấy tất cả các phần thừa của một chương trình trong tính tương đương.

Thực ra, chương trình Datalog đã được nghiên cứu sâu và được ứng dụng mạnh mẽ. Tiểu luận không nhằm mục đích đưa ra những vấn đề mới mà chỉ tóm tắt và trình bày lại những tri thức mà bản thân thu nhận được thông qua một thời gian học tập ngắn và qua tham khảo một số tài liệu.

Tiểu luận được trình bày trong ba phần. Phần 1: Đưa ra một số kiến thức cơ sở. Phần 2: Tối ưu hóa những chương trình đề quy trong tính tương đương đồng dạng. Phần này trình bày một thuật toán để tìm và xóa những nguyên tố và quy tắc thừa trong khi vẫn duy trì tính tương đương đồng dạng. Phần 3: Tối ưu hóa những chương trình đệ quy trong tính tương đương. Phần này trình bày một thuật toán để tìm và xóa những nguyên tố và quy tắc thừa trong khi vẫn duy trì tính tương đương, nhưng có thể không tương đương đồng dạn