Bài giảng Datalog: Ngôn ngữ luật cho các cơ sở dữ liệu

Bài giảng Datalog Ngôn ngữ luật cho các CSDL trình bày các nội dung: Hệ quản trị cơ sở dữ liệu suy diễn, các ngôn ngữ luật đối với các cơ sở dữ liệu, datalog, ngữ nghĩa của chương trình datalog, thủ tục đơn giản tính mô hình nhỏ nhất Tr,... Mời các bạn cùng tham khảo nội dung chi tiết bài giảng.
Nội dung trích xuất từ tài liệu:
Bài giảng Datalog: Ngôn ngữ luật cho các cơ sở dữ liệu 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 2Cá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 3Datalog„ 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 DatalogCá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ếnCô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), Hồ CẩmTOTIEN(z,y) 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 10Datalog 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ệnb) 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 12Ngữ 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 13Thủ 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 14Thủ 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) ...