Đánh giá Horn-DL trong quan hệ so sánh với Horn-Sroiq

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)

ĐÁNH GIÁ HORN-DL TRONG QUAN HỆ SO SÁNH VỚI HORN-SROIQ

Nguyễn Thị Bích Lộc

Khoa Công nghệ Thông tin, Trường Đại học Khoa học – Đại học Huế

Email: [email protected]

TÓM TẮT

Web ngữ nghĩa là một lĩnh vực nghiên cứu phát triển rất nhanh chóng trong những thập

niên gần đây. Một lớp quan trọng trong kiến trúc của Web ngữ nghĩa là ngôn ngữ Web

Ontology (OWL) được xây dựng dựa trên các logic mô tả. Họ các logic mô tả này là các

ngôn ngữ hình thức phù hợp với việc biểu diễn tri thức khái niệm. Vì vậy việc nghiên cứu

các ngôn ngữ quy luật hiệu quả cho Web ngữ nghĩa là một vấn đề được nhiều nhà nghiên

cứu quan tâm. Bài báo nhằm nghiên cứu và đánh giá Horn-DL trong quan hệ so sánh với

các ngôn ngữ có độ phức tạp tương đương¹. Dựa trên các phân tích chúng tôi kết luận

được rằng, khả năng biểu diễn tri thức của ngôn ngữ Horn-DL mạnh hơn hẳn các ngôn

ngữ đã đưa ra so sánh.

Từ khóa: Horn-DL, Logic mô tả, Ngôn ngữ quy luật, Web ngữ nghĩa.

1. MỞ ĐẦU

Logic mô tả là họ các ngôn ngữ dùng để biểu diễn tri thức và lập luận trên cơ sở tri thức

đó, nó được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau, trong đó có Web ngữ nghĩa. Ở

đây, logic mô tả được áp dụng vào trong các ngôn ngữ ontology dùng để biểu diễn miền ứng

dụng. Ngôn ngữ Web ontology (OWL) là tiêu chuẩn để viết ontology cho Web đã được xây

dựng dựa trên các logic mô tả khác nhau.

Phiên bản đầu tiên OWL 1 dựa trên logic mô tả SHIQ, và phiên bản thứ hai OWL 2

được giới thiệu bởi W3C năm 2009 lại dựa trên logic mô tả SROIQ. Tuy nhiên, một vấn đề đặt

ra đó là các ngôn ngữ mô tả có ý nghĩa, khả năng biểu diễn tri thức mạnh thì độ phức tạp trong

lập luận lại cao. Các logic mô tả SHIQ và SROIQ là các ngôn ngữ có khả năng biểu diễn tri

thức cao, nhưng đối với các bài toán lập luận cơ bản thì các logic mô tả này có độ phức tạp tổ

hợp hàm mũ và độ phức tạp dữ liệu thuộc lớp NP-khó. Vì vậy, W3C đã giới thiệu các hồ sơ

1

Các ngôn ngữ có độ phức tạp tương đương ở đây là các ngôn ngữ có độ phức tạp dữ liệu thuộc lớp đa

thức theo thời gian.

1

Đánh giá Horn-DL trong quan hệ so sánh với Horn SROIQ

OWL 2 EL, OWL 2 QL và OWL 2 RL đó là các ngôn ngữ con thu được bằng cách giới hạn

OWL 2 đầy đủ để có độ phức tạp dữ liệu là PTime.

Các ngôn ngữ quy luật trong logic mô tả thu hút sự quan tâm của các nhà nghiên cứu vì

các ứng dụng của nó trong Web ngữ nghĩa. Một mặt, các logic mô tả có khả năng biểu diễn cao

thì các bài toán suy luận lại có độ phức tạp lớn hoặc thậm chí là không xác định được. Mặt khác,

các Logic mô tả yếu (với các thủ tục lập luận hiệu quả) lại không đủ khả năng biểu diễn để mô

tả các khái niệm quan trọng của một ứng dụng đã cho. Vì vậy, việc nghiên cứu sự hài hòa giữa

khả năng biểu diễn của Logic mô tả và độ phức tạp của bài toán lập luận là một vấn đề quan

trọng trong nghiên cứu logic mô tả.

Các hồ sơ OWL 2 EL, OWL 2 QL và OWL 2 RL là các ngôn ngữ quy luật đơn điệu có

độ phức tạp dữ liệu PTime, chúng là các đoạn Horn được xây dựng bằng cách bổ sung các giới

hạn thích hợp để khử tính không tiền định của các họ logic mô tả EL [1], DL-Lite [3] và DLP

[4]. Nhiều đoạn Horn của các logic mô tả có độ phức tạp dữ liệu PTime đã được phát triển theo

cách này. Trong đó đáng chú ý là các đoạn Horn-SHIQ [6] và Horn-SROIQ [9], được biết đến

với các tập cấu trúc và đặc trưng phong phú cho phép trong các đoạn Horn này. Cùng với sự

phát triển trong lĩnh vực ngôn ngữ quy luật, logic mô tả Horn-DL [7] được đề xuất với độ phức

tạp dữ liệu là PTime. Trong bài báo này sẽ đánh giá khả năng mô tả khái niệm của logic mô tả

Horn-DL cùng với các logic mô tả có cùng độ phức tạp dữ liệu PTime.

2. SO SÁNH HORN-DL VỚI HORN-SROIQ

Phần này cho biết cú pháp và ngữ nghĩa của cơ sở tri thức Horn-DL cũng như cơ sở tri

thức Horn-SROIQ. Mỗi cơ sở tri thức đều bao gồm các khẳng định và các tiên đề thuộc các

dạng tương ứng của mỗi ngôn ngữ.

2.1. Logic mô tả Horn-DL

Logic mô tả Horn-DL giới thiệu trong [7] được phát triển từ Logic mô tả Horn-Reg [8]

bằng cách mở rộng tập các khái niệm và bổ sung thêm các khẳng định.

Gọi C, R₊và I là các tập hợp hữu hạn lần lượt là tập các tên khái niệm, tập các tên vai

trò (bao hàm tập con chứa các tên vai trò đơn) và tập các tên cá thể. Ta ký hiệu a, b là các tên cá

thể; A, B là các tên khái niệm; và r, s là các tên vai trò.

Với mỗi r  R₊, ta ký hiệu là đảo ngược của r. Đặt R_= { | r  R₊} và R = R₊R_.

Với R = , ta đặt đại diện cho r. Ta gọi các phần tử của tập R là các vai trò cơ bản và sử dụng

các chữ cái R, S để ký hiệu cho các phần tử này.

Một tiên đề bao hàm vai trò (viết tắt là RIA) là một biểu thức có dạng S₁S₂…S_k⊑R,

với k0. Trường hợp k = 0, vế trái của tiên đề bao hàm được ký hiệu bằng một từ rỗng . Một

khẳng định vai trò là một biểu diễn có dạng Irr(S) hoặc Disj(S,S’), với S và S’ là các vai trò đơn,

Irr viết tắt của “phản phản xạ” và Disj viết tắt của “rời nhau”.

2

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)

Một hệ viết lại phi ngữ cảnh S trên R là một tập hữu hạn các luật sản xuất phi ngữ cảnh

trên bảng chữ R. Hệ gọi là đối xứng nếu luật RS₁S₂…S_kthuộc S, thì luật cũng

thuộc S. Hệ gọi là chính quy nếu với mỗi R  R, thì tập hợp các xâu nhận được từ R khi sử dụng

hệ là một ngô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_hgồm các RIA thỏa mãn

{RS₁S₂…S_k| (S₁ S₂ …  S_k⊑ R)  R_h}

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_alà một tập hữu hạn các

khẳng định vai trò và R_hlà 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 đó ^Ilà một tập

không rỗng gọi là miền của I và ^Ilà 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ử a^I^I, mỗi vai trò rR₊với một quan hệ nhị phân r^I^I^I.

3

Đánh giá Horn-DL trong quan hệ so sánh với Horn SROIQ

Định nghĩa ^I= {x, x | x^I}, U^I= ^I^Ivà ( )^I= (r^I)^-1= {y, x | x, y r^I} 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= {a^I}, (R.Self)^I= {x^I| x, x R^I}, (¬C)^I= ^I\ C^I, (C ⊓ D)^I= C^I D^I,

(C ⊔ D)^I= C^I D^I, (R.C)^I= {x  ^I| y (x, yR^I⇒ y  C^I)}, (U.C)^I= {x  ^I| ^I C^I},

(R.C)^I= {x  ^I| y (x, yR^I y  C^I)}, ( nS.C)^I= {x  ^I| #{y | x, yS^Ivà y  C^I}  n},

( nS.C)^I= {x  ^I| #{y | x, yS^Ivà y  C^I}  n}, (U.C)^I= {x  ^I| C^I ∅}.

Bảng 1. Cú pháp và ngữ nghĩa của Horn-DL.

Cú pháp

S₁S₂…S_k⊑R

Irr(S)

Ngữ nghĩa

S₁^I S₂^I... S_k^I⊑ R^I

S^Iphản phản xạ

(I)

(II)

(III)

RBox

S^IS'^I

Disj(

)

S,S'

= ∅

C^I D^I

a^I C^I

TBox

ABox

(IV)

(V)

(VI)

(VII)

(VIII)

(IX)

C ⊑ D

C(a)

r(a, b)

¬s(a, b)

a≐b

a^I, b^I  r^I

a^I, b^I  s^I

a^I= b^I

a^I≠ b^I

a

b

Trong bảng này, a, b  I, rR₊và s là tên vai trò đơn, S_i, 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ử N_C, N_R, N_Ilà 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 {⊤, ⊥} ⊂ N_C. Nếu r  N_R, thì r và

đảo ngược của chúng tương ứng sẽ là = và = r.

là các vai trò, lúc đó các vai trò

Trong ngôn ngữ SROIQ đầy đủ, một tiên đề bao hàm vai trò tổng quát (RIA) có dạng

s₁ s₂ …  s_k⊑ r, với r và s_ilà 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 N_Rlà 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).

4

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)

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N_Itương ứng với mỗi phần tử a^I^I, mỗi

khái niệm A  N_Cvới mỗi A^I ^Ivà mỗi vai trò rN_Rvớ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

 r^I

⊑ r

(I)

(II)

(II’)

(III)

(IV)

(V)

(VI)

(VII)

(VIII)

(IX)

(X)

TBox

I

 ⊑ r

s₁⊑ r

r   ⊑ r

  r ⊑ r

r  r ⊑ r

Disj(s,s’)

A⊓B ⊑ C

A ⊑ R.B

A ⊑ R.B

R.A ⊑ B

  r

 r^I

I

r    r

I

  r  r

r^I r^I r^I

s^I s’ ^I= ∅

A^I B^I C^I

A^I {x  ^I| y.x, yR^I⇒ y  B^I}

A^I {x  ^I| y.x, yR^I y  B^I}

{x  ^I| y.x, yR^I y  B^I}  A^I

A^I {x  ^I|

 1}

(XI)

A ⊑ 1s.B

 m}

(XII)

A ⊑ m s.B

a:A

(a, b):r

a^I A^I

ABox

(XIII)

(XIV)

a^I, b^I  r^I

Trong bảng này, m  0, a, b  N_I, r  N_R, R là một vai trò và s, s’ là các vai trò đơn.

Ngoài ra,  = s₁ s₂ …  s_k, k1 và với mỗi 1ik thì s_ilà một vai trò thỏa mãn s_i≺ 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.

5

Đánh giá Horn-DL trong quan hệ so sánh với Horn SROIQ

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(

) thì trong R chứa khẳng định vai

s,s'

trò Disj(

).

S,S'

- 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 S₁S₂…S_k⊑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 s₁⊑ 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 S₁S₂…S_k⊑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 S₁S₂…S_k⊑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.

6

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)

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 = <R, T, A> 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).

7

Đánh giá Horn-DL trong quan hệ so sánh với Horn SROIQ

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.

8

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)

EVALUATION OF HORN-DL IN COMPARISON WITH HORN SROIQ

Nguyen Thi Bich Loc

Department of Information Technology, Hue University College of Sciences

Email: [email protected]

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.

9