LỜI CAM ĐOAN
Tôi xin cam đoan đề tài “Tìm hiểu việc mở rộng chương trình Datalog
cho Web ngữ nghĩa” là công trình nghiên cứu do tôi thực hiện, không sao chép bất
kỳ kết quả nghiên cứu nào của các tác giả khác. Các số liệu và kết quả nghiên cứu
nêu trong luận văn là trung thực và chưa từng được công bố trong bất kỳ một công
trình nào khác. Nội dung của luận văn có tham khảo và sử dụng một số thông tin,
tài liệu từ các nguồn sách, tạp chí được liệt kê trong danh mục các tài liệu tham
khảo.
Tôi xin chịu hoàn toàn trách nhiệm về nội dung của luận văn này.
Thừa Thiên Huế, ngày 17 tháng 08 năm 2018
Người cam đoan

Bùi Thị Kim Tuyến

1


LỜI CẢM ƠN
Qua quá trình học tập và nghiên cứu, tôi xin gởi lời cảm ơn chân thành sâu
sắc đến Quý thầy cô giáo Khoa Công nghệ thông tin - Trường Đại học Khoa học
Huế và trường Đại học An Giang đã tận tình hướng dẫn, truyền đạt kiến thức, tạo
điều kiện thuận lợi cho tôi trong quá trình học tập và thực hiện luận văn tốt nghiệp.
Để hoàn thành được luận văn này, tôi xin chân thành gửi lời biết ơn sâu sắc
đến PGS.TS. Trương Công Tuấn, thầy đã khuyến khích, hướng dẫn tận tình, có
những góp ý sâu sắc và đã truyền đạt rất nhiều kiến thức quý báu cho tôi trong suốt
quá trình nghiên cứu. Thầy đã cho tôi nhiều lời động viên cũng như những nhận xét
chân thành để tôi có thể hoàn thành được đề tài này.
Cuối cùng tôi xin được cảm ơn Ban Giám Hiệu, quý thầy cô trong tổ nơi tôi
công tác đã tạo mọi điều kiện để tôi đi học và thực hiện đề tài nghiên cứu này. Tôi
cũng gửi lời cảm ơn chân thành đến anh chị em học viên KHMT_K3 luôn giúp đỡ
động viên. Đó cũng là động lực để tôi hoàn thành việc học và nghiên cứu của mình.

Bản thân tôi đã cố gắng hết sức trong quá trình thực hiện đề tài này nhưng
chắc chắn sẽ không tránh khỏi những thiếu sót. Kính mong quý thầy cô và các bạn
tận tình hướng dẫn, góp ý và chỉ bảo.
Xin chân thành cám ơn!
Thừa Thiên Huế, ngày 17 tháng 08 năm 2018
Học viên

Bùi Thị Kim Tuyến

2


MỤC LỤC
Trang

3


DANH MỤC CÁC HÌNH

4


DANH MỤC CÁC THUẬT NGỮ
Chương trình Datalog
Chương trình Datalog±
Chương trình logic
Chương trình logic xác định
Cơ sở dữ liệu
Cơ sở Herbrand

Datalog± được bảo vệ
Hạng thức
Literal âm
Literal dương
Logic mô tả
Mệnh đề đơn vị
Mô hình nhỏ nhất
Ngôi
Nguyên tố
Quy tắc
Thể hiện
Toán tử hệ quả trực tiếp
Trả lời truy vấn
Vị từ
Vũ trụ Herbrand
Web ngữ nghĩa

Datalog program
Datalog± program
Logic program
Definite logic program
Database
Herbrand base
Guarded Datalog±
Term
Negative literal
Positive literal
Description logics
Unit clause
Least model

Arity
Atom
Rule
Interpretation
The immediate consequence operator
Query Answering
Predicate
Herbrand universe
Semantic Web

5


DANH MỤC CÁC KÝ HIỆU
BP

Cơ sở Herbrand của chương trình P

UP

Vũ trụ Herbrand của chương trình P

2 BP

Tập tất cả các tập con của cơ sở Herbrand BP

MP

Mô hình nhỏ nhất của P


TP

Toán tử hệ quả trực tiếp trên

2 BP

2S

Tập các tập con của tập S

supX

Cận trên của tập X

infX

Cận dưới của tập X

Lfp(T)

Điểm bất động nhỏ nhất của ánh xạ T

Head(r)

Phần đầu của quy tắc Datalog r

Body(r)

Phần thân của quy tắc Datalog r


6


DANH MỤC CÁC CHỮ VIẾT TẮT
ABOX

Assertional Box

BGDP

Bounded Guard-Depth Property

CSDL

Database

EDB

Extensional Database

EGD

Equality-Generating Dependencies

IDB

Inzpional Database

KB


Knowledge Base

SQL

Structured Query Language

TBOX

Terminological Box

TGD

Tuple Generating Dependencies

7


MỞ ĐẦU
Hiện nay, Web ngữ nghĩa là một mạng lưới các thông tin toàn cầu được liên
kết theo một cách thức để máy tính có thể dễ dàng xử lý. Web ngữ nghĩa có khả
năng làm việc với dữ liệu, điều này đã mở ra một lớp các ứng dụng mới trên nền
Web ngữ nghĩa. Web ngữ nghĩa là một cách nhìn về cách thức tổ chức dữ liệu: đó là
ý tưởng về việc dữ liệu trên web được định nghĩa và liên kết theo cách mà nó có thể
được sử dụng bởi máy tính, với mục đích không chỉ cho việc hiển thị mà còn tự
động hóa, tích hợp và sử dụng lại dữ liệu qua các ứng dụng.
Bên cạnh các nghiên cứu về Web ngữ nghĩa, các nhà khoa học đã tìm ra
nhiều sự liên quan với ngôn ngữ Datalog. Datalog là một ngôn ngữ mạnh dựa trên
quy tắc, lúc đầu được thiết kế để biểu diễn các truy vấn phức tạp trên dữ liệu quan
hệ và hiện nay là cơ sở của các ngôn ngữ đặc tả tối ưu hóa. Datalog đã được mở
rộng theo nhiều hướng khác nhau nhằm mục đích đáp ứng các yêu cầu của thực

tiễn. Hiện nay một họ ngôn ngữ Datalog mở rộng giàu khả năng diễn đạt, được gọi
là Datalog±, đây được xem là một mô hình mới để trả lời truy vấn trên các ontology
cho Web ngữ nghĩa, đã được nhiều người nghiên cứu trong thời gian gần đây và rất
nhiều công trình có giá trị được công bố. Họ Datalog± cho phép các biến với lượng
từ tồn tại trong xuất hiện trong phần đầu của các quy tắc và có những ràng buộc
thích hợp nhằm đảm bảo truy vấn Ontology đạt hiệu quả cao.
Luận văn được thực hiện nhằm mục đích tìm hiểu việc mở rộng chương trình
Datalog cho Web ngữ nghĩa. Cấu trúc của luận văn bao gồm phần mở đầu, nội dung
ba chương, phần kết luận và tài liệu tham khảo.
Chương 1: Tổng quan về chương trình Datalog và Web ngữ nghĩa. Chương
này giới thiệu một số khái niệm cơ sở của chương trình Datalog, hai tiếp cận thường
dùng để xác định ngữ nghĩa của chương trình Datalog là tiếp cận theo lý thuyết mô
hình và tiếp cận theo lý thuyết điểm bất động. Ngoài ra, chương 1 cũng trình bày
tổng quan về Web ngữ nghĩa và vai trò của Ontology, logic mô tả trong Web ngữ
nghĩa.

8


Chương 2: Trình bày về cú pháp và ngữ nghĩa của chương trình Datalog± - là
một lớp chương trình Datalog mở rộng, cho phép các biến với lượng từ tồn tại xuất
hiện trong phần đầu của các quy tắc.
Chương 3: Trình bày việc chuyển đổi logic mô tả DL-LITE về chương trình
Datalog±.
Phần kết luận nêu những kết quả đã đạt được và hướng phát triển của luận
văn.
Do thời gian có hạn và bản thân chỉ mới bước đầu nghiên cứu về lĩnh vực
này nên không thể tránh khỏi những thiếu sót, kính mong sự giúp đỡ và góp ý thêm
của Quý Thầy, Cô và các bạn.


9


CHƯƠNG 1.
TỔNG QUAN VỀ CHƯƠNG TRÌNH DATALOG
VÀ WEB NGỮ NGHĨA
Trong chương này sẽ bắt đầu bằng những khái niệm cơ sở của chương trình
Datalog, cú pháp và ngữ nghĩa của chương trình Datalog và giới thiệu tổng quan về
Web ngữ nghĩa. Đây là những kiến thức làm cơ sở cho việc nghiên cứu các chương
tiếp theo của luận văn.
1.1. GIỚI THIỆU VỀ CHƯƠNG TRÌNH DATALOG VÀ WEB NGỮ NGHĨA
1.1.1. Một số khái niệm cơ sở
Định nghĩa 1.1 (Bộ ký tự) Bộ ký tự bao gồm các lớp ký hiệu sau:
•

Hằng: là các giá trị xác định thường được ký hiệu bởi các chữ cái thường, ví dụ: a,

b, c,…
• Biến: chỉ những đại lượng có giá trị thay đổi trong một miền nào đó, thường được
•
•
•

ký hiệu bởi các chữ cái in hoa, ví dụ: X, Y, Z,…
Ký hiệu hàm, thường ký hiệu bởi các chữ cái thường, ví dụ: f, g, h,...
Ký hiệu vị từ, thường ký hiệu bởi các chữ cái thường, ví dụ: p, q, r,…
Hằng vị từ: true, false
• Ký hiệu kết nối: ¬ (phủ định), ∧ (tuyển), ∨ (hội), ← (kéo theo), ↔ (tương

đương).

• 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 (,).
Mỗi ký hiệu hàm, ký hiệu vị từ có kèm theo một số tự nhiên xác định để chỉ các
đối số tham gia cùng với ký hiệu hàm hoặc ký hiệu vị từ đó, gọi là ngôi của vị từ.
Trên cơ sở bộ ký tự đã cho, người ta đưa ra khái niệm về hạng thức. Hạng thức
là yếu tố quan trọng của công thức logic, được xây dựng từ các hằng, biến, hàm và
được định nghĩa hình thức như sau:
Định nghĩa 1.2 (Hạng thức) Hạng thức được định nghĩa đệ quy như sau:
(i) Mỗi hằng là một hạng thức,
(ii) Mỗi biến là một hạng thức,

10


(iii) Nếu f là ký hiệu hàm n-ngôi và t1, …,tn là các hạng thức thì f(t1,…,tn) 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.
Hạng thức nền là hạng thức không chứa biến.
Định nghĩa 1.3 (Nguyên tố) Nếu p là ký hiệu vị từ n-ngôi và t1,…,tn là các hạng
thức thì p(t1,…,tn) được gọi là một nguyên tố. Nguyên tố nền là nguyên tố không
chứa biến.
Ví dụ 1.1 Xét nguyên tố me(Mai,Linh) trong đó vị từ me là vị từ 2-ngôi để chỉ mối
quan hệ mẹ con, hạng thức Mai, Linh là các hằng. Nguyên tố này có ý nghĩa là Mai
là mẹ của Linh. Nguyên tố này cũng là nguyên tố nền vì nó không chứa biến.
Định nghĩa 1.4 (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ố.
Theo định nghĩa 1.3 nếu p là một nguyên tố, lúc đó p là literal dương và ¬p
là literal âm.
Ví dụ 1.2 Xét nguyên tố như ví dụ 1.1, trong đó me(Mai,Linh) là literal dương và

¬me(Mai,Linh) là literal âm.
Định nghĩa 1.5 (Công thức) Công thức được định nghĩa đệ quy như sau:
(i) Nguyên tố là một công thức,
(ii) 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),
(E ↔ F) là các công thức,
(iv) Nếu E là công thức, X là biến 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.
Công thức không chứa biến được gọi là công thức nền.

11


Ví dụ 1.3 Sau đây là các công thức:
∀X(∀Y((yeuthuong(X,Y) ← me(X) ∧ con_cua(Y,X)))
me(Mai) ∧ con_cua(Hoa,Mai)
Nếu trong các công thức ∀X(E) hoặc ∃X(E) chứa biến X và các biến khác
không nằm trong phạm vi của ký hiệu lượng từ ∀, ∃ thì biến X gọi là biến ràng
buộc, các biến khác gọi là biến tự do.
Công thức đóng là công thức không chứa biến tự do.
Ví dụ 1.4 ∀Y(∃X)(p(X,Y) ∧q(X)) là công thức đóng.
Tuy nhiên, ∃X(p(X,Y) ∧q(X)) không phải là công thức đóng vì Y là biến tự do.
1.1.2. Giới thiệu về web ngữ nghĩa.
Tim- Berners Lee là người phát triển Web ngữ nghĩa, ông là cha đẻ của
WWW, URIs, HTTP và HTML. Theo Ông, “Web ngữ nghĩa là sự mở rộng của Web
hiện tại, cho phép người dùng có thể truy tìm, phối hợp, sử dụng lại và trích lọc
thông tin một cách dễ dàng và chính xác”. Công nghệ web có ngữ nghĩa là công
nghệ cho phép máy tính có thể hiểu được nhiều hơn thông tin trên Web, sao cho
chúng có thể hỗ trợ tốt hơn việc khám phá thông tin, tích hợp dữ liệu và tự động hóa
các công việc.

Những tính năng nổi bật của web ngữ nghĩa so với web hiện tại:
- Thông tin trên Web được máy tính hiểu: Các thông tin trên Web được tổ
chức bao gồm các quan niệm về khái niệm và bổ sung quan hệ dưới dạng mà máy
tính có thể hiểu được. Vì vậy, việc xử lý, tìm kiếm, đánh giá, tích hợp thông tin có
thể được tiến hành một cách tự động.
- Tối ưu hóa việc tìm kiếm thông tin: Với công nghệ web ngữ nghĩa, máy
tính có thể xác định một thực thể có thuộc tính và quan hệ dựa trên ngữ cảnh chứa

nó. Do đó, thu hẹp không gian tìm kiếm, cho kết quả nhanh chóng và chính xác.

12


- Công nghệ Web có khả năng suy luận thông minh: Dựa vào các luật suy
diễn trên cơ sở tri thức về các lớp, các thực thể, các thuộc tính và mối quan hệ mà
máy tính có khả năng đưa ra những kết luận mới.
- Cách liên kết dữ liệu là cách liên kết động: Thay thế cách liên kết sử dụng
hyperlink tĩnh trong Web 2.0, Web ngữ nghĩa liên kết bằng siêu dữ liệu từ nhiều
nguồn khác nhau một cách hiệu quả hơn dựa trên định danh của tài nguyênUniform Resource Identifier (URI) và mối quan hệ giữa chúng.
- Với công nghệ web ngữ nghĩa: Các truy vấn từ người dùng được máy tính
hiểu và xử lí nhanh chóng, chính xác đưa ra kết quả tối ưu nhất.
1.2. CHƯƠNG TRÌNH DATALOG
Chương trình Datalog đã được sử dụng như một ngôn ngữ truy vấn và lập
trình cơ sở dữ liệu trong hơn ba thập kỷ qua. Mặc dù Datalog hiếm khi được sử
dụng trực tiếp như một ngôn ngữ truy vấn trong bối cảnh ứng dụng doanh nghiệp,
Datalog đã ảnh hưởng đến sự phát triển của các ngôn ngữ truy vấn phổ biến như
SQL, cho phép người dùng biểu diễn các truy vấn đệ quy.
1.2.1. Cú pháp chương trình Datalog
Định nghĩa 1.6 (Quy tắc Datalog) Một quy tắc Datalog r là một công thức có dạng:
∀X1∀X2…∀Xk ( p0 ← q1 ∧. . .∧qn)


(n≥ 0)

(1)

trong đó p0, qi (i = 0,...,n) là các nguyên tố có các đối là hằng hoặc biến, X1, X2,…,
Xk là các biến xuất hiện trong các nguyên tố, mỗi biến trong p0 phải có mặt trong
một qi nào đó. Ta thường viết quy tắc (1) dưới dạng rút gọn:
p0 ← q1∧. . .∧qn
Nguyên tố p0 được gọi là đầu của quy tắc, ký hiệu head(r), tập các nguyên tố
{q1,..., qn} được gọi là thân của quy tắc, ký hiệu body(r).
Ngữ nghĩa của quy tắc (1) là “đối với mỗi phép gán của mỗi biến bởi các hằng
làm cho thân quy tắc đúng thì đầu quy tắc đúng”.

13


Khi n = 0, (1) trở thành p0 ← được gọi là mệnh đề đơn vị. Ngữ nghĩa của
p0 ← là “đối với mỗi phép gán của mỗi biến trong p 0 bởi các hằng thì p0 luôn đúng”.
Nếu các đối của mệnh đề đơn vị là các hằng thì nó được gọi là một sự kiện.
Định nghĩa 1.7 (Chương trình Datalog) Chương trình Datalog là một tập hữu hạn
các quy tắc Datalog.
Tập các hằng xuất hiện trong P, ký hiệu dom(P).
Trong chương trình Datalog, các vị từ chỉ xuất hiện trong thân các quy tắc
được gọi là vị từ EDB, các vị từ xuất hiện ở đầu quy tắc được gọi là vị từ IDB, các
vị từ IDB cũng có thể xuất hiện trong thân quy tắc.
Mỗi vị từ q k-ngôi được đặt tương ứng một quan hệ Q có k thuộc tính. Giá trị
của quan hệ Q là một tập các bộ, một bộ của quan hệ Q có k thuộc tính được biểu
thị bởi (a1,...,ak), trong đó các ai là hằng và q(a1,...,ak) là đúng nếu (a1,...,ak) thuộc Q
Cơ sở dữ liệu EDB của P, ký hiệu EDB(P) bao gồm các vị từ EDB của P mà

giá trị của chúng được cho bởi một CSDL vào. CSDL IDB của P, ký hiệu IDB(P),
bao gồm các vị từ IDB của P mà giá trị của chúng được tính bởi chương trình P.
Lược đồ của P, ký hiệu SCH(P) là tập các vị từ EDB(P) ∪ IDB(P).
Ví dụ 1.5 Cho chương trình Datalog P gồm các quy tắc sau đây:
r1:

p(a)

←

r2:

p(s(X))

←

p(X)

r3:

q(X,a,X))

←

p(X)

r4: q(X,s(Y),s(Z))

←


q(X,Y,Z)

trong đó p là vị từ 1-ngôi, q là vị từ 3-ngôi, s là ký hiệu hàm 1-ngôi, a là ký hiệu
hằng, X, Y, Z là các biến.
Ví dụ 1.6 Xem chương trình Datalog P gồm các quy tắc sau:
r1: cha_me(X,Y)

←

cha(X,Y)

r2: cha_me(X,Y)

←

me(X,Y)

14


r3: ong(X,Z)

←

cha(X,Y) ∧ cha_me(Y,Z)

r4: totien(X,Y)

←


cha_me(X,Y)

r5: totien(X,Z)

←

totien(X,Y) ∧ cha_me(Y,Z)

r6: anhemho(X,Y)

←

totien(Z,X) ∧ totien(Z,Y)

Trong chương trình này, quy tắc r1, r2 định nghĩa vị từ cha_me để chỉ mối quan
hệ cha/mẹ, quy tắc r3 định nghĩa vị từ ong để chỉ mối quan hệ ông, quy tắc r4, r5
định nghĩa vị từ totien để chỉ mối quan hệ tổ tiên, quy tắc r6 định nghĩa vị từ
anhemho để chỉ mối quan hệ anh em họ. Các vị từ cha, me là vị từ EDB và cha_me,
ong, totien, anhemho là các vị từ IDB.
Như vậy :
EDB(P) = {cha, me},
IDB(P) = {cha_me, ong, totien, anhemho}.
Quy tắc r1 có nghĩa: với mọi X và Y, nếu X là cha của Y thì X là cha/mẹ của Y.
Quy tắc r2 có nghĩa: với mọi X và Y, nếu X là mẹ của Y thì X là cha/mẹ của Y.
Quy tắc r3 có nghĩa: với mọi X, Y, Z, nếu X là cha của Y và Y là cha/mẹ của Z
thì X là ông của Z.
Quy tắc r4 có nghĩa: với mọi X và Y, X là tổ tiên của Y nếu X là cha/mẹ của Y.
Quy tắc r5 có nghĩa: với mọi X, Y, Z, X là tổ tiên của Z nếu X là tổ tiên của Y và
Y là cha/mẹ của Z.
Quy tắc r6 có nghĩa: với mọi X, Y, Z, X là anh em họ của Y nếu X và Y có cùng

tổ tiên là Z.
Định nghĩa 1.8 Cho P là một chương trình Datalog. Lúc đó:
1. Vũ trụ Herbrand của P, ký hiệu UP là tập tất cả các hằng của P.
2. Cơ sở Herbrand của P, ký hiệu BP là tập tất cả các nguyên tố nền của P. Mỗi
phần tử thuộc BP được gọi là một sự kiện.

15


3. Thể hiện Herbrand của Plà một tập con I bất kỳ của cơ sở Herbrand BP.
- Nếu A ∈I ta nói rằng A đúng trong I và ký hiệu I A.
- Nếu A ∈BP nhưng A I, ta nói rằng A sai trong I và ký hiệu I ⊭ A.
Đối với chương trình Datalog thì UP, BP đều là những tập hữu hạn.
Ví dụ 1.7 Xét chương trình Datalog P gồm các quy tắc như sau:
q(a, b)

←

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à: UP = {a, b, c}
Cơ sở Herbrand của P là:
BP = {p(a, a), p(b, b), p(c, c), p(a, b), p(b, c), p(a, c), p(b, a), p(c, b), p(c, a), q(a, a),
q(b, b), q(c, c), q(a, b), q(b, c), q(a, c), q(b, a), q(c, b), q(c, a)}.
Ví dụ 1.8 Xét chương trình Datalog P gồm các quy tắc như sau:
r1: duongdi(X, Y) ← cung(X, Y)
r2: duongdi(X, Z) ← cung(X, Y) ∧ duongdi(Y, Z)
Giả sử quan hệ của vị từ EDB cung chỉ gồm 2 bộ là (1,2) và (2,3).
Lúc đó:
Vũ trụ Herbrand của P là: UP = {1, 2, 3}
Cơ sở Herbrand của P là:
BP = {cung(1,1),cung(2,2), cung(3, 3), cung(1, 2), cung(2, 3), cung(1, 3), cung(2, 1),
cung(3, 2), cung(3, 1), duongdi(1, 1), duongdi(2, 2), duongdi(3, 3), duongdi(1, 2),
duongdi(2, 3), duongdi(1, 3), duongdi(2, 1), duongdi(3, 2), duongdi(3, 1)}.

16


1.2.2. Ngữ nghĩa của chương trình Datalog
Hai cách tiếp cận thường được sử dụng để xác định ngữ nghĩa chương trình
Datalog là tiếp cận lý thuyết mô hình và tiếp cận lý thuyết điểm bất động.
1.2.2.1. Tiếp cận lý thuyết mô hình
Theo quan điểm lý thuyết mô hình, các quy tắc trong chương trình được xem
là công cụ để xác định mô hình. Một thể hiện của một tập các vị từ sẽ gán giá trị
chân lý cho mỗi tình huống có thể có của các vị từ. Để là mô hình của một tập các
quy tắc, một thể hiện phải làm cho các quy tắc đúng với mọi phép gán trị cho các
biến trong mỗi quy tắc được lấy từ miền giá trị đã cho. Với tiếp cận này, ngữ nghĩa
của chương trình Datalog P là mô hình nhỏ nhất của P. Ta có định nghĩa sau:
Định nghĩa 1.9 (Mô hình) Cho P là chương trình Datalog. Lúc đó:
(i)


Một thể hiện Herbrand I của P được gọi là mô hình Herbrand (hoặc đơn giản chỉ
gọi là mô hình) của P, ký hiệu I ⊨P, nếu với mọi quy tắc:
p ← q1 ∧ q2 ... ∧ qn
trong P đều đúng trong thể hiện I.

(ii)

Mô hình Herbrand I của P được gọi là mô hình Herbrand nhỏ nhất nếu với mọi mô
hình J của P ta luôn có I ⊆ J.
Ví dụ 1.9 Xét chương trình Datalog gồm các quy tắc như sau:
r1: p(X)

← q(X, Y),

r2: q(X, Y)

← r(X) ∧ s(X,Y).

trong đó p, q là các vị từ IDB, r và s là các vị từ EDB. Giả sử CSDL EDB là {r(1),
s(1,2)}.
Xét thể hiện M1 = {r(1), s(1,2), q(1,2), p(1)}. Khi thay X = 1, Y = 2 vào quy tắc r1
và r2 đều làm cho r1 và r2 đều đúng nên M1 là một mô hình.

17


Cũng vậy, với thể hiện M2 = {r(1), s(1,2), q(1,2), p(1), p(2)} thì M2 cũng là mô
hình. Tuy nhiên, với thể hiện M3 = {r(1), s(1,2), q(1,2)} thì M3 không phải là một
môhình. Vì khi thay X=1, Y=2 vào r1 ta được một giả thiết đúng và một kết luận sai.

Ví dụ 1.10 Cho chương trình Datalog P như sau:
r1: p(X) ← q(X)
r2: q(1) ←
Các thể hiện I1 = {q(1), p(1)}, I2 ={q(1), p(1), p(2)} là các mô hình của P. Dễ
thấy I1 là mô hình nhỏ nhất của P.
Ta có định lý sau đây:
Định lý 1.1 Cho P là chương trình Datalog và (Mi)I ∈I là họ khác rỗng các mô hình

I

Herbrand của P. Lúc đó i∈ I

Mi
là mô hình Herbrand của P.

Định nghĩa 1.10 (Ngữ nghĩa của chương trình Datalog) Ngữ nghĩa của chương
trình Datalog P được xác định bởi mô hình Herbrand nhỏ nhất của P, ký hiệu P(D).
Ví dụ 1.11 Xét chương trình Datalog Pgraph gồm các quy tắc:
r1: diden(X)

← dinh(X),

r2: diden(Y)

←canh(X,Y) ∧ tiepcan(X).

Ta có EDB(Pgraph) = {canh, dinh} và IDB(Pgraph) = {diden}.
Giả sử CSDL EDB D = {canh(v1,v3), canh(v2,v3), canh(v3,v4), canh(v4,v5),
canh(v5,v3), canh(v1)} đối với lược đồ EDB(Pgraph).
Các quy tắc trên định nghĩa vị từ diden và nguyên tố diden(X) có ý nghĩa là từ

đỉnh X có thể đi đến một đỉnh khác trong một đồ thị có hướng cho trước. Chương
trình Datalog Pgraph cho phép tìm được các đỉnh trong một đồ thị có hướng (tập

18


diden của các đỉnh) mà có thể đi đến chúng từ các đỉnh và các cạnh có hướng
(canh) đã cho trước.
Dễ kiểm tra Pgraph có mô hình nhỏ nhất là

P(D) = D ∪
1.2.2.2. Tiếp cận điểm bất động
Ngữ nghĩa điểm bất động của chương trình Datalog dựa vào một toán tử gọi là
toán tử hệ quả trực tiếp. Toán tử này sẽ tạo ra các sự kiện mới từ các sự kiện đã biết.
Có thể chứng tỏ được rằng mô hình Herbrand nhỏ nhất của chương trình Datalog là
điểm bất động nhỏ nhất của toán tử này. Tiếp cận này có thể xem như một sự thực
thi của ngữ nghĩa lý thuyết mô hình ở trên. Trước hết ta cần đến một số khái niệm
liên quan sau đây:
Định nghĩa 1.11 Một quan hệ R trên tập S là một quan hệ thứ tự nếu thỏa mãn 3
tính chất sau:
(i) Phản xạ: Với mọi x∈S, xRx.
(ii) Đối xứng: Với mọi x, y∈S, xRy và yRx suy ra x = y.
(iii) Bắc cầu: Với mọi x, y, z∈S, xRy và yRz suy ra xRz.
Nếu trên tập hợp S đã xác định một quan hệ thứ tự thì ta nói tập S được sắp thứ
tự, ta thường ký hiệu một quan hệ thứ tự là ≤.
Ví dụ 1.12 Cho S là một tập hợp, ký hiệu 2S là tập các tập con của S. Lúc đó quan
hệ ⊆ trên 2S là một quan hệ thứ tự.
Định nghĩa 1.12 Cho S là một tập hợp và ≤ là quan hệ thứ tự trên S. Phần tử a∈S là
một chặn trên của tập con X của S nếu x ≤ a, với mọi x∈X. Tương tự phần tử b∈S là
một chặn dưới của tập con X của S nếu b ≤ x, với mọi x∈X.


19


Định nghĩa 1.13 Cho S là một tập hợp và ≤ là quan hệ thứ tự trên S. Lúc đó phần tử
a ∈ S là một cận trên của tập con X của S (ký hiệu là supX) nếu a là một chặn trên
của X và với mọi chặn trên a’ của X thì a ≤ a’. Tương tự b ∈ S là một cận dưới của
tập con X của S (ký hiệu là infX) nếu b là một chặn dưới của X và với mọi chặn
dưới b’ của X thì b’≤b.
Chú ý: Cận trên của X nếu tồn tại thì duy nhất, tương tự, cận dưới của X nếu tồn tại
thì duy nhất.
Định nghĩa 1.14 Một tập được sắp thứ tự L là một dàn đầy đủ nếu supX và infX tồn
tại với mọi tập con X của L.
Ví dụ 1.13 Tập 2S cùng với quan hệ ⊆ là một dàn đầy đủ. Thật vậy, gọi X là tập con
tùy ý của 2S, lúc đó:

Y

Y

supX = Y ∈X , infX = Y ∈X .
Định nghĩa 1.15 Cho L là một dàn đầy đủ và T: L→L là một ánh xạ. Ta nói T đơn
điệu nếu ∀a, b∈L, a ≤b suy ra T(a) ≤ T(b).
Định nghĩa 1.16 Cho L là một dàn đầy đủ và T: L→L là một ánh xạ.
(i) Phần tử a ∈ L được gọi là điểm bất động của ánh xạ T nếu T(a) = a.
(ii) Phần tử a ∈ L được gọi là điểm bất động nhỏ nhất của T nếu a là điểm bất
động của T và với mọi điểm bất động b của T thì a ≤b. Ký hiệu a = lfp(T).
(iii) Điểm bất động a của T được gọi là điểm bất động cực tiểu của T nếu không
tồn tại điểm bất động b nào khác của T mà b ≤a.
Định lý 1.2 Cho L là một dàn đầy đủ và T: L→L là một ánh xạ đơn điệu. Lúc đó T

có điểm bất động nhỏ nhất lfp(T). Hơn nữa:
lfp(T) = inf{x ∈L | T(x) ≤x}

20


Trong phần sau đây, ta sẽ xây dựng mô hình Herbrand nhỏ nhất MP bằng cách
dùng khái niệm điểm bất động. Cho P là chương trình Datalog, BP là cơ sở
Herbrand của P. Lúc đó L = ( 2

BP

, ⊆) là một dàn đầy đủ.

Định nghĩa 1.17 (Toán tử hệ quả trực tiếp) Cho P là chương trình Datalog. Ánh

xạ Tp:

2 BP → 2 BP

Với mỗi I∈ 2

BP

được định nghĩa như sau:

, Tp(I) = {A ∈BP | ∃A←A1 ∧A2 ∧ . . . ∧An là hiện hành nền của P và

{A1,…,An} ⊆ I}
TP được gọi là toán tử hệ quả trực tiếp của chương trình Datalog P.

Định lý sau đây cung cấp một đặc trưng điểm bất động của mô hình Herbrand
nhỏ nhất của chương trình logic xác định.
Định lý 1.3 [2] Cho P là chương trình Datalog. Lúc đó toán tử Tp đơn điệu và điểm
bất động nhỏ nhất của Tp là mô hình Herbrand nhỏ nhất MP của P.
Mệnh đề 1.1 Cho P là chương trình Datalog. Mô hình Herbrand nhỏ nhất của P là
giới hạn của dãy TP↑n, n↑N, trong đó TP↑0 = EDB(P), TP↑(i+1) = TP(TP↑i).
Từ mệnh đề này ta có thuật toán:
Thuật toán 1.1: Tính mô hình Herbrand nhỏ nhất của chương trình Datalog P.
Vào: Chương trình Datalog P và DB là cơ sở dữ liệu EDB đã cho của P.
Ra: Mô hình Herbrand nhỏ nhất của P.
Phương pháp: Thuật toán được viết theo ngôn ngữ tựa Pascal như sau:
I := ∅;
J :=TP(DB);
While J <> I do

21


begin
I := J;
J := TP(I);
end;

output I;
Ví dụ 1.14 Xét chương trình Datalog P gồm các quy tắc như sau:
r1 : duongdi(X, Y)

← cung(X, Y)

r2 : duongdi(X, Z)


← cung(X, Y) ∧ duongdi(Y, Z)

Giả sử CSDL EDB(P) được cho bởi:
EDB(P) = {cung(1, 2), cung(2, 3), cung(3, 4), cung(4, 5)}
Các bước lặp để tính mô hình nhỏ nhất của P:
I0 = EDB(P) = {cung(1, 2), cung(2, 3), cung(3, 4), cung(4, 5)},
I1 = TP(I1) = I1 ∪{duongdi(1, 2), duongdi(2, 3), duongdi(3, 4), duongdi(4, 5)},
I2 = TP(I2) = I2 ∪{duongdi(1, 3), duongdi(2, 4), duongdi(3, 5)},
I3 = TP(I3) = I3 ∪{duongdi(1, 4), duongdi(2, 5)},
I4 = TP(I4) = I4 ∪{duongdi(1, 5)},
I5 = TP(I5) = I5 .
Như vậy điểm bất động nhỏ nhất của TP chính là TP(I5), đó cũng chính là mô
hình nhỏ nhất của P.
1.3. ONTOLOGY VÀ LOGIC MÔ TẢ TRONG WEB NGỮ NGHĨA
1.3.1. Ontology trong Web ngữ nghĩa.
Trong những năm gần đây, Ontology đã trở thành một thuật ngữ được biết
đến nhiều trong lĩnh vực khoa học máy tính và được xem như linh hồn của web ngữ

22


nghĩa. Nó giúp con người và máy tính có thể hợp tác, cùng nhau làm việc, giúp máy
có thể hiểu và xử lý thông tin hiệu quả.
Ontology đã được tích hợp với quá trình suy diễn logic và hiện nay đã bắt
đầu được áp dụng vào Web có ngữ nghĩa. Có 3 thuộc tính mà ontology phải có là:
- Phân cấp khái niệm con chặt: mỗi thể hiện của một lớp phải là một thể hiện
của lớp cha của nó.
- Không bị sự nhập nhằng trong biểu diễn các ngữ nghĩa và các quan hệ:
người sử dụng có thể định nghĩa các thuộc tính, các giá trị của thuộc tính có thể bị

hạn chế đối với các miền xác định.
- Sử dụng từ vựng điều khiển, giới hạn nhưng có thể mở rộng.
Ngôn ngữ Ontology:
Ngôn ngữ phổ dụng (RDF) cho phép người sử dụng mô tả các tài nguyên
bằng cách sử dụng các tài nguyên riêng của nó. RDFS cung cấp phương pháp xây
dựng một mô hình đối tượng từ dữ liệu thực tế và cho chúng ta ngữ nghĩa của dữ
liệu. Ngắn gọn, RDFS cho phép người sử dụng định nghĩa tài nguyên với các lớp,
các thuộc tính và các giá trị (tương tự khái niệm lớp)
Ngôn ngữ Web Ontology (OWL) mô tả các lớp, các thuộc tính và các quan
hệ giữa các đối tượng khái niệm này theo cách mà máy có thể hiểu được nội dung
Web. OWL là sự kế thừa của RDFS nhưng giàu ngữ nghĩa hơn. OWL được phân
thành ba chủng khác nhau:
- OWL Lite cung cấp các lớp và các thuộc tính có phân cấp, các ràng buộc
đơn giản với đủ khả năng biểu đạt và các ontology đơn giản.
- OWL DL tăng khả năng biểu đạt và tính quyết định của vấn đề phân lớp,
cho phép hỗ trợ suy diễn hiệu quả.
- OWL Full là ngôn ngữ đầy đủ, không có giới hạn, nhưng nó không đưa ra
khả năng quyết định.

23


1.3.2. Logic mô tả trong web ngữ nghĩa.
Các ngôn ngữ biểu diễn Ontology được xây dựng phải cân bằng được khả
năng biểu diễn và độ phức tạp tính toán. Các ngôn ngữ này thường sử dụng cơ sở
logic là logic mô tả để biểu diễn ngữ nghĩa và hỗ trợ lập luận.
Logic mô tả được ứng dụng đặc biệt hiệu quả trong các hệ thống thông minh,
và gần đây với ý tưởng xây dựng hệ thống Web thế hệ mới: Web Ngữ nghĩa, với
mục đích tăng khả năng liên kết giữa các tài nguyên và khả năng hiểu được thông
tin của máy. Logic mô tả đóng vai trò nền tảng logic để bổ sung ngữ nghĩa, hỗ trợ

suy diễn.
Ngôn ngữ mô tả: Ngôn ngữ mô tả đầu tiên được gọi là ngôn ngữ thuộc tính
AL (attributive language), là ngôn ngữ mô tả có các luật cú pháp đơn giản nhất. Các
ngôn ngữ khác của họ ngôn ngữ này là sự mở rộng của ngôn ngữ AL.
Thuật ngữ trong logic mô tả: ta xét các tiên đề thuật ngữ mà thiết lập các câu
lệnh về việc làm thế nào các khái niệm, các quan hệ có liên hệ với các khái niệm,
quan hệ khác.
Trong trường hợp tổng quát nhất, các tiên đề thuật ngữ có dạng:
C ⊐ D (R ⊐ S)

hay

C ≡ D (R ≡ S)

Với C, D là các khái niệm, R và S là các quan hệ. Các tiên đề dạng đầu tiên
được gọi là các tiên đề bao hàm, các tiên đề thứ hai gọi là các đẳng thức.
1.4. TIỂU KẾT CHƯƠNG 1
Chương 1 đã trình bày các khái niệm cơ sở của ngôn ngữ bậc nhất, cú pháp
và ngữ nghĩa của chương trình Datalog theo tiếp cận lý thuyết mô hình và tiếp cận
điểm bất động. Để ý rằng tất cả các biến xuất hiện trong các quy tắc của chương
trình Datalog đều mặc định xuất hiện sau lượng từ với mọi. Chương 1 cũng trình
bày tổng quan về Web ngữ nghĩa, vai trò của Ontology và logic mô tả trong Web
ngữ nghĩa. Ở chương 2 sẽ tìm hiểu việc mở rộng chương trình Datalog khi cho phép
các biến được lượng hóa bởi lượng từ tồn tại xuất hiện trong phần đầu các quy tắc.

24


CHƯƠNG TRÌNH DATALOG±


CHƯƠNG 2

Trong chương 2 sẽ trình bày cú pháp và ngữ nghĩa của một lớp chương trình
Datalog mở rộng, gọi là chương trình Datalog±. Lớp chương trình này là một sự mở
rộng khả năng biểu diễn của Datalog nhằm hướng đến việc trả lời truy vấn trên các
Ontology.
2.1. VÍ DỤ MỞ ĐẦU
Chương trình Datalog đã được thừa nhận có nhiều ứng dụng trong việc biểu
diễn tri thức. Trong các quy tắc Datalog, mặc định tất các các biến đều được ràng
buộc bởi lượng từ “với mọi”. Ta hãy xem định nghĩa đệ quy về quan hệ tổ tiên như
sau:
1. Nếu X là bố/mẹ của Y thì X là tổ tiên của Y,
2. Nếu X là bố của Y và Y là tổ tiên của Z thì X là tổ tiên của Z.

Để biểu diễn mối quan hệ tổ tiên ta có thể dùng các quy tắc Datalog như sau:
totien(X,Y)

←

cha_me(X,Y)

totien(X,Z)

←

cha_me(X,Y), totien(Y,Z)

trong đó totien là vị từ 2-ngôi chỉ quan hệ tổ tiên, cha_me là vị từ 2-ngôi chỉ quan
hệ bố/mẹ. Các biến xuất hiện trong các quy tắc đều được ràng buộc bởi lượng từ ∀.
Các quy tắc này được viết đầy đủ là:

∀X(∀Y(totien(X,Y)

← cha_me(X,Y)))

∀X(∀Y(∀Z(totien(X,Z)

← cha_me(X,Y), totien(Y,Z))))

Tuy nhiên, việc biểu diễn tri thức: mỗi người (nguoi) đều có đúng một người
cha hoặc mẹ (cha/me) lại không thể sử dụng các quy tắc Datalog thông thường như
trên, điều này có thể thực hiện bằng cách đòi hỏi thêm lượng từ “tồn tại” trong phần
đầu các quy tắc Datalog và được biểu diễn như sau:
∀X∃Y (co_cha(X,Y) ← nguoi(X))

25