Preliminary results on Ontology-based Open Data Publishing Gianluca Cima Dipartimento di Ingegneria Informatica, Automatica e Gestionale Sapienza Università di Roma cima@diag.uniroma1.it Abstract. Despite the current interest in Open Data publishing, a formal and comprehensive methodology supporting an organization in deciding which data to publish and carrying out precise procedures for publishing high-quality data, is still missing. In this paper we argue that the Ontology-based Data Management paradigm can provide a formal basis for a principled approach to publish high- quality, semantically annotated Open Data. We describe two main approaches to using an ontology for this endeavor, and then we present some technical results on one of the approaches, called bottom-up, where the specification of the data to be published is given in terms of the sources, and specific techniques allow deriving suitable annotations for interpreting the published data under the light of the ontology. 1 Introduction In many aspects of our society there is growing awareness and consent on the need for data-driven approaches that are resilient, transparent and fully accountable. But to achieve a data-driven society, it is necessary that the data needed for public goods are readily available. Thus, it is no surprising that in recent years, both public and private organizations have been faced with the issue of publishing Open Data, in particular with the goal of providing data consumers with suitable information to capture the seman- tics of the data they publish. Significant efforts have been devoted to defining guide- lines concerning the management and publication of Open Data. Notably, the W3C1 has formed a working group, whose objective is the release of a first draft on Open Data Standards2 . The focus of the document are areas such as metadata, data formats, data licenses, data quality, etc., which are treated in very general terms, with no refer- ence to any specifical technical methodology. More generally, although there are several works on platforms and architectures for publishing Open Data, there is still no formal and comprehensive methodology supporting an organization in (i) deciding which data to publish, and (ii) carrying out precise procedures for publishing and documenting high-quality data. One of the reasons of this lack of formal methods is that the prob- lem of Open Data Publishing is strictly related to the problem of managing the data 1 World Wide Web Consortium: https://www.w3.org/ 2 Data on the Web Best Practice: https://www.w3.org/TR/dwbp/ within an organization. Indeed, a necessary prerequisite for an organization for pub- lishing relevant and meaningful data is to be able to manage, maintain and document its own information system. The recent paradigm of Ontology-based Data Management (OBDM) [16] (used and experimented in practice in the last years, see, e.g., [3]) is an attempt to provide the principles and the techniques for addressing this challenge. An OBDM system is constituted by an ontology, the data sources forming the information system, and the mapping between the ontology and the sources. The ontology is a for- mal representation of the domain underlying the information system, and the mapping is a precise specification of the relationship between the data at the sources and the concepts in the ontology. In this paper we argue that the OBDM paradigm can provide a formal basis for a principled approach to publish high-quality, semantically annotated Open Data. The most basic task in Open Data is the extraction of the correct content for the dataset(s) to be published, where by “content” we mean both the extensional information (i.e., facts about the domain of interest) conveyed by the dataset, and the intensional knowledge relevant to document such facts (e.g., concepts that intensionally describe facts), and “correct” means that the aspect of the domain captured by the dataset is coherent with a requirement formally expressed in the organization. Current practices for publishing Open Data focus essentially on providing exten- sional information (often in very simple forms, such as CSV files), and they carry out the task of documenting data mostly by using metadata expressed in natural languages, or in terms of record structures. As a consequence, the semantics of datasets is not formally expressed in a machine-readable form. Conversely, OBDM opens up the pos- sibility of a new way of publishing data, with the idea of annotating data items with the ontology elements that describe them in terms of the concepts in the domain of the orga- nization. When an OBDM is available in an organization, an obvious way to proceed to Open Data publication is as follows: (i) express the dataset to be published in terms of a SPARQL query over the ontology, (ii) compute the certain answers to the query, and (iii) publish the result of the certain answer computation, using the query expression and the ontology as a basis for annotating the dataset with suitable metadata expressing its semantics. We call such method top-down. Using this method, the ontology is the heart of the task: it is used for expressing the content of the dataset to be published (in terms of a query), and it is used, together with the query, for annotating the published data. Unfortunately, in many organizations (for example, in Public Administrations) it may be the case that people are not ready yet to manage their information systems through the OBDM paradigm. In these cases, the bottom-up approach could be more appropriate. For example, in the Italian Public Administration system, it is very unlikely that local administration people are able to express their queries over the ontology using SPARQL. Typically, the ontology and the mapping have been designed by third parties, with no or little involvement with IT people responsible of the local administration in- formation system. In other words, these people probably cannot follow the top-down approach, and they are more confident to express the specification of the dataset to be published directly in terms of the source structures (i.e., the relational tables in their databases), or, more generally, in terms of a view over the sources. But how can we au- tomatically publish both the content and the semantics of the dataset if its specification is given in terms of the data sources? We argue that we can achieve this goal by fol- lowing what we call the bottom-up approach: the organization expresses its publishing requirement as a query over the sources, and, by using the ontology and the mapping, a suitable algorithm computes the corresponding query over the ontology. With such query at hand, we have reduced the problem in such a way that the top-down approach can now be followed, and the required data can be published according to the method described above. So, at the heart of the bottom-up approach there is a conceptual issue to address: ”Given a query Q over the sources, which is the query over the ontology that characterizes Q at best (independently from the current source database)?” Note that the answer to this question is relevant also for other tasks related to the man- agement of the information system, e.g., the task of explaining the semantics of the various data sources within the organization. The question implicitly refers to a sort of reverse engineering problem, which is a novel aspect in the investigation of both OBDM and data integration. Indeed, most of (if not all) the literature about manag- ing data sources through an ontology (see, e.g., [5, 18]), or more generally, about data integration [15] assume that the user query is expressed over the global schema, and the goal is to find a rewriting (i.e., a query over the source schema) that captures the original query in the best way, independently from the current source database. 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-to-target rewriting. In this paper we study the above described bottom-up approach, and provide the following contributions. – We introduce the concept of source-to-target rewriting (see Section 3), the main technical notion underlying the bottom-up approach, and we describe two com- putation problems related to it, namely the recognition problem, and the finding problem. The former aims at checking whether a query over the ontology is a source-to-target rewriting of a given query over the sources, taking into account the mapping between the sources and the ontology. The latter aims at computing a suitable source-to-target rewriting of a given source query, with respect to the mapping. – We discuss two different semantics for source-to-target rewritings, one based on the logical models of the OBDM specification, and one based on certain answers. The former is somehow the natural choice, given the first-order semantics behind OBDM. The latter is a significant alternative, that may better capture the intuition of a user who is accustomed to think of query semantics in terms of certain answers. – We show that, although the ideal notion is the one of “exact” source-to-target rewrit- ing, it is important to resort to approximations to exact rewriting when exactness cannot be achieved. For this reason, we introduce the notion of sound and complete source-to-target rewritings. – For the case of complete source-to-target rewritings, we present algorithms both for the recognition (Section 4), and for the finding (Section 5) problem, in particular for the setting where the ontology is expressed in DL-LiteA,id , and the queries involved in the specification are conjunctive queries. 2 Preliminaries We assume familiarity with classical databases [1], Description Logics [4], and the OBDM paradigm. In this section, we (i) review the most basic notions of non-ground instances, and their correlation with conjunctive queries; (ii) briefly discuss the chase of a possible non-ground instance; (iii) discuss the relevant aspects of notation we use in the following regarding the OBDM paradigm. For a possible non-ground instance D, we assume that each value in dom(D), i.e., the set of values occurring in D, comes from the union of two fixed disjoint infinite sets: the set Const of all constants, and the set NullD of all labeled nulls. We also let null (D) := dom(D) ∩ NullD . In particular, each labeled null in a non-ground instance is treated as an unknown value (and hence, an incomplete information), rather than to a non-existent value [20]. Thus, a non-ground instance represents a number of ground instances obtained by assigning constants to each labeled null. More precisely, let D be a non-ground instance, and v be a mapping v : null(D) → Const. Then, v is called a valuation of D, and we indicate, with v(D), the ground instance obtained from D by replacing elsewhere each labeled null x ∈ D with v(x). We also extend this to tuples, that is, given a tuple u = (u1 , ..., un ) of both constants and labeled nulls, with v(u) we indicate the tuple (v 0 (u1 ), ..., v 0 (un )), where v 0 (ui ) = ui if ui is a constant; otherwise (ui is a labeled null), v 0 (ui ) = v(ui ). Given an instance D it is possible to construct in linear time a boolean CQ qD that fully captures it, and vice versa. We also let qD (x) denoting the transformation of qD by removing the existential quantification of the variables x in qD . Moreover, given a non-boolean CQ q (with x as distinguished variables), we associate to it the instance Dq by considering the variables in x as if they were existentially quantified. For ease of presentation, we extend CQs to allow also queries of the form {x | ⊥(x)} and {x | >(x)}, with their usual meaning. We also denote with tup(q) the tuple composed by the terms in head of q. Given a source schema S; a target schema T ; a set M of st-tgds (i.e., assertions of the form ∀x, y(φ(x, y) → ∃zϕ(x, z)), where φ is a CQ over S, and ϕ is a CQ over T); and a set Σt of egds (i.e., assertions of the form ∀x(φT (x) → (x1 = x2 )), where φT is a CQ over T, and x1 , x2 are among the variables in x), the chase procedure of a possibly non-ground source instance D consists in: (i) the chase of D w.r.t. M, where, for every st-tgd φ(x, y) → ∃zϕ(x, z) in M and for every pair of tuples (a, b) such that D |= φ(a, b), there is the introduction of new facts in the instance J of the target schema T so that ϕ(a, u) holds, where u consists in a fresh tuple of distinct labeled nulls coming from an infinite set NullΣ disjoint from NullD ; (ii) the chase of J w.r.t. Σt , where, for every egd ∀x(φT (x) → (x1 = x2 )) and for every tuple a such that J |= φT (a) and a1 6= a2 , we equate the two terms. Equating a1 with a2 means choosing one of the two so that the other is replaced elsewhere in J by the one chosen. In particular, if one is a labeled null and the other is a constant, then the chase choose the constant; if both are labeled nulls, one coming from NullD and the other from NullΣ , it always choose the one coming from NullD ; if both are constants, then the chase fail. Moreover, with ψ we denote the set of equalities applied by the chase of J w.r.t. a set of egds on variables coming from NullD . This can be done by keeping track of the substitution applied by the chase. For example, if the chase equates the variable y ∈ NullD with the variable x ∈ NullD , and then equates the variable z ∈ NullD with the variable w ∈ NullD , and then w with the constant a, given the tuple (x, y, z, w), ψ(x, y, z, w) indicates the tuple (x, x, a, a). Note that, we can compute the certain answers of a boolean union of CQs (UCQ) q with at most one inequality per disjunct by splitting q as a boolean UCQ q 16= with exactly one inequality per disjunct, and a boolean UCQ q 06= with no inequality per disjunct. The key idea is that the negation of q 16= consists in a set of egds, hence, the certain answers of q can be computed by applying the chase procedure over the instance J (i.e., the instance produced by the chase of C w.r.t. M and Σt ) w.r.t. ¬q 16= , where, if the chase fail then the answer is true; otherwise, if the instance J 0 produced satisfy one of the conjunctive query in q 06= , then the answer is true, else the answer is false. We refer to [10] for more details. Given an OBDM specification I = hO, M, Si, where O is a TBox, and M is a set of st-tgds, and given a non-ground source instance D for S, and a set of egds Σt , we denote with AD,Σ , where Σ = M ∪ Σt , the ABox computed as follows: (i) chase the non-ground source instance D w.r.t. Σ; (ii) freeze the instance (or equivalently, the ABox with variables) obtained, i.e., variables in this instance are now considered as constant. Note that, such ABox AD,Σ may also not exists due to the failing of the chase, in this case, we denote AD,Σ with the symbol ⊥. For an OBDM specification I = hO, M, Si, and for a source database C for I (i.e., a ground instance over the schema S), we denote by sem C (I) the set of mod- els B for I relative to C such that: (i) B |= O; (ii) (B, C) |= M. Given a query q over O, we denote by cert(q, I, C) T the set of certain answers to q in I relative to C. It is defined as: cert(q, I, C) = {q B | B ∈ sem C (I)} if sem C (I) 6= ∅; oth- erwise, cert(q, I, C) = AllTup(q, C), where AllTup(q, C) is the set of all possible tuples of constants in C whose arity is the one of the query q. Furthermore, given a DL-LiteA,id [5] TBox O and a DL-LiteA,id ABox A we are able to: (i) check whether hO, Ai is satisfiable by computing the answers of a suitable boolean query Qsat (a UCQ with at most one inequality per disjunct) over the ABox A considered as a relational database. We see Qsat as the union of Q06sat = (the UCQ containing every disjunct not comprising inequalities in Qsat ) and Q16sat= (the UCQ containing every disjunct com- prising inequalities in Qsat ); (ii) compute the certain answers to a UCQ Qg over a satisfiable hO, Ai, denoted with cert(Qg , hO, Ai), by producing a perfect reformula- tion (denoted as a function pr (·)) of such query, and then computing the answers of pr (Qg ) over the ABox A considered as a relational database. See [6] for more details. 3 The notion of source-to-target rewriting In what follows, we implicitly refer to (i) an OBDM specification I = hO, M, Si; (ii) a query Qs over the source schema S; (iii) a query Qg over the ontology O. As we said in the introduction, there are at least two different ways to formally define a source-to-target rewriting (s-to-t rewriting in the following) for each of the three variants, namely “exact”, “complete”, and “sound”. The first one is captured by the following definition. Definition 1. Qg is a complete (resp., sound, exact) s-to-t rewriting of Qs with respect to I under the model-based semantics, if for each source database C and for each model B ∈ sem C (I), we have that QCs ⊆ QB B C B g (resp., Qg ⊆ Qs , Qg = Qs ). C Intuitively, a complete s-to-t rewriting of Qs w.r.t. I under the model-based se- mantics is a query over O that, when evaluated over a model B ∈ sem C (I) for a source database C, returns all the answers of the evaluation of Qs over C. In other words, for ev- ery source database C, the query Qg over O captures all the semantics that Qs expresses over C. Similar arguments hold for the notions of sound and exact s-to-t rewriting un- der this semantics. Moreover, from the formal definition of source-to-target rewriting and the usual definition of target-to-source rewriting (simply called rewriting) used in data integration, it is easy to see that Qg is a complete (resp., sound) source-to-target rewriting of Qs w.r.t. I under the model-based semantics, if and only if Qs is a sound (resp., complete) rewriting of Qs w.r.t. I, implying that, Qg is an exact source-to-target rewriting of Qs w.r.t. I under the model-based semantics, if and only if Qs is an exact rewriting of Qg w.r.t. I. The second possible way to formally define a source-to-target rewriting is as fol- lows. Definition 2. Qg is a complete (resp., sound, exact) s-to-t rewriting of Qs with respect to I under the certain answers-based semantics, if for each source database C such that sem C (I) 6= ∅, we have that QCs ⊆ cert(Qg , I, C) (resp., cert(Qg , I, C) ⊆ QCs , QCs = cert(Qg , I, C)). In this new semantics, in order to capture a query Qs over S, we resort to the notion of certain answers. Indeed, a complete s-to-t rewriting of Qs w.r.t. I under the certain answers-based semantics is a query over O such that, when we compute its certain answers for a source database C, we get all the answers of the evaluation of Qs over C. As before, similar arguments hold for the notions of sound and exact s-to-t rewrit- ing under this semantics. Note also the strong correspondence between the exact s-to-t rewriting under the certain answers-based semantics and the notion of perfect rewriting. We remind that a perfect rewriting of Qg w.r.t. I is a query Qs over S that computes cert(Qg , I, C) for every source database C such that sem C (I) 6= ∅ [8]. Indeed, we have that Qg is an exact s-to-t rewriting of Qs w.r.t. I under the certain answers-based semantics if and only if Qs is a perfect rewriting of Qg w.r.t. I. Note that the above observations imply that the two semantics are indeed different, since it is well-known that the two notions of exact rewriting and perfect rewriting of Qg w.r.t. I are different. The difference between the two semantics is confirmed by the following example. Example 1. O := ∅ (i.e., no TBox assertions in O); S contains a binary relation r1 and a unary relation r2 ; M := {∀x∀y(r1 (x, y) → G(x, y)), ∀x(r2 (x) → ∃Y.G(x, Y ))}; Qs := {(w) | ∃Z.r1 (Z, w)}; Qg := {(w) | ∃Z.G(Z, w)}. It is easy to see that Qg is a sound s-to-t rewriting of Qs w.r.t. I under the certain answers-based semantics (more precisely, it is an exact s-to-t rewriting of Qs w.r.t. I under such semantics), while it is not sound under the model-based semantics. In fact, for the source database C with r1C = {(a, b)} and r2C = {(c)}, and for the model B with GB = {(a, b), (c, d)}, we have B ∈ sem C (I), and QB C g 6⊆ Qs . t u Intuitively, for the sound case, the model-based semantics is too strong, in the sense that under such semantics, a model B may contain not only facts depending on how data in the source C are linked to O through M, but additionally arbitrary facts, with the only constraint of satisfying O. One might think that, in order to address this issue, it is sufficient to resort to a sort of minimizations of the models of O. Actually, the above example shows that, even if we restrict the set of models to the set of minimal models (i.e., models B such that (i) B ∈ sem C (I) and (ii) there is no model B 0 ∈ sem C (I) such that B 0 ⊂ B), and adopt a semantics like the model-based one but restricted to the set of minimal models, Qg is still not a sound s-to-t rewriting (this can be seen considering that the target database B defined earlier is a minimal model). Observe that the above considerations show the difference in the two semantics by referring to sound and exact s-to-t rewritings. It is interesting to ask whether the dif- ference shows up when restricting our attention to complete rewritings. The following proposition deals with this question. Proposition 1. Qg is a complete s-to-t rewriting of Qs with respect to I under the model-based semantics if and only if it is so under the certain answers-based semantics. Proof (Sketch). One direction is trivial. Indeed, when Qg is a complete s-to-t rewriting of Qs with respect to I under the model-based semantics, by definition of certain answers, for each source database C such that sem C (I) 6= ∅ we have that QCs ⊆ cert(Qg , I, C). For the other direction, suppose that Qg is not a complete s-to-t rewriting of Qs w.r.t. I under the model-based semantics. It follows that, there exists a source database C and a model B ∈ sem C (I) such that QCs 6⊆ QB C g , implying that, Qs 6⊆ cert(Qg , I, C), which, in turn, implies that Qg is not a complete s-to-t rewriting of Qs w.r.t. I under the certain answers-based semantics. t u Obviously, the query over the ontology which captures at best a given query q over the source schema is the exact s-to-t rewriting of q. However, the following example shows that even for very simple OBDM specifications, an exact s-to-t rewriting of even trivial queries, may not exist. Example 2. O := ∅ (i.e., no TBox assertions in O); S contains two unary relations man and woman; M := {∀x(man(x) → Person(x)), ∀x(woman(x) → Person(x))}; Qs := {(x) | woman(x)}. It is possible to show that the only sound s-to-t rewriting of Qs w.r.t. I under both semantics is the query Qg := {(x) | ⊥(x)}, which is obviously not a complete s-to-t rewriting of Qs w.r.t. I neither under the model-based semantics, nor under the certain answers-based semantics. On the other hand, the most immediate and intuitive complete s-to-t rewriting of Qs w.r.t. I is the query Q0g := {(x) | Person(x)}. Furthermore, as we will see in Section 5, this query is an “optimal” complete s-to-t rewriting of Qs w.r.t. I, where the term optimal will be precisely defined. t u As we said in the introduction, in the rest of this paper we focus on complete s-to-t- rewritings. In particular, we will address both the recognition problem (see Section 4), and the finding problem (see Section 5) in a specific setting, characterized as follows: – The ontology O in an OBDM specification I = hO, M, Si is expressed as a TBox in DL-LiteA,id . – The mapping M in I is a set of GLAV mapping assertions (or, st-tgds), where each assertion expresses a correspondence between a conjunctive query over the source schema and a conjunctive query over the ontology. – In the recognition problem, both the query over the source schema and the query over the ontology are conjunctive queries. Similarly, in the finding problem, the query over the source schema is a conjunctive query. 4 The recognition problem for complete s-to-t rewritings We implicitly refer to the setting described at the end of the previous section. The recog- nition problem associated to the complete s-to-t rewriting is the following decision prob- lem: Given an OBDM specification I = hO, M, Si, a query Qs over the source schema S, and a query Qg over the ontology O, check whether Qg is a complete s-to-t rewriting of Qs with respect to I. The next lemma is the starting point of our solution. Lemma 1. Qg is not a complete s-to-t rewriting of Qs with respect to I = hO, M, Si if and only if there is a valuation v of DQs and a model B ∈ sem v(DQs ) (I) such that v(tup(Qs )) 6∈ QB g. Proof. ”⇐=” Suppose that there exists a valuation v of DQs and a model B ∈ sem v(DQs ) (I) v(DQs ) such that v(tup(Qs )) 6∈ QB g . Obviously, v(tup(Qs )) ∈ Qs . It follows that, there exist a source database v(DQs ), a model B ∈ sem v(DQs ) (I), and a tuple v(tup(Qs )) v(DQs ) such that v(tup(Qs )) 6∈ QB g and v(tup(Qs )) ∈ Qs . ”=⇒” Suppose that Qg is not a complete s-to-t rewriting of Qs w.r.t. I, i.e., there is a source database C, a model B ∈ sem C (I), and a tuple t such that t ∈ QCs and t 6∈ QB C g . The fact that t ∈ Qs implies the existence of a homomorphism v : DQs → C such that v(tup(Qs )) = t. Note also, that since C is a ground instance, v is a valuation of DQs such that v(DQs ) ⊆ C. Obviously, B ∈ sem v(DQs ) (I), this can be seen by considering that (i) B |= O is true from the supposition that B ∈ sem C (I); and (ii) (B, v(DQs )) |= M is true by considering that, (B, C) |= M (which holds from the supposition that B ∈ sem C (I)), v(DQs ) ⊆ C, and the queries in M are monotone queries. It follows that, there is a valuation v of DQs and a model B ∈ sem v(DQs ) (I) such that v(tup(Qs )) 6∈ QB g. t u Relying on the above lemma, we are now ready to present the algorithm CheckCom- plete for the recognition problem. Algorithm 1: CheckComplete(I, Qs , Qg ) Input: OBDM specification I = hO, S, Mi, query Qs over S, query Qg over O. Output: true or false. 1: Compute DQs from Qs (i.e., the instance, possibly with incomplete information, associated to the query Qs ), and denote it with D. 16= 2: Compute AD,Σ , where Σ = M ∪ ¬Qsat , and let ψ be the set of equality applied to the variables in D by the chase. 3: If AD,Σ = ⊥, then return true. 06= 4: If the evaluation of Qsat over AD,Σ considered as a relational database is {()} (i.e., AD,Σ |= Q06sat = ), then return true. 5: If ψ(tup(Qs )) ∈ cert(Qg , hO, AD,Σ i) then return true, else return false. The next theorem establishes the correctness of the above algorithm. Theorem 1. CheckComplete(I, Qs , Qg ) terminates, and returns true if and only if Qg is a complete s-to-t rewriting of Qs w.r.t. I. Proof (Sketch). Termination of the algorithm easily follows by the termination of the chase procedure, and by the obvious termination of computing the certain answers of a CQ over hO, AD,Σ i. For the ”=⇒” direction, suppose that the algorithm returns false, i.e., AD,Σ 6|= Q06sat= , and ψ(tup(Qs )) 6∈ cert(Qg , hO, AD,Σ i). Now, if we extend ψ(D) by considering the freezing of this instance (i.e., variables are now considered as constants), it is easy to see that we obtain a valuation v of D such that (v(D), AD,Σ ) |= M, and such that sem v(D) (I) 6= ∅. Moreover, the fact that ψ(tup(Qs )) 6∈ cert(Qg , hO, AD,Σ i), implies, by the property of certain answers, that there is at least one model B |= hO, AD,Σ i, and hence B ∈ sem v(D) (I) (because (v(D), AD,Σ ) |= M) such that v(tup(Qs )) 6∈ QB g . It follows, from Lemma 1, that Qg is not a complete s-to-t rewriting of Qs w.r.t. I. For the ”⇐=” direction, in the cases that AD,Σ = ⊥ or AD,Σ |= Q06sat = , it is easy to see that for every valuation v of D, either the chase of v(D) will fail, or every ABox A such that (v(D), A) |= M and A |= ¬Q16sat = will be such that A |= Q06sat = , implying that, for every valuation v of D, sem v(D) = ∅. It follows, from Lemma 1, that in this case Qg is a complete s-to-t rewriting of Qs w.r.t. I. While, in the cases that ψ(tup(Qs )) ∈ cert(Qg , hO, AD,Σ i), it is easy to see that, for every valuation v of D either sem v(D) = ∅, or if we compute Av(D),Σ , we have that v(tup(Qs )) ∈ cert(Qg , hO, Av(D),Σ i). More generally, every A obtained by chasing v(D) w.r.t. M and ¬Q16sat = , and then choosing arbitrary constants for the possible remaining variables, is such that v(tup(Qs )) ∈ cert(Qg , hO, Ai). Hence, for every model B such that B |= hO, Ai, we have that v(tup(Qs )) ∈ QB g . Also, we observe that the set of models sem v(D) coincides with the set of all models B such that B |= hO, Ai for all the possible ABox A obtained using the above procedure. It follows that, for every possible valua- tion v of D and for every possible B ∈ sem v(D) (I), we have that v(tup(Qs )) ∈ QB g, implying, from Lemma 1, that also in this case Qg is a complete s-to-t rewriting of Qs w.r.t. I. t u As for complexity issues of the algorithm, we observe: (i) it runs in PT IME in the size of Qs . Indeed, computing D (the instance associated to the query Qs ) can be done in linear time, and chasing an instance in the presence of a weakly acyclic set of tgds (as in our case) is PT IME in the size of D (M and Σ are considered fixed); (ii) it runs in PT IME in the size of O. Indeed, Qsat and the evaluation of the certain answers of Qg can be both computed in PT IME in the size of O; (iii) it runs in E XP T IME in the size of M. This can be seen from the obvious E XP T IME process of transferring data from D to AD,Σ ; (iv) the problem is NP-complete in the size of Qg because computing the certain answers of a UCQ query is NP-complete in the size of the query (query complexity). 5 Finding optimal complete s-to-t rewritings In this section we study the problem of finding optimal complete s-to-t rewritings. The first question to ask is which rewriting we chose in the case where several complete rewritings exist. The obvious choice is to define the notion of “optimal” complete s-to-t rewriting: one such rewriting r is optimal if there is no complete s-to-t rewriting that is contained in r. In order to formalize this notion, we introduce the following definitions (where MOD(O) denotes the set of models of O). Definition 3. Qg is contained in Q0g with respect to O, denoted Qg ⊆O Q0g , if for B every model B ∈ MOD(O) we have that Qg B ⊆ Q0g . Qg is proper contained in Qg with respect to O, denoted Qg ⊂O Qg , if Qg ⊆O Q0g and for at least one model 0 0 B B ∈ MOD(O) we have that Qg B ⊂ Q0g . Definition 4. Qg is an optimal complete s-to-t rewriting of Qs with respect to I, if Qg is a complete s-to-t rewriting of Qs with respect to I, and there exists no query Q0g such that Q0g is a complete s-to-t rewriting of Qs with respect to I and Q0g ⊂O Qg . We are ready to present an algorithm for computing an optimal complete s-to-t rewriting of a query over the source schema. For the termination and the complexity of this algo- Algorithm 2: FindOptimalComplete(I, Qs ) Input: OBDM specification I = hO, S, Mi, CQ Qs over S. Output: query Qg over O. 1: Compute DQs from Qs (i.e., the instance, possibly with incomplete information, associated to the query Qs ), and denote it with D. 2: Chase D w.r.t. M to produce an instance J 0 . 3: Chase J 0 w.r.t. ¬Q16sat = ; if the chase fails, then stop and return the query {tup(Qs ) | ⊥(tup(Qs ))}; otherwise, let J be the instance produced, and let ψ be the set of equality applied to the variables in D by the chase. 4: Evaluate Q06sat = over J; if the answer is {()} (i.e., J |= Q06sat= ), then stop and return the query {tup(Qs ) | ⊥(tup(Qs ))}. 5: If J = ∅ (i.e., no atoms in the instance J), then stop and return the query {tup(Qs ) | >(tup(Qs ))}; otherwise, let QJ be the boolean conjunctive query associated to the instance J. 6: Let w be the tuple composed by all terms in ψ(tup(Qs )) not appearing in J. If such tuple is not empty, then return {ψ(tup(Qs )) | QJ (ψ(tup(Qs )) ∧ >(w)}; otherwise, return {ψ(tup(Qs )) | QJ (ψ(tup(Qs )))}. rithm hold the same considerations done for the termination and the complexity of the CheckComplete algorithm. In particular, FindOptimalComplete(I,Qs ) terminates, and it runs in (i) PT IME in the size of Qs ; (ii) PT IME in the size of O; (iii) E XP T IME in the size of M. Whereas, the correctness is established by the next theorem. Theorem 2. FindOptimalComplete(I, Qs ) returns an optimal complete s-to-t rewrit- ing of Qs w.r.t. I. Proof (Sketch). When the algorithm returns the query {tup(Qs ) | ⊥(tup(Qs ))}, it is easy to see that, regardless of which is the query Qg , if we run the algorithm Check- Complete(I,Qs ,Qg ) it returns true (also in this case, either the chase will fail, or the ABox AD,Σ produced will satisfy Q06sat = ), and hence, by Theorem 1, Qg is a complete s-to-t rewriting of Qs w.r.t. I. It follows that, also {tup(Qs ) | ⊥(tup(Qs ))} is a com- plete s-to-t rewriting, and, by definition of such query, it is an optimal complete s-to-t rewriting of Qs w.r.t. I. When the algorithm returns the query Qg = {ψ(tup(Qs )) | QJ (ψ(tup(Qs )) ∧ >(w)} (or {tup(Qs ) | >(tup(Qs ))}, in the case J = ∅), if we run the algorithm CheckComplete(I,Qs ,Qg ), it computes the ABox AD,Σ , where tup(Qs ) ∈ cert(Qg , hO, AD,Σ i) holds because Qg corresponds exactly to AD,Σ (before to be freezed) extended with >(w) for all terms w in ψ(tup(Qs )) not appearing in AD,Σ . It follows that, also in this case, CheckComplete(I,Qs ,Qg ) returns true, implying, from Theorem 1, that Qg is a complete s-to-t rewriting of Qs w.r.t. I. We now prove that the query Qg = {ψ(tup(Qs )) | QJ (ψ(tup(Qs )) ∧ >(w)} (or {tup(Qs ) | >(tup(Qs ))}, in the case J = ∅) is also an optimal complete s-to-t rewriting of Qs w.r.t. I. In particular, suppose that there exist a query Q0g such that Q0g ⊂O Qg , i.e., Q0g ⊆O Qg , and there is a model B ∈ sem C (I) and a tuple t such that t ∈ QB g and 0B B t 6∈ Qg . The fact that t ∈ Qg implies the existence of a valuation v to all the variables in Qg that makes Qg true in B. Note that, we can extend the valuation v by assigning a new fresh constant to every variable appearing in D and not appearing in Qg . The v(D) valuation v obtained is now a valuation for D, and obviously t ∈ Qs . Moreover, if we apply the same valuation v to the instance J, it is easy to see that we obtain a ground instance J 0 such that (v(D), J 0 ) |= M (we recall that Qg is the CQ associated to the instance J). Obviously, J 0 ⊆ B, and hence, (v(D), B) |= M holds because queries in the mapping M are monotone queries. Moreover, we also have that B ∈ sem v(D) (I) (the fact that B |= O holds from the initial supposition). Hence, for the source database v(D) B v(D) there is a model B ∈ sem v(D) (I) and a tuple t such that t ∈ Qs and t 6∈ Q0g , implying that, Q0g is not a complete s-to-t rewriting of Qs w.r.t. I. t u It is easy to prove that the query returned by the algorithm is not only an optimal com- plete s-to-t rewriting of Qs w.r.t. I, but it is also the unique (up to equivalence) optimal complete s-to-t rewriting of Qs w.r.t. I. Furthermore, the above result implies that an optimal complete s-to-t rewriting of Qs w.r.t. I can always be expressed as a CQ. 6 Conclusion We have introduced the notion of Ontology-based Open Data Publishing, whose idea is to use an OBDM specification as a basis for carrying out the task of publishing high- quality open data. In this paper, we have focused on the bottom-up approach to ontology-based open data publishing, we have introduced the notion of source-to-target rewriting, and we have developed algorithms for two problems related to complete source-to-target rewrit- ings, namely the recognition and the finding problem. We plan to continue our work on several directions. In particular, we plan to investigate the notion of sound rewriting un- der different semantics. Also, we want to study the top-down approach, especially with the goal of devising techniques for deriving which intensional knowledge to associate to datasets in order to document their content in a suitable way. References 1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. 1995. 2. F. N. Afrati and P. G. Kolaitis. Answering aggregate queries in data exchange. pages 129– 138, 2008. 3. N. Antonioli, F. Castanò, S. Coletta, S. Grossi, D. Lembo, M. Lenzerini, A. Poggi, E. Virardi, and P. Castracane. Ontology-based data management for the italian public debt. pages 372– 385, 2014. 4. F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications. 2003. 5. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, M. Rodrı́guez-Muro, and R. Rosati. Ontologies and databases: The DL-Lite approach. volume 5689, pages 255–356. 2009. 6. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. 39(3):385–429, 2007. 7. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Path-based identifi- cation constraints in description logics. pages 231–241, 2008. 8. D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. View-based query processing: On the relationship between rewriting, answering and losslessness. volume 3363, pages 321– 336, 2005. 9. A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. pages 77–90, 1977. 10. R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. pages 207–224, 2003. 11. R. Fagin, P. G. Kolaitis, and L. Popa. Data exchange: Getting to the core. ACM Trans. Database Syst., 30(1):174–210, mar 2005. 12. A. Hernich. Answering non-monotonic queries in relational data exchange. pages 143–154, 2010. 13. A. Hernich, L. Libkin, and N. Schweikardt. Closed world data exchange. ACM Trans. Database Syst., 36(2):14:1–14:40, 2011. 14. T. Imielinski and W. Lipski, Jr. Incomplete information in relational databases. J. ACM, 31(4):761–791, 1984. 15. M. Lenzerini. Data integration: A theoretical perspective. pages 233–246, 2002. 16. M. Lenzerini. Ontology-based data management. pages 5–6, 2011. 17. L. Libkin and C. Sirangelo. Data exchange and schema mappings in open and closed worlds. pages 139–148, 2008. 18. A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati. Linking data to ontologies. X:133–173, 2008. 19. M. Y. Vardi. The complexity of relational query languages. pages 137–146, 1982. 20. C. Zaniolo. Database relations with null values. In Proc. of PODS, pages 27–33, 1982.