OWL 21 is commonly used to represent objects with complex structure, such as complex 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 ontologya public dictionary of molecular entities used to enhance interoperability of applications supporting tasks such as drug discovery. In order to automate the classification of molecular entities, ChEBI descriptions were translated into OWL and then classified using automated reasoning. However, this approach was hindered by the fundamental inability 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 property 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 required structures. An alternative approach suggests a combination of OWL 2, rules, and description graphs (DGs) [12]-a graphical notation for describing non-tree-like structures. 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 structures 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 merging 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
entailment 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
hydrogen 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
condition from [
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 semantics. 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 decidability 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 decide 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
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 2 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) = fHig1 i `, body +(r) = fBig1 i n, body (r) = fBign<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 2 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 2 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 j= P , if ? 62 I and I satisfies each rule r 2 ground (P ). Given a negation-free program P , set I is a minimal model of P if I j= P and no I0 ( I exists such that I0 j= 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 j= A if A 2 I for each stable model I of P ; otherwise, we write P 6j= A.
A substitution is a partial mapping of variables to ground terms. The result of applying 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 [ fh j h 2 head (r); r 2 P; maps the variables of r to
HU (P [ X) such that body +(r) X and body (r) \ X = ;g Let TP0 = ;, let TPi = TP (TPi 1) for i 1, and let TP1 = Si1=1 TPi . Such P has at most one stable model, and TP1 is the stable model of P if and only if ? 62 TP1. 3
We next motivate our work using examples from the chemical Semantic Web application 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 I0 shown in Figures 1(b) and 1(c), respectively; however, only interpretation I correctly reflects the structure of cyclobutane. Furthermore, interpretation I0 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 fourmembered rings that will be correctly identified as a superclass of cyclobutane.
The formalism from [
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).
(2) (3) This, however, is not the case, since interpretation I00 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 [
C
C
C C (a) Chemical structure of cyclobutane
Molecule; Cyclobutane Carbon
Carbon
Carbon CarbonCarbon
Carbon Carbon
Carbon CarbonCarbon
CarbonCarbon (c) Interpretation I0
Molecule;
Cyclobutane Carbon Carbon (b) Interpretation I
Carbon
Carbon
Molecule; Cyclobutane Carbon Carbon (d) Interpretation I00
Carbon Carbon
Oxygen translation is interpreted under stable models. Consequently, interpretations such as I00 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
structures, so reasoning with DGLP ontologies is trivially undecidable [
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 directed labeled graph where – V = f1; : : : ; ng 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 2 V and a set of binary predicates (v1; v2) P to each edge (v1; v2) 2 E,
Gcb :
Bond Cyclobutane
1 Carbon 2
(a) Cyclobutane DG
Cyclobutane(a) Molecule(a) Gcb(a; f1Gcb (a); f2Gcb (a); f3Gcb (a); f4Gcb (a)) HasAtom(a; fiGcb (a)) for each i 2 f1; 2; 3; 4g Carbon(fiGcb (a)) for each i 2 f1; 2; 3; 4g Bond(fiGcb (a); fiG+c1b(a)) for each i 2 f1; 2; 3g Bond(f4Gcb (a); f1Gcb (a)) MolWith4MemberedRing(a) Hydrocarbon(a)
(b) The stable model of LP(O)
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 orderings, 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 instances 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 carboxyl 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 quadruple 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 [
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; : : : ; fjGV j 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 jV j):
A(x) ! G(x; f1G(x); : : : ; fjGV j 1(x)) G(x1; : : : ; xjV j) !
^ i2V;B2 (i) ^
B(xi) ^
B(xi) ^ ^
^ hi;ji2E;R2 (i;j)
R(xi; xj )
R(xi; xj ) ! G(x1; : : : ; xjV j) i2V;B2 (i);B6=A
hi;ji2E;R2 (i;j)
The start and layout rules of a description graph serve to unfold the graph’s structure, whereas the recognition rule identifies instances of the start predicate. The function terms f1G(x); : : : ; fjGV j 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)) Gcb(x1; x2; x3; x4; x5) ! Cyclobutane(x1) ^ ^ Bond(xi; xi+1) ^ Bond(x5; x2) ^ ^ HasAtom(x1; xi) ^ 2 i 5 2 i 4
^ Carbon(xi) 2 i 5 (sG) (`G) (rG) (sGcb ) (`Gcb )
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 program Axioms(G) is the set of rules that contains the start rule sG and the layout rule `G if m 2 f); ,g, and the recognition rule rG if m 2 f(; ,g. For a set of description graphs DG = fGig1 i n, let Axioms(DG ) = SGi2DG 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 predicates occurring in O, and let a be a fresh constant not occurring in O. Then, D subsumes C w.r.t. O, written O j= C v D, if LP(O) [ fC(a)g j= 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) ^ 1 i 4
^ 1 i 3
Bond(yi; yi+1) ^ Bond(y4; y1) ^ 1 i<j 4
not yi = yj ! MolWith4MemberedRing(x)
The use of the equality predicate = in the body of r1 does not require an extension 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 = fGcbg, let = ;, let R = frigi4=1, let F = fCyclobutane(a)g, 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) j= Hydrocarbon(a) and LP(O) j= MolWith4MemberedRing(a), as expected. (r1) (r3) (r4) 5
Reasoning about logic programs with function symbols is undecidable in general [
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 special 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 2 f1; 2g be two description graphs. We define ChkPair(G1; G2) and ChkSelf(Gi) as follows:
ChkPair(G1; G2) = fG1(x1; : : : ; xjV1j) ^ A2(xk) ! Cycle j 1 k ChkSelf(Gi) = fGi(x1; : : : ; xjVij) ^ Ai(xk) ! Cycle j 1 < k jV1jg jVijg (4) (5) Let DG = fGig1 i n be a set of description graphs and let DG . We define Check(DG ; ) as follows: be a graph ordering on 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 = fGAA; Gcxlg and = f(GAA; Gcxl)g, set Check(DG ; ) contains the following rules:
for 1 for 2 for 2 i i i 3 3 3 Definition 8. A DGLP ontology O is said to be semantically acyclic if and only if LP(O) [ Check(O) 6j= Cycle.
Example 4. Let DG = fGAA; Gcxlg with mAA = mcxl = , , let = f(GAA; Gcxl)g, let F = fAceticAcid(a)g, and let O = hDG ; ; ;; F i. The logic program LP(O) contains F and the following rules (HP abbreviates HasPart):
Methyl(y) ^ Carboxyl(z) ^ HP(x; y) ^ HP(x; z) ! GAA(x; y; z)
Let also Check(O) = Check(DG ; ) as defined in Example 3. We can easily
compute 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 6j= Cycle and O is
semantically acyclic. However, P is neither weakly [
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 ? 62 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 2 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 2 P we have (i) if B 2 body P+(r), then (r0) (r) for each r0 2 P with B 2 head P (r0) and (ii) if B 2 body P (r), then (r0) < (r) for each r0 2 P with B 2 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 2 P , we have r 2 P (r). The sets P1; : : : ; Pn are called the strata of P . Let UP10 = TP11 , U Pij = TPi j (UP1j 1 ) for 1 j n and i 1 and UP1j = TP1j (UP1j 1 ). The stable model of P is given by UP1n . 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 2 DG such that G1 6= G2, G1 6
have ChkPair(G1; G2) Pi, and – for each G 2 DG such that sG 2 Pi, we have ChkSelf(G)
Pi.
G2, and fsG1 ; sG2 g
Pi, we
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 2 U Pij , or U Pi+j1 = U Pij and U Pij is finite. In order to test the applicability of our approach in practice, we developed a prototypical 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 ontology 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
defined in [