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. Chƣơng 1 trình bày khái quát về CSDL suy diễn và chƣơng trình D atalog. Nội dung chính tập trung vào cơ sở lý thuyết của ngôn ngữ cấp một, CSDL suy diễn và chƣơng trình Datalog. Hai dạng ngữ nghĩa phổ biến của chƣơng trình logic đƣợc thiết LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 kế lại để áp dụng trên lớp chƣơng trình Datalog có chứa phủ định là ngữ nghĩa mô hình hoàn hảo và ngữ nghĩa mô hình bền vững.
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. Chƣơng 3 trình bày kỹ hơn về phƣơng pháp biến đổi ma tập và thảo luận một số hạn chế của phép biến đổi ma tập.
Từ đó đã có đƣợc sự cải tiến thuật toán ma tập 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 tập 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.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 CHƢƠNG 1. KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU SUY DIỄN VÀ CHƢƠNG TRÌNH DATALOG 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. 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 (,).2 Hạng thức (term) đƣợc định nghĩa đệ qui nhƣ sau: (i) Mỗi hằng là một hạng thức.
(ii) Mỗi biến là một hạng thức. (iii) Nếu f là ký hiệu hàm n đối và t1, t2, …, tn là các hạng thức thì f(t 1 , t2, …, tn ) là một hạng thức.3 Một nguyên tố (Atom) có dạng p(t 1, t2, …, tn), trong đó p là ký hiệu vị từ có n đối và t i , i=1, …, n là những hạng thức. Nguyên tố nền là nguyên tố không chứa biến. Literal là một nguyên tố, gọi là literal dương hoặc phủ định của một nguyên tố, LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 gọi là literal âm.
Với p là một nguyên tố, literal âm đƣợc ký hiệu p, p và p còn gọi là phần bù của nhau.4 Công thức logic đƣợc định nghĩa một cách đệ qui nhƣ sau: (i) Nguyên tố là một công thức. (ii) True và False là các công thức. (iii) Nếu E và F là các công thức logic thì E F, E, E F, E F, E F là các công thức logic. (iv) Nếu E là một công thức logic và X là một biến thì ( X)E, ( X)E là một công thức logic.5 Công thức không chứa các biến đƣợc gọi là công thức nền (ground formula) Nếu trong các công thức ( X)E, ( X)E chứa biến X và có thể thêm một số biến khác không nằm dƣới dấu , thì biến X đƣợc gọi là biến buộc, còn các biến khác đƣợc gọi là biến tự do.
Công thức đóng là công thức không chứa các biến tự do.1 Y X(p(X,Y) q(Y)) là công thức đóng. Tuy nhiên X(p(X,Y) q(Y)) không phải là công thức đóng, vì Y là biến tự do. Cơ sở dữ liệu suy diễn và chƣơng trình Datalog [23, 24] Trong phần này chỉ tóm tắt một số khái niệm của CSDL suy diễn và tập trung vào mô hình dữ liệu quan trọng của CSDL suy diễn là chƣơng trình Datalog. Datalog là một ngôn ngữ truy vấn rất mạnh dựa trên logic mệnh đề Horn và đã đƣợc nghiên cứu sâu sắc bởi nhiều chuyên gia nhƣ Ullman, Ceri, Gottlob, Tanca, … Chúng ta cũng thảo luận một số tiếp cận ngữ nghĩa của chƣơng trình Datalog khi cho phép các literal âm xuất hiện trong thân quy tắc.
Cơ sở dữ liệu suy diễn Định nghĩa 1.6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 (i) Một CSDL suy diễn là một tập hữu hạn các mệnh đề có dạng: p1 p2 … pm q1 q2 … qn (m 0, n 0) (*) trong đó p i (i=0, 1, …, m) là các nguyên tố và qj (j=0, 1, …, n) là các literal. Tất cả các đối của các pi và qj đều không chứa các ký hiệu hàm. Mệnh đề (*) có thể xuất hiện dƣới các dạng khác nhau tuỳ thuộc vào các giá trị của m và n: Dạng 1: Trƣờng hợp m = 1, n = 0. Ngữ nghĩa của unit p là “với mọi phép gán trị cho các biến thì p đúng”.
Nếu tất cả đối của vị từ p là hằng thì p đƣợc gọi là một sự kiện, ký hiệu ở sau vị từ p là có thể bỏ qua. Dạng 2: Trƣờng hợp m = 0, n 1. Nếu X1, X2, …, Xk là các biến xuất hiện trong đích q1 q2 … qn thì nó chính là công thức: X1 … Xk ( q1. qn) Dạng 3: Trƣờng hợp m = 1, n 1.
(*) có dạng: p q1 q2 … qn đƣợc gọi là quy tắc suy diễn. Vị từ p đƣợc gọi là đầu quy tắc (head), q1 q2 … qn đƣợc gọi là thân quy tắc (body) và qi (i = 1, …, n) đƣợc gọi là các đích con (subgoal). Nếu p, qi (i = 1, …, n) là các nguyên tố thì quy tắc này gọi là quy tắc Datalog. Ta cũng nói rằng p q1 q2 … qn là quy tắc định nghĩa vị từ p.
Dạng 4: Trƣờng hợp m > 1, n = 0. (*) có dạng: p1 p2 … pm Nếu tất cả đối trong mọi vị từ p i là hằng thì nó đƣợc gọi là sự kiện tuyển. Dạng 5: Trƣờng hợp m > 1, n 1. (*) có dạng: p1 p2 … pm q1 q2 … qn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 và đƣợc gọi là quy tắc Datalog dạng tuyển.
p1 p2 … pm gọi là đầu quy tắc và q1 q2 … qn gọi là thân. (ii) Một CSDL suy diễn xác định chỉ bao gồm các quy tắc xác định, nghĩa là các quy tắc có dạng: p q1 q2 … qn (n 0) (iii) Một CSDL suy diễn không xác định cho phép chứa các quy tắc có dạng: p1 p2 … pm q1 q2 … qn (m > 1, n 0) Nếu thân của mọi quy tắc trong CSDL suy diễn không xác định P không chứa phủ định thì P đƣợc gọi là chƣơng trình Datalog dạng tuyển. Ngƣợc lại, P đƣợc gọi là chƣơng trình Datalog dạng tuyển mở rộng. Cú pháp của chƣơng trình Datalog Định nghĩa 1.7 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: p q1 q2 … qn (n 0) Trong đó các vị từ p, 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 thoả 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ó.8 Giả sử P là chƣơng trình Datalog. Vị từ nội hàm hay vị từ IDB là vị từ đƣợc định nghĩa bởi các quy tắc trong P. Vị từ ngoại diên hay vị từ EDB là vị từ không đƣợc định nghĩa qua các quy tắc, nó chỉ xuất hiện trong thân quy tắc. Các vị từ IDB hoặc EDB gọi là những vị từ thông thƣờng.
CSDL ngoại diên hoặc CSDL EDB của chƣơng trình Datalog là tập các sự kiện đƣợc lƣu trữ trong CSDL. CSDL nội hàm hoặc CSDL IDB là tập các quy tắc của chƣơng trình. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 Vị từ được cài sẵn (built-in predicate) là một vị từ so sánh số học =, , , , ,. Nếu là vị từ đƣợc cài sẵn thì ta viết X Y thay cho cách viết (X,Y).
Chú ý: Các vị từ EDB chỉ xuất hiện trong thân quy tắc còn các vị từ IDB có thể xuất hiện ở cả thân và đầu của quy tắc. Vị từ đƣợc cài sẵn chỉ đƣợc xuất hiện trong thân quy tắc.9 Với mỗi vị từ q có k đối đƣợc đặt tƣơng ứng một quan hệ Q có k thuộc tính. Giá trị của quan hệ Q là tập các bộ, một bộ của quan hệ Q có k thuộc tính đƣợc biểu thị bởi (a1 , a2 , …, ak) trong đó các a i là hằng, q(a1, a2, …, ak ) là đúng nếu (a1, a2, …, ak) thuộc Q. Quan hệ ứng với vị từ EDB (tƣơng ứng IDB) gọi là quan hệ EDB (tƣơng ứng IDB).
Với mỗi chƣơng trình Datalog P, ta liên kết với ngôn ngữ cấp một L(P) bao gồm các vị từ, các hằng, các công thức trong P. Ta có định nghĩa sau: Định nghĩa 1.10 Giả sử P là chƣơng trình Datalog. Lúc đó: Vũ trụ Herbrand (Herbrand universe) của P, ký hiệu Up, là tập tất cả các hạng thức nền của P. Cơ sở Herbrand (Herbrand base) của P, ký hiệu Bp, là tập tất cả các nguyên tố nền của P.
Thể hiện Herbrand (Herbrand interpretation) hoặc đơn giản ta chỉ gọi là thể hiện, là một tập con I bất kỳ của cơ sở Herbrand Bp của P. - Nếu A I, ta nói rằng sự kiện A đúng trong I và viết I |= A.