=Paper=
{{Paper
|id=Vol-277/paper-5
|storemode=property
|title=Description Logic Programs: Normal Forms
|pdfUrl=https://ceur-ws.org/Vol-277/paper5.pdf
|volume=Vol-277
|dblpUrl=https://dblp.org/rec/conf/ki/HitzlerE07
}}
==Description Logic Programs: Normal Forms==
https://ceur-ws.org/Vol-277/paper5.pdf
Description Logic Programs: Normal Forms⋆
Pascal Hitzler1 and Andreas Eberhart2
1
AIFB, University of Karlsruhe
2
Hewlett-Packard Germany
Abstract. The relationship and possible interplay between different
knowledge representation and reasoning paradigms is a fundamental topic
in artificial intelligence. For expressive knowledge representation for the
Semantic Web, two different paradigms – namely Description Logics
(DLs) and Logic Programming – are the two most successful approaches.
A study of their exact relationships is thus paramount.
An intersection of OWL with (function-free non-disjunctive) Datalog,
called DLP (for Description Logic Programs), has been described in [1,
2]. We provide normal forms for DLP in Description Logic syntax and
in Datalog syntax, thus providing a bridge for the researcher and user
who is familiar with either of these paradigms. We argue that our nor-
mal forms are the most convenient way to define DLP for teaching and
dissemination purposes.
1 Introduction
The Web Ontology Language OWL3 [3] has been recommended by the W3C
consortium as a standard for the Semantic Web. Based on Description Logics
[4], it provides a sound foundation for the development of sophisticated Semantic
Web technology. It is however understood that the expressivity of OWL lacks
certain features which can most naturally be covered by rule-based approaches
akin to Logic Programming [5], like F-Logic and its variants [6]. At the same time,
pure Logic Programming based approaches to ontology modelling are also being
used in practice, in particular in the form of F-Logic. Providing interoperability
between the two paradigms is thus of practical importance.
In [1] the intersection between OWL-DL and function-free disjunctive Dat-
alog has been described, and called Description Logic Programs (DLP). Since
then, this paradigm has been extended considerably. Most notably, it has been
developed into an efficient and flexible reasoning system using techniques from
disjunctive Datalog for OWL-DL reasoning [7–10] — including the translation
of a major fragment of OWL-DL to disjunctive Datalog. But it has also been
used in different contexts, e.g. for defining OWL Light− [11].
⋆
The authors acknowledge support by the German Federal Ministry for Education and
Research under the SmartWeb project (01 IMD01 B), by the Deutsche Forschungs-
gemeinschaft (DFG) under the ReaSem project, and by the EU in the IST project
NeOn (IST-2006-027595, http://www.neon-project.org/)).
3
http://www.w3.org/2004/OWL/
At the same time, DLP has been a focus of discord in the scientific dispute
about the use of open-world versus closed-world knowledge representation and
reasoning in the semantic web [12]. We believe, however, that DLP can serve
as a basic interoperability layer between these paradigms, at least for scientific
investigations, as spelled out in [12]. It may even find more practical uses if
considered as a tractable fragment of OWL in the sense of the W3C member
submission on OWL 1.14 , or as a basis for the W3C Rule Interchange Format
RIF5 , as it provides a bridge e.g. between OWL and the Web Rule Language
WRL6 .
This short technical note has been written with the sole purpose of describing
normal forms for DLP, both in Description Logic and in Datalog syntax. We
see this as a helpful step for dissemination into adjacent fields of research and
possibly also into practice. At the same time, our normal forms can be used as
definitions for DLP which – in our opinion - are much more concise and more
transparent than others.
For clarification, we note that we do not consider Datalog to come with a
specific semantics (like the minimal model semantics) which is different from its
first-order logic semantics. We simply consider it to be a syntactic fragment of
first order logic which thus inherits its semantics. Some people prefer the notion
OWL-Horn in this case, instead of DLP, but it does not really matter in our
context.
The paper is structured as follows. In Section 2 we provide normal forms for
DLP in both DL and Datalog form, and formally prove that they are indeed
normal forms. In Section 3 we give an extended example for DLP using our
syntax, and in Section 4 we conclude.
2 Normal Forms
We assume that the reader is familiar with basic Description Logics [4], with
OWL [3] and basic notions from logic programming [5]. For detailed background
on DLP we recommend [2], and for a much shorter overview [1].
We need to fix terminology first. We call DLP the (semantic) fragment com-
mon to OWL Lite and Datalog, i.e. we abstract (for the time being) from a
concrete syntax: Every OWL Lite statement which is semantically equivalent —
in the sense of first order logic — to a (finite) set of function-free Horn clauses (i.e.
Datalog rules) constitutes a valid DLP statement. Likewise, every function-free
Horn clause which is semantically equivalent to some set of OWL Lite statements
constitutes a valid DLP statement7 . Allowing integrity constraints, we call the
4
http://www.w3.org/Submission/2006/10/
5
http://www.w3.org/2005/rules/
6
http://www.w3.org/Submission/2005/08/
7
In our terminology, the set of OWL Lite statements {C ⊑ D ⊔ E, D ≡ E} would
not qualify as a set of DLP statements, although it is semantically equivalent to
{C ⊑ D, D ≡ E}, which is expressible in DLP. We are well aware of this restriction,
but will not be concerned with it in the moment, because this more general notion
resulting fragment DLP IC (or just IC). Allowing integrity constraints and equal-
ity, we call the resulting fragment DLP ICE (or ICE). We write DLP+ for the
(semantic) fragment common to OWL DL and (function-free non-disjunctive)
Datalog. Analogously, we write DLP+ IC, IC+ , etc.
In the following, we will give normal forms, both on the Description Logic
side and on the Datalog side. I.e. we provide syntactic fragments which allow
expressing (semantically) everything in DLP.
2.1 Normal Form for Description Logic Syntax
Allowed are the following, where a, b, ai stand for individuals, C stands for a
concept name and R, Q, Ri , Qi,j stand for role names.
– ABox:
C(a) (individual assertion)
R(a, b) (property assertion)
a = b (ICE) (individual equivalence)
– Property Characteristics:
R≡Q (equivalence)
R⊑Q (subproperty)
⊤ ⊑ ∀R.C (C = ⊥) (domain)
⊤ ⊑ ∀R− .C (C = ⊥) (range)
R ≡ Q− (inverse)
R ≡ R− (symmetry)
⊤ ⊑ ≤ 1R (ICE) (functionality)
⊤ ⊑ ≤ 1R− (ICE) (inverseFunctionality)
– TBox: We allow expressions of the form
(−) (−) (−) (−) (−)
∃Q1,1 . . . ∃Q1,m1 Left1 ⊓ · · · ⊓ ∃Qk,1 . . . ∃Qk,mk Leftk ⊑ ∀R1 . . . ∀Rn(−) .Right
where the following apply.
• For DLP we allow Leftj to be of the forms C, {o1 , . . . , on }, ⊥ or ⊤, and
Right to be of the forms C or ⊤.
• For DLP IC we allow Leftj to be of the forms C, {o1 , . . . , on }, ⊥, or ⊤,
and Right to be of the form C, ⊤, or ⊥.
• For DLP ICE we allow Leftj to be of the forms C, {o1 , . . . , on }, ⊥, or
⊤, and Right to be of the form C, ⊤, ⊥, or {o}.
• For the DLP+ versions we furthermore allow Right to be of the form
∃R(−) .{a}.
The superscript (−) shall indicate, that an inverse symbol may occur in
these places. Note that (by a common abuse of notation) we allow any of
k, mi , n to be zero. For k = 0 the left hand side becomes ⊤. Note also that
we could have disallowed ⊥ on the left and ⊤ on the right, since in either
of semantic equivalence is not readily accessible by syntactic means. Note, however,
that C ⊑ D ⊔ D qualifies as a DLP statement, since it is semantically equivalent to
C ⊑ D.
case the statement becomes void. Likewise, it would suffice to require n = 0
in all cases, since universal quantifiers on the right are expressable using
existentials on the left. Disallowing the existential quantifiers on the left
(while keeping universals on the right) is also possible, but at the expense
of the introduction of an abundance of new concept names. As an example,
note that ∃R.C ⊓ ∃Q.D ⊑ E would have to be translated into the set of
statements {C1 ⊓ D1 ⊑ E, C ⊑ ∀R− .C1 , D ⊑ ∀Q− .D1 }, where C1 and D1
are new concept names. Our representation is more compact.
2.2 Normal Form for Datalog Syntax
Allowed are the following, where x, y, z, yi , xi,j are variables, a, b, c, aj are con-
stant symbols, C, D are unary predicate symbols, and Q, R, Ri,j are binary pred-
icate symbols.
– Corresponding to ABox:
C(a) ← (individual assertion)
R(a, b) ← (property assertion)
a = b ← (individual equivalence)
– Corresponding to Property Characteristics:
Q(x, y) ← R(x, y) (subproperty)
C(y) ← R(x, y) (domain)
C(y) ← R(y, x) (range)
R(x, y) ← Q(y, x) (inverse subproperty)
R(x, y) ← R(y, x) (symmetry)
y = z ← R(x, y) ∧ R(x, z) (ICE) (functionality)
y = z ← R(y, x) ∧ R(z, x) (ICE) (inverseFunctionality)
– Corresponding to TBox: We allow rules of the form
(−) (−)
Left(y) ← Q1,1 (x1,1 , x1,2 ) ∧ · · · ∧ Q1,m1 (x1,m1 , x) ∧ Right1 (x)
∧ ...
(−) (−)
∧ Qk,1 (xk,1 , xk,2 ) ∧ · · · ∧ Qk,m1 (xk,mk , x) ∧ Rightk (x)
(−)
∧ R1 (x, y1 ) ∧ · · · ∧ Rn(−) (yn−1 , y),
where Rightj (x) is of the form C(x) or R(−) (x, a), and Left(y) is of the form
D(y), or (for DLP IC) ⊥, or (for DLP ICE) y = b, or (for DLP+ versions)
Q(y, c). Furthermore, we require all variables x, y, yi , xi,j to be mutually
distinct.
The meaning of the inverse symbol here is as follows: For a binary predicate
symbol R we let R− (x, y) stand for R(y, x). A bracketed inverse symbol
in the superscript (−) hence means that the order of the arguments of the
corresponding predicate symbol is not relevant.
By slight abuse of notation we allow any of k, n, mj to be zero, which may
cause the body of the rule to be empty. For mj = 0 the form of
(−) (−)
Qj,1 (xj,1 , xj,2 ) ∧ · · · ∧ Qj,m1 (xj,mj , x) ∧ Rightj (x)
reduces to Rightj (x), with Rightj (x) as indicated. For n = 0 we require y
to be x.
Concerning the terminology just introduced, we can show the following the-
orem.
Theorem 1. Every DLP(+) (DLP(+) IC, DLP(+) ICE) statement made in nor-
mal form for Description logic syntax is semantically equivalent to a set of
DLP(+) (DLP(+) IC, DLP(+) ICE) statements made in normal form for Datalog
syntax. Conversely, every DLP(+) (DLP(+) IC, DLP(+) ICE) statement made
in normal form for Datalog syntax is semantically equivalent to a set of DLP(+)
(DLP(+) IC, DLP(+) ICE) statements made in normal form for Description
Logic syntax.
Proof. We use the translations between Description Logic and Datalog as pro-
vided in [1, 2], and summarized in Table 1. How to obtain the semantically
equivalent statements for the ABox and the Property Characteristics parts is
evident from this summary.
Now consider a rule
(−) (−)
Left(y) ← Q1,1 (x1,1 , x1,2 ) ∧ · · · ∧ Q1,m1 (x1,m1 , x) ∧ Right1 (x)
∧ ...
(−) (−)
∧ Qk,1 (xk,1 , xk,2 ) ∧ · · · ∧ Qk,m1 (xk,mk , x) ∧ Rightk (x)
(−)
∧ R1 (x, y1 ) ∧ · · · ∧ Rn(−) (yn−1 , y),
where Left(y) and Rightj (x) are as indicated above. This translates to the
statement
(−) (−) (−) (−) (−)
∃Q1,1 . . . ∃Q1,m1 Ri1 ⊓ · · · ⊓ ∃Qk,1 . . . ∃Qk,mk Rik ⊑ ∀R1 . . . ∀Rn(−) .Le,
where Le is
– D if Left(x) is D(x),
– ⊥ if Left(x) is ⊥,
– {b} if Left(x) is x = b, and
– ∃Q(−) .{c} if Left(x) is Q− (x, c)
and Rej is
– C if Rightj (xj,1 ) is C(xj,1 ), and
– ∃R(−) .{aj } if Rightj (xj,1 ) is R(−) (xj,q , aj ).
We need to justify our translation by showing that the resulting Datalog rule
is semantically equivalent to the Description Logic statement from which it was
obtained. It boils down to somewhat tedious equivalence transformations in first
order logic following the exhibitions in [1, 2], and we will not be bothered with
OWL DL DL statement DLP rule
ABox
indiv. assertion C(a) C(a) ←
property assertion R(a, b) R(a, b) ←
indiv. equiv. a=b ICE a = b ←
indiv. inequiv. ¬(a = b) not expressible in general
TBox
equivalence C≡D not expressible in general
GCI C⊑D D(x) ← C(x)
top ⊤ expressible
bottom C⊑⊥ IC (ri) ⊥ ← C(x)
conjunction C ⊓D ⊑E E(x) ← C(x) ∧ D(x)
C ⊑E⊓F E(x) ← C(x)
F (x) ← C(x)
disjunction C ⊔D ⊑E (le) E(x) ← C(x)
E(x) ← D(x)
atomic negation ¬A not expressible in general
univ. restriction D ⊑ ∀R.C (C = ⊥) (ri) C(y) ← D(x) ∧ R(x, y)
D ⊑ ∀R.⊥ IC (ri) ⊥ ← D(x) ∧ R(x, y)
exist. restriction ∃R.C ⊑ D (C = ⊥) (le) D(x) ← R(x, y) ∧ C(y)
∃R.⊥ ⊑ D IC (le) ⊥ ← R(x, y) ∧ C(y)
one-of 1 C ⊑ {a} ICE a = x ← C(x)
{a} ⊑ C C(a) ←
hasValue ∃R.{a} ⊑ C C(x) ← R(x, a)
C ⊑ ∃R.{a} DLP+ R(x, a) ← C(x)
one-of {o1 , . . . , on } ⊑ C (le) C(oi ) ← (for i = 1, . . . , n)
card. restrictions ... not expressible in general
Property Characteristics
equivalence R≡Q R(x, y) ← Q(x, y)
Q(x, y) ← R(x, y)
subproperty R⊑Q Q(x, y) ← R(x, y)
domain ⊤ ⊑ ∀R.C (C = ⊥) C(y) ← R(x, y)
range ⊤ ⊑ ∀R− .C (C = ⊥) C(y) ← R(y, x)
inverse R ≡ Q− R(x, y) ← Q(y, x)
Q(x, y) ← R(y, x)
symmetry R ≡ R− R(x, y) ← R(y, x)
transitivity R(x, y) ← R(x, z) ∧ R(z, y)
functionality ⊤ ⊑≤ 1R ICE y = z ← R(x, y) ∧ R(x, z)
inverseFunctionality ⊤ ⊑≤ 1R− ICE y = z ← R(y, x) ∧ R(z, x)
Table 1. Translation from DL to Datalog, taken from [1, 2]. The abbreviation ri (le)
means right (left) of GCI only.
the details. We can, however, make our transformation transparent by means of
the transformations listed in Table 1. The statement
(−) (−) (−) (−) (−)
∃Q1,1 . . . ∃Q1,m1 Ri1 ⊓ · · · ⊓ ∃Qk,1 . . . ∃Qk,mk Rik ⊑ ∀R1 . . . ∀Rn(−) .Le
can be written as the pair of statements
(−) (−) (−) (−)
∃Q1,1 . . . ∃Q1,m1 Ri1 ⊓ · · · ⊓ ∃Qk,1 . . . ∃Qk,mk Rik ⊑ D
(−)
D ⊑ ∀R1 . . . ∀Rn(−) .Le,
where D is a new concept name. These statements can be translated separately
into
(−) (−)
D(x) ← Q1,1 (x1,1 , x1,2 ) ∧ · · · ∧ Q1,m1 (x1,m1 , x) ∧ Right1 (x)
∧ ...
(−) (−)
∧ Qk,1 (xk,1 , xk,2 ) ∧ · · · ∧ Qk,m1 (xk,mk , x) ∧ Rightk (x)
and
(−)
Left(y) ← D(x) ∧ R1 (x, y1 ) ∧ · · · ∧ Rn(−) (yn−1 , y).
By unfolding over D(x) we obtain the desired combined rule.
The translation can obviously be performed in both directions, so there is
nothing more to show.
It is possible to strengthen Theorem 1 by providing a translation between
single Description Logic statements and single Datalog rules (in normal form).
In this case we would have to disallow the property characteristics inverse on
the OWL side, which can be done since R ≡ Q− is expressible e.g. by the set of
statements {R ⊑ Q− , Q− ⊑ R}, each member of which is in turn translatable
into a single Datalog statement. Similarly, property equivalence would have to
be disallowed. We think that the form we have chosen is more concise.
Theorem 2. All description logic programs following [1, 2] can be written in
normal form.
Proof. All statements belonging to DLP as described in [1, 2] are listed in Table
1. It is easy to check that all possibly resulting Datalog statements listed in the
last column are already in normal form, which suffices to show the statement.
3 Examples
A rule of thumb for the creation of DLP ontologies is: Avoid concrete domains
and number restrictions, and be careful with quantifiers, disjunction, and nom-
inals. We give a small example ontology which includes the safe usage of the
latter constructs. It shall display the modelling expressivity of DLP.
For the TBox, we model the following sentences.
(1) Every man or woman is an adult.
(2) A grown-up is a human who is an adult.
(3) A woman who has somebody as a child, is a mother.
(4) An orphan is the child of humans who are dead.
(5) A lonely child has no siblings.
(6) AIFB researchers are employed by the University of Karlsruhe.
They can be written in DLP as follows.
Man ⊔ Woman ⊑ Adult (1)
GrownUp ⊑ Human ⊓ Adult (2)
Woman ⊓ ∃childOf− .⊤ ⊑ Mother (3)
Orphan ⊑ ∀childOf.(Dead ⊓ Human) (4)
LonelyChild ⊑ ¬∃siblingOf.⊤ (5)
AIFBResearcher ⊑ ∃employedBy.{UKARL} (6)
In normal form in Description Logic syntax these are as follows.
Man ⊑ Adult (1)
Woman ⊑ Adult (1)
GrownUp ⊑ Human (2)
GrownUp ⊑ Adult (2)
Woman ⊓ ∃childOf− .⊤ ⊑ Mother (3)
Orphan ⊑ ∀childOf.Dead (4)
Orphan ⊑ ∀childOf.Human (4)
LonelyChild ⊑ ∀siblingOf.⊥ (5)
AIFBResearcher ⊑ ∃employedBy.{UKARL} (6)
We note that for (5) we require DLP IC, while for (6) we require DLP+ .
For the RBox, we use the following.
parentOf ≡ childOf− parentOf and childOf are inverse roles.
parentOf ⊑ ancestorOf parentOf is a subrole of ancestorOf.
fatherOf ⊑ parentOf fatherOf is a subrole of parentOf.
⊤ ⊑ ∀ancestorOf.Human Human is the domain of ancestorOf.
⊤ ⊑ ≤ 1fatherOf− fatherOf is inverse functional.
We can populate the classes and roles by means of an ABox in the following
way.
{Bernhard, Benedikt, Rainer, Ganter} ⊑ Man
{Ruth, Ulrike} ⊑ Woman
Bernhard = Ganter
employedBy(Bernhard, TUD)
...
Note that an ABox statement such as
{Ruth, Ulrike} ⊑ Woman
is simply syntactic sugar for the two statements
Woman(Ruth) Woman(Ulrike)
We therefore consider it to be part of the ABox. To be precise, the original
statement is (syntactically) not in OWL Lite, but the equivalent set of three
ABox statements is. The statement Bernhard = Ganter requires DLP ICE.
Note also that class inclusions cannot in general be replaced by equivalences.
For example, the statement
Adult ⊑ Man ⊔ Woman
is not in DLP.
For illustration, we give the knowledge base in Datalog normal form. The
TBox is as follows.
Adult(y) ← Man(y) (1)
Adult(y) ← Woman(y) (1)
Human(y) ← GrownUp(y) (2)
Adult(y) ← GrownUp(y) (2)
Mother(y) ← childOf(x, y) ∧ Woman(y) (3)
Dead(y) ← Orphan(x) ∧ childOf(x, y) (4)
Human(y) ← Orphan(x) ∧ childOf(x, y) (4)
← LonelyChild(x) ∧ siblingOf(x, y) (5)
y = UKARL ← AIFBResearcher(x) ∧ employedBy(x, y) (6)
Translating the RBox yields the following statements.
parentOf(x, y) ← childOf(y, x)
childOf(x, y) ← childOf(y, x)
ancestorOf(x, y) ← parentOf(x, y)
parentOf(x, y) ← fatherOf(x, y)
Human(y) ← ancestorOf(x, y)
y = z ← fatherOf(y, x) ∧ fatherOf(z, x)
4 Conclusions
We have presented normal forms for Description Logic Programs, both in De-
scription Logic syntax and in Logic Programming syntax. We have formally
shown that these are indeed normal forms.
We believe that these normal forms can and should be used for defining
Description Logic Programs. We have found that some of the definitions used in
the literature remain somewhat ambiguous, so that the language is not entirely
specified. This brief note rectifies this problem in providing a frame of reference.
References
1. Grosof, B., Horrocks, I., Volz, R., Decker, S.: Description logic programs: Com-
bining logic programs with description logics. In: Proc. of WWW 2003, Budapest,
Hungary, May 2003, ACM (2003) 48–57
2. Volz, R.: Web Ontology Reasoning with Logic Databases. PhD thesis, University
of Manchester (2004)
3. Antoniou, G., van Harmelen, F.: Web Ontology Language: OWL. In Staab, S.,
Studer, R., eds.: Handbook on Ontologies. Springer (2004) 67–92
4. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P., eds.:
The Description Logic Handbook: Theory, Implementation, and Applications.
Cambridge University Press (2003)
5. Lloyd, J.W.: Foundations of Logic Programming. Springer, Berlin (1988)
6. Angele, J., Lausen, G.: Ontologies in F-logic. In Staab, S., Studer, R., eds.:
Handbook on Ontologies. Springer (2004) 29–50
7. Hustadt, U., Motik, B., Sattler, U.: Reducing SHIQ-description logic to disjunctive
datalog programs. In Dubois, D., Welty, C.A., Williams, M.A., eds.: Principles of
Knowledge Representation and Reasoning: Proceedings of the Ninth International
Conference (KR2004), Whistler, Canada, June 2-5, 2004, AAAI Press (2004) 152–
162
8. Hustadt, U., Motik, B., Sattler, U.: Reasoning in description logics with a con-
crete domain in the framework of resolution. In de Mántaras, R.L., Saitta, L.,
eds.: Proceedings of the 16th Eureopean Conference on Artificial Intelligence,
ECAI’2004, including Prestigious Applicants of Intelligent Systems, PAIS 2004,
Valencia, Spain, August 22-27, 2004, IOS Press (2004) 353–357
9. Motik, B.: Reasoning in description logics using resolution and deductive
databases. PhD theis, University Karlsruhe, Germany (2006)
10. Motik, B., Sattler, U., Studer, R.: Query answering for OWL-DL with rules.
Journal of Web Semantics: Science, Services and Agents on the World Wide Web
3 (2005) 41–60
11. de Bruijn, J., Pollerres, A., Lara, R., Fensel, D.: OWL− . WSML Working Draft,
DERI (2004)
12. Hitzler, P., Haase, P., Krötzsch, M., Sure, Y., Studer, R.: DLP isn’t so bad after
all. In Grau, B.C., Horrocks, I., Parsia, B., , Patel-Schneider, P., eds.: Proceedings
of the Workshop OWL – Experiences and Directions, Galway, Ireland. Volume
188 of CEUR Workshop Proceedings. (2005) Online http://ftp.informatik.rwth-
aachen.de/Publications/CEUR-WS/Vol-188/sub2.pdf.