Maxime Buron
email: maxime.buron@inria.fr

Franc ¸ois Goasdou

Ioana Manolescu
email: ioana.manolescu@inria.fr

Marie-Laure Mugnier
email: marie-laure.mugnier@lirmm.fr

Rewriting-Based Query Answering for Semantic Data Integration Systems

We consider the integration of heterogeneous data under a global RDF graph data model, based on the knowledge expressed in an ontology describing the concepts relevant for an application, and a set of entailment rules which characterize the logical relationships between these concepts. We consider both standard RDF Schema rules and user-specified ones.

We propose a data integration architecture to compute certain query answers in this setting. Existing approaches to query answering in the presence of knowledge (expressed here in the ontology and the entailment rules) involve either the materialization of inferences in the data or the reformulation of the query. Both approaches have well-known drawbacks. We introduce a new approach to query answering, based on a reduction to view-based query answering. This approach avoids both materialization in the data and query reformulation. We define restrictions of our general architecture under which our method is correct, and formally prove its correctness.

INTRODUCTION

The development of data management systems has quickly lead to the need to integrate several databases under a single schema, or unified view. Such an integrated architecture simplifies application development and isolates it from possible changes in the underlying databases and data management systems. Two classical architectures have been used for data integration: (i) data warehousing [START_REF] Jarke | Fundamentals of data warehouses[END_REF] relies on ingesting all data sources in a single system; (ii) instead, mediation [START_REF] Wiederhold | Mediators in the architecture of future information systems[END_REF] leaves the data sources unchanged, and builds the integrated view of the data as a (virtual) layer above them.

An important question from which the design of a data integration system starts concerns the data models (i) of the underlying data sources, and (ii) of the integrated view of the data. Given the historical pre-eminence of relational data management systems, the early data integration systems as well as many follow-up works considered relational sources and a relational integrated schema. Quite early on, though, other data models have started being used to integrate heterogeneous data sources, e.g., object-oriented [START_REF] Garcia-Molina | The TSIMMIS approach to mediation: Data models and languages[END_REF], Datalog-oriented [START_REF] Genesereth | Infomaster: An information integration system[END_REF], description logic-oriented [START_REF] Abdallah | DL-LITER in the light of propositional logic for decentralized data management[END_REF], and Datalog and description logic-oriented [START_REF] Levy | Data model and query evaluation in global information systems[END_REF][START_REF] Goasdoué | The use of CARIN language and algorithms for information integration: The PICSEL system[END_REF][START_REF] Goasdoué | Answering queries using views: A KRDB perspective for the semantic web[END_REF] data models.

Two important trends influence the design of data integration architectures today.

1. First, RDF, the W3C's standard graph model for representing heterogeneous data, has gained wide acceptance for modeling data from a variety of domains, from life sciences to social networks, bibliography data, cultural resources etc.

2. Second, it has been noted that application semantics, usually expressed as an ontology, can be fruitfully used at the top (integrated) level, allowing users and applications to express their query and processing needs in the terms they are familiar with.

Part of this second trend, the term "Ontology-Based Data Access" (OBDA, in short) has been coined [START_REF] Poggi | Linking data to ontologies[END_REF][START_REF] Lenzerini | Ontology-based data management[END_REF] to designate data integration architectures where data is modeled using a set of unary predicates (or classes) and/or binary predicates (or properties), and described by known relationships between these predicates, e.g., any Student is a Person, and anyone having got a Grade in a Class is a Student). In OBDA settings, data is typically assumed stored in a relational database management system (RDBMS); mappings are then used to specify which parts of the stored data populate the ontology concepts and relations. OBDA has attracted significant attention in the research community, e.g., [START_REF] Giese | Optique: Zooming in on big data[END_REF][START_REF] Lembo | Mapping analysis in ontology-based data access: Algorithms and complexity[END_REF][START_REF] Lanti | Cost-driven ontology-based data access[END_REF], and has been applied in several large reallife data integration settings, e.g. [START_REF] Kharlamov | Ontology based data access in Statoil[END_REF][START_REF] Hovland | Ontology-based data access to Slegge[END_REF].

The above examples illustrate the fact that an important part of domain knowledge can be encapsulated by entailment (or inference) rules, of the general form ∀x(ϕ(x) → ψ(x)), where x designates the free variables of the ϕ and ψ formulae, which may also use other existentially quantified variables. For instance, the sample rules above can be written as:

(1) ∀x(S(x) → P (x)) (2) ∀x(∃y∃z(GS(y, x) ∧ GC(y, z) ∧ C(z)) → S(x))

where the unary predicates S, P and C state that the respective variables are of Student, Person, respectively Course type, while the binary predicate GS associates grades (first attribute) to students (second attribute), while GC associates grades to courses. Some inference rules, such as [START_REF]1.1 Concepts and Abstract Syntax[END_REF] above, can be expressed between a a fixed number of concepts using a standardized vocabulary; for instance, the 1 RDF Schema ontology standard provides a keyword for relating exactly two classes S, P by stating that the first is a subclass of the second. Other rules, such as (2) above, can take a more general form; they allow the human expert greater flexibility in describing the semantics of an application domain.

In this work, we consider the integration of heterogeneous data of any data models, under a global RDF graph data model; further, applications are offered the possibility to query the data with the help of (i) an ontology describing its semantics and (ii) entailment rules (both of standard form as per the RDF standard, and user-specified within a dialect that we describe). Figure 1 gives a broad view of this (focus on the yellow-background boxes at the top and the bottom now; the other components will be explained in due time). From a set of local databases D1, . . . , Dn, some data E of which begin accessible via mapppings M through an ontology O, associated with entailment rules R, our goal is to compute the certain answers of the query q, on the data integration system thus composed.

Our contributions are as follows. [START_REF]1.1 Concepts and Abstract Syntax[END_REF] We propose the first data integration architecture for computing certain query answers in this setting. It goes beyond comparable ones from the literature, focused either on relational data, or on a single non-relational one, e.g., JSON, by its support of data sources of heterogeneous data models, and (especially) by the ability to take into account an ontology and, separately, a set of entailment rules based on which certain answers are computed.

(2) To take into account domain knowledge (i.e., the ontology and entailment rules in our setting), classical query answering approaches would either materialize the consequences of the data and the knowledge (in warehouse data integration style), or, reformulate the query to integrate the relevant part of the knowledge. We propose a third, original query answering approach, based on a reduction to viewbased query answering. We characterize precisely a class of problems for which this approach holds, present a new method for computing certain answers under these hypotheses, and formally establish the correctness of this method.

The rest of the paper is organized as follows. Section 2 introduces preliminary notions and Section 3 presents our problem statement. Section 4 outlines our query answering approach in relationship with the main existing approaches. Then, Section 5 defines a restricted setting in which our approach applies, and Section 6 proves the correctness of our method in this setting. We end with related work.

Proofs of our technical results are available in the appendix (Section 7).

PRELIMINARIES

We present the basics of the RDF graph data model (Section 2.1), of RDF reasoning used to make explicit the implicit information they encode (Section 2.2), as well as how they can be queried using the widely-considered SPARQL Basic Graph Pattern queries (Section 2.3). Finally, we recall the principles of query rewriting using views in an information integration context (Section 2.4), on which our solution to the problem tackled in this paper is built. RDF graphs build on three pairwise disjoint sets of values: I of IRIs (keys), B of blank nodes (labelled null modeling incomplete information [START_REF] Abiteboul | Foundations of Databases[END_REF]), and L of literals (constants).

RDF Graph

An RDF graph G is a set of well-formed triples (s, p, o) from (I ∪ B) × I × (L ∪ I ∪ B). A triple (s, p, o) states that its subject s has the property p with the object value o [START_REF]1.1 Concepts and Abstract Syntax[END_REF]. We denote the set of all values (IRIs, blank nodes and literals) occurring in an RDF graph G by Val(G), and Bl(G) its set of blank nodes.

Within an RDF graph, triples model either an assertions for unary relations called classes and for binary relations called properties properties, or RDFS ontological constraints between classes and properties. The RDFS constraints that can be used in an RDF graph G, which we denote RDFS(G), are of four flavours: subclass constraints, subproperty constraints, typing of the domain (first attribute) or of the range (second attribute) of a property. The triple notations we adopt for RDF graph's assertions and constraints are shown in Table 1. Further, within triples, we use :b possibly with indices to denote blank nodes and strings between quotes to denote literals.

For instance, consider the following sample RDF graph: Gex = {(:Professor, ≺sc, :Person), (:teaches, →r, :Course) (:Fabian, τ, :Professor), (:Fabian, :teaches, :b), ( :b, :label, "Dance") } Gex models with triples, in this order, that professors are persons, that what is taught is a course, and that Fabian is a professor, who teaches somethings (identified with the blank node -hence unknown -value :b), whose label is "Dance". Further, this graph implicitly models that Fabian is a person, because professors are persons, and :b is a course, because Fabian teaches it.

Finally, the notion of homomorphism between RDF graphs allows characterizing whether an RDF graph simply entails, i.e., is more specific than or subsumed by, another based on their explicit triples only. From now, we write G |= ϕ G to state that ϕ is a homomorphism from G to G , i.e., G simply entails G due to ϕ.

RDF Entailment Rules

The semantics of an RDF graph consists of the explicit triples it contains, and of the implicit triples that can be derived using RDF entailment rules.

Definition 2 (RDF entailment rule

). An RDF entailment rule r has the form body(r) → head(r), where body(r) Built-in RDF entailment rules are defined in [START_REF]RDF 1.1 Semantics[END_REF]. They produce implicit triples by exploiting the RDFS ontological constraints of an RDF graph. In this work, we consider the rule set defined in Table 2, denoted by RRDFS; all values except built-in properties denote blank nodes. For example, for Rule rdfs9 used to propagate values from subclasses to their superclasses:

Local database D1 (data model DM1) Local database D2 (data model DM2) • • • Local database Dn (data model DMn) Ontology O (RDF Schema) m1 m2 m3 m4 m5 mn-1 mn Rules R Mappings M Extent E of M Induced RDF graph G M E M STD O Extent EO G M STD O E O (G M E ∪ G M STD O E O ) R q cert(q, O, R, M, E ) Figure 1: Outline of an O-system architecture. Rule [2] Entailment rule rdfs2 (p, ← d, o), (s1, p, o1) → (s1, τ, o) rdfs3 (p, →r, o), (s1, p, o1) → (o1, τ, o) rdfs5 (p1, ≺sp, p2), (p2, ≺sp, p3) → (p1, ≺sp, p3) rdfs7 (p1, ≺sp, p2), (s, p1, o) → (s, p2, o) rdfs9 (s, ≺sc, o), (s1, τ, s) → (s1, τ, o) rdfs11 (s, ≺sc, o), (o, ≺sc, o1) → (s, ≺sc, o1) ext1 (p, ← d, o), (o, ≺sc, o1) → (p, ← d, o1) ext2 (p, →r, o), (o, ≺sc, o1) → (p, →r, o1) ext3 (p, ≺sp, p1), (p1, ← d, o) → (p, ← d, o) ext4 (p, ≺sp, p1), (p1, →r, o) → (p, →r, o)
• body(rdfs9) = {(s, ≺sc, o), (s1, τ, s)} • head(rdfs9) = {(s1, τ, o)}
where s, o, s1 are blank nodes.

The direct entailment of an RDF graph G with a set of RDF entailment rules R, denoted by CG,R, characterizes the set of implicit triples resulting from triggering (a.k.a. firing) the rules in R using the explicit triples of G only. It is defined as:

CG,R = {ϕ(head(r)) safe | ∃r ∈ R, G |= ϕ body(r)
and there is no ϕ extension of ϕ s.t.

G |= ϕ body(r) ∪ head(r)}
where ϕ(head(r)) safe is ϕ(head(r)), where each blank node in Bl(head(r)) \ Bl(body(r)) is replaced by a fresh blank node. Note that the condition "there is no ϕ extension of ϕ s.t. G |= ϕ body(r) ∪ head(r)" prevents the production of obviously redundant triples.

Without loss of generality, as in the RDF standard, we only consider well-formed entailed triples, i.e., from

(I ∪ B) × I × (L ∪ I ∪ B).
For instance, the rule rdfs9 applies to the RDF graph Gex: Gex |= ϕ body(rdfs9) through the homomorphism ϕ defined as {s → :Professor, o → :Person, s1 → :Fabian}. The rule rdfs3 also applies; the direct entailment of Gex with RRDFS contains exactly the triples (:Fabian, τ, :Person) and ( :b, τ, :Course).

The saturation of an RDF graph allows materializing the semantics of an RDF graph, by iteratively augmenting this graph with the triples it directly entails using a set R of RDF entailment rules, till a fixpoint is reached.

We formalize this as the sequence (G R i ) i∈N of RDF graphs recursively defined as follows:

• G R 0 = G, and
• G R i+1 = G R i ∪ C G R i ,R for 0 ≤ i.
Definition 3 (Saturation of RDF graph). Let G be an RDF graph, and R be a set of entailment rules. The saturation of G w.r.t R, denoted by G R , is defined by:

G R = ∪ i∈N G R i .
The saturation of an RDF graph by any subset of RRDFS is finite [START_REF]RDF 1.1 Semantics[END_REF]. In the preceding example, the saturation of Gex w.r.t. RRDFS is completed by the first direct entailment, hence (Gex)

R RDFS = Gex ∪ CG ex,RRDFS .
Finally, the notion of a homomorphism between RDF graphs is also used to characterize whether an RDF graph entails another w.r.t. a set of RDF entailment rules, i.e., in the presence of implicit triples. An RDF graph G entails an RDF graph G w.r.t. a set R of RDF entailment rules, noted G |= ϕ R G , whenever there is a homomorphism ϕ from G to G R . From now, we will just write G |=R G when a particular ϕ is not relevant to the discussion.

Basic Graph Pattern Queries

A popular fragment of the SPARQL query language for RDF graphs is that of basic graph pattern queries, i.e., the SPARQL conjunctive queries. It builds on the notion of basic graph pattern, which generalizes RDF graphs with variables.

We assume given a set of variables V disjoint from I ∪B∪ L . A basic graph pattern (BGP) is a set of triple patterns belonging to (

I ∪ B ∪ V ) × (I ∪ V ) × (I ∪ B ∪ L ∪ V ).
For a BGP P , we note Var(P) the set of variables occurring in P and by Bl(P ) its set of blank nodes.

A basic graph pattern query is defined as follows:

Definition 4 (BGP query). A BGP query (BGPQ) q is of the form q(x) ← P , where P is a BGP also denoted by body(q) and x ⊆ Var(P). The arity of q is |x|.

The semantics of a BGPQ is defined in terms of the homomorphisms that exist between its BGP body and the interrogated RDF graph, i.e., in terms of the possible matches of the BGP onto the RDF graph explicit and implicit triples.

Definition 5 (BGP to RDF graph homomorphism).

A homomorphism from a BGP P to an RDF graph G is a substitution ϕ of Bl(P )∪Var(P) by Val(G) and is the identity elsewhere such that ϕ(P ) ⊆ G with ϕ(P ) = {(ϕ(s), ϕ(p), ϕ(o)) | (s, p, o) ∈ P }. We write G |= ϕ P to state that ϕ is a homomorphism from P to G.

Definition 6 (BGPQ answers

). The answer set to a BGPQ q on an RDF graph G w.r.t. a set R of RDF entailment rules is:

q(G, R) = {ϕ(x) | G |= ϕ R body(q)} If x = ∅,
q is a Boolean query and the answer to q is false when q(G) = ∅ and true when q(G) = { }.

We notice that the answers of a BGPQ on an RDF graph may be composed by blank nodes.

In the following, we consider without loss of generality that BGPQs do not contain blank nodes, as a blank node appearing in a query can be equivalently replaced with a fresh variable.

For example, consider the BGPQ q(x) ← (x, τ, :Course) asking for all courses in the RDF graph Gex, i.e., for all the resources that are explicitly or implicitly of type Courses in Gex. There is one homomorphism from the BGP body(q) to saturated RDF graph (Gex) R RDFS defined by ϕ = {x → :b}, hence the answer to q on Gex w.r.t. RRDFS is :b. We remark that the answers set would be empty for q on Gex w.r.t. an empty set of RDF entailment rules.

Further, we will rely on the saturation of a BGP w.r.t. an RDFS ontology by a set of RDF entailment rules, defined in [START_REF] Hassad | Learning commonalities in SPARQL[END_REF]. Just like for RDF graphs, we have to define a homomorphism from an RDF graph (in particular a rule body) to a BGP. Then, the definition of BGP saturation is the same as for RDF graphs, up to replacing variables by blank nodes in the definition of a homomorphism.

The saturation of a BGPQ contains in its body all the triples entailed from the BGPQ body and a given ontology, but not those entailed by the ontology alone as illustrated by Figure 7: Definition 7 (BGPQ saturation [START_REF] Hassad | Learning commonalities in SPARQL[END_REF]). Let R be a set of RDF entailment rules, O a set of RDFS statements (the ontology), and q a BGPQ. The saturation of q w.r.t. O, denoted by q R,O , is the BGPQ with the same answer variables as q and whose body, denoted by body(q R,O ), is the maximal subset of (body(q) ∪ O) R such that for any of its subsets S: if O |=R S holds, then body(q) |=R S holds.

Figure 2: The cercle represents (body(q) ∪ O) R , the hatched area is removed from q R,O , because it is consequence of O only, hence not relevant to q.

Consider the RDFS ontology Oex from Gex, i.e., RDFS(Gex) equals to {(:Professor, ≺sc, :Person), (:teaches, →r, :Course) } and the BPGQ q(x) ← (x, :teaches, y) asking for professor teaching at least one course. The saturation (q ∪ Oex) R RDFS contains exactly (x, :teaches, y), (y, τ, :Course) and the triples of Oex. By pruning from this set the triples only entailed by Oex w.r.t. RRDFS, i.e., those in Oex here, the saturation of q w.r.t. Oex and RRDFS is q R RDFS ,Oex (x) ← (x, :teaches, y), (y, τ, :Course).

Finally, similarly to RDF graphs, the saturation of a query w.r.t. an ontology and a subset of RDFS entailment rules is finite.

Query Rewriting using Views

The second scientific area (beyond OBDA) on which we base our approach, is view-based query rewriting. Since it has mainly been studied in a relational setting, we recall its main concepts as laid out e.g., in [START_REF] Halevy | Answering queries using views: A survey[END_REF].

An integration system I is made of a global schema S, that is, a set of relations, and of a set of views. Each such view V specifies one way in which the data from a source D is connected to the schema S. The view binds together two components, one referring to D and one to S, the global schema: (i) V D is a query over the schema of D. It specifies which D data is exposed by V to the integration system. Its result V D (D), called the extension of V , is the maximum amount of data that one can get from D through V . In the typical relational setting, V D (D) is a set of tuples. (ii) V (x) ← ϕ(x) is a query over the global schema S; it specifies how the data exposed by V fits in the global integration schema, i.e., how one can use it to answer queries over the global S. ϕ(x) is typically a Datalog or SQL query.

We use V (I) to designate all the data available through the integration system I (including data that may be supplied by other views) as an answer to the query V (x) ← ϕ(x). For instance, if V1(x) ← ϕ(x) is "all conference publications", V1(I) comprises all conference publications one could obtain through the integration system (whether through view V1 or any other). In general, in an integration setting, it is assumed that the views are sound, that is V D (D) ⊆ V (I). This is because in general, several sources (i.e., views) may bring useful information of the same kind, e.g., no single view comprises all conference papers, and when querying I, one typically wants to get all the papers known in the system. This vision corresponds to the Open World Assumption (OWA) [START_REF] Abiteboul | Foundations of Databases[END_REF].

The so-called certain answers to a query on I are defined based on all the instances of S consistent with the views and their extensions, i.e., for which V D (D) ⊆ V (I) holds for each view V . Definition 8 (Certain answers under OWA [START_REF] Halevy | Answering queries using views: A survey[END_REF]). Let V be a set of view definitions on a global schema S, and E the set of extensions for the the views in V. Let q be a conjunctive query on S. The tuple t is a certain answer to q w.r.t. (V, E), if t ∈ q(I), for each instance I of S consistent with (V, E).

Note that the above views integrate data sources in a global schema following the so-called local-as-view approach. An alternative global-as-view approach exists [START_REF] Halevy | Answering queries using views: A survey[END_REF], but is not relevant to the purpose of this work, hence is not further discussed.

From a practical viewpoint, the certain answers (answers for short) can be computed by rewriting a query using the available views, so as to obtain a rewritten query in terms of the view relations, called a view-based rewriting (or rewriting, in short), directly evaluable on the extensions of the views. From a theoretical viewpoint, a rewriting must be contained in the original query in order to provide correct answers to it. Definition 9 (Query containment). For two queries q1, q2 on a global schema S or on a set of views V, we say that q1 is contained in q2, if for all set E of extensions of V and for all instance of S consistent with (V, E), the answer set of q1 is included in that of q2. The two queries are said equivalent, if q1 is contained in q2 and q2 is contained in q1.

An equivalent rewriting for a query may not always exist, depending on the views and the query. In such cases, maximally contained rewritings are guaranteed to produce all the answers that the system I may bring to the query: Definition 10 (Maximally contained rewriting [START_REF] Halevy | Answering queries using views: A survey[END_REF]).

Let q be a query on S, V a set of views on S and L a query language. A query qr is a maximally contained rewriting of q using V w.r.t. L if:

• qr is query in L on views V only;

• qr is contained in q;

• there does not exist a query q r ∈ L on V such that qr is contained in q r , q r is contained in q and q r is not equivalent to qr.

The following known result shows that for conjunctive views, a maximally contained rewriting in the language of unions of conjunctions of views compute exactly the certain answers. This theorem is inspired by the Theorem 3.2 of [4]: Theorem 1. Let V be a set of conjunctive views on S and q be a conjunctive query on S. If a query qr is a maximally contained rewriting of q using V w.r.t. the language of unions of conjunctive queries, then for each set E of extensions of V, the set of answers of qr on E is exactly the set of certain answers of q on (V, E).

PROBLEM STATEMENT

In this section, we first discuss how heterogeneous data sources can be integrated in and queried through an RDF graph using the notion of mappings (Section 3.1). Then, we extend this approach to the use of an RDFS ontology allowing to interpret the data integrated from the sources (Section 3.2).

RDF integration of data sources

We consider a set of heterogeneous data sources D1, . . . , Dn with respective data models DM1, . . . , DMn. For each data model, we assume available a query language, and assume queries expressed in this language return tuples of bindings, which is the usual case e.g. for SQL, XPath (and any tree pattern language), and BGPQs. Our first step toward handling this data model heterogeneity is to assume that data from each source is exposed to the integration system through a set of mappings:

Definition 11 (Mapping and mapping extension).

A mapping m is of the form m = q1(x) ; q2(x) where q1 and q2 are two queries with the same arity. The body of the mapping m is q1 and its head is q2. An extension of m, denoted ext(m), is the set of answers to q1.

Intuitively, a mapping specifies how to translate the tuples returned by a query q1 on a data source into answers of a query q2 on a global schema. Keep in mind that a mapping is a specification only, i.e., it does not always lead to executing q1 on that dataset, especially when no user query is interested in that data.

Given a set of mappings M, we call an extent of M a set E of extensions defined by E = {ext(m) | m ∈ M}, i.e., the data made available by the sources to the integration system.

In our setting, we rely on mappings which integrate source data into RDF graphs: Definition 12 (RDF mapping). An RDF mapping is a mapping m = q1(x) ; q2(x), where q2 is a BGPQ. Importantly, the above definition makes no assumption on the query language of q1, so that RDF mappings can be used to integrate heterogeneous data sources, e.g., relational, XML, RDF ones, into an RDF graph as follows:

Definition 13 (Induced RDF graph). Given a set M of RDF mappings and an extent E of M, the RDF graph induced by M and E is:

G M E = m∈M {(body(q2)( t)) safe | m = q1(x) ; q2(x), t ∈ ext(m)}
where

• body(q2)( t)
is the set of triples of body(q2) in which we replace the x tuple of answer variables by the tuple t.

• (body(q2)( t)) safe is body(q2)( t) in which we replace each variable by a fresh blank node (recall we consider w.l.o.g. that body(q2) contains no blank nodes).

From now, to simplify the notation, we may also specify an RDF mapping m = q1(x) ; q2(x) simply as:

m = q1(x) ; body(q2).
Example 1. Consider the following data sources of a university department. A first relational source Sp pairs professors with the courses they teach. Let qp(professor, course) be the query on Sp returning such pairs. A second JSON source Ss provides pairs students with the courses they register for. Let qs(student, course) be the query on Ss that retrieves such pairs. Finally, let q l (professor, courseLabel) be a BGPQ asking for labels of courses appearing in each professor's page on the RDF website of the university department.

Consider now that these sources are integrated using the following set Mex of RDF mappings: mp = qp(professor, course) ; (professor, :teaches, course) ms = qs(student, course) ; (student, :registeredFor, course) m l = q l (professor, courseLabel) ;

(professor, :teaches, x), (x, :label, courseLabel)

where :teaches, :registeredFor, :courseLabel are IRIs. We note that, in mapping m l , the variable x represents the existence of an unknown course. Finally, assume that the extent Eex of Mex, defined by that answers to qp, qs, q l is: in which, for instance, the last two triples (:Fabian, :teaches, :b), ( :b, :label, "Dance") results from instanciating the body of m l with the results of q l , i.e., ext(m l ), which also instanciate the head of m l to (:Fabian, :teaches, x), (x, :label, "Dance").

The triples (:Fabian, :teaches, :b), ( :b, :label, "Dance") are therefore added to G Mex Eex , after having replaced the x variable to a fresh blank node (recall the safe operation in Definition 13).

We define an RDF system as a triple S = R, M, E , where R is the set of entailment rules under consideration defining the reasoning power of the system, M the set of mappings that integrate data sources into the RDF system and E the extent thereof.

For such systems, we recast the well-known notion of answers to a BGPQ as follows: Definition 14 (Certain answer set). Given a set R of RDF entailment rules, a set M of mappings and an extent E of M, the certain answer set of a BGPQ q against the RDF system S = R, M, E is:

cert(q, S) = {ϕ(x) | G M E |= ϕ R q(x
)} where ϕ(x) is made of IRIs and literals only.

Example 2 (continued). Consider the RDF system S = R, M, E , where M and E are these of the preceding example, and R only contains the entailment rule rex = (s, :registeredFor, c) → (z, :teaches, c), stating that if some student is registered for some course, then this course is taught by some teacher.

Suppose that one asks the query q(x) = (y, :teaches, x) retrieving the courses taught by some teacher. The answers to this query against S are those that can be obtained from the saturation w.r.t. R of the RDF graph induced by M, E, i.e., the saturation of G Mex Eex from Example 1.

The first triple of G Mex

Eex leads to the answer :SemWeb to q. We remark that :b is not an answer to q though there is an obvious homomorphism from q to the fourth triple in G Mex Eex ; this is because blank nodes (i.e., unknown values) are forbidden in query answers.

The saturation of G Mex Eex with R only adds the implicit triple ( :a, :teaches, :RelDB), hence a second answer :RelDB found using reasoning. We stress here that the saturation of G Mex Eex with R does not add a triple ( :c, :teaches, :SemWeb) because of the presence of the second G Mex Eex triple; indeed, such a triple would be redundant w.r.t. the first G Mex Eex triple and saturation avoids this (recall Section 2.2).

The certain answers cert(q, S) to q on S are therefore equals to {:SemWeb, :RelDB}.

Ontology-based RDF integration of data sources

We now extend RDF systems with the ability to use an ontology, hence domain knowledge, when integrating data sources.

To this aim, we introduce specific mappings whose goal is to feed an RDF system with the RDFS ontological constraints it must consider:

m subClassOf = q subClassOf (s, o) ; (s, ≺sc, o) m subPropertyOf = q subPropertyOf (s, o) ; (s, ≺sp, o) m domain = q domain (s, o) ; (s, ← d , o) mrange = qrange(s, o) ; (s, →r, o)
with as body mapping queries:

q subClassOf (s, o) ← (s, ≺sc, o) q subPropertyOf (s, o) ← (s, ≺sp, o) q domain (s, o) ← (s, ← d , o) qrange(s, o) ← (s, →r, o)
Given R a set of RDF entailment rules, the extension of O's standard mappings, denoted EO, contains the following extensions:

ext(m subClassOf ) = q subClassOf (O, R) ext(m subPropertyOf ) = q subPropertyOf (O, R) ext(m domain ) = q domain (O, R) ext(mrange) = qrange(O, R)
Above, qx(O, R) denotes the answer set of the BGPQ qx evaluated on O as an RDF graph with R as entailment rules (recall BGPQ answers from Definition 6). 2). The extension of m domain in M STD Oex is q domain (Oex, RRDFS), i.e., {(:teaches, ← d , :Professor), (:registeredFor, ← d , :Student), (:teaches, ← d , :Person), (:registeredFor, ← d , :Person)}. The first two triples come from O, which the two others are all generalizations thereof, here obtained using the RDF entailment rule ext1 together with the fact that both students and professors are persons. This is similar for the other three mappings. As a result, all O RDFS triples, both explicit and implicit, are part of the induced RDF graph G

M STD Oex E Oex .
The standard mappings M STD O and their extent EO are defined so that the induced RDF graph contains the knowledge of the saturation of O by R. We will see later (Property 8), that this holds under some restrictions on entailment rules and ontology.

We are now able to define an ontology-based RDF system, as depicted in Figure 1:

Definition 16 (O-system). Given an RDFS ontology O, a set R of RDF entailments rules, a set M of RDF mappings and an extent E thereof, the RDF system with ontology (or

O-system, in short) S = O, R, M, E is the RDF system R, M ∪ M STD O , E ∪ EO .
In this ontology-based RDF integration setting, the problem we formally study in this paper is the following: Problem 1. Given an RDFS ontology O, a set R of RDF entailment rules, a set M of instance mappings and a set E of their extensions, compute the certain answer set of a BGPQ q against the O-system S = O, R, M, E .

REWRITING-BASED QUERY ANSWER-ING: A THIRD WAY

Below, we first review the two main existing approaches to query data in similar settings (Section 4.1), i.e., that involve mappings and ontological knowledge; these are based on instance materialization, respectively, query reformulation. Each has its own drawbacks: materialization requires time to compute and space to store, and it necessitates maintenance when the data, rules and/or mappings change, whereas reformulation may lead to very expensive query evaluation.

We then propose a new approach which does not suffer from these drawbacks (Section 4.2). The key idea is an innovative usage of the well-known technique of view-based rewriting, applied on a set of virtual views, which we obtain by saturating the heads of the mappings M. This approach avoids the pitfalls of both materialization and reformulation. However, it provides complete answer sets only under some restrictions, that we will detail in due time (Section 5).

Existing Approaches: Materialization and Reformulation

The simplest family of methods consists in materializing both the data imported by the mappings (as in data warehousing) and inferences computed from ontological knowledge. In our setting, given an RDF system S = R, M, E (including, but not limited to, O-systems), we would materialize the RDF graph G M E , then saturate it with the rules to obtain (G M E ) R ; certain answers to queries would be computed against this materialization. The benefits and drawbacks of this approach are well-known. Query answering can be very fast as one forgets about mappings and rules at query time. On the other hand, there are several situations in which this double level of materialization is not possible, due to the volume of the obtained data or even the non-termination of the saturation by the rules (note that, whereas termination is ensured for the saturation by standard RDFS entailment rules, it is not the case for more general RDF entailment rules, see Section 5.2 for details). Moreover, this approach is not adapted to contexts where data changes frequently, as the materialization has to be recomputed after the updates, which involves triggering again both mappings and rules.

At the other end of the spectrum, one can avoid any kind of materialization as follows: at query time, a query is first reformulated using the ontological knowledge, then the obtained reformulation is rewritten into another query using the mappings. In our setting, the reformulation step would take as input an RDFS ontology O, a set R of RDF entailment rules and a BGPQ q, and would output a reformulation q of q using O and R. We need reformulation to be sound and complete, i.e., for any RDF graph G whose set of RDFS statements is O, the certain answers to q against G alone must be the certain answers to q against G w.r.t. R (in other words, against G R ). The rewriting step would then turn q into a maximally contained rewriting q r (see Section 2.4), which can be asked against the extent E. One could also consider a mixed approach which, on the one hand, materializes the graph obtained from the mappings (yielding G M E ), and on the other hand reformulates queries, subsequently answered against the materialized graph.

Such an approach is typical of the OBDA setting [START_REF] Poggi | Linking data to ontologies[END_REF][START_REF] Lenzerini | Ontology-based data management[END_REF], in which, for the systems implemented so far (see, e.g., [START_REF] Calvanese | Ontop: Answering SPARQL queries over relational databases[END_REF] for one of the most complete systems), the knowledge is encoded in light description logic languages (typically the OWL 2 QL dialect, which relies on the description logic DL-Lite). However, even for relational conjunctive queries and simple ontological languages that guarantee the termination of the reformulation step, the obtained reformulation can be exponentially larger than the initial query, which may question the practical usability of the technique1 . Notably, with the aim of improving the efficiency of reformulation-based query answering, more general reformulation languages have been investigated (e.g., [START_REF] Thomazo | Compact rewritings for existential rules[END_REF][START_REF] Bursztyn | Optimizing reformulation-based query answering in RDF[END_REF][START_REF] König | Query rewriting for existential rules with compiled preorder[END_REF][START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF][START_REF] Lanti | Cost-driven ontology-based data access[END_REF]).

Most works on query answering in the presence of an ontology make the assumption that data is described over the same vocabulary as the ontology, hence they do not study the interaction between the ontology and mappings. Moreover, most contributions are restricted to conjunctive queries, which, when restricted to binary predicates, correspond to specific BGPQs on triples of the form (:s, τ, :c) and (:s, p, :o), where p cannot be a blank node. In [START_REF] Goasdoué | Efficient query answering against dynamic RDF databases[END_REF], general BGPQs were considered and a reformulation technique was introduced for a specific subset of standard RDF entailment rules (namely the DB fragment, consisting of RDF rules 2,3,7 and 9 (see Table 2). However, this technique has not been so far extended to more RDF entailment rules. Hence, to pursue this approach using RDFS rules, one should first define a sound and complete reformulation technique for BGPQs and RDF entailment rules.

Rewriting-Based Query Answering

We now outline our approach, which proceeds in two main steps. Offline, the mapping heads are saturated by the ontology and the entailment rules. Then, each query is rewritten using the saturated mappings, as if these were view definitions. As already mentioned, this approach does not provide complete answer sets for any O-system, hence we will have to put syntactic restrictions on the allowed ontologies, entailment rules and mappings (see the next section). In a nutshell, we reduce the query answering problem in restricted O-systems to a view-based query answering problem.

Note that saturating the mapping heads and saturating the data produced by the mappings have very different costs in terms of volume and robustness to data dynamicity. Indeed, the size of the mapping heads is expected to be small, and the mappings are by definition independent from changes in data. Hence, on the one hand this technique avoids the main drawbacks of materialization-based approaches, and on the other hand it also avoids those of query reformulation.

We first define the saturation of mappings.

Definition 17 (Saturation of Mapping). Given an RDFS ontology O, a set R of RDF entailment rules and an RDF mapping m = q1(x) ; q2(x), the saturation of the mapping m w.r.t. R and O is defined as:

m R,O = q1(x) ; q R,O 2 (x)
Accordingly, the saturation of a set of mappings M w.r.t. The second idea is to see mappings as views in a integration system following the local-as-view approach (recall Section 2.4), which we formally define below.

R and O is M R,O = {m R,O | m ∈ M},
Definition 18 (Views defined by mappings). Given an RDF mapping m = q1 ; q2, the view defined by m, denoted by Vm, is:

Vm(x) ← body(q2).
Let M be a set of RDF mappings. The set of views defined by M, denoted by VM, is:

VM = {Vm | m ∈ M}.
Furthermore, to any pair (M, E), where E is an extent of M, is assigned the pair (VM, E), such that, for all m ∈ M, ext(m) is the extension of Vm.

The following proposition shows that this translation from mappings to views preserves the certain answers to queries. Property 1. Let M be a set of RDF mappings, E be an extent of M, and VM be the set of views defined by M. For any BGPQ q, the certain answer set of q on the RDF system (without entailment rules) ∅, M, E is equal to the certain answer set of q on (VM, E).

We are now able to outline our method. We assume given an O-system S = O, R, M, E . As explained in Section 3.2, we see S as an RDF system R, M ∪ M STD O , E ∪ EO . The different steps of our method are as follows:

1. (Offline step) Compute M R,O , the saturation of M.

2. To compute the certain answer set of a BGPQ q against S, proceed as follows:

(a) Rewrite q into a maximally contained rewriting qr using the views defined by M R,O ∪ M STD O (b) Compute the answers to qr against the extent E ∪ EO.

PROBLEM RESTRICTIONS

In this section, we state the specific hypotheses under which our approach holds. We first characterize our ontologies (Section 5.1), then our entailment rules (Section 5.2), mappings (Section 5.3), and finally the resulting restricted O-systems (Section 5.4).

First-Order Ontology

The following definition of first-order ontology restricts the form of the RDFS statements that can be used in an ontology. Essentially, it is not allowed to express constraints on the RDFS built-in properties and the RDF type property, nor to use anonymous subjects and objects, i.e., unknown classes and properties.

Definition 19 (FO Ontology).

A first-order ontology O is an RDFS ontology whose triples do not contain any of the following values:

• a blank node,

• the property type, τ (see Example 8),

• an RDFS IRI as subject,

• an RDFS IRI as object.

This setting allows one to express schema statements similar to TBox statements in description logics. For example, the triple (C1, ≺sc, C2) in FO ontology states exactly the DL statement C1 C2, which corresponds to the FO formula ∀x (C1(x) → C2(x)).

Restricted Rules

We consider entailment rules that comply with some restrictions. This yields two kinds of entailment rules, namely ontological rules and instance rules, which respectively allow to infer knowledge about the ontology and about individuals.

The goal of the instance rule restrictions is to allow using RDFS triples when inferring facts about individuals, which is one of the interests of RDF, while ensuring the completeness of saturation based on mapping heads2 . Definition 20 (Restricted rules). We call restricted rule an RDF entailment rule r which is either an ontological rule or an instance rule as defined below:

1. (Ontological rule) body(r) and head(r) contain solely RDFS triples such that Bl(head(r)) ⊆ Bl(body(r)) We first point out below that the standard RDF entailment rules from Table 2 are specific restricted rules.

Example 5. Consider Table 2. Rules rdfs5, rdfs 11, ext1, ext2, ext2, ext3 and ext4 are ontological rules. Indeed, their body and head are composed of RDFS statements, e.g., rdfs5: (p1, ≺sp, p2), (p2, ≺sp, p3) → (p1, ≺sp, p3). All the other rules are instance rules, whose body is composed of an RDFS triple and a triple of the form tr, and the head has a single triple. In Rule rdfs2 defined as follows (s, ← d , o), (s1, p, o1) → (s1, τ, o), tr fulfills Restriction 2(b)i, while the head fulfills Restriction 2d. The same holds for Rule rdfs3. In Rule rdfs9 = (s, ≺sc, o), (s1, τ, s) → (s1, τ, o), tr complies with 2(b)ii and the head with 2d. Finally, in Rule rdfs7: (p1, ≺sp, p2), (s, p1, o) → (s, p2, o), tr complies with 2(b)i and the head with 2c.

The syntax of restricted rules also allows for user-specific rules beyond standard RDF entailment rules, see for instance the rule rex = (s, :registeredFor, c) → (z, :teaches, c) from the running example, stating that if some student is registered for some course, then this course is taught by some teacher.

Since entailment rules will be applied to saturate the mapping heads, the termination of saturation is a crucial requirement. Obviously, this requirement is fulfilled by ontological rules. Indeed, rule heads do not introduce new blank nodes (i.e., for any rule r, Bl(head(r)) ⊆ Bl(body(r))). However, termination is not ensured for instance rules: e.g., a rule of the form (x, p, y) → (y, p, z) (intuitively, for all x and y, if x is related to y by p, there exists z such that y is related to z by p) leads to infinite saturation, as each rule application produces a new individual, which leads to a new rule application. However, we prefer not to further restrict instance rules to enforce termination, because of the variety of candidate syntactic restrictions. Indeed, many acyclicity conditions for sets of rules have been defined in the literature about first-order logical rules (e.g., tuple-generating dependencies or existential rules) and can be imported in our setting. Hence, in the following, we will silently assume that the considered set of restricted rules ensures the termination of saturation, as is the case, for instance, of the set of rules RRDFS ∪ {rex}.

In order to comment on the behavior of restricted rules, let us distinguish RDFS triples that can be contained in a FO ontology, from instance triples (s, p, o) such that (1) p ∈ {≺sc, ≺sp, ← d , →r}, and (2) if p = τ , then o ∈ I .

We first point out that ontological rules can only be applied on triples of an FO ontology, and that any restricted rule that can be applied on an FO ontology is an ontological rule (next Property 2); second, the saturation of an FO ontology by restricted rules (hence, necessarily ontological rules) remains an FO ontology (next Property 3); third, given a graph whose set of RDFS triples is an FO ontology, all RDFS triples that can be brought by application of restricted rules come from ontological rules (next Property 4). Finally, restricted rules behave as expected when they are applied to any RDF graph G composed of an FO ontology and instance triples: the ontological rules compute exactly the saturation of the ontological part of the graph (next Property 5), while the instance rules add triples about the individuals (possibly using ontological triples as well, be they initially present in the graph or inferred by the ontological rules).

RDFS(G R ) = O R
This behavior is schematized by Figure 3: the above properties of ontological rules are summarized by the loop on the FO ontology. The body of an instance rule r is composed of tr a triple and body O (r) a set of RDFS triples. When r is applied on G, the triple tr (resp. body O (r)) is necessarily mapped to an instance triple (resp. FO ontology triples) of G, furthermore the triples produced by this application are necessarily instance triples.

Instance Mappings

In line with the distinction between ontological and instance triples, we distinguish between standard mappings associated with an ontology and instance mappings associated with data sources.

Definition 21 (Instance mapping

). An instance mapping is an RDF mapping m = q1(x) ; q2(x), such that the body of q2 contains only triples of one of the following forms:

G M E ∪ O R = {(s, τ, C1), (s, τ, C2), (C1, ≺sc, C2)}.
However, there is no homomorphism from body(r≺ sc ) to (x, τ, y), (C1, ≺sc, C2), hence (head(m)) R,O = head(m). It follows that the triple (s, τ, C2) is missing in

(G M R,O E ∪ O).
For this reason, m is not considered as an instance mapping.

The next property partially explains why no information is lost when we locally saturate the heads of mappings instead of saturating the graph induced by them. See Figure 4: for an instance rule r, if body(r) is mapped by a homomorphism ϕ to an FO ontology O and a triple v(t) from the head of an instance mapping instantiated by a homomorphism v, then (1) there is a homomorphism ϕ that applies r to {t} ∪ O, and (2) the composition ϕ • v is exactly ϕ. The next property expresses that, when a restricted rule is applied to the head of an instance mapping, the added triples keep the property of being an instance mapping.

Property 7. Let O be an FO ontology, t a triple of the head of an instance mapping m = q1(x) ; q2(x) and r an instance rule such that {t} ∪ O |= ϕ body(r). Then the mapping m = q1(x) ; q 2 (x) with q 2 (x) = body(q2)∪ϕ (head(r)) safe is an instance mapping.

Example 7. Reusing the running example, we illustrate the two previous properties. The instance mapping mp generates the triple (:Fabian, :teaches, :SemWeb) by the homomorphism v = {prof essor → :Fabian, course → :SemWeb} applied on t = (prof essor, :teaches, course) in the head of mp. The instance rule rdfs9 can be used on the generated triple v(t) and FO ontology Oex. Indeed, there is a homomorphism ϕ from body(r) to v(t) ∪ Oex defined as:

ϕ = {p → :teaches, o → :Professor, s1 → :Fabian, o1 → :SemWeb}.
As stated by Property 6, there exists a homomorphism from body(r) to {t} ∪ Oex, which is ϕ defined in Example 4. We check that v(ϕ (body(r))) = ϕ(body(r)), which ensures that applying rdfs2 on mp head with ϕ and then instantiating its saturated head with v returns the same triples as applying rdfs2 with ϕ on mp head with v. Moreover, Property 7 ensures that the saturated mapping m {rdfs2,Oex} p is an instance mapping like mp.

Restricted O-system

We have now defined suitable restrictions for each component of an O-system, which yield a restricted O-system. We precise that only previous properties on FO ontology, restricted rules and instance mappings are needed for the rest of the paper. It means that by using an other syntax of this elements satisfying the same properties, following results will still hold.

Definition 22 (Restricted O-system). We say that an O-system S = O, R, M, E is a restricted O-system if O is an FO ontology, R a set of restricted rules and M a set of instance mappings.

As defined in Section 3.2, the standard mappings associated with an ontology O allow one to integrate the ontological statements of O into an RDF graph, as follows: Property 8. Given an FO ontology O and a set R of restricted rules, it holds that:

G M STD O E O = O R
Futhermore, no other RDFS triples are created by instance mappings and applications of instance rules, hence:

Property 9. For any restricted O-system S = O, R, M, E , the set of RDFS triples in (G M∪M STD O E∪E O ) R is exactly O R .

CORRECTNESS OF THE METHOD

In this section, we present the main arguments that prove the correctness of our method, and refer the reader to the appendix for detailed proofs.

Assume first that we adopt a classical materialization approach: starting from the extent E ∪ EO, we trigger the mappings M∪M STD O , then saturate the obtained graph with the entailment rules R, and finally get the graph G

M∪M STD O E∪E O R
, on which we can ask BGP queries and obtain a complete certain answer set. Now, instead of saturating the graph produced by the mappings, we proceed as follows: (1) we saturate the mappings (actually their head) with the entailment rules, then (2) we trigger the mappings. We thus obtain the graph

G M R,O E ∪ G M STD O E O
. The next theorem states that the graphs obtained by the two ways of doing are equal (which holds up to bijective renaming of blank nodes).

Theorem 2. Given an FO ontology O, a set R of restricted rules, a set M of instance mappings, it holds that:

G M∪M STD O E∪E O R = G M R,O ∪M STD O E∪E O
Of course, this equality does not hold for general O-systems. In Section 5, we have illustrated by examples the role of the main restrictions we enforce and hightlighted some key properties ensured by these restrictions. An important characteristic of restricted O-systems is the distinction between standard and instance mappings, and similarly between ontological and instance entailment rules. This allows one to consider two induced graphs, whose union yields

G M R,O ∪M STD O E∪E O : • G M STD O E O
, which is equal to the saturated ontology O R (Property 8).

• G M R,O

E

, which materializes exactly the instances triples of the saturated graph G M E ∪ O R . This equality also relies on the form of the restricted instance rules, which ensures that every application of an instance rule involved in the saturation of the graph produced the mappings can be similarly performed on a mapping head (Property 6); in particular, no application of an instance rule requires instance triples coming from two different mappings.

Finally, instead of computing the answers to a query q against the materialized graph G M E ∪ O R , we rewrite q into a query qr, such that the answers to q against the system are the answers to qr against E ∪ EO:

Definition 23 (Rewriting). Given an FO ontology O, a set R of restricted rules, and a set M of instance mappings, a rewriting qr of a BGPQ q w.r.t. O, R, M is a query such that, for any extent E of M, the answer set of qr against E ∪ EO is cert(q, S = O, R, M, E ).

We have already shown how mappings can be seen as views (Definition 18 and Property 1), more precisely the set of mappings M R,O ∪ M STD O is seen as the following set of views:

V M R,O ∪M STD O = {Vm(x) ← body(q2) | m ∈ M R,O ∪ M STD O , m = q1(x) ; q2(x)}
with, for each m ∈ M, the extension of Vm being set to ext(m).

Based on this translation, one obtains a rewriting of q w.r.t. O, R, M by computing a maximally contained rewriting of q using the views V M R,O ∪M STD O , as expressed by the following theorem: Theorem 3. Given an FO ontology O, a set R of restricted rules, a set M of instance mappings, and a BGPQ q, qr a maximally contained rewriting of q using the views

V M R,O ∪M STD O w.r.t. UCQs is a rewriting of q w.r.t. O, R, M.
Grouping together Theorems 2 and 3, we obtain the wanted result: the certain answer set to a BGPQ q against a restricted O-system O, R, M, E , is exactly the answer set of qr on the extension E ∪ EO.

RELATED WORK

As we have explained in the Introduction, our work pursues a data integration goal [START_REF] Wiederhold | Mediators in the architecture of future information systems[END_REF][START_REF] Özsu | Distributed and Parallel Database Systems[END_REF], that is: providing access to a set of data sources under a single unified schema.

Ontologies have been used to integrate relational or heterogeneous data sources in mediators [START_REF] Wiederhold | Mediators in the architecture of future information systems[END_REF] following the localas-view approach, using the CLASSIC description logic [START_REF] Levy | Data model and query evaluation in global information systems[END_REF], CARIN which combines Datalog with some description logics [START_REF] Goasdoué | The use of CARIN language and algorithms for information integration: The PICSEL system[END_REF][START_REF] Goasdoué | Answering queries using views: A KRDB perspective for the semantic web[END_REF] or the DL-liteR description logic [START_REF] Abdallah | DL-LITER in the light of propositional logic for decentralized data management[END_REF] underpinning the OWL2QL dialect of the W3C's OWL2 semantic web standard; in particular, [START_REF] Abdallah | DL-LITER in the light of propositional logic for decentralized data management[END_REF] adopts the reformulate-thenrewrite query answering approach sketched in Section 4.1. However, none of the above approaches consider graph data models, as we do with RDF.

We follow the observation, at the origin of the semistructured data management area [START_REF] Garcia-Molina | The TSIMMIS approach to mediation: Data models and languages[END_REF], that graphs are a very convenient paradigm for integrating data from heterogeneous data sources. Adding semantics at the integration level in order to enrich its exploitation was proposed early on, for SGML [START_REF] Christophides | A semantic network approach to semi-structured documents repositories[END_REF] and then soon after for RDF [START_REF] Amann | Integrating ontologies and thesauri to build RDF schemas[END_REF][START_REF] Amann | Integrating ontologies and thesauri for RDF schema creation and metadata querying[END_REF]; data is considered to be represented and stored in a flexible objectoriented model, thus no mappings are used. Reconciliation between the source and the integrated schemas is performed semi-automatically, trying to determine the best correspondences based on the available ontologies, and asking users to solve unclear situations. In contrast, our proposal considers heterogeneous sources, and, following the OBDA approach, relies on mappings to connect (in a loose coupling) the integration ontology and the source schemas.

XML trees have also been used as the integration format in systems integrating heterogeneous data sources following the local-as-view approach [START_REF] Manolescu | Answering XML queries on heterogeneous data sources[END_REF][START_REF] Deutsch | MARS: A System for Publishing XML from Mixed and Redundant Storage[END_REF][START_REF] Amann | Querying XML Sources Using an Ontology-Based Mediator[END_REF]. Virtual views were specified in a pivot relational model (enriched with integrity constraints) to describe how the content of each data source contributes to the global schema. View-based rewriting against this relational model lead to queries over the virtual views, which were then translated back into queries that can be evaluated on each individual source. Ontological knowledge was not exploited in here nor in classical relational view-based integration [START_REF] Genesereth | Infomaster: An information integration system[END_REF][START_REF] Halevy | Answering queries using views: A survey[END_REF], whereas we include them in our framework to enrich the set of results that a user may get out of the system, by making available the application knowledge they encapsulate.

Our work follows the OBDA vision [START_REF] Giese | Optique: Zooming in on big data[END_REF][START_REF] Lembo | Mapping analysis in ontology-based data access: Algorithms and complexity[END_REF][START_REF] Lanti | Cost-driven ontology-based data access[END_REF][START_REF] Calvanese | Using OWL in Data Integration[END_REF]. Compared to these works, our novelty is (i) to extend the typical relational setting to heterogeneous data sources (which is rather simple thanks to mappings), (ii) relying on RDF as the integration model, thus in particular allowing applications to query the integrated data and the ontology, and (iii) proposing a novel approach for query answering, different both from materialization and reformulation, which avoids their drawbacks and is capable of computing certain query answers, under the restrictions we detailed above.

Appendix Proof of Property 1

Proof. Let t be a certain answer of q on ∅, M, E . By definition, there exists mappings m1 = q1,1 ; q2,1, . . . , mn = q1,n ; q2,n of M and tuples t1 ∈ ext(m1), . . . , tn ∈ ext(mn) such that: body(q2,1)( t1) safe , . . . , body(q2,n)( tn) safe |= body(q)( t)

Since the safe operation just replaces variables by fresh blank nodes, we have for each 1 ≤ i ≤ n, we have body(Vm i )( ti) = body(q2,i)( ti) |= body(q2,i)( ti) safe . Let D be an instance of triples w.r.t. (VM, E), by definition for each 1 ≤ i ≤ n, we have ti ∈ q2,i(D), i.e., D |= body(Vm i )( ti). So finally, for each D instance of triples w.r.t. (VM, E), we have D |= body(q)( t). And t is a certain answer of q on (VM, E).

Let's make a remark about maximally contained rewriting. Let qr be a maximally contained rewriting of q using VM w.r.t. UCQ on views language and let Cr be one conjunction component of qr with Cr = Vm 1 , . . . , Vm n . Since we know that qr is contained in q, we can deduce that body(Vm 1 ), . . . , body(Vm n ) |= body(q). Let t be a certain answer of q on (VM, E). Since q is a conjunctive query of triples and VM contains conjunctive views, we know that there exists qr a maximally contained rewriting of q using VM w.r.t. union of conjunctive queries on VM. Moreover, applying Theorem 1 on qr infers that t is an answer of qr on E. So, there exists Cr a conjunction component of qr with Cr = Vm 1 , . . . , Vm n and t1 ∈ ext(m1), . . . , tn ∈ ext(mn), such that: body(Vm 1 )( t1), . . . , body(Vm n )( tn) |= body(q)( t).

By considering existential variables as blank nodes, we have for each 1 ≤ i ≤ n, we have body(q2,i)( ti) safe |= body(Vm i )( ti) where q2,i is such that mi = q1,i ; q2,i. So finally, we have G M E |= body(q)( t), i.e., t is an answer of q on G M E . Moreover t is not composed by any blank node, so t is a certain answer on S.

Examples

The following example illustrates why the property τ is not allowed in an FO ontology, here in an object position.

Example 8. Consider an RDF mapping m = q1(x, y) ; (x, τ , y), its extension ext(m) = {(a, C1)}, the RDF entailment rules rdfs9 defined as (s, ≺sc, o), (s1, τ, s) → (s1, τ, o) and rdfs7 defined as (p1, ≺sp, p2), (s, p1, o) → (s, p2, o), and the ontology O = {(C1, ≺sc, C2), (τ , ≺sp, τ )}. Let M = {m}, E = {ext(m)} and R = {rdfs9, rdfs7}; the saturation of the induced RDF graph is:

G M E ∪ O R = {(a, τ , C1
), (a, τ, C1), (a, τ, C2), (C1, ≺sc, C2), (τ , ≺sp, τ )} The saturated mapping m R,O is q1(x, y) ; (x, τ , y), (x, τ, y), so (G M R,O E ∪ O) does not contain, hence misses, the triple (a, τ, C2).

The following example is relative to the definition of restricted rules and illustrates the importance of the condition x = y in the triple tr.

Example 9. Assume the rule r = (x, p, x) → (x, q, x) would be allowed, and let the mapping m = q1(x, y) ; (x, p, y) and its extension ext(m) = {(a, a)}. Let M = {m}, E = {ext(m)} and R = {rdfs9}. Then the saturation of the induced RDF graph is:

G M E R
= {(a, p, a), (a, q, a)}.

However, there is no homomorphism from body(r) to (x, p, y), hence the saturation of the mapping m with R is exactly m. Therefore, the triple (a, q, a) is missing in the saturated mapping graph G M R,{} E . It is the reason why the condition x = y is enforced in 2(b)i, hence r is not a restricted rule.

Proof of Property 2

Proof. If we assume that r is an instance rule, then body(r) = {tr}∪body O (r), and the triple tr has to be of the form (x, p, y) with p ∈ Bl(body O (r)), otherwise ϕ(tr) could not be an RDFS triple (which would contradict the fact that O |= ϕ body(r)). Then ϕ(p) occurs as a subject or an object of a triple in O, because body O (r) does not have any blank node as a property. However, ϕ(p) cannot be an RDFS IRI, because O is an FO ontology. This contradicts the fact that ϕ(p) is an RDFS IRI since ϕ(tr) ∈ O. We conclude that r is necessarily an ontological rule.

Proof of Property 3

Proof. From Property 2, only ontological rules can be applied on an FO-ontology. We check that the produced RDFS triples comply with the conditions of an FO-ontology.

Proof of Property 4

Proof. From the definition of the restricted rules, we know that if the direct entailment of G by {r} contains an RDFS triple, then r is either an ontological rule, or an instance rule with head containing a triple t = (s, p, o), case 2c. The latter case is not possible, because necessarily p ∈ Bl(body O (r)), i.e., p also occurs as the subject or the object of an RDFS triple t b in the body of r. The application of the rule r maps t b to an RDFS triple of G. Since the set of RDFS triples of G is an FO ontology, p cannot be mapped to an RDFS IRI, which is absurd. Therefore, r is an ontological rule.

Proof of Property 5

Proof. First, we prove that O R ⊆ RDFS(G R ). Using Property 3, we know that O R is an FO ontology, so at least

O R is a set of RDFS triples. Since O ⊆ G, we have O R ⊆ RDFS(G R ).
Second, we prove that RDFS(G R ) ⊆ O R . Let t be a triple in RDFS(G R ), so either t is an RDFS triple of G (and then t ∈ O R ) or t is a RDFS triple in entailment of R on G. In the latter case, we prove that t ∈ O R by induction on (G R i ) i∈N the saturation sequence of G R . By Property 4, if a restricted rules r ∈ R applied on G directly derives at least an RDFS triples, r is an ontological rule. And since, the body of an ontological rule is composed of RDFS triples, a such rule r can be apply only on RDFS triples. Moreover, RDFS(G) = O, so each RDFS triple t in CG,r the direct entailment of r on G is actually in CO,r. Finally, we can remark that RDFS(G R 1 ) ⊆ O R . For the initialization step of the induction, if t a RDFS triple directly entails by G, the preceding remark proves that t ∈ O R . And the induction is assured by Property 3 which shows that O R is an FO ontology, so RDFS(G R 1 ) is an FO ontology. We can start the preceding reasoning again replacing G by G R 1 and O by RDFS(G R 1 ).

Proof of Property 6

Proof. We define body(r) as tr∧body O (r). Since body O (r) is a set of RDFS triples and t (thus also v(t)) is not an RDFS triple, then ϕ(body O (r)) ⊆ O. We now consider the two possible forms of tr. Case (i): tr has the form of (x, p, y), Restriction 2(b)i. As in the proof of Property 2, we know that ϕ(p) is not an RDFS IRI and with the same reasoning, we can show that ϕ(p) = τ . So, the triple ϕ((x, p, y)) is equal to v(t) and the instance mapping triple t = (x , p , y ) with p ∈ I \ {τ }. Since we know that x and y are not in Bl(body O (r)), we know that ϕ

Proof of Property 7

Proof. Let body(r) = {tr} ∪ body O (r). Since body O (r) is a set of RDFS triples and t is not an RDFS triple, we have ϕ (body O (r)) ⊆ O.

The result is just a consequence of the form of head(r). Let u = (s, p, o) be a triple in head(r), we check that in each case ϕ (u) safe can be a triple of the head of an instance mapping:

• if p = τ then o ∈ I ∪ Bl(body O (r)). So ϕ (o)

Proof of Property 8

Proof. By Property 3, O R is an FO ontology, hence contains only RDFS triples. The proof then directly follows from the equalities:

O R = {(s, ≺sc, o) | (s, ≺sc, o) ∈ O R } ∪{(s, ≺sp, o) | (s, ≺sp, o) ∈ O R } ∪ {(s, ← d , o) | (s, ← d , o) ∈ O R } ∪{(s, →r, o) | (s, →r, o) ∈ O R } = {(s, ≺sc, o) saf e | m subClassOf = q subClassOf (s, o) ; (s, ≺sc, o), (s, o) ∈ ext(m subClassOf ) = q subClassOf (O, R)} ∪ {(s, ≺sp, o) saf e | m subPropertyOf = q subPropertyOf (s, o) ; (s, ≺sp, o), (s, o) ∈ ext(m subPropertyOf ) = q subPropertyOf (O, R)} ∪ {(s, ← d , o) saf e | m domain = q domain (s, o) ; (s, ← d , o), (s, o) ∈ ext(m domain ) = q domain (O, R)} ∪ {(s, →r, o) saf e | mrange = qrange(s, o) ; (s, →r, o), (s, o) ∈ ext(mrange) = qrange(O, R)} = G M STD O E O q Corollary 1 Corollary 1. The set of RDFS triples of G M∪M STD O E∪E O is exactly O R .
Proof. Since no instance mapping of M has RDFS triples in its head, the ontology of

G M∪M STD O E∪E O is included in G M STD O E O . Moreover, G M STD O E O
contains only RDFS triples, hence the wanted equality holds.

Proof of Property 9

Proof. By Corollary 1, the set of RDFS triples of

G M∪M STD O E∪E O is O R . By Property 3, O R
is an FO ontology, so by Property 5, the set of RDFS triples of (G

M∪M STD O E∪E O ) R is O R . Below: proofs from Section 6

Proof of Theorem 2

To prove the theorem, we will rely on the next definition and some auxilliary lemmas.

Definition 24. We define the following sequence of mappings:

(M) R,O i = q1 ; (q2) R,O i | q1 ; q2 ∈ M where body((q) R,O i ) = max{S ⊆ (body(q) ∪ O) R i | ∀T ⊆ S, O |=R T ⇒ body(q) |=R T }.
Intuitively, (q) R,O i is the saturation of (body(q) ∪ O) at rank i from which triples entailed solely by O are removed, as in Def. 7.

Lemma 1. Let be q the head of an instance mapping, O an FO ontology and R a set of restricted rules, we have:

∀i ∈ N, body((q) R,O i ) = (body(q)∪O) R i \RDFS((body(q)∪O) R i ).
Proof. First, let i be a positive integer, we prove that body(

(q) R,O i ) ⊆ (body(q) ∪ O) R i \ RDFS((body(q) ∪ O) R i ). Let t be a triple in body((q) R,O i ), so t ∈ (body(q) ∪ O) R i .
Hence by definition of (q) R,O i , we have either O |=R t or body(q) |=R t. We will tackle the both cases separately. We recall that since q is the head of an instance mapping, body(q) only contains none RDFS triples. Moreover using Property 7, we know that q R body only contains none RDFS triples. So if body(q) |=R t, then t ∈ (body(q) ∪ O) R i \ RDFS((body(q) ∪ O) R i ). Inspiring by the proof of Property 5, we can prove the following property: for all u ∈ (body(q)∪O) R i , if u ∈ RDFS((body(q)∪O) R i ) then O |=R u. Using the contraposition of this property, we know that if O |=R t then t ∈ (body(q)∪O) R i \RDFS((body(q)∪O) R i ). So in the both case, t ∈ (body(q)∪O) R i \RDFS((body(q)∪O) R i ). Secondly, let i be a positive integer, we prove that (body(q)

∪ O) R i \ RDFS((body(q) ∪ O) R i ) ⊆ body((q) R,O i
). Let t ∈ (body(q)∪O) R i \RDFS((body(q)∪O) R i ) and S ⊂ (body(q)∪ O) R i , which satisfies the property P (S) = ∀T ⊆ S, O |=R T ⇒ body(q) |=R T . We will prove that if t ∈ S, S is not maximal for the property P , i.e., we will prove P (S ∪ {t}). Let T ⊆ S ∪ {t}, if t ∈ T then O |=R T , because t is not an RDFS triples and Property 3, otherwise T ⊆ S. In both cases, O |=R T ⇒ body(q) |=R T holds, so P (S ∪ {t}) also. Finally, t ∈ body((q) R,O i ).

We notice that even if this sequence of mappings is not increasing, it induces a increasing sequence of RDF graphs

G (M) R,O i E i∈N . Lemma 2.
For any i ∈ N:

• (G M∪M STD O E∪E O ) R i ⊆ G (M) R,O i ∪M STD O E∪E O • (M) R,O i only contains instance mappings
Proof. We start by proving that the set of RDFS triples of G

M∪M STD O E∪E O R i is a subset of G (M) R,O i ∪M STD O E∪E O
, for each i ∈ We deduce that:

∀i ∈ N, RDFS( G M∪M STD O E∪E O R i ) = O R
Moreover, using Property 8, we know that:

∀i ∈ N, O R ⊆ G M∪M STD O E∪E O ⊆ G (M) R,O i ∪M STD O E∪E O .
So finally, we prove that:

∀i ∈ N, RDFS( G M∪M STD O E∪E O R i ) ⊆ G (M) R,O i ∪M STD O E∪E O .
After that, we just have to prove for i ∈ N the following statement P (i):

• each non-RDFS triple of G M∪M STD O E∪E O R i is in G (M) R,O i ∪M STD O E∪E O ,
• Let q be an head of a instance mappings of M, NRq,i = (body(q) ∪ O) R i \ RDFS((body(q) ∪ O) R i ) contains only correct triple for instance mapping head. So (M) R,O i only contains instance mappings.

Here, we have to explain why in the second point of this list, the first sentences implies the second. It comes from the fact that if q is an head of a mapping in (M) R,O i , then body(q) ⊂ (body(q)∪O) R i \RDFS((body(q)∪O) R i ), according to Lemma 1.

We will prove P (i) by induction. In the base case, we show that the statement holds for i = 0:

• G M∪M STD O E∪E O R 0 = G M∪M STD O E∪E O = G (M) R,O 0 ∪M STD O E∪E O ,
• For q a head of mapping in M, (body(q) ∪ O) R 0 \ RDFS((body(q)∪O) R 0 ) = (body(q)∪O)\RDFS(body(q)∪ O) = (body(q) ∪ O) \ O = body(q). So like previously explained we have: (M) R,O 0 = M only contains instance mappings.

In the inductive step, we assume that P (i) holds for i ∈ N, we will prove that P (i + 1) also holds. If t is a non-RDFS triple of G

M∪M STD O E∪E O R i+1
, then there are two cases: , we know by induction hypothesis this mapping is actually an instance mapping. So according to Property 6, there exists a homomorphism ϕ such that tm ∪ O R |= ϕ body(r) and ϕ(body(r)) = ve(ϕ (body(r))). Hence, ϕ(head(r)) safe = ve(ϕ (head(r)) safe ). We show that the mapping q1 ; (q2) R,O i+1 ∈ (M) R,O i+1 is such that ϕ (head(r))) safe ⊆ body((q2) R,O i+1 ). Indeed, it is a consequence of Lemma 1, because we know that ϕ (head(r))) safe ⊆ (body(q2)∪O) R i+1 and ϕ (head(r))) safe contains only no RDFS triple. Finally, we have proved: We also have to prove that for q an head of a mapping in M, NRq,i+1 = (body(q) ∪ O) R i+1 \ RDFS((body(q) ∪ O) R i+1 ) contains only valid triples for instance mapping head. By induction hypothesis, we know that M, NRq,i verify the willing property. Let t a triple of NRq,i+1, so there exists r ∈ R such that t is one directly entailed triple by r on (body(q) ∪ O) R i . If the restricted rule r is an ontological rule, then t is an RDFS triple. This case is absurd, because t will be in RDFS((body(q)∪O) R i+1 ) so t ∈ NRq,i+1. So r is an instance rule and there exists an t ∈ NRq,i such that {t}∪ O R |= body(r). Using Property 7, we know that t is a valid triples for instance mapping head. Finally we can deduce from it that (M) R,O i+1 is a set of instance mappings.

• t ∈ G M∪M STD O E∪E O
We are now able to prove the Theorem 2.

Proof

Proof of Theorem 3

Proof. For any extent E of M, we prove that the certain answers of q on the restricted O-system O, R, M, E is equal to the certain answers of q on the RDF system

∅, M R,O ∪ M STD O , E ∪ EO . cert(q, O, R, M, E ) = {ϕ(x) | G M∪M STD O E∪E O |= ϕ R q(x)} = {ϕ(x) | G M∪M STD O E∪E O R |= ϕ q(x)} = {ϕ(x) | G M R,O ∪M STD O E∪E O |= ϕ q(x)} = cert(q, O, ∅, M R,O , E ) = cert(q, ∅, M R,O ∪ M STD O , E ∪ EO )
where ϕ(x) is made of IRIs and literals only. By Property 1, the certain answers of q on the RDF system ∅, M R,O ∪ M STD O , E ∪ EO are exactly the certain answers of q on (V M R,O ∪M STD O , E∪EO). By Theorem 1, since qr is a maximally contained rewriting of q using V M R,O ∪M STD O w.r.t. union conjunctive queries on this views language, the certain answers of q on views based integration of V M R,O ∪M STD O and E ∪ EO are the answers of qr on the extent E ∪ EO. Because all preceding equality do not depend of the extent E of instance mappings M, qr is a rewriting of q.

Definition 1 (

 1 RDF graph homomorphism). Let G and G be two RDF graphs. A homomorphism from G to G is a substitution ϕ of Bl(G) by Val(G), and is the identity for the other G values (IRIs and literals), such that ϕ(G) ⊆ G , where ϕ(G) = {(ϕ(s), ϕ(p), ϕ(o)) | (s, p, o) ∈ G}.

  ext(mp) = {(:Fabian, :SemWeb)} ext(ms) = {(:Alice, :SemWeb), (:Alice, :RelDB)} ext(m l ) = {(:Fabian, "Dance")} In this setting, the induced RDF graph G Mex Eex is G Mex Eex = {(:Fabian, :teaches, :SemWeb), (:Alice, :registeredFor, :SemWeb), (:Alice, :registeredFor, :RelDB), (:Fabian, :teaches, :b), ( :b, :label, "Dance")}

Definition 15 (

 15 Standard RDFS mappings of O). Given an RDFS ontology O and R a set of RDF entailment rules, the standard RDFS mappings of O, denoted M STD O , are as follows:

Example 3 .

 3 Consider the following extension of the ontology Oex introduced in Section 2: Oex = {(:Professor, ≺sc, :Person), (:Student, ≺sc, :Person), (:teaches, ← d , :Professor), (:teaches, →r, :Course) (:registeredFor, ← d , :Student), (:registeredFor, →r, :Course)} Assume a standard integration of O as per Definition 15, with the set RRDFS of RDF entailment rules (Table

Example 4 .

 4 and the saturated mapping graph, denoted by G M R,O E , is the RDF graph induced by M R,O and an extent E. We consider the mapping mp (Example 1) whose head is the triple (prof essor, :teaches, course), the RDF entailment rule rdfs2 (about ← d ) and the ontology Oex. To saturate mp w.r.t. {rdfs2} and Oex, we map body(rdfs2) to body(head(mp)) ∪ Oex using the following homomorphism: ϕ = {p → :teaches, o :Professor, s1 → prof essor, o1 → course}. The head of the saturated mapping m {rdfs2},Oex p has triples (prof essor, :teaches, course) and (prof essor, τ, :Professor). Hence, m {rdfs2},Oex p will also populate the class :Professor with each value taken by the variable prof essor in mp.

2 .(

 2 Instance rule) body(r) = {tr} ∪ body O (r), where (a) body O (r) is a (possibly empty) set of RDFS triples (b) tr is of one of the following forms: i. (x, p, y) where x, y ∈ B \ Bl(body O (r)), x = y and p ∈ (I \{≺sc, ≺sp, ← d , →r, τ })∪Bl(body O (r)), ii. (x, τ, z) where x ∈ B \ Bl(body O (r)), z ∈ I ∪ Bl(body O (r)) and head(r) contains solely (s, p, o) triples such that: (c) p ∈ I \ {≺sc, ≺sp, ← d , →r} or p ∈ Bl(body O (r)), (d) if p = τ , then o ∈ I or o ∈ Bl(body O (r)).

Property 2 .Property 4 .

 24 Let r be a restricted rule and O be an FO ontology, if O |= ϕ body(r), then r is an ontological rule, i.e., it fulfills Restriction 1. Property 3. Let O be an FO ontology and R be a set of restricted rules, O R is also an FO ontology. Let r be a restricted rule and G be an RDF graph whose set of RDFS triples is an FO ontology. If the direct entailment of G by {r} (denoted C G,{r} in Section 2.2) contains an RDFS triple, then r is an ontological rule.Property 5. Let O be an FO ontology, R be a set of restricted rules and G be an RDF graph such that RDFS(G) = O, it holds that:

Figure 3 :

 3 Figure 3: Restricted rule entailments

Property 6 .vFigure 4 :

 64 Figure 4: Illustration of Property 6.

  |Bl(body O (r)) (tr) = (x, p , y). So if we choose ϕ = ϕ |Bl(body O (r)) ∪ {x → x , y → y }, which is indeed a homomorphism because x = y, then we have {t} ∪ O |= ϕ body(r) and ϕ(body(r)) = v(ϕ (body(r))). Case (ii): tr has the form (x, τ, z), with x / ∈ Bl(body O (r)) and z ∈ I ∪ Bl(body O (r)), Restriction 2(b)ii. Since τ is not an RDFS property, we know that ϕ(tr) = v(t). So v(t) is equal to (a, τ, C) with a ∈ B ∪ I and C ∈ I , and there exists y ∈ B ∪ I such that t = (y, τ, C). We have ϕ |Bl(body O (r)) (tr) = (x, τ, C), so if y ∈ B, then ϕ = ϕ |Bl(body O (r)) ∪ {x → y} satisfies the wanted property. Otherwise, y ∈ I and ϕ = ϕ |Bl(body O (r)) satisfies the wanted property as well, because v is then the identity.

N.

  Using preceding results, we have the following equations for i ∈ N:

•.

  or there exists a restricted rule r ∈ R such that G M∪M STD O E∪E O R i |= ϕ body(r) and t ∈ ϕ(head(r)) safe . Since t ∈ ϕ(head(r)) safe is a non-RDFS triple, r is an instance rule. So there exists an t ∈ G M∪M STD O E∪E O R i such that {t} ∪ O R |= ϕ body(r). By the inductive hypothesis, t is a triple of G Hence there exists a mapping m ∈ M with m = q1 ; q2, and a triple tm ∈ body((q2) R,O i ) (defined in Definition 24) and a tuple e ∈ ext(m) such that ve(tm) = t, where ve is the homomorphism induced by the replacement of answer variables of (q2) R,O i by the tuple e. Since (q2) R,O i is the head of a mapping of (M) R,O

  i

t

  ∈ ϕ(head(r)) safe = ve(ϕ (head(r)) safe ) ⊆ ve(body((q2) R,Oi+1))

Proof of Theorem 2 .. 2 ) 2 )

 222 First, we prove the in-Then, there exists a mapping m ∈ M ∪ M STD O such as m = q1(x) ; q2(x) and there exists t ∈ ext(m) with (s, p, o) ∈ (body(q R,O ( t)) safe . We also know that:• (body(q2)( t)) safe ⊆ G the saturation operation is monotonous, i.e., if G, G are RDF graphs such as G ⊆ G , then G R ⊆ G R. So if we put everything together, we have (considering inclusion by bijective renaming of blank nodes):(s, p, o) ∈ (body(q R,O ( t)) safe ⊆ ((body(q2)( t)) safe ∪ O) R ⊆ G M∪M STD O E∪E O RFinally, we have (s, p, o) ∈ G of the saturation of an RDF graph (Definition 3), there exists i ∈ N such that :

Table 1 :

 1 RDF statements.

	RDF assertions	Triple notation
	Class assertion	(s, τ, c)
	Property assertion	(s, p, o) with p = τ
	RDFS constraints Triple notation
	Subclass	(s, ≺sc, o)
	Subproperty	(s, ≺sp, o)
	Domain typing	(s, ← d , o)
	Range typing	(s, →r, o)

Table 2 :

 2 Sample RDF entailment rules.

and head(r) are RDF graphs, respectively called body and head of the rule r.

Note that most papers in the Knowledge Representation area call query rewriting what we call here query reformulation to avoid confusion with view-based query rewriting.

Essentially, the restrictions seek to ensure that, given any extensions for the mappings, the graph obtained by the saturated mappings is equal to the saturation of the graph obtained by the initial mappings, see Theorem 2.

Acknowledgements

Part of this work is supported by the Inria Project Lab grant iCoda, a collaborative project between Inria and several major French media, aiming at building a heterogeneous data integration platform for ontology-driven data journalism.