Compiling Model Representations for Querying Large ABoxes in Expressive DLs

1 Introduction

Answering ontology mediated queries (OMQs) has been a very active field of research over the last decade. However, there is a large gap between two main research lines. On the one hand, for the so-called lightweight Description Logics (DLs), algorithms have been developed, improved, and implemented in reasoners, from DL-Lite (e.g., [Calvanese et al., 2005; Rosati and Almatelli, 2010; RodriguezMuro et al., 2013]), to EL [Stefanoni et al., 2014; P´erezUrbina et al., 2010], and other Horn DLs [Eiter et al., 2012b; Ortiz et al., 2011]. Most works use query rewriting approaches, where an OMQ (T , q) comprising of a DL ontology T (a.k.a. TBox) and a query q in a standard language (e.g., conjunctive queries (CQs)) is written into a new query q′ in a target query language. Obtaining q′ may be costly, but it is independent from a concrete dataset (ABox, in DL jargon), and then q′ can be evaluated over any ABox using existing engines for the target language. On the other hand, for expressive DLs containing ALC, most of the research on OMQ answering has had theory-oriented goals, like understanding decidability and worst-case complexity [Lutz, 2008]. Many algorithms employ tools that are not amenable to implementation, like automata [Calvanese et al., 2008; 2014]. Rewritings have been proposed (e.g.,[Bienvenu et al., 2014b; Ahmetaj et al., 2016; Eiter et al., 2012a]) but they appear unpracticable, and to our knowledge, they have not led to implementation attempts. A rewriting into Datalog for SHIQ was implemented a decade ago in the KAON2 reasoner, but only for instance queries. A published extension to CQs did not yield a data-independent rewriting, and was never implemented [Hustadt et al., 2004]. State-of-the-art reasoners for expressive DLs can handle very large ontologies (e.g., Pellet [Sirin et al., 2007], HermiT [Glimm et al., 2014], Konclude [Steigmiller et al., 2014]), but they usually aim at deciding if some model exists, and it remains unclear whether they could be adapted for OMQ answering.

To start bridging this gap, we propose an algorithm for the DL ALCHI that can efficiently compute a representation of a set of models for answering OMQs. A key feature of our approach is that we compromise data independence, and use generic descriptions of the ABoxes of interest. Our contributions can be summarized as follows:

• We propose profile sets as a simple yet general way to describe families of ABoxes. Profiles are combinations of concepts, role domains, and role ranges that an object may be asserted to participate in. We claim that, in many cases, only a moderate number of profiles is relevant, even when the datasets are large, or ontologies are very complex; preliminary experimental evidence backs this claim.
• We provide an algorithm that takes as an input a TBox T in ALCHI, and a set of profiles P, and effectively computes a structure T that represents a set of relevant models, for all knowledge bases of interest, and that can be used for answering OMQs. Specifically, for any ABox A that complies to the description given by P, we can construct from T a set of models of (T ,A) that is sufficient for answering any monotone query preserved under homomorphisms.
• To illustrate the potential of our algorithm for OMQ answering, we consider two kinds of queries: instance queries and reachability queries. For both of them, we provide a rewriting into ASP programs, reducing query answering to cautious entailment over the answer sets of the rewriting.
• Our algorithm supports incremental reasoning for ABoxes: if the model compilation has been obtained for a set of profiles, and a new family of ABoxes becomes of interest,

new profiles can be incorporated easily. The ASP rewriting can also be efficiently updated by adding new rules.

• Experiments carried out with a proof of concept implementation reveal promising results. Indeed, compiling models and rewriting into ASP is feasible even for complex ontologies. Query answering with our ASP rewritings is scalable for large ABoxes, using off-the-shelf ASP solvers.

2 Preliminaries

We briefly recall the syntax and semantics of the DL ALCHI. We assume countably infinite sets NC, NR, and NI of concept names, role names, and individuals. If r ∈ NR, then r and r- are roles; the set of all roles is denoted NR. For readability, r- stands for s whenever r = s- for s ∈ NR. (Complex) concepts are defined as usual: (a) ⊤,⊥ and every concept name A ∈ NC is a concept, and (b) if C,D are concepts and r is a role, then C ⊓D, C ⊔D, ¬C, ∀r.C, ∃r.C are also concepts. A TBox (or, ontology) T is a finite set of axioms of the forms C ⊑D (concept inclusions), where C and D are concepts, and r ⊑ s (role inclusions), where r and s are roles. An ABox A is a finite set of assertions of the forms A(a) (called concept assertion) and r(a, b) (called role assertion), where a, b ∈ NI, A ∈ NC, r ∈ NR. NI(A) denotes the individuals occurring in A. An interpretation I = (∆I , ·I ) consists of a non-empty domain ∆I and a valuation function ·I that maps each individual a ∈ NI to an element aI ∈ ∆I , each A ∈ NC to a set C I ⊆ ∆I , and each r ∈ NR to a set rI ⊆ ∆I ×∆I . The function ·I is extended to all concepts in the usual way [Baader, 2003]. An interpretation I is a model of a TBox T if C I ⊆ DI for each concept inclusion C ⊑ D ∈ T , and rI ⊆ sI for each role inclusion r ⊑ s ∈ T . An interpretation I is a model of an ABox A if aI ∈ C I for each assertion C(a) ∈ A, and 〈aI , bI 〉 ∈ rI for each assertion r(a, b) ∈ A. An interpretation I is a model of (T ,A), if it's a model of both T and A. A TBox or an ABox is consistent (or, satisfiable) if it has some model. For a TBox T , we use ⊑∗T for the transitive closure of the relation {(r, s) | r ⊑ s ∈ T or r- ⊑ s- ∈ T } ∪ {(r, r)|r ∈ NR}.

We write I ▷ J for two interpretations I and J , if there exists a mapping h from ∆I to ∆J such that: (i) d ∈ AI implies h(d) ∈ AJ for all A ∈ NC, and (ii) (d, d′ ) ∈ rI implies (h(d), h(d′ )) ∈ rJ for all r ∈ NR.

Normal FormWe assume w.l.o.g. that TBoxes are normalized so that they only contain axioms of the following forms:

where A,B,Ai,Bi are concept names in NC, ⊤ or ⊥, and r, s are roles. It is well known that by means of fresh concept names any TBox T can be normalized into a TBox T ′ in polynomial time so that (i) the models of T ′ are models of T , and (ii) each model of T can be extended to a model of T ′ .

3 CompilingModels for Families of ABoxes

To describe families of ABoxes, we define profiles.

Definition 1 (Profiles). Concept names in NC, and concepts of the forms ∃r and ∃r- with r ∈ NR are called basic concepts. A profile is a set of basic concepts. Given an ABox A, the profile of a in A is:

A set P of profiles covers A if prof A(a) ∈ P for all a ∈ NI(A). Example 1. Consider the set of profiles P = {p1, p2} with p1 = {A,B, ∃r} and p2 = {A, ∃r-}. Then P covers the ABox A1 = {A(a), B(a), r(a, b), A(b)}, but it doesn't cover A2 = {A(a), r(a, b), A(b)}, as prof A2 (a) = {A, ∃r} ̸∈ P.

In the rest of this section, we assume we are given a fixed TBox T , and a set P of profiles that covers all the ABoxes of interest. We then expand the profiles p ∈ P with concept names A such that, for some A covered by P, and some a with prof A(a) = p, it may be the case that a ∈ AI holds in the models I of (T ,A). Roughly, we first expand each profile with possibly different 'guesses' of concepts that their neighbours may propagate to it, and then partially complete it with concepts inferred from T . This gives us base types, that in the next stage are further expanded to satisfy the axioms in T , or eliminated if we infer that they cannot occur in models. Definition 2. The relevant guesses for a profile p are:

The subsets of the guesses induce base types of p. A type is a set τ ⊆ NC ∪ {⊥, ⊤}. For a type τ , we let

For a profile p, we define its deterministic closure detCl T (p) as the smallest type τ such that (p ∩NC) ⊆ τ, and

For S ⊆ Guess T (p), we let btyp(p, S) = detCl T (p ∪ S). We define base types induced by profiles and sets of profiles.

To understand the relevant guesses, we observe that each ABox A, by asserting specific relations between individuals, stipulates concepts that the individuals will need to participate in to satisfy the axioms in T , particularly the ones of the forms (NF4) and (NF5). For example, assume ∃r.A⊑B ∈ T , if in a concrete A we have r(a, b) ∈ A, then a ∈ BI must hold in any model I of (A, T ) with b ∈ AI . However, this is not enforced if no relations between a and b are asserted in A, or if b turns out not to be an instance of AI . To abstract away from the relations asserted in each concrete ABox, and the specific concepts that the neighbours of an object may satisfy, we take a simple approach: we consider all possible combinations (or 'guesses') of sets of concepts that may be enforced at an individual due to its neighbourhood in A. That is, we reason explicitly about both a ∈ BI and a ̸∈ BI , but only if a participates in a relation r involved in an axiom of the form (NF4) or (NF5). As shown by our experiments (Section 5), despite being quite naive, this approach already leads to manageable type sets for many large ontologies.

Example 2. For our running example, we use the TBox T :

For P from Example 1, we get these guesses and base types:

where τ1 = {A, B}, τ2 = {A, B, C}, and τ3 = {A}.

3.1 Type Table Compilation

The goal of this section is to provide an algorithm that, starting from the base types of P, computes a representation of all the relevant models of the KBs whose ABox is covered by P. We represent models by means of what we call type tables.

Definition 3. For T a set of types, a type table T is a pair (L, S) with S ⊆ T × (NR × NC ) × T, L ⊆ (T × T). We let

A type table T covers a profile p if L(τ) ̸= ∅ for all τ ∈ btypT (p), and it covers a set P of profiles if it covers all p ∈ P. The set TG of good types in T contains each τ such that (i) ⊥ ̸∈ τ , and (ii) there is some τo with τ ∈ L(τ0) and ⊥ ̸∈ τ0.

We let, for each τ ∈ T, and each r ∈ NR:

The algorithm for computing T works as follows:

• (S2) We obtain (Li+1, Si+1) from (Li, Si) by applying one of the following rules:

(rule-mark) If there exists τ, r,B with Si(τ, r,B) ̸= ∅ such that τ ∈ TGi and Si(τ, r,B) ∩TGi = ∅ , then replace each (τ0, τ ) ∈ Li by (τ0, τ ∪ {⊥}), and each (τ, (r,B), τ ′ )∈Si by (τ ∪ {⊥}, (r,B), τ ′ ).

(rule-det) If there exists some (τ0, τ) ∈ Li with det T (τ) ̸⊆ τ and τ ∈ TGi , then replace

(rule-nondet) If there exists some (τ0, τ) ∈ Li with τ ∈ TGi and an axiom A⊑B1 ⊔ · · · ⊔Bn of the form (NF2) in T such that A ∈ τ and {B1, . . . Bn}∩τ = ∅, then replace, for 1 ≤ i ≤ n:

(rule-addSucc) If there exists some (τ0, τ) ∈ Li with τ ∈ TGi and some A ⊑ ∃r.B ∈ T such that A ∈ τ and Si(τ, r, B) = ∅, then let τn = {B ∪ fwd T (τ, r)} and:

(rule-forw) If there exists some (τ, (r,B), τ ′ ) ∈ Si with τ and τ ′ in TGi and fwd T (τ, r) ̸⊆ τ ′ , then we:

If Li(τn) = ∅ then add (τn, τn) to Li, and

replace (τ, (r, B), τ ′ ) in Si by (τ, (r, B), τn).

Otherwise, replace (τ, (r, B), τn) in Si by (τ, (r, B), τ ′ )

for each τ ′ ∈ Li(τn).

(rule-back) If there exists some (τ, (r,B), τ ′ ) ∈ Si with τ

• (S3) If no rules are applicable, the type table (Li, Si) is called T -complete and the algorithm terminates.

The algorithm starts with (L0, S0), and generates (L1, S1), (L2, S2), . . . until a T -complete (Lfin, Sfin) is reached. Intuitively, in Li we keep track of 'fresh' types and how they are modified. Initially, it only contains the base types, and when the algorithm expands some type, the second component of the corresponding pair is modified. For instance, in our running example, L0 = {(τ1, τ1), (τ2, τ2), (τ3, τ3)}. When τ2 is expanded to satisfy C⊑C1⊔C2 into τ21 = {A, B, C, C1} and τ22 = {A,B,C,C2} using rule-nondet, the pair (τ2, τ2) ∈ Li-1 is replaced by {(τ2, τ21), (τ2, τ22)} ⊆ Li.

In S we store links to the types that objects of the current type can use to satisfy the existential axioms. S0 starts empty. When (τ2, τ22) ∈ Li, rule rule-addSucc becomes applicable due to C2 ⊑ ∃r.C, and a new successor for τ22 is created by setting Si+1 = {(τ22, (r,C), τ4)} with τ4 = {B,C}; the fresh type is also added to Li+1, that is, (τ4, τ4) ∈ Li+1. A similar rule application will create a τ5 = {B,D} successor for τ22 and C2 ⊑ ∃s.D. Type τ4 will also be expanded by rule-nondet into τ41 = {B,C,C1} and τ42 = {B,C,C2}, and rule-addSucc will become applicable for the latter and both C2⊑∃r.C and C2⊑∃s.D. However, the fresh successors will be the same as for τ22 and the entries already in the table will be reused. The final Tfin for this example contains:

The rule applications always lead to a T -complete type table, in at most exponential time:

Lemma 1. The number of different tables (Li, Si) that can be produced by the rule applications, and the number of rule applications required to reach a T -complete (Lfin , Sfin ), are bounded by an exponential in T , and by a polynomial in P.

Incremental Reasoning for dynamic ABoxes. Note that if a type table covers P, then it also covers every P′ ⊆ P. Moreover, the information stored in the L table allows us to expand a type table if we need to cover additional profiles, while reusing as much as possible from previous computations. Let T = (L, S) be a T -completed type table, let P be a set of profiles, and let P′ contain those p ∈ P that are not covered by T. Then we can obtain a T -completed type table T′ that covers P by applying exhaustively the rules in (S2) above to (L ∪ (btypT (P′ ) × btypT (P′ )), S).

3.2 Type Tables as Model Representations

In the rest of this section, we assume a given ABox A covered by P, and a T -complete T = (L, S) that covers P.

Different models of (T , A) can be constructed by selecting good types from T. First, the L relation allows us to assign good types to the input profiles.

Definition 4. For p ∈ P, the set of good types for p in T is:

To capture different models of (T , A), we need to consider the different ways of assigning types from GTT(prof A(a)) to the individuals, so that the axioms of the forms (NF4) and (NF5) in T are compatible with the role assertions in A.

Definition 5 (T-assignment). A T-assignment for A is a mapping t that assigns a type from GTT(prof A(a)) to each a ∈ NI(A) so that:

• (t1) for each r(a, b) ∈ A with A ∈ t(b), if ∃s.A⊑B ∈ T for some r ⊑∗T s, then B ∈ t(a), and
• (t2) for each r(b, a) ∈ A with A ∈ t(b), if A⊑ ∀s.B ∈ T for some r ⊑∗T s, then B ∈ t(a).

Note that GTT(prof A(a)) ̸= ∅ for each a ∈ NI(A) is necessary (but not sufficient) for the existence of T-assignments.

Example 3. In our running example, we get:

and there are two possible Tfin-assignments for the ABox A:

We define a special kind of models of (T ,A) that can be constructed by taking A and a T-assignment t, and adding successors according to the S in our type table.

Definition 6. Let t be a T-assignment. An (A, t, T)- interpretation I = (∆I , ·I ) is defined as follows:

• Its domain ∆I is a set of sequences of the form ar1B1τ1 · · · rnBnτn with n ≥ 0, a ∈ NI(A), and for each 0 ≤ i < n, where τ0 denotes t(a), we have (τi, (ri+1, Bi+1), τi+1) ∈ S and τi+1 is in TG.
• NI(A)⊆∆I and for each a∈NI(A) and pair (r,B) with S(t(a), r,B) ̸= ∅, there is exactly one arBτ ∈ ∆I .
• For each a · · · τn ∈ ∆I and pair (r,B) with S(τn, r, B) ̸= ∅, there is exactly one a · · · τnrBτ ′ in ∆I .
• For each a ∈ NI(A), aI = a.
• For each A ∈ NC, AI = {d ∈ ∆I | A ∈ tail(d)}, where tail(d) = t(d) if d ∈ NI, and tail(d) = τn if d = a · · · τn.
• For all r∈NR, rI = {(a, b) | s(a, b)∈Awith s ⊑∗T r} ∪ {(b, a) | s(a, b) ∈ Awith s ⊑∗T r-} ∪ {(d, dsBτ) ∈ ∆I ×∆I | s ⊑∗T r} ∪ {(dsBτ, d) ∈ ∆I ×∆I | s ⊑∗T r-} The set of (A, t, T)-interpretations is denoted modst(A, T), and mods(A, T) denotes the union of modst(A, T) for all t.

Each interpretation in mods(A, T) is a model of (T , A):

Proposition 1. If I ∈ mods(A, T), then I |= (T ,A).

Conversely, every model is reflected in mods(A, T).

Proposition 2. If I |= (T ,A), then there is some J ∈ mods(A, T) such that J ▷ I.

Finally, we remark that, since the algorithm guarantees that good types always have suitable successors in S to continue the model construction, the existence of a T-assignment already implies the existence of an (A, t, T)-interpretation.

Lemma 2. (T ,A) is satisfiable iff A has a T-assignment.

4 Answering Reachability Queries

Our model compilation is sufficient for answering OMQs subject to a reasonable restriction. We call a query q monotone if I ▷ J and I |= q implies J |= q. Practically all families of queries that have been considered in the context of DLs are monotone, including CQs, regular path queries (RPQs), fragments of Datalog, etc. In fact, decidability results for non-monotone OMQs are very limited, e.g., [Guti´errez-Basulto et al., 2015].

Propositions 1 and 2 imply that the models in mods(A, T) are sufficient for answering OMQs (T , q) where q is monotone. However, if q goes beyond instance queries, we still need an algorithm to evaluate q over mods(A, T). For example, if q is a CQ, the algorithm in [Eiter et al., 2012a] assumes a very similar representation of models and could be adapted rather easily. 1 Here we consider a simpler but nevertheless interesting family of queries, that illustrates the usefulness of our model compilation for OMQ answering:

Definition 7. A reachability query (RQ) q takes the form

where r is a (possibly inverse) role, and C is of the form A1 ⊓ · · · ⊓ An with n ≥ 1 and Ai ∈ NC for 1 ≤ i ≤ n. We call x the answer variable of q. An ontology-mediated reachability query (OMRQ) is a pair (T , q) of a TBox T and an RQ q.

Let I be an interpretation, let e1, e2 ∈ ∆I , and let r be a role. We say that e1 r-reaches e2 if there is a sequence d1, . . . , dn of objects from ∆I such that d1 = e1, dn = e2, n ≥ 1, and for each 1 ≤ i < n, (di, di+1) ∈ rI .

We write I |=q(a), if aI r-reaches some d ∈ ∆I with d ∈ C I . We call a ∈ NI an answer to (T , q) over A, and write (T ,A) |=q(a) if I |=q(a) for all I |=(T ,A).

Example 4. Assume we have an ontology describing items in an inventory system. It may contain, e.g., the following:

1 We did not include the adaptation here, since it needs more machinery than what can be included in this paper, and an efficient implementation would still need some care.

Algorithm 1: Retrieve types that reach C through r

input : r,C, T = (L, S) output: set reach[r,C] of types fromTG Let reach[r,C] := {τ|τ ∈ TG and C ∈ τ} Let reach ′[r,C] := reach[r,C] repeat forall τ ∈TG and s, B with s⊑∗T r such that S(τ, s, B) ∩ TG ̸= ∅ do if τ ′ ∈ reach[r,C] for each (τ, (s, B), τ ′ ) ∈ S with τ ′ ∈ TG then reach[r,C] := reach[r,C] ∪ {τ} until reach ′[r,C] = reach[r,C]; return reach[r,C]

as well as the role inclusion hasProcessor ⊑ hasPart. Assume a dataset containing instances of concepts like Phone5 , Tab2 , etc. If the prices of Atom processors increase, we may want to find all items that contain one. It would then be valuable to be able support RQs like (∃y hasPart∗ (x, y),AtomProcessor(y)), which can navigate the hasPart relation to different levels of depth.

We note that in ALCHI, RQs can be reduced to instance queries by modifying the TBox (see [Bienvenu et al., 2014a]), but then the 'expensive' TBox reasoning step would depend on the query. RQs are a restricted case of the well-known RPQs (see e.g., [Bienvenu et al., 2015a; Calvanese et al., 2003; 2002]), and as they are monotone, they can be answered with our model compilation.

Lemma 3. Let (T , q) be OMRQ, P be a set of profiles, and T be a T -complete type table that covers P. Given an ABox A covered by P, and an individual a, we have (T , A) ̸|= q(a) iff there is some I ∈ mods(A, T) such that I ̸|= q(a).

We now provide a technique to decide whether I |= q(a) for all models in mods(A, T). Below, for an interpretation I and d ∈ ∆I , we let typeI (d) = {A ∈ NC | d ∈ AI }. The core component of our technique is Algorithm 1, which runs on T = (L, S). It takes as an input a role r and a concept C = A1 ⊓ · · · ⊓ An, and collects the set reach[r,C] of all the good types τ from T such that each d with typeI (d) = τ r-reaches some d′ ∈ C I , for every I ∈ mods(A, T). For convenience, we write C ∈ τ to denote {A1, . . . , An} ⊆ τ .

Proposition 3. Let τ ∈ TG. Then τ ∈ reach[r,C] iff for every I ∈ mods(A, T) and every d ∈ ∆I , typeI (d) = τ implies that d r-reaches in I some d′ ∈ C I .

Example 5. Let q(x) = ∃y s∗ (x, y),D(y) be a reachability query that we would like to answer against the knowledge base in our running example. After the computation of the Algorithm 1 the reach[s,D] would contain τ22, τ42 and τ5. τ5 would be contained trivially since it already contains D, where as types τ22, τ42 will be added since each of them has an s-successor in the table Sfin that contains the concept D.

To test I |= q(a) for all I ∈ mods(A, T ), we consider a set of ABoxes, which intuitively capture models of modst(A, T )

for the different T-assignments t, and add to them the information from reach[r,C], using a fresh concept name RrC.

Definition 8. Let t be a T-assignment. At is the smallest A ⊆ At such that:

(a1) A(a) ∈ At for all A ∈ t(a) and all a ∈ NI(A).

Let q(x) = ∃y r∗ (x, y), C(y) with C = A1 ⊓ · · · ⊓ An be an RQ. Then At,q is the smallest At ⊆ At,q such that:

Already the ABoxes At suffice for answering instance queries, and the assertions added in At,q correctly capture the entailment of q in all the models in modst(A, T).

Lemma 4. Let α be an assertion and q an RQ. Then:

• I |= α for all I ∈ modst(A, T) iff α ∈ At .
• I |= q(a) for all I ∈ modst(A, T) iff RrC(a) ∈ At,q .

4.1 A Practicable ASP Rewriting

ASP programs. We briefly introduce ASP, for more details refer to [Brewka et al., 2011]. We use an alphabet of unary and binary predicates, which includes NC (unary) and NR (binary), and an infinite countable set of variables V . A term t is a variable x ∈ V or an individual a ∈ NI. Atoms take the form pu(t) or pb(t, t′ ), where t, t′ are terms, pu is a unary predicate and pb a binary one. If the terms in an atom do not contain variables, we say they are ground.

where the hl, . . . hk are the head atoms, and b1, . . . , bm are the body atoms. Among the latter, b1, . . . , bℓ are positive, and bℓ+1, . . . , bm are negative. A rule with no head atoms (i.e., k = 0) is a constraint. A rule p(⃗a) ← consisting of a single ground head is called a fact. A ground program contains only ground atoms. For a programP, its grounding ground(P) is the program obtained by replacing each rule by all its ground instances obtained by applying a substitution, that is, a mapping from variables to individuals.

The semantics of ASP programs is given by Herbrand interpretations, which are sets of ground atoms. Note that ABoxes are Herbrand interpretations, and a Herbrand interpretation becomes an ABox when restricted to atoms over the predicates in NC ∪NR. An answer set (a.k.a. stable model) of P is a Herbrand interpretation M that is a minimal model of the GL-reduct [Gelfond and Lifschitz, 1988] of ground(P) w.r.t. M, obtained by: (i) deleting every rule ρ that contains a negative body atom r(⃗u) with r(⃗u) ∈ M, and (ii) deleting all negated atoms in the remaining rules.

We now provide a rewriting of OMRQs into logic programs that extend Datalog with disjunction and negation under the answer set semantics. In this section we assume a T -complete type table T = (L, S) that covers a given set P containing all the profiles of interest. We show how to obtain a program PT,q such that, for an input ABox A represented as a program PA (see below), the answer sets of PT,q ∪ PA are in close correspondence with the ABoxes At,q , so that answering OMRQs amounts to cautious entailment. As anticipated, the rewriting does not depend on a specific ABox,

∨ t∈GTT(p) type τ (x) ← prof p (x) for each p ∈ P (1) A(x) ← type τ (x) for each τ ∈ TG and each A ∈ τ (2) s(x, y) ← r(x, y) for each r ⊑∗T s (3) ⊥ ← r(x, y), A(y), notB(x) for each ∃r.A⊑B ∈ T (4) ⊥ ← r(x, y), A(x), notB(y) for each A⊑∀r.B ∈ T (5) RrC(x) ← type τ (x) for each τ ∈ reach[r,C] (6) RrC(x) ←A1(x), · · · ,An(x) with C = A1 ⊓ · · · ⊓An(x) (7) RrC(x) ← r(x, y), RrC(y) (8)

but only on a T that covers a set P of profiles, and it can be used for answering q over any ABox that is covered by P.

First we define the program PT comprising the rules (1) - (5) in the upper part of Figure 1. We use names in NC as unary predicates and (possibly inverse) roles in NR as binary predicates. We also use a unary predicate prof p for each p ∈ P and a unary predicate typeτ for each τ ∈ TG. Intuitively, assuming that the fact prof p(a) holds for each a ∈ NI(A) with p = prof A(a), rule (1) guesses assignments of types to individuals. Rules (2) and (3) generate the assertions (a1) and (a2) in At for each guess, while (4) and (5) verify conditions (t1) and (t2) in Definition 5.

For a given RQ q(x) = ∃y r∗ (x, y),C(y), the rules (6) - (8) in the lower part of the figure define the program Pq; generate the assertions (q1) - (q3) in the definition of At,q .

Finally, we represent each given ABox A as a program PA, with facts α ← for all assertions α ∈ A, and facts prof p(a) ← for each a ∈ NI(A) with p = prof A(a). 2

Example 6. Let A, T , T and reach[s,D] be taken from our running example. We get the following ASP rewriting (here we use τi and pi rather than typeτi and prof pi as predicates):

The ASP program PT ∪ Pq ∪ PA has two answer sets: {τ21(a), τ1(b), A(a), B(a), C(a), C1(a), A(b), B(b)}, and

2 We chose to use negation and constraints in the program, but transforming it into plain disjunctive Datalog is easy. Using Datalog rules to infer the facts prof p (a) from an input ABox is also easy.

{τ22(a), τ1(b), A(a), B(a), C(a), C2(a), A(b), B(b).RsD(a)}. Note their correspondence with the T-assignments from Example 3. C(a) is found in all the answers sets, as a is an instance of C. In contrast, q from Example 5 has no certain answers: RsD(a) is in only one answer set, RsD(a) in none.

The answer sets of PT ∪ PA coincide (on the common vocabulary) with the ABoxes At for the different Tassignments. Similarly, the answer sets of PT ∪ Pq ∪ PA coincide with the At,q . From this and Lemma 4 we get:

Theorem 1. Let A be an ABox covered by P.

• For any assertion α, we have (T , A) |= α iff α ∈ M for all answer sets M of PT ∪ PA.
• Given RQ q(x) = ∃y r∗ (x, y), C(y), we have (T , A) |= q(a) iff RrC(a) ∈ M for all answer sets M of PT ∪Pq ∪PA.

5 Implementation and Experiments

We have implemented our approach in a prototype reasoner Mod4Q 3 for the DL ALCH. Given a TBox T and a set P of profiles, the reasoner: (1) transforms T into normal formand drops axioms not in ALCH; (2) computes btypT (P); (3) runs the algorithm described in Section 3.1 to obtain a T -complete type table T that covers P, and (4) generates the ASP program PT ∪PA as described in Section 4.1. If a set of RQs is given, it adds the rules in Pq for each q in the set.

The reasoner can also take a TBox T and an ABox A as an input. In this case, it first extracts the set {prof A(a) | a ∈ NI(A)} of profiles occurring in A, and then executes steps (1)-(3) above. It also generates the program PA for the given A, additionally to PT and possibly Pq. Moreover, the reasoner supports incremental reasoning over ABoxes: if after running over some set P of profiles, an ABox that is not covered by P is given, it detects which individuals have profiles not found in P, and runs the algorithm for these new profiles only, reusing the previous type table.

Mod4Q is written in Java, and uses a PostgreSQL database to store computed type tables for later use. Experiments were run on a PC with an i7 2.4 GHz CPU running 64bit LinuxMint 17, with a JAVA heap space of 12GB. The generated ASP programs were evaluated with Clingo [Gebser et al., 2011]. In all cases, we used the profile set obtained from the ABox, and did the following sets of experiments:

Querying large ABoxes We considered some large realworld data sets, including NPD, a petroleum ontology, IMDb, a film ontology, and MyITS, a transport ontology. The first two were obtained from [Glimm et al., 2017] while the latter from [Bajraktari et al., 2017]. These are shown in Table 1. The time reported for producing PA includes the extraction of P from the ABox, while the time for producing PT includes the full computation of T. Our experiments showed that:

• Very large real-world datasets are covered by small sets of profiles. The upper part of the table shows that the ratio of profiles to individuals found in these ABoxes is very small.
• Our approach to compiling models and rewriting into ASP is feasible even for large ABoxes. The time to compute T and PT is very short. The generated ASP programs are simple and perform well when evaluated with Clingo.

3 http://www.kr.tuwien.ac.at/research/systems/Mod4Q/

• Query answering with our ASP rewritings scales to very large ABoxes. We evaluated two families of queries:

Instance queries: Using the program (PT ∪ PA) and Clingo, we tested for the instances of all concept names in each ontology. This resulted in 370 (MyITS), 333 (NPD) and 84 (IMDb) IQs. The average answer time over all of them is reported in the table. For comparison, we ran the same instance queries using HermiT [Glimm et al., 2014]; it took 4.5 hours for MyITS50, versus 10 minutes accumulated time with our prototype. For all other ontologies, HermiT either timed out after 6 hours, or crashed due to memory exhaustion.

Reachability queries: We generated all RQs paring a role name r and concept name A for which either (a) r occurs in a role assertions in an ABox, and A in a good type matching the profile of an individual in the range of r; or (b) there was an (r, B) entry in the S with A in its end type. Note that for all other pairs, the answers are trivially empty or coincide with the instances of concept A. This resulted in a total of 139 (MyITS), 121 (NPD), and 51 (IMDb) RQs. Answering RQs was on average slightly slower than answering IQs.

Compiling complex ontologies We took the 87 ontologies from the Oxford ontology library 4 that have both ABox assertions, and axioms of the forms NF2, NF4 and NF5. In Figure 2 we can observe that our prototype was successful on roughly 80% of the ontologies (70), while the remaining 17 cases were infeasible since we had ≥ 215 base types for some profiles. For these 70 ontologies, on average the number of profiles per ontology was 10, while the number of base types 24, and the number of computed good types was 23. The time for compiling and producing PT ranged from 171 ms to 14 s, with an average of 1.3 s. We report selected results in Table 2. Our experiments showed that:

4 http://www.cs.ox.ac.uk/isg/ontologies/

• In most cases, the number of base types generated from the profiles used in the ABox is sufficiently small.
• Our model compilation can handle complex ontologies. Both the number of good types in the computed T, and the time required to produce T, were very small even for ontologies with thousands of concept names and axioms.

Not surprisingly, the evaluation on complex ontologies made apparent that, while computing all the base types for the given profiles is feasible in most cases, it is also the main bottle neck of our approach. Indeed, in all cases where our prototype failed to compute the model compilation, there were profiles with over 9 relevant guesses, thus 29 base types. An interesting observation is that some ontologies, like DOLCE21, have a large number of base types, but result in few good types that are often shared by profiles.

6 Discussion and Conclusions

We have presented an algorithm for compiling the models of a set of relevant knowledge bases, which allows to answer OMQs over families of ABox that comply to a given description. We have proposed ASP rewritings that can be executed on standard ASP solvers to efficiently answer instance and reachability queries over large ABoxes. We plan to extend our technique to other families of OMQs, like CQs (using the ideas in [Eiter et al., 2012a]), and RPQs (combining the former with the ideas in [Bienvenu et al., 2015b]); and to more expressive DLs. Transitive and inverse roles can be easily incorporated. Supporting number restrictions seems feasible, albeit technical, while nominals seem more challenging.

As a compromise between data-centric and data-independent reasoning, our techniques work for families of ABoxes, represented by sets of profiles. Despite their simplicity, profiles seem useful, and even large ABoxes seem to use few profiles. This may sometimes be partially explained by automated processes that produce the data (mappings, forms, scripts, etc), which naturally restrict its shape. Investigating this is an interesting path for future research. Currently, the main bottleneck of our algorithm is the computation of 'base types' from profiles, which expands the profiles with sets of guesses. Although the number of guesses was usually small for the considered ontologies, it became unmanageable in roughly 20% of the cases. Investigating more refined alternatives than this naive guessing seems crucial.

Acknowledgments

This work was supported by the Austrian Science Fund (FWF) via projects P30360, P30873, and W1255.