Lời cám ơn

Trước hết, tôi xin gửi lời cảm ơn sâu sắc đến thầy Cao Hoàng
Trụ, người đã trực tiếp hướng dẫn tôi hoàn thành bản luận văn này.
Nếu không nhờ những hướng dẫn chu đáo và tận tình chỉ bảo của thầy
cùng những tài liệu quý giá do thầy cung cấp thì có lẽ luận văn này đã
không được hoàn thành và có kết quả như hôm nay.
Tôi xin chân thành cảm ơn tất cả các thầy cô trong Khoa Công
Ngh
ệ Thông Tin, cùng các thầy cô ở Phòng Đào Tạo Sau đại học
trường Đại Học Bách Khoa Tp.Hồ Chí Minh đã giúp đỡ tạo điều kiện
cho tôi hoàn thành khóa học cao học này.
Tôi cũng xin gửi lời cảm ơn đến tất cả người thân, bè bạn,
những người đã động viên, khích lệ tinh thần, giúp tôi vượt qua mọi
khó khăn trong cuộc sống để đạt được kết quả như ngày hôm nay.
Luận vă
n này được hoàn thành trong một thời gian hạn hẹp nên
sẽ không tránh khỏi sai sót, tôi rất mong sự góp ý của quí thầy cô và
các bạn

Học viên
Võ Hoàng Hải

i

1 Tóm tắt

Resource Desription Framework (RDF) và RDF Schema (RDFS) được thừa
nhận là chuẩn biểu diễn thông tin tri thức cho Web ngữ nghĩa. SeRQL là một ngôn

2.1 Giới thiệu 9
2.2 Hằng, Biến, Định danh tài nguyên duy nhất và Biểu thức đường dẫn 9
2.2.1 Hằng, Biến, Định danh tài nguyên duy nhất 9
2.2.2 Biểu thức đường dẫn 10
2.2.3 Cây phân cấp lớp và quan hệ trong RDF&RDFS 14
2.3 Mệnh đề điều kiện luận lý WHERE 14
2.3.1 Các toán tử luận lý cơ bản 15
2.3.2 AND, OR, NOT 16
2.3.3 Mệnh đề WHERE lồng trong điều kiện tùy chọn 16
2.3.4 Các hàm kiểm tra luận lý khác củ
a SeRQL 17
2.4 Các tính năng nâng cao và tùy chọn khác 18
2.4.1 Truy vấn lồng nhau – Query Nesting 18
2.4.2 Các phép toán tập hợp 21

iii
2.4.3 Các mệnh đề OFFSET và LIMIT 22
2.5 Kết luận 23
3 Chương 3: NGÔN NGỮ ĐỒ THỊ Ý NIỆM TRUY VẤN TRI THỨC
25

3.1 Giới thiệu 25
3.2 Đồ thị ý niệm truy vấn tri thức đơn giản - sCGQL 25
3.3 Đồ thị ý niệm truy vấn tri thức - CGQL 27
3.4 Đồ thị ý niệm truy vấn tri thức mở rộng - xCGQL 31
3.5 Kết luận 34
4 CHƯƠNG 4: HIỆN THỰC HỆ THỐNG TRUY VẤN TRI THỨC36
4.1 Giới thiệu 36
4.2 Tổng quan hệ thống truy vấn tri thức bằng xCGQL 37
4.3 Xây dựng công cụ soạn thảo đồ thị ý niệm truy vấn - xCGQL Editor . 39

Hình 2.4.1.1 Truy vấn “Tìm tên của những người là tác giả” 19
Hình 2.4.1.2 Truy vấn “Tìm tên và sở thích của những người có trùng tên với tên
tác giả nào đó” 20

Hình 2.4.1.3 Truy vấn “Tìm giá trị lớn nhất trong của các tài nguyên trong cơ sở dữ
liệu” 21

Hình 2.4.2.1 Ví dụ truy vấn với các phép toán tập hợp 22
Hình 2.4.3.1 Ví dụ truy vấn với các mệnh đề OFFSET, LIMIT 23
Hình 3.3.1 Ví dụ mở rộng thuộc tính 27
Hình 3.3.2: Biểu diễn chi tiết cho đỉnh khái niệm mở rộng 28
Hình 3.3.3 Truy vấn đỉnh mở rộng có điều kiện 30
Hình 3.4.1 Đỉnh truy vấn con các quan hệ 31
Hình 4.2.1: Hệ thống truy vấn tri thức bằng đồ thị ý niệm 37
Hình 4.2.2: Hệ thống truy vấn tri thức chi tiết 38
Hình 4.3.1: Cấu trúc bộ soạn thảo 40
Hình 4.3.2.1 Soạn thảo Đỉnh khái niệm 43

v
Hình 4.3.2.2 Soạn thảo Kiểu khái niệm 44

Hình 4.3.2.3 Soạn thảo tham chiếu thực thể khái niệm 45
Hình 4.3.2.4 Soạn thảo cây ràng buộc điều kiện 46
Hình 4.3.2.5 Ví dụ giao diện soạn thảo đồ thị ý niệm 47
Hình 4.3.3.1 Soạn thảo đỉnh quan hệ 48
Hình 4.3.3.2 Cây phân cấp kiểu quan hệ 49
Hình 4.3.4.1 Cây ràng buộc điều kiện thuộc tính 51
Hình 4.4.1.1 Các mức truy vấn lồng nhau 54
Hình 4.4.1.2 Cấu trúc quản lý đối tượng 55
Hình 4.4.3.1 Chuyển đổi câu truy vấn sang SeRQL 65

.
Hơn nữa, trong lĩnh vực biểu diễn tri thức, với kết luận CG dễ dàng được tích hợp
với Web ngữ nghĩa [16]
, chúng ta hoàn toàn tin tưởng vào việc có thể xây dựng 2
được một ngôn ngữ CG tương ứng với SeRQL – một ngôn ngữ truy vấn tri thức
Web ngữ nghĩa biểu diễn bằng RDF&RDFS.
Mục tiêu của luận văn là phát triển một ngôn ngữ đồ thị ý niệm truy vấn
(CGQL) đủ mạnh, có khả năng diễn đạt gần tương đương với SeRQL khi truy vấn
tri thức biểu diễn bằng RDF&RDFS. Để thực hiện điều này, chúng tôi nghiên cứu
các thành phần cơ bản của ngôn ngữ SeRQL kết hợp với việc khai thác sức mạnh
diễn đạt, suy luận của CG, từ đó xây dựng nên các thành phần của ngôn ngữ CG
tương ứng. Ngôn ngữ CG này cần phải được biểu diễn hình thức ở bước tiếp theo.
Công việc cuối cùng là thực hiện một hệ thống truy hồi tri thức dùng đồ thị ý niệm
đã xây dựng ở phầ
n giao diện.
1.2 Các công trình liên quan
1.2.1 Resource Desription Framework (RDF)
RDF được xem là chuẩn biểu diễn và chuyển đổi thông tin cho Web ngữ
nghĩa. Trong RDF, thông tin về một tài nguyên (resource) nào đó được biểu diễn
dưới dạng mệnh đề (statement). Mệnh đề là một bộ ba chủ ngữ-vị từ-bổ ngữ
(subject-predicate-object triple). Cách thức biểu diễn thông tin của RDF cho phép
các máy tính giao tiếp với nhau theo ngữ nghĩa của đối tượng nhưng cú pháp bộ ba
của RDF không dễ đọc và hiểu bởi con người. RDF Primer tiế
p cận theo hướng
diễn đạt mô hình RDF một cách trực quan bằng đồ thị [12]
. Trong đồ thị RDF, các
chủ ngữ, bổ ngữ của bộ ba RDF được biểu diễn bằng các đỉnh của một đồ thị, trong

vấn dữ liệu cổ điển (SQL) cho đến ngôn ngữ luật sinh, theo hướng suy luận dựa trên
các luật (rules language).
Các ngôn ngữ truy vấn RDF lại có các chức năng hoặc cách hỗ trợ mở rộng
khác nhau. Tuy rằng hiện nay vẫn chưa có một ngôn ngữ nào được chấp nhận là
chuẩn s
ử dụng, gần đây W3C đã đưa ra đặc tả và yêu cầu chung cho một ngôn ngữ
truy vấn dữ liệu RDF [10]
.
Các ngôn ngữ truy vấn hầu hết đều được xem xét trên các tính chất chung bao
gồm khả năng diễn đạt của ngôn ngữ, tính đóng, tính đầy đủ, tính trực giao và tính
an toàn [4]
. Hơn nữa, các ngôn ngữ truy vấn này phải đáp ứng được các yêu cầu của
mô hình RDF. RDF là mô hình dữ liệu trừu tượng chỉ bao gồm các bộ ba RDF nên
các ngôn ngữ sẽ không cung cấp các chức năng truy vấn liên quan đến việc lưu trữ
dự liệu cụ thể. Mô hình RDF không chỉ lưu trữ thông tin mà còn hỗ trợ suy luận tri
thức [14]
. Do đó các ngôn ngữ truy vấn cũng phải xem xét khía cạnh này và cung
cấp chức năng nhận biết các hệ quả suy luận này. Ngôn ngữ truy vấn tri thức còn
phải hỗ trợ tính không đầy đủ thông tin của mô hình RDF vì không phải bất cứ tài
nguyên nào được lưu trữ cũng có đầy thông tin mô tả về nó.
1.2.3 Ngôn ngữ truy vấn SeRQL
SeRQL là ngôn ngữ hiệu quả đáp ứng các yêu cầu truy vấn RDF. SeRQL là
một phần của Sesame [8]
, một kiến trúc lưu trữ và truy vấn đa dạng tri thức biểu
diễn bằng RDF và RDFS đang được phát triển bởi Aduna. Ngôn ngữ này kết hợp
các đặc tính của các ngôn ngữ truy vấn khác và thêm các chức năng riêng của mình
để đáp ứng được hầu hết các yêu cầu chính yếu. Đồng thời trong quá trình phát 5

viết câu truy vấn dễ dàng nhưng với cú pháp tương tự ngôn ngữ SQL, SeRQL vẫn
còn phức tạp với người dùng bình thường nếu không được học bài bản. 6
1.2.4 Đồ thị ý niệm
Đồ thị ý niệm (CG) là một hệ thống luận lý dựa trên đồ thị tồn tại của Charles
Sanders Peirce và mạng ngữ nghĩa. Ngôn ngữ CG cho phép sử dụng một hình thức
đồ họa trực quan để diễn đạt ý nghĩa chính xác về mặt luận lý nhưng lại thân thiện
với người dùng mà máy tính có thể xử lý được. Đồ thị ý niệm là một đồ thị phân đôi
(bipartile graph) bao gồm hai loại đỉnh: các
đỉnh khái niệm (concept) và các đỉnh
quan hệ (relation) trong đó các đỉnh khái niệm chỉ liên kết với các đỉnh quan hệ bởi
các cạnh và ngược lại. Phép chiếu (projection) trên một đồ thị ý niệm chuẩn hóa cho
phép chúng ta thực hiện được các suy luận dựa trên cơ sở tri thức [10]
. Tri thức biểu
diễn trong đồ thị khái niệm dựa trên hai dàn phân cấp (hierarchy lattice) là kiểu khái
niệm (concept type) và quan hệ (relation type).
Bằng cách kết hợp các khái niệm và các quan hệ, mô hình CG có thể dùng để
biểu diễn tri thức trực quan thân thiện với người dùng. Sau đây là một ví dụ dùng
CG để biểu diễn cho phát biểu “Nam học một môn thuộc khoa CNTT”:
Hình 1.2.4.1: Ví dụ CG
Trong ví dụ trên, [Sinh viên: Nam],[Môn:*] và [Khoa:CNTT] là các khái niệm
có kiểu khái niệm lần lượt là Sinh viên, Môn, Khoa còn (Học) và (Thuộc) là các
quan hệ. Các tham chiếu –referents- Nam và CNTT của các khái niệm [Sinh
viên:Nam] và [Khoa:CNTT] là các kí hiệu cá thể – individual markers chỉ định rõ
một đối tượng thuộc về một kiểu khái niệm nào đó. Tham chiếu * trong khái niệm
[Môn:*] là một kí hiệu chung ám chỉ sự tồn tại của thực thể nào đó. Hai khái niệm
khác nhau nếu tham chiếu đến hai cá thể khác nhau. Như vậy để nói rõ hai tham
chiếu * cùng là m

biểu diễn bằng RDF và đề nghị gi
ải quyết vấn đề truy vấn dữ liệu RDF bằng CG
trong tương lai.
Sinh viên:
N
Môn: *
Học
Khoa: CNTT
Thuộc
Người: * Môn: *
Học 8
1.3 Cấu trúc luận văn
Tiếp theo sau chương 1 là phần trình bày chi tiết về ý tưởng và phương pháp
của chúng tôi để đạt được mục tiêu đã đề ra. Cấu trúc các chương tiếp theo như sau:
Chương 2 trình bày chi tiết các thành phần cấu trúc của ngôn ngữ SeRQL.
Mục 2.2, 2.3 trình bày các thành phần cơ bản nhất của ngôn ngữ SeRQL. Các tính
năng nâng cao được trình bày ở mục 2.4. Song song với việc trình bày các thành
phần của ngôn ngữ SeRQL ở các mục 2.2, 2.3 và 2.4, phương pháp ánh xạ các
thành phần này vào các thành phần tương
ứng của đồ thị ý niệm trong ngữ cảnh
của tri thức biểu diễn bằng RDF&RDFS cũng được đề cập.
Chương 3 tiếp theo giới thiệu ngôn ngữ truy vấn tri thức bằng đồ thị ý niệm
(CGQL). Chương này tập trung mô tả hình thức cho ngôn ngữ CGQL từ các mức
đơn giản ở các mục 3.2 và 3.3 đến mức nâng cao ở mục 3.4.
Việc xây dựng hiện thực hệ thống truy vấ
n tri thức sử dụng ngôn ngữ CGQL
ở phần giao diện được trình bày ở chương 4. Mục 4.2 trình bày tổng quan hệ thống

Định danh tài nguyên duy nhất (từ đây gọi tắt là tài nguyên) và hằng là các
thành phần cơ bản trong biểu diễn dữ liệu RDF. Tài nguyên có thể là vị từ hay bổ
ngữ như hằng nhưng cũng có thể là chủ ngữ của một bộ ba RDF. Chính vì vậy, cả
hằng và tài nguyên đều là các thành phần không thể thiếu để thành lập câu truy vấn
SeRQL. Ngoài tài nguyên và hằng, trong câu truy vấn SeRQL, biến cũng là một
thành phần chính dùng để trả về
kết quả tìm kiếm. Biến cũng có thể là chủ ngữ, vị 10
từ hay bổ ngữ được xác định bởi một tên. Như vậy, thật sự là hằng, biến hay tài
nguyên là các thành phần cơ bản nhất trong câu truy vấn SeRQL sẽ tùy theo ngữ
cảnh truy vấn của nó mà được ánh xạ vào thành phần nào trong ngôn ngữ CG tương
ứng. Nói cách khác hằng, biến hay tài nguyên đều có thể là khái niệm hay quan hệ
trong một CG.
2.2.2 Biểu thức đường dẫn
Biểu thức đường dẫn là thành phần cơ bản nhất trong SeRQL. Biểu thức
đường dẫn sẽ được so trùng với một thành phần đồ thị trong RDF khi thực hiện câu
truy vấn.
2.2.2.1 Đường dẫn cơ bản
Biểu thức đường dẫn cơ bản nhất trong SeRQL thực chất là một bộ ba RDF
được biểu diễn {node} edge {node}. Một cách tự nhiên để biểu diễn biểu thức
đường dẫn cơ bản trong mô hình CG là chuyển đổi bộ ba RDF thành một đồ thị CG:
chuyển chủ ngữ hay bổ ngữ của bộ ba RDF thành khái niệm và chuyển vị từ thành
quan hệ [7]
. Câu truy vấn “Ai là người học môn Toán?” có thể biểu diễn bằng
SeRQL và CG tương ứng (giả sử kí hiệu <xxx> là một địa chỉ tài nguyên cụ thể)
như sau:
Hình 2.2.2.1.1: Ví dụ đường dẫn cơ bản
Một phát biểu RDF chỉ là bộ ba (chủ ngữ, vị từ, bổ ngữ) nên quan hệ trong CG

{subj}pred1{obj1},{subj}pred2{obj2}
Thực chất các cách viết gọn của SeRQL là sự phát triển dựa trên biểu thức
đường dẫn cơ bản và các quan hệ luận lý. Do đó chỉ cần ánh xạ các chủ ngữ, bổ ngữ
thành khái niệm và vị từ thành quan hệ như trên thì hoàn toàn có thể biểu diễn được
các biểu thức đường dẫn mở rộng tương ứng (sau khi biểu diễn được các quan hệ
luận lý). 12
2.2.2.3 Reification
Biểu diễn RDF cho phép dùng mệnh đề RDF để mô tả một mệnh đề RDF
khác. Ngôn ngữ SeRQL cho phép biểu diễn cấu trúc cú pháp cho Reification:
{{reifSubj}reifPred{reifObj}} pred {obj}
Trên thực tế, SeRQL hỗ trợ cách viết tắt cho Reification dựa trên RDFS, bao
gồm các vị từ cơ bản như rdf:type, rdf:subject, rdf:predicate, rdf:object và
rdf:Statement. Như vậy biểu thức đường dẫn Reification trên đây sẽ tương đương
với tập các biểu thức đường dẫn cơ bản sau:
 {_statement}rdf:type{rdf:Statement},

{_statement}rdf:subject {reifSubj},
 {_statement}rdf:predicate{reifPredicate},
 {_statement}rdf:object{reifObj},
 {_statement}pred{obj}
Như vậy chỉ cần định nghĩa bổ sung các kiểu khái niệm và quan hệ tương ứng
với các vị từ, chủ ngữ hay bổ ngữ của RDFS sẽ cho phép biểu diễn được Reification
trong ngôn ngữ CG tương ứng.
2.2.2.4 Đường dẫn tùy chọn – (Optional Match)
SeRQL cho phép truy vấn trong điều kiện giá trị dữ liệu không tồn tại đối với
một vị từ nào đó. Điều này cho phép truy vấn dữ liệu không đầy đủ biểu diễn bằng
RDF. Phần biểu thức đường dẫn có vị từ chấp nhận truy vấn dữ liệu không tồn tại

[Property]
? Title
foo:title
?
[foo:author]14
[<foo:có tác giả>{Tác giả}[<foo:có tên>{Tên}];
[<foo:email>{Email}]]

Như vậy theo cách hiểu đã qui định,
Tên và Email lần lượt có vị từ
<foo:có tên> và <foo:email> là tùy chọn đối với Tác giả và Tác giả có vị
từ
<foo:có tác giả> là tùy chọn của Tài liệu. Hơn nữa cả Tên, Email
cũng là tùy chọn đối với
Tài liệu.
2.2.3 Cây phân cấp lớp và quan hệ trong RDF&RDFS
SeRQL hỗ trợ RDFS thông qua các vị từ. Ví dụ vị từ <rdfs:subClassOf> để
diễn đạt quan hệ lớp con trong RDF [9]
. Ngoài ra SeRQL cung cấp thêm các vị từ
xây dựng sẵn cho phép truy vấn về sự phân cấp các lớp. Các vị từ này được dùng
như những vị từ của bộ ba RDF trong các biểu thức đường dẫn hoặc dùng để kiểm
tra điều kiện luận lý trên những đối tượng truy vấn trong mệnh đề WHERE [3]
. Sau
đây là một số vị từ được cung cấp trong SeRQL:
 <serql:directSubClassOf>
 <serql:directSubPropertyOf>
 <serql:directType>.

ất định tương ứng. Vấn đề này sẽ được xem
xét khi hiện thực hệ thống. Dưới đây là ví dụ minh họa cho câu truy vấn: “Chỉ ra
các tỉnh thành có dân số nhỏ hơn 1000000” :
Select TỉnhTP
From {TỉnhTP} <foo:có dân số> {Dânsố}
Where Dânsố > “1000000”^^xsd:Integer
Hình 2.3.1.1 Ví dụ về câu truy vấn dân số > 1000000

TỉnhTP:?
Dân số
Có dân s
ố
Integer:1000000
> 16
2.3.2 AND, OR, NOT
Trong SeRQL, các toán tử quan hệ luận lý giữa các đối tượng truy vấn có thể
kết hợp với nhau qua các ràng buộc luận lý AND, OR, NOT trong mệnh đề
WHERE.Trong mô hình CG đơn giản qui tắc ràng buộc AND giữa các quan hệ
được hiểu là các mệnh đề viết liền nhau. Để phủ định một tập các quan hệ, chúng ta
tạo khái niệm mệnh đề bao lấy rồi phủ định [13]
. Qui tắc OR được thực hiện thông
qua phép biến đổi Demorgan: x OR y = NOT((NOT x) AND (NOT y)). Tuy nhiên,
điều này quá phức tạp với người sử dụng cuối cùng nên không được sử dụng trong
ngôn ngữ CG của chúng tôi.
Để mô tả đơn giản hơn cho người sử dụng đầu cuối, ngôn ngữ CG được mở
rộng bằng cách ẩn đi các điều kiện luận lý bên trong bản thân các khái niệm hay
quan hệ. Vấn đề này sẽ đượ

định danh tài nguyên URIs. Các hàm này vừa cho phép trả về giá trị truy vấn vừa
cho phép thực hiện chức năng kiểm tra luận lý trong mệnh đề WHERE. Các hàm
tiện ích trên hằng bao gồm
label(), lang() và datatype(), còn các hàm tiện
ích trên tài nguyên là
namespace() và localName(). Mỗi hàm tương ứng được
xây dựng một cặp quan hệ luận lý và khái niệm tương ứng:
 Khái niệm là đối tượng chứa kết quả trả về của hàm
 Quan hệ giữa đối tượng hàm thực hiện với đối tượng kết quả
Xét ví dụ minh họa sau: “Tìm những tài nguyên trong cơ sở dữ liệu có nhãn là
tên hằng bằng tiếng Anh”
Select label(L)
From {R} rdfs:label {L}
Person:* Name:?
name
EmailAddress:?
[email]
String: g*
LIKE 18
Where isLiteral(L) AND lang(L) like “en*”
Hình 2.3.4.1 Ví dụ truy vấn các hàm kiểm tra luận lý

Như vậy hàm lang() được mô tả trong CG bằng cặp quan hệ lang() và
khái niệm
String : ? . Về mặt biểu diễn, chúng tôi dùng cặp dấu ngoặc đơn ()
theo sau tên các hàm trong quan hệ luận lý của CG để phân biệt với các phép toán
luận lý bình thường,

minh họa cách diễn đạt bằng mô hình CG khi gặ
p các câu truy vấn lồng nhau.
“Tìm tên của những người là tác giả”. Một cách viết theo truy vấn con như
sau: “Tìm tên của những người có tên trong các tên tác giả”.
Select Name
From {} rdf:type {ex:person}; ex:name {Name}
Where Name IN (
Select n
From {} rdf:type {ex:Author};
ex:name {n}
)
Hình 2.4.1.1 Truy vấn “Tìm tên của những người là tác giả”

SubQUERY:
* ex:Autho
r

rdf:type
ex:name
n?
IN
*
ex:Person
rdf:type
ex:name
Name:?