=Paper=
{{Paper
|id=None
|storemode=property
|title=Modelling Structured Domains Using Description Graphs and Logic Programming
|pdfUrl=https://ceur-ws.org/Vol-846/paper_22.pdf
|volume=Vol-846
|dblpUrl=https://dblp.org/rec/conf/dlog/MagkaMH12
}}
==Modelling Structured Domains Using Description Graphs and Logic Programming==
<pdf width="1500px">https://ceur-ws.org/Vol-846/paper_22.pdf</pdf>
<pre>
            Modelling Structured Domains Using
        Description Graphs and Logic Programming?

                   Despoina Magka, Boris Motik, and Ian Horrocks

                  Department of Computer Science, University of Oxford
                     Wolfson Building, Parks Road, OX1 3QD, UK



1    Introduction
OWL 21 is commonly used to represent objects with complex structure, such as com-
plex assemblies in engineering applications [5], human anatomy [13], or the structure
of chemical molecules [7]. In order to ground our discussion, we next present a concrete
application of the latter kind; however, the problems and the solution that we identify
apply to numerous similar scenarios.
    The European Bioinformatics Institute (EBI) has developed the ChEBI2 ontology—
a public dictionary of molecular entities used to enhance interoperability of applica-
tions supporting tasks such as drug discovery. In order to automate the classification of
molecular entities, ChEBI descriptions were translated into OWL and then classified us-
ing automated reasoning. However, this approach was hindered by the fundamental in-
ability of OWL to precisely represent the structure of complex molecular entities, as the
tree-model property of OWL prevents one from describing non-tree-like relationships
using schema axioms. For example, OWL axioms can state that butane molecules have
four carbon atoms, but they cannot state that the four atoms in a cyclobutane molecule
are arranged in a ring. Please note that this applies to schema descriptions only: the
structure of a particular cyclobutane molecule can be represented using class and prop-
erty assertions, but the general definition of all cyclobutane molecules—a problem that
terminologies such as ChEBI aim to solve—cannot be fully described in OWL. As we
show in Section 3, an ontology may therefore fail to entail certain desired consequences.
    A common solution to this problem is to extend OWL 2 with a rule-based formalism
such as SWRL;3 however, this either results in undecidability [9] or requires restrictions
in the shape of the rules [8], which typically prevent the rules from axiomatising the re-
quired structures. An alternative approach suggests a combination of OWL 2, rules, and
description graphs (DGs) [12]—a graphical notation for describing non-tree-like struc-
tures. Decidability of reasoning is ensured via a property separation condition and by
requiring DGs to be acyclic. Intuitively, the latter means that DGs can describe struc-
tures of arbitrary shape, but bounded in size, while the former limits the interaction
between the OWL and DG parts, thus preventing multiple DG structures from merg-
ing into one structure of (potentially) unbounded size. As reported in [7], DGs solved
?
   Work supported by EU FP7 SEALS and EPSRC projects ConDOR, ExODA, and LogMap.
 1
   http://www.w3.org/TR/owl2-overview/
 2
   http://www.ebi.ac.uk/chebi/
 3
   http://www.w3.org/Submission/SWRL/
only some of the problems related to the representation of structured objects, and our
subsequent discussions with EBI researchers revealed the following drawbacks.
    First, the DG approach does not allow one to define structures based on the absence
of certain characteristics. For example, an inorganic molecule is commonly described
as ‘a molecule not containing a carbon atom’, which can then be used to classify water
as an inorganic molecule. Designing an axiomatisation that produces the desired entail-
ment is very cumbersome with the DG approach: apart from stating that ‘each water
molecule consists of one oxygen and two hydrogen atoms’, one must additionally state
that ‘these three atoms are the only atoms in a water molecule’ and that ‘neither hydro-
gen nor oxygen atoms are carbon atoms’. Second, the separation conditions governing
the interaction of the OWL 2 and DG components makes the combined language rather
difficult to use, as no role can be used in both components. Third, the acyclicity condi-
tion from [12] is rather cumbersome: a modeller must add a number of negative class
assertions to DGs so as to make any ontology with cyclic implications between DGs
unsatisfiable. This solution fails to cleanly separate the semantic consequences of an
ontology from the acyclicity check.
    In response to this critique, in this paper we present a radically different approach
to modelling complex objects via a novel formalism that we call Description Graph
Logic Programs (DGLP). At the syntactic level, our approach combines DGs, rules, and
OWL 2 RL axioms.4 In order to overcome the first problem, we give semantics to our
formalism via a translation into logic programs interpreted under stable model seman-
tics. As we show in Section 4, the resulting formalism can capture conditions based on
the absence of information. Moreover, we address the second problem by ensuring de-
cidability without the need for complex property separation conditions. To address the
third problem, in Section 5 we discuss existing syntactic acyclicity conditions and argue
that they unnecessarily rule out some very simple and intuitively reasonable ontologies.
As a remedy, we present a novel semantic acyclicity condition. Roughly speaking, a
precedence relation describing allowed implications between DGs is specified by the
modeller; a cyclic ontology that is not compatible with this precedence relation entails
a special propositional symbol. A cyclic ontology can still entail useful consequences,
but termination of reasoning can no longer be guaranteed. In Section 6 we consider
the problem of reasoning with negation-free ontologies and ontologies with stratified
negation. We show that the standard bottom-up evaluation of logic programs can de-
cide the relevant reasoning problems for semantically acyclic ontologies, and that it can
also decide whether an ontology is semantically acyclic. In Section 7 we briefly discuss
a preliminary evaluation of our formalism which indicates that reasoning with DGLP
ontologies is practically feasible. Proofs of the technical results can be found online.5


2      Preliminaries
We assume the reader to be familiar with OWL and description logics; for brevity, we
write OWL axioms using the DL notation. Let Σ = (ΣC , ΣF , ΣP ) be a first-order logic
signature, where ΣC , ΣF , and ΣP are countably infinite sets of constant, function, and
 4
     http://www.w3.org/TR/owl-profiles/
 5
     http://www.cs.ox.ac.uk/isg/people/despoina.magka/pubs/reports/DGLPTechnicalReport.pdf
 predicate symbols, respectively, and where ΣP contains the 0-ary predicate ⊥. The
 arity of a predicate A is given by ar (A). A vector t1 , . . . , tn of first-order terms is often
 abbreviated as ~t. An atom is a first-order formula of the form A(~t), where A ∈ ΣP and
~t is a vector of the terms t1 , . . . , tar (A) . A rule r is an implication of the form
             B1 ∧ . . . ∧ Bn ∧ not Bn+1 ∧ . . . ∧ not Bm → H1 ∧ . . . ∧ H`                    (1)
where H1 , . . . , H` are atoms, B1 , . . . , Bm are atoms different from ⊥, m ≥ 0, and
` > 0. Let head (r) = {Hi }1≤i≤` , body + (r) = {Bi }1≤i≤n , body − (r) = {Bi }n<i≤m ,
and body(r) = body + (r) ∪ body − (r). A rule r is safe if every variable that occurs
in head (r) ∪ body − (r) also occurs in body + (r). If body(r) = ∅ and r is safe, then
                                                             −
r is a fact. We denote with head P (r), body +   P (r), body P (r), and body P (r) the set of
                                          +          −
predicates that occur in head (r), body (r), body (r), and body(r), respectively. A rule
r is function-free if no function symbols occur in r. A logic program P is a set of rules.
A logic program P is negation-free if, for each rule r ∈ P , we have body − (r) = ∅.
    Given a logic program P , HU (P ) (Herbrand Universe) is the set of all terms that
can be formed using constants and functions from P (w.l.o.g. we assume that P contains
at least one constant). If no variables occur in an atom (rule), then the atom (rule)
is ground. Given a logic program P , the set HB (P ) is the set of all ground atoms
constructed using the terms in HU (P ) and the predicates in P . The grounding of a rule
r w.r.t. a set of terms T is the set of rules obtained by substituting the variables of r by
the terms of T in all possible ways. Given a logic program P , the program ground (P )
is obtained from P by replacing each rule r ∈ P with its grounding w.r.t. HU (P ).
    Let I ⊆ HB (P ) be a set of ground atoms. Then, I satisfies a ground rule r if
body + (r) ⊆ I and body − (r) ∩ I = ∅ imply head (r) ⊆ I. Furthermore, I is a model
of a (not necessarily ground) program P , written I |= P , if ⊥ 6∈ I and I satisfies each
rule r ∈ ground (P ). Given a negation-free program P , set I is a minimal model of P
if I |= P and no I 0 ( I exists such that I 0 |= P . The Gelfond-Lifschitz reduct P I of a
logic program P w.r.t. I is obtained from ground (P ) by removing each rule r such that
body − (r) ∩ I 6= ∅, and removing all atoms not Bi in all the remaining rules. A set I is
a stable model of P if I is a minimal model of P I . Given a fact A, we write P |= A if
A ∈ I for each stable model I of P ; otherwise, we write P 6|= A.
    A substitution is a partial mapping of variables to ground terms. The result of apply-
ing a substitution θ to a term, atom, or a set of atoms M is written as M θ and is defined
as usual. Let P be a logic program in which no predicate occurring in the head of a rule
in P also occurs negated in the body of a (possibly different) rule in P . Operator TP ,
applicable to a set of facts X, is defined as follows:
  TP (X) = X ∪ {hθ | h ∈ head (r), r ∈ P, θ maps the variables of r to
                 HU (P ∪ X) such that body + (r)θ ⊆ X and body − (r)θ ∩ X = ∅}
                                                             S∞
Let TP0 = ∅, let TPi = TP (TPi−1 ) for i ≥ 1, and let TP∞ = i=1 TPi . Such P has at
most one stable model, and TP∞ is the stable model of P if and only if ⊥ 6∈ TP∞ .

3    Motivating Application
We next motivate our work using examples from the chemical Semantic Web appli-
cation mentioned in the introduction. The goal of this application is to automatically
classify chemical entities based on descriptions of their properties and structure. The
inability of OWL to describe cyclic structures with sufficient precision causes problems
when modelling chemical compounds, as molecules are highly cyclic. For example,
the cyclobutane molecule contains four carbon atoms connected in a ring, as shown in
Figure 1(a). One might try to represent this structure using the following OWL axiom:

      Cyclobutane v Molecule u = 4 hasAtom.[Carbon u (= 2 bond.Carbon)]

This axiom is satisfied in first-order interpretations I and I 0 shown in Figures 1(b)
and 1(c), respectively; however, only interpretation I correctly reflects the structure of
cyclobutane. Furthermore, interpretation I 0 cannot be ruled out by adding axioms due
to the tree-model property of OWL, according to which each satisfiable TBox has at
least one tree-shaped interpretation. This can prevent the entailment of certain desired
consequences. For example, one cannot define the class of molecules containing four-
membered rings that will be correctly identified as a superclass of cyclobutane.
     The formalism from [12] addresses this problem by augmenting an OWL ontology
with a set of rules and a set of description graphs (DGs), where each DG describes a
complex object by means of a directed labeled graph. To avoid misunderstandings, we
refer to the formalism from [12] as DGDL (Description Graph Description Logics), and
to the formalism presented in this paper as DGLP (Description Graph Logic Programs).
Thus, cyclobutane can be described using the DG shown in Figure 2(a). The first-order
semantics of DGDL ontologies ensures that all models of an ontology correctly repre-
sent the DG structure; for example, interpretation I 0 from Figure 1(c) does not satisfy
the DG in Figure 2(a). Nevertheless, the interpretation I 00 shown in Figure 1(d) also sat-
isfies the definition of cyclobutane under the semantics of DGDL ontologies. We next
show how the presence of models with excess information can restrict entailments.
     One might describe the class of hydrocarbon molecules (i.e., molecules consisting
exclusively of hydrogens and carbons) using axiom (2). One would expect the definition
of cyclobutane (as given in a DGDL ontology) and (2) to imply subsumption (3).

            Molecule u ∀hasAtom.(Carbon t Hydrogen) v Hydrocarbon                      (2)
            Cyclobutane v Hydrocarbon                                                  (3)

This, however, is not the case, since interpretation I 00 does not satisfy axiom (3). One
might preclude the existence of extra atoms by adding cardinality restrictions requiring
each cyclobutane to have exactly four atoms. Even so, axiom (3) would not be entailed
because of a model similar to I, but where one carbon atom is also an oxygen atom.
One could eliminate such models by introducing disjointness axioms for all chemical
elements. Such gradual circumscription of models, however, is not an adequate solution,
as one can always think of additional information that needs to be ruled out.
    In order to address such problems, we present a novel expressive formalism that
we call Description Graph Logic Programs (DGLP). DGLP ontologies are similar to
DGDL ontologies in that they extend OWL ontologies with DGs and rules. In our case,
however, the ontology is restricted to OWL 2 RL so that the ontology can be translated
into rules [6]. We give semantics to our formalism by translating DGLP ontologies
into logic programs with function symbols. As is common in logic programming, the
                                                                      Molecule,
                                                                     Cyclobutane
            hasAtom
              bond


                        C           C                       Carbon                    Carbon


                        C       C                           Carbon               Carbon
      (a) Chemical structure of cyclobutane                 (b) Interpretation I
                                    Molecule, Cyclobutane

                                                              Molecule, Cyclobutane
             Carbon         Carbon
               Carbon                                                                    Oxygen
      CarbonCarbon          Carbon Carbon          Carbon
                                                            Carbon                    Carbon

               CarbonCarbon              CarbonCarbon       Carbon                Carbon
                                0
         (c) Interpretation I                               (d) Interpretation I 00

                   Fig. 1. The chemical structure and the models of cyclobutane


translation is interpreted under stable models. Consequently, interpretations such as I 00
are not stable models of the DG in Figure 2(a), and hence subsumption (3) is entailed.
    Logic programs with function symbols can axiomatise infinite non-tree-like struc-
tures, so reasoning with DGLP ontologies is trivially undecidable [2]. Our goal, how-
ever, is not to model arbitrarily large structures, but to describe complex objects up to a
certain level of granularity. For example, acetic acid has a carboxyl part, and carboxyl
has a hydroxyl part, but hydroxyl does not have an acetic acid part (see Fig. 3(a)). In
Section 5 we exploit this intuition and present a new acyclicity condition that ensures
decidability and allows for the modelling of naturally-arising molecular structures, such
as acetic acid, that would be ruled out by existing syntactic acyclicity conditions [4, 11].


4     Description Graph Logic Programs
We now present the DGLP formalism in detail; we first define description graphs.

Definition 1 (Description Graph). A description graph G = (V, E, λ, A, m) is a di-
rected labeled graph where
    – V = {1, . . . , n} is a nonempty set of vertices,
    – E ⊆ V × V is a set of edges,
    – λ assigns a set of unary predicates λ(v) ⊆ ΣP to each vertex v ∈ V and a set of
      binary predicates λ(v1 , v2 ) ⊆ ΣP to each edge (v1 , v2 ) ∈ E,
                 HasAtom
                    Bond
                                        Cyclobutane(a) Molecule(a)
                Cyclobutane                      G          G          G          G
                                        Gcb (a, f1 cb (a), f2 cb (a), f3 cb (a), f4 cb (a))
        Gcb :        1                                   Gcb
                                        HasAtom(a, fi (a)) for each i ∈ {1, 2, 3, 4}
                                                    G
                                        Carbon(fi cb (a)) for each i ∈ {1, 2, 3, 4}
                                                 Gcb        Gcb
                                        Bond(fi (a), fi+1       (a)) for each i ∈ {1, 2, 3}
        Carbon 2           3 Carbon              Gcb        G
                                        Bond(f4 (a), f1 cb (a))
                                        MolWith4MemberedRing(a)
         Carbon 5          4 Carbon     Hydrocarbon(a)

        (a) Cyclobutane DG                      (b) The stable model of LP(O)

                          Fig. 2. Representing cyclobutane with DGLP

                       Carboxyl
                                          GAA :     AceticAcid         Gcxl :     Carboxyl
                      O
                                                        1                            1
                           Carbonyl     HasPart
                      C
                             Hydroxyl               2       3                   2     3
    Methyl CH3                OH                  Methyl Carboxyl           CarbonylHydroxyl

   (a) Chemical graph of acetic acid       (b) Acetic acid DG            (c) Carboxyl DG

           Fig. 3. The chemical graph of acetic acid and the GAA and the Gcxl DGs


 – A ∈ ΣP is a start predicate for G such that A ∈ λ(1), and
 – m ∈ {⇒, ⇐, ⇔} is a mode for G.

     A description graph (DG) abstracts the structure of a complex object by means of
a directed labeled graph. For example, Figure 2 illustrates a DG that represents the
structure of a cyclobutane molecule. The start predicate of the graph (Cyclobutane in
this case) corresponds to the name of the object that the graph describes. The mode
determines whether a graph should be interpreted as an ‘only if’, ‘if’, or ‘if and only
if’ statement. More precisely, ⇒ means that each instance of the DG’s start predicate
implies the existence of a corresponding instantiation of the entire graph structure; ⇐
means that an instantiation of a suitable graph structure is ‘recognised’ as an instance
of the corresponding DG; and ⇔ means both of the above. Next we define graph or-
derings, which will play an important role in ensuring the decidability of DGLP.

Definition 2 (Graph Ordering). A graph ordering on a set of description graphs DG
is a transitive and irreflexive relation ≺ ⊆ DG × DG.

    Intuitively, a graph ordering specifies which DGs can imply the existence of in-
stances of other DGs. For example, let GAA be a graph that represents acetic acid, and
let Gcxl be a graph that represents the carboxyl group (Fig. 3); then, one might define ≺
such that GAA ≺ Gcxl , so that an acetic acid instance may imply the existence of a car-
boxyl group instance, but not vice versa. We are now ready to define DGLP ontologies.
Definition 3 (DGLP Ontology). A DGLP ontology O = hDG, ≺, R, F i is a quadru-
ple where DG is a finite set of description graphs, ≺ is a graph ordering on DG, R is
a finite set of function-free and safe rules, and F is a finite set of function-free facts.
    For the sake of simplicity, we do not explicitly include an OWL 2 RL TBox into the
definition of DGLP ontologies: OWL 2 RL axioms can be translated into rules as shown
in [6] and included in R, and datatypes can be handled as in [10]. Similarly, we could
think of F as an OWL 2 ABox, as ABox assertions correspond directly to facts [6]. An
example of a DGLP ontology is h{GAA , Gcxl }, {(GAA , Gcxl )}, ∅, {AceticAcid(a)}i.
    We next define the semantics of DGLP via a translation into logic programs. Since
R and F are already sets of rules and ≺ serves only to check acyclicity, we only need
to specify how to translate DGs into rules.
Definition 4 (Start, Layout, and Recognition Rule). Let G = (V, E, A, λ, m) be a
description graph and let f1G , . . . , f|V
                                         G
                                            |−1 be fresh distinct function symbols uniquely
associated with G. The start rule sG , the layout rule `G , and the recognition rule rG of
G are defined as follows (G is also used as a predicate of arity |V |):
      A(x) → G(x, f1G (x), . . . , f|V
                                    G
                                       |−1 (x))                                               (sG )
                               ^                            ^
      G(x1 , . . . , x|V | ) →          B(xi ) ∧                       R(xi , xj )            (`G )
                            i∈V,B∈λ(i)             hi,ji∈E,R∈λ(i,j)
             ^                           ^
                        B(xi ) ∧                      R(xi , xj ) → G(x1 , . . . , x|V | )    (rG )
      i∈V,B∈λ(i),B6=A              hi,ji∈E,R∈λ(i,j)

    The start and layout rules of a description graph serve to unfold the graph’s struc-
ture, whereas the recognition rule identifies instances of the start predicate. The function
terms f1G (x), . . . , f|V
                        G
                           |−1 (x) correspond to existential restrictions whose existentially
quantified variables have been skolemised.
Example 1. The start rule and layout rule that correspond to the DG of cyclobutane
from Figure 2 (assuming mode ⇒ as specified in Definition 5) are the following.
      Cyclobutane(x)→ Gcb (x, f1Gcb (x), f2Gcb (x), f3Gcb (x), f4Gcb (x))                (sGcb )
                                                    ^
 Gcb (x1 , x2 , x3 , x4 , x5 ) → Cyclobutane(x1 ) ∧       Bond(xi , xi+1 ) ∧ Bond(x5 , x2 ) ∧
                                                   2≤i≤4
                         ^                              ^
                                HasAtom(x1 , xi ) ∧            Carbon(xi )                   (`Gcb )
                        2≤i≤5                          2≤i≤5

    Next, we define Axioms(DG), which is a logic program that encodes a set of DGs.

Definition 5 (Axioms(DG)). For a description graph G = (V, E, λ, A, m), the pro-
gram Axioms(G) is the set of rules that contains the start rule sG and the layout rule
`G if m ∈ {⇒, ⇔}, and the recognition rule rG if mS∈ {⇐, ⇔}. For a set of descrip-
tion graphs DG = {Gi }1≤i≤n , let Axioms(DG) = Gi ∈DG Axioms(Gi ).
   For each DGLP ontology O = hDG, ≺, R, F i, we denote with LP(O) the program
Axioms(DG)∪R∪F . We check whether D subsumes C as in standard OWL reasoning:
we assert C(a) for a a fresh individual, and we check whether D(a) is entailed.
Definition 6 (Subsumption). Let O be a DGLP ontology, let C and D be unary pred-
icates occurring in O, and let a be a fresh constant not occurring in O. Then, D sub-
sumes C w.r.t. O, written O |= C v D, if LP(O) ∪ {C(a)} |= D(a) holds.

Example 2. We now show how a DGLP ontology can be used to obtain the inferences
described in Section 3. Rule (r1 ) encodes the class of four-membered ring molecules
and rules (r2 ) and (r3 ) represent the class of hydrocarbons.
                   ^                          ^
 Molecule(x) ∧           HasAtom(x, yi ) ∧         Bond(yi , yi+1 ) ∧ Bond(y4 , y1 )
                  1≤i≤4                  1≤i≤3
      ^
              not yi = yj → MolWith4MemberedRing(x)                                 (r1 )
    1≤i<j≤4

 Molecule(x) ∧ HasAtom(x, y) ∧ notCarbon(y) ∧ notHydrogen(y) → NHC(x) (r2 )
 Molecule(x) ∧ not NHC(x) → HydroCarbon(x)                                          (r3 )
 Cyclobutane(x) → Molecule(x)                                                       (r4 )

The use of the equality predicate = in the body of r1 does not require an exten-
sion to our syntax: if = occurs only in the body and not in the head of the rules,
then negation of equality can be implemented using a built-in predicate. We also state
that cyclobutane is a molecule using (r4 ) that corresponds to the OWL 2 RL axiom
Cyclobutane v Molecule. Let DG = {Gcb }, let ≺ = ∅, let R = {ri }4i=1 , let F =
{Cyclobutane(a)}, and let O = hDG, ≺, R, F i. Figure 2(b) shows the only stable
model of LP(O) by inspection of which we see that LP(O) |= Hydrocarbon(a) and
LP(O) |= MolWith4MemberedRing(a), as expected.


5     Semantic Acyclicity
Reasoning about logic programs with function symbols is undecidable in general [2].
This problem is similar to reasoning about datalog programs with existentially quan-
tified rule heads (known as tuple-generating dependencies or tgds) [3]. For such pro-
grams, conditions such as weak acyclicity [4] or super-weak acyclicity [11] ensure the
termination of bottom-up reasoning algorithms: these conditions examine the syntactic
structure of the rules and check whether values created by a rule’s head can be prop-
agated so as to eventually satisfy the premise of the same rule. Such conditions can
also be applied to DGLP ontologies; however, they may overestimate the propagation
of values introduced by existential quantification and thus rule out unproblematical pro-
grams that generate only finite structures. As shown in Example 4, this is the case for
programs that naturally arise from DGLP representations of molecular structures.
     To mitigate this problem, we propose a new semantic acyclicity condition. The idea
is to detect repetitive construction of DG instances by checking the entailment of a spe-
cial propositional symbol Cycle. In particular, the graph ordering ≺ of a DGLP ontology
O is used to extend LP(O) with rules that derive Cycle whenever an instance of a DG
G1 implies existence of an instance of a DG G2 but G1 6≺ G2 .
Definition 7 (Check(O)). Let Gi = (Vi , Ei , λi , Ai , mi ), i ∈ {1, 2} be two description
graphs. We define ChkPair(G1 , G2 ) and ChkSelf(Gi ) as follows:

   ChkPair(G1 , G2 ) = {G1 (x1 , . . . , x|V1 | ) ∧ A2 (xk ) → Cycle | 1 ≤ k ≤ |V1 |}   (4)
        ChkSelf(Gi ) = {Gi (x1 , . . . , x|Vi | ) ∧ Ai (xk ) → Cycle | 1 < k ≤ |Vi |}   (5)

Let DG = {Gi }1≤i≤n be a set of description graphs and let ≺ be a graph ordering on
DG. We define Check(DG, ≺) as follows:
                             [                                  [
  Check(DG, ≺) =                          ChkPair(Gi , Gj ) ∪       ChkSelf(Gi )
                      i,j∈{1,...,n}, i6=j, Gi 6≺Gj                   1≤i≤n

For a DGLP ontology O = hDG, ≺, R, F i, we define Check(O) = Check(DG, ≺).

Example 3. Figure 3(a) shows the structure of acetic acid molecules and the parts they
consist of. In this example, however, we focus on the description graphs for acetic acid
(GAA ) and carboxyl (Gcxl ), which are shown in Figures 3(b) and 3(c), respectively. Since
an instance of acetic acid implies the existence of an instance of a carboxyl, but not
vice versa, we define our ordering as GAA ≺ Gcxl . Thus, for DG = {GAA , Gcxl } and
≺ = {(GAA , Gcxl )}, set Check(DG, ≺) contains the following rules:

           Gcxl (x1 , x2 , x3 ) ∧ AceticAcid(xi ) → Cycle          for 1 ≤ i ≤ 3
          GAA (x1 , x2 , x3 ) ∧ AceticAcid(xi ) → Cycle            for 2 ≤ i ≤ 3
             Gcxl (x1 , x2 , x3 ) ∧ Carboxyl(xi ) → Cycle          for 2 ≤ i ≤ 3
Definition 8. A DGLP ontology O is said to be semantically acyclic if and only if
LP(O) ∪ Check(O) 6|= Cycle.
Example 4. Let DG = {GAA , Gcxl } with mAA = mcxl = ⇔ , let ≺ = {(GAA , Gcxl )},
let F = {AceticAcid(a)}, and let O = hDG, ≺, ∅, F i. The logic program LP(O) con-
tains F and the following rules (HP abbreviates HasPart):

   AceticAcid(x) → GAA (x, f1 (x), f2 (x))
   GAA (x, y, z) → AceticAcid(x) ∧ Methyl(y) ∧ Carboxyl(z) ∧ HP(x, y) ∧ HP(x, z)
   Methyl(y) ∧ Carboxyl(z) ∧ HP(x, y) ∧ HP(x, z) → GAA (x, y, z)
   Carboxyl(x) → Gcxl (x, g1 (x), g2 (x))
   Gcxl (x, y, z) → Carboxyl(x) ∧ Carbonyl(y) ∧ Hydroxyl(z) ∧ HP(x, y) ∧ HP(x, z)
   Carbonyl(y) ∧ Hydroxyl(z) ∧ HP(x, y) ∧ HP(x, z) → Gcxl (x, y, z)

Let also Check(O) = Check(DG, ≺) as defined in Example 3. We can easily com-
pute the stable model of P = LP(O) ∪ Check(O) using the TP operator and check
that Cycle is not in the (only) stable model of P ; so P 6|= Cycle and O is semanti-
cally acyclic. However, P is neither weakly [4] nor super-weakly acyclic [11]. This, we
believe, justifies the importance of semantic acyclicity for our applications.
6     Reasoning with DGLP Ontologies
Initially, we consider the problem of reasoning with a negation-free DGLP ontology
O = hDG, ≺, R, F i. Intuitively, one can apply the TP operator to P = LP(O) ∪
Check(O) and compute TP1 , . . . , TPi and so on. By Theorem 5, for some i we will
either reach a fixpoint or derive Cycle. In the former case, we have the stable model of
O (if ⊥ 6∈ TPi ), which we can use to decide the relevant reasoning problems; in the
latter case, we know that O is not acyclic.
Theorem 5. Let O = hDG, ≺, R, F i be a DGLP ontology with R negation-free, and
let P = LP(O) ∪ Check(O). Then, Cycle ∈ TPi or TPi+1 = TPi for some i ≥ 1.
    Checking the semantic acyclicity of O is thus decidable. If the stable model of
LP(O) ∪ Check(O) is infinite, then Cycle is derived; note that the inverse does not hold
as semantic acyclicity is a sufficient but not necessary termination condition.
    Next, we consider the case of DGLP ontologies with stratified negation-as-failure.
We start by recapitulating several definitions. For each program P , a stratification of P
is a mapping σ : P → N such that for each rule r ∈ P we have (i) if B ∈ body +                P (r),
then σ(r0 ) ≤ σ(r) for each r0 ∈ P with B ∈ head P (r0 ) and (ii) if B ∈ body −         P (r), then
σ(r0 ) < σ(r) for each r0 ∈ P with B ∈ head P (r0 ). A logic program P is stratifiable if
there exists a stratification of P . Moreover, a partition P1 , . . . , Pn of P is a stratification
partition of P w.r.t. σ if, for each r ∈ P , we have r ∈ Pσ(r) . The sets P1 , . . . , Pn are
called the strata of P . Let UP∞0 = TP11 , UPi j = TPi j (UP∞j−1 ) for 1 ≤ j ≤ n and i ≥ 1
and UP∞j = TP∞j (UP∞j−1 ). The stable model of P is given by UP∞n . Next we introduce the
notion of a DG-stratification, which ensures that the cycle detection rules are assigned
to the strata containing the relevant start rules of DGs.
Definition 9 (DG-stratification). Let O = hDG, ≺, R, F i be a DGLP ontology, let
P = LP(O) ∪ Check(O) and let P1 , . . . , Pn be a stratification partition of P w.r.t.
some stratification σ of P . Then, σ is a DG-stratification if
    – for each G1 , G2 ∈ DG such that G1 6= G2 , G1 6≺ G2 , and {sG1 , sG2 } ⊆ Pi , we
      have ChkPair(G1 , G2 ) ⊆ Pi , and
    – for each G ∈ DG such that sG ∈ Pi , we have ChkSelf(G) ⊆ Pi .
    The following result shows that, as long as LP(O) is stratified, one can always
assign the cycle checking rules in Check(O) to the appropriate strata and thus obtain a
DG-stratification of LP(O) ∪ Check(O).
Lemma 1. Let O = hDG, ≺, R, F i be a DGLP ontology. If σ is a stratification of
LP(O), then σ can be extended to a DG-stratification σ 0 of LP(O) ∪ Check(O).
    The following theorem implies that, given a stratifiable DGLP ontology, we can
decide whether the ontology is semantically acyclic, and if so, we can compute its
stable model and thus solve all relevant reasoning problems; please note that we show
the decidability of semantic acyclicity only for ontologies with stratified negation.
Theorem 6. Let O be a DGLP ontology and P = LP(O) ∪ Check(O). If P1 , . . . , Pn
is a stratification partition of P w.r.t. a DG-stratification of P , then, for each j with
1 ≤ j ≤ n, there exists i ≥ 1 such that Cycle ∈ UPi j , or UPi+1
                                                              j
                                                                 = UPi j and UPi j is finite.
7      Implementation Results and Discussion
In order to test the applicability of our approach in practice, we developed a prototyp-
ical implementation based on the XSB system.6 Using data extracted from ChEBI, we
built a number of DGLP ontologies with stratified NAF and we checked each ontology
for acyclicity and for entailed subsumptions: all ontologies were found acyclic and all
molecules were classified as expected; additionally, testing subsumptions for an ontol-
ogy representing 70 molecules did not require more than a few minutes on a standard
desktop computer. Given the prototypical nature of our application, we consider the
results as evidence of the practical feasibility of our approach.
    In this paper we have laid the theoretical foundations of a novel, expressive, and
OWL 2 RL-compatible ontology language that is well suited to modelling objects with
complex structure. In the future, we plan to modify our approach in order to avoid the
explicit definition of graph ordering by the modeller; furthermore, we shall investigate
whether semantic acyclicity can be combined with other conditions (such as those de-
fined in [1]) in order to obtain a more general acyclicity check. Finally, we will optimise
our prototype in order to obtain a fully-scalable chemical classification system.

References
 1. Baget, J.F., Leclère, M., Mugnier, M.L., Salvat, E.: On rules with existential variables: walk-
    ing the decidability line. Artif. Intell. 175(9-10), 1620–1654 (2011)
 2. Beeri, C., Vardi, M.Y.: The implication problem for data dependencies. In: Proc. ICALP. pp.
    73–85 (1981)
 3. Cali, A., Gottlob, G., Lukasiewicz, T., Marnette, B., Pieris, A.: Datalog+/-: A family of
    logical knowledge representation and query languages for new applications. In: LICS (2010)
 4. Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answer-
    ing. In: ICDT. pp. 207–224 (2003)
 5. Graves, H.: Representing product designs using a description graph extension to OWL 2. In:
    Proc. of the 5th OWLED Workshop (2009)
 6. Grosof, B.N., Horrocks, I., Volz, R., Decker, S.: Description logic programs: combining logic
    programs with description logic. In: WWW (2003)
 7. Hastings, J., Dumontier, M., Hull, D., Horridge, M., Steinbeck, C., Sattler, U., Stevens, R.,
    Hörne, T., Britz, K.: Representing chemicals using OWL, description graphs and rules. In:
    OWLED (2010)
 8. Krötzsch, M., Rudolph, S., Hitzler, P.: ELP: tractable rules for OWL 2. In: Proc. of the 7th
    Int. Semantic Web Conference (ISWC 2008). pp. 649–664 (2008)
 9. Levy, A.Y., Rousset, M.C.: Combining horn rules and description logics in CARIN. Artificial
    Intelligence 104(1–2), 165–209 (1998)
10. Lutz, C., Areces, C., Horrocks, I., Sattler, U.: Keys, nominals, and concrete domains. J. of
    Artificial Intelligence Research 23, 667–726 (2004)
11. Marnette, B.: Generalized schema-mappings: from termination to tractability. In: PODS
    (2009)
12. Motik, B., Grau, B.C., Horrocks, I., Sattler, U.: Representing ontologies using description
    logics, description graphs, and rsules. Artif. Int. 173, 1275–1309 (2009)
13. Rector, A.L., Nowlan, W.A., Glowinski, A.: Goals for concept representation in the GALEN
    project. In: SCAMC ’93. pp. 414–418 (1993)

 6
     http://xsb.sourceforge.net/

</pre>