Inconsistency-Tolerant Ontology-Based Data Access Revisited: Taking Mappings into Account

1 Introduction

Ontology-based data access aims to improve access to data (typically stored in a relational database) by using an ontology to provide a conceptual view of the data that describes the semantic relationships holding between different terms [Poggi et al., 2008]. As the ontology usually introduces a more convenient high-level vocabulary that abstracts from the way data is stored, mappings are used to relate the terms in the ontology with the relations in the database. The user query is formulated using the ontology vocabulary, and query answers are computed by combining the information from the data, the mapping, and ontology. Most of the work on OBDA considers ontologies expressed using description logics (DLs) [Baader et al., 2017]. The DL-Lite family of DLs [Calvanese et al., 2007; Artale et al., 2009] has been shown to be especially well suited for OBDA, as it is possible for query answering to be reduced, via query rewriting and unfolding, to query evaluation over relational databases.

The focus of this paper is on handling data inconsistencies in OBDA. It is widely acknowledged that real-world data suffers from numerous data quality issues, and errors in data are frequent. In the OBDA setting, such errors can lead to logical contradictions, in which case standard OBDA semantics (based upon classical first-order logic) trivializes. Fixing the errors by making changes to the underlying data is typically impossible, as we often do not have permission to modify the data (and even if we do, it may not be clear which modifications should be made). A solution is to adopt inconsistencytolerant semantics, which allow meaningful answers to be obtained from inconsistent data.

The problem of querying inconsistent data using alternative semantics has been extensively studied by the database community, under the name of consistent query answering [Arenas et al., 1999; Bertossi, 2011; Chomicki, 2007]. In the database setting, inconsistencies arise from violations of integrity constraints, and a repair is a database that satisfies the constraints and differs minimally from the original database. Various notions of repairs have been considered, among them, subset repairs (⊆-repairs), which are maximal consistent subsets of the database, and symmetric difference repairs (⊕- repairs), which may both add and delete facts and minimize the set of such changes. Consistent query answering semantics returns those query answers that hold in every repair.

The topic of inconsistency-tolerant query answering has been recently taken up by the DL community, and the last few years have seen a flurry of activity, with proposals of different inconsistency-tolerant semantics [Lembo et al., 2010; Bienvenu and Rosati, 2013], extensive studies of the complexity of query answering under said semantics [Rosati, 2011; Bienvenu, 2012], and some first implemented systems [Bienvenu et al., 2014; Lembo et al., 2015; Tsalapati et al., 2016]. We refer the reader to the survey [Bienvenu and Bourgaux, 2016] for an overview and further references. However, all of these works focus on a simplified version of OBDA, in which the data is given as a set of ABox facts using the vocabulary of the ontology (aka TBox). The question of how to define repairs in the full OBDA setting with mappings, and how the presence of mappings and type of repair affects the complexity of query answering have not yet been addressed.

The present paper constitutes a first study of full-fledged inconsistency-tolerant OBDA. We begin by proposing a notion of OBDA repair, which is defined at the level of the database, with the mapping and ontology serving to define consistent instances. As the repairs involve modifications of the database, we in fact consider two notions: ⊆-repairs and ⊕-repairs. We then show how to transfer existing repairbased semantics to our setting. We consider three such semantics: AR semantics (the DL name for consistent query answering semantics), brave semantics (the dual of AR, which requires a query to hold in some repair), and IAR semantics (a strengthening of AR semantics, which queries the intersection of all repairs).

We perform a detailed study of the data complexity of OBDA under these semantics. We show results both for DLLite and for the general class of 'data-tractable' DLs, i.e. DLs for which consistency checking and query answering are in PTIME for data complexity. This class includes DLs of the EL family [Baader et al., 2005] as well as more expressive Horn DLs like Horn-SHIQ [Eiter et al., 2008]. Mappings in OBDA typically take the form of global-as-view (GAV) mappings. For this initial study, we consider two forms of GAV mappings, one which only allows positive atoms in mapping bodies and a more expressive form of GAV mapping whose bodies can contain negated atoms and inequalities. Mappings with complex bodies (in particular, negated atoms) are supported by existing OBDA systems and have been shown to be useful in applications of OBDA (see discussion in Section 6).

Our data complexity results are summarized in Figure 1. For GAV mappings without negated atoms, we obtain precisely the same complexity as in the simple OBDA setting without mappings, and in particular, the tractability results for DL-Lite under IAR and brave semantics are preserved. By contrast, for the richer form of GAV mappings with negation, there is a sharp increase in complexity, with all problems moving to the second level of the polynomial hierarchy. Interestingly, although they require different techniques, ⊆-repairs and ⊕-repairs also yield the same complexity.

2 Preliminaries

We recall basic notions about relational databases, description logics, and ontology-based data access (OBDA).

Databases A database signature ΣDB consists of a finite set of relation symbols, each with an associated arity. A database instance over signature ΣDB (or ΣDB-instance) is a finite set of facts of the form P(c1, . . . , cn), where P ∈ ΣDB is an n-ary relation symbol, and c1, . . . , cn are constants. Every instance D corresponds to a finite first-order logic interpretation, whose domain contains the constants in D and which interprets relation P as {⃗c | P(⃗c) ∈ D}.

We consider three types of atoms: relational atoms of the form P(t1, . . . , tn), equality atoms of the form t1 = t2, and inequality atoms t1 ̸= t2, where the terms ti are either constants or variables. A first-order query (FO-query) is a first-order formula built up from such atoms using the usual Boolean connectives (∧, ∨, ¬) and quantifiers (∀, ∃). We will consider several types of FO-queries. Conjunctive queries (CQs) are existentially quantified conjunctions of relational atoms. Conjunctive queries with inequality (CQ̸=s) additionally allow for inequality atoms. Conjunctive queries with safe negation (CQ¬s) extend CQs with negated relational atoms, but require that every variable that appears in a negated relational atom also appears in a positive relational atom. We use CQ¬,̸= to refer to CQs with both inequalities and safe negation. Unions of conjunctive queries (UCQs) are disjunctions of CQs such that every disjunct has the same set of free variables. We can define in the same manner UCQ̸=s and UCQ¬,̸=s. A query is Boolean if it contains no free variables. A Boolean query q is satisfied by instance D, written D |= q, if q evaluates to true in the interpretation corresponding to D.

Integrity constraints express properties that database instances should satisfy. Universal constraints take the form ∀⃗x (α1 ∧ . . . αn ∧ ε → β1 ∨ . . . ∨ βm) where the αi and βj are relational atoms all of whose terms belong to ⃗x, and ϵ is a (possibly empty) conjunction of inequality atoms. Denial constraints are a subclass of universal constraints in which the right-hand side of the implication is empty, denoted ⊥. Note that denial constraints capture functional dependencies (FDs) and key constraints, two common forms of constraints. An instance D satisfies a set of constraints C, written D |= C, if every constraint in C evaluates to true in the interpretation corresponding to D. A database instance D is consistent w.r.t. C if D |= C, and inconsistent otherwise.

Description Logics A DL knowledge base (KB) consists of an ABox and a TBox, which are constructed from a set NC of concept names (unary relation symbols) and a set of NR of role names (binary relation symbols). The ABox (dataset) is a finite set of facts of the forms A(a) and R(a, b), with A ∈ NC and R ∈ NR. The TBox (ontology) consists of a finite set of axioms whose form depends on the chosen DL.

We will be particularly interested in DLs from the DLLite family. The core DL-Lite language allows only for concept inclusions B1 ⊑ (¬B2) where each Bi is either some A ∈ NC or ∃P, with P either a role name R or inverse role R-. However, our results will hold for all common DL-Lite dialects, including ones whose TBoxes allow for role inclusions, or functionality assertions [Calvanese et al., 2007].

Another DL we will consider is EL⊥ [Baader et al., 2005], whose TBoxes consists of concept inclusions C ⊑ D, where C, D are complex concepts formed according to the grammar C := ⊤ | ⊥ | A | ∃R.C | C ⊓ C, where A ∈ NC and R ∈ NR. We observe that EL⊥ can express atomic concept disjointness using inclusions of the form A ⊓ B ⊑ ⊥ (which is equivalent to the DL-Lite axiom A ⊑ ¬B).

The semantics of DL KBs is given by first-order logic interpretations I = (∆I , ·I ), where ∆I is a non-empty domain and ·I maps every A ∈ NC to a unary relation AI ⊆ ∆I and every R ∈ NR to a binary relation RI ⊆ ∆I × ∆I . The function ·I is extended to complex concepts and roles, e.g. ⊥I = ∅ and (C ⊓ D)I = C I ∩ DI . A concept inclusion C ⊑ D is satisfied in I if C I ⊆ DI . A model of a KB 〈A, T 〉 is an interpretation that satisfies all axioms in T and facts in A. We say that 〈A, T 〉 is consistent if it has a model, and otherwise, it is inconsistent, written 〈A, T 〉 |= ⊥.

Querying DL KBs Conjunctive queries are the main query language used to query DL KBs. To simplify the presentation, we focus w.l.o.g. on Boolean CQs. We say that a Boolean CQ q is entailed from a KB 〈A, T 〉, written 〈A, T 〉 |= q, if q is satisfied in every model of 〈A, T 〉.

Query rewriting is a technique that can be used to reduce KB consistency and CQ entailment to database query evaluation. Formally, we say that an FO-query q⊥ is a rewriting of inconsistency w.r.t. T if 〈A, T 〉 |= q iff ADB |= q′ , for every ABox A. Note that here ADB signifies that A is treated like a database instance (i.e. facts not present in A are treated as false). An FO-query q′ is a rewriting of a Boolean CQ q w.r.t. TBox T if 〈A, T 〉 |= q iff ADB |= q′ , for every ABox A.

It is well known that for every DL-Lite TBox T , we can construct a UCQ̸= that is a rewriting of inconsistency, and for every Boolean CQ q, we can construct a UCQ̸= q′ that is a rewriting of q w.r.t. T [Calvanese et al., 2007].

Ontology-based Data Access In OBDA, we have a TBox T , but data is stored in a relational database D, rather than an ABox. Typically, D is formulated using a different signature than T , so a mapping is used to relate D and T . In this paper, we consider two forms of global-as-view (GAV) mappings. A (plain) GAV mapping consists of a set of rules ∀⃗xϕ → γ, where ϕ is a CQ all of whose variables are free and among ⃗x, and γ is either a concept atom A(x) or role atom R(x, x′ ) with x, x′ ∈ ⃗x. GAV¬,̸= mappings are defined similarly, except that ϕ can be a CQ¬,̸=. To simplify the presentation, we will typically omit the initial ∀⃗x when writing mappings.

We use the term OBDA specification to refer to a triple 〈ΣDB,M, T 〉, consisting of a database signature ΣDB, mapping M, and TBox T ; by restricting to mappings M from the mapping language LM and TBoxes T from the DL LO, we obtain the class of (LM,LO) OBDA specifications. An OBDA instance is also a triple, 〈D,M, T 〉, but with an instance D in the first position. Given an instance D and mapping M, the induced ABox M(D) is the ABox obtained by applying the mapping to D and collecting the resulting facts. More precisely, for every ϕ → γ ∈ M and variable assignment ν such that ν(ϕ) holds in D, the ABox M(D) contains the fact ν(γ) (andM(D) contains only such facts). We say that a CQ q is entailed by an OBDA instance 〈D,M, T 〉, written 〈D,M, T 〉 |= q, if 〈M(D), T 〉 |= q.

When T is a DL-Lite TBox, we can perform query entailment as follows: (1) compute a rewriting q′ of the input query q w.r.t. T , (2) unfold q′ w.r.t.Mto get q′′ , and (3) evaluate q′′ over D. Intuitively, the unfolding of q′ w.r.t. Mworks by replacing each DL atom A(t) or R(t, t′ ) by a disjunction of the mapping bodies that can create the atom. We refer the reader to [Poggi et al., 2008] for more details of the construction of the induced ABox M(D) and the unfolding operation.

Remark 1. When computing the induced ABox M(D), mapping bodies are evaluated using standard (closed-world) database semantics: each database instance corresponds to a single finite interpretation that is intended to provide be (locally) complete. For example, hospital data could be expected to contain a complete list of all diagnoses made within the hospital. The use of a closed-world semantics on the underlying relational data is entirely compatible with the open-world interpretation of the induced ABox. Indeed, ontologies typically introduce new terms, or give a wider meaning to existing terms. For example, diagnoses from the hospital data will be used to populate ontology terms about medical conditions, but will generally only provide a partial view of a patient's medical conditions (as some diagnoses may have made elsewhere, or the patient may have undiagnosed conditions). Importantly, however, because the database relations are intended to be complete, it can be meaningful to use negation in the bodies of mappings, e.g. to identify patients that are not on the opt-in organ donation list.

Complexity We focus on data complexity, which is measured with respect to the size of the data (either a database instance or ABox). We consider the following standard complexity classes: PTIME (solvable in deterministic polynomial time), NP (solvable in non-deterministic polynomial time), coNP (complement is in NP), Σp2 (solvable in non-deterministic polynomial time with access to an NPoracle), and Πp2 (complement is in Σp2 ). We will also mention a circuit complexity class AC0⊆ PTIME. It is known that FO-query evaluation over database instances is in AC0 w.r.t. data complexity.

3 Inconsistency-Tolerant OBDA

As previously mentioned, there is a large body of literature on inconsistency-tolerant query answering over relational databases and DL knowledge bases. In this section, we review the key notions from this body of work and then show how to adapt them to the OBDA setting.

3.1 Database and ABox Repairs

Intuitively, a repair of a database D w.r.t. integrity constraints C is a database that satisfies C and is as close as possible to D. In this paper, we consider two well-studied forms of repairs: symmetric difference repairs (⊕-repairs) and subset repairs (⊆-repairs). Symmetric difference repairs are the most commonly used and are appropriate in settings where both fact insertions and fact deletions can be used to fix constraint violations (i.e., when facts may be both missing or erroneous). Formally, a ⊕-repair of an instance D w.r.t. C is an instance R such that (i) R |= C, and (ii) there is no R′ such that R′ ⊕D ⊊R⊕D andR′ |= C. Here⊕denotes the symmetric difference operation: S1⊕S2 = (S1 \S2)∪(S2 \S1). If only fact deletions are permitted (i.e. constraint violations are due to the presence of erroneous facts, rather than missing facts), we can use ⊆-repairs instead: R is a ⊆-repair of D w.r.t. C iff (i) R ⊆ D, (ii) R |= C, and (iii) there is no R′ such that R ⊊ R′ and R′ |= C. We use Rep⊕(D, C) and Rep⊆(D, C) to denote the sets of ⊕- and ⊆-repairs, respectively.

In the DL setting, we have the corresponding notion of ABox repair, first proposed in [Lembo et al., 2010]. Formally, an ABox repair of an ABox A w.r.t. a TBox T is an ABox R ⊆ A such that (i) 〈R, T 〉 ̸|= ⊥ and (ii) there is no R′ such that R ⊊ R′ and 〈R′ , T 〉 ̸|= ⊥. Note that in contrast to the database setting, adding facts to an ABox can never restore consistency, which is why it only makes sense to consider repairs that are subsets of A. We will use ARep(A, T ) to refer to the set of repairs of A w.r.t. T .

In this paper, we consider three natural repair-based semantics that have been proposed for querying DL KBs. A query is entailed under AR semantics if it is entailed from every ABox repair. The AR semantics essentially corresponds to the standard semantics used for consistent query answering over databases [Arenas et al., 1999] but translated to the DL setting [Lembo et al., 2010]. Under the stronger IAR semantics, put forth in [Lembo et al., 2010], a query is entailed if it is entailed from the intersection of the repairs, i.e. from the 'surest' ABox facts. The weakest reasonable semantics is the so-called brave semantics [Bienvenu and Rosati, 2013], which only requires that a query be entailed from some repair. These semantics can be profitably used together, either to identify query results of different levels of confidence, or to improve efficiency, as the IAR and brave semantics can sometimes be used as tractable upper and lower approximations of AR semantics, see [Bienvenu and Bourgaux, 2016] for discussion. For S ∈ {AR, IAR, brave}, we will use 〈A, T 〉 |=S q for query entailment over DL KB 〈A, T 〉 under S semantics.

To more easily relate semantics based upon ABox, database, and OBDA repairs, we will adopt the notation 1 〈D, C〉 |=r S q, with r ∈ {⊕,⊆} indicating the type of repair, to refer to query entailment using the database analog of semantics S ∈ {AR, IAR, brave}. For S = AR and S = brave, the definition is the same but uses database repairs in place of ABox repairs (when S = AR, this is just the standard consistent query answering semantics). Suitably translating the IAR semantics to the database setting proves more subtle and will be addressed later in the section (Definition 10).

3.2 OBDARepairs

In order to transfer the preceding repair-based semantics to the OBDA setting, we need to formalize what we mean by a repair of an OBDA instance 〈D,M, T 〉. There are two natural options: either we consider the ABox repairs of M(D) w.r.t. T ('map then repair' approach), or we compute repairs of D using the pair (M, T ) to determine consistent database instances ('repair at source' approach).

The 'map then repair' approach has some appealing characteristics, as it leads to repairs preserving more ABox facts and allows us to more easily reuse techniques for querying ABox repairs. Moreover, similar strategies have been employed in the data integration setting [Bravo and Bertossi, 2003; Cal`ı et al., 2003]. However, it has one major disadvantage: as the approach does not keep track of the origins of the mapped facts, it is possible for repairs to contain ABox facts that originate from conflicting database facts.

Example 2. Consider the instance D∗ = {T (a, b, c), U(a, c)}, TBox T ∗ = {∃P ⊑ ¬A}, and mapping M∗ = {U(x, y) → A(x), U(x, y) → B(y), T(x, y, z) → P (x, z), T (x, y, z) → R(y, z)}. The ABox M∗ (D) contains four facts: P(a, c),R(b, c),A(a),B(b). There are two ABox repairs of M(D): R1 drops P(a, c), and R2 drops A(a). Note that B(b) ∧ R(b, c) holds in both repairs, even though B(b) and R(b, c) originate from conflicting facts. If we adopt the 'repair at source' approach, we will have two repairs: S1 = {T(a, b, c)} and S2 = {U(a, c)}, with M(S1) = {P (a, c), R(b, c)} and M(S2) = {A(a), B(b)}.

1 To facilitate comparisons, we are committing an abuse of notation and terminology, as AR and IAR stand for 'ABox Repair' and 'Intersection of ABox Repairs' (conveniently, they also abbreviate the mnemonic 'All Repairs' and 'Intersection of All Repairs').

In a recent work on inconsistency-tolerant data exchange [ten Cate et al., 2016], the authors similarly faced a decision as to whether to define repairs on the source dataset, or to perform the repair on the mapped data. They opt for the former in order to avoid the semantic anomalies that can arise when combining facts derived from conflicting facts.

The preceding considerations lead us to investigate the 'repair at source' approach, which can be formalized as follows:

Definition 3. A database instance R is an ⊕-repair of an OBDA instance 〈D,M, T 〉 if (a) 〈R,M, T 〉 ̸|= ⊥, and (b) there is no R′ with R′ ⊕ D ⊊ R ⊕ D with 〈R′ ,M, T 〉 ̸|= ⊥. An instance R is a ⊆-repair of 〈D,M, T 〉 if (a) R ⊆ D, (b) 〈R,M, T 〉 ̸|= ⊥, and (c) there is no R′ with R ⊊ R′ such that 〈R′ ,M, T 〉 ̸|= ⊥. For r ∈ {⊕,⊆}, we use Repr(D,M,R) to refer to the set of r-repairs of 〈D,M, T 〉.

Remark 4. Another advantage of defining repairs at the level of the database instances is that it is straightforward to integrate database constraints. Indeed, we can easily adapt Definition 3 to the case where the instance comes with a set of integrity constraints C by simply requiring that possible repairs R satisfy R |= C in addition to 〈R,M, T 〉 ̸|= ⊥.

The following easy lemma, an immediate consequence of Def. 3, shows that every ⊆-repair is also a ⊕-repair:

Lemma 5. For every OBDA instance 〈D,M, T 〉: Rep⊆(D,M, T ) ⊆ Rep⊕(D,M, T ).

In general, however, some ⊕-repairs are not ⊆-repairs, as illustrated by the following example:

Example 2 (continued). Reconsider D∗ and T ∗ , but now with the mapping M′ = {T(x, y, z) ∧ ¬N(y) → P(x, y),U(x, y) → A(x)}. There are two ⊆-repairs of 〈D∗ ,M′ , T ∗ 〉: S1 and S2. If we consider ⊕-repairs instead, then we have a third repair S3 = D∗ ∪ {N(b)}. Indeed, by adding N(b), we block the derivation of P (a, b).

3.3 Repair-based Semantics for OBDA

With a notion of repair in hand, we can now define variants of the AR, brave, and IAR semantics for OBDA instances.

Definition 6. Consider an OBDA instance 〈D,M, T 〉, CQ q, and r ∈ {⊕, ⊆}. Then:

• 〈D,M, T 〉 |=r AR q iff 〈M(R), T 〉 |= q for every R ∈ Repr(D,M, T )
• 〈D,M, T 〉 |=r brave q iff 〈M(R), T 〉 |= q for some R ∈ Repr(D,M, T )

Example 7. Consider the OBDA instance with D† = {P(a),R(a), S(a)}, M† = {P(x) → A(x),R(x) → B(x), S(x) → D(x), S(x) ∧ ¬P(x) → E(x)}, and T † = {A ⊑ ¬B,A ⊑ C,B ⊑ C}. The two (⊕- and ⊆-) repairs are: R†1 = {P(a), S(a)} and R†2 = {R(a), S(a)}.

Their induced ABoxes are: M† (R†1 ) = {A(a),D(a)} and M† (R†2 ) = {B(a),D(a),E(a)}. Under brave semantics, A(a),B(a),C(a),D(a), and E(a) can all be derived, while under AR semantics, only C(a) and D(a) are entailed.

The most obvious way of defining the IAR semantics in the OBDA setting would be to consider a query q to be entailed if 〈M(R∩), T 〉 |= q where R∩ = ⋂R∈Repr(D,M,T ) R. Note however that R∩ satisfies a negated fact if the fact is absent from even a single repair, whereas a positive fact must appear in all repairs. To correct this asymmetry and stay closer to the spirit of the original IAR definition, we propose to compute the induced ABox using the negated facts common to all repairs. This can be formalized as follows, where Fs and Fp are intended to contain respectively the set of sure and possible positive facts (i.e. those holding in all / some repair(s)).

Definition 8. Fix two sets of facts Fs ⊆ Fp. A CQ¬,̸= q is satisfied in (Fs,Fp) under variable assignment ν (written (Fs,Fp) |=µ q) if µ satisfies all inequality atoms in q and

• for every positive atom α ∈ q: ν(α) ∈ Fs
• for every negated atom ¬β ∈ q: ν(β) ̸∈ Fp.

Given a GAV¬,̸= mapping M, we define M(Fs, Fp) as the ABox consisting of those facts ν(γ) for which there exists ϕ→ γ ∈Msuch that (Fs,Fp) |=µ ϕ.

Definition 9. Consider an OBDA instance 〈D,M, T 〉 with M a GAV¬,̸= mapping, CQ q, and r ∈ {⊕,⊆}. Then 〈D,M, T 〉 |=r IAR q iff 〈M(R∩,R∪), T 〉 |= q where:

We return to our example to illustrate the IAR semantics.

Example 7 (continued). By intersecting and unioning the repairs of 〈D† ,M† , T † 〉, we get R†∩ = {S(a)} and R†∪ = {P(a),R(a), S(a)}. The ABox M† (R†∩,R†∪) consists of a single fact, D(a). Note that the mapping S(x) ∧ ¬P(x) → E(x) cannot be applied since P(a) ∈ R†∪, whereas E(a) would be entailed with the na¨ıve definition of IAR semantics.

Similar considerations apply when translating the IAR semantics to the database setting, leading us to propose the following definition:

Definition 10. Consider an instance D, set of integrity constraints C, r ∈ {⊕, ⊆}, and UCQ¬,̸= Q = q1 ∨ . . . ∨ qn. Then 〈D, C〉 |=r IAR Q iff (R∩,R∪) |=µ qi for some 1 ≤ i ≤ n and variable assignment µ, where R∩ (resp. R∪) denotes the intersection (resp. union) of all r-repairs of 〈D, C〉.

The next theorem shows that, as one would hope, the semantics we have defined based upon OBDA repairs obey the same relationships as those for ABox repairs. Note that this result crucially depends on the way the IAR semantics is defined; indeed, it does not hold if one adopts the 'na¨ıve' definition (to see why, consider 〈D† ,M† , T † 〉 from Example 7).

Theorem 11. For every OBDA instance Γ, CQ q, and r ∈ {⊕,⊆}: Γ |=r IAR q ⇒ Γ |=r AR q ⇒ Γ |=r brave q. The converse implications do not hold in general.

Proof. The second implication is immediate from Def. 6, and Example 7 prove that the converse implications fail. To show the first implication, suppose 〈D,M, T 〉 |=r IAR q, i.e. 〈M(R∩,R∪), T 〉 |= q, with R∩ and R∪ defined as in Def. 9. To prove 〈D,M, T 〉 |=r AR q, it suffices to show that M(R∩, R∪) ⊆ M(R) for every R ∈ Repr(D,M, T ). Take some R ∈ Repr(D,M, T ) and θ ∈ M(R∩,R∪). By Def. 9, there exists ϕ → γ ∈ M and a variable assignment ν that satisfies the inequality atoms in ϕ and is such that θ = ν(γ) and ν(α) ∈ R∩ (resp. ν(β) ̸∈ R∪) for every positive atom α ∈ ϕ (resp. negated atom ¬β) in ϕ. It follows from the definition of R∩ and R∪ that ν(αi) ∈ R for all 1 ≤ i ≤ n and ν(βi) ̸∈ R for all 1 ≤ i ≤ m. We can therefore apply the same rule to R to get θ ∈ M(R).

The next result shows that the semantics based upon ⊕- repairs are more conservative (i.e. entail fewer queries) than those based upon ⊆-repairs.

Theorem 12. For every OBDA instance 〈D,M, T 〉, CQ q, and S ∈ {AR, IAR}: 〈D,M, T 〉 |=⊕S q implies 〈D,M, T 〉 |=⊆S q. The converse implication do not hold.

Proof. The implication follows from Def. 6 and Lemma 5. To see why the converse implication does not hold, take D = {P(a, a), T(a)}, M = {P(x, y) ∧ ¬S(x, y) → A(x), P(x, y) ∧ ¬S(x, y) → B(y), T(x) ∧ ¬P(x, x) → E(x)}, T = {A ⊑ ¬B}, and q = E(a). There is a single ⊆-repair R1 = {T(a)} with induced ABox {E(a)}, but an additional ⊕-repair R2 = {P(a, a), T(a), S(a, a)} with an empty induced ABox. Thus, for every S ∈ {AR, IAR, brave}, 〈D,M, T 〉 |=⊆S E(a), but 〈D,M, T 〉 |=⊕S E(a).

It follows from Example 2 that the 'map then repair' approach would lead to some queries being entailed that are not entailed w.r.t. our 'repair at source' approach. In the next example, show the opposite, namely that there are queries entailed according to our approach that would not be entailed in the 'map-then-repair' approach, thereby showing that the two approaches are incomparable w.r.t. the set of entailed queries.

Example 13. Consider the OBDA instance with D‡ = {P(a, a), S(a), T(a)}, M‡ = {P(x, y) → A(x), P (x, y) → B(y), S(x) ∧ T (x) ∧ ¬P (x, y) → D(x)}, and T ‡ = {A ⊑ ¬B}. As M‡ (D‡ ) = {A(a),B(a)}, we have 〈M‡ (D‡ ), T ‡ 〉 ̸|=S D(a) for S ∈ {AR, IAR, brave}. However, the single OBDA repair R‡ = {S(a), T(a)} gives rise to the induced ABox {D(a)}, so 〈D‡ ,M‡ , T ‡ 〉 |=r S D(a) for r ∈ {⊆,⊕} and S ∈ {AR, IAR, brave}. We argue that it is reasonable to infer D(a) from this inconsistent OBDA instance. Indeed, as the fact P(a, a) contradicts the specification, it must be false. Thus, the negated fact ¬P(a, a) holds in the correct version of the database, and it can be combined with the (presumed correct) facts S(a) and T(a) to fire the mapping rule S(x) ∧ T (x) ∧ ¬P (x, y) → D(x).

In the next two sections, we will provide algorithms and data complexity results for inconsistency-tolerant OBDA, considering the impact of varying the semantics (AR, IAR, or brave), the type of repair (⊕ or ⊆) and the form of the mapping (GAV or GAV¬,̸=). In addition to deciding query entailment under the three semantics, we will consider the repair checking problem, which as its name suggests, is to check whether a given instance is a repair.

4 Results for GAVMappings

In this section, we describe how we obtain the results for GAV mappings. We begin by observing that when GAV mappings are used, it is sufficient to study ⊆-repairs, as every ⊕-repair is a ⊆-repair. This is essentially a rephrasing of an analogous result for databases with denial constraints and exploits the fact that consistency can never be recovered by adding facts.

Lemma 14. For every OBDA instance 〈D,M, T 〉 withMa GAV mapping, Rep⊆(D,M, T ) = Rep⊕(D,M, T ).

Another easy observation is that when GAV mappings are considered, our way of defining the IAR semantics (Def. 9) coincides with the 'na¨ıve' definition.

Lemma 15. For every OBDA instance 〈D,M, T 〉 with M a GAV mapping, 〈D,M, T 〉 |=⊆IAR q iff 〈M(R∩), T 〉 |= q where R∩ = ⋂R∈Rep⊆(D,M,T ) R.

We next establish the upper bounds in Table 1 for 'PTIME DLs', i.e. DLs for which both consistency and CQ answering are in PTIME for data complexity.

Theorem 16. Let L be a PTIME description logic. Then CQ answering w.r.t. (GAV, L) OBDA specifications is:

• coNP in data complexity, for AR and IAR semantics
• NP in data complexity, for brave semantics.

Proof. The upper bounds for AR and brave semantics are easy and lift the corresponding results for DL KBs.

We first observe that it is in PTIME to recognize ⊆-repairs. Indeed, to show that R is not a repair, it suffices to iterate over all τ ∈ D \ R, and show that some R ∪ {τ} is consistent.

For AR semantics, we can show that 〈D,M, T 〉 ̸|=⊆AR q by guessing R ⊆ D and verifying that (i) R ∈ Rep⊆(D, M, T ), and (ii) 〈M(R), T 〉 ̸|= q. Both checks are in PTIME.

For brave semantics, we can show that 〈D,M, T 〉 |=⊆brave q by guessing R ⊆ D and verifying in PTIME that (i) R ∈ Rep⊆(D,M, T ),, and (ii) 〈M(R), T 〉 |= q.

For IAR semantics, we adapt an upper bound from [Rosati, 2011]. By Lemma 15, 〈D,M, T 〉 |=⊆IAR q iff 〈M(R∩), T 〉 |= q where R∩ = ⋂R∈Repr(D,M,T ) R. To show 〈M(R∩), T 〉 ̸|= q, we guess a subset N ⊆ D as well as a subset R¬τ ⊆ D for every τ ̸∈ D \ N. We then verify that (i) every R¬τ is a repair such that τ ̸∈ R¬τ , and (ii) 〈M(N), T 〉 ̸|= q. It follows from (i) that R∩ ⊆ N, which implies M(R∩) ⊆ M(N ), since M is a GAV mapping. We then use (ii) to get 〈M(R∩), T 〉 ̸|= q.

The preceding upper bounds match existing lower bounds for inconsistency-tolerant query answering over KBs expressed in EL⊥ [Rosati, 2011; Bienvenu and Bourgaux, 2016], one of the simplest PTIME DLs. The next result allows us to transfer these lower bounds to the OBDA setting.

Lemma 17. For every DL L and S ∈ {AR, IAR, brave}, there is a data-independent reduction from CQ answering under S semantics over L knowledge bases to CQ answering under S semantics w.r.t. (GAV, L) OBDA specifications.

Proof. Consider a TBox T with signature Σ, and let Mcopy = {P(⃗z) → P(⃗z) | P ∈ Σ}. As Mcopy(A) = A, we have ARep(A, T ) = Rep⊆(A,Mcopy, T )}. It follows that 〈A, T 〉 |=S q iff 〈A,M, T ′ 〉 |=S q for every query q and S ∈ {AR, IAR, brave} (for IAR, we again use Lemma 15).

It is known that CQ answering under IAR and brave semantics is tractable for DL-Lite knowledge bases [Lembo et al., 2015; Bienvenu and Rosati, 2013], and we will show that these positive results hold also in the OBDA setting with GAV mappings. We start by giving a reduction to inconsistencytolerant query answering in the database setting.

Theorem 18. For every (DL-Lite, GAV) OBDA specification 〈ΣDB,M, T 〉 and every CQ q, there exists a set CM,T of denial constraints and a UCQ̸= Qq such that

for every ΣDB-instance D and S ∈ {AR, IAR, brave}.

Proof. Given a (GAV, DL-Lite) OBDA specification 〈ΣDB,M, T 〉, we proceed as follows:

1. Construct a UCQ̸= Qq such that for every ΣDB-instance D such that 〈D,M, T 〉 ̸|= ⊥: D |= Qq iff 〈D,M, T 〉 |= q.
2. Construct a UCQ̸= Qunsat such that for every ΣDBinstance D: D |= Qunsat iff 〈D,M, T 〉 is inconsistent.

Steps 1 and 2 can be performed by applying existing query rewriting and unfolding procedures (as described in [Poggi et al., 2008; Kontchakov and Zakharyaschev, 2014]), followed by standard equivalence-preserving transformations. To show correctness of the reduction, we use the facts that Rep⊆(D,M, T ) = Rep⊆(D, CM,T ), and that 〈M(R), T 〉 |= q iff R |= Qq, for every repair R.

Next we show that UCQ̸= answering with denial constraints under IAR and brave semantics can be achieved by query rewriting. We do this by adapting a result from [Bienvenu and Rosati, 2013] on CQ answering under brave and IAR semantics for first-order rewritable ontology languages.

Theorem 19. For every data signature ΣDB, set of denial constraints C, S ∈ {IAR, brave}, and UCQ̸= q, there exists a first-order query qS such that 〈D, C〉 |=⊆S q iff D |= qS, for every ΣDB-instance D.

Proof. A result from [Bienvenu and Rosati, 2013] shows that CQ answering under IAR and brave semantics can be reduced to FO-query evaluation for all known FO-rewritable ontology languages. The construction starts with a UCQ̸= Qunsat that identifies inconsistent datasets and a UCQ̸= Qq that is a rewriting of the input query q w.r.t. the ontology. These two queries are then manipulated to obtain FO-queries implementing the IAR and brave semantics. Every set C of denial constraints gives rise to a UCQ̸= QC that holds on instances violating C. We can thus apply the same construction to the input UCQ̸=q and the UCQ̸= QC to obtain FO-queries qIAR and qbrave such that 〈D, C〉 |=⊆S q iff D |= qS, for every ΣDBinstance D and S ∈ {IAR, brave}.

Combining Theorems 18 and 19, we obtain the following.

Corollary 20. CQ answering under IAR and brave semantics is in AC0 for (GAV, DL-Lite) OBDA specifications.

We point out that all upper bounds in this section hold also in the presence of denial constraints over the data signature.

5 Results for GAV¬,̸= Mappings

We next turn to GAV¬,̸= mappings, starting by establishing the complexity of repair checking:

Theorem 21. For every PTIME DL L that can express atomic concept disjointness and every r ∈ {⊆, ⊕}, r-repair checking for (GAV¬,̸=, L) specifications is coNP-complete.

Proof. Membership in coNP can be shown similarly to the GAV case (proof of Theorem 16), and coNP-hardness for ⊕-repairs can be adapted from a similar result for universal constraints [Staworko and Chomicki, 2010].

We thus focus on the lower bound for ⊆-repairs, which is proven by reduction from unsatisfiability of 3CNF formulas. Consider a 3SAT instance ϕ = λ1 ∧ . . . ∧ λn over variables v1, . . . , vm, where λi = ℓi,1 ∨ ℓi,2 ∨ ℓi,3. We use var(ℓ) to refer to the variable of literal ℓ and set sgn(ℓ) = t (resp. sgn(ℓ) = f) if ℓ is a positive (resp. negative) literal. We consider the TBox Tsat = {T ⊑ V, F ⊑ V, T ⊑ ¬F, V ⊑ ¬V ′ , C ⊑ ¬U} and the mapping M that contains:

• At (x) → T (x) and Af (x) → F (x)
• for s ∈ {t, f}: As (x) ∧ ¬Z → V ′ (x)
• for every (s1, s2, s3) ∈ {t, f}3 :
• Z ∧ Ss1s2s3 (x, y1, y2, y3) → C(x)
• Ss1s2s3 (x, y1, y2, y3) ∧¬As1 (y1) ∧ ¬As2 (y2) ∧ ¬As3 (y3) → U (x)

We take the instance Dϕ consisting of the tuples

and let D′ be the restriction of Dϕ to the relations Ss1s2s3 .

We claim that ϕ is satisfiable iff D′ ̸∈ Rep⊆(Dϕ,M, Tsat). Indeed, if ϕ has a satisfying valuation ν, then D′ ∪ {Z} ∪ {At (vj) | ν(vj) = t} ∪ {Af (vj) | ν(vj) = f} is consistent, so D′ is not a repair. Conversely, suppose there is a repair R with D′ ⊊ R′ . Consistency of R implies that for every j, either At (vj) ̸∈ R or Af (vj) ̸∈ R. There exists thus a valuation νR to v1, . . . , vm such that As (vj) ∈ R implies ν(vj) = s. We claim that νR satisfies ϕ. Indeed, R\D′ ̸= ∅, so R contains either Z or a fact of the form As (vj). If Z ̸∈ R and As (vj) ∈ R, then 〈M(R), Tsat〉 entails V (vj) and V ′ (vj), contradicting V ⊑ ¬V ′ . Thus, Z ∈ R, which implies that C(ci) ∈ M(R) for every 1 ≤ i ≤ n. It follows that M(R) cannot contain any U(ci), and thus for every

1 ≤ i ≤ m, there must exist 1 ≤ l ≤ 3, such that R contains As (vk), where vk = var(ℓi,l) and s = sgn(ℓi,l). The latter shows that νR satisfies λi.

We use the preceding result to derive the remaining upper bounds in Figure 1.

Theorem 22. Let L be a PTIME description logic. Then CQ answering w.r.t. (GAV¬,̸=, L) OBDA specifications is:

• Πp2 in data complexity, under AR and IAR semantics
• Σp2 in data complexity, under brave semantics,

for both ⊆- and ⊕-repairs.

Proof. By adapting a result about ⊕-repairs w.r.t. universal constraints [Staworko and Chomicki, 2010], we can show that ⊕-repairs of 〈D,M, T 〉 use only constants from D and are thus of polynomial size in |D|. This makes it possible for us to reuse / adapt the algorithms from the proof of Theorem 16. As repair checking is now coNP-complete (Theorem 21), these algorithms yield membership in Πp2 (resp. Σp2 ) for AR (resp. brave semantics). For the IAR semantics, we need to modify the algorithm as follows. We guess two sets N∩ and N∪, together with a set R¬τ (resp. Rτ ) of facts for each τ ∈ D \ N∩ (resp. τ ∈ N∪). The guessed sets only use constants from D, so are of polynomial size w.r.t. D. We then check that (i) every R¬τ is a repair such that τ ̸∈ R¬τ , (ii) every Rτ is a repair such that τ ∈ Rτ , and (iii) 〈M(N∩,N∪), T 〉 ̸|= q. It follows from (i) and (ii) that R∩ ⊆ N∩ and N∪ ⊆ R∪, which implies that M(R∩,R∪) ⊆ M(N∩,N∪). Combining this with (iii), we obtain 〈M(R∩, R∪), T 〉 ̸|= q.

For DL-Lite ontologies coupled with GAV¬,̸= mappings, it is still possible to proceed by reduction to the database setting if we accept to move to a more expressive class of constraints:

Theorem 23. For every (DL-Lite, GAV¬,̸=) OBDA specification 〈ΣDB,M, T 〉 and every CQ q, there exists a set CM,T of universal constraints and a UCQ¬,̸= q′ such that

for every ΣDB-instance D, semantics S ∈ {AR, IAR, brave}, and r ∈ {⊆, ⊕}.

Proof. We proceed similarly to the proof of Theorem 18. The key difference is that because the mapping bodies can contain negated atoms, the queries Qq and Qunsat from Steps 1 and 2 will take the form of UCQ¬,̸=s rather than UCQ̸=s. Each disjunct of Qunsat can be written as ∧j αj ∧ ∧k ¬βk, with each αj a positive atom or inequality atom, and each βk a positive atom. In Step 3, such a disjunct will be translated into the universal constraint ∧j αj → ∨i βk. Another difference is that for the IAR semantics, we need to work with M(R∩,R∪), so the proof of correctness is a bit more involved.

Although the preceding theorem does not lead to improved upper bounds, it is relevant from the practical viewpoint as it suggests an alternative algorithmic approach.

We now establish matching lower bounds:

Theorem 24. For every PTIME DL L that can express atomic concept disjointness, CQ answering w.r.t. (GAV¬,̸=, L) OBDA specifications is

• Πp2 -hard in data complexity, for AR and IAR semantics
• Σp2 -hard in data complexity, for brave semantics,

for both ⊆- and ⊕-repairs.

Proof. For ⊕-repairs, we can adapt an existing lower bound for query answering under AR semantics w.r.t. universal constraints [Staworko and Chomicki, 2010]. As the reduction uses a ground atomic query, it directly applies to IAR semantics and can be slightly modified to handle brave semantics.

For ⊆-repairs, we give a reduction from ∀∃-QBF validity. Consider a ∀∃-QBF instance Φ = ∀v1, . . . , vk∃vk+1 . . . vm ϕ where ϕ = λ1 ∧ . . . ∧ λn is a 3CNF formula, defined as in the proof of Theorem 21. We use the TBox Tsat from before, and consider the mapping M consisting of:

• for p ∈ {∀, ∃}: At,q (x) → T (x) and Af,q (x) → F (x)
• for s ∈ {t, f}: As,∃ (x) ∧ ¬Z → V ′ (x)
• for every (s1, s2, s3) ∈ {t, f}3 and (p1, p2, p3) ∈ {∀, ∃}3 :
• Z ∧ Ss1p1s2p2s3p3 (x, y1, y2, y3) → C(x)
• Ss1p1s2p2s3p3 (x, y1, y2, y3) ∧¬As1p1 (y1) ∧ ¬As2p2 (y2) ∧ ¬As3p3 (y3) → U (x)
• Z0(x) ∧Z →Q(x)

We consider the following instance DΦ:

where quant(vi) = ∀ when 1 ≤ i ≤ k and quant(vi) = ∃ when k + 1 ≤ i ≤ m.

We claim that Φ is valid iff every R ∈ Rep⊆(Dϕ,M, Tsat) contains Z. First suppose for a contradiction that Φ is valid, but there is a repair R such that Z ̸∈ R. As R is a ⊆- maximal consistent subset, it must contain Z0(a) and all of the Ss1p1s2p2s3p3 -facts, and cannot contain any At,∃ (vj) or At,∃ (vj) facts. Moreover, for every 1 ≤ j ≤ k, exactly one of At,∀ (vj) and At,∀ (vj) belongs to R. We can thus define an assignment ν∀ to v1, . . . , vk by setting ν(vi) = t if At,∀ (vi) ∈ R and ν(vi) = f if Af,∀ (vi) ∈ R. As Φ is valid, there exists an extension ν ′ of ν to the variables vk+1, . . . , vm that satisfies all clauses in Φ. Let R′ be obtained from R by adding Z and all facts As,∃ (vi) such that ν(vi) = s and k + 1 ≤ i ≤ m. It can be verified that R′ is consistent, contradicting the maximal consistency of R. For the other direction, suppose every R ∈ Rep⊆(Dϕ,M, Tsat) contains Z, and consider a valuation ν of the universal variables. Then there exists a repair R such that At,∀ (vi) ∈ R if ν(vi) = t, and Af,∀ (vi) ∈ R if ν(vi) = f. As R is consistent, it contains at most one of At,∃ (vi) and At,∃ (vi) for every k+1 ≤ vi ≤ m. We let ν ′ be a variable assignment to v1, . . . , vk 'induced' by R (observe that ν ′ extends ν). Consider some clause λi. As R contains Z and Ss1p1s2p2s3p3 (ci, u1, u2, u3), C(ci) ∈

M(R), hence U(ci) ̸∈ M(R). It follows that R contains at least one of As1p1 (u1), As2p2 (u2), and As3p3 (u3), from which we can infer that ν ′ satisfies λi.

To complete the proof, we note that for S ∈ {AR, IAR}, 〈DΦ,M, T 〉 |=⊆S Q(a) iff every R ∈ Rep⊆(Dϕ,M, Tsat) contains Z. Indeed, Q(a) holds in the induced ABox just in the case that the repair (or positive intersection of repairs) contains Z0(a) and Z (and Z0(a) holds in every repair). For brave semantics, a similar reduction can be used: it suffices to replace Z0(x) ∧ Z → Q(x) by Z0(x) ∧ ¬Z → Q(x).

We remark that all upper bounds in this section hold also in the presence of universal constraints over the data signature.

6 Discussion and FutureWork

This paper provides a first study of inconsistency-tolerant querying in the OBDA setting, where data are stored in relational databases and linked to the ontology via mappings. Interestingly, while our framework builds upon existing work on querying inconsistent DL KBs, the addition of mappings introduces significant conceptual and computational challenges. Indeed, it is not immediately clear how to appropriately transfer the notion of repairs to the OBDA setting, nor how to define a suitable OBDA analog of the IAR semantics. To justify our proposed definitions, we have exhibited desirable properties that our definitions satisfy but which alternative definitions do not. Our complexity study showed that the inconsistency-tolerant semantics are highly sensitive to the shape of mappings (unlike standard OBDA semantics): while plain GAV mappings do not increase the complexity compared to the mapping-free setting, our three repair-based semantics jump to the second level of the polynomial hierarchy for mappings with negated atoms.

The experience gained in deploying the OBDA paradigm in practical applications has highlighted the need for rich mappings (allowing for complex mapping bodies, with negation, subqueries, and even aggregation), in order to bridge the (often large) semantic gap between the database and ontology vocabularies 2 . For example, in a project on the Italian public debt, the data contained a relation storing all loans and another with all shared loans, and a mapping with negation was required to be able to access single-borrower loans [Antonioli et al., 2014]. It is also relevant to note that the R2RML mapping language 3 (a W3C standard for mapping relational data to RDF), allows for arbitrary SQL expressions in mapping bodies, and R2RML mappings is used by the well-known OBDA systems Ontop [Calvanese et al., 2017] and Mastro 4 .

In future work, we plan to extend our investigation to a wider range of mapping languages (in particular, full R2RML) and to develop practical algorithms. Initially, we plan to focus on DL-Lite ontologies and leverage the reduction to the database setting. We expect that we will be able to exploit some existing algorithms and optimizations from consistent query answering, but we will also need to develop new techniques, in particular, for handling the IAR and brave semantics with constraints, as these semantics are as of yet little explored in the database setting.

2 Here we cite the experience of researchers at DIAG, La Sapienza that have been involved in several industrial OBDA projects in which complex mappings proved indispensable. Riccardo Rosati, personal communication, April 2018.

3 https://www.w3.org/TR/r2rml/

4 http://www.obdasystems.com

Acknowledgments

This work was partially funded by the ANR project GoAsQ (ANR-15-CE23-0022). The author would like to thank the reviewers for insightful remarks that led to examining further properties of the proposed framework.