ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
________ ________
BÀI THU HOẠCH MÔN HỌC
Môn: CƠ SỞ DỮ LIỆU NÂNG CAO
CƠ SỞ DỮ LIỆU SUY DIỄN VÀ
PROLOG
Học viên thực hiện:
CH1101154
TRẦN THỊ TƯỜNG VI

TP. HCM, năm 2012
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Mở đầu
Bài thu hoạch này chỉ gói gọn trong 2 phần:
Phần 1: Giới thiệu kiến thức sơ lược về cơ sở dữ liệu suy diễn và Prolog
Phần 2: Áp dụng kiến thức tìm hiểu trên để giải bài toán về quan hệ
‘ancestor’

MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 1 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
MỤC LỤC
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG 1
TP. HCM, năm 2012 1
Mở đầu 1
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG 2
PHẦN I : LÝ THUYẾT 3
I. CƠ SỞ DỮ LIỆU SUY DIỄN 3
II. NGÔN NGỮ PROLOG 5

PHẦN II : ÁP DỤNG 9
I. GIẢI BÀI TOÁN 9
II. NHẬN XÉT 12
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 2 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
PHẦN I : LÝ THUYẾT
I. CƠ SỞ DỮ LIỆU SUY DIỄN
1. Giới thiệu
- CSDL suy diễn tích hợp CSDL và lập trình logic. Lập trình logic có thế
mạnh là khả năng diễn đạt tri thức, ràng buộc toàn vẹn.
- CSDL có khả năng quản trị dữ liệu, bảo mật dữliệu.
- 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 CSDL.
2. Mô hình dữ liệu suy diễn
- Có 2 đặc tính quan trọng của mô hình cấu trúc dữ liệu suy diễn như sau:
a. Mô hình dữ liệu Suy diễn cung cấp một cách tiếp cận hợp nhất tới định
nghĩa của những cấu trúc dữ liệu và những thủ tục.
b. Mô hình dữ liệu Suy diễn qui định một khả năng để khôi phục không
những rõ ràng dữ liệu được cất giữ mà còn suy luận dữ liệu một cách
hợp lý. Hay nói cách khác, những hệ thống cơ sở dữ liệu suy diễn có
khả năng kế xuất và đưa ra những kết luận mang tính logic.
- Để máy tính có thể xữ lý được các thông tin, những biểu thức thực tế cần
được viết bằng mã được quy định bởi một tập hợp các quy tắc, hình thức ký
pháp mã hóa. Những hệ thống cơ sở dữ liệu suy diễn hoạt động trên những
quy tắc, hình thức được gọi chung là những vị từ, ký hiệu vị từ.
- Những khuôn mẫu thực tế là một ký pháp đại diện cho một số thực tế. Thật
sự, một khuôn mẫu thực tế là một hàm logic hợp lệ ( ví dụ trả lại giá trị "
Đúng " nếu những giá trị biến thiên có thể được tìm thấy trong cơ sở dữ

liệu hoặc trả lại giá trị " Sai " nếu những giá trị biến thiên không được tìm
thấy trong cơ sở dữ liệu
3. Quy tắc suy diễn
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 3 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
- Những quy tắc suy diễn được định nghĩa:
Ký hiệu thuật ngữ (x1, x2,…xn)  hàm logic (x1,x2,…xn)
- Những quy tắc suy diễn được định nghĩa như sau: “nếu có sự kết hợp đặc
biệt giữa những biến tự do x1, x2 trong thuật ngữ đúng thì với những giá trị
giống như vậy cũng sẽ cho hàm logic đúng.” Như vậy, những quy tắc suy
diễn được xác định mới từ những suy luận thực tế.
- Trong đó:
o Biến là những định danh đặc biệt để giữ một mục tin dữ liệu trong
thời gian dữ liệu xử lý.
Chúng ta cũng có thể sử dụng những biến trên những miền khác,
hay định nghĩa hai và nhiều biến hơn nào trên những mục tin dữ liệu
của một miền.
o Logic là ký pháp vị từ ( Biến 1, Biến 2,…) định nghĩa một hàm
lôgic mà trả lại những giá trị Đúng hay Sai phụ thuộc vào một hay
nhiều giá trị hiện tại của các biến. Những biến (Biến 1, Biến 2,…)
được gọi là những biến tự do.
o Những số hạng lôgic có thể được kết hợp vào trong một hàm lôgic
mới, phức tạp hơn bằng phương pháp những phép toán logic như
phép hội, phép phủ định, trong đó kết quả phụ thuộc vào tất cả các
biến tự do được định nghĩa cho những số hạng lôgic.
- Một cơ sở dữ liệu suy diễn gồm có những thực tế cơ bản.Những khung mẫu
cho tất cả các thực tế cơ bản như vậy được mô tả trong mô hình cơ sở dữ
liệu hiện thời. Đồng thời, mô hình cơ sở dữ liệu định nghĩa cái gọi là những
quy tắc suy diễn được dùng để tự động suy luận những thực tế mới (gọi là

những thực tế được suy luận). Suy luận những thực tế đã được trở nên sẵn
có đối với những người sử dụng thông qua một giao diện hợp nhất.
- Những người sử dụng giao tiếp với một cơ sở dữ liệu suy diễn thực hiện
những mục đích kiểm tra thông tin, tìm kiếm thông tin và thực hiện các
thông tin.
o Kiểm tra thông tin là một vị từ mà có thể xác định bởi 02 kết quả
Đúng hoặc Sai.
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 4 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
o Tìm kiếm thông tin là một hàm logic định nghĩa với ít nhất một biến
tự do.
- Một số quy tắc suy diễn:
o Quy tắc suy diễn đệ quy: Những thực tế được suy luận có thể được
định nghĩa một cách đệ quy, một thực tế được suy luận có thể được
sử dụng như một kết luận và như một vị từ trong quy tắc suy diễn.
o Quy tắc móc xích ngược: DBMS suy diễn suy luận một sự đáp lại
tới một mục đích đã cho như thế nào?
+ Bước 1: Thay thế mục đích đã cho với những mục đích đơn
giản tương xứng với những thực tế cơ bản hay những thủ tục.
+ Bước 2: tìm kiếm những giá trị cho những mục đích đơn giản
và cho giá trị cuối cùng.
o Những thuật ngữ tính toán: Để cung cấp những quy tắc suy diễn
với một sức mạnh tính toán đầy đủ, mô hình dữ liệu logic cũng hỗ
trợ một khái niệm gọi là những thuật ngữ tính toán. Những thuật ngữ
tính toán là những biểu thức số học có những biến tự do, những hằng
số và những tham số.
Ký pháp sau đây được dùng để định nghĩa những thuật ngữ tính
toán như vậy:
([Tham số_1] [Thao tác] [ Tham số_2])

Ở đây [ tham số_1] và [ tham số_2] là những biến tự do, những
hằng số hay những thuật ngữ tính toán khác. Thuật ngữ được sử
dụng như những biến tự do trong những quy tắc suy diễn.
II. NGÔN NGỮ PROLOG
1. Giới thiệu
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 5 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
- Prolog là một ngôn ngữ lập trình. Tên gọi Prolog được xuất phát từ cụm từ
tiếng Pháp Programmation en logique, nghĩa là "lập trình theo lô gích".
Xuất hiện từ năm 1972 (do Alain Colmerauer và Robert Kowalski thiết kế),
mục tiêu của Prolog là giúp người dùng mô tả lại bài toán trên ngôn ngữ
của logic, dựa trên đó, máy tính sẽ tiến hành suy diễn tự động dựa vào
những cơ chế suy diễn có sẵn (hợp nhất, quay lui và tìm kiếm theo chiều
sâu) để tìm câu trả lời cho người dùng.
- Prolog được sử dụng nhiều trong các ứng dụng của trí tuệ nhân tạo và ngôn
ngữ học trong khoa học máy tính (đặc biệt là trong ngành xử lý ngôn ngữ
tự nhiên vì đây là mục tiêu thiết kế ban đầu của nó). Cú pháp và ngữ nghĩa
của Prolog đơn giản và sáng sủa, nó được người Nhật coi là một trong
những nền tảng để xây dựng máy tính thế hệ thứ năm mà ở đó, thay vì phải
mô tả cách giải quyết một bài toán trên máy tính, con người chỉ cần mô tả
bài toán và máy tính sẽ hỗ trợ họ nốt phần còn lại.
- Ví dụ về một số mệnh đề Horn:
1. Nếu một người già mà (và) khôn ngoan thì người đó hạnh phúc.
2. Jim là người hạnh phúc.
3. Nếu X là cha mẹ của Y và Y là cha mẹ của Z thì X là ông của Z.
4. Tom là ông của Pat.
5. Tất cả mọi người đều phải chết (hoặc Nếu ai đó là người thì ai đó phải
chết.)
6. Socrat là người.

- Trong các mệnh đề Horn ở trên, các mệnh đề 1,3,5 được gọi là các luật
(rule), các mệnh đề còn lại được gọi là các sự kiện (fact). Một chương trình
logic có thể được xem như là một cơ sở dữ liệu gồm các mệnh đề Horn,
hoặc dạng luật, hoặc dạng sự kiện, chẳng hạn như tất cả các sự kiện và luật
từ 1 đến 6 ở trên. Người dung gọi chạy một chương trình logic bằng cách
đặt câu hỏi truy vấn trên CSDL này, chẳng hạn:
Socrat có chết không? (tương đương với khẳng định Socrat chết đúng hay
sai?)
- Một hệ thống logic sẽ thực hiện chương trình theo các “suy luận”tìm kiếm
dựa trên vốn “hiểu biết” đã có là chương trình-CSDL để minh chứng câu
hỏi là một khẳng định là đúng (yes) hoặc sai (No). Và như trên câu trả lời
sẽ là :
Yes (Có nghĩa là Socrat chết là đúng.)
2. Cú pháp Prolog
- Một chương trình Prolog là một CSDL gồm các mệnh đề (Clause). Mỗi
mệnh đề được xây dựng từ các vị từ (predicate). Một vị từ là một phát biểu
nào đó về các đối tượng có giá trị chân đúng (true) hoặc sai (false). Một vị
từ có thể có các đối là các nguyên logic (logic atom).
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 6 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Mỗi nguyên tử biểu diễn một quan hệ giữa các hạng (term). Như vậy, hạng
và quan hệ giữa các hạng tạo thành mệnh đề.
Hạng được xem alf những đối tượng “dữ liệu” trong một trình Prolog.
Hạng có thể là hạng sơ cấp gồm hằng, biến, cà các hạng thức phức hợp.
Các hạng phức hợp là một hàm tử có chứa các đối, có dạng:
Tên_hàm_tử(Đối 1,…, Đối n)
- Ví dụ:
f(5,a,b).
student(Robert, 1975,info,2,address(6,’mal juin’,’Caen’)).

[a,b,c]
- Mệnh đề có thể là một sự kiện, một luật (hay quy tắc), hay một câu hỏi.
- Prolog quy ước viết sau mỗi mệnh đề một dấu chấm để kết thúc như sau:
o Sự kiện: <…> (tương ứng với luật <…> )
o Luật: <…>:-<…>.
o Câu hỏi ?-<…>. (ở chế độ tương tác có dấu nhắc lệnh)
3. Lập trình đệ quy với Prolog
- Kỹ thuật này cũng phù hợp với suy nghĩ của con người khi tiếp cận
giải quyết vấn đề và khiến cho việc lập trình trên Prolog có một sự uyển
chuyển và nhẹ nhàng trong việc viết mã. Tuy vậy, nó tạo ra một sự khó
khăn với những người quen lập trình thủ tục.
- Chúng ta sẽ xem xét lại từng bước trong việc gọi đệ quy để tìm ra lời giải
qua ví dụ sau.
Có đoạn chương trình như sau:
giaithua(0,1):-!.
giaithua(X,Y):- X1 is X -1, giaithua(X1,Y1), Y is X*Y1.
- Ở đây có một sự thay đổi nhỏ: chúng ta đặt nhát cắt để chuyển sự kiện đầu
thành luật.
- Chúng ta muốn khẳng định: nếu số cần tìm giai thừa là 0 thì giai thừa của
nó là 1, và kết quả này là duy nhất, không cần phải tiếp tục tìm các trường
hợp khác. Ngoài ra, chúng ta cũng cần lưu ý thêm là vị từ “is” khác với
phép hợp nhất “=” như trong ví dụ sau:
Với biến Y có giá trị là 1 thì trong mệnh đề “X is Y + 1” thì X có giá trị
là 2 còn trong mệnh đề “X = Y + 1” thì X có giá trị là 1 + 1.
Với goal là giaithua(2,X), hệ thống sẽ so trùng với mệnh đề
giaithua(0,1) là mệnh đề đầu tiên tìm thấy có liên quan đến khái niệm giaithua.
- Hệ thống sẽ hợp nhất các thông số theo thứ tự, 2 hợp nhất với 0 và X hợp
nhất với 1.
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 7 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH

CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
- Công việc hợp nhất X với 1 thành công, X có giá trị là 1, nhưng 2 hợp nhất
với 0 thất bại.
- Hệ thống sẽ tiếp tục tìm kiếm lời giải khác bằng cách so trùng với mệnh đề
khác. Lần này hệ thống so trùng goal với mệnh đề giaithua(X,Y). Khi tạo
mối liên quan giữa các thông số, hệ thống hợp nhất 2 với X của mệnh đề và
Y với X của goal. Chúng ta sẽ ký hiệu XG là X thong số của goal. Do Y và
XG đều chưa có giá trị, Prolog sẽ xem hai biến này là một.
- Sau đó hệ thống bắt đầu thực hiện từng sub-clause:
X1 is X -1
X1 là biến mới, và chưa có giá trị. X đã có giá trị là 2, nên X - 1 có giá trị là
1. Hợp nhất X1 với 1 ta sẽ có giá trị của X1 là 1.
giaithua(X1,Y1)
- Ở đây mệnh đề giai thừa được gọi đệ quy. Lưu ý lúc này X1 đã có giá trị là
1, Y1 là biến mới chưa có giá trị, vì vậy nhiệm vụ của hệ thống là tìm giá
trị của Y1 sao cho sub-clause
giaithua(X1,Y1) cho giá trị là đúng. Và cũng như các ví dụ trên, cách
thức Prolog trả lời một sub-clause cũng tương tự như khi trả lời câu hỏi từ
goal, tức là lại so trùng câu hỏi với các mệnh đề đã biết
- So trùng với giaithua(0,1), Prolog tiến hành hợp nhất X1 với 0, Y1 với 1,
do X1 đã có giá trị là 1, việc hợp nhất với 0 thất bại, Prolog phải so trùng
với mệnh đề khác.
- So trùng với giaithua(X,Y), Prolog tiến hành hợp nhất X1 với X đồng nhất
Y1 với Y.
- Chúng ta ký hiệu X và Y ở lần gọi đệ quy này là X2 và Y2, và sử dụng
cách ký hiệu tương tự như vậy cho các biến còn lại ở lần gọi đệ quy này
cũng như các lần gọi đệ quy tiếp theo. Như vậy X2 sẽ có giá trị là 1 và Y1
sẽ có giá trị mà Y2 sẽ có.
- Tương tự ở lần gọi thứ nhất, các sub-clause của mệnh đề trên ở lần gọi thứ
hai này sẽ lần lượt được gọi:

X12 is X2 - 1, hợp nhất X12 với X2 -1, ta có X12 có giá trị là 0.
giaithua(X12,Y12), X12 đã có giá trị là 0, Prolog sẽ tìm giá trị của Y12
bằng việc tiếp tục so trùng giaithua(X12,Y12) với các mệnh đề có liên
quan:
So trùng giaithua(X12,Y12) với giaithua(0,1). Do X12 đã có giá trị là
0, Prolog tiến hành hợp nhất X12 với 0 và Y12 với 1. Thực hiện tiếp
subclause!, do câu hỏi giaithua(X12,Y12) chưa tìm được câu trả lời nào,
nên sub-clause này trả lời là đúng. Việc thực hiện mệnh đề giaithua(0,1)
thành công, và Y12 đã có giá trị là 1 nên câu hỏi
giaithua(X12,Y12) đã có đáp số. Vị từ ! sẽ ngăn chặn việc tìm các đáp
số khác, vì vậy trong trường hợp này, Prolog không tiếp tục so trùng
tiếp với mệnh đề giaithua(X,Y).
Y2 = X2 * Y12, lúc này Y2 chưa có giá trị, X2 và Y12 đã có giá trị là 1
và 1 nên
Prolog sẽ hợp nhất Y2 và 1. Kết quả sẽ là Y2 có giá trị là 1.
- Như vậy đến đây các sub-clause của mệnh đề giaithua(X2,Y2) đã thực thi
thành công, và Y2 đã có giá trị là 1, và vì Y1 được đồng nhất với Y2, nên
Y1 cũng sẽ có giá trị la 1. Y = X* Y1, lúc này Y chưa có giá trị, X và Y1
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 8 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
đã lần lượt có giá trị là 2 và 1, nên Prolog hợp nhất Y và 2*1, kết quả Y sẽ
có giá trị là 2.
- Như vậy đến đây các sub-clause của mệnh đề giaithua(X,Y) đã thực thi
thành công, và Yđã có giá trị là 2, và vì XG được đồng nhất với Y, nên XG
cũng sẽ có giá trị là 2, và lời giải củabài toán đã được tìm thấy.
PHẦN II : ÁP DỤNG
I. GIẢI BÀI TOÁN
1. Mô tả bài toán
Viết chương trình để tính:

MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 9 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
?ancestor(mildred,mary)
?ancestor(chester, ?)
?ancestor(?, ken)
?ancestor(?,?)
Biết rằng:
ancestor(X,Y) :- parent(X,Y)
ancestor(X,Y) :- parent(X,Z) & ancestor(Z,Y)
Và:
2. Giải bài toán
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 10 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
- Sử dụng SWI Prolog, tạo file ancestor.pl
parent(chester,irvin).
parent(chester,clarence).
parent(chester,mildred).
parent(irvin,ken).
parent(irvin,ron).
parent(clarence,nora).
parent(clarence,elizabeth).
parent(clarence,sharon).
parent(mildred,shinky).
/*các qui tắc */
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
- Trong shell cua prolog lần lượt gọi lệnh để tính, ta được kết quả như bên
dưới.

MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 11 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
II. NHẬN XÉT
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 12 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Bài thu hoạch chỉ là một phần nhỏ trong kiến thức bộ môn này, gói gọn trong mục
tiêu tìm hiểu đủ kiến thức để giải quyết bài toán tìm quan hệ ‘ancestor’.
Qua đó em cũng hiểu thêm nhiều về cơ sở dữ liệu suy diễn và đặc biệt là ngôn
ngữ Prolog.
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 13 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Tài liệu tham khảo
1. Bài giảng môn học “Cơ sở dữ liệu nâng cao” .
Giảng viên : PGS.TS Đỗ Phúc
2. Seminar CSDL: Mô hình dữ liệu suy diễn – Deductive Data
Phan Thanh Quảng
3. Nguyên lý các hệ dữ liệu phân tán
M. Tamer Ozsu, Patrick Valduriez
4.
MÔN HỌC : CƠ SỞ DỮ LIỆU NÂNG CAO - PGS.TS. Đỗ Phúc - 14 -