Tài liệu Datalog và cơ sở dữ liệu suy diễn

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Hồng Sơn DATALOG VÀ CƠ SỞ DỮ LIỆU SUY DIỄN LUẬN VĂN THẠC SĨ Hà Nội - 2005 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Hồng Sơn DATALOG VÀ CƠ SỞ DỮ LIỆU SUY DIỄN Ngành: Công nghệ thông tin Mã số: 1.01.10 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Hồ Thuần Hà Nội - 2005 1 MỤC LỤC LỜI CAM ĐOAN ............................................................... Error! Bookmark not defined. LỜI CẢM ƠN ..................................................................... Error! Bookmark not defined. MỤC LỤC ................................................................................................................................. 1 DANH MỤC CÁC KÝ HIỆU CÁC CHỮ VIẾT TẮT ....................................................... 3 DANH MỤC CÁC HÌNH VẼ ................................................................................................ 4 MỞ ĐẦU ................................................................................................................................... 5 CHƢƠNG 1. KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU SUY DIỄN VÀ CHƢƠNG TRÌNH DATALOG................................................................................................................................ 8 1.1. Ngôn ngữ cấp một (first order language) ................................................................... 8 1.2. Cơ sở dữ liệu suy diễn và chƣơng trình Datalog....................................................... 9 1.2.1. Cơ sở dữ liệu suy diễn........................................................................................... 9 1.2.2. Cú pháp của chƣơng trình Datalog .................................................................... 11 1.2.3. Giả thiết thế giới đóng và các tiếp cận để xác định ngữ nghĩa chƣơng trình Datalog ............................................................................................................................. 16 1.2.4. Các thuật toán xác định ngữ nghĩa chƣơng trình Datalog .............................. 19 1.3. Chƣơng trình Datalog có chứa phủ định .................................................................. 25 1.3.1. Ngữ nghĩa mô hình hoàn hảo ............................................................................. 25 1.3.2. Ngữ nghĩa mô hình bền vững............................................................................. 32 1.4. Kết luận ........................................................................................................................ 34 CHƢƠNG 2. TỐI ƢU CÂU TRUY VẤN ĐỐI VỚI CHƢƠNG TRÌNH DATALOG 36 2.1. Định giá câu truy vấn theo kiểu trên xuống (top-down) ........................................ 36 2.2. Định giá câu truy vấn theo kiểu trên xuống có sử dụng kỹ thuật ghi nhớ ........... 37 2.2.1. Định giá SLD ....................................................................................................... 38 2.2.2. Định giá bảng ...................................................................................................... 40 2.3. Định giá câu truy vấn theo kiểu dƣới lên (bottom-up) .......................................... 45 2.3.1. Thuật toán định giá câu truy vấn theo phƣơng pháp dƣới lên ...................... 47 2.3.2. Thuật toán định giá chƣơng trình Datalog theo các thành phần liên thông mạnh ................................................................................................................................ 48 2.4. Định giá câu truy vấn theo cách kết hợp trên xuống và dƣới lên ........................ 53 2.5. Một số nhận xét so sánh về các phƣơng pháp định giá bảng và ma tập .............. 55 2.6. Kết luận ........................................................................................................................ 56 CHƢƠNG 3. PHƢƠNG PHÁP MA TẬP ........................................................................... 57 3.1. Phƣơng pháp ma tập .................................................................................................. 57 3.1.1. Tô điểm ................................................................................................................ 57 3.1.2. Truyền thông tin sang ngang ............................................................................. 58 3.1.3. Phép biến đổi ma tập (Magic set transformation) ........................................... 60 3.1.4. Phƣơng pháp ma tập ........................................................................................... 61 3.2. Cải tiến phƣơng pháp ma tập trên một số lớp con của chƣơng trình Datalog ..... 62 2 3.2.1. Phƣơng pháp ma tập cải tiến trên chƣơng trình Datalog tuyên tính phải ..... 62 3.2.2. Phép biến đổi ma tập trên chƣơng trình Datalog không đệ qui .................... 66 3.3. Phƣơng pháp ma tập cải tiến ..................................................................................... 70 3.3.1. Thuật toán tổ điểm chƣơng trình ...................................................................... 71 3.3.2. Tối ƣu bƣớc tô điểm chƣơng trình .................................................................... 75 3.3.3. Cải tiến việc thực thi chƣơng trình Mag_P ad ................................................... 77 3.3.4. Phƣơng pháp ma tập cải tiến ............................................................................. 82 3.4. Kết luận ........................................................................................................................ 83 KẾT LUẬN ............................................................................................................................. 84 TÀI LIỆU THAM KHẢO ..................................................................................................... 85 PHỤ LỤC ................................................................................................................................ 88 3 DANH MỤC CÁC KÝ HIỆU CÁC CHỮ VIẾT TẮT CSDL: Cơ sở dữ liệu CWA: Closed World Assumption – Giả thiết thế giới đóng. EDB: Extensionl Database – CSDL Ngoại diên. GCWA: Generalized Closed World Assumption – Giả thiết thế giới đóng tổng quát. IDB: Intensionl Database – CSDL Nội hàm. mgu: most general unifier – Hợp nhất tử tổng quát nhất. SCC: Strongly Connect Component – Thành phần liên thông mạnh. Sips: Sideway Information Pausing - Truyền thông tin sang ngang. SLD: Linear Selection resolution for Definite clauses SLG: Linear Resolution with Selection function for General logic programs WGCWA: Weak Generalized Closed World Assumption – Giả thiết thế giới đóng yếu tổng quát. 4 DANH MỤC CÁC HÌNH VẼ Hình 1.1 Đồ thị phụ thuộc của chƣơng trình trong ví dụ 1.5 ........................................... 16 Hình 1.2 Cây chứng minh của sự kiện p(a, d) .................................................................... 18 Hình 1.3 Đồ thị phụ thuộc của chƣơng trình trong ví dụ 1.12 ......................................... 28 Hình 1.4 Đồ thị phụ thuộc của chƣơng trình trong ví dụ 1.13 ......................................... 30 Hình 2.1 Cây SLD đối với câu truy vấn p(1, Y) trong ví dụ 2.1 ..................................... 39 Hình 2.2 Cây SLD đối với câu truy vấn p(1, Y) trong ví dụ 2.2 ..................................... 40 Hình 2.3 Định giá SLG của chƣơng trình P trong ví dụ 2.3 ............................................. 44 Hình 2.4 Đồ thị phụ thuộc của chƣơng trình trong ví dụ 2.5 ........................................... 49 Hình 2.5 Đồ thị phụ thuộc thu gọn của chƣơng trình trong ví dụ 2.5 ............................. 50 Hình 2.6 Đồ thị phụ thuộc của chƣơng trình trong ví dụ 2.6 ........................................... 52 Hình 3.1 Đồ thị mở rộng của chƣơng trình trong ví dụ 3.5 .............................................. 68 Hình 3.2 Truyền thông tin sang ngang trong ví dụ 3.7 ..................................................... 72 5 MỞ ĐẦU CSDL suy diễn, một sự mở rộng CSDL quan hệ, không những chỉ có các nguyên tố nền tƣơng ứng với các bộ của các quan hệ trong CSDL quan hệ mà còn có các quy tắc tổng quát (gồm các quy tắc suy diễn và các ràng buộc toàn vẹn). Những quy tắc này tạo thành phần mở rộng. 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, nghĩa là nó đƣợc xem xét nhƣ một lý thuyết bao gồm một tập các công thức cấp một, còn việc thực hiện một câu truy vấn hoặc làm thoả 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 hoá câu hỏi (truy vấ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. 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 6 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. 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 tập (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. Ý tƣởng chính của phép biến đổi ma tập là mô phỏng sự lan truyền các 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ọc. Một quy tắc mới đƣợc tạo ra để mô phỏng sự lan truyền các trị buộc. Mặc dầu kỹ thuật ma tập đã đƣợ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. 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 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. 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. 1.1. 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ữ đó. Định nghĩa 1.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: (tƣơng đƣơng), các ký hiệu lƣợng từ: (phủ định), (tồn tại), (hội), (tuyển), (kéo theo), (với mọi), các cặp dấu ngoặc đơn (), dấu phẩy (,). Định nghĩa 1.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. Định nghĩa 1.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ố, 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. Định nghĩa 1.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. Định nghĩa 1.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. Ví dụ 1.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. 1.2. 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. 1.2.1. Cơ sở dữ liệu suy diễn Định nghĩa 1.6 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. (*) có dạng: p đƣợc gọi là mệnh đề đơn vị (unit). 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 (*) có dạng: q1 … q2 1. qn đƣợc gọi là đích (goal) hoặc một truy vấn (query). 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 … Dạng 3: Trƣờng hợp m = 1, n 1. (*) có dạng: p qn q1 q2 … Xk ( q1 .. 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 (*) có dạng: p1 p2 … pm 1. q1 q2 … qn 11 và đƣợc gọi là quy tắc Datalog dạng tuyển. p1 q2 … p2 … pm gọi là đầu quy tắc và q1 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. 1.2.2. 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ó. Định nghĩa 1.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. 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. Định nghĩa 1.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. - Nếu A Bp nhƣng A I, ta nói rằng sự kiện A sai trong I va viết I | A. Ví dụ 1.2 Xét chƣơng trình Datalog P gồm các quy tắc sau: q(a, b) q(b, c) p(X, Y) q(X, Y) p(X, Y) p(X, Z) p(Z, Y) 13 Vũ trụ Herbrand của P là Up = {a, b, c} và cơ sở Herbrand của P là: Bp = {p(a, a), p(a, b), p(a, c), p(b, a), p(b, b), p(b, c), p(c, a), p(c, b), p(c, c), q(a, a), q(a, b), q(a, c), q(b, a), q(b, b), q(b, c), q(c, a), q(c, b), q(c, c), } Định nghĩa 1.11 Một phép thế (substitution) là tậo hữu hạn có dạng {X1/t1, …, Xn/tn} trong đó Xi là các biến phân biệt, t i là các hạng thức, Xi ti, mỗi phần tử Xi/ti là ký hiệu của phép thế tƣơng ứng biến Xi với hạng thức t i, i=1, …, n. Nếu tất cả t i là hằng thì đƣợc gọi là phép thế nền. Định nghĩa 1.12 Một biểu thức là một hạng thức, một literal hoặc hội hoặc tuyển các literal. Định nghĩa 1.13 Giả sử E là một biểu thức và phép thế = {X1/t1, …, Xn/tn }. Lúc đó E , gọi là hiện hành của E bởi , là biểu thức nhận đƣợc từ E bằng cách thay thế đồng thời các biến Xi xuất hiện trong E bởi các t i (i= 1, …, n). Nếu E không chứa biến thì E đƣợc gọi là một hiện hành nền của E. Định nghĩa 1.14 Giả sử ta có hai phép thế = {X1/t1, …, Xn /tn} = {Y1/t1 , …,Ym/tm} Hợp thành của và , là phép thế nhận đƣợc bằng cách xoá khỏi tập hợp: {X1/t1 , …, Xn/tn , Y1/t1 , …,Ym/tm} Mọi phần tử X i/ti mà Xi = ti và Yi/ti mà Yi {Xi , X2, …, Xn}. Ký hiệu = . Định nghĩa 1.15 Phép hợp nhất Cho E và F là hai nguyên tố. Lúc đó: (i) E và F gọi là có thể hợp nhất nếu tồn tại phép thế sao cho E = F , lúc đó đƣợc gọi là phép hợp nhất của E và F. (ii) Cho 2 phép thế 1 và 2. Ta gọi phép thế tồn tại một phép thế sao cho 1= 2 . 1 tổng quát hơn phép thế 2 nếu 14 (iii) Cho là một phép hợp nhất của E và F. Nếu nhất khác của E và F thì tổng quát hơn mọi phép hợp đƣợc gọi là hợp nhất tử tổng quát nhất (most general unifier) của E và F, ký hiệu mgu(E, F). Ví dụ 1.3 Cho E=p(f(x), z) và F=p(y, a) Ta có E và F có thể hợp nhất và = {y/f(a), x/a, z/a} là một hợp nhất tử của E và F. Hợp nhất tử tổng quát nhất của E và F là = {y/f(x), z/a}. Để ý = {x|a}. Định lý 1.1 [19] Tồn tại thuật toán tìm hợp nhất tử tổng quát nhất của hai nguyên tố nếu chúng có thể hợp nhất đƣợc và ngƣợc lại thông báo không tồn tại hợp nhất tử. Định nghĩa 1.16 Giả sử P là chƣơng trình Datalog. Lúc đó: Một thể hiện Herbrand I gọi là mô hình Herbrand (hoặc đơn giản là mô hình) của P, ký hiệu I |= P, nếu với mọi quy tắc p q1 … qn trong P và mọi phép thế nền đối với quy tắc này, điều kiện sau đây là thoả: Nếu qi I với mọi i = 1, 2, …, n thì p I. Mô hình I của P đƣợc gọi là mô hình cực tiểu (minimal model) nếu không tồn tại một mô hình J nào khác của P sao cho J I. Mô hình I của P đƣợc gọi là mô hình nhỏ nhất (least model) nếu với mọi mô hình J của P ta luôn có I J. Mệnh đề 1.1 [19] Đối với mọi chƣơng trình Datalog P, luôn luôn tồn tại mô hình cực tiểu duy nhất của P. Mô hình cực tiểu của chƣơng trình Datalog P có thể tính đƣợc nhờ vào một toán tử hệ quả trực tiếp (direct consequence operator) Tp. Đối với thể hiện Herbrand I cho trƣớc của chƣơng trình Datalog P, toán tử Tp xây dựng nên một thể hiện Herbrand của P là Tp (I) - chứa các sự kiện đƣợc dẫn xuất bởi các quy tắc trong P từ những sự kiện trong I. Định nghĩa 1.17 Giả sử P là chƣơng trình Datalog, Bp là cơ sở Herbrand của P. Ký hiệu 2 là tập các tập con của Bp. Toán tử hệ quả trực tiếp là một ánh xạ Tp: Bp 15 2 Bp 2 p đƣợc định nghĩa nhƣ sau: Với mỗi I quy tắc p q1 đối với quy tắc này sao cho p = A và I |= (q1 … B … qn của P và phép thế nền qn ) }. Ví dụ 1.4 Xét quy tắc r: p(a,X) q(b, c), r(c, a) (q(X, Y) q(X, Y) B 2 p , Tp (I) = {A r(Y, a) của chƣơng trình Datalog P. Giả sử thể hiện Herbrrand I và phép thế nền r(Y, a)) = q(b, c) r(c, a) Bp | = {X/b, Y/c}. Lúc đó ta có I và p(a, X) = p(a, b) nên suy ra p(a,b) Tp(I). Định lý sau đây cho ta một tính chất quan trọng của toán tử Tp: Định lý 1.2 [12] Giả sử P là chƣơng trình Datalog. Lúc đó: (i) Tp đơn điệu tăng và có điểm bất động nhỏ nhất. (ii) Điểm bất động nhỏ nhất của Tp chính là mô hình cực tiểu duy nhất của P. Định nghĩa 1.18 Giả sử P là chƣơng trình Datalog. Đồ thị phụ thuộc (dependency graph) của P là một đồ thị có hƣớng DG(P) = , trong đó V là tập đỉnh gồm các vị từ IDB và EDB của P và E là tập cạnh, cạnh (q, p) E nếu P chứa quy tắc với p là đầu và q ở trong thân. Chƣơng trình P đƣợc gọi là đệ qui nếu đồ thị phụ thuộc DG(P) có ít nhất một chu trình, ngƣợc lại P đƣợc gọi là không đệ qui. Vị từ p nằm trong một chu trình nào đó của đồ thị DG(P) đƣợc gọi là vị từ đệ qui, ngƣợc lại gọi là vị từ không đệ qui. Ví dụ 1.5 Xét chƣơng trình Datalog sau đây: q(X, Y) p(Z, X) p(Z, Y) q(X, Y) r(Z, X) r(Z, Y) p(X, Y) r(Z, Y) s(X, Z) r(X, Y) p(Z, Y) s(Z, X) Đồ thị phụ thuộc của chƣơng trình trên có dạng nhƣ hình vẽ. 16 s p r q Hình 1.1 Đồ thị phụ thuộc của chƣơng trình trong ví dụ 1.5 1.2.3. Giả thiết thế giới đóng và các tiếp cận để xác định ngữ nghĩa chƣơng trình Datalog 1.2.3.1. Giả thiết thế giới đóng Trong CSDL suy diễn, giả thiết thế giới đóng (CWA) của Reiter đóng vai trò hết sức quan trọng. CWA đã đƣợc sử dụng nhƣ một quy tắc ngầm định để đƣa ra kết luận đối với các sự kiện phủ định. Dƣới CWA, nếu một nguyên tố nền p thuộc cơ sở Herbrand Bp của chƣơng trình Datalog P không thể suy ra đƣợc từ những quan hệ EDB và các quy tắc trong P thì p sẽ đƣợc xem là đúng. Ký hiệu CWA(P) là tập đƣợc xác định bởi: CWA(P) = { p | p Bp và P | p} Với giả thiết thế giới đóng, có ba tiếp cận khác nhau thƣờng đƣợc sử dụng trong việc xác định ngữ nghĩa của chƣơng trình Datalog: tiếp cận theo quan điểm lý thuyết mô hình, tiếp cận theo quan điểm lý thuyết chứng minh và tiếp cận theo quan điểm lý thuyết điểm bất động. 1.2.3.2. Tiếp cận theo quan điểm lý thuyết mô hình Theo quan điểm lý thuyết mô hình, các quy tắc trong chƣơng trình đƣợc xem là công cụ để xác định mô hình. Một thể hiện của một tập các vị từ sẽ gán giá trị chân lý cho mỗi tình huống có thể có của các vị từ. Để là mô hình của một tập các quy tắc, một thể hiện phải làm cho các quy tắc đúng với mọi phép gán giá trị cho các biến trong mỗi 17 quy tắc đƣợc lấy từ miền giá trị đã cho. Theo quan điểm này, ngữ nghĩa của chƣơng trình Datalog P là mô hình cực tiểu của P EDB. Ví dụ 1.8 Xét chƣơng trình Datalog sau đây: r1: p(X) r2: q(X, Y) q(X, Y) r(X) s(X, Y) trong đó p, q là các vị từ IDB, r và s là các vị từ EDB. Giả sử CSDL EDB là {r(1), s(1, 2)}. Xét thể hiện M1 = {r(1), s(1, 2), q(1, 2), p(1)}. Khi thay X = 1, Y = 2 vào quy tắc r1 và r2 đều làm cho r1 và r2 đều đúng nên M1 là một mô hình. Cũng vậy, với thể hiện M2 = {r(1), s(1, 2), q(1, 2), p(1), p(2)} thì M 2 cũng là mô hình. Tuy nhiên, với thể hiện M3 = {r(1), s(1, 2), q(1, 2)} thì M 3 không phải là một mô hình. Lý do khi thay X=1, Y=2 vào r 1 ta đƣợc một giả thiết đúng và một kết luận sai. Trong ví dụ này, có thể thấy rằng có một lƣợng vô hạn các mô hình phù hợp với CSDL {r(1), s(1, 2)} . Thể hiện M 1 là một mô hình đặc biệt, bởi vì nó là mô hình cực tiểu, theo nghĩa là chúng ta không thể làm cho một sự kiện đúng trong mô hình trở thành sai mà vẫn nhận đƣợc mô hình. Để ý rằng mô hình M 2 không có đặc tính này, chẳng hạn có thể loại bỏ sự kiện p(2), nghĩa là xem p(2) là sai, kết quả nhận đƣợc cũng là một mô hình. Hơn nữa, mô hình cực tiểu M 1 là duy nhất phù hợp với CSDL {r(1), s(1, 2)}. 1.2.3.3. Tiếp cận theo quan điểm lý thuyết chứng minh Theo quan điểm lý thuyết chứng minh, các công thức của chƣơng trình đƣợc xem là các tiền đề đƣợc sử dụng trong chứng minh. Ngữ nghĩa của chƣơng trình Datalog P đƣợc định nghĩa là tập tất cả các sự kiện có thể đƣợc dẫn xuất từ P bằng cách áp dụng các quy tắc trong P và những sự kiện đã biết trong CSDL. Quá trình có thể đƣợc thực hiện bắt đầu từ các sự kiện EDB đã cho và tiến hành lặp trên các quy tắc trong chƣơng trình từ vế phải sang vế trái, tức là từ thân đến đầu, chẳng hạn ta xét ví dụ: 18 Ví dụ 1.9 Xét chƣơng trình gồm các quy tắc sau: r1: p(X, Y) q(X, Y) r2: p(X, Y) p(X, Z) p(Z, Y) trong đó q vị từ EDB, giả sử q(a, e) và q(e, d) là các sự kiện EDB. Từ quy tắc r 1 ta suy ra p(a, e) và p(e, d) đúng và từ quy tắc r 2 ta nhận đƣợc p(a, d) đúng. Quá trình suy dẫn để chứng minh p(a, d) có thể mô tả nhƣ hình vẽ sau: p(a, d) p(a, e) p(e, d) q(a, e) q(e, d) Hình 1.2 Cây chứng minh của sự kiện p(a, d) 1.2.3.4. Tiếp cận theo quan điểm lý thuyết điểm bất động Với các kết quả nghiên cứu về lý thuyết điểm bất động trong chƣơng trình logic bởi Van Emden và Kowalski, Apt và Van Emden, ngữ nghĩa của chƣơng trình Datalog P cũng có thể đƣợc xác định là điểm bất động nhỏ nhất của toán tử hệ quả trực tiếp Tp (định lý 1.2). Nhận xét: Trong cả ba cách tiếp cận trên, đối với trƣờng hợp đơn giản là chƣơng trình Datalog nguyên thuỷ, nghĩa là các quy tắc không chứa phủ định thì tất cả phƣơng pháp đều cho ra cùng một kết quả. Trong trƣờng hợp tổng quát, khi cho phép sử dụng nhiều loại quy tắc phức tạp hơn thì ta có nhiều cách tiếp cận khác nhau, dẫn đến nhiều câu trả lời khác nhau. Trong nhiều trƣờng hợp, không có gì đảm bảo chỉ có một câu trả lời duy nhất đƣợc tạo ra. Chẳng hạn, với chƣơng trình P = { p q, q p}, P có hai mô hình cực tiểu là {p} và {q}, tuy nhiên P không có mô hình nhỏ nhất. Chúng ta xem xét kỹ hơn vấn đề này trong phần 1.3