Combined approaches have become a successful technique for CQ answering over ontologies. Existing algorithms, however, are restricted to the logics underpinning the OWL 2 profiles. Our goal is to make combined approaches applicable to a wider range of ontologies. We focus on RSA: a class of Horn ontologies that extends the profiles while ensuring tractability of standard reasoning. We show that CQ answering over RSA ontologies without role composition is feasible in NP. Our reasoning procedure generalises the combined approach for E LHO and DL-LiteR using an encoding of CQ answering into fact entailment w.r.t. a Logic Program with function symbols and stratified negation. Our results are significant in practice since many out-of-profile Horn ontologies are RSA.
Answering conjunctive queries (CQs) over ontology-enriched datasets is a core
reasoning task for many applications. CQ answering is computationally expensive: for
expressive description logics it is at least doubly exponential in combined complexity
[
Recently, there has been a growing interest in ontology languages with favourable
computational properties, such as E L [
A technique that is receiving increasing attention is the combined approach [
Our goal is to push the boundaries of the logics underpinning the OWL 2 profiles while retaining their nice complexity for CQ answering. Furthermore, we aim to devise algorithms that seamlessly extend the combined approach and which can be applied to a wide range of ontologies.
Recently, a class of Horn ontologies, called role safety acyclic (RSA), has been
proposed [
In this paper, we investigate CQ answering over RSA ontologies and show its
feasibility in NP. This result has significant implications in practice as it shows that CQ
answering over a wide range of out-of-profile ontologies is no harder (in combined
complexity) than over a database. Our procedure generalises the combined approach
for E LHO [
Logic Programs We use the standard notions of constants, terms and atoms in firstorder logic (FO). A literal is an atom a or its negation not a. A rule r is an expression of the form '(~x; ~z) ! (~x) with '(~x; ~z) a conjunction of literals with variables ~x [ ~z, and (~x) a non-empty conjunction of atoms over ~x.3 We denote with vars(r) the set ~x [ ~z. With head(r) we denote the set of atoms in , body+(r) is the set of atoms in ', and body (r) is the set of atoms which occur negated in r. Rule r is safe iff vars(r) all occur in body+(r). We consider only safe rules. Rule r is definite if body (r) is empty and it is datalog if it is definite and function-free. A fact is a rule with empty body and head consisting of a single function-free atom.
A program P is a finite set of rules. Let preds(X) denote the predicates in X, with X a (set of) atoms or a program. A stratification of P is a function str : preds(P) ! f1; : : : ; kg, where k jpreds(P)j, s.t. for every r 2 P and P 2 preds(head(r)) it holds that: (i) for every Q 2 preds(body+(r)): str(Q) str(P ), and (ii) for every Q 2 preds(body (r)): str(Q) < str(P ). The stratification partition of P induced
by str is the sequence (P1; : : : ; Pk), with Pi consisting of all rules r 2 P such that maxa2head(r)(str(pred(a))) = i. The programs Pi are the strata of P . A program is stratified if it admits a stratification. All definite programs are stratified.
Stratified programs have a Least Herbrand Model (LHM), which is constructed using the immediate consequence operator TP . Let U and B be the Herbrand Universe and Base of P, and let S B. Then, TP (S) consists of all facts in head(r) with r 2 P and a substitution from vars(r) to U satisfying body+(r) S and body (r) \ TS !=(S;).=ThSe1powers of TP are as follows: TP0 (S) = S, T Pi+1(S) = TP (TPn(S)), and
P i=0 TPn(S). Let str be a stratification of P, and let (P1; : : : ; Pk) be its stratification partition. Also, let U1 = TP!1 (;) and for each 1 i k let Ui+1 = TP!i+1 (Ui). Then, the LHM of P is Uk and is denoted M [P]. A program P entails a positive existential sentence (P j= ) if M [P] seen as a FO structure satisfies .
We use LPs to encode FO theories. For this, we introduce rules axiomatising the built-in semantics of the equality ( ) and truth (>) predicates. For a finite signature , we denote with F > the smallest set with a rule p(x1; x2; : : : ; xn) ! >(x1) ^ >(x2) ^ : : : ^ >(xn) for each n-ary predicate p in , and with F the usual axiomatisation of as a congruence over . For an LP P, we denote with P ;> the extension of P to P [ F > [ F with the signature of P.
Ontologies and Queries We define Horn-ALCHOIQ and specify its semantics via
translation to definite programs. W.l.o.g. we consider a normal form close to that in [
OWL 2 specifies the EL, QL, and RL profiles, which are all fragments of HornALCHOIQ with the exception of property chain axioms and transitivity, which we do not consider here. An ontology is: (i) EL if it does not contain inverse roles or axioms (T4); (ii) RL if it does not contain axioms (T5); and (iii) QL if it does not contain axioms (T2) or (T4), each axiom (T1) satisfies n = 1, and each axiom (T3) satisfies A = >.
A conjunctive query (CQ) Q is a formula 9~y: (~x; ~y) with (~x; ~y) a conjunction of function-free atoms over ~x [ ~y, where ~x are the answer variables. We denote with terms(Q) the set of terms in Q. Queries with no answer variables are Boolean (BCQs) and for convenience are written as a set of atoms.
We define the semantics by a mapping into definite rules as in Table 1: (O) = f ( ) j 2 Og 5. An ontology O is satisfiable if (O) ;> 6j= 9y:?(y). A tuple of constants ~c is an answer to Q if O is unsatisfiable, or (O) ;> j= 9~y: (~c; ~y). The set of answers is written cert(Q; O). This semantics is equivalent to the usual one. 4 Axioms A v n R:B can be simulated by (T1) and (T5). 5 By abuse of notation we say that R 2 O whenever R occurs in O.
Axioms
R
R v S (R1) (R2) (T1) dn
i=1 Ai v B (T2) A v fag (T3) 9R:A v B (T4) A v 1R:B (T5) A v 9R:B (A1) A(a) (A2) R(a; b)
Definite LP rules ( ) R(x; y) ! R (y; x); R (y; x) ! R(x; y)
R(x; y) ! S(x; y) Vin=1 Ai(x) ! B(x)
A(x) ! x a
R(x; y) ^ A(y) ! B(x) A(x) ^ R(x; y) ^ B(y) ^ R(x; z) ^ B(z) ! y
A(x) ! R(x; fRA;B (x)) ^ B(fRA;B (x))
! A(a)
! R(a; b)
CQ answering is EXPTIME-complete for Horn-ALCHOIQ ontologies [
RSA is a class of ontologies where all axioms in Table 1 are allowed, but their
interaction is restricted s.t. model size can be polynomially bounded [
Roles in O are divided into safe and unsafe. The intuition is that unsafe roles may participate in harmful interactions.
Definition 1. A role R is unsafe if it occurs in an axiom of the form A v 9R:B, and there is a role S s. t. either: 1. R vR Inv(S) and S occurs in an axiom of the form 9S:A v B with A 6= >, or 2. R vR S or R vR Inv(S) and S occurs in an axiom of the form A v 1S:B. A role R in O is safe, if it is not unsafe.
It follows from Definition 1 that RL, QL, and EL ontologies contain only safe roles. Example 1. Let OEx be the (out-of-profile) ontology with the following axioms:
A(a) A v D (1) (2)
A v 9S :C 9S:A v D (3) (4)
D v 9R:B B v 9S:D (5) (6)
R v T S v T (7) (8)
Roles R, S, T , and T are safe; however, S is unsafe as it occurs in an axiom (T5) while S occurs in an axiom (T3). We will OEx use as a running example. The distinction between safe and unsafe roles makes it possible to strengthen the translation in Table 1 while preserving satisfiability and entailment of unary facts. The translation of axioms (T5) with R safe can be realised by replacing the functional term fRA;B (x) with a Skolem constant vRA;B unique to A, R and B. The modified transformation generally leads to a smaller LHM: if all roles are safe then O is mapped into a Datalog program whose LHM is polynomial in the size of O.
Definition 2. Let vRA;B be a fresh constant for each concept A, B, and each safe role R in O. Then safe maps each 2 O to (i) A(x) ! R(x; vRA;B) ^ B(vRA;B) if is of type (T5) with R safe;(ii) ( ), otherwise. Let P = f safe( ) j 2 Og and PO = P ;>.
D(x) ! R(x; vRD;B) ^ B(vRD;B).
on ax. (5) and (6). For instance, (5) yields Theorem 1. [4, Theorem 2] Ontology O is satisfiable iff PO 6j= 9y:?(y). If O is satisfiable, then O j= A(c) iff A(c) 2 M [PO] for each unary predicate A and individual c in O.
If O has unsafe roles the model M [PO] might be infinite. We next define a Datalog program PRSA by introducing Skolem constants for all axioms (T5) in O. PRSA introduces also a predicate PE which ‘tracks’ all binary facts generated by the application of Skolemised rules over unsafe roles. A unary predicate U is initialised with the constants associated to unsafe roles and a rule U(x) ^ PE(x; y) ^ U(y) ! E(x; y) stores the PE-facts originating from unsafe roles using a predicate E. Then, M [PO] is of polynomial size when the graph induced by the extension of E is an oriented forest (i.e., a DAG whose underlying undirected graph is a forest). When this condition is fulfilled together with some additional conditions which preclude harmful interactions between equality-generating axioms and inverse roles, we say that O is RSA.
Definition 3. Let PE and E be fresh binary predicates, U be a fresh unary predicate, and uAR;B be a fresh constant for each concept A; B and each role R in O. Function
RSA maps each (i) 2 O to A(x) ! R(x; uAR;B) ^ B(uAR;B) ^ PE(x; uAR;B), if is of type (T5), and to (ii) ( ), otherwise. The program PRSA consists of RSA( ), for each 2 O, a rule U(x) ^ PE(x; y) ^ U(y) ! E(x; y), and a fact U(uAR;B) for each uAR;B with R unsafe.
Let MRSA be the LHM of PRSA ;>. Then, GO is the digraph with an edge (c; d) for each E(c; d) in MRSA. Ontology O is equality-safe if: 1. for each pair of atoms w t (with w and t distinct) and R(t; uAR;B) in MRSA and each role S s.t. R v Inv(S), it holds that S does not occur in an axiom (T4); and 2. for each pair of atoms R(a; uAR;B); S(uAR;B; a) in MRSA, with a 2 NI, there does not exist a role T such that both R vR T and S vR Inv(T ) hold.
We say that O is RSA if it is equality-safe and GO is an oriented forest.
The fact that GO is a DAG ensures that the LHM M [PO] is finite, whereas the lack of ‘diamond-shaped’ subgraphs in GO guarantees polynomiality of M [PO]. The safety condition on will ensure that RSA ontologies enjoy a special form of forest-model property that we exploit for CQ answering. Every ontology in QL (which is equalityfree), RL (where PRSA has no Skolem constants) and EL (no inverse roles) is RSA. Theorem 2. [4, Theorem 3] If O is RSA, then jM [PO]j is polynomial in jOj.
Tractability of standard reasoning for RSA ontologies follows from Theorems 1, 2. It can be checked that OEx is RSA. a)
A; D a
R; T S
R; T f(a) C; D vRD;B B S; T R; T B vS;D D b)
A; D a
vRD;B B (S )f T b
Rf
T b TSff T b Rf f(a) C; D
B vS;D D We next present our combined approach with filtration to CQ answering over RSA ontologies, which generalises existing techniques for DL-LiteR and E LHO.
In Section 4.1 we take the LHM for RSA ontologies given in Section 3 as a starting
point and extend it to a more convenient canonical model over an extended signature. In
order to deal with the presence of inverse roles in RSA ontologies, the extended model
captures the “directionality” of binary atoms; this will allow us to subsequently extend
the filtration approach from [
As usual in combined approaches, this model is not universal and the evaluation of
CQs may lead to spurious, i.e. unsound answers. In Section 4.2, we specify our filtration
approach for RSA ontologies as the LHM of a stratified program. In the following, we
fix an arbitrary RSA ontology O = R [ T [ A and an input CQ Q, which we use to
parameterise all our technical results.
The LHM M [PO] in Sec. 3 is a model of O that preserves entailment of unary facts.
It generalises the canonical model in [
A main source for spurious matches when evaluating Q over the canonical model of an EL ontology is the presence of ‘forks’ — confluent chains of binary atoms — in the query which map to ‘forks’ in the model over Skolem constants. This is also problematical in our setting since RSA ontologies have the forest-model property. (a; vRD;B) and (vSB;D; vRD;B) in M [POEx ], which form a fork over vRD;B. Example 3. Fig. 1 a) depicts the LHM M [POEx ] of OEx (the function fS;C is abbreviated with f ). We see models as digraphs where the direction of edges reflects the satisfaction of axioms (T5). Consider Q1 = fA(y1); R(y1; y2); R(y3; y2)g. Substitution (y1 7! a; y2 7! vRD;B; y3 7! vSB;D) is a spurious match of Q1 as it relies on edges
In EL, only queries which contain forks can be mapped to forks in the model. This is no longer the case for RSA ontologies, where forks in the model can lead to spurious answers even for linearly-shaped queries due to the presence of inverse roles.
Rf y t
Sf s
Rf y t
s Sb
Rb y t
Sb R(s; y) ^ S(t; y) a) forward/forward
R(s; y) ^ S(y; t) b) forward/backward
R(y; s) ^ S(y; t) c) backward/backward
To identify such situations, we compute a canonical model over an extended signature that contains fresh roles Rf and Rb for each role R. Annotations f (forward) and b (backwards) are intended to reflect the directionality of binary atoms in the model, where binary atoms created to satisfy an axiom (T5) are annotated with f . To realise this intuition declaratively, we modify the rules in PO for axioms (T5) as follows. If R is safe, then we introduce the rule A(x) ! Rf (x; vRA;B) ^ B(vRA;B); if it is unsafe, we introduce rule A(x) ! Rf (x; fRA;B(x)) ^ B(fRA;B) instead.
Superroles inherit the direction of the subrole, while roles and their inverses have opposite directions. To reflect this we include the following rules where 2 ff; bg: (i) R (x; y) ! S (x; y) for each axiom R v S in O; (ii) Rf (x; y) ! Inv(R)b(y; x) and Rb(x; y) ! Inv(R)f (y; x) for each role R; and (iii) R (x; y) ! R(x; y) for each role R. Rules (ii) are included only if O has inverse roles, and rules (iii) ‘copy’ annotated atoms to atoms over the original predicate. Fig. 1 b) depicts the annotated model for POEx : solid (resp. dotted) lines represent ‘forward’ (resp. ‘backward’) atoms.
Fig. 2 depicts the ways in which query matches may spuriously rely on a fork in an annotated model. Nodes represent the images in the model of the query terms; solid lines indicate the annotated atoms responsible for the match; and dashed lines depict the underpinning fork. The images of s and t must not be equal; additionally, y cannot be mapped to (a term identified to) a constant in O. For instance, the match in Ex. 4 is spurious as it corresponds to pattern (b) in Fig. 2. Unfortunately, the annotated model can present ambiguity: it is possible for both atoms Rf (s; t) and Rb(s; t) to hold. Example 5. Consider Q2 from Ex. 4. (y1 7! a; y2 7! vRD;B; y3 7! vSB;D) is also a match, where both T f (vRD;B; vSB;D) and T b(vRD;B; vSB;D) hold in the annotated model.
Such ambiguity is problematic for the subsequent filtration step. To disambiguate,
we use a technique similar to the one in [
a) A; D a f (a) C; D
Rf
T b Sf ; T f vRD;;B0 B vSB;;D0 D
T b Rf Definition 4. Let con (R) be the set of roles S s.t. R vR T and S vR Inv(T ) for some T . Let be a strict total order on triples (A; R; B), with R safe and A and B concept names B in O. For each (A; R; B), let: – vRA;;B0 , vRA;;B1 , and vRA;;B2 be fresh constants;
(D; S; C); vSD;;C1 if (D; S; C) – self(A; R; B) be the smallest set containing vRA;;B0 and vRA;;B1 if R 2 con (R); – cycle(A; R; B) be the smallest set containing, for each S 2 con (R), vSD;;C0 if (A; R; B) (A; R; B); fSD;C (vRA;;B0) and every fTF;E (vRA;;B0 ) s. t. uSD;C uTF;E is in MRSA, if S is unsafe.
– unfold(A; R; B) = self(A; R; B)[ cycle(A; R; B).
Let Rf and Rb be fresh binary predicates for each role R in O, NI be a fresh unary predicate, and notIn be a built-in predicate which holds when the first argument is an element of second argument. Let P be the smallest program with a rule ! NI(a) for each constant a and all rules in Fig. 4 and EO = P ;>. symbols/axioms in O ax. not of type (T5)
R v S, 2 ff; bg
ax. (T5), R unsafe ax. (T5), R safe
Logic Programming Rules
( ) R (x; y) ! S (x; y)
R (x; y) ! R(x; y) Rf (x; y) ! Inv(R)b(y; x)
Rb(x; y) ! Inv(R)f (y; x)
A(x) ! Rf (x; fRA;B(x)) ^ B(fRA;B(x)) A(x) ^ notIn(x; unfold(A; R; B)) ! Rf (x; vRA;;B0) ^ B(vRA;;B0)
if R 2 con (R), for every i = 0; 1: A(vRA;;Bi) ! Rf (vRA;;Bi; vRA;;Bi+1) ^ B(vRA;;Bi+1)
for every x 2 cycle(A; R; B):
A(x) ! Rf (x; vRA;;B1) ^ B(vRA;;B1)
Fig. 4: Rules in the program EO
The set con (R) contains roles that may cause ambiguity in conjunction with R. The ordering determines how cycles are unfolded using auxiliary constants. Each axiom A v 9R:B with R safe is Skolemised by default using vRA;;B0 , except when the axiom applies to a term in unfold(A; R; B) where we use vRA;;B1 or vRA;;B2 instead. Theorem 3. The following holds: (i) M [EO] is polynomial in jOj (ii) O is satisfiable iff EO 6j= 9y:?(y) (iii) if O is satisfiable, O j= A(c) iff A(c) 2 M [EO] and (iv) there are no terms s; t and role R s.t. EO j= Rf (s; t) ^ Rb(s; t). (1) (~x; ~y) ! QM(~x; ~y) (2) ! named(a) for each constant a in O (3a) QM(~x; ~y); not NI(yi) ! id(~x; ~y; i; i), for each 1 i j~yj (3b) id(~x; ~y; u; v) ! id(~x; ~y; v; u) (3c) id(~x; ~y; u; v) ^ id(~x; ~y; v; w) ! id(~x; ~y; u; w) for all R(s; yi), S(t; yj ) in Q with yi; yj 2 ~y (4a) Rf (s; yi) ^ Sf (t; yj ) ^ id(~x; ~y; i; j) ^ not s t ! fk (~x; ~y) for all R(s; yi), S(yj ; t) in Q with yi; yj 2 ~y: (4b) Rf (s; yi) ^ Sb(yj ; t) ^ id(~x; ~y; i; j) ^ not s t ! fk (~x; ~y) for all R(yi; s), S(yj ; t) in Q with yi; yj 2 ~y: (4c) Rb(yi; s) ^ Sb(yj ; t) ^ id(~x; ~y; i; j) ^ not s t ! fk (~x; ~y) for all R(yi; yj ), S(yk; yl) in Q with yi; yj ; yk; yl 2 ~y: (5a) Rf (yi; yj ) ^ Sf (yk; yl) ^ id(~x; ~y; j; l) ^ yi yk ^ not NI(yi) ! id(~x; ~y; i; k) (5b) Rf (yi; yj ) ^ Sb(yk; yl) ^ id(~x; ~y; j; k) ^ yi yl ^ not NI(yi) ! id(~x; ~y; i; l) (5c) Rb(yi; yj ) ^ Sb(yl; yk) ^ id(~x; ~y; i; l) ^ yj yk ^ not NI(yj ) ! id(~x; ~y; j; k) for each R(yi; yj ) in Q with yi; yj 2 ~y, and 2 ff; bg: (6) R (yi; yj ) ^ id(~x; ~y; i; v) ^ id(~x; ~y; j; w) ! AQ (~x; ~y; v; w) (7a) AQ (~x; ~y; u; v) ! T Q (~x; ~y; u; v), for each 2 ff; bg (7b) AQ (~x; ~y; u; v) ^ T Q (~x; ~y; v; w) ! T Q (~x; ~y; u; w), for each 2 ff; bg (8a) QM(~x; ~y) ^ not named(x) ! sp(~x; ~y), for each x 2 ~x (8b) fk (~x; ~y) ! sp(~x; ~y) (8c) T Q (~x; ~y; v; v) ! sp(~x; ~y), for each 2 ff; bg (9) QM(~x; ~y) ^ not sp(~x; ~y) ! Ans(~x) We now define a program PQ that can be used to eliminate all spurious matches of Q over the annotated model of O. The rules of the program are summarised in Table 2. We will refer to all terms in the model that are not equal to a constant in O as anonymous.
Matches where an answer variable is not mapped to a constant in O are spurious. We introduce a predicate named and populate it with such constants (rules (2)); then, we flag answers as spurious using a rule with negation (rules (8a)).
To detect forks we introduce a predicate fk , whose definition in datalog encodes the patterns in Fig. 2 (rules (4)). If terms s and t in Fig. 2 are existential variables mapping to the same anonymous term, further forks might be recursively induced. Example 7. Let Q3 = fA(y1); R(y1; y2); T (y2; y3); C(y4); R(y4; y5); S(y5; y3)g be a BCQ over OEx, with (y1 7! a; y2 7! vRD;;B0 ; y3 7! vSB;;D0 ; y4 7! f (a); y5 7! vRD;;B0 ) being its only match over the model in Fig. 3a). The identity of y2, y5 induces a fork on the match of R(y1; y2) and R(y4; y5).
We track identities in the model relative to a match using a fresh predicate id. It is initialised as the minimal congruence relation over the positions of the existential variables in the query which are mapped to anonymous terms (rules (3)). Identity is recursively propagated (rules (5)). Matches involving forks are marked as spurious by rule (8b).
Spurious matches can also be caused by cycles in the model and query satisfying certain requirements. First, the positions of existential variables of the query must be cyclic when considering also the id relation. Second, the match must involve only anonymous terms. Finally, all binary atoms must have the same directionality. Example 8. Consider the following BCQs over OEx: Q4 = fS(y1; y2); R(y2; y3); S(y3; y4); R(y4; y1)g; Q5 = fT (y1; y2); S(y2; y3); R(y3; y1)g; and Q6 = fS(y1; y2); R(y2; y3); S(y3; y4); R(y4; y5)g: Then, (y1 7! vRD;;B0 ; y2 7! vSB;;D0 ; y3 7! vRD;;B1 ; y4 7! vSB;;D1 ) is a match of Q4 inducing a cycle: all binary atoms are mapped ‘forward’ and the cycle involves only anonymous terms. In contrast, match (y1 7! vRD;;B0 ; y2 7! f (a); y3 7! a) over Q5 does not satisfy the requirements as it involves constant a. Note that Q4 and Q5 are cyclic. Q6 is not cyclic; thus, although the match (y1 7! vRD;;B0 ; y2 7! vSB;;D0 ; y3 7! vRD;;B1 ; y4 7! vSB;;D1 ; y5 7! vRD;;B0 ) involves a cycle in the model, it is not spurious.
Such cycles are recognised by rules (6) and (7). Rule (6) defines potential individual arcs in the cycle with their directionality using fresh predicates AQ with 2 ff; bg. Rules (7) detect the cycles recursively using predicates T Q . Matches involving cycles are marked as spurious by rules (8c). All correct answers are collected by rule (9) using predicate Ans. We next define program PQ and its extension PO;Q with EO in Def. 4, which can be exploited to answer Q w.r.t. O.
Definition 5. Let Q = 9~y: (~x; ~y) be a CQ, let QM, sp, and fk be fresh predicates of arity j~xj + j~yj, let id, AQ , and T Q , with 2 ff; bg, be fresh predicates of arity j~xj + j~yj + 2, let Ans be a fresh predicate of arity j~xj, let named be a fresh unary predicate, and let U be a set of fresh variables s.t. jU j j~yj. Then, PQ is the smallest program with all rules in Table 2, and PO;Q is defined as EO [ PQ.
Note that, to distinguish between constants in O (recorded by named in PQ) and their closure under equality (recorded by NI in EO), we do not axiomatise equality w.r.t. PQ. Theorem 4. (i) PO;Q is stratified; (ii) M [PO;Q] is polynomial in jOj and exponential in jQj; and (iii) if O is satisfiable, ~x 2 cert(Q; O) iff PO;Q j= Ans(~x).
Theorem 4 suggests a worst-case exponential algorithm that, given O and Q, materialises PO;Q and returns the extension of predicate Ans. This procedure can be modified to obtain a ‘guess and check’ algorithm applicable to BCQs. This algorithm first materialises EO in polynomial time; then, it guesses a match to Q over the materialisation; finally, it materialises (PO;Q) , where variables ~x and ~y are grounded by . The latter step can also be shown to be tractable.
Theorem 5. Checking whether O j= Q is NP-complete in combined complexity. 5
We implemented our approach using the DLVsystem,6 which supports function
symbols and stratified negation. For testing, we used the LUBM ontology [
and Uniprot come with large datasets, which we sampled. Test queries are given in the appendix. We measured (M1) number of facts of the given data; (M2) materialisation times for the canonical model; (M3) model size; (M4) materialisation times for PQ; (M5) number of candidate query answers; and (M6) percentage of spurious answers. Experiments were performed on a MacBook Pro laptop with 8GB RAM and an Intel Core 2.4 GHz processor.
Table 3 summarises our results. Computation times for the models scale linearly in
data size. Model size is at most 6 times larger than the original data, which is a
reasonable growth factor in practice. As usual in combined approaches (e.g. see [
We presented an extension to the combined approaches to CQ answering that can be applied to a wide range of out-of-profile Horn ontologies. Our theoretical results unify and extend existing techniques for E LHO and DL-LiteR in a seamless and elegant way. Our preliminary experiments indicate the feasibility of our approach in practice.
We anticipate several directions for future work. First, we have not considered logics
with transitive roles. Recently, it was shown that CQ answering over EL ontologies with
transitive roles is feasible in NP [