Cơ Sở Dữ Liệu Suy Diễn Luận Văn Thạc Sĩ Tại Đại Học Quốc Gia Hà Nội

Luận văn nghiên cứu các kỹ thuật tối ưu câu truy vấn trên CSDL suy diễn được viết trong Datalog, là ngôn ngữ chuẩn của CSDL suy diễn. Có ba kiểu tiếp cận khác nhau trong việc định giá câu truy vấn: các phương pháp trên xuống, các phương pháp dưới lên và các phương pháp có sự kết hợp các đặc trưng của phương pháp trên xuống và dưới lên. Các phương pháp trên xuống (còn gọi là suy luận đích hoặc kết xâu lùi) có điểm khởi đầu của việc tính toán là từ đích truy vấn và chúng sẽ không tính các sự kiện không thích hợp với câu truy vấn. Tuy nhiên quá trình tính toán có thể kéo dài vô hạn.

Các phương pháp dưới lên đảm bảo tính kết thúc trong quá trình tìm lời giải của câu truy vấn, nhưng điều này không có nghĩa là nó hiệu quả. Chúng thường không định hướng đích, nhiều sự kiện không thích hợp với câu truy vấn cũng được tính. Các chiến lược dưới lên không xem xét câu truy vấn trong suốt quá trình định giá, tức là việc tính toán không được gắn liền với câu truy vấn như thường xảy ra trong các phương pháp trên xuống.

Ý tưởng chính của phép biến đổi ma trận là mô phỏng sự lan truyền các giá trị buộc được tạo ra trong phương pháp định giá câu truy vấn theo kiểu trên xuống. Sự lan truyền này nhận được bằng cách viết lại chương trình gốc ban đầu. Trong mỗi quy tắc gốc một điều kiện mới được thêm vào để hạn chế việc tính toán trên quy tắc. Các điều kiện này được xem là các quan hệ lọi. Một quy tắc mới được tạo ra để mô phỏng sự lan truyền các giá trị buộc.

Mặc dầu kỹ thuật ma trận đã được đánh giá là rất hiệu quả nhưng nó chưa hẳn là chiến lược định giá câu truy vấn tốt nhất. Trong luận văn này đi sâu vào phân tích một số hạn chế của phương pháp này và giới thiệu một số cải tiến. Luận văn gồm phần mở đầu, ba chương nội dung, phần kết luận, tài liệu tham khảo và phần phụ lục.

Định giá bảng là một phương pháp khác được sử dụng để tối ưu hóa truy vấn trong CSDL suy diễn. Nó liên quan đến việc lưu trữ các kết quả trung gian trong quá trình đánh giá truy vấn để tránh tính toán lại. Điều này có thể cải thiện đáng kể hiệu suất, đặc biệt đối với các truy vấn phức tạp hoặc đệ quy. Định giá bảng thường được sử dụng kết hợp với các kỹ thuật tối ưu hóa khác, chẳng hạn như phép biến đổi ma trận, để đạt được hiệu suất tốt nhất.

Ngôn ngữ cấp một [19] (first order language) chúng ta tìm hiểu về logic vị từ bậc nhất được xem như là một phương thức biểu diễn tri thức, đồng thời là một ngôn ngữ để diễn tả các phép toán trên các quan hệ. Một ngôn ngữ cấp một được xây dựng trên một bảng chữ và những công thức được xây dựng trên bảng chữ đó.1 Bảng chữ bao gồm các hằng, biến, ký hiệu hàm, ký hiệu vị từ, hằng vị từ: true, false, các toán tử liên kết: (phủ định), (hội), (tuyển), (kéo theo), (tương đương), các ký hiệu lượng từ: (tồn tại), (với mọi), các cặp dấu ngoặc đơn (), dấu phẩy (,).

Một chương trình Datalog là một CSDL suy diễn xác định bao gồm một tập hữu hạn các mệnh đề Horn, nghĩa là các quy tắc có dạng: ρ ← q1, q2, …, qn (n ≥ 0). Trong đó các vị từ ρ, qi là các nguyên tố. Để đảm bảo các kết quả của chương trình Datalog là hữu hạn, ta giả thiết mọi quy tắc trong chương trình Datalog đều thỏa mãn điều kiện an toàn: mỗi biến xuất hiện trong đầu một quy tắc phải xuất hiện trong thân của nó.

Tiếp cận từ trên xuống, còn gọi là suy diễn đích hoặc kết xâu lùi, bắt đầu từ đích truy vấn và chỉ tính toán các sự kiện liên quan đến truy vấn. Tuy nhiên, phương pháp này có thể dẫn đến vòng lặp vô hạn nếu không có cơ chế ngăn chặn phù hợp.

Tiếp cận từ dưới lên đảm bảo tính kết thúc nhưng có thể kém hiệu quả vì tính toán nhiều sự kiện không liên quan đến truy vấn. Phương pháp này không định hướng đích và không xem xét truy vấn trong quá trình định giá.

Định giá bảng là một kỹ thuật quan trọng để ngăn chặn vòng lặp vô hạn trong quá trình định giá truy vấn từ trên xuống. Bằng cách lưu trữ các kết quả trung gian, định giá bảng tránh tính toán lại và đảm bảo tính kết thúc.

Ý tưởng chính của phép biến đổi ma trận là mô phỏng sự lan truyền các giá trị buộc được tạo ra trong phương pháp định giá câu truy vấn theo kiểu trên xuống. Sự lan truyền này nhận được bằng cách viết lại chương trình gốc ban đầu.

Mặc dù kỹ thuật ma trận đã được đánh giá là rất hiệu quả nhưng nó chưa hẳn là chiến lược định giá câu truy vấn tốt nhất. Cần có những cải tiến để khắc phục các hạn chế của phương pháp này.

CSDL suy diễn có tiềm năng ứng dụng rộng rãi trong nhiều lĩnh vực, bao gồm y tế, tài chính, giáo dục và thương mại điện tử. Việc phát triển các ứng dụng này tại ĐHQGHN có thể mang lại nhiều lợi ích cho cộng đồng.

Hướng nghiên cứu tiếp theo có thể tập trung vào việc tích hợp học máy vào CSDL suy diễn để tự động hóa quá trình suy luận và khám phá tri thức. Ngoài ra, việc nghiên cứu các phương pháp xử lý dữ liệu lớn trong CSDL suy diễn cũng là một hướng đi đầy tiềm năng.