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 normal forms are the most convenient way to define DLP for teaching and dissemination purposes.
1 AIFB, University of Karlsruhe 2 Hewlett-Packard Germany
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
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 common 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 equality, 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
∃Q(
• 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 constant symbols, C, D are unary predicate symbols, and Q, R, Ri,j are binary predicate 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) ← Q(
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
Q(j−,1)(xj,1, xj,2) ∧ · · · ∧ Q(j−,m)1 (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 theorem.
Theorem 1. Every DLP(+) (DLP(+) IC, DLP(+) ICE) statement made in normal 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 provided 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) ← Q(
∃Q(
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 ABox indiv. assertion property assertion indiv. equiv. indiv. inequiv.
TBox equivalence GCI top bottom conjunction
C(a) R(a, b) a = b ¬(a = b)
C(a) ←
R(a, b) ← ICE a = b ← not expressible in general C ≡ D not expressible in general C ⊑ D D(x) ← C(x) ⊤ expressible C ⊑ ⊥ IC (ri) ⊥ ← C(x) 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 the details. We can, however, make our transformation transparent by means of the transformations listed in Table 1. The statement
∃Q(
D(x) ←
Q(
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
A rule of thumb for the creation of DLP ontologies is: Avoid concrete domains and number restrictions, and be careful with quantifiers, disjunction, and nominals. 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. 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(y) ← Woman(y) Human(y) ← GrownUp(y)
Adult(y) ← GrownUp(y) Mother(y) ← childOf(x, y) ∧ Woman(y)
Dead(y) ← Orphan(x) ∧ childOf(x, y) Human(y) ← Orphan(x) ∧ childOf(x, y)
← LonelyChild(x) ∧ siblingOf(x, y) y = UKARL ← AIFBResearcher(x) ∧ employedBy(x, y) 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)
(
We have presented normal forms for Description Logic Programs, both in Description 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.