Semantic Characterization of Data Services through Ontologies

1 Introduction

The architecture of many modern Information Systems is based on data services [Zheng et al., 2013], i.e., services deployed on top of data stores, other services, and/or applications to encapsulate a wide range of data-centric operations. Data services are also used to handle the programming logic for data virtualization in a cloud-hosted data storage infrastructure, so as to delegate most administrative tasks to the cloud infrastructure, and effectively realizing the idea of Data-As-A-Service. Furthermore, since big data, which is now imperative in many contexts, may be obtuse, disorganized, and may not make much sense to most potential users, in order to get value from them, it is reasonable to resort to data services built on top of massive amount of raw data.

In order to realize the promises of data services, in particular to foster their reuse, it is of vital importance to well document and clearly specify their semantics. While most current techniques manually associate APIs (Application Programming Interface) to data services, and describe their intended meaning with ad-hoc methods, often using natural language or complex metadata [Carey et al., 2012], we propose a new approach, whose goal is to automatically associate formal semantic descriptions to data services. We base our proposal on the Ontology-Based Data Access (OBDA) paradigm [Poggi et al., 2008]. An OBDA specification consists of an ontology expressed in Description Logic (DL) [Baader et al., 2003], the schema of the data sources forming the information system, and a mapping between the source schema and the ontology. The ontology is a formal representation of the underlying domain, and the mapping specifies the relationship between the data at the sources and the elements in the ontology. The semantics of data services can be thus expressed using the elements of the domain ontology, which is assumed to be familiar to the consumer of data services.

But how can we automatically produce a semantic characterization of a data service, having an OBDA specification available? The idea is to exploit a new reasoning task over the OBDA specification, that works as follows: we express the data service in terms of a query over the sources, and we aim at automatically deriving the query over the ontology that best describes the data service, given the mapping. The following example illustrates this idea.

Example 1. Let Σ = 〈O, S,M〉 be as follows: O = { ErasmusStudent ⊑ Student, MathStudent ⊑ Student, Student ⊑ ¬Professor } S = { s1, s2, s3, s4, s5 } M = { {(x) | s1(x)} → {(x) | Student(x)}, {(x) | s2(x)} → {(x) | Student(x)}, {(x) | s3(x)} → {(x) | Professor(x)}, {(x) | s1(x), s4(x, y)} → {(x) | ErasmusStudent(x)}, {(x) | s1(x), s5(x, y)} → {(x) | MathStudent(x)} }

One can verify that the query over O that best describes the data service qS = {(x) | s1(x)} ∨ {(x) | s2(x)} in terms of O is qO = {(x) | Student(x)}.

Most of (if not all) the literature about managing data sources through an ontology [Lenzerini, 2018; Xiao et al., 2018; Ortiz, 2018; Bienvenu, 2016] deals with user queries expressed over the ontology, and studies the problem of finding an ontology-to-source rewriting, i.e., a query over the source schema that, once executed over the data, provides the answers to the original query. Here, the problem is reversed, because we start with a source query and we aim at deriving a corresponding query over the ontology, called a source-toontology rewriting (s-to-o rewriting for short). Thus, we deal with a sort of reverse engineering problem, which is novel in the investigation of both OBDA and data integration.

The notions introduced in this paper are relevant in a plethora of scenarios. For the sake of brevity, we mention only three of them. Following the ideas in [Cima, 2017], it can be shown that our notions of s-to-o rewriting can be used to provide the semantics of open datasets and open APIs published by organizations, which is a key aspect for unchaining all the potentials of open data. In [Lutz et al., 2018], the concept of realization of source queries, similar to one of the notions studied here, is used for checking whether the mapping provides the right coverage for expressing the relevant data services at the ontology level. Our notions are also useful for a semantic-based approach to source profiling [Abedjan et al., 2017], in particular for describing the structure and the content of a data source in terms of the business vocabulary.

The contributions provided by this paper can be summarized as follows. We propose a formal framework for the problem of semantically characterizing a data service through an ontology (Section 3). We introduce the notions of perfect, sound, and complete s-to-o rewritings, and we define two basic reasoning tasks, namely verification and computation. The former checks whether a given query is an s-to-o rewriting of a data service, whereas the latter computes one such rewriting. We show that, although the ideal notion is the one of perfect s-to-o rewriting, there are cases where, with the given mapping, no query over the ontology can precisely characterize the data service at hand. Thus, we introduce maximally sound and minimally complete s-to-o rewritings, which intuitively aim at approximating the perfect s-to-o rewriting of a data service at best, with the goal of either precision (sound rewriting), or recall (complete rewriting). We study both the verification, and the computation problem for complete (Section 4), sound (Section 5) and perfect (Section 6) s-to-o rewritings in one of the most popular OBDA setting considered in the literature, namely where the ontology language is DL-LiteR, each mapping assertion maps a conjunctive query (CQ) over the source to a CQ over the ontology, and both the data service and the s-to-o rewriting are expressed as unions of CQs. For perfect and complete s-to-o rewritings we present algorithms for verification and computation, and characterize the complexity of both tasks. For the case of sound s-to-o rewritings, we do the same for verification, and then we precisely determine the cases where a maximally sound rewriting is not guaranteed to exist. We single out a restricted setting for OBDA specifications that is still meaningful from the point of view of expressive power, and guarantees the existence of maximally sound s-to-o rewritings (Section 7). For such restricted setting, we provide algorithms and complexity results for verification and computation of maximally sound s-to-o rewritings. Preliminaries (Section 2), and conclusions (Section 8) complete the paper.

To the best of our knowledge, the problem studied in this paper has been (partially) addressed only in [Cima, 2017; Lutz et al., 2018]. The former provides complexity upper bounds for complete s-to-o rewritings, and the latter focuses on both DL-LiteR and the EL family of ontology languages, and studies perfect s-to-o rewritings only, under a slightly different semantics with respect to the one proposed here.

2 Preliminaries

We assume basic knowledge about databases [Abiteboul et al., 1995] and DLs [Baader et al., 2003]. In what follows, we use σ(x) to denotes the size of x.

A database schema is a set of predicate symbols, each with a specific arity, and a set of integrity constraints. Given a schema S, an S-database D is a set of facts P(⃗t) satisfying all integrity constraints in S, where P is a predicate in S of arity n, and ⃗t is an n-uple of constants, each taken from a denumerable infinite set of symbols, where each such symbol is called an S-constant, or simply constant.

In its general form, an L-query q over a schema S is a function in a certain class L that can be evaluated over an Sdatabase D to return a set of answers qD , each answer being a tuple of constants. A conjunctive query (CQ) q over a schema S is an expression of the form {⃗t | φ(⃗t, ⃗y)}, also denoted q(⃗t), where ⃗t is a tuple of terms, each term being either a constant or a variable, ⃗y is a tuple of variables not appearing in ⃗t, called the existential variables of q, and φ(⃗t, ⃗y) is either ⊥ (in this case we also say that the whole q is ⊥), or a finite conjunction of atoms of the form P(t1, ..., tn), where P is an n-ary predicate symbol of S and each tj is either a constant, or a variable in ⃗t ∪ ⃗y. We call φ and ⃗t the body and target list of q, respectively, and we sanction that every variable in ⃗t appears in φ. If ⃗t is empty, then the query is a boolean query. A union of CQs (UCQ) is a union of a finite set of conjunctive queries (called its disjuncts) with same arity. If not otherwise stated, we implicitly assume that all CQs of a UCQ have the same target list 1 . If q1, q2 are two queries with the same arity over S, q1 is contained in q2, denoted as q1 ⊑ q2 if for every S-database D, qD 1 ⊆ qD 2 . Containment of CQs and UCQs is characterized in terms of homomorphism [Chandra and Merlin, 1977; Sagiv and Yannakakis, 1980]. In what follows, we also consider CQs with no existential variables occurring more than once (CQJFE), and unions thereof (UCQJFE).

We consider ontologies expressed in DL-LiteR, the member of the DL-Lite family [Calvanese et al., 2007] that underpins OWL2QL [Motik et al., 2012], i.e., the profile of OWL2 especially designed for the OBDA scenarios. In DL-LiteR axioms have the following forms:

where B1, B2 are basic concepts, i.e., expressions of the form A, ∃P, or ∃P -, with A and P atomic concept (atomic concepts include the universal concept ⊤) and atomic role, respectively, and R1 and R2 basic roles, i.e., expressions of the form P, or P -. We will also consider one sublanguage of DL-LiteR, namely DL-LiteRDFS, where both disjointness axioms, and concepts of the forms ∃P or ∃P - in the right-hand side of the inclusion axioms, are ruled out.

An OBDA specification Σ is a triple 〈O, S,M〉 [Poggi et al., 2008], where O is a DL ontology, S is a database schema, called the source schema, and M is a set of mapping assertions (or simply mappings) relating S to O, i.e., assertions of the form qS → qO, where qS and qO are CQs of the same arity over S and O, respectively.

Mappings of the above form are called GLAV mappings. Special cases are GAV (Global-as-View) and LAV (Local-as- Views) mappings [Doan et al., 2012]: in a GAV (resp., LAV) mapping, qO (resp., qS) is simply an atomwithout existential variables. A GAV mapping is called pure if qO does not have constants or repeated variables, i.e., it is either of the form A(x), or R(x, y), with x, y different variables.

1 All the results of this paper can be generalized to the case of UCQs whose disjuncts may have different target lists.

An interpretation B for O is a model for Σ relative to an S-database D if (i) it is a model of O, and (ii) for every mapping qS → qO in M, we have qD S ⊆ qB O , where qB O denotes the answers of qO over the interpretation B (seen as a database). The set of models for Σ relative to D is denoted by ModD(Σ), and D is said to be consistent with Σ if ModD(Σ) ̸= ∅.

If qS is a CQ, we denote byM(qS) the query obtained by applying the chase [Maier et al., 1979] w.r.t. M to the socalled freezing of qS, with the proviso that M(qS) is ⊥ if qS is ⊥, and ⊤ if its chase is empty. Note that the freezing of qS is the database obtained by seeing the atoms of qS as facts.

Given an OBDA specification Σ = 〈O, S,M〉, a query qO over O, and an S-database D, the certain answers of qO w.r.t. Σ and D are the set of tuples ⃗t of S-constants such that ⃗t ∈ qB O , for every B ∈ ModD(Σ). An O-to-S Σ-rewriting of a query qO over O is a query qS over S of the same arity as qO such that for every S-database D, qD S is a subset of the certain answers of qO w.r.t. Σ and D. A perfect O-to-S Σrewriting of qO, denoted by certqO,Σ, is a query over S of the same arity as qO such that for every S-database D, cert DqO,Σ coincides with the certain answers of qO w.r.t. Σ and D. We say that query q1 over O is equivalent w.r.t. Σ to query q2 over O if certq1,Σ ≡ certq2,Σ. It is easy to see that, with a slight modification for taking care of the presence of ⊤ and ⊥ in queries, we can use the results in [Levy et al., 1995] to show that, if O has no axiom, and qO is a UCQ over O, one can compute a UCQ over S, denoted by REWM(qO), that is equivalent to certqO,Σ.

We conclude the section with some observations about the case where the ontology O in Σ is a DL-LiteR ontology. In this case, it is well-known (see, e.g., [Calvanese et al., 2009]) that an S-database D is consistent with Σ if and only if cert DVO,Σp = ∅, where Σp is obtained from Σ by eliminating the disjointness axioms from O, and VO is the Oviolation query, i.e., the boolean UCQ obtained by including a CQ qd for each disjointness axiom, where qd has the form {()|B1(x) ∧ B2(x)} (resp., {()|R1(x, y) ∧ R2(x, y)}) for the axiom B1 ⊑ ¬B2 (resp., R1 ⊑ ¬R2). Also, we denote by V t1,...,tn O the UCQ over Owith target list (t1, . . . , tn) obtained by adding ⊤(t1) ∧ . . . ∧ ⊤(tn) (written also as ⊤(t1, . . . , tn)) to each of the disjuncts of VO.

If qO is a (U)CQ-query over O, we denote by PerfRefqO,O the UCQ computed by executing the algorithm PerfectRef described in [Calvanese et al., 2007] on qO and O (again, slightly modified to take care of ⊤ and ⊥), and by PerfRefqO,Σ the UCQ REWM(PerfRefqO,O). Note that PerfectRef ignores the disjointness axioms in O, and if D is consistent with Σ, then PerfRefDqO,Σ computes exactly cert DqO,Σ. From these observations, and exploiting the results in [Calvanese et al., 2012; Levy et al., 1995], it is possible to prove that for an OBDA specification Σ = 〈O, S,M〉, if O is a DL-LiteR ontology, and qO(⃗t) is a (U)CQ-query over O, then certqO,Σ ≡ PerfRefqO,Σ ∨ PerfRefV⃗tO ,Σ.

3 Framework

We implicitly refer to an OBDA specification Σ = 〈O, S,M〉. Intuitively, given a data service expressed as a query qS over S, we aim at finding the query over O that precisely characterizes qS w.r.t. Σ. Since the evaluation of queries over O is based on certain answers, this means that we aim at finding a query over O whose certain answers w.r.t. Σ and D exactly capture the answers of qS w.r.t. D, for every S-database D. So, we are naturally led to the notion of perfect s-to-o rewriting. In what follows, qS refers to a query over S, and qO to a query over O of the same arity.

Definition 2. qO is a perfect S-to-O Σ-rewriting of qS if for every S-database D, ModD(Σ) ̸= ∅ implies qD S = certDqO,Σ.

The above notion is similar, but not equivalent, to the notion of realization in [Lutz et al., 2018]. Indeed, while the latter sanctions that qD S = certDqO,Σ for all S-databases, in our notion the condition is limited to the S-databases that are consistent with Σ. The difference between the two notions is highlighted by the following example.

Example 3. Refer to Example 1, and consider again the query qS = {(x) | s1(x)} ∨ {(x) | s2(x)} over S, and the query qO = {(x) | Student(x)} over O. For the S-database D = {s1(a), s3(a), s4(a, b)}, we have that qD S = {〈a〉}, while, since D is inconsistent with Σ, cert DqO,Σ contains all S-constants of D (including, for example, the tuple 〈b〉). It follows that qO is not a realization of qS in Σ, whereas, since qD S = cert DqO,Σ for every S-database D consistent with Σ, qO is a perfect S-to-O Σ-rewriting of qS.

As noted in [Cima, 2017; Lutz et al., 2018] and illustrated in the next example, perfect s-to-o rewritings may not exist.

Example 4. Refer again to Example 1, and consider the data service expressed as the source query qS = {(x) | s1(x)}. By inspecting the mappings, one can see that, since the certain answers of Student include the values stored both in s1 and in s2, such concept is too general for exactly characterizing qS. On the other hand, both ErasmusStudent and MathStudent are too specific, and therefore we can conclude that no perfect S-to-O Σ-rewriting of qS exists.

In order to cope with the situations illustrated in the example, we introduce the notions of sound and complete s-too rewritings, which, intuitively, provide sound and complete approximations of perfect rewritings, respectively.

Definition 5. qO is a sound (respectively, complete) S-to-O Σ-rewriting of qS if for every S-database D, ModD(Σ) ̸= ∅ implies cert DqO,Σ ⊆ qD S (resp., qD S ⊆ cert DqO,Σ).

Example 6. We refer to Example 4, and observe that {(x) | ErasmusStudent(x)∧MathStudent(x)} is a sound S-to-O Σrewriting of qS = {(x) | s1(x)}, whereas {(x) | Student(x)} is a complete S-to-O Σ-rewriting of qS .

Obviously, qO is a perfect S-to-O Σ-rewriting of qS if and only if qO is a sound and complete S-to-O Σ-rewriting of qS . There are also interesting relationships between the notions of S-to-O Σ-rewritings introduced here and the usual notions of rewritings studied in OBDA.

Proposition 7. qO is a complete S-to-O Σ-rewriting of qS if and only if qS is an O-to-S Σ-rewriting of qO. If qS is a perfect O-to-S Σ-rewriting of qO, then qO is a perfect S-toO Σ-rewriting of qS .

It is easy to see that different sound or complete s-to-o rewritings of qS may exist, and therefore it is reasonable to look for the "best" approximations of qS, at least relative to a certain class of queries.

Definition 8. qO ∈ L is an L-maximally sound (respectively, L-minimally complete) S-to-O Σ-rewriting of qS if qO is a sound (respectively, complete) S-to-O Σ-rewriting of qS , and no q′ ∈ L exists such that (i) q′ is a sound (resp., complete) S-to-O Σ-rewriting of qS, (ii) certqO,Σ ⊑ certq′ ,Σ (resp., certq′ ,Σ ⊑ certqO,Σ), and (iii) there exists an S-database D s.t. cert DqO,Σ ⊂ cert Dq′ ,Σ (resp., cert Dq′ ,Σ ⊂ cert DqO,Σ).

Example 9. We refer again to Example 4, and observe that while {(x) | Student(x)} is a minimally complete S-to-O Σrewriting of qS = {(x) | s1(x)} in the class of UCQs, both {(x) | ErasmusStudent(x)}, and {(x) | MathStudent(x)} are maximally sound S-to-O Σ-rewritings of qS in the class of CQs, while qO = {(x) | ErasmusStudent(x)} ∨ {(x) | MathStudent(x)} is so in the class of UCQs.

Given the general framework presented so far, it is natural to consider the following two basic computational problems, for classes LS and LO of queries:

• Verification: given Σ = 〈O, S,M〉, qS ∈ LS over S and qO ∈ LO over O of the same arity as qS, verify whether qO is a sound (resp., complete, perfect) S-to-O Σ-rewritings of qS.
• Computation: given Σ = 〈O, S,M〉, and qS ∈ LS over S compute any LO-maximally sound (resp., LOminimally complete, perfect) S-to-O Σ-rewriting of qS, if it exists.

In the rest of this paper, if not otherwise stated, we refer to the most common setting studied in OBDA, i.e., where (i) the ontology is expressed in DL-LiteR, (ii) S is a relational database schema without integrity constraints, and (iii) both LO and LS denote the class of UCQs. Interestingly, in this case, we have the following.

Proposition 10. If q1 and q2 are UCQ-minimally complete (resp., UCQ-maximally sound) S-to-O Σ-rewritings of qS, then they are equivalent w.r.t. Σ.

4 Complete Source-to-Ontology Rewritings

In this section, we study both the verification and the computation problem for complete s-to-o rewritings.

We first address the verification problem. Suppose we want to check whether qO is a complete S-to-O Σ-rewriting of qS . Obviously, if qS is contained in PerfRefqO,Σ, then for every S-database D consistent with Σ, we have that qD S ⊆ cert DqO,Σ and therefore the answer is positive. However, if qS is not contained in PerfRefqO,Σ, it might be that qO is still a complete S-to-O Σ-rewriting of qS , in particular in the case where the non-emptiness of qS in D reveals the presence of inconsistencies. From this observation, we derive the following.

Algorithm 1 Compute complete s-to-o rewritings

Proposition 11. qO is a complete S-to-O Σ-rewriting of qS(⃗t) if and only if qS ⊑ PerfRefqO,Σ ∨ PerfRefV⃗tO ,Σ.

The following theorem characterizes the complexity of verification for complete s-to-o rewritings.

Theorem 12. The verification problem for complete s-to-o rewritings is NP-complete.

Proof sketch. As for the upper bound, we show how to check the containment qS(⃗t) ⊑ PerfRefqO,Σ ∨ PerfRefV⃗tO ,Σ in NP. For every disjunct q of qS, (i) we guess a query q′ over O with the same arity of qO and size at most the maximum between σ(qO) and σ(V⃗tO ), a sequence ρ of ontology axioms, a query q′′ over S of size σ(M) × σ(q′ ) and a function φ from the variables of q′′ to the variables q, and (ii) we check in PTIME whether we can rewrite either qO or V⃗tO into q′ through ρ, q′′ is in REWM(q′ ), and φ is a homomorphism from q′′ to q. As for the lower bound, the proof of NP-hardness is by a LOGSPACE reduction from the 3-COLOURABILITY problem, which is NPcomplete [Garey et al., 1976].

We point out that the result of NP-hardness holds even when O is empty, M is both a pure GAV mapping and a LAV mapping, and qS, qO are boolean CQs.

We now deal with the computation problem. In particular, we propose Algorithm 1 for computing UCQ-minimally complete s-to-o rewritings.

Intuitively, the algorithm computes the output query as union of CQs obtained by simply applying the mapping M to each CQ qiS in qS, using ⊤ to bind the variables that are not involved in the application of M to qiS .

Theorem 13. Algorithm 1 computes the UCQ-minimally complete S-to-O Σ-rewriting of qS .

The algorithm shows that the UCQ-minimally complete Sto-O Σ-rewriting of qS always exists. Moreover, if qS is a CQ, then it is a CQ. Finally, we observe that the complexity of Algorithm 1 does not depend on O and is in PTIME in σ(qS). Moreover, it is in EXPTIME in σ(M), since it essentially applies the chase using the queries in the mapping. It can be shown that an algorithm for computing the UCQ-minimally complete s-to-o rewritings that is PTIME in the size of all inputs would imply a PTIME algorithm for CQ containment. So, assuming PTIME ̸= NP, the computation problem cannot be solved in PTIME.

5 Sound Source-to-Ontology Rewritings

We now turn to both the verification and the computation problem for sound s-to-o rewritings.

As for verification, we remind the reader that, for an Sdatabase D consistent with Σ, PerfRefDqO,Σ computes exactly cert DqO,Σ. So, intuitively, checking whether qO is a sound Sto-O Σ-rewriting of qS means checking whether for all Sdatabases D, either ModD(Σ) = ∅ or PerfRefDqO,Σ ⊆ qD S . This observation leads to the following characterization.

Proposition 14. qO(⃗t) is a sound S-to-O Σ-rewriting of qS if and only if PerfRefqO,Σ ⊑ qS ∨ PerfRefV⃗tO ,Σ.

The following theorem characterizes the complexity of the verification problem for sound s-to-o rewritings.

Theorem 15. The verification problem for sound s-to-o rewritings is Πp2 -complete.

Proof sketch. As for the upper bound, we show that checking PerfRefqO(⃗t),Σ ̸⊑ qS ∨PerfRefV⃗tO ,Σ can be done in Σp2 : we guess a CQ q1 over S whose size is at most σ(M) × σ(qO), we check in PTIME whether q1 is a disjunct of PerfRefqO,Σ, and then we use an NP oracle to check q1 ̸⊑ qS∨PerfRefV⃗tO ,Σ. As for the lower bound, the proof of Πp2 -hardness is by a LOGSPACE reduction from the ∀∃-CNF problem.

We point out that the result of Πp2 -hardness holds even when O is empty, M is both a GAV mapping and a LAV mapping, and qS, qO are boolean CQs.

We now tackle the computation problem. Our main result is that there are many cases where a UCQ-maximally sound s-to-o rewriting of a query is not guaranteed to exist. To illustrate the result, we introduce a specific setting for OBDA specifications, that we call restricted, obtained from the general one by: (i) limiting the ontology language to DL-LiteRDFS, (ii) limiting the mapping to pure GAV, and (iii) limiting qS to UCQJFEs. We now show that, surprisingly, as soon as we try to extend such setting, we lose the guarantee of the existence of s-to-o rewritings that are maximally sound in the class of UCQs.

Theorem 16. UCQ-maximally sound s-to-o rewritings of a query qS may not exist if we extend the restricted setting with each of the following features:

1. disjointness axioms in the ontology;
2. inclusion axioms with ∃R as right-hand side in the ontology;
3. LAV mapping assertions, even without joins involving existential variables in the right-hand side;
4. non-pure GAV mapping assertions;
5. qS in a fragment of CQs going beyond CQJFEs.

Proof sketch. We present the proof for case 5. Consider the OBDA specification Σ = 〈O, S, M〉, where O has no axiom, and M consists of the following pure GAV mappings:

and let qS be the query {() | s1(x, y) ∧ s1(y, z)}. Observe that q′O = {() | R(x, y) ∧ R(y, z)} is a complete S-to-O Σ-rewriting of qS, but is not sound, because the query q′S = {() | s1(x, y) ∧ s1(z, z) ∧ s3(y)} is a disjunct of PerfRefq′O ,Σ such that q′S ̸⊑ qS. Conversely, one can verify that each of the following queries is a sound S-to-O Σ-rewriting of qS:

• q0 = {() | R(x, y) ∧ R(y, y)},
• q1 = {() | R(x, y) ∧ R(y, z1) ∧ R(z1, y)},
• q2 = {() | R(x, y) ∧ R(y, z1) ∧ R(z1, z2) ∧ R(z2, y)},

More precisely, if we define qn to be {() | R(x, y)∧R(y, z1)∧ R(z1, z2) ∧ . . . ∧ R(zn-1, zn) ∧ R(zn, y)}, for n ≥ 2,, then it can be shown that every qn is a sound S-to-O Σrewriting of qS, and for no pair (i, j), with i ̸= j, i, j ≥ 0, certqi,Σ ⊑ certqj,Σ. It follows that the infinite union of q0, q1, and all qn's can be shown to be the maximally sound Sto-O Σ-rewriting of qS in the class of positive queries.

It remains to study sound s-to-o rewritings in the restricted setting. We do so in Section 7.

6 Perfect Source-to-Ontology Rewritings

Both the verification and the computation problem for perfect s-to-o rewritings can be addressed by combining the techniques illustrated in the previous sections. As for verification, we can check whether qO(⃗t) is a perfect S-to-O Σ-rewriting of qS(⃗t′ ) by checking both PerfRefqO,Σ ⊑ qS ∨ PerfRefV⃗tO ,Σ and qS ⊑ PerfRefqO,Σ ∨ PerfRefV ⃗ t′ O ,Σ. As for computation, we can first compute the query qO that is the UCQ-minimally complete S-to-O Σ-rewriting of qS, and then check whether qO is a sound S-to-O Σ-rewriting of qS. If the answer is positive, we return qO, otherwise we report that no perfect rewriting exists. From the above observation we derive the following: (i) all complexity results illustrated for the case of sound s-to-o rewritings hold for perfect rewritings as well, and (ii) if qS is a CQ, then either its perfect S-to-O Σ-rewriting does not exist, or it is a CQ as well.

Finally, we briefly discuss the case of perfect rewritings under the semantics used in [Lutz et al., 2018], that imposes the condition qD S = certDqO,Σ for all S-databases. From the results presented in the previous sections, it follows that qO(⃗t) is a perfect S-to-O Σ-rewriting of qS(⃗t′ ) under such semantics if and only if qS ≡ PerfRefqO,Σ ∨ PerfRefV⃗tO ,Σ. This allows us to easily derive algorithms and complexity bounds for both verification and computation in this case, too.

7 Restricted Setting

We now deal with the restricted setting mentioned at the end of Section 5. Before delving into the technical part, we observe that, despite its limitations, the expressive power of this setting is sufficient for several meaningful applications. Indeed, several popular ontologies are expressible in DL-LiteRDFS (e.g., Dublin Core [Weibel et al., 1998] and SKOS [Miles and Bechhofer, 2009]), and the form of pure GAV mapping is exactly the one originally defined in the literature of data integration. Moreover, UCQJFEs captures data services expressible in the famous USPJ (Union, Select, Project, Join) fragment of Relational Algebra [Codd, 1970], with the only limitation that joining variables cannot be projected out. Note that such fragment is the one needed for all tasks related to source profiling [Abedjan et al., 2017].

Definition 17. Let q1(⃗t) and q2(⃗t) be two CQs, and let F1 = S(t1,1, . . . , t1,n) and F2 = S(t2,1, . . . , t2,n) be two atoms of q1 and q2, respectively. We say that F1 instantiates F2, if for every i = 1, . . . , n, we have that if t2,i is a term of ⃗t or a constant, then t2,i = t1,i.

Clearly, given atoms F1 in q1 and F2 in q2, checking whether F1 instantiates F2 can be done in PTIME. Based on this observation, the following lemma shows that checking whether a UCQ is contained in a UCQJFE is tractable.

Lemma 18. Given a UCQ q1 and a UCQJFE q2 of the same arity, checking whether q1 ⊑ q2 can be done in PTIME.

We are now ready to characterize the complexity of the verification problem in the restricted setting.

Theorem 19. The verification problem for sound s-to-o rewritings in the restricted setting is coNP-complete; it is in PTIME if qS is a CQJFE.

Proof sketch. The coNP upper bound is obtained by noticing that we have to guess a disjunct q1 of PerfRefqO,Σ and then check whether q1 is not contained in qS , which, by virtue of Lemma 18, can be done in PTIME. The coNP lower bound is shown by a reduction from VALIDITY. To show that verification is in PTIME when qS is a CQJFE, we notice that, for the characteristics on the OBDA setting, for every q(⃗t) in qO, PerfRefq,Σ = ∧α∈q PerfRefqα,Σ, where qα is the query with body α and target list the tuple of variables that occur both in ⃗t and α. Hence, verification can be solved by checking, for every atom F in qS and every query q in qO, whether there is an atom G in q such that all disjuncts of PerfRefqG,Σ contain at least one atom that instantiates F . Clearly, this can be done in PTIME w.r.t. σ(qS), σ(M), and σ(qO).

We observe that the coNP upper bound holds even when O is expressed in the fragment of DL-LiteR that does not admit disjointness axioms, and M is GLAV, while the coNPhardness holds even when O is empty, M is a set of both pure GAV and LAV mappings, qO is a CQ, and both qS and qO have no existential variables.

We now address the computation problem by providing an algorithm to compute maximally sound s-to-o rewritings, thus proving that in the restricted setting, for each query qS, the UCQ-maximally sound s-to-o rewriting of qS always exists.

Let γ(M) be the number of mapping assertions inMand η(qS) the number of distinct atoms appearing in qS. Moreover, let bound(qS) = 1+γ(M)+γ(M)2 +. . .+γ(M)η(qS) if qS is a UCQJFE, and bound(qS) = η(qS) if qS is a CQJFE. The following lemma, showing that we can limit our attention to queries with at most bound(qS) atoms when we search for the maximally sound S-to-O Σ-rewriting of qS, allows us to immediately derive Algorithm 2.

Lemma 20. If a CQ qO(⃗t) is a sound S-to-O Σ-rewriting of qS, then there exists a CQ q′O (⃗t) which is a sound S-to-O Σ-rewriting of qS whose body is the conjunction of m atoms appearing in qO, where m ≤ bound(qS).

Note that the disjuncts of query qO computed by Algorithm 2 do not have necessarily the same target list.

Theorem 21. Algorithm 2 computes the UCQ-maximally sound S-to-O Σ-rewriting of qS .

Proof sketch. It is immediate to verify that the query returned by the algorithm is a sound S-to-O Σ-rewriting of qS .

Algorithm 2 Compute sound s-to-o rewritings

Input: Σ = 〈O, S,M〉, qS (U)CQJFE over S

Output: qO over O

• 1: qO := ⊥.
• 2: for each q over Owith at most bound(qS) atoms, involving only constants from qS andMdo
• 3: if q is a sound S-to-O Σ rewriting of qS then
• 4: qO := qO ∨ q.
• 5: end if
• 6: end for
• 7: return qO

To show that it is the maximally sound S-to-O Σ-rewriting of qS, we proceed by contradiction, i.e., by assuming that there exists a CQ q′ such that PerfRefq′ ,Σ ⊑ qS and PerfRefq′ ,Σ ̸⊑ PerfRefq′O ,Σ, for every disjunct q′O of qO, where qO is the query computed by Algorithm 2. Let q′′ be obtained by substituting in q′ each constant neither in qS nor in M (if any) with a new fresh existential variable. It can be shown that in the restricted case, q′′ would be such that PerfRefq′′ ,Σ ⊑ qS. Also, let m be the number of atoms of q′′ . If m > bound(qS), by Lemma 20, there exists a query ¯ q that is a sound S-to-O rewriting of qS whose body is the conjunction of ¯m atoms appearing in q′′ , where ¯m ≤ bound(qS). But then, since ¯ q possibly contains only constants in qS or M and since ¯m ≤ bound(qS), by construction, ¯ q would be a disjunct of qO and we get a contradiction. Finally, if m ≤ bound(qS), we obtain a contradiction, by a similar argument.

It can be shown that Algorithm 2 (i) computes the unique (up to equivalence w.r.t. Σ) maximally sound S-to-O Σrewriting of qS in the class of monotone queries, (ii) is PTIME in σ(O) and σ(M), and EXPTIME in η(qS). Finally, we can show that (i) assuming PTIME ̸= NP, the computation problem cannot be solved in PTIME, and (ii) there are cases where the number of atoms of the maximally sound Sto-O Σ-rewriting of qS is necessarily exponential w.r.t. η(qS).

8 Conclusion

We have presented a framework for semantically characterizing data services through ontologies, and carried out a comprehensive analysis for the most common OBDA setting, including a restricted setting, still useful in practice. We plan to continue this work along several directions. For example, in the unrestricted setting, we will study the problem of checking for the existence of a UCQ-maximally sound source-toontology rewriting of a query, and we aim at singling out the minimal class LO of queries that guarantees the existence of an LO-maximally sound source-to-ontology rewriting of a query qS . Also, we will extend our analysis to OBDA settings going beyond the one based on DL-LiteR, e.g., by considering DL-LiteA and the EL family as ontology languages.

Acknowlegments

Work supported by Sapienza under the project "PRE-O-PRE" and by MIUR, under the SIR project "MODEUS" - grant n. RBSI14TQHQ, and under the PRIN 2017 project "HOPE".