Ontology-Mediated Queries with Closed Predicates

1 Introduction

The aim of ontology-based data access (OBDA) is to facilitate querying of data that is significantly incomplete and heterogeneous. To account for the incompleteness, OBDA formalisms typically adopt the open world assumption (OWA). In some applications, though, there are selected parts of the data for which the closed world assumption (CWA) is more appropriate. As an example, consider a large-scale data integration application where parts of the data are extracted from the web and are significantly incomplete, thus justifying the OWA, while other parts of the data come from curated relational database systems and are known to be complete, thus justifying the CWA. Another example is given in [Lutz et al., 2013], namely querying geo-databases such as OpenStreetMap in which the geo-data is typically assumed to be complete, thus justifying the CWA, while annotations are significantly incomplete and thus require the OWA.

In this paper, we consider OBDA formalisms where the ontology is formulated in a description logic (DL). Several approaches have been proposed to implement a partial CWA in OBDA and in other forms of DL reasoning [Calvanese et al., 2007b; Donini et al., 2002; Grimm and Motik, 2005; Motik and Rosati, 2010; Sengupta et al., 2011]. A particularly simple and natural one is to distinguish between OWA predicates and CWA predicates (a predicate is a concept name or a role name) and to adopt the standard semantics from relational databases for the latter: the interpretation of CWA predicates is fixed to what is explicitly stated in the data while OWA predicates can be interpreted as any extension thereof [Lutz et al., 2013]. This semantics generalizes both ABoxes as used in conventional OBDA (all predicates OWA) and so-called DBoxes (all predicates CWA) [Seylan et al., 2009].

Closing predicates has a strong effect on the complexity of query answering. In this paper, we concentrate on data complexity, see [Ngo et al., 2015] for an analysis of combined complexity in the presence of closed predicates. The (data) complexity of answering conjunctive queries (CQs) becomes CONP-hard already when ontologies are formulated in inexpressive DLs such as DL-Lite and EL [Franconi et al., 2011] while CQ answering without closed predicates is in AC0 for DL-Lite and in PTIME for EL [Calvanese et al., 2007a; Artale et al., 2009; Hustadt et al., 2005]. Since intractability comes so quickly, from a user's perspective it is not very helpful to analyze complexity on the level of logics, as in the complexity statements just made; instead, one would like to know whether adopting the CWA results in intractability for the concrete ontology and query used in an application. If it does not, there can be considerable benefit in adopting the CWA since it potentially results in additional (that is, more complete) answers and allows to use full first-order (FO) queries for the closed part of the vocabulary (which otherwise leads to undecidability). If adopting the CWA results in intractability, this is important information and the user can decide whether (s)he wants to resort to OWA as an approximation semantics or pay (in terms of complexity) for adopting the (partial) CWA.

Such a non-uniform analysis has been carried out in [Lutz and Wolter, 2012] and in [Bienvenu et al., 2014] for classical OBDA (that is, no CWA predicates) with expressive DLs such as ALC. The former reference aims to classify the complexity of ontologies, quantifying over the actual query: query answering for an ontology O is in PTIME if every CQ can be answered in PTIME w.r.t. O and it is CONP-hard if there is at least one Boolean CQ that is CONP-hard to answer w.r.t. O. In the latter reference, an even more fine-grained approach is taken where the query is not quantified away. It aims to classify the complexity of ontology-mediated queries (OMQs), that is, triples (O,ΣA, q) where O is an ontology, ΣA a data vocabulary, and q an actual query. In both cases, a close connection to the complexity of (fixed-template) constraint satisfaction problems (CSPs) is identified, an active field of research that brings together algebra, graph theory, and logic [Feder and Vardi, 1993; Kun and Szegedy, 2009; Bulatov, 2011]. Such a connection is interesting for at least two reasons. First, it clarifies how difficult it is to attain a full complexity classification of relevant classes of ontologies/OMQs; in fact, there is a large body of literature on classifying the complexity of CSPs that revolves around the FederVardi conjecture which states that every CSP is in PTIME or NP-hard [Feder and Vardi, 1993]. And second, it allows to transfer the technically deep results that have been obtained for CSPs in the last years to the world of OBDA.

For OBDA with closed predicates, the case of quantified queries has been analyzed in [Lutz et al., 2013]. The main finding is that there are transparent and PTIME decidable syntactic conditions that separate the easy cases from the hard cases for ontologies formulated in DL-Lite and in EL (thus the complexity classification is much easier than for CSPs). However, it is also shown that the PTIME cases are exactly those where adopting the CWA does not result in returning additional answers and thus being able to use FO queries on the closed part of the vocabulary is the only benefit. This suggests that an analysis which quantifies over the queries is still too coarse to be practically useful. In the present paper, we therefore consider a complexity analysis on the level of ontology-mediated queries with closed predicates (OMQCs), which are quadruples (O, ΣA, ΣC, q) where O, ΣA, and q are as above and ΣC ⊆ ΣA is a set of closed predicates.

Our main finding is that while classifying the complexity of OMQs with expressive ontologies corresponds to classifying CSPs, classifying OMQCs is tightly linked to classifying surjective CSPs. The latter are defined exactly like standard CSPs (with fixed template) except that homomorphisms are required to be surjective. What might sound like a minor change actually makes complexity analyses dramatically more difficult. In fact, there are concrete surjective CSPs of size 6 whose complexity is not understood [Bodirsky et al., 2012] while there are no such open cases for standard CSPs. Like standard CSPs, the complexity of surjective CSPs is currently subject to significant research activities [Bodirsky et al., 2012; Chen, 2014]. Unlike for standard CSPs, though, we are not aware of dichotomy conjectures for surjective CSPs, this kind of question appears to be wide open.

Our connection to surjective CSPs concerns OMQCs where the ontology is formulated in any DL between DL-Litecore and ALCHI or between EL and ALCHI, where only concept names (unary predicates) can be closed, and where the actual queries are tree-shaped unions of conjunctive queries (tUCQs). We find it remarkable that there is no difference between classifying OMQCs based on extremely simple DLs such as DL-Litecore and rather expressive ones such as ALCHI. For the case where also role names (binary predicates) can be closed, we show that for every NP Turing machine M, there is an OMQC that is polynomially equivalent to the complement of M's word problem and where the ontology can either be formulated in DL-Lite or in EL (and queries are tUCQs). In the case of closed role names, there is thus no dichotomy between PTIME and CONP (unless PTIME = NP) and a full complexity classification does thus not appear feasible with today's knowledge in complexity theory.

We start in Sections 2 and 3 with formally introducing our framework and establishing some preliminary results. In Section 4, we identify a large and practically useful class of OMQCs that are tractable and even FO-rewritable; ontologies in these OMQCs are formulated in DL-LiteR, both concept and role names can be closed, and queries are quantifier-free UCQs. In Section 5, we establish the connection to surjective CSPs for the case where only concept names can be closed (and where quantifiers in the query are allowed) and in Section 6 we establish the connection to Turing machines when also role names can be closed.

Proof details can be found in the appendix which is available at http://informatik.uni-bremen.de/tdki/p.html.

2 Preliminaries

Let NC, NR, and NI be countably infinite sets of concept, role, and individual names. A DL-Lite concept is either a concept name or a concept of the form ∃r or ∃r- with r ∈ NR. We call r- an inverse role and set s- = r if s = r- and r ∈ NR. A role is of the form r or r-, with r ∈ NR. A DL-Lite concept inclusion is of the form B1 ⊑ B2 or B1 ⊑ ¬B2, where B1, B2 are DL-Lite concepts. A role inclusion is of the form r ⊑ s, where r, s are roles. A DL-Litecore TBox is a finite set of DL-Lite concept inclusions and a DL-LiteR TBox might additionally contain role inclusions [Calvanese et al., 2007a; Artale et al., 2009]. As usual in DLs, we use the terms TBox and ontology interchangeably.

EL concepts are constructed according to the rule C, D := ⊤ | A | C ⊓ D | ∃r.C, where A ∈ NC and r ∈ NR. ELI concepts extend EL concepts by adding existential restrictions ∃r-.C, where r- is an inverse role, and ALCI further allows negation. For L ∈ {EL, ELI,ALCI}, an L concept inclusion is of the form C ⊑ D, where C, D are L concepts. An EL TBox is a finite set of EL concept inclusions, and ELI TBoxes are defined accordingly. An ALCHI TBox consists of ALCI concept inclusions and role inclusions. An ABox is a finite set of concept assertions A(a) and role assertions r(a, b) with A ∈ NC, r ∈ NR, and a, b ∈ NI. We use Ind(A) to denote the set of individuals used in the ABox A.

An interpretation I (defined as usual) satisfies a concept inclusion C ⊑ D if C I ⊆ DI , a role inclusion r ⊑ s if rI ⊆ sI , a concept assertion A(a) if a ∈ AI and a role assertion r(a, b) if (a, b) ∈ rI . Note that this interpretation of ABox assertions adopts the standard names assumption (SNA) which requires that aI = a for all a ∈ NI and implies the unique name assumption (UNA). An interpretation is a model of a TBox T if it satisfies all inclusions in T and a model of an ABox A if it satisfies all assertions in A. As usual, we write T |= r ⊑ s if every model of T satisfies the CI r ⊑ s (which can be checked in polytime).

A predicate is a concept or role name. A signature Σ is a finite set of predicates. The signature sig(C) of a concept C, sig(r) of a role r, and sig(T ) of a TBox T , is the set of predicates that occur in C, r, and T , respectively. An ABox is a Σ-ABox if it only uses predicates from Σ.

In this paper, we combine ontologies (that is, TBoxes) with database queries. A conjunctive query (CQ) takes the form q(⃗x) = ∃⃗y ϕ(⃗x, ⃗y) where ϕ(⃗x, ⃗y) is a conjunction of atoms of the form A(x) and r(x, y) with A ∈ NC and r ∈ NR. We call ⃗x the answer variables of q(⃗x). A tree CQ (tCQ) is a CQ that is a tree when viewed as a directed graph (multi-edges disallowed) with the root the only answer variable. An atomic query (AQ) is a CQ of the form A(x). A CQ is Boolean when it has no answer variables. We use BtCQ to refer to Boolean tCQs. A Boolean AQ (BAQ) has the form ∃xA(x). A union of conjunctive queries (UCQ) is a disjunction of CQs. Additional query classes such as tUCQ and BtUCQ are then defined in the obvious way, demanding that every CQ in the UCQ is of the expected form. The length |q| of a UCQ q is the number of its variables.

In this paper, the general type of query that we are interested in are ontology-mediated queries with closed predicates (OMQCs) that consist of a TBox T , a set ΣA of predicates that can occur in the ABox, a set of closed predicates ΣC ⊆ ΣA, and an actual query q (such as a UCQ) that is to be answered. The semantics of such queries is as follows. A model I of an ABox A respects closed predicates ΣC if the extension of these predicates agrees with what is explicitly stated in the ABox, that is,

AI = {a | A(a) ∈ A} for all A ∈ ΣC ∩ NC rI = {(a, b) | r(a, b) ∈ A} for all r ∈ ΣC ∩NR.

Let Q = (T ,ΣA,ΣC, q) be an OMQC and A a ΣA-ABox. A tuple ⃗a ∈ Ind(A) is a certain answer to Q on A, written T ,A |=c(ΣC) q(⃗a), if I |= q[⃗a] for all models I of T and A that respect ΣC.

Example 1. Assume an automobile company (say Skoda) wants to monitor the model ranges of international automobile manufacturers. It integrates its company databases storing information about its own products with information about other manufacturers extracted from the web. An ontology is used to provide a unifying vocabulary to be used in queries and to add background knowledge such as

SkodaModel ⊑ ∃has engine.SkodaEngine TeslaModel ⊑ ∃has engine.TeslaEngine DieselEngine ⊑ ICEngine PetrolEngine ⊑ ICEngine

where IC stands for internal combustion. Assume that all data is stored in an ABox, which contains information about Skoda models:

SkodaModel(sm1), SkodaModel(sm2), . . . SkodaEngine(se1), SkodaEngine(se2) . . . has engine(sm1, se1), . . . DieselEngine(se1), PetrolEngine(se2), . . .

and about models by other manufacturers:

TeslaModel(tm1), . . . TeslaEngine(te1), ElectEngine(te1), . . .

Skoda is sure that its own models and engines are in the database, therefore the concept names SkodaModel and SkodaEngine are closed. As information about other manufacturers is taken from the web, it is assumed to be incomplete. To illustrate the effect of closing these predicates, consider the following query q1(x):

∃y(SkodaModel(x) ∧ has engine(x, y) ∧ ICEngine(y)).

Assume that sm17 is a new Skoda model for which an existing engine will be used, but it is not yet decided which one. Thus the data only contains SkodaModel(sm17), but no other assertions mentioning sm17. Note that Skoda offers only petrol and diesel engines and that Tesla offers only electric engines which is both reflected in the data (e.g, for every assertion TeslaEngine(tei), there is an assertion ElecEngine(tei)). Due to the knowledge in the ontology and since SkodaEngine is closed, sm17 is returned as an answer to q1. This is not the case without closed predicates and it is in this sense that closed predicates can result in more complete answers. In particular, the query

∃y(TeslaModel(x) ∧ has engine(x, y) ∧ ElectEngine(y))

does not return tm4 if the ABox only contains TeslaModel(tm4), but does not associate tm4 with any specific engine.

An OBDA language is constituted by a triple (L,Σ,Q) that consists of a TBox language (such as DL-Litecore, EL, or ALCHI), a set of predicates Σ (such as NC ∪ NR or NC) and a query language Q (such as UCQ or CQ). It comprises all OMQCs (T ,ΣA,ΣC, q) such that T ∈ L, ΣC ⊆ Σ, and q ∈ Q. Examples of OBDA languages considered in this paper include, for example, (DL-LiteR,NC ∪ NR, BtUCQ) and (ALCHI, NC, BtUCQ).

For an ABox A, we denote by IA the interpretation corresponding to A, which satisfies ∆IA = Ind(A) and is defined in the obvious way. An OMQC Q = (T , ΣA, ΣC, q) is FO-rewritable if there is an FO-query ϕ(⃗x) such that for all ΣA-ABoxes A and all tuples ⃗a of individuals from Ind(A), we have IA |= ϕ(⃗a) iff T ,A |=c(ΣC) q(⃗a). Here and throughout the paper, we assume that FO-queries use only atoms of the form A(x), r(x, y), and x = y where A is a concept name and r a role name.

In many applications, it is useful to identify and report inconsistencies of the data with the ontology. An ABox A is consistent w.r.t. T and closed ΣC if there is a model of T and A that respects ΣC. We say that ABox consistency is FOrewritable for an OMQC (T ,ΣA,ΣC, q) if there is a Boolean FO-query ϕ such that for all ΣA-ABoxes A, we have IA |= ϕ iff A is consistent w.r.t. T and closed ΣC.

3 Basic Results

We establish some basic results that set the stage for the rest of the paper. The first one is a general CONP upper bound (in data complexity) that encompasses all OMQ languages studied in this paper. Note that this bound is not a consequence of results on OBDA querying with nominals [Ortiz et al., 2008] because nominals are part of the TBox and thus their number is a constant while closing a predicate corresponds to considering a set of individuals whose number is bounded by the size of the ABox (the input size). The proof uses a decomposition of countermodels (models that demonstrate query non-entailment) into mosaics and then relies on a guessand-check algorithm for finding such decompositions.

Theorem 2. Every OMQC in (ALCHI,NC ∪ NR,UCQ) is in CONP.

Our next result concerns the relationship between ABox signatures and closed predicates. In the cases relevant for us, we can assume w.l.o.g. that the ABox signature and the set of closed predicates coincide. This setup was called DBoxes in [Seylan et al., 2009; Franconi et al., 2011]. In the remainder of the paper, we are thus free to assume that OMQCs (T , ΣA, ΣC, q) satisfy ΣA = ΣC whenever convenient. We denote such OMQCs as a triple (T , Σ, q) meaning that Σ serves both as ΣA and ΣC. Two Σ-queries Q1 and Q2 are equivalent if Q1(A) = Q2(A) for all Σ-ABoxes A. A class Q of queries is called canonical if it is closed under replacing a concept or role atom in a query with an atom of the same kind. All classes of queries considered in this paper are canonical.

Theorem 3. Let L ∈ {DL-LiteR,ALCHI} and Q be a canonical class of UCQs, or let L ∈ {DL-Litecore, EL} and Q be a canonical class of UCQs closed under forming unions of queries. Then for every OMQC Q = (T , ΣA, ΣC, q) from (L,NC ∪ NR,Q), one can construct in polynomial time an equivalent query OMQC Q′ = (T ′ , ΣA, ΣA, q′ ) with T ′ ∈ L and q′ ∈ Q.

As noted in the introduction, full first-order queries can be used for the closed predicates. This simple observation was already made in [Lutz et al., 2013] in a related but slightly different setup, and we repeat it here for the setup considered in the present paper. Let ΣC be a signature that declares closed predicates and let q = ∃⃗y ϕ(⃗x, ⃗y) be a CQ. An FO(ΣC)-extension of q is a query of the form ∃⃗y∃⃗z ϕ(⃗x, ⃗y)∧ψ1(⃗z1), . . . , ψn(⃗zn) where ψ1(⃗z1), . . . , ψn(⃗zn) are FO-queries with sig(ψi) ⊆ ΣC and ⃗z1 ∪ · · · ∪ ⃗zn ⊆ ⃗x ∪ ⃗y ∪ ⃗z.

Theorem 4. If an OMQC (T ,ΣA,ΣC, q) is FO-rewritable (in PTIME), then every (T ,ΣA,ΣC, q′ ) with q′ an FO(ΣC)- extension of q is also FO-rewritable (in PTIME).

4 Quantifier-Free UCQs and FO-Rewritability

The aim of this section is to identify useful OBDA languages whose UCQs are guaranteed to be FO-rewritable. It turns out that FO-rewritability can be achieved by combining lightweight DLs with quantifier-free queries. We use qfUCQ to denote the class of quantifier-free UCQs, that is, none of the CQs is allowed to contain a quantified variable.

Our main result is that all OMQCs from the OBDA language (DL-LiteR,NC ∪ NR, qfUCQ) are FO-rewritable under the mild restriction that there is no role inclusion which requires an open role to be contained in a closed one. We believe that this class of queries is potentially relevant for practical applications. In fact, DL-LiteR is very popular as an ontology language in large-scale OBDA and, in practice, many queries turn out to be quantifier-free. Note that the query language SPARQL, which is used in many web applications, is closely related to qfUCQs and, in fact, does not admit existential quantification under its standard entailment regimes [Glimm and Kr¨otzsch, 2010]. We remark that our result also covers the OBDA language (DL-Litecore, NC ∪ NR, qfUCQ) without further restrictions.

Theorem 5. Every OMQC (T ,ΣA,ΣC, q) from (DL-LiteR,NC ∪ NR, qfUCQ) such that T contains no role inclusion of the form s ⊑ r with s ̸∈ ΣC and r ∈ ΣC is FO-rewritable.

We first show that ABox consistency is FO-rewritable for each of the OMQCs (T ,ΣA,ΣC, q) covered by Theorem 5. On inconcistent ABoxes, every query returns all possible answers, but in most practical cases it is more useful to detect and point out the inconsistency instead. We assume w.l.o.g. that ΣA = ΣC and denote ΣA by Σ. Let sub(T ) be the set of all concept names in T , their negations, and all concepts ∃r, ∃rsuch that r is a role name that occurs in T . A T -type is a set t ⊆ sub(T ) such that for all B1, B2 ∈ sub(T ):

• if B1 ∈ t and T |= B1 ⊑ B2, then B2 ∈ t;
• if B1 ∈ t and T |= B1 ⊑ ¬B2, then B2 /∈ t.

A T -typing is a set T of T -types. A path in T is a sequence t, r1, . . . , rn where t ∈ T, ∃r1, . . . , ∃rn ∈ sub(T ) use no symbols from Σ, ∃r1 ∈ t and for i ∈ {1, . . . , n - 1}, T |= ∃ri ⊑ ∃ri+1 and ri ̸= ri+1. The path is Σ-participating if for all i ∈ {1, . . . , n - 1}, there is no B ∈ sub(T ) with sig(B) ⊆ Σ and T |= ∃ri ⊑ B while there is such a B for i = n. A T -typing T is Σ-realizable if for every Σparticipating path t, r1, . . . , rn in T , there is some u ∈ T such that {B ∈ sub(T ) | T |= ∃rn ⊑ B} ⊆ u.

A T -typing T provides an abstraction of a model of T and a Σ-ABox A, where T contains the types that are realized by ABox elements. Σ-realizability ensures that we can build from T a model that respects the closed predicates in Σ. To make this more precise, define a T -decoration of a Σ-ABox A to be a mapping f that assigns to each a ∈ Ind(A) a T -type f(a) such that f(a)|Σ = taA|Σ where taA = {B ∈ sub(T ) | a ∈ BIA } and S|Σ denotes the restriction of the set S of concept to those member that only use symbols from Σ. For brevity, let RΣ = {s ⊑ r | T |= s ⊑ r and sig(s ⊑ r) ⊆ Σ}.

Lemma 6. A Σ-ABox A is consistent w.r.t. T and closed Σ iff

1. A has a T -decoration f whose image is a Σ-realizable T -typing and

We now construct the required FO-query. For all role names r and variables x, y, define ψr(x, y) = r(x, y) and ψr-(x, y) = r(y, x). For all concept names A and roles r, define ψA(x) = A(x) and ψ∃r(x) = ∃y ψr(x, y). For each T -type t, set

and for each T -typing T = {t1, . . . , tn}, set

Let R be the set of all Σ-realizable typings and set

Note that the two conjuncts of ΨT ,Σ express exactly Points 1 and 2 of Lemma 6. We have thus shown FO-rewritability of ABox consistency for Q.

Proposition 7. A Σ-ABox A is consistent w.r.t. T and closed Σ iff IA |= ΨT ,Σ.

The next step is to construct an FO-rewriting of Q over ABoxes that are consistent w.r.t. T and closed Σ. If desired, this rewriting can be combined with the one for ABox consistency given above. Due to space limitations and the slightly intricate details of the construction, we only give a rough intuition and defer the details to the appendix.

Whereas the FO-query ΨT ,Σ above is Boolean and identifies ABoxes that have a common model with T , we now aim to construct an FO-formula ϕ(⃗x) (where ⃗x are the answer variables of the actual query q fromQ) such that for all Σ-ABoxes A and ⃗a ∈ Ind(A), we have IA |= ϕ[⃗a] iff there is a common model I of A and T such that there is no homomorphism from some CQ in q to I that takes ⃗x to ⃗a. The desired FOrewriting ΦQ(⃗x) of Q over consistent ABoxes is then simply the negation of ϕ(⃗x). The construction of ϕ(⃗x) is based on an extended notion of T -typing called T , q-typing that provides an abstraction of a model of T and a Σ-ABox A that avoids a homomorphism from ⃗x to certain individuals ⃗a. This finishes the proof of Theorem 5.

We now show that without the restriction on role inclusions adopted in Theorem 5, OMQCs from (DL-LiteR, NC ∪ NR, qfUCQ) are no longer FO-rewritable. In fact, we prove the following, slightly stronger result by reduction from propositional satisfiability.

Theorem 8. There is a DL-LiteR TBox T and set of predicates ΣC such that ABox consistency w.r.t. T and closed ΣC is NP-complete.

We close this section with noting that, for the case of EL and its extensions, quantifier-free queries are computationally no more well-behaved than unrestricted queries; in fact, all hardness results established in the remainder of this paper for EL and its extensions can be adapted to the case of quantifierfree queries.

5 Closing Concept Names: Connection to CSP

We consider OBDA languages that only allow to close concept names, but not role names. Unlike in the previous section, queries admit unrestricted existential quantification. Our main contribution here is to establish a close connection between such OBDA languages based on a wide range of DLs and surjective constraint satisfaction problems. This result implies that a full complexity classification of these two problem classes is intimately related. In fact, a full complexity classification of surjective CSPs is a very difficult, ongoing research effort. As pointed out in the introduction, there are even concrete surjective CSPs whose complexity is unknown and, via the established connection, these problems can be used to derive concrete OMQCs whose computational properties are currently not understood.

We start with introducing CSPs. An interpretation I is a Σ-interpretation if it only interprets symbols in Σ, that is, all other symbols are interpreted as empty. Every finite Σ-interpretation I defines a constraint satisfaction problem CSP(I) in signature Σ: given a finite Σ-interpretation I ′ , decide whether there is a homomorphism from I ′ to I, i.e., a mapping h : ∆I ′ → ∆I such that d ∈ AI ′ implies h(d) ∈ AI and (d, e) ∈ rI ′ implies (h(d), h(e)) ∈ rI . The problem CSP(I)sur is the variant of CSP(I) where we require h to be surjective. Note that we do not consider CSPs with relations of arity larger than two.

We first show that for every problem CSP(I)sur , there is an OMQC Q from (DL-Litecore, NC, BtUCQ) that has the same complexity as the complement of CSP(I)sur , up to polynomial time reductions. Here, the complexity of an OMQC Q = (T , ΣA, ΣC, q) is the complexity to decide, given a ΣA-ABox A, whether T ,A |=c(ΣC) q.

Consider CSP(I)sur in signature Σ. We may assume w.l.o.g. that there is at least one Σ-interpretation J that does not homomorphically map to I. 1 Define the OMQC (T , ΣA, ΣC, q) as follows:

To understand the construction, it is useful to consider the reduction of (the complement of) CSP(I)sur to (T , ΣA, ΣC, q). Given a Σ-interpretation J that is an input to CSP(I)sur , we construct a ΣA-ABox A as an input to (T , ΣA, ΣC, q) as

where AJ is J viewed as an ABox (with the elements of J serving as ABox individuals) and where ad is a fresh individual name for each d ∈ ∆I . We show in the appendix that J ∈ CSP(I)sur iff T ,A ̸|=c(ΣC) q. For the "if" direction, we extract a homomorphism h from a model I ′ of T and A that respects ΣC and satisfies I ̸|= q by setting h(d) = e when (d, ae) ∈ valI ′ . The first line of T and the closing of V thus ensure that h(d) is defined for every d ∈ ∆J and q1 ensures that the value of h(d) is unique; q2 ensures that h is a homomorphism and Line 3 of T together with the closing of A and q3 guarantees that it is surjective. Line 2 of T is only needed for the converse reduction to go through, ensuring that we always consider homomorphisms onto I. We say that two decision problems P1 and P2 are polynomially equivalent if P1 polynomially reduces to P2 and vice versa.

1 Otherwise we can simply use as Q any OMQC (T , Σ, ΣC, q) such that T ,A ̸|=c(ΣC) q for all Σ-ABoxes A. Then CSP(I)sur is exactly the complement problem of Q.

Lemma 9. The complement of CSP(I)sur is polynomially equivalent to (T ,ΣA,ΣC, q).

Note that the same reduction works when DL-Litecore is replaced with EL. For example, the first line of T then reads A ⊑ ∃val.V . Since all disjuncts of q are tree-shaped, we can view them as EL-concepts, extend T with q′ ⊑ A0 for every disjunct q′ of q, and replace q with the BAQ ∃xA0(x). We have thus established the following result.

Theorem 10. For every CSP(I)sur , there is an OMQC Q from (DL-Litecore,NC, BtUCQ) such that the complement of CSP(I)sur has the same complexity as Q, up to polytime reductions. The same holds for (EL, NC, BAQ).

We remark that, as can easily be verified by checking the constructions in the proof of Lemma 9, the complement of CSP(I)sur and Q actually have the same complexity up to FO reductions [Immerman, 1999]. This links the complexity of the two problems even closer. For example, if one is complete for LOGSPACE or in AC0, then so is the other.

We now establish (almost) a converse of Theorem 10 by showing that for every OMQC Q from (ALCHI, NC, BtUCQ), there is a generalized surjective CSP that has the same complexity as the complement of Q, up to polytime reductions. A generalized surjective CSP in signature Σ is characterized by a finite set Γ of finite Σ-interpretations instead of a single such interpretation, denoted CSP(Γ)sur . The problem is to decide, given a Σ-interpretation I ′ , whether there is a homomorphism from I ′ to some interpretation in Γ. Note that, in the non-surjective case, every generalized CSP can be translated into an equivalent non-generalized CSP [Foniok et al., 2008]. In the surjective case, such a translation is not known, so there remains a gap in our analysis. Closing this gap is primarily a (difficult!) CSP question rather than an OBDA question.

Let Q = (T ,ΣA,ΣC, q) be an OMQC from (ALCI,NC, BtUCQ). We assume w.l.o.g. that T contains only a single concept inclusion ⊤ ⊑ CT (plus role inclusions) where CT uses only the constructors ¬, ⊓, and ∃, and that q has the form ∃xA0(x) with A0 occurring in T . The latter is possible since every tCQ q can be expressed as an ALCI concept Cq in an obvious way, and thus when the BtUCQ is q = ∨i ∃xi qi, then we can add Cqi ⊑ A0 to the TBox with A0 a fresh concept name and replace q with ∃xA0(x). We use cl(T ) to denote the set of subconcepts of CT , extended with all concepts ∃s.C such that ∃r.C is a subconcept of CT and r ⊑ s ∈ T , as well as the negations of these concepts. A Q-type is a subset t ⊆ cl(T ) such that for some model I of T and some d ∈ ∆I , we have t = tpI(d) := {C ∈ cl(T ) | d ∈ C I }. Let TP(T ) denote the set of all types for Q. For t, t′ ∈ TP(T ) and a role r, we write t ⇝r t′ if for all roles r with T |= r ⊑ s, we have

• C ∈ t′ implies ∃s.C ∈ t, for all ∃s.C ∈ cl(T ) and
• C ∈ t implies ∃s-.C ∈ t′ , for all ∃s-.C ∈ cl(T ).

A subset T ⊆ TP(T ) is realizable in a countermodel if there is a ΣA-ABox A and model I of T and A that respects closed predicates ΣC such that I ̸|= q and

We define the desired surjective generalized CSP by taking one template for each T ⊆ TP(T ) that is realizable in a countermodel. The signature Σ of the CSP comprises the symbols in ΣA, one concept name A for each concept name in ΣC, and the concept name A0 from q. We assume w.l.o.g. that there is at least one concept name in ΣC and at least one concept name Aopen ∈ ΣA \ ΣC.

Each T ⊆ TP(T ) realizable in a countermodel gives raise to a template IT , defined as follows:

Note that, in IT restricted to domain T, A is interpreted as the complement of A. At each element dA, all concept names except A and A are true, and these elements are connected to all elements with all roles. Intuitively, we need the concept names A to ensure that when an assertion A(a) is missing in an ABox A with A closed, then a can only be mapped to a template element that does not make A true; this is done by extending A with A(a) and exploiting that A is essentially the complement of A in each IT . The elements dA are then needed to deal with inputs to the CSP where some point satisfies neither A nor A. Let Γ be the set of all interpretations IT obtained in the described way.

Lemma 11. (T ,ΣA,ΣC, q) is polynomially equivalent to the complement of CSP(Γ)sur .

We have thus established the following result

Theorem 12. For every OMQC Q from (ALCHI,NC, BtUCQ), there is a (generalized) CSP(Γ)sur in binary signature such that Q has the same complexity as the complement of CSP(Γ)sur , up to polytime reductions.

Again, the theorem can actually be strengthened to state the same complexity up to FO reductions. Note that the DL ALCHI used in Theorem 12 is a significant extension of the DLs referred to in Theorem 10 and thus our results apply to a remarkable range of DLs: all DLs between DL-Litecore and ALCHI as well as all DLs between EL and ALCHI.

6 Closing Role Names: TMEquivalence

We generalize the setup from the previous section by allowing also role names to be closed. Our main result is that for every NP Turing machine M, there is an OMQC in (DL-LiteR,NC ∪ NR, BtUCQ) that is polynomially equivalent to the complement of M's word problem, and the same is true for (EL,NC ∪NR, BAQ). By Ladner's theorem, it follows that there are CONP-intermediate OMQCs in both of the mentioned OBDA languages (unless P = NP) and that a full complexity classification of the queries in these languages is currently far beyond reach.

To establish the above, we utilize a result from [Lutz and Wolter, 2012; Bienvenu et al., 2014] which states that for every NP Turing machine M, there is a monadic disjunctive datalog program of a certain restricted shape that is polynomially equivalent to the complement of M's word problem. It thus suffices to show that for every such datalog program, there is a polynomially equivalent OMQC of the required form. The actual reduction then uses similar ideas as the proof of Theorem 10.

Theorem 13. For every simple disjunctive datalog program Π, there exists an OMQC in (EL, NC ∪ NR, BAQ) that is polynomially equivalent to Π. The same is true for (DL-LiteR, NC ∪ NR, BtUCQ).

The computational status of (DL-Litecore, NC ∪ NR, BtUCQ) remains open. In particular, it is open whether Theorem 13 can be strengthened to this case. We are, however, able to clarify the status of (DL-Litecore, NC ∪ NR, BtCQ), where BtUCQs are replaced with BtCQs. In fact, we show that every OMQC in this language is polynomially equivalent to an OMQC that is formulated in the same language but does not use closed roles. Via the results in Section 5, OMQCs in (DL-Litecore,NC ∪ NR, BtCQ) are thus linked to surjective CSPs.

Theorem 14. For every OMQC in (DL-Litecore,NC ∪ NR, BtCQ) there exists a polynomially equivalent OMCQ in (DL-Litecore, NC, BtCQ).

Interestingly, Theorem 14 can be extended from BtCQs to BtUCQs for the case of ABoxes in which there is at least one assertion for each closed role name. The unrestricted case of (DL-Litecore,NC ∪NR, BtUCQ), though, remains open.

7 Conclusion

Admitting closed predicates in OBDA has significant advantages as it can result in more complete answers and allows to use FO queries for the closed part of the vocabulary. The main results of this paper characterize the computational challenges: for a wide range of DLs, closing concept names corresponds to moving from CSPs to surjective CSPs, while closing role names yields the full computational power of NP. As future work, it would be interesting to exploit closed predicates in OBDA practice. Our results on FO-rewritability of quantifierfree UCQs provide a starting point.