=Paper=
{{Paper
|id=Vol-1417/paper9
|storemode=property
|title=Datalog+, RuleML and OWL 2: Formats and Translations for Existential Rules
|pdfUrl=https://ceur-ws.org/Vol-1417/paper9.pdf
|volume=Vol-1417
|dblpUrl=https://dblp.org/rec/conf/ruleml/BagetGLMRS15
}}
==Datalog+, RuleML and OWL 2: Formats and Translations for Existential Rules==
<pdf width="1500px">https://ceur-ws.org/Vol-1417/paper9.pdf</pdf>
<pre>
               Datalog+, RuleML and OWL 2:
         Formats and Translations for Existential Rules

       Jean-François Baget, Alain Gutierrez, Michel Leclère, Marie-Laure Mugnier,
                            Swan Rocher, and Clément Sipieter

                            Inria, CNRS and University of Montpellier
                                            France


         Abstract. This paper is devoted to formats and translations for Datalog+. We
         first introduce the dlgp format, which extends classical Datalog format to Dat-
         alog+. It allows to encode facts, existential rules (including equality), negative
         constraints and conjunctive queries. Moreover, for compatibility with Semantic
         Web languages, this format includes Web notions (IRIs and literals, according to
         Turtle syntax). Second, we define a translation from dlgp to the Datalog+ frag-
         ment of RuleML. Third, we define a translation from OWL 2 to dlgp. We point
         out that the composition of both translations allows to import OWL 2 to RuleML.
         The associated parsers and translators are available.


1     Introduction
The novel framework of existential rules, also known as Datalog+ (and Datalog± for
its decidable fragments) raised considerable interest in the last years, specially in the
context of ontology-mediated query answering. For the theoretical foundations of this
framework, we refer the reader to [CGK08,BLMS09,CGL09,BLMS11,KR11,CGP12].
A sublanguage of RuleML corresponding to Datalog+ has been recently defined (see
Deliberation RuleML 1.01).1
    This paper is devoted to formats and translators for the existential rule framework.
It can be seen as a companion to the paper [BLM+ 15] devoted to Graal, a toolkit for
querying existential rule knowledge bases. First, we introduce a textual format, called
dlgp, for “Datalog+”. This format is indeed an extension of the classical Datalog format
to Datalog+. In addition, to ensure compatibility with Semantic Web languages, the
current version (2.0) includes Web notions like IRIs and literals. Second, we briefly
present a translation from dlgp to (the Datalog+ sublanguage of) RuleML, which is
quite direct. Third, we define a translation from OWL 2 to dlgp. More precisely, we
define OWL 2 ER, an OWL 2 profile that can be translated into the existential rule
framework. In particular, this profile generalizes so-called tractable profiles of OWL
2. Our translator from OWL 2 to dlgp accepts as input any OWL 2 file but ignores
(parts of) OWL 2 axioms that cannot be recast as axioms of OWL 2 ER. Note that the
composition of both translations allows to import OWL 2 to RuleML.
    The dlgp parser, as well as translators from dlgp to RuleML and from OWL 2 to dlgp
are available online at http://graphik-team.github.io/graal/ (Graal home-
page). The paper focuses on salient aspects of these three points and illustrates them
 1
     http://wiki.ruleml.org/index.php/Specification_of_Deliberation_RuleML_1.01
2         J.-F. Baget, A. Gutierrez, M. Leclère, M.-L. Mugnier, S. Rocher, C. Sipieter

by examples. Details on the dlgp format and OWL 2 ER profile (including OWL 2 ER
grammar) can be found in technical reports available on Graal website.

Preliminaries. We recall here the basic components of the existential rule framework:
facts, (pure) existential rules, which include equality rules, negative constraints and
conjunctive queries. We consider logical atoms of the form p(t1 . . . tn ), where p is a
predicate of any arity greater or equal to one (i.e., n ≥ 1) and the ti are variables or
constants. We also consider equality atoms (of the form t1 = t2 ). By conjunction, we
mean a conjunction of such atoms.

    – A (pure) existential rule is a positive rule of the form ∀X∀Y (B[X, Y ] → ∃Z
      H[X, Z]), where X, Y and Z are sets of variables, B (the body) is a conjunc-
      tion with variables in X and Y , and H (the head) is a conjunction with variables
      in X and Z; hence Z denotes the set of variables that occur in H but not in B; a
      specific kind of pure existential rules are equality rules, whose head is restricted to
      an equality atom.
    – A fact is an existentially closed conjunction, i.e., of the form ∃XF[X], where F is
      a conjunction whose set of variables is exactly X. Note that we generalize here the
      classical notion of a fact defined as a ground atom. Indeed, a fact is usually seen as
      a rule with an empty body, hence the previous definition is in line with existential
      rules. Moreover, existential variables in facts allow to naturally encode unknown
      values in databases (“nulls”) or blank nodes in RDF.
    – A negative constraint is the negation of a fact, i.e., of the form ¬∃XC[X]; equiva-
      lently, it can be seen as a rule with a head restricted to the always-false symbol ⊥:
      ∀X(C[X] → ⊥);
    – A conjunctive query is an existentially quantified conjunction, in which the free
      variables are called answer variables. It can also be seen as a rule of the form
      ∀X∀Y (B[X, Y ] → ans(X)), where ans is a special predicate and X is the set of
      answer variables.

      The following running example illustrates these different components.

Example 1 (Running example). We consider a vocabulary composed of the following
predicates, with their arity mentioned after their name: Project/1, Researcher/1, isPro-
ject/3, hasCost/2, hasExpertise/2, isMember/2. The unary predicates can be seen as
types of entities (i.e., classes or concepts); the ternary predicate isProject relates a
project, the area of this project and the leader of this project; the predicate hasCost
relates a project and its cost, while predicates hasExpertise and isMember relate a re-
searcher to an area and to a project, respectively.
    We consider a knowledge base built on this vocabulary composed of the following
three facts and four rules:
    – F1 = Researcher(a), where a is a constant
      “Individual a is a researcher”
    – F2 = ∃X∃Y (isM ember(a, X) ∧ isP roject(X, kr, Y ) ∧ hasCost(X, 1.5)),
      where a, kr and 1.5 are constants;
      “Individual a is member of a project in the kr area which has a cost of 1.5”
          Datalog+, RuleML and OWL 2: Formats and Translations for Existential Rules          3

     – F3 = Researcher(b) ∧ hasExpertise(b, sw), where b and sw are constants
       “Individual b is a researcher who has expertise in the sw area”
     – R1 = ∀X∀Y ∀Z(isP roject(X, Y, Z) → isM ember(Z, X))
       “Every leader of a project is a member of this project”
     – R2 = ∀X∀Y (Researcher(X)∧ hasExpertise(X, Y ) →
                                              ∃Z∃L (isP roject(Z, Y, L) ∧ isM ember(X, Z)))
       “Every researcher expert in an area is a member of a project in that area”
     – R3 = ∀X∀Y ∀Z(isP roject(X, Y, Z) ∧ isP roject(X, Y, Z 0 ) → Z = Z 0 )
       “Every project has at most one leader”
     – R4 = ∀X(Researcher(X) ∧ P roject(X) → ⊥)
       “Classes Researcher and Project are disjoint”

    R1 is a (plain) Datalog rule since it has no existential variable. R3 is an equality
rule. R4 is a negative constraint. Note that Fact F3 can be decomposed into two atomic
facts, whereas F2 cannot because its atoms are linked by the variable X. Here are two
examples of conjunctive queries on this vocabulary:
     – Q1 = ∃Y ∃Z(Researcher(X) ∧ isM ember(X, Y ) ∧ isP roject(Y, kr, Z))
       “find all researchers members of a project in kr”
     – Q2 = ∃X∃ZisP roject(X, sw, Z)
       “is there a project in the sw area ?”

   The set of answers to Q1 on the knowledge base is {a} (found in F1 ∧ F2 ). The
answer to Q2 is yes (which requires to consider F3 ∧ R2 ).

    In the next sections, we present the dlgp format, then its translation to RuleML, and
finally the translation from OWL 2 to dlgp.


2      The Datalog+ format (dlgp)

The dlgp format is a textual exchange format, meant to be at once human-friendly,
concise and easy to parse. It can be seen as an extension of the commonly used format
for plain Datalog. In particular, rules are of the form head :- body. Note that a
comma is interpreted as a logical ∧, even in a rule head. Quantifiers are omitted since
there is no ambiguity. We remind that variables that occur in the head and not in the
body are existentially quantified.
    In Datalog, variables begin with an uppercase letter, while constants and predicates
begin with a lowercase letter. To make the dlgp format compatible with data from the
Semantic Web, more elaborate kinds of identifiers are mandatory. That is why dlgp
deals with the notions of IRI and literal, as detailed later.
    The following example shows a dlgp encoding of the knowledge from Example 1.
The predicates that begin with an uppercase letter are enclosed in angle brackets (<>).
The directives @facts, @rules, @constraints, @queries are optional indica-
tions for the reader or the parser. 2 Knowledge elements are preceded by an optional
label (enclosed in square brackets).
 2
     These directives allow the parser to be sooner informed of the nature of coming statements.
     However, the parser is free to ignore them.
4         J.-F. Baget, A. Gutierrez, M. Leclère, M.-L. Mugnier, S. Rocher, C. Sipieter

Example 2 (Running example in dlgp).
% this dlgp file encodes Example 1
@facts
[F1] <Researcher>(a).
[F2] isMember(a,X), isProject(X, kr, Y), hasCost(X,1.5).
[F3] <Researcher>(b), hasExpertise(b,sm).
@rules
[R1] isMember(Z,X) :- isProject(X,Y,Z).
[R2] isProject(Z,Y,L), isMember(X,Z) :- <Researcher>(X), hasExpertise(X,Y).
[R3] Z1=Z2 :- isProject(X,Y,Z1), isProject(X,Y,Z2).
@constraints
[R_4] ! :- <Researcher>(X), <Project>(X).
@queries
[Q1] ? (X) :- isMember(X,Y), isProject(Y, kr, Z).
[Q2] ? :- isProject(X,sw,Z).


   Other features of dlgp have been added for compatiblity with Semantic Web lan-
guages:

    – predicates and constants can be denoted by IRIs;
    – constants can be literals;
    – namespaces are introduced;
    – a universal class can be declared (e.g., Thing in OWL 2);
    – whether the Unique Name Assumption is made or not can be specified.

    To implement these features, we rely on Turtle syntax.3 In particular, a predicate
or a constant can be denoted by an IRI in Turtle format, which can be written in three
forms: a relative IRI, an absolute IRI or a prefixed name. Relative and absolute IRIs are
strings of the form <iri> (IRIREF in Turtle grammar). A prefixed name is a string
prefixed by a namespace (PrefixedName in Turtle grammar); moreover, the classical
Datalog notation (a string beginning with a lowercase letter) is allowed and understood
as a relative IRI. A constant can also be a literal (literal in Turtle grammar).
    For instance, here are different ways of writing a predicate:

    – pred (classical Datalog notation);
    – <pred> (a relative IRI, whose base is specified by a directive of the form
      @base <http://example.org>);
    – <http://exemple.org/pred> (an absolute IRI)
    – ex:pred (a prefixed name; the IRI associated with the prefix ex is specified by a
      directive of the form @prefix ex: <http://exemple.org/>

    All these forms can be used to encode a constant. Moreover, constants can be de-
scribed by literals, e.g., -5.1, true, "constant", or any other Turtle literal. Note
that the tokens true and false are interpreted as Boolean literals and not as IRIs.
    The following example shows another dlgp encoding of the knowledge from Exam-
ple 1 using IRIs and namespaces.

Example 3 (Running example in dlgp with IRIs and namespaces).
 3
     http://www.w3.org/TR/turtle/
         Datalog+, RuleML and OWL 2: Formats and Translations for Existential Rules         5

@prefix ex: <http://example.org/> % namespace
@facts
[F1] ex:Researcher(ex:a).
[F2] ex:isMember(ex:a,X), ex:isProject(X, ex:kr, Y), ex:hasCost(X,1.5).
[F3] ex:Researcher(ex:b), ex:hasExpertise(ex:b,ex:sw).
@rules
[R1] ex:isMember(Z,X) :- ex:isProject(X,Y,Z).
[R2] ex:isProject(Z,Y,L), ex:isMember(X,Z) :- ex:Researcher(X),
ex:hasExpertise(X,Y).
[R3] Z1=Z2 :- ex:isProject(X,Y,Z1), ex:isProject(X,Y,Z2).
@constraints
[R_4] ! :- ex:Researcher(X), ex:Project(X).
@queries
[Q1] ? (X) :- ex:isMember(X,Y), ex:isProject(Y, kr, Z).
[Q2] ? :- ex:isProject(X,ex:sw,Z).


      The complete grammar of dlgp is available on Graal website.


3      From dlgp to RuleML

The translation from dlgp to RuleML targets more precisely the Datalog+ fragment of
Deliberation RuleML 1.01. This sublanguage includes:

    – positive facts,
    – universally quantified implications,
    – existentials in the heads of implications,
    – equality,
    – falsity in the heads of implications,
    – conjunctions in the heads of implications.

     The translation from dlgp to this sublanguage is quite direct. Since existential quan-
tification in facts is not allowed in this sublanguage, we translate each existential vari-
able in facts by a new constant 4 , as illustrated in Example 4. This example also illus-
trates the translation of datatypes.

Example 4 (Fact with existential variables and datatypes).
[F2] isMember(a,X), isProject(X, kr, Y), hasCost(X, 1.5).

<Assert>
  <Atom><Rel>isMember</Rel><Ind>a</Ind><Ind>i0</Ind></Atom>
  <Atom><Rel>isProject</Rel><Ind>i0</Ind><Ind>kr</Ind><Ind>i1</Ind></Atom>
  <Atom><Rel>hasCost</Rel><Ind>i0</Ind>
    <Data xsi:type="xs:decimal">1.5</Data></Atom>
</Assert>


    Example 5 illustrates the translation of existential rules. Constraints are translated
in the same manner with an empty disjunction in the head.

Example 5 (Rule with existential variables in the head).
 4
     To preserve the semantics of the knowledge base, the unique name assumption should not be
     made on these new constants.
6       J.-F. Baget, A. Gutierrez, M. Leclère, M.-L. Mugnier, S. Rocher, C. Sipieter

[R2] isProject(Z,Y,L), isMember(X,Z) :- <Researcher>(X), hasExpertise(X,Y).

<Assert><!-- R2 -->
  <Forall><Var>X</Var><Var>Y</Var>
    <Implies><if><And>
      <Atom><Rel>Researcher</Rel><Var>X</Var></Atom>
      <Atom><Rel>hasExpertise</Rel><Var>X</Var><Var>Y</Var></Atom>
    </And></if><then>
      <Exists><Var>L</Var><Var>Z</Var><And>
        <Atom><Rel>isProject</Rel><Var>Z</Var><Var>Y</Var><Var>L</Var></Atom>
        <Atom><Rel>isMember</Rel><Var>X</Var><Var>Z</Var></Atom>
      </And></Exists>
    </then></Implies>
  </Forall>
</Assert>


    Example 6 illustrates the translation of queries.

Example 6 (Query).
[Q1] ? (X) :- isMember(X,Y), isProject(Y, kr, Z).

<Query><!-- Q1 -->
  <Exists><Var>Y</Var><Var>Z</Var><And>
    <Atom><Rel>isMember</Rel><Var>X</Var><Var>Y</Var></Atom>
    <Atom><Rel>isProject</Rel><Var>Y</Var><Ind>kr</Ind><Var>Z</Var></Atom>
  </And></Exists>
</Query>


    Finally, Example 7 shows how IRIs are translated.

Example 7 (Fact with IRI).
@prefix ex: <http://example.com/>
[F1] ex:Researcher(ex:a).

<Assert>
  <Atom>
    <Rel iri="http://example.com/Researcher"/>
    <Ind iri="http://example.com/a"/>
  </Atom>
</Assert>


    The full translation of Example 3 to RuleML is available on Graal website.


4   From OWL 2 to dlgp: the ER profile

We introduce here the ER (for Existential Rule) profile of OWL 2, for which all axioms
can be translated into dlgp statements. We point out that all axioms that can be written
in existing profiles of OWL 2 (namely EL, QL and RL) are axioms of ER.
    For space requirements and the sake of simplicity, we do not discuss here datatypes
nor literals. Axioms used for datatypes and literals always correspond to a similar axiom
used for classes and individuals (for instance DataIntersectionOf corresponds to
ObjectIntersectionOf). They are thus processed similarly in our translation.
          Datalog+, RuleML and OWL 2: Formats and Translations for Existential Rules             7

4.1     Preliminary Notions

Basic objects in an OWL 2 ontology are entities, such as classes, properties and indi-
viduals. These entities are identified by IRIs. We associate an OWL 2 individual i with
the logical constant i, an OWL 2 class C with the unary predicate C, and an OWL 2
property p with the binary predicate p.5
    Entities are used to build expressions, such as class expressions or property ex-
pressions. We present these expressions both in OWL 2 functional notation, such as
ObjetIntersectionOf(A, ObjectComplementOf(B)), and in their DL no-
tation such as A u ¬B; they both identify the class whose elements are in A and
not in B. For every class expression C, we can build a FOL formula ΦC (x) whose
only free variable is x, expressing that “x is an element of the class C”. For instance,
ΦAu¬B (x) = A(x) ∧ ¬B(x). In the same way, for every property expression p, we can
build a FOL formula ΦP (x, y) whose only free variables are x and y, expressing that
“the relation p holds between the subject x and the object y”.
    An OWL 2 ontology is a set of axioms, built from expressions (we do not discuss
here annotations, which have no logical translation). The axiom SubclassOf(A,
B) means that all elements of A are also elements of B. It is written A v B in DL no-
tation. This axiom is translated into a FOL formula (without free variable) ∀x (A(x) →
B(x)). Almost all OWL 2 axioms can be translated into formulas of the form ∀~x(B(~x) →
H(~x)) where B(~x) and H(~x) are FOL formulas whose only free variable is x. These
formulas cannot always be translated into dlgp, as shown in Example 8.

Example 8. The axiom C v A u ¬B is translated by the formula ∀x (C(x) → A(x) ∧
¬B(x). It is equivalent to the conjunction of the two formulas ∀x (C(x) → A(x))
and ∀x (C(x) → ¬B(x)). The first is expressed by the dlgp rule A(X) :- C(X)
and the second by the dlgp constraint ! :- B(X), C(X). In contrast, the axiom
A u ¬B v C cannot be translated into dlgp.

     The ER (for existential rules) profile of OWL 2 is obtained by putting syntactic re-
strictions on OWL 2 expressions and axioms, in order to ensure that all axioms have an
equivalent translation in dlgp. This profile defines different kinds of class expressions,
according to the position they can fill in a formula of the form ∀~x(B(~x) → H(~x)).
EquivClass expressions can appear in both sides of such an implication, as will be dis-
cussed in Sect. 4.2. SubClass expressions can only appear in the left side (Sect. 4.3),
while SuperClass expressions can only appear in the right side (Sect. 4.4). We show in
Sect. 4.5 that any OWL 2 axiom can either be easily translated into dlgp or is equivalent
to a formula of the form ∀~x(B(~x) → H(~x)), that can be translated when it complies
with the restrictions of the ER profile.
 5
     We already discuss here the particular case of two specific classes, Thing and Nothing
     (respectively written > and ⊥ in DL). Thing is the universal class that contains everything
     and Nothing is the empty class. They are used as any other class in our framework, though
     their particular semantics is expressed in dlgp by the two following dlgp statements that must
     be present in every dlgp knowledge base translating an OWL 2 ontology: the dlgp constraint
     ! :- Nothing(X); and the dlgp annotation @top Thing that declares that the universal
     class in the knowledge base is named Thing.
8          J.-F. Baget, A. Gutierrez, M. Leclère, M.-L. Mugnier, S. Rocher, C. Sipieter

    In this paper, all axioms and expression constructors will be presented according to
the format given in Tab. 1.

                                      Type of axiom or expression
Name of axiom or expression
Axiom or expression in OWL 2 functional syntax DL syntax Logical translation
Optional comments.

                               Table 1. General format of tables




4.2     EquivClass expressions
A FOL formula F(~x) is said to be conjunctive when it is in the form ∃~z (C1 [~x, ~z] ∧
. . . ∧ Cp [~x, ~z]) where the Ci [~x, ~z] are (positive) atoms whose variables are in ~x ∪ ~z.6
Property 1. For every property expression p, Φp (x, y) is a conjunctive formula. See
Tab. 2.
    In the ER profile, an EquivClass expression is a class expression built, without any
other restriction, from the constructors listed in Tab. 3.
Property 2. For every EquivClass expression C, ΦC (x) is equivalent to a conjunctive
formula.
      The following property is the basis of our transformation from OWL 2 to dlgp.
Property 3. Every formula of the form ∀~x(B(~x) → H(~x)) where B(~x) and H(~x) are
conjunctive can be translated into an equivalent dlgp rule.
Example 9. The class expression ∃p·(∃q ·C) is translated into FOL by Φ∃p·(∃q·C) (x) =
∃y1 (p(x, y1 ) ∧ (∃y2 (q(y1 , y2 ) ∧ C(y2 )))). By putting it in prenex form, we obtain the
conjunctive formula ∃y1 ∃y2 (p(x, y1 )∧q(y1 , y2 )∧C(y2 )). Thus the axiom D v ∃p·(∃q·
C) is translated by the dlgp rule: p(X, Y1), q(Y1, Y2), C(Y2) :- D(X).
    As a final remark on the translation of implications of conjunctive formulas, we
point out that formulas of the form ∀x(B(x) → Thing(x)) or ∀x(Nothing(x) →
H(x)) do not bring any information, thus do not need to be translated; that formulas of
the form ∀x(B(x) → Nothing(x)) can be directly translated into a dlgp constraint;
and that formulas of the form ∀x(x = a → B(x)) can be directly translated into a dlgp
fact.
Example 10. The axiom A v ∃p · ⊥ is translated by the FOL formula ∀x(A(x) →
(∃y(p(x, y) ∧ Nothing(y)))), which can be simplified in ∀x(A(x) → Nothing(x)),
and thus can be expressed by the dlgp constraint ! :- A(X)
   The axiom {a} v ∃p · C is translated by the FOL formula ∀x ((x = a) →
∃y(p(x, y) ∧ C(y)) and thus can be expressed by the dlgp fact: p(a, Y), C(Y).
 6
     Moreover, we always simplify such a conjunctive formula: it is equivalent to Nothing(x) if
     one of its atoms is some Nothing(y), and we can remove all atoms of the form Thing(y)
     without changing the semantics (unless the formula is restricted to a single atom Thing(x)).
          Datalog+, RuleML and OWL 2: Formats and Translations for Existential Rules                            9

                                          Object Property Expressions
Object Property
p                                        p             p(x, y)
Inverse Object Property
ObjectInverseOf(p)                       p−            p(y, x)
                                              Property Expression Chain
ObjectPropertyChain(p1 , . . . , pk ) p1 · . . . · pk ∃z1 . . . ∃zk−1 (Φp1 (x, z1 ) ∧ . . . ∧ Φpk (zk−1 , y))
Note that the arguments of a property expression chain are always object property expressions.

                             Table 2. Property expressions in OWL 2.


                                              EquivClass expressions
Class
C                                           C          C(x)
Intersection of Class Expressions
ObjectIntersectionOf(C1 , . . . , Ck ) C1 u . . . u Ck ΦC1 (x) ∧ . . . ∧ ΦCk (x)
Existential Quantification
ObjectSomeValuesFrom(p, C)                  ∃p · C     ∃y (Φp (x, y) ∧ ΦC (y))
Individual Value Restriction
ObjectHasValue(p, i)                        ∃p · {i}   Φp (x, i)
Self-Restriction
ObjectHasSelf(p)                            ∃p · Self  Φp (x, x)
Minimum Cardinality - Restricted to n = 0 or 1
ObjectMinCardinality(0, p, C)               ≥ 0pC      Thing(x)
ObjectMinCardinality(1, p, C)               ≥ 1pC      ∃y (Φp (x, y) ∧ ΦC (y))
Enumeration of Individuals - Restricted to n = 1
ObjectOneOf(i)                              {i}        x=i

                          Table 3. EquivClass expressions constructors



4.3     SubClass expressions

A FOL formula F(~x) is said to be disjunctive when it is a disjunction F1 (~x) ∨ . . . ∨
Fk (~x) of conjunctive formulas. In that case, we say that the disjunction is of size k.7
    In the ER profile, a SubClass expression is a class expression built, without any
other restriction, from the constructors listed in Tab. 4.

Property 4. If C is a SubClass expression, ΦC (x) is equivalent to a disjunctive formula.

Example 11. The SubClass expression (A t B) u ∃p · (A t B) is translated by the FOL
formula (A(x)∨B(x))∧∃y(p(x, y)∧(A(y)∨B(y))). It is equivalent to the disjunctive
formula FAA (x)∨FAB (x)∨FBA (x)∨FBB (x) where FAA (x) = ∃y(A(x)∧p(x, y)∧
A(y)), FAB (x) = ∃y(A(x) ∧ p(x, y) ∧ B(y)), FBA (x) = ∃y(B(x) ∧ p(x, y) ∧ A(y))
and FBB (x) = ∃y(B(x) ∧ p(x, y) ∧ B(y)).

   Note that putting the formula translating a SubClass expression into its disjunctive
form can be exponential in the size of the initial formula.
 7
     We always simplify a disjunctive formula: it is equivalent to Thing(x) if one of its conjunctive
     formulas is Thing(x), and we can remove all conjunctive formulas of the form Nothing(x)
     without changing the semantics (unless the formula is restricted to a single conjunctive formula
     Nothing(x)).
10        J.-F. Baget, A. Gutierrez, M. Leclère, M.-L. Mugnier, S. Rocher, C. Sipieter

                                            EquivClass expressions
All EquivClass expressions constructors: Atomic class expressions (including Thing and Nothing),
ObjectIntersectionOf, ObjectSomeValuesFrom, ObjectHasValue, ObjectHasSelf,
ObjectMinCardinality (restricted to n = 0 or 1), ObjectOneOf (restricted to n = 1).
                                             SubClass expressions
Union of class expressions
ObjectUnionOf(C1 , . . . , Ck ) C1 t . . . t Ck ΦC1 (x) ∨ . . . ∨ ΦCk (x)
Enumeration of individuals (unrestricted)
ObjectOneOf(i1 , . . . , ik )    {i1 , . . . , ik } x = i1 ∨ . . . ∨ x = ik

                           Table 4. SubClass expressions constructors.



Property 5. Every formula of the form ∀~x(B(~x) → H(~x)), where B(~x) is a disjunctive
formula of size k and H(~x) is a conjunctive formula, can be translated into an equivalent
conjunction of k dlgp rules.

Example 12. The axiom (A t B) u ∃p · (A t B) v ∃q · > is translated by the
four following dlgp rules: q(X, Z) :- A(X), p(X, Y), A(Y) and q(X, Z)
:- A(X), p(X, Y), B(Y) and q(X, Z):- B(X), p(X, Y), A(Y) and
q(X, Z) :- B(X), p(X, Y), B(Y).


4.4   SuperClass expressions

Contrary to what happens with EquivClass and SubClass expressions, all OWL 2 con-
structors can appear in ER SuperClass expressions. Hence, these expressions can also
use, in addition to the constructors already presented, the constructors listed in Tab. 5.
However, we impose syntactic restrictions on the possible interactions between these
constructors.

Definition 1. SuperClass expressions are defined inductively. A SuperClass expression
is either an EquivClass expression; the intersection C1 u . . . u Ck of SuperClass ex-
pressions Ci ; the complement ¬C of a SubClass expression C; the universal restriction
∀p·C of a SuperClass expression C; or the maximum cardinality ≤ n p C of a SubClass
expression C, when n is restricted to 0 or 1.


Property 6. A formula ∀x (ΦB (x) → ΦH (x)), where B is a SubClass expression and
H is a SuperClass expression, is equivalent to a conjunction of formulas of the form
∀x (B(x) → H(x)), where B(x) is disjunctive and H(x) is conjunctive.

Proof. We show the property inductively on the SuperClass expression H.
    If H is an EquivClass expression, then the property is immediate.
    If H = H1 u . . . u Hk , then our formula is equivalent to the conjunction of formulas
∀x (ΦB (x) → ΦHi (x)), where the Hi are SuperClass expressions.
    If H = ¬H 0 , then our formula is equivalent to ∀x (ΦB (x) ∧ ΦH 0 (x) →
Nothing(x)). Since both B and H 0 are SubClass expressions, the conjunction of
ΦB (x) and ΦH 0 (x) is equivalent to a disjunctive formula.
         Datalog+, RuleML and OWL 2: Formats and Translations for Existential Rules                                11

Complement of Class Expressions
ObjectComplementOf(C)                         ¬C      ¬ΦC (x)
Is a SuperClass expression when C is a SubClass expression
Universal Quantification
ObjectAllValuesFrom(p, C)                     ∀p · C ∀y (Φp (x, y) → ΦC (y)
Is a SuperClass expression when C is a SuperClass expression
Maximum Cardinality
ObjectMaxCardinality(n, p, C)                 ≤ npC ∀y1 . . . ∀yn+1 ((Φp (x, y1 ) ∧ ΦC (y1 ) ∧ . . . ∧ Φp (x, yn+1 ) ∧
                                                      ΦC (yn+1 )) → ∨1≤i<j≤n+1 yi = yj ))
Only used when n is restricted to 0 or 1, is a SuperClass expression when C is a SubClass expression.
Exact Cardinality
ObjectExactCardinality(n, p, C) = npC Macro                          for        ObjectMinCardinality              and
                                                      ObjectMaxCardinality.

                Table 5. List of all other (non datatype) OWL 2 constructors.



     If H = ∀p · H 0 , then our formula is equivalent to ∀y (∃x (ΦB (x) ∧ Φp (x, y)) →
ΦH 0 (y)). Since ΦB (x) is disjunctive, its conjunction with ∃y p(x, y) can also be put in
disjunctive form, and ΦH 0 (y) is a SuperClass expression.
     If H =≤ 0 p H 0 , then our formula is equivalent to ∀x (∃y (ΦB (x) ∧ Φp (x, y) ∧
ΦH (y)) → Nothing(x)). Since both B and H 0 are SubClass expressions, the formula
    0

∃y (ΦB (x) ∧ Φp (x, y) ∧ ΦH 0 (y)) is equivalent to a disjunctive formula.
     If H =≤ 1 p H 0 , then our formula is equivalent to ∀x (∃y1 ∃y2 (ΦB (x)∧Φp (x, y1 )∧
ΦH 0 (y1 ) ∧ Φp (x, y2 ) ∧ ΦH 0 (y2 )) → y1 = y2 ). Since both B and H 0 are SubClass
expressions, the formula ∃y1 ∃y2 (ΦB (x) ∧ Φp (x, y1 ) ∧ ΦH 0 (y1 ) ∧ Φp (x, y2 ) ∧ ΦH 0 (y2 ))
is equivalent to a disjunctive formula.

Example 13. Let {a} t ∃p · A v (∃q · B) u (¬C) u (∀r · D) be an axiom. Its associated
formula is ∀x ((x = a ∨ ∃y1 (p(x, y1 ) ∧ A(y1 ))) → (∃y2 (q(x, y2 ) ∧ B(y2 )) ∧ ¬C(x) ∧
∀y3 (r(x, y3 ) → D(y3 )))). It is equivalent to the conjunction of the three formulas F1 =
∀x ((x = a ∨ ∃y1 (p(x, y1 ) ∧ A(y1 ))) → ∃y2 (q(x, y2 ) ∧ B(y2 ))), F2 = ∀x ((x = a ∨
∃y1 (p(x, y1 ) ∧ A(y1 ))) → ¬C(x)) and F3 = ∀x ((x = a ∨ ∃y1 (p(x, y1 ) ∧ A(y1 ))) →
∀y3 (r(x, y3 ) → D(y3 ))).
    The formula F1 is translated into the two dlgp statements q(a, Y2), B(Y2).
and q(X, Y2), B(Y2) :- p(X, Y1), A(Y1).
    The formula F2 is equivalent to ∀x ((C(x) ∧ (x = a ∨ ∃y1 (p(x, y1 ) ∧ A(y1 )))) →
Nothing(x)). By putting the left side of the implication in disjunctive form, we ob-
tain ∀x (((C(x) ∧ x = a) ∨ ∃y1 (p(x, y1 ) ∧ A(y1 ) ∧ C(x))) → Nothing(x)), that
can be translated in the two dlgp constraints ! :- C(a). and ! :- p(X, Y1),
A(Y1), C(X).
    Finally, the formula F3 is equivalent to ∀y3 ((∃x (r(x, y3 ) ∧ x = a)) ∨ (∃x∃y1
(p(x, y1 ) ∧ A(y1 ) ∧ r(x, y3 ))) → D(y3 )) and can thus be translated into the two dlgp
rules D(Y3) :- r(a, Y3). and D(Y3):-p(X, Y1), A(Y1), r(X, Y3).


4.5    Axioms

We have seen that we can translate into dlgp any formula of the form ∀~x(B(~x) →
H(~x)), when B(~x) is a disjunctive formula, and H(~x) a conjunctive formula.
12         J.-F. Baget, A. Gutierrez, M. Leclère, M.-L. Mugnier, S. Rocher, C. Sipieter

                                               Object Property Axioms
Object Subproperties
SubObjectPropertyOf(p, q)                            pvq          ∀x∀y (Φp (x, y) → Φq (x, y))
Equivalent Object Properties
EquivalentObjectProperties(p, q)                     p≡q          ∀x∀y (Φp (x, y) ↔ Φq (x, y))
Equivalent to the conjunction of ∀x∀y (Φp (x, y) → Φq (x, y)) and ∀x∀y (Φq (x, y) → Φp (x, y))
Disjoint Object Properties
DisjointObjectProperties(p, q)                       p v ¬q       ∀x∀y((Φp (x, y)∧Φq (x, y)) → Nothing(x)
Inverse Object Properties
InverseObjectProperties(p, q)                        p ≡ q−       ∀x∀y (Φp (x, y) ↔ Φq (y, x))
Equivalent to the conjunction of ∀x∀y (Φp (x, y) → Φq (y, x)) and ∀x∀y (Φq (x, y) → Φp (y, x))
Functional Object Properties
FunctionalObjectProperty(p)                                       ∀x∀y∀z (Φp (x, y) ∧ Φp (x, z) → y = z)
Equivalent to ∀y∀z (∃x(Φp (x, y) ∧ Φp (x, z)) → y = z)
Inverse-Functional Object Properties
InverseFunctionalObjectProperty(p)                                ∀x∀y∀z (Φp (y, x) ∧ Φp (z, x) → y = z)
Equivalent to ∀y∀z (∃x(Φp (y, x) ∧ Φp (z, x)) → y = z)
Reflexive Object Properties
ReflexiveObjectProperty(p)                                        ∀x (Thing(x) → Φp (x, x))
Irreflexive Object Properties
IrreflexiveObjectProperty(p)                                      ∀x (Φp (x, x) → Nothing(x))
Symmetric Object Properties
SymmetricObjectProperty(p)                                        ∀x∀y (Φp (x, y) → Φp (y, x))
Asymmetric Object Properties
AsymmetricObjectProperty(p)                                       ∀x∀y((Φp (x, y)∧Φp (y, x) → Nothing(x))
Transitive Object Properties
TransitiveObjectProperty(p)                                       ∀x∀y∀z (Φp (x, y) ∧ Φp (y, z) → Φp (x, z))
                                                      Assertions
Individual Equality
SameIndividual(i1 , i2 )                                   i1 = i2     i1 = i2
Translated by the dlgp fact i1 = i2
Individual Inequality
DifferentIndividuals(i1 , i2 )                             i1 6= i2    ¬i1 = i2
Translated by the dlgp constraint ! :- i1 = i2
Positive Object Property Assertions
ObjectPropertyAssertion(i1 , p, i2 )                       p(i1 , i2 ) Φp (i1 , i2 )
Translated by the dlgp fact obtained by replacing x by i1 and y by i2 in Φp (x, y)
Negative Object Property Assertions
NegativeObjectPropertyAssertion(i1 , p, i2 ) ¬p(i1 , i2 ) ¬Φp (i1 , i2 )
Translated by the dlgp constraint ! :- Φp (i1 , i2 ) as described above.

                 Table 6. OWL 2 axioms that do not require class expressions



    In Tab. 6, we show that, since the formula associated with a property expression is
conjunctive, all OWL 2 axioms that do not require class expressions can be put in such
a form. Hence, the following property:
Property 7. OWL 2 axioms with no class expression can be translated into dlgp.
    On the other hand, an OWL 2 axiom that requires class expressions may not be
translatable in dlgp. This is why we impose restrictions on all these axioms in the
OWL 2 ER profile: EquivalentClasses is restricted to EquivClass expressions;
DisjointClasses and HasKey are restricted to SubClass expressions;
ObjectPropertyDomain, ObjectPropertyRange, and ClassAssertion
are restricted to SuperClass expressions; the first argument of SubClassOf must be a
SubClass expression and its second argument must be a SuperClass expression. Finally,
DisjointUnion does not belong to the ER profile.
         Datalog+, RuleML and OWL 2: Formats and Translations for Existential Rules                   13

   Assuming these restrictions as displayed in Tab. 7, we conclude with the following
property:
Property 8. All OWL 2 axioms in the ER profile can be translated into dlgp.


                                                 Class Axioms
Subclass axioms
SubClassOf(C1 , C2 )                   C1 v C2 ∀x (ΦC1 (x) → ΦC2 (x))
C1 must be a Subclass expression and C2 must be a SuperClass expression
Equivalent Classes
EquivalentClasses(C1 , C2 )            C1 ≡ C2 ∀x (ΦC1 (x) ↔ ΦC2 (x))
Translated by the conjunction of ∀x (ΦC1 (x) → ΦC2 (x)) and ∀x (ΦC2 (x) → ΦC1 (x)).
Both C1 and C2 must be EquivClass expressions.
Disjoint Classes
DisjointClasses(C1 , C2 )              C1 v C2 ∀x ((ΦC1 (x) ∧ ΦC2 (x)) → Nothing(x)
Both C1 and C2 must be SubClass expressions.
Disjoint Union of Class Expressions
DisjointUnion(C, C1 , . . . , Ck )                  ∀x (ΦC (x) ↔ (∨1≤i≤k ΦCi (x)))
                                                    ∧1≤i<j≤k ¬(∃x (ΦCi (x) ∧ ΦCj (x)))
Cannot be translated into dlgp, even when restricted to (atomic) classes.
                                            Object Property Axioms
Object Property Domain
ObjectPropertyDomain(p, C)                     ∀x∀y (Φp (x, y) → ΦC (x))
C must be a SuperClass expression.
Object Property Range
ObjectPropertyRange(p, C)                      ∀x∀y (Φp (y, x) → ΦC (x))
C must be a SuperClass expression.
                                                   Assertions
Class Assertions
ClassAssertion(C, i)                 C(i)     ΦC (i)
Equivalent to the formula ∀x (x = i → ΦC (x)). C must be a SuperClass expression.
                                                     Keys
HasKey
HasKey(C, p1 , . . . , pk )                    ∀x∀y∀z1 . . . ∀zk ((ΦC (x) ∧ ΦC (y) ∧1≤i≤k (Φpi (x, zi ) ∧
                                               Φpi (y, zi ))) → x = y)
C must be a SubClass expression.

                      Table 7. OWL 2 axioms that require class expressions



   Finally, we point out that the profiles of OWL 2 (namely EL, QL and RL) are frag-
ments of OWL2 ER.
Property 9. All OWL 2 axioms that are either EL, QL or RL axioms are also ER ax-
ioms.

4.6    Implementation of the translator
When the OWL 2 input belongs to the ER fragment, our tool ensures that it will be
translated into a set of existential rules having the same models. We detail here the
behavior of our tool when the input does not necessarily belong to the ER fragment.
    Each axiom (and assertion) that does not require class expressions (see Tab. 6)
is translated into one or two (in the case of EquivalentObjectProperty or
14      J.-F. Baget, A. Gutierrez, M. Leclère, M.-L. Mugnier, S. Rocher, C. Sipieter

InverseObjectProperty) dlgp rules or constraints. Such axioms always belong
to the ER fragment.
    Each axiom (and assertion) that requires class expressions (except Disjoint-
Union, that we never handle, for which a warning is issued) is translated into one or
two (in the case of EquivalentClasses) class inclusions, as described in Tab. 7.
For instance, A ≡ B generates the two class inclusions A v B and B v A; (∃R.C)(a)
generates the class inclusion {a} v ∃R.C.
    Each class inclusion A v B thus generated will then be independently analysed.
The first step is to rewrite that inclusion in the form A v E u R1 u . . . u Rk where
E, if present, is an EquivClass expression and the rests Ri , if present, are neither
EquivClass expressions nor an ObjectIntersectionOf. The initial class inclu-
sion is thus equivalent to the k + 1 class inclusions A v E and, for 1 ≤ i ≤ k,
A v Ri . We try now to rewrite each inclusion A v Ri . This can be done when
Ri is an ObjectComplementOf, ObjectAllValuesFrom, or ObjectMax-
Cardinality (0 or 1), and we can replace the inclusion A v Ri by an inclusion
A0 v Ri0 as in the proof of Prop. 6. Otherwise that particular class inclusion is not
translated and a warning is issued. The whole process is repeated on the inclusion ob-
                    (n)
tained, until the Ri obtained is an EquivClass expression or a warning is issued.
Example 14. Let us consider the class inclusion A v (BtC)u(∀r.D). Neither (BtC)
nor (∀r.D) are EquivClass expressions, so we generate the two class inclusions A v
B t C and A v ∀r.D. We have no possibility to rewrite the first one, so a warning is
issued. The second is rewritten into ∃r− .A v D. Since D is an EquivClass expression,
that class inclusion is kept and the analysis halts.
    After this first step, the only remaining class inclusions are of form A v B where B
is an EquivClass expression. Their left side are first put into disjunctive normal form to
obtain an equivalent inclusion A1 t. . .tAp v B where no Ai is an ObjectUnionOf.
For each Ai being an EquivClass expression, we generate a dlgp expression translating
Ai v B, otherwise a warning is issued.
Example 15. Let us consider the class inclusion A t ¬B v ∀r.(C u ¬B) u ¬(C t
D) u ∃r.(B t C). It does not belong to the ER fragment since its left side is not a
SubClass expression and its right side is not a SuperClass expression. It is equivalently
rewritten into (1) A t ¬B v ∀r.(C u ¬B), (2) A t ¬B v ¬(C t D), and (3) A t ¬B v
∃r.(B t C). (1) is equivalently rewritten into (1.0) ∃r− .(A t ¬B) v C u ¬B and (2)
into (2.0) (A t ¬B) u (C t D) v ⊥. Since the right side of (3) is not an EquivClass
expression and we don’t know how to rewrite it, a warning is issued and that inclusion
is not translated. The inclusion (1.0) is equivalently rewritten into (1.0.1) ∃r− .(A t
¬B) v C and (1.0.2) ∃r− .(A t ¬B) v ¬B. The inclusion (1.0.2) is equivalently
rewritten into (1.0.2.0) B u ∃r− .(A t ¬B) v ⊥. Our initial inclusion is thus equivalent
to the inclusions (1.0.1), (1.0.2.0), (2.0) and (3). (3) has been rejected and a warning
has been issued, and the right side of the other inclusions are EquivClass expressions.
    We now put the left sides of (1.0.1), (1.0.2.0), and (2.0) in disjunctive normal form,
obtaining the inclusions (1.0.1.0) ∃r− .A t ∃r− .(¬B) v C, (1.0.2.0.0) (B u ∃r− .A) t
(B u ∃r− .(¬B)) v ⊥ and (2.0.0) (A u C) t (A u D) t (¬B u C) t (¬B u D) v ⊥.
By “splitting” the disjunctions, we obtain the class inclusions (1.0.1.0.1) ∃r− .A v
       Datalog+, RuleML and OWL 2: Formats and Translations for Existential Rules            15

C, (1.0.1.0.2) ∃r− .(¬B) v C, (1.0.2.0.0.1) B u ∃r− .A v ⊥, (1.0.2.0.0.2) B u
∃r− .(¬B) v ⊥, (2.0.0.1) A u C v ⊥, (2.0.0.2) A u D v ⊥, (2.0.0.3) ¬B u C v ⊥
and (2.0.0.4) ¬B u D v ⊥. The left side of axioms (1.0.1.0.2), (1.0.2.0.0.2), (2.0.0.3)
and (2.0.0.4) are not EquivClass expressions, so they cannot be translated and four
warnings are issued. The other axioms are translated into dlgp.
(1.0.1.0.1) C(X) :- r(Y, X), A(Y)
(1.0.2.0.0.1) ! :- B(X), r(Y, X), A(X)
(2.0.0.1) ! :- A(X), C(X)
(2.0.0.2) ! :- A(X), D(X)
    The initial class inclusion (that does not belong to ER) has been translated into nine
class inclusions, from which four could be translated into dlgp. Five warnings have been
issued.

    When the input belongs to the OWL 2 ER fragment, no warning can be issued and
the models of the OWL 2 ontology and the models of its dlgp translation are the same.
However, even when a warning is issued, our algorithm ensures that all models of the
OWL 2 ontology are models of the dlgp translation.


5   Conclusion

In this paper, we presented the main aspects of the dlgp format dedicated to the frame-
work of existential rules, the translation from dlgp to the Datalog+ fragment of RuleML
and the OWL 2 ER profile, which allows to translate the “Datalog+” part of an OWL
2 ontology (as precisely explained in the preceding section). The associated software
tools and documentation can be found on Graal website. Future improvements will be
made available on the same website.


References
BLM+ 15. J.-F. Baget, M. Leclère, M.-L. Mugnier, S. Rocher, and C. Sipieter. Graal: A Toolkit
         for Query Answering with Existential Rules. In RuleML, to appear, 2015.
BLMS09. J.-F. Baget, M. Leclère, M.-L. Mugnier, and E. Salvat. Extending decidable cases for
         rules with existential variables. In IJCAI’09, pages 677–682, 2009.
BLMS11. J.-F. Baget, M. Leclère, M.-L. Mugnier, and E. Salvat. On rules with existential
         variables: Walking the decidability line. Artificial Intelligence, 175(9-10):1620–1654,
         2011.
CGK08. A. Calı̀, G. Gottlob, and M. Kifer. Taming the infinite chase: Query answering under
         expressive relational constraints. In KR’08, pages 70–80, 2008.
CGL09. A. Calı̀, G. Gottlob, and T. Lukasiewicz. A general datalog-based framework for
         tractable query answering over ontologies. In PODS’09, pages 77–86, 2009.
CGP12. A. Calı̀, G. Gottlob, and A. Pieris. Towards more expressive ontology languages: The
         query answering problem. Artif. Intell., 193:87–128, 2012.
KR11.    M. Krötzsch and S. Rudolph. Extending decidable existential rules by joining acyclic-
         ity and guardedness. In IJCAI’11, pages 963–968, 2011.

</pre>