Abstractions of Queries in Ontology-Based Data Access

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Abstractions of Queries in Ontology-Based Data Access

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

artificialintelligence knowledgerepresentation reasoning

artificial intelligence, reasoning, knowledge representation

Abstractions of Queries in Ontology-Based Data Access (Extended version) ∗

arXiv:2606.24618v1 [cs.AI] 23 Jun 2026

Michel Leclère , Marie-Laure Mugnier , Guillaume Pérution-Kihli LIRMM, Inria, University of Montpellier, CNRS, Montpellier, France {michel.leclere, marie-laure.mugnier, guillaume.perution-kihli}@lirmm.fr

Abstract In ontology-based data access (OBDA), multiple data sources are integrated via mappings to an ontology. We consider an OBDA setting based on existential rules and the certain answer semantics. We address the recent issue of query abstraction, which consists of abstracting data queries by translating them to the ontology layer. Since a perfect abstraction may not exist, the notions of minimally complete and maximally sound abstractions have been introduced. We study abstractions within an extension of UCQs with a limited form of inequality and a special predicate marking database constants. While this extension does not lead to an increased complexity of the problems of interest, it is able to express minimally complete abstractions, hence perfect abstractions when they exist. We also characterize maximally sound abstractions by making a new connection with the notion of maximum recovery stemming from data exchange.

Introduction

In ontology-based data access (OBDA), multiple data sources are integrated via mappings to a shared ontology (Poggi et al. 2008). This approach generalizes classical data integration by replacing the global schema with an ontology, enabling users to query data at a high level of abstraction while benefiting from reasoning over domain knowledge. A central problem in OBDA is ontological query answering. Given an OBDA specification Σ = (S, O, M, O), where S is a data schema, O an ontology schema, M a mapping from S to O, and O an ontology over O, and a database D over S, the goal is to compute the answers to an ontological query QO over the knowledge base (KB) defined by D, M, and O. Such KB may remain virtual: then, QO is rewritten into a data-level query QS that is a perfect translation of QO , which means that, for any database D over S, the answers to QS on D coincide with the answers to QO on the virtual KB. While QS is simply evaluated on D, the answers to QO are logically entailed by the KB—corresponding to the standard semantics of certain answers, i.e., answers that hold in every model of the KB. ∗ This report contains the paper published at KR 2025 (with title “Abstractions of Queries in Ontology-Based Data Access” and the same list of authors) and an appendix with detailed proofs and further examples.

More recently, research in OBDA has also investigated query translation in the opposite direction, i.e., from data queries to ontological queries—a task called query abstraction (Cima, Poggi, and Lenzerini 2023). This issue arises in a range of relevant scenarios. First, during the (often incremental) design of an OBDA system, query abstraction can be used to verify whether the mapping provides adequate coverage of important data queries (Lutz, Marti, and Sabellek 2018). Second, query abstraction is a means to automatically characterize the semantics of data services implemented at the data-source level—which can be seen as a form of reverse engineering (Cima, Lenzerini, and Poggi 2019). This capability opens the door to promising applications, such as providing open datasets supplied by organizations with high-level semantics, or enhancing the FAIRness of data services (Cima, Poggi, and Lenzerini 2023). In this paper, we investigate query abstraction within an OBDA setting based on existential rules (Baget et al. 2009; Calı́, Gottlob, and Lukasiewicz 2009), aka TGDs in database theory (Abiteboul, Hull, and Vianu 1995).We use existential rules for both the mapping (we obtain Global-Local-AsView (GLAV) mappings) and the ontology. So doing, we generalize classical OBDA frameworks based on Horn description logics (DLs), as these can be seen as specific existential rule classes. Moreover, this uniform setting allows us to rely on the same fundamental tools to handle mappings and ontologies, namely the chase and query rewriting. It also helps to make connections with database theory. Most work in OBDA has focused on ontological queries expressed as unions of conjunctive queries (UCQs), the core relational database queries. FO-rewritable ontologies—such as those expressed with the main dialects of the DL-Lite family (Calvanese et al. 2007) or certain fragments of existential rules (Baget et al. 2009; Calı̀, Gottlob, and Pieris 2010)—guarantee that every ontological UCQ admits a perfect rewriting as a UCQ. In the other direction, query translation appears to be much more challenging. To start with, a perfect abstraction of a data (U)CQ may not exist at all, even with an empty ontology. Apart from the fact that mappings may not transfer all the answers, they may also make source relations indistinguishable, as illustrated next. Example 1. Let S = {s1 , s2 }, O = {r} and M = {m1 , m2 }, with m1 : s1 (x) → r(x) and m2 : s2 (x) → r(x). The query QS (u) = s1 (u) has no perfect abstraction

through M. In particular, the ontological query QO (u) = r(u) captures all answers to QS , i.e., it is a complete abstraction of QS , but it is not a sound abstraction of QS , as it also retrieves values coming from the source relation s2 . In fact, QO would be a perfect abstraction of s1 (u) ∨ s2 (u). The topic began to be investigated only recently (Lutz, Marti, and Sabellek 2018; Cima, Lenzerini, and Poggi 2019; Cima et al. 2021). However, OBDA can build on a rich body of previous work in database theory. As pointed out by Lutz et al. (Lutz, Marti, and Sabellek 2018), when the ontology is ignored, deciding if a source query has a perfect abstraction as a UCQ is closely related to the long-studied problem of query expressibility with views (Nash, Segoufin, and Vianu 2010). We will establish a new link with database theory by considering specific inverse mappings from data exchange (Fagin et al. 2008; Arenas, Pérez, and Riveros 2009). Since a perfect abstraction of a UCQ QS may not exist, Cima et al. introduced minimally complete and maximally sound abstractions, which respectively provide a minimal superset and a maximal subset of answers to QS (Cima, Lenzerini, and Poggi 2019). Here, minimality and maximality are with respect to the set of queries definable in some target query language (e.g., UCQ). With the aim of capturing perfect abstractions of UCQs, we consider an extension of UCQ, denoted by UCQ̸=,C , with a limited form of inequality (variables that occur in inequalities must be mapped to constants) and a special unary predicate marking database constants, denoted by C—which was introduced in (Fagin et al. 2008) to define inverse mappings. As a data query language, UCQ̸= is of great interest in practice, especially as inequalities are in fact not limited when the queried databases are ground. However, the true benefit of UCQ̸=,C is as an ontological query language. Indeed, while a perfect abstraction of a UCQ, when it exists, may not be expressible as a UCQ, we will show that it is always expressible as a UCQ̸=,C . We will now detail our main contributions. To distinguish between the settings of database integration, i.e., without ontology, and OBDA, we will use the terms M-abstraction and Σ-abstraction, respectively. (1) Complexity of the problems of interest within the UCQ̸=,C class. In Section 3, we study the computational impact of extending UCQ to UCQ̸=,C . In particular, we show that this does not lead to increased complexity of verifying whether a candidate M-abstraction is perfect, which is ΠP2 -complete (see Table 1, first column). We also exhibit an FO-rewritable rule fragment for which this problem with a Σ-abstraction remains in ΠP2 (this subsumes earlier results on DL-Lite). Other complexity results are established later. (2) Capturing minimally-complete and perfect abstractions of UCQ̸=,C s. In Section 4, we first point out that a non-Boolean query QS may not have a complete abstraction and characterize the conditions under which it has one (which only depends on the interactions between QS and the mapping). For a UCQ QS that has a complete abstraction, it is known that, by applying M to QS (i.e., “chasing” QS with M), one produces a UCQ QO that is minimally complete w.r.t. all M-abstractions definable as UCQs

Setting (U)CQ, GAV, bounded arity UCQ̸=,C , GLAV bounded frontier UCQ̸=,C , GLAV

Verification ΠP2 - C (*)

Existence ΠP2 - C (*)

ΠP2 - C

in C O -NE XP T IME (*) from (Lutz, Marti, and Sabellek 2018)

Table 1: Complexity of problems related to perfect M-abstractions

(Lutz, Marti, and Sabellek 2018; Cima, Lenzerini, and Poggi 2019). However, we point out that QS may have a better M-abstraction (i.e., a complete M-abstraction with fewer unwanted answers) in the UCQ̸=,C class, which can be computed by a modified chase. The important result here is that UCQ̸=,C is in fact able to express a minimally complete M-abstraction (and Σ-abstraction as well) of any source UCQ̸=,C , where minimality is w.r.t. all possible ontological queries (i.e., queries on schema O expressed in any language, provided that they are answered with the semantics of certain answers). We take special care in exhibiting the properties behind this result. It follows that, when a perfect Σ-abstraction of a UCQ̸=,C exists, it can be expressed in this class. Moreover, UCQ̸=,C is a minimal language with this property, even when the source query is a plain UCQ. Finally, we use these results to show that the complexity of deciding whether a perfect M-abstraction exists for a given UCQ̸=,C is ΠP2 -complete when the mapping rules have a frontier of bounded size (the frontier being the set of variables shared between the body and head) and in CoNExpTime otherwise (see Table 1, second column). (3) Characterizing maximally sound abstractions of UCQ̸=,C s. There is no known algorithm that builds a maximally sound M-abstraction of a UCQ as a UCQ (or UCQ̸=,C ), when such abstraction exists, except in a very specific case (Cima, Lenzerini, and Poggi 2019). Whether the associated existence problem is decidable is an open question. In Section 5, we make a step towards better understanding by drawing a connection with the notion of a maximum recovery investigated in a quite different context, namely data exchange. In data exchange, mappings are used to specify how to transfer data from a source schema to a target schema; then, a maximum recovery of a mapping M is an inverse mapping from target to source that allows one to recover the most answers to source queries when it is composed with M (Arenas, Pérez, and Riveros 2009). To express such inverse mapping, a strictly more expressive language than GLAV is required, as disjunction in rule heads is needed. We show that a maximally sound M-abstraction of a UCQ̸=,C QS can be equivalently defined as the rewriting of QS with a maximum recovery of M. To define such rewriting, we rely on a rewriting operator for UCQs and disjunctive existential rules introduced in (Leclère, Mugnier, and Pérution-Kihli 2023). In passing, we correct a wrong claim from the literature, that a maximum recovery for CQs could always be expressed by a conjunctive mapping (i.e., without disjunction) (Arenas et al. 2009). We then extend

the notion of a maximum recovery to an OBDA specification (i.e., we add an ontology) and show that a maximum recovery can still be expressed by the same form of disjunctive mapping when the ontology is FO-rewritable; hence, in this case, a maximally sound Σ-abstraction of a UCQ̸=,C can also be characterized as a rewriting with a maximum recovery. When this rewriting is finite, it is a UCQ̸=,C .

Preliminaries

We assume the reader has basic knowledge in database theory and ontological query answering. Database theory We consider a denumerable set of constants C. A term is a constant from C or a variable. A schema is a finite set of predicates. An atom with predicate p is called a p-atom. Given a schema P , a P -atom is any p-atom with p ∈ P . A P -instance is a possibly infinite set of P -atoms, also seen as an interpretation of (P, C), in which constants are interpreted by themselves. A database is a ground finite instance. Given an instance I, we denote by vars(I), consts(I) and terms(I) its sets of variables, constants and terms, respectively. A tuple ⃗x of pairwise distinct variables is sometimes seen as a set. Given instances I1 and I2 , a homomorphism h from I1 to I2 is a substitution of vars(I1 ) by terms(I2 ) such that h(I1 ) ⊆ I2 . We also denote it by h : I1 → I2 and we say that I1 maps to I2 (by h). When convenient, we extend the domain of a homomorphism to constants. We define the notion of a query in an abstract way, i.e., independently from any syntactic form: an n-ary query Q on schema P is any function that maps each P -instance I to a set of n-ary tuples on consts(I). We denote by Q(I) the set of answers to Q on I. An n-ary FO-query on P has the form Q(⃗x), where Q is an FO-formula on P and ⃗x are n free variables from Q (the answer variables). A Boolean query is 0-ary. Given an instance I, a tuple ⃗c ⊆ consts(I) with |⃗c| = |⃗x| is an answer to an FO-query Q(⃗x) on I if I is a model of Q(⃗c), where Q(⃗c) is obtained by substituting each i-th variable in ⃗x by the i-th constant in ⃗c. A conjunctive query (CQ) has the form q(⃗x) = ∃⃗y . ϕ[⃗x, ⃗y ], where ϕ is a finite conjunction of atoms and ⃗x ∪ ⃗y = vars(ϕ); to denote a CQ, we write q rather than Q. A CQ is with join-free existential variables (CQJFE) if each existential variable occurs only once. A union of conjunctive queries (UCQ) is a finite disjunction of CQs with the same tuple of answer variables. A UCQ may contain equalities, but to simplify technical developments we will silently assume that, before any processing, equalities are removed by substituting variables. Given queries Q1 and Q2 , Q1 is contained in Q2 , denoted by Q1 ⊑ Q2 , if Q1 (I) ⊆ Q2 (I) for any instance I. Given two CQs q1 (⃗x1 ) and q2 (⃗x2 ), a query homomorphism from q1 to q2 is a homomorphism h from q1 to q2 such that h(⃗x1 ) = ⃗x2 . It is well known that, given CQs q1 and q2 , q1 ⊑ q2 iff there is a query homomorphism from q2 to q1 . Note that for UCQs Q1 and Q2 , we have Q1 ⊑ Q2 iff for all q1 ∈ Q1 , there is q2 ∈ Q2 such that q1 ⊑ q2 . When information is incomplete, a set of instances is often considered instead of a single instance; then, the set of certain answers to a query Q on a set of instances I is

certain(Q, I) =

Q(I).

I∈I

Rules and mappings An existential rule R (or simply rule hereafter) is a closed formula of the form ∀⃗x. (∃⃗y . B[⃗x, ⃗y ]) → ∃⃗z. H[⃗x, ⃗z] where B and H ̸= ∅ are finite conjunctions, respectively called the body and the head of R, also noted body(R) and head(R), and ⃗x, ⃗y and ⃗z are pairwise disjoint tuples of variables and consts(H) ⊆ consts(B). The frontier of R is fr(R) = ⃗x. Note that body(R) and head(R) can be seen as CQs with answer variables fr(R). R is Datalog if ⃗z = ∅. Given schemas S and T , called source and target respectively, with S ∩ T = ∅, an S-to-T rule has a body made of S-atoms and a head made of T -atoms. A GLAV mapping from S to T is a finite set of S-to-T rules. A GLAV mapping is GAV if it is a set of Datalog rules. OBDA An OBDA specification is a quadruplet Σ = (S, O, M, R) where S is the source schema, O the ontology schema, M a (GLAV) mapping from S to O and R a finite set of rules over O. An OBDA system is a pair (D, Σ) with Σ an OBDA specification and D an S-database. A source query, usually denoted by QS , is defined on S and an ontological query, usually denoted by QO , is defined on O. The answers to an ontological query QO on an OBDA system (D, Σ), denoted by Qcert O (D, Σ), are its certain answers on the models of the OBDA system, denoted by ModΣ (D): ModΣ (D) = {O-instance I | D ∪ I |= M and I |= R} Qcert O (D, Σ) = certain(QO , ModΣ (D)) When we want to ignore the set of rules R of an OBDA system, we use notations with M instead of Σ. Query containment is extended to ontological queries: Q1 ⊑Σ Q2 if Qcert (D, Σ) ⊆ Qcert (D, Σ) for every S-database D. 1 2 Query abstraction For an OBDA specification Σ, a query QO on O is a complete (resp. sound) Σ-abstraction of a query QS on S if QS (D) ⊆ Qcert O (D, Σ) (resp. Qcert (D, Σ) ⊆ Q (D)) for all D; Q is a perfect ΣS O O abstraction if it is both sound and complete. We also consider “best” approximations of perfect abstractions within a target query class: Given a query class Q, an ontological query QO ∈ Q is a Q-minimally complete Σ-abstraction of QS if QO is a complete Σ-abstraction of QS and QO ⊑Σ Q′O for any Q′O ∈ Q that is a complete Σ-abstraction of QS ; similarly, QO is a Q-maximally sound Σ-abstraction of QS if QO is a sound Σ-abstraction of QS and Q′O ⊑Σ QO for any Q′O ∈ Q that is a sound Σ-abstraction of QS . When we do not specify Q, we consider any query, as abstractly defined above. Finally, when R is ignored, we speak of M-abstraction instead of Σ-abstraction. Let X ∈ {M, Σ} and Q be a class of queries. We study three kinds of problems: • Verifying if an abstraction is perfect: the Q X -perfectness verification problem takes as input X , Q-queries QS and QO , and asks if QO is a perfect X -abstraction of QS . This problem is decomposed into verifying X -soundness and X -completeness. • Deciding the existence of a perfect abstraction: the Q X expressibility problem takes as input X and QS ∈ Q, and asks if a perfect X -abstraction of QS is expressible in Q.

• Computing abstractions satisfying property P ∈ {perfectness, maximal soundness, minimal completeness}; Given X and a Q-query QS , the task is to compute a Q-query QO that is an X -abstraction of QS with property P , when such an abstraction exists. Reasoning tools Let R be a set of rules. Given an instance I, the chase with R exhaustively applies rules from R to I, towards a fixpoint. 1 We denote by chase(I, R) the (possibly infinite) resulting instance. Crucially, chase(I, R) is a universal model of I and R, i.e., it maps to any model of I and R. Given a UCQ Q, query rewriting with R starts from Q seen as a set of CQs; it iteratively rewrites a CQ from the set with a rule from R and adds the resulting CQ to the set, while keeping a minimal set w.r.t. query containment, towards a fixpoint. We consider here the rewriting algorithm from (König et al. 2015), based on so-called piece-unifiers, and denote by rew(Q, R) the possibly infinite set (i.e., union) of CQs it produces. Each rewriting step is based on a piece-unifier, which unifies a subset q ′ of a CQ q with a subset of a rule head h′ while satisfying the following piece condition: an existential variable from h′ can only be unified with variables from q ′ , which furthermore do not occur in q \ q ′ . A fundamental property holds: For any instance I, set of rules R and Boolean UCQ Q, I ∪ R entails Q iff chase(I, R) |= Q iff I |= rew(Q, R). A pair (Q, R) where Q is a UCQ, is FO-rewritable if there is a UCQ Q′ such that Q′ (I) = certain(Q, chase(I, R)) for any instance I. Note that (Q, R) is FO-rewritable iff rew(Q, R) is finite. A rule set R is FO-rewritable, or fus, if (Q, R) is FO-rewritable for any UCQ Q. When mappings (from S to T ) are considered instead of rules on a single schema, the result of the chase or of query rewriting is restricted to the relevant schema (T or S). Given a mapping M from S to T and a (finite) S-instance I, the chase of I with M yields the T -instance M(I) = {A ∈ chase(I, M) | A is a T -atom}. Given a CQ qs , the chase of qs with M is defined similarly, on the atoms of qs seen as an instance, provided that each answer variable from qs occurs in a T -atom of M(qs ); hence, M(qs ) can be seen as a CQ with the same arity as qs . The chase is further extended to a UCQ: given an S-UCQ Qs , M(Qs ) is defined only if M(qsi ) is defined for each qsi ∈ Qs ; then M(Qs ) is the T UCQ obtained by making the disjunction of the M(qsi ), for all qsi ∈ Qs . Query rewriting with a mapping M takes as input a T -UCQ Qt and produces the S-UCQ M− (Qt ) = {q ∈ rew(Qt , M) | q is a query on S}. Note that M(Qs ) and M− (Qt ) are always finite. It is convenient to use the same notations for mappings and general rule sets; so we also note R(I) = chase(I, R) and R− (Q) = rew(Q, R). For an OBDA specification Σ = (S, O, M, R), we note Σ(I) = R(M(I)) and Σ− (Q) = M− (R− (Q)). When R− (Q) is not finite, it is seen as an infinitary query, as in (Lutz, Marti, and Sabellek 2018). Properties of OBDA systems We finally list some fundamental properties of OBDA systems, which are explicit or 1 This formulation corresponds to the simplest chase variant, called oblivious (Calı̀, Gottlob, and Kifer 2008).

implicit in previous work, except that we consider existential rules instead of specific Horn description logics. Proposition 2. For any OBDA specification Σ = (S, O, M, R), S-database D, S-UCQ QS and O-UCQ QO the following holds: cert 1. Qcert O (D, M) ⊆ QO (D, Σ) − − 2. Qcert O (D, Σ) = QO (R(M(D))) = (M (R (QO )))(D) ′ ′ 3. If QS ⊑ QS then M(QS ) ⊑M M(QS ) 4. QO ⊑M Q′O iff M− (QO ) ⊑ M− (Q′O ) 5. QO ⊑Σ Q′O iff R− (QO ) ⊑M R− (Q′O )

When a perfect M-abstraction of a UCQ QS is expressible as a UCQ, M(QS ) is such an abstraction (this follows, e.g., from (Nash, Segoufin, and Vianu 2010)). Moreover, when QS has a complete M-abstraction, M(QS ) is such an abstraction, which is even UCQ-minimally complete (Cima, Lenzerini, and Poggi 2019). Hence, a UCQ QS has a perfect M-abstraction expressible as a UCQ iff M(QS ) is sound, which can be checked by verifying if M− (M(QS )) ⊑ QS . This result has been extended to a Σ-abstraction in some specific OBDA settings.2 Next, we use the following notations: Σ is an OBDA specification defined by (S, O, M, R), D is an S-database, and QS , QO are queries over S and O respectively.

From UCQ to UCQ̸=,C

The class UCQ̸=,C extends UCQ with two special predicates: a restricted form of inequality (̸=) and a unary predicate C stating that its argument is a constant.3 In the context of query abstraction, C is used to mark variables in ontological queries that must be mapped to values coming from the database, whereas ̸= allows one to distinguish between different ways of matching query variables. Definition 3 (UCQ̸=,C ). A UCQ̸=,C Q is a UCQ extended with atoms on special predicates ̸= (binary) and C (unary), such that: (1) All the variables of Q occur in standard atoms, and (2) The terms of any ̸=-atom are constants, answer variables, or variables that occur in a C-atom. We denote by std(Q) the restriction of Q to standard atoms. The C-atoms on answer variables and constants, as well as ̸=-atoms over constants, can be made explicit or not. Also, C is useless in source queries since databases are ground, but for simplicity we keep the same query class at the data and the ontology levels. A UCQ̸=,C Q is consistent if there exists a database D such that Q(D) ̸= ∅, which can be checked in polynomial time. Next, we implicitly assume that queries are consistent. All the technical tools for CQs are extended to CQ̸=,C in the natural way. A homomorphism h : q → I is a homomorphism from std(q) to I such that (i) for all C(t) ∈ q, h(t) is a constant, and (ii) for all t1 ̸= t2 , h(t1 ) ̸= h(t2 ). A query homomorphism h : q1 → q2 is a homomorphism 2 GAV mappings (Lutz, Marti, and Sabellek 2018) or ontology in DL-LiteR (Cima, Lenzerini, and Poggi 2019). 3 Formally: for any FO-interpretation I = (∆, .I ) it holds that I C = consts(I) and ̸=I = {(d1 , d2 ) ∈ ∆2 | d1 ̸= d2 }.

from std(q1 ) to std(q2 ) such that (i) for all C(t) ∈ q1 , h(C(t)) ∈ q2 or h(t) is a constant or h(t) is an answer variable, and (ii) for all t1 ̸= t2 ∈ q1 , h(t1 ̸= t2 ) ∈ Q2 or h(t1 ) and h(t2 ) are distinct constants. The chase of q with M, i.e., M(q), is obtained from M(std(q)) by (1) adding the atoms (t1 ̸= t2 ) from q if t1 and t2 are both in M(std(q)), and (2) adding C(x) on the variables from vars(q) ∩ vars(M(std(q))). Hence, if the C-atoms in q are made explicit, M(q) is defined as for a plain (U)CQ w.r.t. target predicates T ∪ {C, ̸=}. Similarly, the rewriting of q with M, i.e., M− (q), is defined w.r.t. source predicates S ∪ {C, ̸=}; inconsistent CQs can be removed from M− (q) and the C-atoms can be made implicit. Note that, by definition of a piece-unifier, an existential variable from a rule head cannot be unified with a variable that occurs in a C- or ̸=-atom. These notions are illustrated in Ex. 4. They are extended to UCQ̸=,C as expected. Note that the fundamental properties from Prop. 2 still hold. Example 4. Let M be the following mapping: m1 : s1 (x, y) → p(x, y) m3 : s2 (x) → p(x, x) m2 : s1 (x, x) → r(x) m4 : s3 (x) → ∃y.p(x, y) ̸= Let the source CQ q(u) = ∃v. s1 (u, v) ∧ u ̸= v. Then, M(q(u)) = p(u, v)∧ u ̸= v ∧ C(v) (with C(u) left implicit as u is an answer variable) and M− (M(q(u)) ≡ q(u). Let us detail the rewriting of M(q(u)): p(u, v) can be unified with head(m1 ), which yields q(u), as well as with head(m3 ), which yields the inconsistent CQ s2 (u) ∧ u ̸= u (discarded); p(u, v) cannot be unified with head(m4 ) because v would be unified with the existential variable y, while it also occurs in C(v) and in u ̸= v. The next example shows that a UCQ may have no perfect abstraction in UCQ but one in UCQ̸=,C . Example 5 (Perfect abstraction within UCQ̸=,C ). Consider again M from Ex. 4. The CQ qS (u) = ∃v.s1 (u, v) has no perfect M-abstraction in UCQ. Indeed, M(qS ) = ∃v.p(u, v), and Q′S = M− (M(qS )) = ∃v.s1 (u, v) ∨ s2 (u) ∨ s3 (u) strictly contains qS . Hence, M(qS ) is not a sound abstraction. However, the following UCQ̸=,C is a perfect abstraction of qS : QO (u) = 1 2 1 qO (u) ∨ qO (u), with qO (u) = ∃v. p(u, v) ∧ C(v) ∧ u ̸= v 2 and qO (u) = r(u) ∧ p(u, u). Such query QO is the output of the algorithm given in Section 4. Intuitively, QO is a sound abstraction because it does not retrieve the p-atoms 1 produced by m3 and m4 . Indeed, qO only retrieves p-atoms 1 produced by m1 , thanks to u ̸= v and C(v). However, qO is not a complete abstraction as it avoids atoms of the form 2 p(a, a) that can be produced by m1 . Subquery qO compen2 sates for this elimination. Note that the atom p(u, u) in qO is actually not needed: indeed, when an atom r(a) is produced (by m2 ), the atom p(a, a) is necessarily produced (by m1 ). More formally, let us check that M− (QO ) ≡ qS . The 1 rewriting of qO yields the CQ ∃v. s1 (u, v) ∧ u ̸= v, see 2 Ex. 4. The rewriting of qO yields two CQs: 1. s1 (u, u), obtained by unifying r(u) with head(m2 ) and p(u, u) with head(m1 ); and 2. (s1 (u, u) ∧ s2 (u)), obtained by unifying r(u) with head(m2 ) and p(u, u) with head(m3 ). The latter query is contained in the former, hence can be ignored. We obtain M− (QO ) = (∃v. s1 (u, v) ∧ u ̸= v) ∨ s1 (u, u) ≡ qS .

A natural question is whether this extension increases the complexities of the problems we are interested in. First note that a homomorphism from a CQ̸=,C q to an instance I necessarily maps terms from a ̸=-atom to terms known to be constants. It follows that, for q Boolean, if I entails q then q maps to I (and reciprocally); hence, query answering can still rely on homomorphism. This is different for query containment: given CQs̸=,C q1 and q2 , the existence of a query homomorphism from q2 to q1 is no longer a necessary condition for q1 ⊑ q2 , even when considering only databases. Let UCQ̸=,C containment be the problem that takes as input two queries Q1 and Q2 in UCQ̸=,C , and asks if Q1 ⊑ Q2 . This problem is known to be ΠP2 -complete, already when both queries are in CQ̸=,C (van der Meyden 1997; Kolaitis, Martin, and Thakur 1998). As a complementary result, we prove that ΠP2 -hardness already holds when Q1 is a very simple kind of CQ. Theorem 6 (Complexity of UCQ̸=,C containment). The UCQ̸=,C containment problem is ΠP2 -hard when Q1 is a Boolean CQJFE and Q2 is a Boolean CQ̸=,C . Proof sketch. By a reduction from ∀∃3CNF adapted from (Abiteboul, Kanellakis, and Grahne 1991). We now study the complexity of M-perfectness verification, by decomposing that problem into M-completeness and M-soundness verifications. The M-completeness (resp. M-soundness) verification problem can be recast as verifying if QS ⊑ M− (QO ) (resp. M− (QO ) ⊑ QS ). There is an immediate reduction from UCQ̸=,C containment to verification, taking a trivial mapping M that bijectively translates n-ary predicates in S into n-ary predicates in O. Theorem 7 (Complexity of M-completeness). The UCQ̸=,C M-completeness verification problem is ΠP2 complete, even if QS is a CQJFE and QO is a CQ̸= . Proof. To verify that QS ⊑ M− (QO ), we can check if, for every ground instantiation D of a CQ̸= from QS , there is a CQ̸= qi ∈ M− (QO ) that maps to D (with answer variables mapped correctly). We can universally choose a D in polynomial time as it is given by a substitution of the variables of a qs ∈ QS by fresh constants and we can guess qi and a homomorphism from qi to D in polynomial time. Indeed, to obtain a qi , we guess a CQ̸= qj ∈ QO , a subset of M with at most |qj | rules and associated piece-unifiers. Hence, Mcompleteness is in ΠP2 . Hardness follows from Th. 6. Theorem 8 (Complexity of M-soundness). The UCQ̸=,C M-soundness verification problem is ΠP2 -complete, even if QS is a Boolean CQ̸= and QO is a is a Boolean CQJFE. Proof. Similar to that of Th. 7. Since Q1 ⊑ Q2 iff Q1 ≡ Q1 ∧Q2 , query equivalence is as hard as query containment, hence: Corollary 9. The UCQ̸=,C M-perfectness verification problem is ΠP2 -complete. It is known that M-perfectness verification is ΠP2 -hard already for QS and QO CQs and M a GAV mapping in a DL setting, i.e., with mapping heads restricted to unary and binary predicates (Lutz, Marti, and Sabellek 2018; Cima, Lenzerini, and Poggi 2019). Hence, considering

(U)CQ̸=,C (and GLAV mappings) does not lead to increased complexity of verification. When it comes to taking an ontology into account, most previous works have considered lightweight DLs that are fus.4 The key point is that, for any fus rule set R and QO in UCQ̸=,C , R− (QO ) is also in UCQ̸=,C ; hence the techniques designed for M-abstractions can be extended, however at the risk of increased complexity. Next, we show that perfectness verification remains in ΠP2 when R is a set of linear rules—i.e., existential rules whose body has a single atom—over predicates with bounded arity. This rule class generalizes several dialects of the DL-Lite family, in particular DL-LiteR (Calı́, Gottlob, and Lukasiewicz 2009). Theorem 10. The UCQ̸=,C Σ-perfectness verification problem is in ΠP2 when R is linear with bounded-arity predicates. Proof sketch. W.l.o.g. assume QO is a CQ̸=,C . We show we can guess a CQ̸=,C q ′ from R− (QO ) in polynomial time. Since R is linear, any such q ′ has at most |QO | atoms, which only share terms from QO . Hence, the length of a rewriting sequence to q ′ can be bounded by |QO | × A, where A is an upper-bound on the number of “non-isomorphic” atoms— with isomorphism being the identity on terms(QO )— i.e., A = |P | × (|terms(QO )| + a)a , where P is the set of predicates and a is the maximal arity of a predicate in P . This result subsumes previous results establishing ΠP2 membership of Σ-perfectness verification with UCQs and DL-LiteR (Lutz, Marti, and Sabellek 2018; Cima, Lenzerini, and Poggi 2019). 5 The theorem actually applies to any FOrewritable pair (QO , R) such that all the CQs in R− (QO ) can be generated in a polynomial number of rewriting steps.

Computing Minimally Complete and Perfect Abstractions

Let us first point out that a complete abstraction of a nonBoolean query QS may not exist, simply because M may not transfer all the constants that occur in the answers to QS . This is independent from any target query language. E.g., let M = {s(x, y) → r(y)} and the CQ qS (u) = ∃v.s(u, v): qS has no complete Σ-abstraction, for any Σ with M. Let us characterize when a UCQ̸=,C has a complete Σ-abstraction: Proposition 11 (Existence of a complete abstraction). A CQ̸=,C qS (⃗x) has a complete Σ-abstraction iff for all x ∈ ⃗x there are m ∈ M and a homomorphism h : body(m) → qS (⃗x) s.t. x ∈ h(fr(m)). A UCQ̸=,C QS (⃗x) has a complete Σ-abstraction iff each qi (⃗x) ∈ QS has one. Hence, deciding if a non-Boolean UCQ̸=,C has a complete Σ-abstraction is NP-complete, while it is trivial for a Boolean UCQ̸=,C . UCQ̸=,C captures perfect Σ-abstractions of UCQ̸=(,C) source queries. As already mentioned, chasing a (relevant) 4

An exception is (Lutz, Marti, and Sabellek 2018) considering also non-fus DLs from the EL family. 5 We can ignore the disjointness axioms from DL-LiteR , as they have no impact on the complexity results.

UCQ with M yields a UCQ that is minimally complete within this class. However, as illustrated by Ex. 5, the class UCQ̸=,C may provide a more faithful translation: the UCQ M(QS ) is minimally complete within UCQs but not sound, while the UCQ̸=,C QO is a perfect abstraction. We now state the main result of this section: the class UCQ̸=,C captures minimally complete abstractions of source UCQs̸=,C , where minimality is w.r.t. any ontological query class (still with certain answer semantics)6 . Theorem 12 (Minimal completeness). For any mapping M and any UCQ̸=,C QS that has a complete M-abstraction, there is a UCQ̸=,C QO such that, for any Σ with mapping M, QO is a minimally complete Σ-abstraction of QS . Note that QO is also a minimally complete M-abstraction (we take Σ with R = ∅). However, a minimally complete M-abstraction is generally not a minimally complete Σabstraction, and vice-versa; to obtain Th. 12, we will rely on the specific abstraction computed by the M-chase. Moreover, if there is a perfect Σ-abstraction of QS , any minimally complete Σ-abstraction of QS is perfect, hence UCQ̸=,C also captures perfect abstractions: Corollary 13 (Perfectness). For any Σ and any UCQ̸=,C QS , if there is a perfect Σ-abstraction of QS , then it can be expressed as a UCQ̸=,C . Furthermore, it is easy to find examples in which C or the limited ̸= is required to express a perfect abstraction of a UCQ, hence one can argue that UCQ̸=,C is a minimal class to express perfect abstractions of UCQs and UCQ̸=,C . To prove Th. 12, we first state a fundamental semantic property of OBDA systems. Proposition 14. For any databases D and D′ on S, if Σ(D) |= M(D′ ), then: 7 1. ModΣ (D) ⊆ ModM (D′ ). ′ cert 2. Hence: for any QO on O, Qcert O (D , M) ⊆ QO (D, Σ). We now explain how to build the desired abstraction. Only M is required (not R), the resulting query being minimally complete for any Σ with mapping M. In a nutshell, before chasing QS , we first split each qi ∈ QS into an equivalent UCQ̸=,C , whose CQs encode all the ways of mapping qi to a database: terms substituted identically are merged, remaining terms are declared distinct (̸=) and marked by C. We will show that chasing the output with M yields the desired minimally complete Σ-abstraction. Note that a similar split operation is presented in (Cima et al. 2022) to compute minimally complete abstractions expressed in a more complex target language. Such operation is also commonly used to build inverse mappings, see e.g. Ex. 19. For the sake of self-containedness, and to include the processing of constants, we detail our split operation next. Given a CQ̸=,C q, a partition of terms(q) is said admissible if none of its classes contains two constants 6

See the discussion at the end of this section. As regards the formulation of the proposition, note that Σ(D) |= M(D′ ) is stronger than Σ(D) |= Σ(D′ ): indeed, Σ(D) |= M(D′ ) implies R(Σ(D)) |= R(M(D′ )), with R(Σ(D)) ≡ Σ(D) and R(M(D′ )) ≡ Σ(D′ ) 7

nor both terms of a ̸=-atom from q. Informally, each class of the partition gathers the terms of q mapped to the same database constant. To each admissible partition Pσ can be assigned a substitution σ, which is obtained by (1) selecting one term ti in each class Ci ∈ Pσ , with priority given to constants, then to answer variables if any, and (2) setting σ(tj ) = ti for each tj ∈ Ci s.t. tj ̸= ti . E.g., to Pσ = {{x, u}, {v, w, a}}, with x an answer variable and a a constant, is assigned σ = {u 7→ x, v 7→ a, w 7→ a}. Given a UCQ̸=,C QS (⃗x), split(QS ) is a UCQ̸=,C built as follows: Let split(QS ) = ∅ For each qi ∈ QS For each admissible Pσ on terms(qi ) ∪ consts(M) Let q ′ = σ(qi ) // q ′ is consistent For any v ∈ vars(q ′ ) If v ̸∈ ⃗x then add C(v) to q ′ For any t ∈ terms(q ′ ) ∪ consts(M) with v ̸= t Add v ̸= t to q ′ Add q ′ to split(QS ) Note that q ′ may include atoms of the form v ̸= c, where c is a constant from M that does not occur in std(q ′ ): this is necessary to ensure the desired behavior of split(QS ) (see Lemma 16). It is easy to check that for any database D, QS (D) = split(QS )(D). Example 15. (Minimally complete abstraction) Consider again Example 5 with qs (u) = ∃v.s1 (u, v). split(qs (u)) = (∃v.s1 (u, v) ∧ C(v) ∧ u ̸= v) ∨ s1 (u, u) M(split(qs (u))) = QO (u) The following lemma states the crucial property of split(QS ). We call grounding of a CQ̸=,C qS a substitution σ of each variable in qS by a constant s.t. σ(qS ) is consistent. The key point is that any grounding of a qsi ∈ split(QS ) is injective. It follows that any rule body maps “in the same way” to qsi and to any of its groundings: Lemma 16. Let σsi be a grounding of qsi ∈ split(QS ). Then: M(σsi (qsi )) ≡ σsi (M(qsi )). Proof of Th. 12 (Sketch). Let QO (⃗x) = M(split(QS )). We show that QO is a minimally complete Σ-abstraction of QS , for any Σ with mapping M. Completeness follows from the properties of the M-chase. To prove that QO is minimally complete, we consider any D and ⃗c ∈ QO (Σ(D)) and show that ⃗c is a certain answer to any complete Σi abstraction of QS . Let qO ∈ QO that maps by hi to Σ(D) i i with hi (⃗x) = ⃗c. Let qS ∈ split(QS ) such that qO = M(qSi ). i Let Di be obtained by a grounding of hi (qS ). Since hi (⃗x) = i ⃗c, ⃗c ∈ qSi (Di ). Since qO is a complete Σ-abstraction of i i qS , ⃗c ∈ qO (Σ(Di )). We have M(hi (qSi )) ≡ M(Di ), i hence, from Lemma 16, M(Di ) maps to hi (qO ). Since i hi (qO ) ⊆ Σ(D), M(Di ) maps to Σ(D). So, by Prop. 14, for all ontological query Q, Qcert (Di , Σ) ⊆ Qcert (D, Σ), hence if Q is Σ-complete then ⃗c ∈ Qcert (D, Σ). Complexity of expressibility With these results in hand, we can now study the complexity of determining whether a

UCQ̸=,C QS has a perfect M-abstraction. Let us say that M is frontier-bounded if the frontier of all its rules is bounded by a constant. From (Lutz, Marti, and Sabellek 2018) we know that UCQ M-expressibility is ΠP2 -complete in a GAV setting with bounded predicates (in rule heads). We observe that ΠP2 -membership can be extended to GLAV mappings with unbounded predicate arity provided that M is frontierbounded. Indeed, for a CQ qsi ∈ QS , M(qsi ) is built from rule heads whose frontier is substituted by terms(qsi ); hence, for each m ∈ M, the number of substitutions that need to be considered is bounded by terms(qsi )|fr(m)| . Therefore, when M is frontier-bounded, we can build each M(qsi ) by making a polynomial number of calls to an NP oracle, asking for each m ∈ M with fr(m) = (x1 , . . . , xk ) (according to an arbitrary total ordering of the frontier variables) and tuple t = (y1 , . . . , yk ) ∈ terms(qsi )k if there is a homomorphism h : body(m) → qsi such that h(fr(m)) = t. When M is not frontier-bounded, M(QS ) can be computed in ExpTime, which yields a Co-NExpTime upper bound. These arguments can be generalized to (unrestricted) M-expressibility of UCQ̸=,C queries, as shown next. Theorem 17. (Complexity of M-expressibility) UCQ̸=,C M-expressiblity is ΠP2 -complete when M is frontierbounded, otherwise it is in Co-NExpTime. Proof sketch. To check that Qs is not M-expressible, one can guess a CQ̸= from Qs and a partition on its terms, which yields a CQ̸= qsi from split(Qs ), compute qoi = M(qsi ) and guess a rewriting qs′ i of qoi (of polynomial size in qoi ) such that qs′ i ̸⊑ Qs (test in ΣP 2 ). If M is frontier-bounded, qoi = M(qsi ) can be built by making a polynomial number of calls to an NP oracle, otherwise, it can be computed in ExpTime. Hence, the (co-)problem is in ΣP 2 if M is frontier-bounded, otherwise in NExpTime. ΠP2 -hardness follows from (Lutz, Marti, and Sabellek 2018). Discussion on related frameworks We will now discuss our framework further in relationship with previous work. As shown above, one can decide if a UCQ̸=,C QS has a perfect M-abstraction by simply checking if QO = M(split(QS )) is a sound M-abstraction, i.e., M− (QO ) ⊑ QS . This may seem contradictory with other results from the literature. In particular, it is shown in (Cima et al. 2021) that determining if a CQ has a perfect M-abstraction is undecidable. In fact, the crucial point is the semantics of ontological queries. We consider the widely adopted semantics of certain answers. As a consequence, ontological queries are necessarily monotone, in the following sense: QO is monotone if for all D1 , D2 on S, if ModΣ (D2 ) ⊆ ModΣ (D1 ) then any answer to QO on (D1 , Σ) is an answer to QO on (D2 , Σ). This is a corollary of our Prop. 14. A more general notion of ontological query is investigated in the above-mentionned paper, which allows for non-monotone queries. Note that a source query may have no perfect monotone abstraction but a perfect abstraction in this more general setting, which is studied in (Cima, Lenzerini, and Poggi 2020). The C predicate was introduced in (Fagin et al. 2008), under the name is-constant, to define specific kinds of inverses of GLAV mappings, which are disjunctive̸=,C map-

pings (Definition 18). It has been commonly used since then in the data exchange litterature, not only in inverse mappings but also in queries, see e.g., (Arenas, Pérez, and Riveros 2008). Similar notions have also been studied in KR, as closed-world variables (Amendola et al. 2018), or nominal variables in description logics (Krötzsch and Rudolph 2014). We think that C yields a very simple and effective way of dealing with unknown values introduced by mappings (and ontologies). First, it is easy to understand for a user and its introduction has no impact on computational complexity. Second, it can be handled using offthe-shelf tools. Indeed, one can slighly modify the mapping by adding a head atom C(t) for each frontier variable or constant t: then, C-atoms in ontological queries can be processed just like the standard atoms. A more general way of introducing some closed world reasoning would have been to extend queries with the epistemic operator K (“is known”), as in (Cima, Lenzerini, and Poggi 2020; Cima et al. 2022). However, this operator does not have the simplicity of C, which seems a better choice to us in the context of abstractions under standard certain answer semantics. On the other hand, K comes into its own in the context of non-monotone ontological queries, which inherently requires a more general semantics than certain answers.

Computing Maximally Sound Abstractions

A (U)CQ(̸=) always has a sound abstraction (the empty UCQ, which has no answer) but may not have a maximally sound abstraction expressible as a UCQ(̸=,C) . Finding a suitable language for such abstractions remains open. In this section, we make progress by providing a characterization of maximally sound M-abstractions of UCQ(̸=) s, which we further extend to Σ-abstractions with fus rules. For that, we rely on specific inverse mappings from O to S, which, as explained later, correspond to so-called maximum recoveries. Such mappings have disjunctive heads, as defined next. Definition 18 (Disjunctive̸=,C mapping). A disjunctive (resp. disjunctive̸=,C ) mapping from a source schema S to a target schema T is a set of S-to-T disjunctive existenn W tial rules of the form ∀⃗x.(∃⃗y .B[⃗x, ⃗y ]) → ∃⃗ zi .Hi [⃗x, z⃗i ], i=1

where B is a CQ (resp. a CQ̸=,C ) and each Hi is a CQ, all with answer variables ⃗x. Given a (GLAV) mapping M from S to O, we will consider a disjunctive̸=,C mapping M∨ from O to S, which has the property of being a maximum recovery of M (Arenas, Pérez, and Riveros 2009; Arenas et al. 2009). Before entering into the formal framework of maximum recoveries, we first explain how M∨ is built. Briefly, each rule of M∨ is obtained by rewriting a rule head from M against M. Precisely, for each m ∈ M with head ∃⃗y .H[⃗x, ⃗y ] (seen as a CQ), M∨ has the following disjunctive rule: ∀⃗x.(∃⃗y .H[⃗x, ⃗y ] ∧ C[⃗x]) → M− (∃⃗y .H[⃗x, ⃗y ]) This is illustrated in Ex. 19. As shown in the example, the head of the obtained rule may contain equalities; these equalities can be turned into inequalities in the rule body, by

a split operation similar in spirit to that described in Sect. 4, which yields a rule complying with Def. 18; see (Arenas et al. 2009) for details. Example 19. Let M = m1 = s1 (x) → ∃y.p(x, y) m3 = s3 (x, y) → r(x, y) m2 = s2 (x, y) → p(x, y) m4 = s4 (x) → r(x, x) ′ By  rewriting the CQs head(mi )(fr(mi )), one gets M = ′  m1 = p(x, y) ∧ C(x) → s1 (x) ∨ ∃z.s2 (x, z)    ′  m = p(x, y) ∧ C(x) ∧ C(y) → s2 (x, y)  2 ′ m3 = r(x, y) ∧ C(x) ∧ C(y) → s3 (x, y) ∨    (s4 (x) ∧ x = y)    ′ m4 = r(x, x) ∧ C(x) → s3 (x, x) ∨ s4 (x) Moreover, Rule m′3 with equality can be replaced by two rules obtained by considering that, in body(m′3 ), either x = y (which yields m′4 , already present) or x ̸= y, which yields: m′′3 = r(x, y) ∧ C(x) ∧ C(y) ∧ x ̸= y → s3 (x, y) Finally, M∨ = {m′1 , m′2 , m′′3 , m′4 }. We furthermore consider the rewriting operator for UCQs against disjunctive mappings introduced in (Leclère, Mugnier, and Pérution-Kihli 2023). This operator is sound and complete and yields a possibly infinite disjunction of CQs. Its extension to UCQ̸=,C s and disjunctive̸=,C mappings is straightforward. We can now outline our characterization of maximal sound M-abstractions: For any mapping M (from S to O) and UCQ̸=,C QS on S, let M∨ be the disjunctive̸=,C mapping from O to S built as above; then, M− ∨ (QS ), i.e., the rewriting of QS against M∨ , is a maximally sound abstraction of QS . This result relies on the fact that M∨ is a maximum recovery of M and is proven in Th. 21. Maximum recoveries The following definitions and results come from (Arenas, Pérez, and Riveros 2009; Arenas et al. 2009). The notion of a maximum recovery is defined on abstract mappings, which may then be specified by concrete mappings, i.e., provided with a specific syntax (e.g., GLAV). An abstract mapping MA from a schema S to a schema T is any relation from the S-instances to the T instances.8 Let QT be a query on T . Given T an S-instance I, we denote by certainMA (QT , I) = (I,J)∈MA QT (J) the certain answers to QT through I and MA . A query QS on S such that QS (I) = certainMA (QT , I) for all instance I on S, is called a perfect rewriting of QT through MA (such QS may not exist). The composition of two abstract mappings MA and M′A is denoted by MA • M′A .9 Given an abstract mapping MA from S to T , the abstract mapping M′A from T to S is a recovery of MA if for any query QS on S and instance I on S, certainMA •M′A (QS , I) ⊆ QS (I); and M′A is a maximum recovery if, moreover, for any recovery M′′A of MA , certainMA •M′′A (QS , I) ⊆ certainMA •M′A (QS , I). An abstract mapping MA from S to T is specified by a (GLAV) mapping M from S to T if: for every pair of (S, T )-instances (I, J), (I, J) ∈ MA iff I ∪ J |= M. In 8

In the cited work, instances are finite, but the definitions work in the infinite case. 9 We use • to avoid confusion with the classical ◦: MA • M′A can be read M′A ◦ MA .

this case, certainMA (QT , I) = Qcert (I, M) holds for T ̸=,C any query QT and, when QT is a UCQ , M− (QT ) is a perfect rewriting of QT through MA . Not all abstract mappings have a maximum recovery. However, when the source instances are ground, a GLAV mapping always has one, taking the form of a disjunctive̸=,C mapping (Def. 18).10 Maximally sound M-abstractions Let MA be an abstract mapping specified by a GLAV mapping M. The following lemma shows that a perfect rewriting of a source query QS through a maximum recovery of MA behaves similarly to a maximally sound S-to-T translation of QS through M (i.e., an M-abstraction of QS when S = S and T = O). Indeed, Point (1) corresponds to the soundness of an M-abstraction and Point (2) to its maximality. Lemma 20. Let QS be a query on S, MA be an abstract mapping from S to T that has a maximum recovery M′A . Let QT be a perfect rewriting of QS through M′A . Then, for any S-instance I: (1) certainMA (QT , I) ⊆ QS (I), and (2) certainMA (Q′T , I) ⊆ certainMA (QT , I) for any query Q′T such that certainMA (Q′T , I) ⊆ QS (I). Finally, Th. 21 directly relies on Lemma 20: Theorem 21. Let M be a (GLAV) mapping from S to O, M∨ be a disjunctive̸=,C mapping that is a (concrete) maximum recovery of M, and QS be a UCQ̸=,C on S. Then M∨ − (QS ) is a maximally sound M-abstraction of QS . In general, M∨ − (QS ) is a possibly infinite disjunction of UCQ̸=,C . Yet, the next proposition gives cases where it is a UCQ̸=,C . In such cases, the rewriting algorithm from (Leclère, Mugnier, and Pérution-Kihli 2023) can be used to effectively output a maximally sound M-abstraction. Proposition 22. The maximally sound M-abstraction of a UCQ̸=,C Q is a UCQ̸=,C when: 1. M− (head(m)) is a CQ̸=,C for all m ∈ M; or: 2. Q contains only full CQs̸=,C (i.e., without existential variables) and M is GAV; or: 3. Q contains only atomic CQs̸=,C (i.e., with at most one standard atom). Proof. Let M∨ be a maximum recovery of M. (1) M∨ is a conjunctive mapping. (2) All rules in M∨ are lossless (all body variables are frontier) which guarantees to get a UCQ̸=,C -rewriting from any full CQ̸=,C . (3) Disjunctive source-to-target rule sets guarantee to get a UCQ̸=,C rewriting from any atomic CQ̸=,C . Points (2) and (3) follow from the rewriting algorithm in (Leclère, Mugnier, and Pérution-Kihli 2023). Note. We remark that Th. 21 contradicts a result from (Arenas et al. 2009) (see Th. 4.4). This result states that a recovery that maximally recovers answers to CQs (not UCQs), called a CQ-maximum recovery, can be specified 10

More precisely: For every GLAV mapping M, which specifies an abstract mapping MA , there is a concrete mapping M∨ that specifies a maximum recovery of MA and can be expressed as a disjunctive mapping̸=,C . For the sake of simplicity, we say that M∨ is a (concrete) maximum recovery of M.

by a conjunctive mapping (i.e., without disjunctive heads). But then, the rewriting of a CQ through a CQ-maximum recovery would always be finite (this is a property of conjunctive mappings), hence a CQ would always have a maximally sound M-abstraction as a UCQ̸=,C , which is false. Maximally sound Σ-abstractions We now extend previous results to an OBDA specification with a fus ontology R. A suitable disjunctive̸=,C mapping from O to S, say MΣ ∨, is obtained by rewriting each rule head of M ∪ R against M ∪ R. For a rule head ∃⃗y .H[⃗x, ⃗y ], this yields the disjunctive rule ∀⃗x.(∃⃗y .H[⃗x, ⃗y ] ∧ C[⃗x]) → Σ− (∃⃗y .H[⃗x, ⃗y ]). To bring OBDA specifications into the maximum recovery framework, we say that an abstract mapping MA from S to O is specified by Σ = (S, O, M, R) if, for all S-database D and O-instance J, (D, J) ∈ MA iff D ∪ J |= M and J |= R both hold. Theorem 23. Let Σ be an OBDA specification with FOrewritable R. Then: 1. MΣ ∨ is a (concrete) maximum recovery of Σ. −

2. For any UCQ̸=,C QS on S, MΣ ∨ (QS ) is a maximally sound Σ-abstraction of QS . Proof (sketch). (1) Since M∪R is fus, MΣ ∨ is well defined. ′ We first prove that MΣ ∨ specifies a recovery ΣA of the abstract mapping ΣA specified by Σ. To do that, we prove that for all S-databases D, there is an O-instance J s.t. (D, J) ∈ ΣA and (J, D) ∈ Σ′A . Such J always exists, f.i. J = Σ(D). Then, we prove that Σ′A is a maximum recovery of ΣA , using Prop. 3.8 from (Arenas, Pérez, and Riveros 2009), from which follows that Σ′A is a maximum recovery of ΣA iff Σ′A is a recovery and for every (D1 , D2 ) ∈ ΣA • Σ′A , it is the case that ∅ ̸= ModΣA (D2 ) ⊆ ModΣA (D1 ). Σ′A has this property by construction of MΣ ∨ . (2) The proof is similar to the proof of Th. 21, using Point (1) and Lemma 20. Prop. 22 can be extended to Σ-abstractions as follows: (1) taking M ∪ R instead of M; (2) and (3): taking rule classes ensuring that R− (Q) has the desired property, in particular lossless rules for (2) and linear rules for (3).

Conclusion

We have investigated the properties of the query class UCQ̸=,C for capturing abstractions in an OBDA setting under certain answer semantics. We found that this class enjoys nice computational behavior in this context. We proved that it is able to express any minimally complete—and therefore any perfect—abstraction of a source UCQ̸=,C , when such an abstraction exists. Although a maximally sound abstraction of a UCQ always exists, it may not be expressible in UCQ̸=,C . However, we identified an interesting connection with the notion of maximum recovery from data exchange, and showed that a maximally sound M-abstraction of a source UCQ̸=,C is precisely its rewriting with a maximum recovery of M. While the ontology plays no role in minimal completeness, it does in maximal soundness. Accordingly, we extended the preceding result to OBDA specifications with fus ontologies. Among the open questions, it remains unknown whether the problem of determining if a (U)CQ admits a maximally

sound abstraction in UCQ̸=,C is decidable. Moreover, no known algorithm is guaranteed to terminate whenever such a finite abstraction exists.

Acknowledgements We thank the reviewers for their helpful comments.

References Abiteboul, S.; Hull, R.; and Vianu, V. 1995. Foundations of Databases. Addison-Wesley. Abiteboul, S.; Kanellakis, P. C.; and Grahne, G. 1991. On the representation and querying of sets of possible worlds. Theor. Comput. Sci. 78(1):158–187. Amendola, G.; Leone, N.; Manna, M.; and Veltri, P. 2018. Enhancing existential rules by closed-world variables. In Lang, J., ed., Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, 1676–1682. ijcai.org. Arenas, M.; Pérez, J.; Reutter, J. L.; and Riveros, C. 2009. Inverting schema mappings: Bridging the gap between theory and practice. Proc. VLDB Endow. 2:1018–1029. Arenas, M.; Pérez, J.; and Riveros, C. 2008. The recovery of a schema mapping: bringing exchanged data back. In ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Arenas, M.; Pérez, J.; and Riveros, C. 2009. The recovery of a schema mapping: Bringing exchanged data back. ACM Trans. Database Syst. 34:22:1–22:48. Baget, J.-F.; Leclère, M.; Mugnier, M.-L.; and Salvat, E. 2009. Extending Decidable Cases for Rules with Existential Variables. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI 2009, 677–682. Calı̀, A.; Gottlob, G.; and Kifer, M. 2008. Taming the infinite chase: Query answering under expressive relational constraints. In Brewka, G., and Lang, J., eds., Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, KR 2008, 70–80. AAAI Press. Calı́, A.; Gottlob, G.; and Lukasiewicz, T. 2009. A general datalog-based framework for tractable query answering over ontologies. In ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Calı̀, A.; Gottlob, G.; and Pieris, A. 2010. Advanced processing for ontological queries. Proc. VLDB Endow. 3(1):554–565. Calvanese, D.; Giacomo, G. D.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2007. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reason. 39(3):385–429. Cima, G.; Console, M.; Lenzerini, M.; and Poggi, A. 2021. Abstraction in data integration. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, 1– 11. IEEE. Cima, G.; Console, M.; Lenzerini, M.; and Poggi, A. 2022. Monotone Abstractions in Ontology-Based Data Management. In AAAI Conference on Artificial Intelligence.

Cima, G.; Lenzerini, M.; and Poggi, A. 2019. Semantic characterization of data services through ontologies. In International Joint Conference on Artificial Intelligence. Cima, G.; Lenzerini, M.; and Poggi, A. 2020. Nonmonotonic ontology-based abstractions of data services. In International Conference on Principles of Knowledge Representation and Reasoning. Cima, G.; Poggi, A.; and Lenzerini, M. 2023. The notion of abstraction in ontology-based data management. Artif. Intell. 323:103976. Fagin, R.; Kolaitis, P. G.; Popa, L.; and Tan, W.-C. 2008. Quasi-inverses of schema mappings. ACM Transactions on Database Systems (TODS) 33(2):1–52. Kolaitis, P. G.; Martin, D. L.; and Thakur, M. N. 1998. On the complexity of the containment problem for conjunctive queries with built-in predicates. In Mendelzon, A. O., and Paredaens, J., eds., Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 197–204. ACM Press. König, M.; Leclère, M.; Mugnier, M.; and Thomazo, M. 2015. Sound, complete and minimal ucq-rewriting for existential rules. Semantic Web 6(5):451–475. Krötzsch, M., and Rudolph, S. 2014. Nominal schemas in description logics: Complexities clarified. In Baral, C.; Giacomo, G. D.; and Eiter, T., eds., Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014. AAAI Press. Leclère, M.; Mugnier, M.; and Pérution-Kihli, G. 2023. Query rewriting with disjunctive existential rules and mappings. In Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023, 429–439. Lutz, C.; Marti, J.; and Sabellek, L. 2018. Query expressibility and verification in ontology-based data access. In International Conference on Principles of Knowledge Representation and Reasoning. Erratum at https://www.informatik. uni-leipzig.de/kr/research/papers.html. Nash, A.; Segoufin, L.; and Vianu, V. 2010. Views and queries: Determinacy and rewriting. ACM Trans. Database Syst. 35(3):21:1–21:41. Poggi, A.; Lembo, D.; Calvanese, D.; Giacomo, G. D.; Lenzerini, M.; and Rosati, R. 2008. Linking data to ontologies. J. Data Semant. 10:133–173. van der Meyden, R. 1997. The complexity of querying indefinite data about linearly ordered domains. J. Comput. Syst. Sci. 54(1):113–135.

Appendix This appendix contains detailed proofs of the paper’s results, as well as further examples, discussions and results that could not be included in the paper due to space constraints.

Complements to Section 3

The next example shows that homomorphism is not a necessary condition for containment of CQ̸=,C s. Example 24 (Query containment within UCQ̸=,C ). Consider the following Boolean queries: q1 = ∃u, v. p(u, v) ∧ C(u) ∧ C(v) ∧ u ̸= v q2 = ∃x, y, z. p(x, y) ∧ p(x, z) ∧ C(x) ∧ C(y) ∧ C(z) ∧ y ̸= z. Note that all the variables in these queries occur in a C-atom, hence inequalities are allowed between all (distinct) terms. There is no homomorphism from q1 to q2 ; however q2 ⊑ q1 . Indeed, for any database D that answers yes to q2 , either x and y are mapped to distinct constants, and D answers yes to q1 , or x and y are mapped to the same constant, in which case x and z are necessarily mapped to distinct constants (because of the atom y ̸= z), and D answers yes to q1 . Let UCQ̸=,C containment be the problem that takes as input two queries Q0 and Q1 in UCQ̸=,C , and asks if Q0 ⊑ Q1 . This problem is known to be ΠP2 -complete, already when both queries are in CQ̸=,C (van der Meyden 1997; Kolaitis, Martin, and Thakur 1998). As a complementary result, we prove that ΠP2 -hardness already holds when Q0 is Boolean CQJFE, which is a very simple kind of CQ. Theorem 6 The UCQ̸=,C containment problem is ΠP2 -hard when Q0 is a Boolean CQJFE and Q1 is a Boolean CQ̸=,C . To prove this result, we adapt a reduction from (Abiteboul et al., 1991)11 . In that paper, they study query containment given databases with incomplete information. An instance is a complete database, and a query is defined as a mapping from a set of instances to a set of instances. An incomplete database represents a set of instances, and it is defined as a set of relations featuring null values, and furthermore provided with equalities and inequalities. The following problem, denoted by CONT(q0 , q), is defined as follows: q0 and q are fixed queries; given incomplete databases ϕ0 and ϕ, does it hold that q0 (ϕ0 ) ⊆ q(ϕ)? In particular CONT( , ) is the case where q0 and q are the identity, hence the question is whether the set of instances represented by ϕ0 is included in the set of instances represented by ϕ. Their theorem 4.2 proves that CONT( , ) is ΠP 2 -complete for data complexity for several kinds of incomplete databases. Our proof is inspired from their proof of Case (1), where we turn incomplete databases into CQ̸=,C s. Proof. To prove ΠP2 -hardness, we reduce the ΠP2 -complete problem ∀∃3CNF, which takes as input a quantified Boolean formula ∀X.∃ Y.ϕ[X, Y ], where X and Y are sets of variables, X ∩ Y = ∅ and ϕ is a 3CNF, and asks if for all truth assignments of variables in X, there is a truth assignment of variables in Y that make ϕ true. Let ∀X∃Y C be an instance of ∀∃3CN F . Let X = {x1 , . . . , xn }. We consider the following set of predicates: for each i ∈ {1, . . . , n}, there is a binary predicate vali ; there is also a ternary predicate cl (cl for “clause”). We build Q0 and Q1 such that Q0 is a Boolean CQJFE and Q1 is a CQ̸= . We build Q0 as follows. For each i ∈ {1, . . . , n}, there is a variable zi . The atoms are the following: 1. For each i ∈ {1, . . . , n}, two atoms: vali (0, zi ) and vali (1, 0), where zi is a variable. 2. All the cl-atoms that make a 3-clause true, i.e., all the cl-atoms on {0, 1}3 except (0, 0, 0). Note that, to obtain a ground instantiation of Q0 , we only have to instantiate the zi . We build Q1 as follows. For each propositional variable x ∈ X ∪ Y , there are two variables: x and x̄. Furthermore, for each i ∈ {1, . . . , n}, there are four variables: ui , wi , vi and yi . Finally, there are two constants, arbitrarily denoted by 5 and 6. The atoms are the following: 1. For each i ∈ {1, . . . , n}, two atoms: vali (ui , wi ) and vali (vi , yi ), where all the terms are variables. 2. For each clause (l1 ∨ l2 ∨ l3 ) ∈ C, the atom cl(var(l1 ), var(l2 ), var(l3 )), where var(li ) = li if li is positive, and ¯li if li is negative. 3. For each propositional variable x ∈ X ∪ Y , the atom x ̸= x̄. 4. For each propositional variable xi ∈ X, the atoms xi ̸= vi , x̄i ̸= ui , wi ̸= 5 and yi ̸= 6. 11 Serge Abiteboul, Paris C. Kanellakis, Gösta Grahne: On the Representation and Querying of Sets of Possible Worlds. Theor. Comput. Sci. 78(1): 158-187 (1991)

Intuition: (1) will be used to consider all the assignements of propositional variables xi ∈ X. The idea is that when the propositional variable xi is true, ui is mapped to 1 in Q0 . When it is false, vi is mapped to 1 in Q0 . (2) encodes C and (3) encodes the fact that x and x̄ cannot have the same value. The inequalities in (4) ensure the consistency of values taken by the variables xi and x̄i . Constants 5 and 6 are arbitrary, they just need to be different from 0 and 1. (⇐) We prove that, if (Q0 , Q1 ) is a positive instance of query containment then ∀X∃Y C is a positive instance of ∀∃3CN F . Assume that Q0 ⊑ Q1 , i.e., every instantiation of Q0 is a model of Q1 . Consider any truth valuation of the symbols in X. Then, consider an instantiation M of Q0 such that: for every zi in Q0 , zi 7→ 5 if xi is true, otherwise zi 7→ 6. Since M is a model of Q1 (by hypothesis), ui 7→ 1 if xi is true (indeed, since wi ̸= 5, we have wi 7→ 0 and ui 7→ 1 - and for other symbols: x̄i 7→ 0, xi 7→ 1, vi 7→ 0, yi 7→ 5), otherwise vi 7→ 1 (indeed, since yi ̸= 6, we have yi 7→ 0 and vi 7→ 1 - and for other symbols: xi 7→ 0, x̄i 7→ 1, ui 7→ 0, wi 7→ 6). Since M is a model of Q1 , the cl-atoms are mapped to the instantiated cl-atoms in Q0 while satisfying the inequalities, which yields a truth valuation of the symbols in X ∪ Y that satisfies C. We conclude that any any truth valuation of the symbols in X can be extended to a truth valuation of the symbols in Y that satisfies C. (⇒) We prove that if ∀X∃ Y C is a positive instance of ∀∃3CN F then (Q0 , Q1 ) is a positive instance of query containment. Assume ∀X ∃ Y C is a positive instance of ∀∃ 3CN F . Let M be any instantiation of Q0 . Consider the following truth assignment of X: let xi 7→ true if zi is instantiated by 5, otherwise xi 7→ f alse. By hypothesis, this truth assignment can be extended to a truth assignment of Y that satisfies C. We consider the following assignment of the variables of Q1 , which shows that M is a model of Q1 : • For each i ∈ {1, . . . n}: if zi is instantiated by 5, then wi 7→ 0, ui 7→ 1, vi 7→ 0, yi 7→ 5; otherwise, vi 7→ 1, yi 7→ 0, ui 7→ 0, wi 7→ c, where c is the instantiation of zi . • The other variables are mapped to the truth assignement of the corresponding literal. Then, we obtain a homomorphism from the standard atoms of Q1 (i.e., the vali - and cl-atoms) to M , and we check that the ̸=-atoms are satisfied.

Complements to Section 4

Remark on the existence of a complete abstraction. To ensure the existence of complete Σ-abstractions for all queries, one may enrich the mapping with rules of the form p(x1 , . . . , xn ) → ⊤(x1 ) ∧ . . . ∧ ⊤(xn ) for all the source predicates p/n , see e.g., (Cima, Lenzerini, and Poggi 2019). However, this amounts to transferring all data values to the ontological level, whereas the role of a mapping is precisely to select relevant data. Moreover, this may lead to very unintuitive minimally complete abstractions, as illustrated by the next example. Example 25. Consider an OBDA specification with source schema S = {s-cat(·), s-owner(·, ·)} about cats and their owners, and a mapping M = {s-cat(x) → cat(x)}. Let qS (x) = ∃y.s-owner(x, y) ∧ s-cat(y) asking for the owners of cats. There is no complete abstraction of qS because owners are not transferred to the ontological level. If we add to M the rule s-owner(x, y) → ⊤(x) ∧ ⊤(y), then M(qS ) = ⊤(x) ∧ ∃y.Cat(y) is a minimally complete abstraction of qS , which, by the semantics of ⊤, retrieves all the database values as soon as the data mentions a cat. For practical use, it seems preferable to identify and exclude the queries that do not admit a complete M-abstraction, because such queries are intrinsically not relevant to abstraction through M. Proposition 11. A CQ̸=,C qS (⃗x) has a complete Σ-abstraction iff for all x ∈ ⃗x there are m ∈ M and a homomorphism h : body(m) → qS (⃗x) s.t. x ∈ h(fr(m)). A UCQ̸=,C QS (⃗x) has a complete Σ-abstraction iff each qi (⃗x) ∈ QS has one. Proof. • For a CQ̸=,C qS (⃗x): (⇒) Let g be an injective substitution of the variables in qS by fresh constants (i.e., that do not occur in qS ), and let D be the obtained S-database, i.e., D = g(qS ). In particular, g(⃗x) ∈ qS (D). Hence, for every complete Σ-abstraction QO of qS , g(⃗x) ∈ Qcert x) are transferred by M to the ontological level. For any O (D, Σ), which implies that the constants from g(⃗ variable x ∈ ⃗x, let c = g(x), and let m ∈ M and hm be a homomorphism from body(m) to D that map a variable y from fr(m) to c. The substitution g can be seen as a bijective mapping from terms(qS ) to terms(D) (which maps variables to fresh constants and constants to themselves). Then, the composition h = g −1 ◦ hm defines a homomorphism from body(m) to qS such that h(y) = x, i.e., x ∈ h(fr(m)). (⇐) The following is known: (i) for any S-database D and any homomorphism hs from qS to D, there is a homomorphism h′ from M(qS ) to M(D) such that, for all variable x ∈ vars(qS ) ∩ vars(M(qS )), h′ (x) = hs (x). Now, let D be an Sdatabase and hs be a homomorphism from qS to D with ⃗c = hs (⃗x). If for all x ∈ ⃗x there are m ∈ M and a homomorphism h from body(m) to qS (⃗x) such that x ∈ h(fr(m)), then ⃗x ⊆ vars(M(qS )), hence, by (i), there is a homomorphism h′

from M(qS ) to M(D) such that h′ (⃗x) = hs (⃗x) = ⃗c, i.e., ⃗c ∈ M(qS )(M(D)). Therefore, ⃗c ∈ M(qS )cert (D, Σ). We conclude that M(qS ) is a complete Σ-abstraction of qS . • For a UCQ̸=,C QS (⃗x): (⇒) Let qi ∈ QS . We have qi ⊑ QS , i.e., (i) for every S-database D, qi (D) ⊆ QS (D). Let QO be a complete Σ-abstraction of QS , i.e., such that (ii) for every S-database D, QS (D) ⊆ Qcert O (D, Σ). From (i) and (ii), we conclude that QO is a complete Σ-abstraction of qi . (⇐) For each qi ∈ QS , let QiO be a complete Σ-abstraction of qi . Let QO be the union of all QiO : since it is a complete Σ-abstraction of each CQ qi ∈ QS , it is also a complete Σ-abstraction of QS .

Proposition 14. For any databases D and D′ on S, if Σ(D) |= M(D′ ), then: 12 1. ModΣ (D) ⊆ ModM (D′ ). ′ cert 2. Hence: for any QO on O, Qcert O (D , M) ⊆ QO (D, Σ). Proof. Assume Σ(D) |= M(D′ ). Note that ModΣ (D′ ) ⊆ ModM (D′ ) is always true, by the monotonicity of first-order logic. We will prove that ModΣ (D) ⊆ ModΣ (D′ ). Let J ∈ ModΣ (D), i.e., D ∪ J |= M and J |= R. We have to prove that D′ ∪ J |= M. By assumption M(D′ ) can be mapped (by homomorphism) to Σ(D), and, Σ(D) being a universal model for (D, Σ), it can be mapped to J. Hence, M(D′ ) can be mapped to J, i.e., J |= M(D′ ). Therefore, D′ ∪ J |= D′ ∪ M(D′ ). Furthermore, by definition of the chase, D′ ∪ M(D′ ) |= M, hence D′ ∪ J |= M. We conclude that J ∈ ModΣ (D′ ). ′ 1. 2. Let ⃗c ∈ Qcert c ∈ QO (J), for all J ∈ ModM (D′ ). Since ModΣ (D) ⊆ ModM (D′ ) O (D , M). By definition of certain answers, ⃗ ′ ′ by Point 1, we also have that ⃗c ∈ QO (J ), for each J ∈ ModΣ (D), hence ⃗c ∈ Qcert O (D, Σ). Lemma 16 is obtained as a corollary of the following proposition: Proposition 26. Let σSi be a grounding of qSi ∈ split(QS ). Then, for any mapping rule m: 1. For all h : body(m) → qSi , σSi ◦ h is a homomorphism from body(m) to σSi (qSi ); 2. For all h′ : body(m) → σSi (qSi ), (σSi )−1 ◦ h′ is a homomorphism from body(m) to qSi . Note that Point 1 holds for any CQ̸=,C , while Point 2 relies on the injectivity of σSi and the special handling of constants from body(m). Proof. 1. Since h is a homomorphism from body(m) to qSi and σSi is a homomorphism from qSi , σSi ◦ h is a homomorphism from body(m) to σSi (qSi ). 2. Wlog, we assume that m and qSi do not share any variable. Let fσSi be the function from terms(qSi ) to terms(σSi (qSi )) obtained from σSi by extending its domain (and range) to the constants of qSi , such that each such constant is mapped to itself. The key point is that fσSi is injective. Indeed, by construction, there is a ̸=-atom between any pair of distinct terms in i i i qSi . Hence, fσSi admits an inverse relation fσ−1 i , which is a function (and even a bijection) from terms(σS (qS )) to terms(qS ). S

Let fh′ be the function from terms(body(m)) to terms(σSi (qSi )) obtained from h′ by extending its domain (and range) to the constants of qSi , such that each such constant is mapped to itself. Let fh be the function from terms(body(m)) to terms(qSi ), defined as follows: fh = fσ−1 i ◦ fh′ . Let h be the restriction of fh to the domain vars(body(m)). We show that S

h is a homomorphism from body(m) to qSi . For any atom a ∈ body(m), it holds that fh (a) ∈ qSi : indeed, fh′ (a) ∈ σSi (qSi ) because fh′ (a) = h′ (a) and h′ is a i homomorphism to σSi (qSi ), and, since fσ−1 maps each atom of σSi (qSi ) to an atom of qSi , we obtain fσ−1 i i (fh′ (a)) ∈ qS . S

So, fh (body(m)) ⊆ qSi . It remains to check that fh is the identity on the constants from body(m). By construction, fh′ is the identity on these constants. And this is also true for fσ−1 by construction of split(QS ): there is a ̸=-atom between i S

each variable from qSi ∈ split(QS ) and each constant from body(m), hence σSi cannot ground a variable from qSi by a 12 As regards the formulation of the proposition, note that Σ(D) |= M(D′ ) is stronger than Σ(D) |= Σ(D′ ): indeed, Σ(D) |= M(D′ ) implies R(Σ(D)) |= R(M(D′ )), with R(Σ(D)) ≡ Σ(D) and R(M(D′ )) ≡ Σ(D′ )

constant from body(m); so, fσ−1 i is also the identity on the constants from body(m). Hence, for any atom a ∈ body(m), S fh (a) = h(a), i.e., fh (body(m)) = h(body(m)).

Theorem 12. For any mapping M and any UCQ̸=,C QS that has a complete M-abstraction, there is a UCQ̸=,C QO such that, for any Σ with mapping M, QO is a minimally complete Σ-abstraction of QS . Proof. Let Σ be any OBDA specification with mapping M. Let QO (⃗x) = M(split(QS )). We show that QO is a minimally complete Σ-abstraction of QS . We first point out that QO is a complete Σ-abstraction of QS . Since QS has a complete Σ-abstraction, and QS is logically equivalent to split(QS ), split(QS ) also has a complete Σ-abstraction. By Prop. 11, split(QS ) has a complete Σ-abstraction iff each qSi ∈ split(QS ) has one. By the properties of the chase, we know that if qSi has a complete Σ-abstraction, then M(qSi ) is such abstraction. Hence, M(split(QS )) = QO is a complete Σ-abstraction of QS . To prove that QO is minimally complete, we consider any D and ⃗c ∈ QO (Σ(D)) (i.e., ⃗c is a certain answer to QO on i (D, Σ)) and we show that ⃗c is a certain answer to any complete Σ-abstraction of QS on (D, Σ). Let qO ∈ QO that maps by i i i i hi to Σ(D) with hi (⃗x) = ⃗c. Let qS ∈ split(QS ) such that qO = M(qS ). Consider hi (qS ): all the variables shared between i qSi and qO have been instantiated, in particular, ⃗x in qSi has been instantiated by ⃗c in hi (qSi ). Let σi be a grounding of hi (qSi ), and let Di = σi (hi (qSi )). Since qSi maps to Di by the homomorphism defined by σi ◦ hi , and σi (hi (⃗x)) = hi (⃗x) = ⃗c, we have ⃗c ∈ qSi (Di ). i i i ), since the )) = hi (qO )). Moreover, σi (hi (qO From Lemma 16, M(σi (hi (qSi ))) ≡ σi (hi (M(qSi )), i.e., M(Di ) ≡ σi (hi (qO i i i domain of σi does not contain any variable from hi (qO ), hence M(Di ) ≡ hi (qO ). In particular, M(Di ) maps to hi (qO ), cert i (Di , Σ) ⊆ and since hi (qO ) ⊆ Σ(D), we have M(Di ) maps to Σ(D). So, by Prop. 14, for all ontological query Q, Q Qcert (D, Σ). Let Q be any complete Σ-abstraction of QS . Since ⃗c ∈ qSi (Di ), we have ⃗c ∈ QS (Di ), hence ⃗c ∈ Qcert (Di , Σ). Since Qcert (Di , Σ) ⊆ Qcert (D, Σ), we have ⃗c ∈ Qcert (D, Σ). We conclude that QO is a minimally-complete Σ-abstraction of QS .

C C.1

Complements to Section 5

Known results on the (non-)existence of maximally sound abstractions

As shown in (Cima, Lenzerini, and Poggi 2019), a UCQ may not have a maximally sound M-abstraction in that class. The following example illustrates such a case, and it is still valid if the target class is UCQ̸=,C . Example 27 (from (Cima, Poggi, and Lenzerini 2023), proof of Th. 5.2.). Let M be the following (GAV) mapping:  s1 (x) → q(x)    s2 (x) ∧ s5 (x) → t(x) M=  s (y) ∧ s3 (x, y) → p(x, y)   1 s2 (x) ∧ s4 (x, y) → p(x, y) Let qS = ∃u.s1 (u) ∧ s2 (u). Any maximally sound M-abstraction of qS is equivalent to an infinite union of pairwise incomparable Boolean CQs of the following shape: ! n ^ n qO = q(u0 ) ∧ p(ui−1 , ui ) ∧ t(un ) for n ∈ N i=1

Hence, it is not possible to express a maximally sound M-abstraction of qS as a UCQ (nor a UCQ̸=,C ). Let us insist on the importance of comparing ontological queries with ⊑M and not simply ⊑. For that, we can rely on j j i i the following equivalence: qO ⊑M qO iff M− (qO ) ⊑ M− (qO ). Note that if the atom s5 (x) in the second mapping rule n 0 were removed, then the infinite union of qO (n ∈ N) would become equivalent to qO , because, for all n ∈ N, we would have − n − 0 0 M (qO ) ⊑ M (qO ) = ∃u0 .s1 (u0 ) ∧ s2 (u0 ); then qO would even be a perfect abstraction of qS . In (Cima, Lenzerini, and Poggi 2019), it is also shown that a maximally sound Σ-abstraction is expressible as a UCQ (and can be computed) in a quite restricted case: qS is a (U)CQJFE, M is a pure GAV mapping and the ontology is DL-LiteRDF S . A GAV mapping is pure if each variable in the head of a rule occurs only once. DL-LiteRDF S is the restriction of DL-LiteR to its Datalog part, i.e., rule heads have no existential variables.

C.2

Proofs of Section 5

Let MA be an abstract mapping. The domain of MA is defined as dom(MA ) = {I1 | (I1 , I2 ) ∈ MA } and its set of models w.r.t. an instance I1 is defined as ModMA (I1 ) = {I2 | (I1 , I2 ) ∈ MA }. Definition of a maximum recovery. On can find two equivalent definitions of a maximum recovery in the literature. The first one, given in Section 5, comes from (Arenas et al. 2009); in that paper, they actually define the notion of a C-maximum recovery, i.e., a maximum recovery for the class of queries C; when C can be any class of queries, it is a maximum recovery. This definition has the advantage of being intuitive and well suited to discussing query abstraction; however in the proofs, we also rely on an alternative definition of a maximum recovery, from (Arenas, Pérez, and Riveros 2009), which is the following. Let MA be an abstract mapping from S to T and M′A be an abstract mapping from T to S. Then M′A is said to be a recovery of MA if (I, I) ∈ MA • M′A for every instance I ∈ dom(MA ). Let M′A and M′′A be recoveries of MA . Then M′A is said to be at least as informative as M′′A for MA , which is denoted by M′′A ⪯MA M′A , if MA • M′A ⊆ MA • M′′A . Finally, M′A is a maximum recovery of MA if for every recovery M′′A of MA , it is the case that M′′A ⪯MA M′A . Next Proposition 28 gives useful properties of maximum recoveries. This proposition uses the notion of a reduced recovery: an abstract mapping M′A is a reduced recovery of MA if M′A is a recovery of MA and for every (I1 , I2 ) ∈ MA • M′A , we have I2 ∈ dom(MA ). Proposition 28 (Proposition 3.8 from (Arenas, Pérez, and Riveros 2009)). Let MA and M′A be abstract mappings. Then the following conditions are equivalent: 1. M′A is a maximum recovery of MA . 2. M′A is a reduced recovery of MA and MA = MA • M′A • MA . 3. M′A is a recovery of MA and for every (I1 , I2 ) ∈ MA • M′A , it is the case that ∅ ⊊ ModMA (I2 ) ⊆ ModMA (I1 ). We also use the characterisation given by next Theorem 30, which involves the notion of a witness model: Definition 29 (Witness Model). An instance J on T is a witness model for I under MA if: 1. (I, J) ∈ MA , and 2. for every instance I ′ on S such that (I ′ , J) ∈ MA , we have ModMA (I) ⊆ ModMA (I ′ ). Theorem 30 (Theorem 3.12 from (Arenas, Pérez, and Riveros 2009)). A mapping MA has a maximum recovery if and only if for every I ∈ dom(MA ), there exists a witness model for I under MA . The characterisations of a maximum recovery from Proposition 28 and Theorem 30 still hold for abstract mappings that are relations between infinite instances. Indeed, one can check that the proofs in (Arenas, Pérez, and Riveros 2009) do not use any property of a finite instance. Lemma 20. Let QS be a query on S, MA be an abstract mapping from S to T that has a maximum recovery M′A . Let QT be a perfect rewriting of QS through M′A . Then, for any S-instance I: (1) certainMA (QT , I) ⊆ QS (I), and (2) certainMA (Q′T , I) ⊆ certainMA (QT , I) for any query Q′T such that certainMA (Q′T , I) ⊆ QS (I). Proof. (1) By definition of a recovery, (i) certainMA •M′A (QS , IS ) ⊆ QS (IS ), for any S-instance IS . We show that (ii) certainMA •M′A (QS , IS ) = certainMA (QT , IS ) for any S-instance IS . From (i) and (ii), we have certainMA (QT , IS ) ⊆ QS (IS ) for any S-instance IS . Let IS be any S-instance: certainMA •M′A (QS , IS ) =

QS (IS′ ) (by definition of certain answers)

′ )∈M •M′ (IS ,IS A A

QT (IT ) (because QT is a perfect rewriting of QS through M′A )

(IS ,IT )∈MA

= certainMA (QT , IS ) (2) The proof is by contradiction. Assume there are a query Q′T , which is a sound MA -abstraction of QS , and an Sdatabase D such that certainMA (QT , D) ⊊ certainMA (Q′T , D). This implies there is ⃗c ∈ certainMA (Q′T , D) such that ⃗c ∈ / certainMA (QT , D). And since we know from (1) that certainMA •M′A (QS , D) = certainMA (QT , D), we have ⃗c ∈ / certainMA •M′A (QS , D). This implies there exists (D, D′ ) ∈ MA • M′A such that ⃗c ∈ / QS (D′ ). By Proposition ′ ′ ′ ′ 28, we have ModMA (D ) ⊆ ModMA (D). Thus, certainMA (QT , D) ⊆ certainMA (QT , D ). But since Q′T is a sound MA -abstraction of QS , we also have certainMA (Q′T , D′ ) ⊆ QS (D′ ). Therefore, certainMA (Q′T , D) ⊆ QS (D′ ), which contradicts the assumption that ⃗c ∈ certainMA (Q′T , D) and ⃗c ∈ / QS (D′ ).

Theorem 21. Let M be a (GLAV) mapping from S to O, M∨ be a disjunctive̸=,C mapping that is a (concrete) maximum recovery of M, and QS be a UCQ̸=,C on S. Then M∨ − (QS ) is a maximally sound M-abstraction of QS . Proof. Follows directly from Lemma 20. Theorem 23. 1. 2.

Let Σ be an OBDA specification with FO-rewritable R. Then:

MΣ ∨ is a (concrete) maximum recovery of Σ. − For any UCQ̸=,C QS on S, MΣ ∨ (QS ) is a maximally sound Σ-abstraction of QS .

Proof. First note that MΣ ∨ is well defined because the ruleset R is fus, hence M ∪ R too, which ensures that the rewriting of each rule head of M ∪ R against M ∪ R is a finite disjunction of CQs. Let ΣA and MΣ A be the abstract mappings associated with Σ and MΣ ∨ , respectively. Point 2 of the theorem follows directly from its Point 1 using Lemma 20. We will now prove Point 1. To show that MΣ ∨ is a maximum recovery of Σ, we will rely on the third point of Proposition 28 and show that: (1) MΣ A is a recovery of ΣA , and (2) for every (I1 , I2 ) ∈ ΣA • MΣ A , it is the case that ∅ ⊊ ModΣA (I2 ) ⊆ ModΣA (I1 ). Note that, since instances on the source schema are databases, I1 and I2 are databases. In the following, we denote by ′ m = ∀⃗x∀⃗y .B[⃗x, ⃗y ] → ∃⃗z.H[⃗x, ⃗z] a rule in M, and by m′ = ∀⃗x∀⃗z.H[⃗x, ⃗z] ∧ C(⃗x) → ∃z⃗′ .H ′ [⃗x, z⃗′ ] a rule in MΣ ∨ , where H is a Σ-rewriting of H (hence, a disjunction). Σ (1) We show that MΣ A is a recovery of ΣA , that is, for all D over S, (D, D) ∈ ΣA • MA , which is equivalent to: there Σ is an instance I such that (D, I) ∈ ΣA and (I, D) ∈ MA . Let us consider I = Σ(D). By the properties of the chase, Σ ′ ′ Σ (D, Σ(D)) ∈ ΣA . Let us show that (Σ(D), D) ∈ MΣ A , i.e., Σ(D) ∪ D |= M∨ . Given any m : H → H ∈ M∨ , we show that ′ Σ(D)∪D |= m . Assume that there exists a tuple of constants ⃗c such that Σ(D) |= ∃⃗z.H[⃗c, ⃗z]∧C[⃗c] (frontier variables can only be mapped to constants because of the C-atoms). We need to show that D |= ∃z⃗′ .H ′ [⃗c, z⃗′ ]. Let qH (⃗x) = ∃⃗z.H[⃗x, ⃗z] be the CQ associated with H and QH ′ (⃗x) = ∃z⃗′ .H ′ [⃗x, z⃗′ ] be the UCQ associated with H ′ . Since we have C(⃗c) and Σ(D) |= ∃⃗z.H[⃗c, ⃗z], cert cert we have ⃗c ∈ qH (Σ(D)). By the properties of the chase, qH (D, Σ) = qH (Σ(D)), hence ⃗c ∈ qH (D, Σ). By definition of cert m′ , QH ′ is a (perfect) Σ-rewriting of qH , hence QH ′ (D) = qH (D, Σ). So, ⃗c ∈ QH ′ (D), that is D |= ∃z⃗′ .H ′ [⃗c, z⃗′ ]. We conclude that Σ(D) ∪ D |= MΣ ∨. Σ (2) We show that MΣ A is maximum. Relying on Proposition 28, we show that for all (D1 , D2 ) ∈ ΣA • MA , we have ∅ ̸= ModΣA (D2 ) ⊆ ModΣA (D1 ). We know that ModΣA (D2 ) ̸= ∅ as it contains at least Σ(D2 ). Let I ∈ ModΣA (D2 ). Note that I |= R (because R and I are both only over O). So, to prove that I ∈ ModΣA (D1 ), we only have to show that D1 ∪ I |= M. Let m = B → H be a rule in M. Assume that there exists a tuple of constants ⃗c such that D1 |= ∃⃗y .B[⃗c, ⃗y ]. ′ ′ Σ ′ We show that I |= ∃⃗z.H[⃗c, ⃗z]. By definition of MΣ ∨ , we have m = H → H ∈ M∨ where H is a Σ-rewriting of H. Since Σ Σ (D1 , D2 ) ∈ ΣA •MA , there exists an instance J such that (D1 , J) ∈ ΣA and (J, D2 ) ∈ MA . Since D1 |= ∃⃗y .B[⃗c, ⃗y ] and J ∈ Σ ⃗′ ′ c, z⃗′ ], i.e., ModΣA (D1 ), we have J |= ∃⃗z.H[⃗c, ⃗z]. And since (J, D2 ) ∈ MΣ A , we have J ∪ D2 |= M∨ and thus D2 |= ∃z .H [⃗ cert cert ⃗c ∈ QH ′ (D2 ). Since QH ′ is a (perfect) Σ-rewriting of qH , QH ′ (D2 ) = qH (D2 , Σ), hence ⃗c ∈ qH (D2 , Σ). By definition of certain answers, ⃗c is an answer to qH on all instances from ModΣA (D2 ), in particular ⃗c ∈ qH (I), i.e., I |= ∃⃗z.H[⃗c, ⃗z]. So, D1 ∪ I |= M. We conclude that I ∈ ModΣA (D1 ).

C.3

Maximum recovery of an OBDA specification (additional result)

From Theorem 23, we know that every abstract mapping associated with an OBDA specification where R is FO-rewritable has a maximum recovery that can be expressed as a disjunctive mapping, and we furthermore know how to compute this maximum recovery. The following additional theorem states that every abstract mapping associated with an OBDA specification (without any condition on R) has a maximum recovery. We leave open the question of which mapping language would allow one to specify such a maximum recovery when R is not FO-rewritable. Theorem 31. Any abstract mapping associated with an OBDA specification has a maximum recovery. Proof. By Theorem 30, we know that an abstract mapping MA from S to T has a maximum recovery if and only if for every instance I on S (i.e., database on S), there exists a witness model for I under MA . Let ΣA be an abstract mapping associated with an OBDA specification Σ. Let D be any database on S and let J = Σ(D). By the properties of the chase, J is a universal model for (D, Σ). We will show that J is a witness model for D under ΣA . Let D′ be a database over S such that J ∈ ModΣA (D′ ). Let J ′ = Σ(D′ ). Since J ′ is a universal model for (D′ , Σ), there is a homomorphism from J ′ to J. Since J ′ = Σ(D′ ) and J = Σ(D), by Proposition 14, we have ModΣ (D) ⊆ ModΣ (D′ ), i.e., ModΣA (D) ⊆ ModΣA (D′ ). We conclude that J is a witness model for I under ΣA .

C.4

Non-expressiblity of CQ-maximum recoveries as conjunctive mappings

Let us recall that a CQ-maximum recovery of a (GLAV) mapping is a recovery that maximally recovers the answers to CQs (and not necessarily to UCQs) (Arenas et al. 2009). As pointed out in Section 5, our Theorem 21 contradicts Theorem 4.4 from (Arenas et al. 2009), which states that a CQ-maximum recovery of a GLAV mapping can always be specified by a conjunctive mapping. That paper furthermore proposes an algorithm designed to output such CQ-maximum recovery, given any GLAV mapping M. But then, CQ rewriting through a CQ-maximum recovery would always be finite (hence, expressible as a UCQ or UCQ̸=,C ), which contradicts the fact that a maximally sound M-abstraction of a CQ is not always expressible as a UCQ. Let us take a closer look at these results and show that Theorem 4.4 does not hold true. Relying again on the mapping M from previous Example 27, we show that (1) the conjunctive mapping output by the algorithm from (Arenas et al. 2009) is not a CQ-maximum recovery of M, and (2) in fact, M does not admit any CQ-maximum recovery expressible as a conjunctive mapping. Example 32. Let M be the mapping from Example 27. The maximum recovery of M can be specified by  ′ → s1 (x) m1 = q(x) ∧ C(x) M′ = m′2 = t(x) ∧ C(x) → s2 (x) ∧ s5 (x)  ′ m3 = p(x, y) ∧ C(x) ∧ C(y) → (s1 (y) ∧ s3 (x, y)) ∨ (s2 (x) ∧ s4 (x, y)) The algorithm from (Arenas et al. 2009) outputs the conjunctive mapping M′′ = {m′1 , m′2 }, supposed to be a CQ-maximum recovery of M. Now, consider the database D = {s1 (a), s2 (a), s2 (b), s4 (a, b), s5 (b)} and the CQ qS = ∃u.s1 (u) ∧ s2 (u) from Example 27. Then: M′′ (M(D)) = {s1 (a), s2 (b), s5 (b)} ̸|= qS . If we consider M′ instead of M′′ , we have to use the disjunctive chase to apply M′ (see e.g. (Leclère, Mugnier, and Pérution-Kihli 2023) for details), and we obtain M′ (M(D)) = I1 ∨ I2 , with I1 = {s1 (a), s2 (b), s5 (b), s1 (b), s3 (a, b)} and I2 = {s1 (a), s2 (b), s5 (b), s2 (a), s4 (a, b)}. Since I1 |= qS and I2 |= qS , we have M′ (M(D)) |= qS . In other words, ∅ = certainMA •M′′A (qS , D) ⊊ certainMA •M′A (qS , D) = {()} (with MA , M′A and M′′A being the abstract mappings associated with M, M′ and M′′ , respectively). This shows that M′′ is not maximum for CQs. In fact, the mapping M allows one to show the following: Proposition 33. There is a G(L)AV mapping that does not admit any CQ-maximum recovery expressible as a conjunctive mapping. Proof. Consider again Example 27, which provides a G(L)AV mapping M and a CQ qS that does not admit any maximally sound M-abstraction expressible as a UCQ (or UCQ̸=,C ). Assume that M has a CQ-maximum recovery M′′ that is a conjunctive mapping. Then, M′′− (qS ) is finite (i.e., it is a UCQ̸=,C ). Moreover, let M′ be the maximum recovery of M given in Example 32, and let QO = M′− (qS ). Then: 1. For all database D, certainM•M′′ (qS , D) ⊆ qS (D) because M′′ is a recovery. 2. For all database D, certainM (M′′− (qS ), D) = certainM•M′′ (qS , D) by the properties of perfect query rewriting. 3. From 1 and 2: For all database D, certainM (M′′− (qS ), D) ⊆ qS (D), i.e., M′′− (qS ) is a sound abstraction of qS . 4. From 3 and QO being a maximally sound abstraction of qS : For all database D, certainM (M′′− (qS ), D) ⊆ certainM (QO , D). 5. From 4 and QO not being equivalent to any UCQ̸=,C : There is a database D, such that certainM (M′′− (qS ), D) ⊊ certainM (QO , D). 6. From 5 and the properties of perfect query rewriting: For this database D, certainM.M′′ (qS , D) ⊊ certainM.M′ (qS , D). This contradicts the assumption that M′′ is a CQ-maximum recovery.

Record · ID 303273 · SHA-256 6e7fbf0748f69787
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.