TrướchếtđólàmộthệQTCSDL: cóngônngữDDL, DML
Đemchongườidùngmộtgiaodiệncóngônngữluật, cho
phép: từcácquanhệcơsở(lưutrữtrongCSDL càiđặt) suy
diễnranhữngquanhệmới(CSDL tiềmẩn)
25 trang |
Chia sẻ: tranhoai21 | Lượt xem: 1408 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Ngôn ngữ luật cho các cơ sở dữ liệu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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 !