Số hóa bởi Trung tâm Học liệu ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

PHẠM THỊ CHI LÊ

TỐI ƢU HÓA TRUY VẤN
CƠ SỞ DỮ LIỆU SUY DIỄN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên - 2013
Số hóa bởi Trung tâm Học liệu LỜI CAM ĐOAN
Tôi cam đoan luận văn này là do bản thân tự nghiên cứu và thực hiện theo sự
hƣớng dẫn khoa học của PGS.TS Đoàn Văn Ban.
Tôi hoàn toàn chịu trách nhiệm về tính pháp lý quá trình nghiên cứu khoa học
của luận văn này.

Thái Nguyên, ngày tháng năm 2013
Ngƣời Cam Đoan
Phạm Thị Chi Lê

Số hóa bởi Trung tâm Học liệu

1
LỜI CẢM ƠN
Trƣớc tiên tôi bầy tỏ lời cảm ơn chân thành đến các Thầy, Cô giáo đã
giảng dạy, hƣớng dẫn và giúp đỡ tôi trong thời gian học tập và nghiên cứu
hoàn thành luận văn này.
Xin đƣợc bầy tỏ lòng biết ơn sâu sắc tới Thầy giáo PGS.TS Đoàn Văn

qua ngƣời ta đã tập trung nghiên cứu và cho nhiều kết quả thú vị cả lĩnh vực
lý thuyết và ứng dụng. CSDL suy diễn có khả năng sử dụng các tính năng của
lập trình logic để thực hiện các suy diễn nhằm tạo ra thông tin mới dựa trên
các luật suy diễn và dữ liệu đƣợc lƣu trữ trong cơ sở dữ liệ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ó 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
Số hóa bởi Trung tâm Học liệu



Số hóa bởi Trung tâm Học liệu

4
Chƣơng 3: Cài đặt chƣơng tr .
Phần phụ lục giới thiệu về Swi-Prolog và hƣớng dẫn cách thức làm việc với
Swi-Prolog. Số hóa bởi Trung tâm Học liệu

5
CHƢƠNG 1. CƠ SỞ DỮ LIỆU SUY DIỄN VÀ NGỮ NGHĨA
CHƢƠNG TRÌNH LOGIC
Chương 1 trình bày kiến thức cơ bản về cơ sở dữ liệu suy diễn với các khái
niệm, cấu trúc, mô hình, mục đích, chức năng cơ bản của cơ sở dữ liệu suy
diễn và giới thiệu một số hệ quản trị cơ sở dữ liệu suy diễn như hệ LDL, hệ
Anditi, hệ Coral; giới thiệu về chương trình logic với các khái niệm cơ bản
như logic vị từ, hạng thức, công thức đóng, bộ kí tự và ngữ nghĩa của
chương trình logic; cuối chương giới thiêu về cơ sở dữ liệu Horn với các khái
niệm, định lý, hệ quả, ngữ nghĩa của cơ sở dữ liệu Horn và các ví dụ để minh

Khái niệm về CSDL suy diễn cũng đƣợc nhiều nhà nghiên cứu đề cập theo
hƣớng phát triển các kết quả mà Green đã đạt đƣợc vào năm 1969 về các hệ
thống hỏi – đáp. Xuất phát từ quan điểm lý thuyết, các CSDL suy diễn có thể
Có khả năng quản lí các khối
lƣợng lớn dữ liệu
Có các khả năng suy luận
- Dữ liệu ngoại diên: các sự kiện
- Tính toàn vẹn, khôi phục, tối
ƣu hoá câu hỏi
- Đƣợc bảo trì bởi những nhà
quản trị
- Tri thức nội hàm: các luật
- Biểu diễn tri thức
- Đƣợc bảo trì bởi các chuyên
gia
Cần những khả năng suy luận
bên trong cơ sở dữ liệu
Cần một hệ thống hoàn thiện để
quản lí các khối lƣợng lớn thông
tin
Các hệ CSDL
Các hệ chuyên gia
Cơ sở dữ liệu suy
diễn
Hình 1.1. Sự tiến triển song song của các hệ CSDL và các hệ chuyên
gia
Số hóa bởi Trung tâm Học liệu


Số hóa bởi Trung tâm Học liệu

8
- Tập các sự kiện (facts): cho phép biểu diễn thông tin cơ sở đƣợc biết là
đúng trong CSDL.
- Tập các luật suy diễn (deductive rules): cho phép suy dẫn các sự kiện mới
từ các sự kiện đƣợc lƣu trữ trong CSDL.
- Tập các ràng buộc toàn vẹn (integrity constrains): tƣơng ứng với các điều
kiện mà mỗi trạng thái của CSDL phải thỏa mãn.
Ví dụ 1.1 Một CSDL suy diễn mô tả các mối quan hệ gia tộc
- Sự kiện
Bố(Dƣơng, Tân)
Mẹ(Mai, Bách)
Bố(Phát, Mai)
- Các luật suy diễn
Cha_mẹ(x, y) ← Bố(x, y)
Cha_mẹ(x, y) ← Mẹ(x, y)
Bà(x, y) ← Mẹ(x, z) ^ Cha_mẹ(z, y)
Tổ_tiên(x, y) ← Cha_mẹ(x, y)
Tổ_tiên(x, y) ← Cha_mẹ(x, z) ^ Tổ_tiên(z, y)
- Các rằng buộc toàn vẹn
IC1(x) ← Cha_mẹ(x, x)
IC2(x) ← Bố(x, y) ^ Mẹ(x,y)
Tóm lại, một CSDL suy diễn là một bộ ba (F, DR, IC), trong đó F là một
tập hữu hạn các sự kiện cơ sở, DR là một tập hữu hạn các luật suy diễn, và IC
là một tập hữu hạn các rằng buộc toàn vẹn. Tập F các sự kiện đƣợc gọi là
phần ngoại diên của CSDL (còn gọi là CSDL ngoại diên – EDB), còn tập DR
và IC làm thành nội hàm của CSDL (còn gọi là CSDL nội hàm – IDB) [10],
[16], [20].

P
2
… P
k

Tƣơng đƣơng với câu:
¬P
1
¬ P
2
. . . ¬P
k
R
1
R
2
. . . R
m

Mệnh đề đƣợc gọi là có tầm hạn chế nếu mọi biến xuất hiện ở vế phải cũng
xuất hiện ở vế trái.
Kỹ thuật để xử lý dữ liệu nhƣ trả lời câu hỏi, kiểm tra điều kiện toàn vẹn.
Tuy nhiên, để dễ biểu diễn hình thức các khái niệm về CSDL suy diễn,
ngƣời ta thƣờng dùng phép toán vị từ, tức logic vị từ bậc nhất. Logic vị từ bậc
nhất là ngôn ngữ hình thức dùng để thể hiện các quan hệ giữa các đối tƣợng
và để suy diễn ra quan hệ mới từ những quan hệ đƣợc xem là đúng.
1.1.2 Mục đích và đặc trƣng cơ bản của CSDLSD
 Mục đích chính của CSDLSD
Mở rộng ngôn ngữ CSDL theo cách tiếp cận logic để hỗ trợ cho truy vấn,
lập luận và lập trình dựa vào các luật suy diễn [1].

Đệ qui: cho định nghĩa một quan hệ thông qua chính nó
Có khả năng chấp nhận phủ định (xử lí vị từ âm) để suy dẫn đến các sự
kiện không tồn tại
Thực hiện đƣợc các hàm số học và các hàm đƣợc định nghĩa bởi ngƣời
dùng
Cập nhật các sự kiện thông qua các luật
Có tính đơn nguyên với các mức trừu xuất liên tiếp và các siêu luật
Số hóa bởi Trung tâm Học liệu

11
Có nhiều các tiếp cận để xây dựng, xuất phát từ một hệ quản trị CSDL
quan hệ:
+ Mở rộng, bổ sung các sự kiện, các luật
+ Sửa đổi, cập nhật
1.1.4 Một số hệ QT CSDL suy diễn
1.1.4.1 Hệ LDL/LDL++
Dự án LDL thực hiện ở MCC (1984), Austin, Texas, sau phát triển tiếp
LDL++ (1990) nhằm phát triển những hệ thống CSDLSD trên cơ sở kết hợp
Prolog với CSDLQH và thực hiện suy diễn theo kỹ thuật bottom-up. Version
5.1 đƣợc phát triển ở UCLA (University of California, Los Angeles) [1], [17].
Hệ ngôn ngữ dữ liệu logic LDL (logic data language system) cung cấp một
ngôn ngữ khai báo dựa trên logic và tích hợp CSDL quan hệ với kỹ thuật lập
trình logic để hỗ trợ những ứng dụng phức tạp và dựa vào cơ sở tri thức.

Hình 1.2: Kiến trúc của LDL++
 Chƣơng trình dịch (Compiler)


truy vấn vào CSDL cục bộ.
Số hóa bởi Trung tâm Học liệu

13
Thực hiện tƣơng tự đối với CSDL khác thông qua quản trị CSDL ngoại
diên (External Database Manager) và quản trị vị từ ngoại diên (External
Predicate Manager).
Thực hiện các hàm ngoại diên (external functions) hoặc các gói phần mềm
(software packages) thực hiện theo lời gọi hàm của C/C++.
 Giao diện ngƣời sử dụng (User Interface)
Tất cả các ứng dụng viết bằng C/C++ có thể gọi LDL++ system thông qua
chuẩn API; những ứng dụng viết bằng LDL++ có thể nhúng vào những hệ
thống hƣớng thủ tục khác.
Một trong những ứng dụng có thể thông dịch hƣớng dòng lệnh hỗ trợ thực
hiện một tập lệnh đƣợc định nghĩa trƣớc bởi ngƣời sử dụng (NSD). Giao diện
viết bằng C++ có thể thay thế bằng những giao diện đồ họa GUI, mà không
cần thay đổi cấu trúc bên trong của hệ thống.
Hiện nay ngƣời ta có thể sử dụng Java để phát triển giao diện để hỗ trợ truy
cập từ xa (trên mạng).
Hệ LDL++ hiện nay có thể link trực tiếp với Sybase, Oracle, DB2, và giao
tiếp với các hệ CSDL khác (viết bằng Java) thông qua JDBC.
Các qui tắc suy diễn trong chƣơng trình không phân biệt giữa các quan hệ
nội hàm (internal relations) và quan hệ ngoại diên (external relations).
Các quan hệ từ những CSDL SQL ngoại diên (external SQL databases)
đƣợc khai báo giống nhƣ quan hệ nội trong sơ đồ LDL++, nhƣng đƣợc bổ
sung phần đặc tả kiểu và tên của SQL server để xử lý dữ liệu.
Ví dụ 1.2 Ví dụ về một khai báo lƣợc đồ (LDL++ schema) sử dụng để truy

toán của CSDL nhƣ kết nối (joining), hợp (merging), trừ (subtracting) các
quan hệ theo yêu cầu của clients.
Trong Aditi, mỗi client có một server riêng, nhƣng nó cũng có thể chia sẻ
với các server của những clients khác.
Hệ Aditi có 5 đặc trƣng phân biệt với những hệ CSDLSD khác:
+ Nó đƣợc xây dựng dựa trên đĩa (disk-based) và cho phép các xử
lý những quan hệ lớn, quá cỡ của bộ nhớ.
Số hóa bởi Trung tâm Học liệu

15
+ Hỗ trợ truy cập đồng thời nhiều ngƣời sử dụng.
+ Thực hiện đƣờng dẫn xử lý song song ở nhiều mức khác nhau.
+ Cho phép lƣu trữ các hạng thức có chứa ký hiệu hàm.
+ Định hƣớng chính là tính toán, định giá truy vấn bottom/up
giống nhƣ nhiều CSDLSD khác, nhƣng cũng hỗ trợ thực hiện định
giá các vị từ top/down.
1.1.4.3 Hệ CORAL
Hệ CORAL (1992) ở University of Wisconsin, Madison. Là hệ thống
thực hiện theo hƣớng bottom-up và đƣợc viết bằng C++ [1], [17].
Thƣờng các ứng dụng CORAL phần nhiều là logic, nhƣng ngƣời lập trình
cũng có thể dùng C++ để tạo lập những kiểu dữ liệu trừu tƣợng mới và định
nghĩa, thao tác đối với các quan hệ.
Các quan hệ cơ sở CORAL có thể lƣu trữ trong các file dữ liệu riêng của
CORAL hoặc trong hệ quản trị lƣu trữ dữ liệu EXODUS (Carey et al., 1986).
CORAL hỗ trợ tập ( set) và cả đa tập ( multisets).
CORAL sử dụng những thuật toán chuyên biệt dựa phần nhiều vào kỹ thuật
Prolog hơn là kỹ thuật CSDL để cài đặt các phép toán quan hệ.

(nếu và chỉ nếu).
+ Các ký hiệu lƣợng tử: (với mọi), (tồn tại).
+ Dấu ngoặc đơn trái (, dấu ngoặc đơn phải ), dấu phẩy ,.
Định nghĩa (Hạng thức) Gọi A là bộ ký tự. Hạng thức đƣợc định nghĩa đệ
qui nhƣ sau:
(i) Mỗi hằng trong A là một hạng thức.
(ii) Mỗi biến A là một hạng thức.
(iii) Nếu f là ký hiệu hàm n ngôi (n-ary) trong A và t
1
, ,t
n
là các hạng
thức thì f(t
1
, ,t
n
) là một hạng thức.
(iv) Hạng thức chỉ đƣợc sinh ra bởi các quy tắc trên.
Số hóa bởi Trung tâm Học liệu

17
Định nghĩa (Nguyên tố) Giả sử t
1
, ,t
n
là các hạng thức, p là ký hiệu vị từ n
ngôi thì p(t


18
Định nghĩa (Literal) Nguyên tố hoặc phủ định của một nguyên tố đƣợc
gọi là một literal. Một literal dương là một nguyên tố, literal âm là phủ định
của một nguyên tố.
Định nghĩa Mệnh đề (Clause) là một công thức có dạng:
L
1
L
n
(1)
trong đó L
1
, ,L
n
là các literal.
Nếu A
1
, , A
k
là các literal dƣơng trong L
1
, , L
n
và B
1
, , B
m
là các
literal âm trong L


B
m

là tiền đề, A
1

A
k

là kết luận.
Mệnh đề (2) có thể viết A
1
, , A
k
B
1

, , B
m

Nếu k = 1 thì nó đƣợc gọi là mệnh đề xác định (definite clause), nghĩa là
mệnh đề có dạng (mệnh đề Horn):
A B
1

B
m

(m 0) (3)

r
2
: p(X, Z) e(X, Y) p(Y, Z),
r
3
: p(1, Y).
Trong đó r
1
, r
2
là các mệnh đề xác định, trong mệnh đề r
1
thì p(X, Y) là đầu
và e(X, Y) là thân, trong mệnh đề r
2
thì p(X, Z) là đầu và e(X, Y) p(Y, Z) là
thân, mệnh đề r
3
là một đích.
1.2.2 Chƣơng trình logic
Chƣơng trình logic là tập hữu hạn khác rỗng các mệnh đề (qui tắc) xác định
có dạng:
p q
1
q
n
(n 0)
Trong đó, các vị từ p, q
i
(i = 0,…,n) là các nguyên tố có các đối là hằng

4
: related(X,Y) sibling(X,Y),
r
5
: related(X,Y) related(X,Z) parent(Y,Z),
r
6
: related(X,Y) related(Z,Y) parent(X,Z).
Trong đó parent là vị từ EDB và parent(A, B) có nghĩa là B là cha, mẹ
của A, định nghĩa các sự kiện trong CSDL, còn các vị từ sibling, cousin,
related là các vị từ IDB.
1.2.3 Thể hiện của chƣơng trình logic
Thể hiện (diễn dịch) I của ngôn ngữ bậc nhất L bao gồm:
+ Một tập D khác rỗng, đƣợc gọi là miền của thể hiện I.
+ Mỗi hằng c trong L xác định một phần tử c
I
của D.
+ Mỗi ký hiệu hàm f bậc n trong L với một ánh xạ f
I
: D
n
D,
+ Mỗi ký hiệu vị từ p bậc n trong L với một ánh xạ p
I
: D
n{true, false}.
Thể hiện của các hằng, hàm và ký hiệu vị từ là cơ sở cho việc gán giá trị

q(b,c) ,
p(X,Y) q(X,Y),
p(X,Y) p(X,Z) p(Z,Y).
Vũ trụ Herbrand của P là U
P
= { a, b, c } và cơ sở Herbrand của P là:
B
P
= { 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 (CSDLSD xác định) Một CSDL suy diễn xác định
(CSDLSD) là một cặp <P, DB>, trong đó P là chƣơng trình logic không chứa
ký hiệu hàm, DB là CSDL EDB cho trƣớc.
Ví dụ 1.7 Chƣơng trình logic P gồm các quy tắc:
r
1
: path(X,Y) arc(X,Y),
r
2
: path(X,Z) arc(X,Y) hoặc path(Y,Z).
CSDL EDB gồm các bộ của vị từ arc {(1,2), (1, 4), (2,3), (3, 1)}.
Thể hiện Hebrand I của ngôn ngữ bậc nhất L bao gồm:
+ Một miền D là tập phổ dụng U
L
.
+ Mỗi hằng đƣợc gán bởi chính nó.
+ Mỗi ký hiệu hàm f n-biến đƣợc gán bởi một ánh xạ .
f
I
: U

Số hóa bởi Trung tâm Học liệu

22
1.3 Ngữ nghĩa của chương trình Prolog
Một chƣơng trình Prolog có thể đƣợc hiểu theo nghĩa khai báo (declarative
signification) hoặc theo nghĩa thủ tục (procedural signification). Vấn đề là cần
phân biệt hai mức nghĩa của một chƣơng trình Prolog, là nghĩa khai báo và
nghĩa thủ tục. Ngƣời ta còn phân biệt mức nghĩa thứ ba của một chƣơng trình
Prolog là nghĩa lôgic (logical semantic).
 Nghĩa khai báo của chƣơng trình Prolog
Về mặt hình thức, nghĩa khai báo, hay ngữ nghĩa chủ ý (intentional
semantic) xác định các mối quan hệ đã được định nghĩa trong chƣơng trình.
Nghĩa khai báo xác định những gì là kết quả (đích) mà chƣơng trình phải tính
toán, phải tạo ra.
Nghĩa khai báo của chƣơng trình xác định nếu một đích là đúng, và trong
trƣờng hợp này, xác định giá trị của các biến.
 Nghĩa lôgic của các mệnh đề
Nghĩa lôgic thể hiện mối liên hệ giữa đặc tả lôgic (logical specification)
của bài toán cần giải với bản thân chƣơng trình.
 Nghĩa thủ tục của Prolog
Nghĩa thủ tục, hay ngữ nghĩa thao tác (operational semantic), lại xác định
làm cách nào để nhận đƣợc kết quả, nghĩa là làm cách nào để các quan hệ
được xử lý thực sự bởi hệ thống Prolog.
Nghĩa thủ tục tƣơng ứng với cách Prolog trả lời các câu hỏi như thế nào
(how) hay lập luận trên các tri thức. Trả lời một câu hỏi có nghĩa là tìm cách
xóa một danh sách. Điều này chỉ có thể thực hiện đƣợc nếu các biến xuất hiện
trong các đích này đƣợc ràng buộc sao cho chúng đƣợc suy ra một cách lôgic