Datalog - Ngôn ngữ luật cho các cơ sở dữ liệu

1Datalog- Ngôn ngữ luật cho các CSDL Hồ Cẩm Hà - ĐHSPHN 2 Hệ QTCSDL suy diễn „ Trước hết đó là một hệ QTCSDL: có ngôn ngữ DDL, DML „ Đem cho người dùng một giao diện có ngôn ngữ luật, cho phép: từ các quan hệ cơ sở (lưu trữ trong CSDL cài đặt) suy diễn ra những quan hệ mới (CSDL tiềm ẩn) Hồ Cẩm Hà - ĐHSPHN 3 Các ngôn ngữ luật đối với các CSDL Một ngôn ngữ luật phải là „ tập hợp và phi thủ tục „ dễ giao diện với một hệ QTCSDL (dễ dàng được dịch thành một chương trình của đại số quan hệ mở rộng) Hồ Cẩm Hà - ĐHSPHN 4 Datalog „ Là một ngôn ngữ luật cho các CSDL, cho phép xác định các quan hệ suy diễn nhờ phép kéo theo đơn giản không có kí hiệu hàm „ Có thể xem đó là một biến dạng của Prolog với một ngữ nghĩa tập hợp (kết quả của một chương trình không phụ thuộc vào thứ tự các câu) Hồ Cẩm Hà - ĐHSPHN 5 Datalog Các mở rộng: • Đưa thêm kí hiệu hàm vào trong đối của các tân từ DATALOGfunc • Thêm phép phủ định DATALOGneg • Cập nhật tường minh trong một luật DATALOGmaj • Đưa vào những điều kiện tổng quát chứa các phép hội, tuyển, phủ định (phi Horn) DATALOGnon Hồ Cẩm Hà - ĐHSPHN 6 Datalog (cú pháp) Bảng chữ được dùng gồm các kí hiệu: „ hằng a, b, c,... „ biến x, y, z,... „ các tân từ quan hệ P, Q, R,... „ các tân từ so sánh =, , ... „ các liên kết logic v, ∧, ¬, →, ⇔ Hạng thức: hằng hay biến Công thức nguyên tố: Literal dương P(t1, t2, ...tn) Công thức nguyên tố cá biệt (được làm cá biệt): công thức nguyên tố không chứa biến Hồ Cẩm Hà - ĐHSPHN 7 Datalog (cú pháp) Luật: biểu thức có dạng Q ← P1 , P2 ,... , Pn „ Đầu luật Q là công thức nguyên tố (kết luận) „ thân luật P1 , P2 ,... , Pn là các tân từ (tiền đề hay điều kiện) „ mỗi Pi gọi là một đích con „ Luật được gọi là đệ qui nếu tân từ của đầu luật cũng xuất hiện trong thân luật Hồ Cẩm Hà - ĐHSPHN 8 Datalog (ví dụ về các luật) „ hằng: Hùng, Dũng, Mai, Thanh, .. „ các literal cá biệt còn gọi là các sự kiện: BO(Hùng, Dũng) ← MẸ(Mai, Dũng) ← .... „ Các luật khác: CHAMẸ(x,y) ← BO(x,y) CHAMẸ(x,y) ← MẸ(x,y) ONG(x,z) ← BO(x,y), CHAMẸ(y,z) TOTIEN(x,y) ← CHAMẸ(x,y) TOTIEN(x,z) ← TOTIEN(x,y), CHAMẸ(y,z) ANHEMHO(x,y) ← TOTIEN(z,x), TOTIEN(z,y) Hồ Cẩm Hà - ĐHSPHN 9 Datalog ‰ Một chương trình DATALOG là một tập các luật (thứ tự các luật không quan trọng} ‰ DATALOG cho phép người dùng phản ánh các luật và các sự kiện ‰ CSDL logic = CSDL cài đặt + CSDL tiềm ẩn (viết bằng DATALOG) Hồ Cẩm Hà - ĐHSPHN 10 Ngữ nghĩa của chương trình DATALOG ¾ Ngữ nghĩa của một chương trình DATALOG là cái mà chương trình đó tính được: ƒ Phương pháp khai báo/dựa trên việc tính mô hình của một chương trình logic ƒ Phương pháp thủ tục (từng bộ một)/ dựa trên phương pháp chứng minh bằng ppgiải và "phủ định bởi thất bại" Hồ Cẩm Hà - ĐHSPHN 11 Datalog Một mô hình của một chương trình DATALOG là một thể hiện thỏa mãn các tính chất sau: a) Với mọi bộ (a1,..., an) của một quan hệ B, B(a1,...,an) đúng trong thể hiện b) Với mọi luật Q(t1, t2, ..., tn) ← P1, P2, ..., Pn và với mọi phép gán θ trong thể hiện: Nếu θ(P1, P2, ..., Pn) đúng trong thể hiện thì θ(Q(t1, t2, ..., tn)) cũng đúng Hồ Cẩm Hà - ĐHSPHN 12 Datalog Một mô hình của một chương trình DATALOG là một tập các tân từ cá biệt: „ chứa tất cả các sự kiện của CSDL và „ tất cả các sự kiện có thể được suy diễn bằng áp dụng các luật Hồ Cẩm Hà - ĐHSPHN 13 Ngữ nghĩa chính tắc của chương trình DATALOG ƒ Giao của hai mô hình cũng là mô hình ƒ Giao của tất cả các mô hình: mô hình nhỏ nhất được gọi là ngữ nghĩa chính tắc ƒ Dùng Toán tử Tr để tính (hệ quả trực tiếp - Van Edem 1976) Hồ Cẩm Hà - ĐHSPHN 14 Thủ tục đơn giản tính mô hình nhỏ nhất Tr • Cho I là tập sự kiện • Tính Tp(I) = {Q/ ∃ P1, P2, ..., Pn ∈ I sao cho Q ← P1, P2, ..., Pn là một luật các biệt của P} • Bắt đầu với I = Ø, khi đó Tp(Ø) = tập các sự kiện của chương trình Hồ Cẩm Hà - ĐHSPHN 15 Thủ tục đơn giản tính mô hình nhỏ nhất Tr Ví dụ Cho chương trình DATALOG sau: P = { BO(Hùng, Dũng) ← ; MẸ(Mai, Dũng) ← ; CHAMẸ(x,y) ← BO(x,y); CHAMẸ(x,y) ← MẸ(x,y); TOTIEN(x,y) ← CHAMẸ(x,y) } Tính: bắt đầu Tp(Ø) = { BO(Hùng, Dũng) ← ; MẸ(Mai, Dũng) ← } Hồ Cẩm Hà - ĐHSPHN 16 Thủ tục đơn giản tính mô hình nhỏ nhất Tr Ví dụ Tp(Ø) = { BO(Hùng, Dũng) ← ; MẸ(Mai, Dũng) ← } .... Tp(I) = I' I' là mô hình nhỏ nhất của chương trình P Với những chương trình lớn cần có những thuật toán tối ưu hơn. Hồ Cẩm Hà - ĐHSPHN 17 Ngữ nghĩa chính tắc của chương trình DATALOG „ Tính khi cần trả lời câu hỏi „ Câu hỏi được biểu diễn bằng SQL trên quan hệ được suy diễn hay „ Câu hỏi biểu diễn bằng một luật không đầu dạng ← P1, P2, ..., Pn , trong đó thay ← bởi ? Ví dụ ? TOTIEN(x, Mai) Hồ Cẩm Hà - ĐHSPHN 18 Liên hệ DATALOG với ĐSQH „ DATALOG có sức mạnh của ĐSQH với sự cho phép đệ qui (ĐSQH không cho phép đệ qui) „ Phép hợp: 1 số luật cùng đầu „ Phép chiếu: một luật có một số biến ở phần thân bị lấy đi khỏi phần đầu của luật „ Phép chọn: một luật có ít nhất một tân từ quan hệ (so sánh) trong phần thân „ Phép kết nối: luật gồm một số tân từ quan hệ ở phần thân Hồ Cẩm Hà - ĐHSPHN 19 Mở rộng DATALOG với các hàm Nhờ các hàm có thể tính tóan, xử lí trên những đối tượng phức tạp (hình vẽ, kiểu dữ liệu trừu tượng) Do vậy đưa vào DATALOG các hàm của logic tân từ cấp một: • +, -, x, / • LOG, EXP,... • hàm định nghĩa bởi người dùng Đưa vào các kí hiệu hàm f, g,... có một số cố định đối số Các đối của tân từ có thể là hằng hoặc biến hoặc là hàm tác động lên các hạng thức f (t1, t2, ..., tn) Hồ Cẩm Hà - ĐHSPHN 20 Mở rộng DATALOG với các hàm (tiếp) Vi dụ: Có bản đồ đường đi nối các thành phố (đồ thị có hướng) {Đường_đi (x, y, d) ← Cung (x, y, d); Đường_đi (x, y, e+d) ← Đường_đi (x, z, e), Cung (z, y, d)} ? Đường_đi (Hà nội, Sài gòn, t) Hồ Cẩm Hà - ĐHSPHN 21 Mở rộng DATALOG với các hàm (tiếp) Ví dụ: „ {lương (100) ← ; cao_hơn (y, x) ← lương(x), x<y } ? cao_hơn (y, x) cho vô số đáp số „ {nguyên (0) ←; nguyên(x+1) ← Nguyên (x)} chương trình này phát sinh tất cả các số nguyên dương Một luật gọi là có trường hạn chế nếu tất cả các biến trong đầu luật đều xuất hiện trong một tân từ quan hệ ở thân luật. Một chương trình gọi là an toàn nếu không phát sinh vô hạn đáp số Hồ Cẩm Hà - ĐHSPHN 22 Mở rộng DATALOG với phép phủ định Ví dụ : tính độ dài các đường đi trên đồ thị có hướng, có sử dụng quan hệ lưu trữ các cung bị cấm {Đường_đi (x, y, d) ← Cung (x, y, d), ¬ Cấm(x, y); Đường_đi (x, y, e+d) ← Đường_đi (x, z, e), Cung (z, y, d), ¬ Cấm(z, y)} Giao của hai mô hình nói chung không là mô hình Hồ Cẩm Hà - ĐHSPHN 23 Mở rộng DATALOG với phép phủ định (tiếp) Ví dụ: {chim (ngựa_có_cánh) ← ; chim_cánh_cụt (x) ← chim (x), ¬bay(x); bay(x) ← chim (x), ¬ chim_cánh_cụt (x)} Chương trình này có 2 mô hình: Mô hình 1: {chim (ngựa_có_cánh), chim_cánh_cụt (ngựa_có cánh)} Mô hình 2: {chim (ngựa_có_cánh), bay (ngựa_có cánh)} Giao của hai mô hình là {chim (ngựa_có_cánh)} không là mô hình Hồ Cẩm Hà - ĐHSPHN 24 Mở rộng DATALOG (tiếp) „ Mở rộng với các tập: để có ngôn ngữ khả năng xử lí các thuộc tính đa trị chứa tập các giá trị „ Mở rộng với các phép cập nhật „ Mở rộng với điều kiện phi Horn 25 Xin cảm ơn !