I. Tổng Quan Về Cơ Sở Dữ Liệu Suy Diễn Luận Văn Thạc Sĩ
Luận văn thạc sĩ nghiên cứu về cơ sở dữ liệu suy diễn (CSDL suy diễn) như một sự mở rộng của CSDL quan hệ. CSDL suy diễn không chỉ chứa các yếu tố nền tương ứng với các bộ của các quan hệ trong CSDL quan hệ, mà còn chứa các quy tắc tổng quát, bao gồm các quy tắc suy diễn và các ràng buộc toàn vẹn. So với các hệ CSDL quan hệ, các hệ CSDL suy diễn thừa nhận một kiểu lý thuyết chứng minh. Việc thực hiện một câu truy vấn hoặc làm thỏa mãn một ràng buộc toàn vẹn có thể xem như chứng minh một công thức cấp một là hệ quả logic của lý thuyết đã cho. Sức mạnh biểu diễn của CSDL suy diễn là thật sự quan trọng trong nhiều lĩnh vực khác nhau. Các ứng dụng tiêu biểu của CSDL bao gồm hệ chuyên gia, hệ hỗ trợ quyết định, phân tích tài chính, phân tích ngôn ngữ, cú pháp. Tuy vậy, trong lĩnh vực CSDL suy diễn, mặc dù đã có nhiều kết quả có giá trị nhưng cũng có nhiều vấn đề cần nghiên cứu tiếp, đặc biệt là các vấn đề về ngữ nghĩa của phủ định và tối ưu hóa câu hỏi (truy vấn).
1.1. Giới Thiệu Chương Trình Datalog Trong CSDL Suy Diễn
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.
1.2. Ưu Điểm Của Phương Pháp Suy Diễn Dưới Lê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.
II. Thách Thức Giải Pháp Tối Ưu Truy Vấn Trong CSDL
Trong thời gian gần đây, một số phương pháp mở rộng để trả lời câu truy vấn được đề xuất nhằm mục đích tạo ra một chiến lược tìm kiếm hướng đích, đồng thời có tính hiệu quả là đảm bảo kết thúc quá trình tính toán câu trả lời truy vấn. Điển hình đó là phép biến đổi ma trận (magic set transformation) và định giá bảng. Các phương pháp này được đánh giá là một trong những kỹ thuật tối ưu câu truy vấn có hiệu quả trong CSDL suy diễn. Nó đã kết hợp được các ưu điểm của kỹ thuật định giá theo kiểu trên xuống và dưới lên, do đó giảm thiểu được số các sự kiện cần tính và tìm kiếm trên CSDL. Ở đây áp dụng hai phương pháp này để xử lý vòng lặp vô hạn trong quá trình định giá câu truy vấn trên chương trình Datalog.
2.1. Phép Biến Đổi Ma Trận Magic Set Transformation
Ý 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.
2.2. Hạn Chế Của Kỹ Thuật Ma Trận Trong Tối Ưu Truy Vấn
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.
2.3. Định Giá Bảng Và Ứng Dụng Trong Datalog
Đị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.
III. Ngôn Ngữ Datalog Nền Tảng Của CSDL Suy Diễn Hiện Đại
Chương 1 trình bày cú pháp, ngữ nghĩa và các kỹ thuật định giá câu truy vấn đối với CSDL suy diễn và chương trình Datalog. Phần lớn nội dung của chương này được tổng hợp từ nhiều công trình nghiên cứu của các tác giả ở trong và ngoài nước. Đây là những kiến thức cơ sở cần thiết mà luận văn sẽ dùng trong các chương tiếp theo. CSDL suy diễn sử dụng ngôn ngữ logic cấp một làm ngôn ngữ cơ sở. Vì vậy, chúng ta bắt đầu từ ký pháp của logic cấp một.
3.1. Logic Vị Từ Bậc Nhất Cơ Sở Biểu Diễn Tri Thức
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 (,).
3.2. Cú Pháp Datalog Quy Tắc Và Mệnh Đề Horn
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ó.
IV. Định Giá Truy Vấn Trong CSDL Suy Diễn Các Phương Pháp
Chương 2 trình bày về các cách tiếp cận khác nhau để trả lời câu truy vấn trong CSDL suy diễn. Luận văn đã tiến hành thảo luận một cách chi tiết, phân tích làm rõ đặc trưng, ý nghĩa của mỗi cách tiếp cận. Các phương pháp nhằm ngăn chặn các vòng lặp vô hạn khi tìm kiếm lời giải của câu truy vấn đối với chương trình Datalog bằng phương pháp định giá bảng cũng như thuật toán định giá chương trình Datalog theo các thành phần liên thông mạnh đã được phân tích, xem xét.
4.1. Tiếp Cận Từ Trên Xuống Ưu Điểm Và Hạn Chế
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.
4.2. Tiếp Cận Từ Dưới Lên Đảm Bảo Tính Kết Thúc
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á.
4.3. Định Giá Bảng Giải Pháp Ngăn Chặn Vòng Lặp Vô Hạn
Đị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.
V. Phép Biến Đổi Ma Trận Cải Tiến Hiệu Năng Truy Vấn Datalog
Chương 3 trình bày kỹ hơn về phương pháp biến đổi ma trận và thảo luận một số hạn chế của phép biến đổi ma trận. Từ đó đã có được sự cải tiến thuật toán ma trận trên một số lớp con của chương trình Datalog là chương trình Datalog tuyến tính phải và chương trình Datalog không đệ qui. Một số cải tiến khác về thuật toán ma trận trên chương trình Datalog cũng được xem xét [6]. Phần phụ lục trình bày một số phương pháp định giá chương trình Datalog bằng một số thuật toán đơn giản, dễ cài đặt. Tuy nhiên một số phương pháp xử lý vòng lặp vô hạn khi định giá trên xuống chưa được đề cập trong phụ lục này.
5.1. Mô Phỏng Lan Truyền Giá Trị Ý Tưởng Cốt Lõi
Ý 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.
5.2. Hạn Chế Của Biến Đổi Ma Trận Cần Cải Tiến
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.
VI. Kết Luận Hướng Phát Triển CSDL Suy Diễn Tại ĐHQGHN
Luận văn đã trình bày tổng quan về CSDL suy diễn, ngôn ngữ Datalog và các phương pháp định giá truy vấn. Các kỹ thuật tối ưu hóa truy vấn, đặc biệt là phép biến đổi ma trận, đã được phân tích và cải tiến. Nghiên cứu này đóng góp vào việc nâng cao hiệu năng của các hệ thống CSDL suy diễn, mở ra nhiều ứng dụng tiềm năng trong các lĩnh vực khác nhau. Hướng phát triển tiếp theo có thể tập trung vào việc nghiên cứu các phương pháp xử lý dữ liệu lớn và tích hợp học máy vào CSDL suy diễn.
6.1. Ứng Dụng Thực Tế Tiềm Năng Phát Triển Tại ĐHQGHN
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.
6.2. Nghiên Cứu Tiếp Theo Tích Hợp Học Máy Và Dữ Liệu Lớn
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.
