Giáo trình Tin Học: Datalog Ngôn ngữ luật cho các CSDL

Chia sẻ: Abcdef_12 Abcdef_12 | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

133
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hệ QTCSDL suy diễnTrướ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)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Tin Học: Datalog Ngôn ngữ luật cho các CSDL

1 Datalog- Ngôn ngữ luật cho các CSDL
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 2
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 3
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 4
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 5
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 6
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 7
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),mTOTIEN(z,y) Hồ Cẩ Hà - ĐHSPHN 8
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 9
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 10
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 11
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 12
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 13
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 14
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 15
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 16
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 17
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 18
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 19
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 20