Đánh giá horn-dl trong quan hệ so sánh với horn-sroiq

n ngữ chính quy trên R. 
Một box chính quy các RIA là một tập hữu hạn R
h
 gồm các RIA thỏa mãn 
{R S1S2Sk | (S1  S2    Sk ⊑ R) Rh} 
là một hệ viết lại chính quy đối xứng S trên bảng chữ R sao cho nếu R R là một vai trò đơn thì 
chỉ có các xâu độ dài 1 hoặc 0 nhận được từ R khi sử dụng hệ S. 
Một RBox chính quy là một tập R = R
a
  R
h
, trong đó R
a 
là một tập hữu hạn các 
khẳng định vai trò và R
h
 là một box chính quy các RIA. 
Với A C, R R, a I, n là một số tự nhiên và S là một vai trò đơn, các khái niệm được 
xác định bởi văn phạm dạng BNF như dưới đây: 
C ::= ⊤ | ⊥ | A | ¬C | C⊓C | C⊔C | R.C | R.C |{a}| U.C |U.C| R.Self | nS.C | nS.C 
Ta ký hiệu U R là vai trò phổ quát; C, D là các khái niệm. 
Sử dụng ký hiệu R.C để viết tắt cho R.C⊓R.C. Với A C, R R, a I và S là một 
vai trò đơn, các khái niệm ở vế trái Horn-DL (gọi tắt là khái niệm vế trái), được xác định bởi 
văn phạm dạng BNF như sau: 
C ::= ⊤ | A | C⊓C | C⊔C | R.C | R.C |{a}| U.C |U.C| S.Self 
Với A C, D là một khái niệm vế trái, R R, a I và S là một vai trò đơn, các khái niệm 
ở vế phải Horn-DL (gọi tắt khái niệm vế phải), được xác định bởi văn phạm dạng BNF như sau: 
C ::= ⊤ | ⊥ | A | ¬D | C⊓C | ¬D⊔C | R.C | R.C |{a}| U.C |U.C| R.Self| nS.C | nS.C 
Một tiên đề thuật ngữ Horn-DL, còn gọi là tiên đề (bao hàm) TBox là một biểu thức có 
dạng C ⊑ D, với C là khái niệm vế trái và D là khái niệm vế phải. 
TBox Horn-DL là một tập hữu hạn các tiên đề thuật ngữ Horn-DL. 
ABox Horn-DL là một tập hữu hạn các khẳng định có dạng C(a), r(a, b), ¬s(a, b), a≐b 
hoặc a b, với C là khái niệm vế trái, r R+ và s là tên vai trò đơn. 
Một cơ sở tri thức Horn-DL là một bộ R, T, A, với R là một RBox chính quy, T là 
một TBox Horn-DL và A là một ABox Horn-DL. 
Ngữ nghĩa của cơ sở tri thức Horn-DL là một diễn giải I =  I, I, trong đó I là một tập 
không rỗng gọi là miền của I và I là hàm diễn giải của I tương ứng mỗi cá thể a I với một 
phần tử aI I, mỗi vai trò r R+ với một quan hệ nhị phân r
I
  I I. 
Đánh giá Horn-DL trong quan hệ so sánh với Horn SROIQ 
4 
Định nghĩa I = {x, x | x I}, UI = I I và ( )I = (rI)-1 = {y, x | x, y rI} với r R+. 
Hàm diễn giải được mở rộng đối với tất cả các khẳng định và các tiên đề như trong Bảng 1 và 
đối với các khái niệm phức như sau: 
⊤I = I , ⊥I = ∅, {a}I = {aI}, (R.Self)I = {x I | x, x RI }, (¬C)I = I \ CI, (C ⊓ D)I = CI  DI, 
(C ⊔ D)I = CI  DI, (R.C)I = {x I | y (x, y RI ⇒ y CI)}, (U.C)I = {x I | I  CI }, 
(R.C)I = {x I | y (x, y RI  y CI)}, ( nS.C)I = {x I | #{y | x, y SIvà y CI} n}, 
( nS.C)I = {x I | #{y | x, y SIvà y CI} n}, (U.C)I = {x I | CI ∅}. 
Bảng 1. Cú pháp và ngữ nghĩa của Horn-DL. 
Cú pháp Ngữ nghĩa 
(I) S1S2Sk⊑R 
I
k
II SSS ...21 ⊑ R
I
 RBox 
(II) Irr(S) S
I
 phản phản xạ 
(III) Disj( ',SS ) II SS ' = ∅ 
(IV) C ⊑ D CI  DI TBox 
(V) C(a) a
I
 CI ABox 
(VI) r(a, b) aI, bI  rI 
(VII) ¬s(a, b) aI, bI  sI 
(VIII) a≐b aI = bI 
(IX) a b aI ≠ bI 
Trong bảng này, a, b I, r R+ và s là tên vai trò đơn, Si, R R, và S, S’ là các vai trò 
đơn, k ≥ 0, C là khái niệm vế trái, D là khái niệm vế phải. Như vậy, các tiên đề bao hàm TBox 
là một họ các tiên đề bao hàm dạng (IV). 
2.2. Logic mô tả Horn-SROIQ và Horn-SHOIQ 
Logic mô tả Horn-SROIQ [9] được định nghĩa là một đoạn của SROIQ đầy đủ [5] 
nhưng trong đó không cho phép sử dụng phép hợp. 
Giả sử NC, NR, NI là các tập hữu hạn, tương ứng là tập tên các khái niệm, tên các vai trò 
và các cá thể; Giả sử rằng {⊤, ⊥} ⊂ NC. Nếu r NR, thì r và là các vai trò, lúc đó các vai trò 
đảo ngược của chúng tương ứng sẽ là = và = r. 
Trong ngôn ngữ SROIQ đầy đủ, một tiên đề bao hàm vai trò tổng quát (RIA) có dạng 
s1  s2    sk ⊑ r, với r và si là các vai trò. Một tập các RIA R là chính quy nếu có một thứ tự 
cục bộ nghiêm ngặt ≺ trên các vai trò sao cho s ≺ r nếu và chỉ nếu ≺ r, và mỗi RIA trong R 
phải có dạng (I) hoặc (V) trong Bảng 2. Các vai trò đơn trong R được định nghĩa một cách đệ 
quy như sau: (a) r NR là vai trò đơn nếu r ở vế phải của các RIA dạng s⊑r và s là vai trò đơn; 
và (b) là vai trò đơn nếu r là vai trò đơn. 
Một TBox T có dạng RT’, trong đó R là một tập chính quy chứa các RIA và T’ là 
một tập các tiên đề có các dạng từ (VI) đến (XII) trong Bảng 2. Cơ sở tri thức Horn-SROIQ là 
một bộ K = T, A, với T là một TBox và ABox A là một tập không rỗng các khẳng định có 
dạng (XIII) và (XIV). 
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học – ĐH Huế Tập 7, Số 1 (2017) 
5 
Logic mô tả Horn-SHOIQ thu được bằng cách giới hạn Horn-SROIQ như sau: chỉ 
cho phép các RIA dạng (I), (II’) và (V) trong Bảng 2; không cho phép các tiên đề rời nhau như 
dạng (VI) ở Bảng 2, các khái niệm dạng r.Self cũng không cho phép. 
Cũng như các logic mô tả khác, ngữ nghĩa của cơ sở tri thức ở đây được cho bởi diễn 
giải I =  I, I. Diễn giải này ánh xạ mỗi cá thể a NI tương ứng với mỗi phần tử a
I
 I, mỗi 
khái niệm A NC với mỗi A
I
  I và mỗi vai trò r NR với một quan hệ nhị phân r
I
  I I, 
sao cho ⊤I = I, ⊥I = ∅. Ánh xạ I được mở rộng đến tất cả các khái niệm và các vai trò như được 
giới thiệu trong Bảng 2. 
Bảng 2. Cú pháp và ngữ nghĩa của Horn-SROIQ. 
Cú pháp Ngữ nghĩa 
(I) ⊑ r  rI TBox 
(II)  ⊑ r I  rI 
(II’) s1 ⊑ r  r
I 
(III) r   ⊑ r rI  I  rI 
(IV)   r ⊑ r I  rI  rI 
(V) r  r ⊑ r rI  rI  rI 
(VI) Disj(s,s’) sI  s’ I = ∅ 
(VII) A⊓B ⊑ C AI  BI  CI 
(VIII) A ⊑ R.B AI  {x I | y.x, y RI ⇒ y BI} 
(IX) A ⊑ R.B AI  {x I | y.x, y RI  y BI} 
(X) R.A ⊑ B {x I | y.x, y RI  y BI}  AI 
(XI) A ⊑ 1s.B A
I  {x I | 1} 
(XII) A ⊑ m s.B A
I  {x I | m} 
(XIII) a:A a
I
 AI ABox 
(XIV) (a, b):r aI, bI  rI 
Trong bảng này, m 0, a, b NI, r NR, R là một vai trò và s, s’ là các vai trò đơn. 
Ngoài ra,  = s1  s2    sk, k 1 và với mỗi 1 i k thì si là một vai trò thỏa mãn si ≺ r. A, B và 
C là các tên khái niệm, các định danh dạng {a} hoặc có thể là các dạng r.Self. 
2.3. Bài toán thỏa được của cơ sở tri thức 
Một diễn giải I là một mô hình của cơ sở tri thức KB, nếu nó thỏa mãn tất cả các tiên 
đề trong TBox và tất cả các khẳng định trong ABox, ký hiệu I ⊨KB. Bài toán thỏa được của 
cơ sở tri thức là bài toán quyết định xem đối với một cơ sở tri thức KB đã cho, liệu có tồn tại 
một mô hình I để cho I ⊨ KB hay không. 
Lớp độ phức tạp dữ liệu của Horn-DL được định nghĩa là lớp độ phức tạp của bài toán 
thỏa được của cơ sở tri thức Horn-DL theo kích thước của ABox A, giả định rằng RBox R và 
TBox T là cố định và A là một ABox Horn-DL rút gọn [7]. Lúc đó độ phức tạp dữ liệu của 
Horn-DL thuộc lớp PTime. 
Đánh giá Horn-DL trong quan hệ so sánh với Horn SROIQ 
6 
Bài toán thỏa được của cơ sở tri thức Horn-SROIQ thuộc lớp ExpTime [9], và nếu cố 
định TBox T thì độ phức tạp dữ liệu của Horn-SROIQ thuộc lớp PTime. 
3. KẾT QUẢ VÀ THẢO LUẬN 
Mặc dù độ phức tạp dữ liệu của cơ sở tri thức Horn-SROIQ và Horn-DL đều thuộc lớp 
PTime, tuy nhiên khả năng biểu diễn tri thức của các ngôn ngữ này không hoàn toàn như nhau. 
3.1. Đánh giá RBox của Horn-DL và tập các RIA của Horn-SROIQ 
Giả sử R’ là tập các RIA của Horn-SROIQ và R là một RBox của Horn-DL. Dựa trên 
cú pháp và ngữ nghĩa của Horn-SROIQ và Horn-DL, chúng ta thấy rằng mọi biểu diễn trên R’ 
đều có thể được biểu diễn bằng cách sử dụng các khẳng định vai trò hoặc các tiên đề bao hàm 
vai trò trong R. 
- Nếu R’ có chứa khẳng định vai trò dạng Disj( ',ss ) thì trong R chứa khẳng định vai 
trò Disj( ',SS ). 
- Nếu R’ chứa tiên đề bao hàm vai trò dạng ⊑ r thì trong R chứa S ⊑ R, đây là 
trường hợp đặc biệt của tiên đề bao hàm vai trò dạng S1S2Sk⊑R, với k = 1 và S là nghịch 
đảo của một tên vai trò đơn (tức là S Rˍ); 
- Nếu R’ chứa tiên đề bao hàm vai trò dạng s1 ⊑ r thì trong R chứa S ⊑ R, ở đây S là 
một vai trò con của R; 
- Nếu R’ chứa các tiên đề bao hàm vai trò dạng  ⊑ r, r   ⊑ r,   r ⊑ r, r  r ⊑ r, thì 
trong R chứa các tiên đề bao hàm vai trò có dạng S1S2Sk⊑R, ở đây giá trị của k ≥ 1; 
Như vậy ta có thể thấy rằng mọi tập chứa các RIA của Horn-SROIQ cũng có thể là 
một RBox trong Horn-DL, nhưng điều ngược lại không đúng. Cụ thể, nếu trong RBox của 
Horn-DL chứa khẳng định vai trò Irr(S) thì khả năng biểu diễn tính phản phản xạ của một vai trò 
trong R’ của Horn-SROIQ không thực hiện được. Ngoài ra, RBox trong Horn-DL còn có thể 
chứa các tiên đề bao hàm vai trò dạng ⊑ R (trường hợp đặc biệt của S1S2Sk⊑R, với k = 0), 
nhưng trong các RIA của Horn-SROIQ dạng này không cho phép. 
3.2. Đánh giá TBox của Horn-DL và TBox của Horn-SROIQ 
Các tiên đề bao hàm khái niệm của Horn-SROIQ gồm các tiên đề từ dạng (VII) đến 
dạng (XII) trong bảng 2. Các tiên đề bao hàm TBox của Horn-DL là các tiên đề dạng C ⊑ D, 
trong đó C là khái niệm vế trái, D là khái niệm vế phải. Ta nhận thấy rằng mọi vế trái của quan 
hệ bao hàm ⊑ trong các tiên đề từ (VII) đến (XII) của Horn-SROIQ thì đều được chấp nhận 
bởi các khái niệm vế trái C, và vế phải của mọi quan hệ bao hàm ⊑ trong các tiên đề này cũng 
đều được chấp nhận bởi các khái niệm vế phải D. Tuy nhiên ngược lại không đúng. 
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học – ĐH Huế Tập 7, Số 1 (2017) 
7 
Trong Horn-SROIQ khái niệm r.Self chỉ có thể xuất hiện ở vế phải của quan hệ bao 
hàm ⊑ khi r là một vai trò đơn, trong khi ở Horn-DL thì chấp nhận R.Self với R là một vai trò 
bất kỳ. 
Khái niệm vế trái C có thể có dạng R.C, tuy nhiên Horn-SROIQ không cho phép 
cấu trúc R.C ở vế trái của tiên đề bao hàm TBox. 
Ngoài ra, Horn-DL còn chứa vai trò phổ quát trong khi Horn-SROIQ không chấp nhận 
vai trò này. 
Như vậy mọi TBox của Horn-SROIQ cũng có thể là một TBox trong Horn-DL, nhưng 
điều ngược lại không đúng. 
3.3. Đánh giá ABox của Horn-DL và ABox của Horn-SROIQ 
Từ bảng 1 và bảng 2, ta thấy mọi ABox của Horn-SROIQ đều có thể là ABox của 
Horn-DL, tuy nhiên điều ngược lại không đúng. Trong ABox của Horn-DL chứa các khẳng định 
dạng Irr(S), s(a, b), a b nhưng ABox của Horn-SROIQ không chấp nhận các dạng này. 
3.4. Bài toán minh họa và đánh giá 
Chúng ta mô tả quan hệ trong gia đình từ khái niệm nguyên tử là Human như sau. 
Đặt R = {hasChild ⊑ , ⊑ hasParent, hasChild ⊑ hasDescendant, 
hasChild hasChild ⊑ hasDescendant, ,  
 ⊑ }. 
T = {Man ⊑ Human, Woman ⊑ Human, Man ⊓ Woman ⊑ ⊥, hasChild.Human ⊑ Parent, 
hasChild.Parent ⊑ GrandParent, Parent ⊓ Man ⊑ Father, Parent ⊓ Woman ⊑ Mother, 
hasChild.Woman ⊑ ParentHasNoSon, hasChild.Man ⊑ ParentHasNoDaughter}. 
A = {Man(Tom), Woman(Helen), ParentHasNoDaughter(Peter), hasChild(Olga, Peter), 
hasChild(Peter, Bill), hasChild(Peter, Win), hasChild(Helen, Win), hasDescendant(Tom, Win), 
Bill Win, ¬hasChild(Tom, Helen)}. 
Lúc đó KB = là cơ sở tri thức Horn-DL. Ta có thể thấy rằng Tom, Peter là 
các thể hiện của khái niệm Father tương ứng với KB và Tom, Peter, Bill, Win là các thể hiện 
của khái niệm Man tương ứng với KB, đồng thời KB ⊨ hasChild(Tom, Peter). 
Nếu dùng các cấu trúc của Horn-SROIQ để mô tả cơ sở tri thức trên, khi đó chúng ta 
không thể mô tả các bao hàm khái niệm hasChild.Woman ⊑ ParentHasNoSon, 
hasChild.Man ⊑ ParentHasNoDaughter thì chúng ta chưa đủ cơ sở để suy ra Bill, Win là các 
thể hiện của Man được. Ngoài ra, cấu trúc của Horn-SROIQ cũng không thể mô tả Bill Win, 
¬hasChild(Tom, Helen) và do đó các mô hình của cơ sở tri thức cũng chưa chắc thỏa 
hasChild(Tom, Peter). 
Đánh giá Horn-DL trong quan hệ so sánh với Horn SROIQ 
8 
4. KẾT LUẬN 
Bài báo đã đánh giá khả năng biểu diễn tri thức của các ngôn ngữ quy luật, từ đó kết 
luận được rằng Horn-DL về cơ bản hoàn toàn mạnh hơn Horn-SROIQ. Như vậy, Horn-DL là 
một ngôn ngữ có khả năng biểu diễn tri thức cao và việc nghiên cứu để phát triển Horn-DL là 
một nghiên cứu có nhiều triển vọng. Hướng phát triển trong tương lai là tìm kiếm các thuật toán 
hiệu quả để trả lời truy vấn trong cơ sở tri thức Horn-DL. 
LỜI CẢM ƠN 
Xin cảm ơn Trường Đại học Khoa học Huế đã cấp kinh phí cho bài báo này (đây là một 
phần trong đề tài Nghiên cứu Khoa học cấp cơ sở Trường). Cảm ơn Khoa Công nghệ Thông tin, 
các thầy cô và đồng nghiệp đã tạo mọi điều kiện để nghiên cứu này được hoàn thành. 
TÀI LIỆU THAM KHẢO 
[1]. F. Baader, S. Brandt, and C. Lutz (2005). Pushing the EL envelope, In Proceedings of IJCAI’2005, 
Edinburgh, pp. 364-369. 
[2]. F. Baader, S. Brandt, and C. Lutz (2008). Pushing the EL envelope futher, In Proceedings of 
OWLED 2008 DC Workshop on OWL: Experiences and Directions, Washington. 
[3]. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati (2007). Tractable reasoning 
and efficient query answering in description logics: The DL-Lite family, J. Automated Reasoning, 
vol. 39(3), pp. 385-429. 
[4]. B.N. Grosof, I. Horrocks, R. Volz, and S. Decker (2003). Description logic programs: combining 
logic programs with description logic, In Proc. of WWW’2003, Budapest, pp. 48-57. 
[5]. I. Horrocks, O. Kutz, U. Sattler (2006). The Even More Irresistible SROIQ, In Proc. KR’2006, 
Lake District, pp. 57-67. 
[6]. U. Hustadt, B. Motik, and U. Sattler (2007). Reasoning in description logics by a reduction to 
disjuntive Datalog, J. Automated Reasoning, vol. 39(3), pp. 351-384. 
[7]. L.A. Nguyen, T.B.L. Nguyen, and A. Szałas (2013). Horn-DL: An expressive Horn description logic 
with PTime data complexity, In Proc. of RR’2013, Mannheim, vol. 7994 of LNCS, pp. 259-246. 
[8]. L.A. Nguyen (2010). Horn knowledge base in regular description logics with PTime data 
complexity, Fundamenta Informaticae, vol. 104(4), pp. 349-384. 
[9]. M. Ortiz, S. Rudolph, and M. Šimkus (2010). Worst-case Optimal Reasoning for the Horn-DL 
Fragments of OWL 1 and 2, In Proc. KR’2010, Toronto, pp. 269-279. 
[10]. M. Ortiz, S. Rudolph, and M. Šimkus (2011). Query answering in the Horn fragments of the 
description logics SHOIQ and SROIQ, In Proceedings of IJCAI’2011, Barcelona, pp. 1039-1044. 
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học – ĐH Huế Tập 7, Số 1 (2017) 
9 
EVALUATION OF HORN-DL IN COMPARISON WITH HORN SROIQ 
Nguyen Thi Bich Loc
Department of Information Technology, Hue University College of Sciences 
Email: ntbichloc@hueuni.edu.vn 
ABSTRACT 
Semantic Web is a research area which has been rapidly growing in the last decades. One 
of the important layers of Semantic Web is Web Ontology Language (OWL), which is based 
on the description logics (DLs). These logics are formal languages suitable for 
representing terminological knowledge. Thus, effective rule languages are a research 
problem received much attention from researchers. In this article, we have researched and 
evaluated Horn-DL in comparison with languages of same complexity. Basing on the 
analysis we concluded that the ability of knowledge representation of Horn-DL fragments 
is stronger than the languages compared. 
Keywords: Description Logics, Horn-DL, Rule Languages, Semantic Web.