Header Page 1 of 126.

ĐẠ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

Footer Page 1 of 126.

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

/>

Header Page 2 of 126.

ĐẠ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

Chuyên ngành : Khoa học máy tính

Footer Page 3 of 126.

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

/>

Header Page 4 of 126.

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
Ban đã tận tình hƣớng dẫn, giúp đỡ và đóng góp cho tôi nhiều ý kiến quí báu
để hoàn thành luận văn này.
Xin chân thành cảm ơn các Thầy, Cô giáo Trƣờng Đại học Công nghệ
thông tin & truyền thông Thái Nguyên và Viện Công nghệ thông tin đã giảng
dạy, giúp đỡ và tạo điều kiện thuận lợi cho tôi trong thời gian học tập tại
Trƣờng.
Tôi xin gửi lời cảm ơn đến các bạn đồng nghiệp và các bạn học viên lớp
Cao học K10A khóa 2011 – 2013 đã giúp đỡ và tạo điều kiện thuận lợi cho tôi
trong quá trình học tập và làm luận văn.
Cuối cùng, xin chân thành cảm ơn gia đình và bạn bè đã động viên, quan
tâm, giúp đỡ tôi hoàn thành khóa học và luận văn.

PHẦN MỞ ĐẦU
Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực đƣợc tập trung nghiên
cứu và phát triển của công nghệ thông tin, nhằm giải quyết các bài toán quản

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
Footer Page 5 of 126.

/>

Header Page 6 of 126.

3

hợp với câu truy vấn. Tuy nhiên quá trình tính toán có thể kéo dài vô hạn. Các
phƣơng pháp dƣới lên đảm bảo tính kết thúc trong quá trình tìm lời giải của
câu truy vấn, nhƣng điều này không có nghĩa là nó hiệu quả. Chúng thƣờng
không định hƣớng đích, nhiều sự kiện không thích hợp với câu truy vấn cũng
đƣợc tính. Các chiến lƣợc dƣới lên không xem xét câu truy vấn trong suốt quá
trình định giá, tức là việc tính toán không đƣợc gắn liền với câu truy vấn nhƣ
thƣờng xảy ra trong các phƣơng pháp trên xuống.
Trong thời gian gần đây, một số phƣơng pháp mở rộng để trả lời câu truy

.

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
Footer Page 7 of 126.

/>

Header Page 8 of 126.

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
chứng cho phần lý thuyết.
1.1 Giới thiệu về cơ sở dữ liệu suy diễn
Tính từ thời điểm xuất hiện các hệ quản trị cơ sở dữ liệu đầu tiên (khoảng
những năm 1960) đến nay, công nghệ CSDL đã tiến triển nhanh chóng, và đã
thu đƣợc rất nhiều thành tựu trong các lĩnh vực ứng dụng khác nhau của công
nghệ thông tin. Một đặc điểm chung của các hệ CSDL là khả năng quản lí
những khối lƣợng lớn dữ liệu, tuy nhiên thƣờng chỉ thực hiện các thao tác đơn


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ơ 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
Hình trên đây minh hoạ sự tiến triển song song của các hệ CSDL và các hệ
chuyên gia.
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ơ sở dữ liệu 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.
Cấu trúc của một CSDL suy diễn
Một CSDL suy diễn là một bộ gồm ba tập hữu hạn:

Số hóa bởi Trung tâm Học liệu
Footer Page 10 of 126.

/>

Header Page 11 of 126.

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)

quát của các mệnh đề biểu diễn sự kiện và luật suy diễn là:
R2 … Rm

R1

P2 … Pk

P1

Tƣơng đƣơng với câu:
¬P1

¬ P2

...

¬Pk

R1

R2 . . .

Rm

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

Hệ quản trị CSDLSD phải có các chức năng nhƣ sau:
Ngôn ngữ định nghĩa dữ liệu DDL (Data Definition Language),
Ngôn ngữ thao tác dữ liệu DML (Data Manipulation Language)
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ệ, sự kiện mới (CSDL tiềm ẩn)
Có khả năng thực hiện các phép toán quan hệ
Xử lí đƣợc các tập hợp bao gồm các hàm kết tập: nhƣ các tính toán đa trị
(Max, Min, Sum, Avg, Count)
Đệ 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
Footer Page 13 of 126.

/>

Header Page 14 of 126.

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

+ Dịch sang PCG rồi chuyển sang cho Interpreter.
 Quản trị CSDL (Database Manager)
Hệ quản trị CSDLSD hỗ trợ :
(i) Truy cập nhanh theo đƣờng dẫn vào CSDL của hệ thống (fast-path).
(ii) Tích hợp với những hệ quản trị CSDL khác (external DBMS), CSDL
ngoại. Nghĩa là cơ thể phát triển những hệ thống mới trên cơ sở tích hợp
những hệ thống có sẵn.
CSDLSD đƣợc quản trị bởi Fact Base Manager. Module này hỗ trợ để quản
trị, tìm kiếm các đối tƣợng phức tạp của LDL++, kể cả các tập hợp, danh
sách, và những quan hệ tạm thời đƣợc tạo ra trong quá trình tính toán.
CSDLSD cũng hỗ trợ external database manager để thực hiện tối ƣu hóa
truy vấn đối với những CSDL SQL.
 Thông dịch (Interpreter)
Đầu vào là đồ thị PCG ứng với câu truy vấn LDL++ đƣợc sinh ra bởi
chƣơng trình dịch.
Thông dịch các câu truy vấn thông qua các lời gọi từng thành phần của câu
truy vấn vào CSDL cục bộ.

Số hóa bởi Trung tâm Học liệu
Footer Page 15 of 126.

/>

Header Page 16 of 126.

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).


14

from sybase_tarski
use payroll
user_name ’Nam’
application_name ’downsizing’
interface_filename ’/tmp/ldl++/demo/interfaces’
password maN
}).
Hệ LDL++ sinh ra các truy vấn SQL vào external database server để thực
hiện:
+ Các phép join, select, project tƣơng ứng với các mục đích dƣơng
(positive goals) trong các qui tắc,
+ Thiết lập sự khác biệt tƣơng ứng giữa các mục đích phủ định (negated
goals),
+ Phép kết nhập (aggregate) đã đƣợc xác định trong các đầu của qui tắc,
1.1.4.2 Hệ Aditi
Aditi (University of Melbourne, 1988) đƣợc xây dựng theo mô hình
client/server đã đƣợc áp dụng trong rất nhiều hệ CSDL thƣơng mại phổ biến
[1], [17].
Theo mô hình này, NSD tƣơng tác với tiến trình giao diện với NSD (userinterface process) và client trao đổi với server chính để thực hiện những phép
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

chọn lập trình logic làm mô hình cơ s ở cho dự án Các hệ thống máy tính đời
thứ 5 của Nhật (Japanese Fifth Generation Computer Systems Project) đã mở
đầu cho sự phát triển của các ngôn ngữ lập trình logic khác.

Số hóa bởi Trung tâm Học liệu
Footer Page 18 of 126.

/>

Header Page 19 of 126.

16

1.2.1 Các khái niệm cơ bản
Trong mục này trình bày các khái niệm cơ bản cần để hiểu tổng quan về
chương trình logic.
Logic vị từ (Predicate) là ngôn ngữ hình thức cho phép biểu diễn đối tƣợng
đƣợc mô tả thông qua mệnh đề, biểu diễn quan hệ giữa các đối tƣợng và các
phép toán logic vị từ. Logic vị từ đƣợc định nghĩa bởi tập các từ vựng, các
văn phạm, các qui tắc (luật). Nó cho phép chúng ta xây dựng công thức vị từ
và diễn dịch (tính) công thức thông qua thể hiện.
Định nghĩa (Bộ ký tự) Bộ ký tự bao gồm các lớp ký hiệu sau:
+ Hằng là các xâu bắt đầu bởi chữ cái viết thƣờng a, b, c,...
+ Biến là xâu bất kỳ bao gồm các ký tự của bảng chữ cái và các chữ
số, thƣờng ký hiệu bởi các chữ cái in hoa X, Y, Z,...,
+ Các ký hiệu hàm, thƣờng ký hiệu bởi f, g, h,... ,
+ Các ký hiệu vị từ, thƣờng ký hiệu bởi p, q, r,...,
+ Các hằng vị từ: true, false
+ Các ký hiệu kết nối:



17

Định nghĩa (Nguyên tố) Giả sử t1,...,tn là các hạng thức, p là ký hiệu vị từ n
ngôi thì p(t1,...,tn) đƣợc gọi là một công thức nguyên tố (hoặc đơn giản chỉ gọi
là nguyên tố).
Định nghĩa (Công thức) Công thức đƣợc định nghĩa đệ qui nhƣ sau:
(i) Mỗi nguyên tố là một công thức.
(ii) Các hằng vị từ true và false là các công thức.
(iii)Nếu E và F là các công thức thì: (E

F),

E), (E F), (E

F),

F) là các công thức.

(E

(iv) Nếu E là công thức và X là một biến trong miền D thì

X(E),

X(E) là các công thức.
(v) Công thức chỉ đƣợc sinh ra bởi một số hữu hạn các quy tắc trên.
Định nghĩa (Ngôn ngữ bậc nhất) Một ngôn ngữ bậc nhất (first order
language) bao gồm một bộ ký tự và những công thức đƣợc xây dựng trên bộ
ký 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:
L1 ... Ln

(1)

trong đó L1,...,Ln là các literal.
Nếu A1,..., Ak là các literal dƣơng trong L1,..., Ln và

B1,...,

Bm là các

literal âm trong L1,...,Ln thì công thức (1) đƣợc viết:
A1

...

Ak

B1

...

Bm



B1

...

Bm

(m

0)

(3)

Mệnh đề này chứa đúng một nguyên tố A đƣợc gọi là đầu (head) hay kết
luận và B1

...

Bm đƣợc gọi là thân (body) hay tiền đề của mệnh đề.

Trong mệnh đề (3), nếu m = 0 thì nó đƣợc gọi là mệnh đề đơn vị (unit
clause), nghĩa là mệnh đề có dạng: A

, với thân rỗng còn đƣợc gọi là các sự

kiện.
Đích (goal) là mệnh đề có dạng:
B1

...

và e(X, Y) là thân, trong mệnh đề r2 thì p(X, Z) là đầu và e(X, Y)

p(Y, Z) là

thân, mệnh đề r3 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

q1

...

qn

(n

0)

Trong đó, các vị từ p, qi (i = 0,…,n) là các nguyên tố có các đối là hằng
hoặc biến.
Trong CSDL SD các vị từ chỉ xuất hiện trong thân các quy tắc đƣợc gọi là
vị từ CSDL ngoại diên, vị từ EDB (Extensional Database predicate), hoặc
CSDL EDB.
+ Tƣơng ứng với tập sự kiện đang, đã có.
+ Đƣợc xây dựng từ các nội dung dữ liệu trong CSDL.
Trong CSDL quan hệ: tập các quan hệ, các bảng.
Trong chƣơng trình logic các vị từ xuất hiện ở đầu quy tắc đƣợc gọi là các
vị từ nội hàm (hoặc vị từ IDB (Intensional Database predicate), CSDL IDB.


r3: cousin(X,Y)

parent(X,Xp)

parent(Y,Yp)

r4: related(X,Y)

sibling(X,Y),

r5: related(X,Y)

related(X,Z)

parent(Y,Z),

r6: related(X,Y)

related(Z,Y)

parent(X,Z).

cousin(Xp,Yp),

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:

21

- Nếu A
hiệu I

BP nhƣng A

I, ta nói rằng A sai (có giá trị false) trong I và ký

A.

Ví dụ 1.6 Xét chƣơng trình logic không chứa ký hiệu hàm P nhƣ sau:
q(a,b)

,

q(b,c)

,

p(X,Y)

q(X,Y),

p(X,Y)

p(X,Z)

p(Z,Y).



+ Mỗi ký hiệu vị từ p n-biến đƣợc gán bởi ánh xạ.
PI : ULn

{true, false}

Số hóa bởi Trung tâm Học liệu
Footer Page 24 of 126.

/>

Header Page 25 of 126.

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)