Mapping Repair in Ontology-based Data Access Evolving Systems

1 Introduction

Ontology-based data access (OBDA) is the problem of accessing source databases through the mediation of a conceptual domain view, given in terms of an ontology [Poggi et al., 2008]. A major issue in OBDA concerns the design of a specification and the management of its evolution. An OBDA specification is constituted by an ontology, usually a Description Logic (DL) TBox [Baader et al., 2007], a schema of the source databases, and a mapping specifying the relationship between the data at the sources and the elements of the ontology, which is commonly given as a set of assertions, each one associating a query over the source schema with a query over the ontology. In the following we denote an OBDA specification as J = 〈T , S,M〉, where T is the TBox, S is the source schema, and M is the mapping.

The mapping is certainly the component of the specification that has received so far less attention, and thus consolidated tools for its design and maintenance are currently not available. Mapping design is a time-consuming and complex operation, which in general cannot be totally automatized. Of course, modifying the mapping due to changes in the other components of the specification may result in a time-consuming process as well. We experienced this in various industrial and academic projects. Among them, we mention a collaboration with the Italian Ministry of Economy and Finances, where we had to map a domain ontology with a source database completely independent from it, which caused mapping definition to be particularly complex [Antonioli et al., 2014], and the use cases of the EU project Optique, focused on OBDA for Big Data [Giese et al., 2015], which were particularly challenging with respect to mapping design and analysis.

In this paper we study the evolution of OBDA specifications. We first observe that many approaches exist for both ontology evolution [Zablith et al., 2015] and database schema evolution [Rahm and Bernstein, 2006]. However, to the best of our knowledge, no previous study has analyzed evolution in the presence of a mapping connecting an ontology to a database schema. In this sense, a problem that is close to OBDA is ontology matching and alignment, which is based on the use of a notion of mapping to integrate different ontologies. Several works have studied the problem of repairing inconsistent mappings in this context (e.g., [Jim´enez-Ruiz et al., 2013; Meilicke et al., 2009; Qi et al., 2009]). However, the framework of ontology matching, and in particular the notion of mapping, is very different fromOBDA.

We adopt a mapping-centered notion of OBDA evolution: given an OBDA specification J = 〈T , S,M〉, we want to repair the mapping M given a modification of the TBox T and/or of the source schema S. This is a natural assumption: indeed, the mapping is an information that depends on both the TBox and the source schema, while the TBox and the schema are (at least in principle) semantically independent entities (since the data sources are autonomous systems).

Following the classical approaches to belief revision, we want to find a notion of repair of a mapping that is based on two general principles: (i) it should preserve consistency of the OBDA specification; (ii) it should express minimal change with respect to the initial OBDA specification. With respect to consistency preservation, we adopt a non-classical notion of inconsistency for an OBDA specification, called global mapping inconsistency, recently introduced in [Lembo et al., 2014; 2015]. According to this notion, a mappingM is inconsistent with respect to a TBox T and a source schema S if there exists no instance D for S that activates all the mapping assertions inM, i.e., every query over S appearing inMhas a non-empty answer on D. In the context of OBDA, global mapping inconsistency provides a more meaningful notion of inconsistency than the classical one (which indeed considers all possible source instances): for example, in all the cases when S is a relational schema with standard integrity constraints, the OBDA specification is inconsistent according to the classical semantics iff its TBox is inconsistent (which in turn implies that this notion is trivial for many DLs).

With respect to minimal change, we propose two different notions of repair. The first one, called deletion-based mapping repair (DMR), reflects the simple idea of repairing a mapping through a (subset-)minimal deletion of assertions from the initial mapping. The second notion, called entailment-based mapping repair (EMR), relies on the mapping entailment set (MES). The MES of an OBDA specification J for a mapping language L is a set of mapping assertions in L that are logical consequences of J . Then, the repairs are globally consistent mappings that allow to preserve as much as possible of the initial MES, according to a minimality criterion that formalizes the intuitive principle of preferring insertions over deletions.

Finally, we define and study query entailment under mapping repairs. In particular, we focus on TBoxes specified in DL-LiteR [Calvanese et al., 2007], the logical counterpart of the W3C standard OWL 2 QL [Motik et al., 2009], which is a prominent DL in OBDA, and consider both GAV and GLAV mappings, two classical mapping languages used in data integration and OBDA [Doan et al., 2012; Poggi et al., 2008]. In these settings we provide a number of complexity results on the entailment of conjunctive queries.

2 Preliminaries

Source schemas. A source schema S is a relational schema, possibly equipped with integrity constraints (ICs) [Abiteboul et al., 1995]. A legal instance D for S is a database for S (i.e., a possibly infinite set of ground atoms over S) that satisfies the ICs of S. A source schema S is consistent if at least one legal instance for S exists. If S has no ICs, it is called simple. We adopt standard notions for conjunctive queries (CQs) over relational schemas and with φ(⃗x) we denote a CQ with free variables ⃗x. A Boolean CQ (BCQ) is a CQ without free variables. Given a CQ q over S and a legal instance D for S, eval (q, D) denotes the evaluation of q over D. With a little abuse of notation, we will sometimes treat a CQ q as the set of the atoms in q.

Ontologies. A DL ontology represents knowledge through concepts, denoting sets of objetcs, and roles, denoting binary relationships between concepts, and is constituted by a TBox, i.e., a finite set of intensional assertions, and an ABox, i.e., a finite set of extensional assertions [Baader et al., 2007]. In this paper we focus on DL-LiteR [Calvanese et al., 2007] TBoxes, whose assertions have the following forms

where B1 and B2 are basic concepts, i.e., expressions of the form A, ∃P, or ∃P -, and R1 and R2 are basic roles, i.e., expressions of the form P , or P -, where A and P denote an atomic concept and an atomic role, respectively. Assertions in the left-hand side (resp. right-hand side) are called positive (resp. negative) inclusions. The semantics of DL ontologies is given in the standard way [Baader et al., 2007], and as in the W3C standard OWL 2 [Hitzler et al., 2012], we do not interpret ontologies under the Unique Name Assumption. Given a TBox T , we denote with Mod(T ) the set of models of T , and with T |= α the fact that T entails a sentence or TBox assertion α. A TBox is said inconsistent if Mod(T ) = ∅. A CQ over T is a CQ over the signature of T , i.e., the set of its atomic concepts and roles.

Mappings. A mapping assertion m from a source schema S to a TBox T has the form φ(⃗x) ❀ ψ(⃗x), where φ(⃗x), called the body of m and denoted body(m), and ψ(⃗x), called the head of m and denoted head(m), are queries over S and T , respectively, both with free variables ⃗x, called frontier variables. A mappingM from S to T is a possibly infinite set of mapping assertions from S to T . In this paper, we consider the notable cases in which φ(⃗x) is a CQ, and ψ(⃗x) is either a CQ without constants (GLAV mapping language), or a single-atom query without constants and existential variables (GAV mapping language) [Doan et al., 2012]. Both mappings are special cases of the W3C standard R2RML [Das et al., 2012]. In the following, given a mapping language L, with an L-mapping we mean a possibly infinite subset of L.

We say that a mapping assertion φ(⃗x) ❀ ψ(⃗x) is active on a source instance D if eval (φ(⃗x), D) ̸= ∅. A mapping M is active on D if each m ∈ M is active on D.

OBDA specifications. An OBDA specification is a triple J = 〈T , S,M〉, where T is a TBox, S is a source schema, and M is a mapping between the two, all as aforementioned. The semantics of J is given with respect to a legal instance D for S: a model for J w.r.t. D is a first-order interpretation I that satisfies T and satisfies Mw.r.t. D, i.e., if for each assertion φ(⃗x) ❀ ψ(⃗x) in M and each tuple of constants ⃗t such that ⃗t ∈ eval (φ(⃗x), D), we have that I |= ψ(⃗t). The set of models of J w.r.t. D is denoted with Mod(J , D). Also, we use (J , D) to denote J with source instance D, say that (J ,D) is inconsistent if Mod(J ,D) = ∅, and denote with (J , D) |= α the entailment of a sentence or TBox assertion α by (J , D). Given a mapping assertion m, we say that J |= m if for every legal instance D for S, and every I ∈ Mod(J , D), I satisfies the mapping {m} w.r.t. D. We also say that two mappingsM1 andM2 from S are equivalent with respect to T if the specifications 〈T , S,M1〉 and 〈T , S,M2〉 are equivalent, i.e, Mod(〈T , S,M1〉, D) = Mod(〈T , S,M2〉, D), for every legal instance D for S. Hereinafter, for ease of exposition, we omit quantifiers in mapping assertions.

In this paper we use the following notion of inconsistency [Lembo et al., 2015].

Definition 1 (Global mapping inconsistency). Let T be a TBox, S a source schema, and M a mapping. We say that M is globally inconsistent for 〈T , S〉 if no instance D legal for S exists such that M is active on D and Mod(J , D) ̸= ∅.

Intuitively, it is impossible to activate simultaneously all the assertions of a globally inconsistent mapping without contradicting T and S. Note that a classical notion of inconsistency considers, instead, also source instances that do not activate all assertions in M, which means considering as consistent also specifications that admit models only if D = ∅, which is a trivial case for OBDA. Definition 1 recognizes the central role of the mapping, and is particularly suited in OBDA.

3 Mapping Repairs

In this section we define two operators for updating an OBDA specification when its TBox and/or source schema change. Each such operator is based on a specific notion of mapping repair. We start with deletion-based mapping repairs, where one looks for repairs among subsets of the original mapping, and then introduce entailment-based mapping repairs, aimed at preserving as much as possible of mapping assertions implied by the original specification.

From now on, for ease of exposition and without loss of generality, we assume that J = 〈T , S,M〉 is such that different mapping assertions inMuse different variable symbols.

Below we provide our first definition of mapping repair.

Definition 2 (Deletion-based mapping repair). Let J = 〈T , S,M〉 be an OBDA specification such that M is globally consistent for 〈T , S〉, T ′ a consistent TBox, S ′ a consistent source schema, andM′ a mapping such that M′ ⊆M. We say that M′ is a deletion-based mapping repair (DMR) for J under update 〈T ′ , S ′ 〉 if:

1. M′ is globally consistent for 〈T ′ , S ′ 〉, and
2. there exists no mappingM′′ ⊆Msuch that:
3. (a) M′′ is globally consistent for 〈T ′ , S ′ 〉, and
4. (b) M′′ ⊃M′ .

In other words, a DMR is a maximal subset of M that is globally consistent for the new TBox and source schema. It is easy to see that a DMR for J under update 〈T ′ , S ′ 〉 always exists, and that ifMis finite, alsoM′ is finite. Furthermore, if M is globally consistent for 〈T ′ , S ′ 〉, thenM is the only DMR for J . In general, however, several repairs exist.

We are now able to introduce our DMR-based update operator, denoted with ·, and define the OBDA specifications computed by such operator. Given J under update 〈T ′ , S ′ 〉, the set of such specifications, denoted by J · 〈T ′ , S ′ 〉, is

Note that the above notions are actually independent of the initial TBox T and schema S. Therefore, in the following we will simply call M′ a DMR for Munder update 〈T ′ , S ′ 〉, and will denote the set J · 〈T ′ , S ′ 〉 asM· 〈T ′ , S ′ 〉.

Example 3. Let J = 〈T , S,M〉 be as follows:

where A,C, F,E are atomic concepts, P is an atomic role, and T is a binary relation. Moreover, let T ′ = T ∪ {A ⊑ ¬∃P}. It is easy to see thatMis not globally consistent for 〈T ′ , S〉, since for every source schema that activatesM, the mapping produces two facts of the form P(x, y) and C(x) which violate the assertion C ⊑ ¬∃P , inferred by T ′ . Then, M· 〈T ′ , S〉 = {〈T ′ , S,M1〉, 〈T ′ , S,M2〉}, where: M1 = {T (x, y) ❀ P (x, y)} and M2 = {T (x′ , y′ ) ❀ C(x′ )}.

The following definition formalizes the notion of query entailment in the DMR-based update framework.

Definition 4 (Query Entailment under DMR). Let M be a mapping, T ′ a consistent TBox, S ′ a consistent source schema, D a legal instance for S ′ , and q a BCQ. We say that q is entailed under DMR by M , T ′ , S ′ , and D, denoted as (M· 〈T ′ , S ′ 〉,D) |= q, if (J ′ ,D) |= q for every J ′ ∈M· 〈T ′ , S ′ 〉.

Let M, S and T ′ be as in Example 3, and let D = {T(a, b)}. It is easy to see that (M· 〈T ′ , S〉,D) |= E(a).

We finally notice that DMRs depend on the syntax of the initial mapping M. As the following example shows, two equivalent (but syntactically different) mappings may have non-equivalent DMRs under the same update.

Example 5. Let T , S, Mand T ′ be as in Example 3, and let M′ be the mapping {T (x, y) ❀ P (x, y), T (x′ , y′ ) ❀ C(x′ ), T (x′′ , y′′ ) ❀ F (x′′ )}. M and M′ are equivalent with respect to T , since T |= C ⊑ F. However, whileM· 〈T ′ , S〉 is as in Example 3, M′ · 〈T ′ , S〉 = {〈T ′ , S,M′1 〉, 〈T ′ , S,M′2 〉}, where: M′1 = {T(x, y) ❀ P(x, y), T(x′′ , y′′ ) ❀ F(x′′ )} and M′2 = {T (x′ , y′ ) ❀ C(x′ ), T (x′′ , y′′ ) ❀ F (x′′ )}. This implies that query entailment is different in the two cases. E.g., given the source instance D = {T (a, b)}, we have that (M· 〈T ′ , S〉,D) ̸|= F(a), while (M′ · 〈T ′ , S〉,D) |= F(a).

We also notice that DMRs do not preserve mapping assertions not included in the original specification but entailed by it, and that would not directly lead to a contradiction with the update. For instance, in Example 3 the mapping T(x′′ , y′′ ) ❀ F(x′′ ) is implied by J and is not in contradiction with other mapping assertions under T ′ , but it is not entailed in 〈T ′ , S,M1〉.

In the following, we provide a different definition of mapping repair, which tries to preserve entailed mappings, and guarantees a reasonable form of syntax independence.

We first introduce some preliminary definitions.

Definition 6 (Mapping entailment set). Given an OBDA specification J and a mapping language L, the mapping entailment set (MES) of J in L, denoted by MESL(J ), is the set of mapping assertions {m ∈ L | J |= m and there exists m0 ∈ M such that body(m0) = body(m)}.

Among mapping assertions implied by J , in the above definition we excluded those using queries in their bodies that are different than those already present in M. Indeed, we cannot assume that any possible query over S can be really asked to the data sources, since usually they allow only for a controlled access to their content. We thus prefer to consider only queries already in the specification, which we can assume to be of the form accepted at the sources.

Note that, if the mapping language is infinite, the mapping entailment set MESL(J ) may be an infinite set of assertions even if the mapping M is a finite set.

We now need to give a characterization of the notion of "closeness" between sets. To this aim, we refer to the fewer changes relation given in [Fagin et al., 1983].

Let M, M1, and M2 be three sets. We say that M1 has fewer deletions than (resp. same deletions of) M2 with respect toMifM\M1 ⊂M\M2 (resp.M\M1 =M\M2). We also say that M1 has fewer insertions thanM2 with respect toM if M1 \M⊂M2 \M.

Definition 7 (Fewer changes). LetM,M1, andM2 be three sets. We say that M1 has fewer changes thanM2 with respect to M if:

1. M1 has fewer deletions thanM2 with respect toM; or
2. M1 andM2 have the same deletions with respect toM, andM1 has fewer insertions thanM2 with respect to M.

Notice that the notion of fewer changes gives preference to the sets having fewer deletions over those having fewer insertions. Such behavior is justified by the idea of retaining as much information as possible from the original set M.

We can now provide a new definition of mapping repair.

Definition 8 (Entailment-based mapping repair). Let J = 〈T , S,M〉 be an OBDA specification such that M is globally consistent for 〈T , S〉, T ′ a consistent TBox, S ′ a consistent source schema, L a mapping language, andM′ an L-mapping. We say that M′ is an entailment-based L-mapping repair (LEMR) for J under update 〈T ′ , S ′ 〉 if:

1. M′ is globally consistent for 〈T ′ , S ′ 〉; and
2. there exists no L-mappingM′′ such that:
3. (a) M′′ is globally consistent for 〈T ′ , S ′ 〉; and
4. (b) MESL(〈T ′ , S ′ ,M′′ 〉) has fewer changes than MESL(〈T ′ , S ′ ,M′ 〉) with respect to MESL(J ).

Intuitively, an entailment-based mapping repair (or more precisely its MES with respect to T ′ and S ′ ) preserves as much as possible of the mappings that were entailed in the initial OBDA specification and that do not contradict the update.

The following proposition shows the relationship between L-EMRs and DMRs of MESL(J ) under update 〈T ′ , S ′ 〉.

Proposition 9. For every L-EMR M′ for J under update 〈T ′ , S ′ 〉 there exists a DMR M′′ for MESL(J) under update 〈T ′ , S ′ 〉 such that MESL(〈T ′ , S ′ ,M′ 〉) = MESL(〈T ′ , S ′ ,M′′ 〉), and vice-versa, i.e., for every DMR M′′ for MESL(J) under update 〈T ′ , S ′ 〉 there exists a L-EMR M′ for J under update 〈T ′ , S ′ 〉 such that MESL(〈T ′ , S ′ ,M′′ 〉) = MESL(〈T ′ , S ′ ,M′ 〉).

We notice that, differently from DMRs, EMRs depend on the language L in which the repair is specified. This is due to the fact that EMRs may also contain mapping assertions that are not contained inM, and we thus need to specify the language in which such assertions are expressed.

Example 10. Let J and T ′ be as in Example 3. One can easily verify that the mappings M′1 = {T(x, y) ❀ P(x, y), T(x′ , y′ ) ❀ F(x′ )} and M′2 = {T(x, y) ❀ C(x)} are GAV-EMRs. Moreover, for any other GAVEMR M′3 , we have that MESGAV (〈T ′ , S ′ ,M′3 〉) = MESGAV (〈T ′ , S ′ ,M′1 〉) or MESGAV (〈T ′ , S ′ ,M′3 〉) = MESGAV (〈T ′ , S ′ ,M′2 〉).

Similarly to DMR, we now introduce an operator, denoted ◦L, to update an OBDA specification through EMR. Then, the set of OBDA specifications computed by ◦L for J under update 〈T ′ , S ′ 〉, denoted J ◦L 〈T ′ , S ′ 〉, is

Consider now again Example 5, and the equivalent specifications J = 〈T , S,M〉 and J ′ = 〈T , S,M′ 〉. It is easy to see that J ◦GAV 〈T ′ , S〉 = J ′ ◦GAV 〈T ′ , S〉, i.e., despite the syntactic difference between M and M′ , the set of GAV-EMRs is the same in the two cases (and so are the sets of OBDA specifications in the two cases). We point out that syntax independence for EMRs does not hold in general. However, it can be easily shown that two equivalent OBDA specifications J = 〈T , S,M〉 and J ′ = 〈T , S,M′ 〉 that are not mapping redundant (i.e., deleting any mapping assertion from J or J ′ produces a non-equivalent specification) have always equivalent EMRs with respect to any update. This does not hold for DMRs.

Below we give the notion of query entailment for L-EMRs. Definition 11 (Query Entailment under L-EMR). Let J = 〈T , S,M〉 be an OBDA specification such that M is globally consistent for 〈T , S〉, T ′ a consistent TBox, S ′ a consistent source schema, L a mapping language, D a legal instance for S ′ , and q a BCQ. We say that q is entailed under L-EMR by J , T ′ , S ′ , and D, denoted as (J ◦L 〈T ′ , S ′ 〉,D) |= q, if (J ′ ,D) |= q for every J ′ ∈ J ◦L 〈T ′ , S ′ 〉.

Let J = 〈T , S,M〉 and T ′ as in Example 3, and let D = {T(a, b)}. It is easy to see that (J ◦GAV 〈T ′ , S〉,D) |= F(a), while (M· 〈T ′ , S〉, D) ̸|= F(a).

We finally note that, differently from DMRs, a finite LEMR does not always exist, even if M is finite, thus the study of this case is particularly challenging.

4 Query Entailment under DMRs

In this section we study the query entailment problem under deletion-based repairs. First, we define the following general algorithm for checking whether (M·〈T ′ , S ′ 〉, D) |= q, whose correctness follows immediately from Definition 2.

Algorithm 1: CheckDMR-QE (M, T ′ , S ′ , D, q)

Input: finite GLAV mappingM, TBox T ′ , source schema S ′ legal instance D for S ′ , BCQ q over T ′

if there exists a subsetM′ ofMsuch that

• (i) M′ is globally consistent for 〈T ′ , S ′ 〉 and
• (ii) for every m ∈M\M′ ,M′ ∪ {m} is globally inconsistent for 〈T ′ , S ′ 〉 and
• (iii) (〈T ′ , S ′ ,M′ 〉,D) ̸|= q

then return false

else return true

We now focus on the setting with DL-LiteR TBoxes and simple source schemas 1 , and provide the following result.

Theorem 12. Let T ′ be a DL-LiteR TBox, S ′ a simple source schema, M a finite GLAV mapping, q a BCQ over T ′ , and D a legal instance for S ′ . Deciding (M· 〈T ′ , S ′ 〉,D) |= q is Πp2 -complete in combined complexity and in AC0 in data complexity.

Proof (sketch). The complexity of AlgorithmCheckDMRQE is coNP using an oracle that is able to decide global mapping inconsistency and CQ entailment. Since in this case both such problems are NP-complete in combined complexity when the TBox is DL-LiteR [Lembo et al., 2015], we obtain an upper bound of Πp2 . Through a reduction from 2-QBF validity we can in fact show that the above bound is exact.

1 Notice that DL-LiteR TBoxes and simple source schemas are always consistent, as required by Definition 2.

As for data complexity, all DMRs for a mappingMunder update 〈T ′ , S ′ 〉 can be computed in constant time (through steps (i) and (ii) of CheckDMR-QE), since this task does not depend on the data. Then, the data complexity coincides with that of checking (〈T ′ , S ′ ,M′ 〉,D) |= q for each DMRM′ , which is AC0 in data complexity [Calvanese et al., 2009]

5 Query Entailment under EMRs in GAV

We focus on the case when TBoxes are expressed in DL-LiteR, mappings are GAV, and the source schemas are simple.

First, we need to introduce the notion of mapping saturation with respect to a TBox. In the definition, C and F denote atomic concepts, and P and S denote atomic roles.

Definition 13. Let T be a DL-LiteR TBox and M a GAV mapping. We define the saturation of Mwith respect to T , denoted by sat TGAV (M), as follows:

• if φ(x) → C(x) is in M, then φ(x) → F(x) is in sat TGAV (M), for every F such that T |= C ⊑ F;
• if φ(x, y) →P(x, y) is inM, then:
• φ(x, y) → C(x) (resp., φ(x, y) → C(y)) is in sat TGAV (M), for every C such that T |= ∃P ⊑ C (resp., T |= ∃P - ⊑ C);
• φ(x, y) → S(x, y) (resp., φ(x, y) → S(y, x)) is in sat TGAV (M), for every S such that T |= P ⊑ S (resp., T |= P ⊑ S-);

We note that our notion of mapping saturation is equivalent to that of T -mapping given in [Rodr´ıguez-Muro and Calvanese, 2011]. Roughly, the set sat TGAV (M) represents a set of mapping assertions (which is finite if M is finite) that are relevant for computing GAV-EMRs, as stated below.

Theorem 14. Let J = 〈T , S,M〉, with T a DL-LiteR TBox, S a simple source schema, and M a GAV mapping globally consistent for 〈T , S〉, and let T ′ be a DL-LiteR TBox and S ′ a simple source schema. For every GAV-EMRM′ for J under update 〈T ′ , S ′ 〉 there exists a DMRM′′ for sat TGAV (M) under update 〈T ′ , S ′ 〉 such that M′ andM′′ are equivalent with respect to T ′ , and vice-versa, i.e., for every DMRM′′ for sat TGAV (M) under update 〈T ′ , S ′ 〉 there exists a GAV-EMR M′ for J under update 〈T ′ , S ′ 〉 such that M′′ andM′ are equivalent with respect to T ′ .

Proof (sketch). The thesis follows from Proposition 9 and the fact that for each mapping m′ ∈ MESGAV (J ) there exists a mapping m′′ ∈ sat TGAV (M) such that head(m′ ) = head(m′′ ) and body(m′ ) ⊆ body(m′′ ).

A direct consequence of the above theorem is that we can reduce query entailment under GAV-EMR to query entailment under DMR, i.e., to decide entailment of a BCQ q under GAV-EMR we can execute CheckDMR-QE (sat TGAV (M), T ′ , S ′ ,D, q), where M, T ′ , and S ′ are as in Theorem 14, and D is a legal instance for S. The above result immediately implies the following theorem.

Theorem 15. Let J = 〈T , S,M〉 be an OBDA specification, where T is a DL-LiteR TBox, S is a simple source schema, and M is a finite GAV mapping that is globally consistent for 〈T , S〉. Let T ′ be a DL-LiteR TBox, S ′ a simple source schema, D a legal instance for S ′ , and q a BCQ over T ′ . Deciding (J ◦GAV 〈T ′ , S ′ 〉, D) |= q is Πp2 -complete in combined complexity and in AC0 in data complexity.

Proof (sketch). To prove the theses we exploit Theorem 12 and the fact that sat TGAV (M) can be computed in polynomial time w.r.t. the size of T andMand is independent of D.

6 Query Entailment under EMRs in GLAV

As stated by Proposition 9, we can decide CQ entailment under EMRs for GLAV mappings by computing the DMRs of MESGLAV (J ). In order to be effective, such a reduction of EMR query entailment to DMR query entailment requires to overcome the problem of dealing with the infinite mapping MESGLAV (J). In the following, our main goal is to identify a finite subset of MESGLAV (J) that is correct for the purpose of CQ entailment under EMRs for GLAV mappings and DL-LiteR TBoxes. We reach this goal through the notions of mapping chase (MapChase) and mapping expansion (MapExp). This allows us to prove the decidability of CQ entailment under EMRs and establish its data complexity under a condition on the negative role inclusions of the updated TBox.

From now on, we assume that T and T ′ are DL-LiteR TBoxes, and we also assume without loss of generality that T and T ′ have the same signature. Moreover, we denote by T ∗ the positive deductive closure of T , i.e., the set of positive concept and role inclusions entailed by T . Finally, we denote by NR(T ) the negative role inclusions entailed by T .

We now adapt the well-known chase of an ABox with respect to a set of DL-LiteR positive inclusions [Calvanese et al., 2007] to the heads of GLAV mapping assertions. We call atom a GLAV mapping head atom, i.e., an expression of the form C(x) or P (x, x′ ), where C is an atomic concept, P is an atomic role, and x, x′ are variable symbols. Given a DL-LiteR positive inclusion I, an atom α, and a set of atoms Φ such that α ∈ Φ, we denote by Res(α, I, Φ) the atom computed by the application of I to α, similar to chase computation for DL-Lite ontologies. For example, if α = C(x) and I = C ⊑ ∃P, Res(α, I, Φ) = P(x, z), where z is a fresh variable in Φ.

Given a set of atoms Φ and a DL-LiteR TBox T , we define:

• chase 0 (Φ, T ) = Φ;
• for every integer k such that k ≥ 1, chase k (Φ, T ) = chase k-1 (Φ, T ) ∪ {α | β ∈ chase k-1 (Φ, T ) and I ∈ T and α = Res(β, I, chase k-1 (Φ, T ))}.

We now define a notion of chase for GLAV mapping assertions in DL-LiteR. Given an OBDA specification J = 〈T , S,M〉 and an integer k ≥ 0, we define MapChasek (J ) as the set of mapping assertions of the form body(m) ❀ H, such that m ∈ M and ∅ ⊂ H ⊆ chase k (head(m), T ∗ ). Moreover, we define MapChase(J ) = ⋃∞k=0 MapChasek (J ).

Informally, MapChase(J) augments the initial mapping M by adding mapping assertions that are obtained expanding (through the chase w.r.t. T ) the heads of the assertions inM.

We say that a GLAV mapping M is body-saturated if, for every pair of mapping assertions m1,m2 ∈M, if there exists a homomorphism h : Vars(body(m1)) → Vars(body(m2)) (where Vars(Φ) denotes the set of variables occurring in Φ)

such that h(body(m1)) ⊆ body(m2), then the mapping assertion body(m2) ❀ head(m2), h(head(m1)) belongs to M.

For body-saturated mappings, the following property holds.

Theorem 16. Let J = 〈T , S,M〉 where M is a bodysaturated mapping. For every m ∈ MESGLAV (J) there exists m′ ∈ MapChase(J) such that body(m′ ) = body(m) and there exists a homomorphism h : NFVars(head(m)) → Vars(head(m′ )) such that h(head(m)) ⊆ head(m′ ), where NFVars(head(m)) denotes the set of non-frontier variables occurring in head(m).

From now on, we assume without loss of generality that Mis body-saturated. Indeed, ifMviolates this assumption, it is possible to construct in finite time an equivalent bodysaturated GLAV mapping (by adding a finite number of mapping assertions toM). Note that every mapping assertion in MapChase(J ) belongs to MESGLAV (J ), while the opposite does not hold. Furthermore, it can easily be verified that it is not correct to use MapChase(J ) instead of MESGLAV (J ) to compute the EMRs of J under some update 〈T ′ , S ′ 〉. To reach such a property, we have to expand the set MapChase(J ).

Let Φ be a set of atoms. For every positive integer k, we define AtomExpk (Φ) as the set of atoms

Moreover, we define AtomExp(Φ) = ⋃∞k=1 AtomExpk (Φ). Intuitively, AtomExp(Φ) expands Φ with "copies" of the atoms of Φ, using "copies" xi of each variable x occurring in Φ. It is immediate to see that such an expansion of the set of atoms Φ does not change the meaning of Φ (interpreted as an existentially quantified conjunction of atoms).

We now define a notion of expansion of a mapping M that applies the function AtomExp to the heads of the assertions in M. Let m be a GLAV mapping assertion. We define MapExpk (m) as the set {m′ | body(m′ ) = body(m) and ∅ ⊂ head(m′ ) ⊆ AtomExpk (head(m))}. Given a GLAV mapping M, we define MapExpk (M) = ⋃m∈M MapExpk (m). Finally, we define MapExp(M) = ⋃∞k=1 MapExpk (M).

Theorem 17. Let J = 〈T , S,M〉. Then: (i) MapExp(MapChase(J)) ⊆ MESGLAV (J); (ii) for every m ∈ MESGLAV (J) there exists m′ ∈ MapExp(MapChase(J)) such that m′ is equal to m up to renaming of the non-frontier variables of head(m′ ).

Proof (sketch). Thesis (i) follows trivially from the definitions of MapChase and MapExp. Thesis (ii) follows from Theorem 16 and from the key property that, for every mapping m ∈ M and for every m′ ∈ MESGLAV (J) such that body(m′ ) = body(m) and there exists a homomorphism h : NFVars(head(m′ )) → Vars(head(m)) such that h(head(m)) ⊆ head(m′ ), the set of atoms head(m′ ) is a subset of MapExp(chase(head(m), T )) (up to renaming of the non-frontier variables of head(m′ )).

Theorem 17 implies that MapExp(MapChase(J )) is a subset of MESGLAV (J ) that produces equivalent DMRs under any update. However, such a subset is still infinite, due to: (i) the infiniteness introduced by MapChase (when T contains cycles of existentially quantified concepts); (ii) the inifiniteness introduced by MapExp. We first deal with the latter problem, showing that we can safely restrict MapExp to a finite number of expansion steps without losing the above property. More precisely, it is possible to prove that there exists k such that MapExpk (MapChase(J )) and MapExp(MapChase(J )) have equivalent DMRs under arbitrary updates.

Theorem 18. Let J = 〈T , S,M〉 be an OBDA specification, where T is a DL-LiteR TBox, S is a simple source schema, and M is a GLAV mapping, let T ′ be a DL-LiteR TBox such that M is globally consistent for 〈T ∪ NR(T ′ ), S〉 and let S ′ be a simple source schema. There exists an integer k such that, for every DMRM′ of MESGLAV (J ) under update 〈T ′ , S ′ 〉 there exists a DMR M′′ of MapExpk (MapChase(J )) under update 〈T ′ , S ′ 〉 such that M′ and M′′ are equivalent with respect to T ′ .

Based on the previous theorem, we are able to establish the data complexity of query entailment under EMR in GLAV for DL-LiteR TBoxes under the condition that the mapping M is consistent with the negative role inclusions of the updated TBox T ′ , i.e.,Mis globally consistent for 〈T ∪NR(T ′ ), S〉.

Theorem 19. Let J = 〈T , S,M〉 with T DL-LiteR TBox, S simple source schema, andMfinite GLAV mapping. Let T ′ be a DL-LiteR TBox such that M is globally consistent for 〈T ∪ NR(T ′ ), S〉, S ′ a simple source schema, D a legal instance for S ′ , and q a BCQ over T ′ . Deciding (J ◦GLAV 〈T ′ , S ′ 〉,D) |= q is in AC0 in data complexity.

It can be shown that, for T ′ such that M is not globally consistent for 〈T ∪ NR(T ′ ), S〉, Theorem 18 no longer holds, and as a consequence Theorem 19 does not apply as well.

7 Conclusions

Besides their theoretical relevance, the results presented in this paper have a practical fallout. Typically, in ontology (and thus in OBDA) design a set of so-called competency questions is used, which are representative of the intended usages of the system. The ability of successfully answering such questions is a measure of the quality of the design, and in particular of the fitness of the system with respect to its functional requirements [Neuhaus and Vizedom, 2013]. Therefore, query answering under our repair semantics can be of help for the maintenance of an evolving OBDA system, since it can allow the designer to measure the impact of repairing with respect to the ability of the system to answer competency questions. We also note that variants of this service might be considered, for instance, to identify repairs under which the system has a desired behaviour with respect to query answering. We believe this is a promising direction towards semi-automatic mapping evolution management, even though several aspects still need to be investigated. In particular, we want to complete the study of CQ entailment under EMRs for GLAV mappings for DL-LiteR ontologies and analyze query entailment under our repair semantics for different DLs. Furthermore, we aim at defining approximations of the notions of DMR and EMR that guarantee the existence of a single repair, which might have important practical implications.