This paper is devoted to formats and translations for Datalog+. We first introduce the dlgp format, which extends classical Datalog format to Datalog+. 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+ fragment 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.
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 8X 8Y (B[X; Y ] ! 9Z H[X; Z]), where X , Y and Z are sets of variables, B (the body) is a conjunction 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 9X F [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 :9X C[X ]; equivalently, it can be seen as a rule with a head restricted to the always-false symbol ?: 8X (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 8X 8Y (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, isProject/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 researcher 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 = 9X9Y (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” – 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 = 8X8Y 8Z(isP roject(X; Y; Z) ! isM ember(Z; X))
“Every leader of a project is a member of this project” – R2 = 8X8Y (Researcher(X)^ hasExpertise(X; Y ) !
9Z9L (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 = 8X8Y 8Z(isP roject(X; Y; Z) ^ isP roject(X; Y; Z0) ! Z = Z0) “Every project has at most one leader” – R4 = 8X(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 = 9Y 9Z(Researcher(X) ^ isM ember(X; Y ) ^ isP roject(Y; kr; Z)) “find all researchers members of a project in kr” – Q2 = 9X9ZisP roject(X; sw; Z) “is there a project in the sw area ?”
The set of answers to Q1 on the knowledge base is fag (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 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 indications 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. 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 languages: – 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 described 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 Example 1 using IRIs and namespaces.
Example 3 (Running example in dlgp with IRIs and namespaces). 3 http://www.w3.org/TR/turtle/ @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.
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 quantification in facts is not allowed in this sublanguage, we translate each existential variable in facts by a new constant 4 , as illustrated in Example 4. This example also illustrates 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. [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 (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>
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.
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.
Basic objects in an OWL 2 ontology are entities, such as classes, properties and individuals. 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 expressions. We present these expressions both in OWL 2 functional notation, such as ObjetIntersectionOf(A, ObjectComplementOf(B)), and in their DL notation 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 notation. This axiom is translated into a FOL formula (without free variable) 8x (A(x) ! B(x)). Almost all OWL 2 axioms can be translated into formulas of the form 8~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 8x (C(x) ! A(x) ^ :B(x). It is equivalent to the conjunction of the two formulas 8x (C(x) ! A(x)) and 8x (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 restrictions 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 8~x(B(~x) ! H(~x)). EquivClass expressions can appear in both sides of such an implication, as will be discussed 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 8~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.
In this paper, all axioms and expression constructors will be presented according to the format given in Tab. 1.
Name of axiom or expression Axiom or expression in OWL 2 functional syntax DL syntax Logical translation Optional comments.
Type of axiom or expression A FOL formula F (~x) is said to be conjunctive when it is in the form 9~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 8~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 9p (9q C) is translated into FOL by 9p (9q C)(x) = 9y1(p(x; y1) ^ (9y2(q(y1; y2) ^ C(y2)))). By putting it in prenex form, we obtain the conjunctive formula 9y19y2(p(x; y1)^q(y1; y2)^C(y2)). Thus the axiom D v 9p (9q 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 8x(B(x) ! Thing(x)) or 8x(Nothing(x) ! H(x)) do not bring any information, thus do not need to be translated; that formulas of the form 8x(B(x) ! Nothing(x)) can be directly translated into a dlgp constraint; and that formulas of the form 8x(x = a ! B(x)) can be directly translated into a dlgp fact.
Example 10. The axiom A v 9p ? is translated by the FOL formula 8x(A(x) ! (9y(p(x; y) ^ Nothing(y)))), which can be simplified in 8x(A(x) ! Nothing(x)), and thus can be expressed by the dlgp constraint ! :- A(X)
The axiom fag v 9p C is translated by the FOL formula 8x ((x = a) ! 9y(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)). Object Property p Inverse Object Property ObjectInverseOf(p)
Object Property Expressions p p p(x; y) p(y; x)
Property Expression Chain ObjectPropertyChain(p1; : : : ; pk) p1 : : : pk 9z1 : : : 9zk 1( p1 (x; z1) ^ : : : ^ pk (zk 1; y)) Note that the arguments of a property expression chain are always object property 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. and FBB(x) = 9y(B(x) ^ p(x; y) ^ B(y)).
Example 11. The SubClass expression (A t B) u 9p (A t B) is translated by the FOL formula (A(x) _ B(x)) ^ 9y(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) = 9y(A(x)^p(x; y)^ A(y)), FAB(x) = 9y(A(x) ^ p(x; y) ^ B(y)), FBA(x) = 9y(B(x) ^ p(x; y) ^ A(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)).
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) fi1; : : : ; ikg x = i1 _ : : : _ x = ik
Property 5. Every formula of the form 8~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 9p (A t B) v 9q > 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
Contrary to what happens with EquivClass and SubClass expressions, all OWL 2 constructors 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 expressions Ci; the complement :C of a SubClass expression C; the universal restriction 8p 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 8x ( 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 8x (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 8x ( B(x) ! Hi (x)), where the Hi are SuperClass expressions.
If H = :H0, then our formula is equivalent to 8x ( B(x) ^ H0 (x) ! Nothing(x)). Since both B and H0 are SubClass expressions, the conjunction of B(x) and H0 (x) is equivalent to a disjunctive formula. Complement of Class Expressions ObjectComplementOf(C) :C : C(x) Is a SuperClass expression when C is a SubClass expression Universal Quantification ObjectAllValuesFrom(p; C) 8p C 8y ( p(x; y) ! C(y) Is a SuperClass expression when C is a SuperClass expression Maximum Cardinality ObjectMaxCardinality(n; p; C) npC 8y1 : : : 8yn+1(( p(x; y1) ^ C(y1) ^ : : : ^ p(x; yn+1) ^
C(yn+1)) ! _1 i<j n+1yi = 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.
If H = 8p H0, then our formula is equivalent to 8y (9x ( B(x) ^ p(x; y)) ! H0 (y)). Since B(x) is disjunctive, its conjunction with 9y p(x; y) can also be put in disjunctive form, and H0 (y) is a SuperClass expression.
If H = 0 p H0, then our formula is equivalent to 8x (9y ( B(x) ^ p(x; y) ^ H0 (y)) ! Nothing(x)). Since both B and H0 are SubClass expressions, the formula 9y ( B(x) ^ p(x; y) ^ H0 (y)) is equivalent to a disjunctive formula.
If H = 1 p H0, then our formula is equivalent to 8x (9y19y2 ( B(x)^ p(x; y1)^ H0 (y1) ^ p(x; y2) ^ H0 (y2)) ! y1 = y2). Since both B and H0 are SubClass expressions, the formula 9y19y2 ( B(x) ^ p(x; y1) ^ H0 (y1) ^ p(x; y2) ^ H0 (y2)) is equivalent to a disjunctive formula.
Example 13. Let fag t 9p A v (9q B) u (:C) u (8r D) be an axiom. Its associated formula is 8x ((x = a _ 9y1(p(x; y1) ^ A(y1))) ! (9y2(q(x; y2) ^ B(y2)) ^ :C(x) ^ 8y3(r(x; y3) ! D(y3)))). It is equivalent to the conjunction of the three formulas F1 = 8x ((x = a _ 9y1(p(x; y1) ^ A(y1))) ! 9y2(q(x; y2) ^ B(y2))), F2 = 8x ((x = a _ 9y1(p(x; y1) ^ A(y1))) ! :C(x)) and F3 = 8x ((x = a _ 9y1(p(x; y1) ^ A(y1))) ! 8y3(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 8x ((C(x) ^ (x = a _ 9y1(p(x; y1) ^ A(y1)))) ! Nothing(x)). By putting the left side of the implication in disjunctive form, we obtain 8x (((C(x) ^ x = a) _ 9y1(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 8y3 ((9x (r(x; y3) ^ x = a)) _ (9x9y1 (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
We have seen that we can translate into dlgp any formula of the form 8~x(B(~x) ! H(~x)), when B(~x) is a disjunctive formula, and H(~x) a conjunctive formula.
Object Property Axioms Object Subproperties SubObjectPropertyOf(p; q) p v q 8x8y ( p(x; y) ! q(x; y)) Equivalent Object Properties EquivalentObjectProperties(p; q) p q 8x8y ( p(x; y) $ q(x; y)) Equivalent to the conjunction of 8x8y ( p(x; y) ! q(x; y)) and 8x8y ( q(x; y) ! p(x; y)) Disjoint Object Properties DisjointObjectProperties(p; q) p v :q Inverse Object Properties
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.
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 8x ( C1 (x) ! C2 (x)) C1 must be a Subclass expression and C2 must be a SuperClass expression Equivalent Classes EquivalentClasses(C1; C2) C1 C2 8x ( C1 (x) $ C2 (x)) Translated by the conjunction of 8x ( C1 (x) ! C2 (x)) and 8x ( C2 (x) ! C1 (x)).
Both C1 and C2 must be EquivClass expressions.
Disjoint Classes DisjointClasses(C1; C2) C1 v C2 8x (( C1 (x) ^ C2 (x)) ! Nothing(x) Both C1 and C2 must be SubClass expressions.
Disjoint Union of Class Expressions DisjointUnion(C; C1; : : : ; Ck) 8x ( C (x) $ (_1 i k Ci (x))) ^1 i<j k:(9x ( Ci (x) ^ Cj (x))) Cannot be translated into dlgp, even when restricted to (atomic) classes.
Object Property Domain ObjectPropertyDomain(p; C) C must be a SuperClass expression.
Object Property Range ObjectPropertyRange(p; C) C must be a SuperClass expression.
Class Assertions ClassAssertion(C; i) Equivalent to the formula 8x (x = i ! HasKey HasKey(C; p1; : : : ; pk) C must be a SubClass expression.
Finally, we point out that the profiles of OWL 2 (namely EL, QL and RL) are fragments of OWL2 ER.
Property 9. All OWL 2 axioms that are either EL, QL or RL axioms are also ER axioms. 4.6
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 InverseObjectProperty) dlgp rules or constraints. Such axioms always belong to the ER fragment.
Each axiom (and assertion) that requires class expressions (except DisjointUnion, 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; (9R:C)(a) generates the class inclusion fag v 9R: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 inclusion 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 ObjectMaxCardinality (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 obtained, until the R(n) obtained is an EquivClass expression or a warning is issued.
i Example 14. Let us consider the class inclusion A v (B tC)u(8r:D). Neither (B tC) nor (8r:D) are EquivClass expressions, so we generate the two class inclusions A v B t C and A v 8r:D. We have no possibility to rewrite the first one, so a warning is issued. The second is rewritten into 9r :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 8r:(C u :B) u :(C t D) u 9r:(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 8r:(C u :B), (2) A t :B v :(C t D), and (3) A t :B v 9r:(B t C). (1) is equivalently rewritten into (1:0) 9r :(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) 9r :(A t :B) v C and (1:0:2) 9r :(A t :B) v :B. The inclusion (1:0:2) is equivalently rewritten into (1:0:2:0) B u 9r :(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) 9r :A t 9r :(:B) v C, (1:0:2:0:0) (B u 9r :A) t (B u 9r :(: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) 9r :A v C, (1:0:1:0:2) 9r :(:B) v C, (1:0:2:0:0:1) B u 9r :A v ?, (1:0:2:0:0:2) B u 9r :(: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
In this paper, we presented the main aspects of the dlgp format dedicated to the framework 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.