François Goasdoué

Ioana Manolescu

Alexandra Roatiş

BGP Query Answering against Dynamic RDF Databases

Keywords: RDF fragments, query answering, reasoning fragments RDF, réponses aux requêtes, raisonnement subClassOf s 2 . s 2 rdfs:subClassOf s 2 . p 1 rdfs:subPropertyOf p 2 . p 1 rdfs:subPropertyOf p 1 . p 1

A promising method for efficiently querying RDF data consists of translating SPARQL queries into efficient RDBMS-style operations. However, answering SPARQL queries requires handling RDF reasoning, which must be implemented outside the relational engines that do not support it. We introduce the expressive database (DB) fragment of RDF for which we devise novel sound and complete techniques for answering Basic Graph Pattern (BGP) queries. Our techniques explore the two established approaches for handling RDF semantics, namely reformulation and saturation; we show how they cope with updates, a complex problem due to the rich RDF semantics. Our algorithms can be deployed on top of any RDBMS(-style) engine, and we experimentally study their performance trade-offs.

Introduction

The Resource Description Framework (RDF) [START_REF]Resource description framework[END_REF] is a graph-based data model accepted as the W3C standard for Semantic Web applications. As such, it comes with an ontology language, RDF Schema (RDFS), that can be used to enhance the description of RDF graphs, i.e., RDF datasets. The W3C standard for querying RDF is SPARQL Protocol and RDF Query Language (SPARQL) [START_REF] W3c | SPARQL protocol and RDF query language[END_REF].

The literature provides several scalable solutions for querying RDF graphs using relational data management systems (RDBMSs, in short) or RDBMS-style specialized engines [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF][START_REF] Neumann | x-RDF-3X: Fast querying, high update rates, and consistency for RDF databases[END_REF][START_REF] Weiss | Hexastore: sextuple indexing for Semantic Web data management[END_REF]. These works, however, ignore the essential RDF feature called entailment, which allows modeling implicit information within RDF. Taking entailment into account is crucial for answering SPARQL queries, as ignoring implicit information leads to incomplete answers [START_REF] W3c | SPARQL protocol and RDF query language[END_REF]. Thus, to capitalize on (and benefit from) scalable RDBMS performance, SPARQL query answering can be split into a reasoning step which handles entailment outside the RDBMSs, and a query evaluation step delegated to RDBMSs.

A popular reasoning step is graph saturation (a.k.a. closure). This consists of pre-computing (making explicit) and adding to the RDF graph all implicit information. Answering queries using saturation amounts to evaluating the queries against the saturated graph. While saturation leads to efficient query processing, it requires time to be computed, space to be stored, and must be recomputed upon updates. The alternative reasoning step is query reformulation. This consists in turning the query into a reformulated query, which, evaluated against the original graph, yields the correct answers to the original query. Since reformulation is made at query run-time, it is intrinsically robust to updates; reformulation is also typically very fast. However, reformulated queries are often syntactically more complex than the original ones, thus their evaluation may be costly.

RDF on one hand, and SPARQL on the other hand, are complex languages with many features. For instance, the RDF specification supports a form of incomplete information through blank nodes and it provides a large set of entailment rules for deriving implicit information. The forthcoming SPARQL 1.1 supports aggregates, negation etc.

If saturation is used, one first choses an RDF fragment and saturates the RDF graph accordingly. Then in a fully orthogonal way, one choses the SPARQL dialect to evaluate on the graph thus saturated. In contrast, reformulation leads to a subtle interplay between the RDF and SPARQL dialects, since the query must be reformulated within the latter, so as to compute correct query answers with respect to the former. Reformulation-based query answering has been studied for the Description Logics (DL) [START_REF] Baader | The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] fragment of RDF and the relational conjunctive SPARQL subset [START_REF] Adjiman | SomeRDFS in the semantic web[END_REF][START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF][START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF], and extensions thereof [START_REF] Arenas | Foundations of RDF databases[END_REF][START_REF] Goasdoué | View selection in semantic web databases[END_REF][START_REF] Kaoudi | RDFS reasoning and query answering on DHTs[END_REF][START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF].

In this paper, we devise and compare query answering techniques for the database (DB) fragment of RDF and the Basic Graph Pattern (BGP) queries of SPARQL. This DB fragment, which we introduce, extends the fragments mentioned above, notably with the support of RDF blank nodes, encoding incomplete information. The Basic Graph Pattern (BGP) queries, identified in the SPARQL recommendation, are more expressive than relational conjunctive queries, since BGPs also allow querying (and joining on) RDF relation names (called classes and properties), which conjunctive queries do not allow.

Our contributions within this DB fragment are:

1. a saturation-based query answering technique robust to updates, relying on saturation maintenance; 2. a reformulation-based query answering technique; 3. a thorough experimental study of the performance trade-offs between the two techniques.

Importantly, our techniques can work on top of any standard RDBMS, to which we delegate RDF graphs storage and BGP query evaluation (through SQL), while implementing out of the core all the necessary steps in order to compute correct answers. This allows extending the benefits of RDBMS scalability and reliability to a larger RDF fragment (the DB fragment) than in previous works. The positioning of our work with respect to the most prominent previous ones is sketched in Figure 1 (more details are provided in Section 9).

Inria

Query language expressive power SPARQL BGP queries relational conjunctive queries RDF fragment expressive power DL DB [START_REF] Adjiman | SomeRDFS in the semantic web[END_REF][START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF][START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF] [10, [START_REF] Kaoudi | RDFS reasoning and query answering on DHTs[END_REF][START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF] [4]

this work The paper is organized as follows. Section 2 introduces RDF graphs and BGP queries. Section 3 relates RDF to relational databases. Section 4 defines our DB fragment of RDF, for which Section 5 presents saturation-based and reformulation-based query answering techniques. These techniques are then studied in-depth in Sections 6 and 7, and experimentally compared in Section 8. We discuss related work in Section 9, then we conclude.

RDF graphs and queries

We introduce RDF graphs, modeling RDF datasets, in Section 2.1, and Basic Graph Pattern queries in Section 2.2.

RDF Graphs

An RDF graph (or graph, in short) is a set of triples of the form s p o . (the final dot preceded by a white space belongs to the normative triple syntax). A triple states that its subject s has the property p, and the value of that property is the object o. Given a set U of URIs, a set L of literals (constants), and a set B of blank nodes (unknown URIs or literals), such that U , B and L are pairwise disjoint, a triple is well-formed whenever its subject belongs to U ∪ B, its property belongs to U , and its object belongs to U ∪ B ∪ L. In what follows, we only consider well-formed triples.

Blank nodes are essential features of RDF allowing to support unknown URI/literal tokens. For instance, one can use a blank node _:b 1 to state that the country of _:b 1 is United States while the city of the same _:b 1 is Washington. Many such blank nodes can co-exist within a graph, e.g., one may also state that the country of _:b 2 is Sweden while the city of _:b 2 is Stockholm; at the same time, the population of Stockholm can be said to be an unspecified value _:b 3 . Notations. We use s, p, o and _:b in triples (possibly with subscripts) as placeholders. That is, s stands for values in U ∪ B, p stands for values in U , o represents values from U ∪ B ∪ L, and _:b denotes values in B. Finally, we use strings between quotes as in "string" to denote literals.

Figure 2 shows how to use triples to describe resources; we use the usual namespaces rdf: and rdfs: for classes and properties comprised in the RDF standard [START_REF]Resource description framework[END_REF], and which can be seen as an RDF meta-model. rdf:type is used to specify to which classes a resource belongs. This can be seen as a form of resource typing. A more intuitive representation of a graph can be drawn from its triples: every distinct subject or object value corresponds to a node labeled with this value; for each triple, there is a directed edge from the subject node to the object one, labeled with the property value. Example 1 (Running example). The two representations in Figure 3 are equivalent as they model the same graph G. The namespaces for user-defined classes and properties were omitted for the sake of readability. This graph describes the resource doi 1 that belongs to an unknown class, whose title (hasTitle) is "Complexity of Answering Queries Using Materialized Views", whose author (hasAuthor) is "Serge Abiteboul" and which has an unknown contact author (hasContactA). This paper is in the proceedings of (inProceedingsOf) an unknown resource whose name (hasName) is "PODS'98". Lastly, the URI www2012 is a conference and the property that associates names (hasName) has been created by "John Doe".

A valuable feature of RDF is RDF Schema (RDFS) that allows enhancing the descriptions in graphs. An RDF Schema declares semantic constraints between the classes and the properties used in these graphs. Figure 4 shows the allowed constraints and how to express them; in this figure, s, o ∈ U ∪ B, while domain and range denote respectively the first and second attribute of every property. The figure also relates these constraints to relational inclusion constraints under the open-world assumption.

Traditionally, constraints can be interpreted in two ways [START_REF] Abiteboul | Foundations of Databases[END_REF]: under the closed-world assumption (CWA) or under the open-world assumption (OWA). Under CWA, any fact not present in the database is assumed not to hold. Under this assumption, if the set of database facts does not respect a constraint, then the database is inconsistent. For instance, the CWA interpretation of a constraint of the form R 1 ⊆ R 2 is: any tuple in the relation R 1 must also be in the relation R 2 in the database, otherwise the database is inconsistent. On the contrary, under OWA, some facts may hold even though they are not in the database. For instance, the OWA interpretation of the same example is: any tuple t in the relation R 1 is considered as being also in the relation R 2 (the inclusion constraint propagates t to R 2 ). The RDF data model -and accordingly, the present work -is based on OWA, and this is how we interpret all the constraints in Figure 4. To give another example in RDF, if the triples hasFriend rdfs:domain Person . and Anne hasFriend Marie . hold in the graph, then so does the triple Anne rdf:type Person . The latter is due to the rdfs:domain constraint in Figure 4.

Example 2 (Continued). Consider next to the above graph G, a schema stating that poster papers (posterCP) together with the unknown class _:b 0 of which doi 1 is an instance, are subclasses of conference papers (confP), which are scientific papers (paper). Moreover, titles (hasTitle), authors (hasAuthor), contact authors (hasContactA) (who are authors) are used to describe papers, which are connected to the conferences (conference) in whose proceedings (inProceedingsOf) they appear. Finally, names (hasName) describe conferences, and creators (createdBy) describe resources. The extended graph G of G corresponding to this schema is depicted in Figure 5.

Entailment. Our discussion about OWA above illustrated an important RDF feature: implicit triples, considered to be part of the graph even though they are not explicitly present in it. The W3C names entailment the mechanism through which, based on the set of explicit triples and some entailment rules (to be described shortly), implicit RDF triples are derived. We denote by i RDF immediate entailment, i.e., the process of deriving new triples through a single application of an entailment rule. Then, (full) RDF entailment can be defined as follows: a triple s p o . is entailed by a graph G, denoted G RDF s p o . if and only if there is a sequence of applications of immediate entailment rules that leads from G to s p o . (where at each step of the entailment sequence, the triples previously entailed are also taken into account). Graph saturation. The immediate entailment rules allow defining the finite saturation (a.k.a. closure) of a graph G, which is the graph, denoted G ∞ , defined as the fixpoint of:

• G 0 = G • G α = G α-1 ∪ {s p o . | G α-1 i RDF s p o .}
The saturation of a graph is unique (up to blank node renaming), and does not contain any implicit triples (they have all been made explicit by saturation).

An obvious connection holds between the triples entailed by a graph G and its saturation:

G RDF s p o . if and only if s p o . ∈ G ∞ .
It is worth noticing that entailment is part of the RDF specification itself, and therefore the semantics of a graph is its saturation. From the RDF standard perspective, any graph G is equivalent to, and models, its saturation G ∞ . Immediate entailment rules. We give here an overview of the different kinds of immediate entailment rules upon which RDF entailment relies.

A first kind of rule generalizes triples using blank nodes. For instance, in the running example, doi 1 rdf:type _:b 0 . entails _:b 3 rdf:type _:b 0 . Indeed, if doi 1 is an instance of _:b 0 , then there exists an instance of _:b 0 .

A second kind of rule derives entailed triples from the semantics of built-in classes and properties. E.g., RDF provides rdfs:Class whose semantics is the set of all built-in and user-defined classes, with the striking effect that rdfs:Class is an instance of itself. As a result, in the running example, doi 1 rdf:type _:b 0 . entails that _:b 0 is a class, i.e., _:b 0 rdf:type rdfs:Class .

Finally, the third kind of rule derives entailed triples from the constraints modeled in an RDF Schema. Some rules derive entailed RDFS statements, through the transitivity of class and property inclusions, and from inheritance of domain and range typing. Using our running example, _:b 0 rdfs:subClassOf confP . and confP rdfs:subClassOf paper . entail _:b 0 rdfs:subClassOf paper .; and hasContactA rdfs:subPropertyOf hasAuthor . and hasAuthor rdfs:domain paper . entail hasContactA rdfs:domain paper . Some other rules derive entailed RDF statements, through the propagation values (URIs, blank nodes, and literals) from sub-classes and sub-properties to their super-classes and superproperties, and from properties to classes typing their domains and ranges. Using our running example, hasContactA rdfs:subPropertyOf hasAuthor . and doi 1 hasContactA _:b 1 . entail doi 1 hasAuthor _:b 1 .; and doi 1 hasAuthor _:b 1 . and hasAuthor rdfs:domain paper . entail doi 1 rdf:type paper .

BGP queries

We consider the well-known subset of SPARQL consisting of (unions of) basic graph pattern (BGP) queries.

A BGP is a set of triple patterns, or triples in short. Each triple has a subject, property and object. Subjects and properties can be URIs, blank nodes or variables; objects can also be literals.

Inria

We focus on the boolean BGP queries of the form ASK WHERE {t 1 , . . . , t α }, and on the non-boolean BGP queries of the form SELECT x WHERE {t 1 , . . . , t α }, where {t 1 , . . . , t α } is a BGP, i.e., a set of triples modeling their conjunction; the variables x in the head of the query are called distinguished variables, and are a subset of the variables occurring in t 1 , . . . , t α . Notations. Without loss of generality, in the following we will use the conjunctive query notation q(x):-t 1 , . . . , t α for both ASK and SELECT queries (for boolean queries, x is empty). We use x, y, and z (possibly with subscripts) to denote variables in queries. We denote by VarBl(q) the set of variables and blank nodes occurring in the query q. The set of values (URIs, blank nodes, literals) of a graph G is denoted Val(G). Query evaluation. Given a query q and a graph G, the evaluation of q against G is:

q(G) = {x µ | µ : VarBl(q) → Val(G) is a total assignment s.t. (t 1 , . . . , t α ) µ ⊆ G}.
In the above, for any triple or set of triples O, we denote by O µ the result of replacing every occurrence of a variable or blank node e ∈ VarBl (q) in O by the value µ(e) ∈ Val(G). If q is boolean, the empty answer set encodes false, while the non-empty answer set made of the empty tuple ∅ µ = encodes true.

Notice that (normative) query evaluation treats the blank nodes in a query as non-distinguished variables. That is, one could consider equivalently queries without blank nodes or queries without non-distinguished variables. Query answering. The evaluation of q against G only uses G's explicit triples, thus may lead to an incomplete answer set. The (complete) answer set of q against G is obtained by the evaluation of q against G ∞ , denoted by q(G ∞ ).

Example 3 (Continued). The following query asks for the authors of papers published in the proceedings of a conference somehow related to PODS'98: q(x):-y 1 hasAuthor x ., y 1 inProceedingsOf y 2 ., y 2 y 3 "P ODS 98" .

That query could be equivalently rewritten into:

q(x):-_:b 0 hasAuthor x ., _:b 0 inProceedingsOf _:b 1 ., _:b 1 _:b 2 "P ODS 98" .
The answer set of q against G is: q(G ∞ ) = { "SA" , _:b 1 }. The answer "SA" results from the assignment µ = {y 1 → doi 1 , x → "SA", y 2 → _:b 2 , y 3 → hasName}, while the answer _:b 1 results from G RDF doi 1 hasAuthor _:b 1 . and the assignment µ

= {y 1 → doi 1 , x → _:b 1 , y 2 → _:b 2 , y 3 → hasName}.
Note that evaluating q against G leads to the incomplete answer set q(G ) = { "SA" } ⊂ q(G ∞ ).

RDF meets RDBMS

Graphs turn out to be a special case of incomplete relational databases based on V-tables [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Imielinski | Incomplete information in relational databases[END_REF]. Such tables allow using variables in their tuples. Observe that repeating a variable within a V-table allows expressing joins on unknown values. An important result on V-table querying is that the standard relational evaluation (which sees variables in V-tables as constants) computes the exact answer set of any conjunctive query [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Imielinski | Incomplete information in relational databases[END_REF]. From a practical viewpoint, this provides a possible way of answering conjunctive queries against V-tables using standard relational database management systems (RDBMSs, in short).

From the above observations, a graph G can be encoded into a (single) Vtable Triple(s, p, o) storing the triples of G as tuples, in which blank nodes become variables. Then, given a BGP query q(x):s 1 p 1 o 1 ., . . . , s n p n o n ., in which blank nodes have been equivalently replaced by fresh non-distinguished variables, the SPARQL evaluation q(G) of q against G is obtained by the relational evaluation of the conjunctive query Q(x):-n i=1 Triple(s i , p i , o i ) against the aforementioned Triple table. Indeed, SPARQL and relational evaluations coincide with the above encoding, as relational evaluation amounts to finding all the total assignments from the variables of the query to the values (constants and variables) in the Triple table, so that the query becomes a subset of that Triple table.

It follows that evaluating Q(x):-n i=1 Triple(s i , p i , o i ) against the Triple table containing the saturation of G, instead of G itself, computes the answer set of q against G. Hence, BGP queries against graphs can be evaluated by any RDBMS.

Example 4 (Continued). Provided that the saturation of the above graph G is encoded into a V-table Triple(s, p, o) as described above, the answer set of the following BGP query: q(x):-y 1 hasAuthor x ., y 1 inProceedingsOf y 2 ., y 2 y 3 "P ODS 98" .

against G (i.e., q(G ∞ )) is the same as the result of evaluating the following relational query against the Triple table:

Q(x):-Triple(y 1 , hasAuthor, x) ∧ Triple(y 1 , inProceedingsOf, y 2 ) ∧
Triple(y 2 , y 3 , "P ODS 98").

The database fragment of RDF

We define a restriction of RDF that we call its database (DB) fragment. Our goal in identifying this fragment is to devise saturation-and reformulation-based query answering techniques that can be deployed on top of any off-the-shelf or RDF-tuned RDBMS. This DB fragment is obtained by:

• restricting RDF entailment [START_REF]Resource description framework[END_REF] to the rules dedicated to RDF Schema only (a.k.a. RDFS entailment), shown in Figures 6789;

• not restricting graphs in any way, in other words, any triple that the RDF specification allows is also allowed in the DB fragment.

We call a graph belonging to our DB fragment a database. A database db is a pair S, D , where S and D are two disjoint sets of triples. S triples can only be RDFS statements such as shown in Figure 4. We call these triples the schema-level of db. The other triples, of the forms listed in Figure 2, belong to D, and are called the instance-level of db. Observe that S and D provide a way to partition any graph (any triple belongs to exactly one of them). The saturation of a database db with this aforementioned entailment rule set is denoted db ∝ , thus db ∝ ⊆ db ∞ .

We consider the BGP queries previously introduced to query the DB fragment of RDF. The evaluation of a query q against a database db is exactly the evaluation of q against the graph db, i.e., q(db), and the answer set of q against db is q(db ∝ ), thus q(db ∝ ) ⊆ q(db ∞ ).

In general, user queries may traverse both the schema-and instance-level of the database. In our running example, one can ask for the ranges of the properties describing conference papers, i.e., ClassRelatedToConfPaper(x):y 1 rdf:type confP ., y 1 y 2 y 3 ., y 2 rdfs:range x .

In some settings, however, the separation between data and schema, which corresponds to many users' intuitive comprehension of the database, may lead them to specify that their queries be evaluated only against the instance-level or only against the schema-level database.

From a database (DB) perspective, queries whose evaluation is asked against the (saturated) instance-level database only are the most familiar. While schema triples are not part of the answer to such an instance-level query, they do impact its answer, because the saturation of the instance-level database (necessary in order to return complete answers) relies on the schema-level triples. E.g., an instance-level query returning the city of WWW2012 is: WWWCity(y):x name "WWW2012" ., x city y . Instance-level queries can also return classes and properties associated to specific values. For instance, one can ask for the classes to which a given value v belongs, i.e., ClassFinding(x):-v rdf:type x .

From a knowledge representation (KR) perspective, a class of interesting queries can be evaluated over the schema-level database alone. Such queries offer a convenient means to explore the relationships between the classes and properties of a schema, including the implied relationships. For instance, one can ask whether a given class is a subclass of another, e.g., SubclassChecking():-posterCP rdfs:subClassOf paper .; or, what are the classes typing the domain of a given property, e.g., DomainFinding(x):-inProceedingsOf rdfs:domain x . Another schema exploration query can be Schema(x, y, z):-x y z ., returning all triples of the database. By restricting the query to only the schema-level database, the user retrieves all classes, properties, and direct or entailed relationships among them.

In conclusion, our setting is general enough to integrate both DB-style instance-level querying and KR-style schema-level querying, while also allowing a smooth integration of both levels through queries on both database components.

Query answering in databases

We investigate two query answering techniques against RDF databases: saturation-and reformulation-based. Each technique performs a specific preprocessing step, either on the database or on the queries, to deal with entailed triples; after which query answering is reduced to query evaluation.

Saturation-based query answering is rather straightforward, since the answer set of a query is computed exactly as it is formally defined. The saturation of the database is computed (using the allowed entailment rules), so that the answer set of every query against the (original) database is obtained by query evaluation against the saturation. The advantage of this approach is that it is easy to implement. Its disadvantages are that database saturation needs time to be computed and space to store all the entailed triples; moreover, the saturation must be somehow recomputed upon every database update.

Reformulation-based query answering reformulates a query q w.r.t. a database db into another query q (using the immediate entailment rules), so that the evaluation of q against the (original) database db, denoted q (db), is exactly the answer set of q against db (i.e., q(db ∝ )). The advantage of reformulation is that the database saturation does not need to be (re)computed. The disadvantage is that every incoming query must be reformulated, which often results in a more Inria complex query.

We focus on saturation-and reformulation-based query answering only for instance-level queries. The following theorem shows that to answer such queries, among our DB fragment's rules shown in Figures 6789, it suffices to consider only the entailment rules in Figure 9:

Theorem 1.
Let db be a database, t 1 be a triple of the form s rdf:type o ., and t 2 be a triple of the form s p o . t 1 ∈ db ∝ (respectively, t 2 ∈ db ∝ ) iff there exists a sequence of application of the rules in Figure 9 leading from db to t 1 (respectively t 2 ), assuming that each entailment step relies on db and all triples previously entailed.

Proof of Theorem 1. For one direction (⇐), the proof is trivial as the rules of Figure 9 are among those defining db ∝ .

For the converse direction (⇒), let us call a derivation of t any sequence of immediate entailment rules that produces the entailed triple t, starting from db. Let us consider, without loss of generality, a minimal derivation (i.e., in which removing a step of rule application does not allow deriving t anymore). A derivation can be minimized by gradually removing steps producing entailed triples that are not further reused in the entailment sequence of t. We show for such a minimal derivation of an entailed triple t that any step using a rule that is not in Figure 9 can be replaced by a sequence of steps using only rules from Figure 9, leading to another derivation of t. Applying exhaustively the above replacement on the minimization of obtained derivations obviously leads to a derivation of t using the rules in Figure 9 only.

Consider a minimal derivation of t using the immediate entailment rule from Figure 9: s rdfs:subClassOf o ., s 1 rdf:type s . RDF s 1 rdf:type o . While the triple s 1 rdf:type s . is either in db or produced by a rule from Figure 9 (only the rules in Figure 9 produce such a triple), the triple s rdfs:subClassOf o . may result from the triples {s rdfs:subClassOf o n ., o n rdfs:subClassOf o n-1 ., . . . , o 1 rdfs:subClassOf o .} ⊆ db and n applications of the rule s rdfs:subClassOf o ., o rdfs:subClassOf o 1 . RDF s rdfs:subClassOf o 1 . from Figure 8 (only that rule produces triples of the form s rdfs:subClassOf o .). Observe that we do not have to consider the rules from Figure 6 in a minimal derivation. It is therefore easy to see that the application of s rdfs:subClassOf o ., s 1 rdf:type s . RDF s 1 rdf:type o . in the derivation of t can be replaced by the following sequence:

s rdfs:subClassOf o n ., s 1 rdf:type s . RDF s 1 rdf:type o n ., o n rdfs:subClassOf o n-1 ., s 1 rdf:type o n . RDF s 1 rdf:type o n-1 ., . . . , o 1 rdfs:subClassOf o ., s 1 rdf:type o 1 . RDF s 1 rdf:type o .
The rest of the proof is omitted as it amounts to show, similarly as above, that the claim also holds for the three other immediate entailment rules of Figure 9.

Saturation-based query answering

The first query answering technique is based on our Saturate algorithm, which computes the instance-level saturation of a given database. Evaluating the original query against this saturation then yields the exact answer set.

{c 1 rdfs:subClassOf c 2 ., s rdf:type c 1 .} ⊆ db db = db ∪ {s rdf:type c 2 .} (1)
{p rdfs:domain c .,

s p o .} ⊆ db db = db ∪ {s rdf:type c .} (2)
{p rdfs:range c .,

s p o .} ⊆ db db = db ∪ {o rdf:type c .} (3)
{p 1 rdfs:subPropertyOf p 2 ., s p 1 o .} ⊆ db db = db ∪ {s p 2 o .} (4)
Figure 10: Saturation rules for an RDF database db.

Saturate 0 (db) = db Saturate 1 (db) = Saturate 0 (db) ∪ {doi 1 rdf:type confP ., doi 1 rdf:type paper ., doi 1 hasAuthor _:b 1 ., _:b 2 rdf:type conference .} Saturate 2 (db) = Saturate 1 (db)

Database saturation

Our Saturate Algorithm relies on the saturation rules in Figure 10, which are a direct implementation of the entailment rules in Figure 9. In Figure 10 and in the sequel, the bold symbols (possibly with subscripts) c for a class, and p for a property, denote some unspecified values.

The rules in Figure 10 define a set of database transformations of the form input output , where both the input and the output are databases. Intuitively, given a database db, Saturate(db) applies exhaustively the rules in Figure 10, on db plus all the gradually generated triples. The output of Saturate(db) is defined as the fixpoint Saturate ∞ (db), where:

Saturate 0 (db) = db Saturate k+1 (db) = Saturate k (db) ∪ {t 3 | ∃i ∈ [1, 4] s.t. applying rule (i) on some {t 1 , t 2 } ⊆ Saturate k (db) produces t 3 with t 2 ∈ Saturate j<k-1 (db)} Example 5 (Continued).
The saturation of db is shown in Figure 11.

Theorem 2 shows that our saturation algorithm terminates and provides an upper bound for the size of its output.

Theorem 2. For a database db, the size (number of triples) of the output of Saturate(db) is in O(#db 2 ), where #db is the size (number of triples) of db.

Proof of Theorem 2. A close examination of the saturation rules exhibits producer-consumer dependencies among rules. For instance, triples produced

Inria by the rule (1) can only be used to further apply the same rule. We say rule (1) can only feed itself. One can similarly see that rules ( 2) and ( 3) can only feed rule (1), and rule (4) can only feed itself plus rules (2) and [START_REF] Adjiman | SomeRDFS in the semantic web[END_REF].

Given the two possible forms of instance-level triples, we write the saturation schemes based on the above dependencies using regular expressions as follows.

Instance-level triple Saturation scheme s rdf:type o .

(1) * s p o . • The triple s rdf:type o . can be transformed at most #S times by the sequence of rules (1) * (there is at most #S schema-level triples in db).

• The triple s p o . can be transformed at most #S times by the sequence of rules (4) * .( 2).( 1) * and also at most #S times by the sequence of rules (4) * .( 3).( 1) * (there is at most #S schema-level triples in db).

As a result, the worst-case is for a triple s p o .: the overall upper bound for the size of the output of Saturate(db) is 2 * #S.

The above result easily generalizes to a database whose instance-level is of size #D: 2 * #S * #D. Given that #db = #S + #D, the size of the output of Saturate(q) is in O(#db 2 ).

Saturation maintenance upon updates

As mentioned earlier, saturation-based query answering is efficient when the saturation is pre-computed, so that query answering reduces to direct evaluation at query time. However, when database updates are allowed, the saturation must be somehow recomputed upon every update.

We propose here saturation maintenance upon two kinds of updates: insertion -adding triples to the database and deletion -removing triples from the database.

We extend the previous notion of database saturation, so that it becomes a multiset in which a triple appears as many times as it can be entailed. Formally, given a database db, the saturation is now defined as the fixpoint Saturate ∞ + (db) obtained from the following Saturate + algorithm; where is the union operator for multisets.

Saturate 0 + (db) = db Saturate k+1 + (db) = Saturate k + (db) {t 3 | ∃i ∈ [1,
(db \ {t}) = • Saturate + (db) if t ∈ db, otherwise, t ∈ db and • Saturate + (db)\ + [Saturate + ( S, {t} )\ + S] if t is an instance-level triple; • (Saturate + (db) \ + {t}) \ + ( t ∈D [Saturate + ( S, {t } ) \ + S]), where the multiset D is {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on {t, t 2 } with t 2 ∈ Saturate + (db) yields t 3 }, if t is a schema-level triple.
Proof of Theorem 3. Let us consider the three cases for insertions.

\ + S] = S, D 1 [ S, D 2 \ + S] = S, D 1 D 2 . Thus, Saturate 0 + ( S, D 1 D 2 ) = Saturate 0 + ( S, D 1 ) [Saturate 0 + ( S, ) \ + S] holds. Inductive step: Suppose that Saturate k + ( S, D 1 D 2 ) = Saturate k + ( S, D 1 ) [Saturate k + ( S, D 2 ) \ + S]
for k < α and let us show that it still holds for k = α.

By definition, Saturate α + ( S, D 1 ) [Saturate α + ( S, D 2 ) \ + S] = [Saturate α-1 + ( S, D 1 ) {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + ( S, D 1 ) yields t 3 with t 2 ∈ Saturate j<α-1 + ( S, D 1 )}] [(Saturate α-1 + ( S, D 2 ) {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + ( S, D 2 ) yields t 3 with t 2 ∈ Saturate j<α-1 + ( S, D 2 )}) \ + S] holds.
By the semantics of the and

\ + operators, Saturate α + ( S, D 1 ) [Saturate α + ( S, D 2 )\ + S] = [Saturate α-1 + ( S, D 1 ) (Saturate α-1 + ( S, D 2 ) \ + S)] {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + ( S, D 1 ) [Saturate α-1 + ( S, D 2 ) \ + S] yields t 3 with t 2 ∈ Saturate j<α-1 + ( S, D 1 ) [Saturate j<α-1 + ( S, D 2 ) \ + S]} holds. By IH, Saturate α + ( S, D 1 ) [Saturate α + ( S, D 2 ) \ + S] = Saturate α-1 + ( S, D 1 D 2 ) {t 3 | ∃i ∈ [1,
k + (db ∪ {t}) = Saturate k + (db) {t} k l=0 t l ∈D l [Saturate k-l + ( S, {t l } )\ + S],
where the multiset D l is ∅ for l = 0 and {t 3 | ∃i ∈ [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF][START_REF] Arenas | Foundations of RDF databases[END_REF]

0 l=0 t l ∈D l [Saturate 0-l + ( S, D l ) \ + S] = db {t} = db ∪ {t} since t ∈ db. Therefore, Saturate 0 + (db ∪ {t}) = Saturate 0 + (db) {t} 0 l=0 t l ∈D l [Saturate 0-l + ( S, D l ) \ + S] holds. Inductive step: Suppose that Saturate k + (db ∪ {t}) = Saturate k + (db) {t} k l=0 t l ∈D l [Saturate k-l
+ ( S, {t l } ) \ + S] holds for k < α and let us show that it still holds for k = α.

By definition, Saturate

α + (db) {t} α l=0 t l ∈D l [Saturate α-l + ( S, {t l } ) \ + S] = (Saturate α-1 + (db) {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + (db) yields t 3 with t 2 ∈ Saturate j<α-1 + (db)}) {t} t α ∈D α [Saturate 0 + ( S, {t α } ) \ + S] α-1 l=0 t l ∈D l [(Saturate α-1-l + ( S, {t l } ) {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1-l + ( S, {t l } ) yields t 3 with t 2 ∈ Saturate j<α-1-l + ( S, {t l } )}) \ + S] holds.
That is, by the semantics of the and \ + operators, Saturate α + (db) {t}

α l=0 t l ∈D l [Saturate α-l + ( S, {t l } ) \ + S] = Saturate α-1 + (db) {t} α-1 l=0 t l ∈D l [Saturate α-1-l + ( S, {t l } ) \ + S] {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + (db) yields t 3 with t 2 ∈ Saturate j<α-1 + (db)} t α ∈D α [ S, {t α } \ + S] α-1 l=0 t l ∈D l {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1-l + ( S, {t l } ) yields t 3 with t 2 ∈ Saturate j<α-1-l + ( S, {t l } )} holds. By IH, Saturate α + (db) {t} α l=0 t l ∈D l [Saturate α-l + ( S, {t l } ) \ + S] = Saturate α-1 + (db∪{t}) {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + (db) yields t 3 with t 2 ∈ Saturate j<α-1 + (db)} D α α-1 l=0 t l ∈D l {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1-l + ( S, {t l } ) yields t 3 with t 2 ∈ Saturate j<α-1-l + ( S, {t l } )} holds. By definition of D 0≤i≤α , Saturate α + (db) {t} α l=0 t l ∈D l [Saturate α-l + ( S, {t l } ) \ + S] = Saturate α-1 + (db ∪ {t}) {t 3 | ∃i ∈ [1,
+ (db)})\ + [(Saturate α-1 + ( S, {t} ) {t 3 | ∃i ∈ [1, 4] such that applying Inria α-1 l=0 t l ∈D l [(Saturate α-1-l + ( S, {t l } ) {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1-l + ( S, {t l } ) yields t 3 with t 2 ∈ Saturate j<α-1-l + ( S, {t l } )}) \ + S]) holds.
That is, by the semantics of the and \ + operators and since

α-1 l=0 t l ∈D l [Saturate α-1-l + ( S, {t l } ) \ + S] ⊆ Saturate α-1 + (db) holds due to t ∈ db, (Saturate α + (db)\ + {t})\ + ( α l=0 t l ∈D l [Saturate α-l + ( S, {t l } )\ + S]) = [(Saturate α-1 + (db) \ + {t})\ + α-1 l=0 t l ∈D l (Saturate α-1-l + ( S, {t l } ) \ + S)] {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + (db) yields t 3 with t 2 ∈ Saturate j<α-1 + (db)}\ + ( t α ∈D α [Saturate 0 + ( S, {t α } ) \ + S] α-1 l=0 t l ∈D l {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1-l + ( S, {t l } ) yields t 3 with t 2 ∈ Saturate j<α-1-l + ( S, {t l } )}) holds. By IH, (Saturate α + (db) \ + {t})\ + ( α l=0 t l ∈D l [Saturate α-l + ( S, {t l } ) \ + S]) = Saturate α-1 + (db\{t}) {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + (db) yields t 3 with t 2 ∈ Saturate j<α-1 + (db)} \ + (D α α-1 l=0 t l ∈D l {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1-l + ( S, {t l } ) yields t 3 with t 2 ∈ Saturate j<α-1-l + ( S, {t l } )}) holds. By definition of D 0≤i≤α , (Saturate α + (db) \ + {t})\ + ( α l=0 t l ∈D l [Saturate α-l + ( S, {t l } ) \ + S]) = Saturate α-1 + (db \ {t}) {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + (db\ {t}) yields t 3 with t 2 ∈ Saturate j<α-1 + (db \ {t})} holds. Therefore, (Saturate α + (db) \ + {t})\ + ( α l=0 t l ∈D l [Saturate α-l + ( S, {t l } ) \ + S]) = Saturate α + (db \ {t}) holds.
Theorem 3 reads as follows. Inserting a triple already in the database, or deleting a triple that is not in the database, does not affect the current saturation. Otherwise, inserting (deleting) a given instance-or schema-level triple also adds to (removes from) the current saturation any instance-level triple whose derivation uses this given triple.

From a practical viewpoint, the multiset Saturate + (db) can be compactly stored as the set Saturate(db), for which every triple is tagged with (i) a boolean indicating whether it is either in db or only entailed by db and (ii) an integer indicating how many times it appears in Saturate + (db). That way, we encode in a single lightweight representation db, Saturate(db), and Saturate + (db).

From database saturation to saturation-based query answering

Based on the above notion of saturation, we state our saturation-based query answering technique:

Inria

Theorem 4. Given a BGP query q and a database db, the following holds:

q(db ∝ ) = q(Saturate(db)) = q(set(Saturate + (db))).

The proof for Theorem 4 trivially follows from Theorem 1, the definition of our Saturate algorithm, and Property 1. From a practical viewpoint, based on Section 3, saturation-based query answering can be delegated to any RDBMS by storing either Saturate(db) or the aforementioned compact representation of Saturate + (db) in the Triple table, and then by evaluating queries using relational evaluation.

Example 7 (Continued). Consider now the query q(x, y):-x rdf:type y . asking for all resources and the classes to which they belong. The answer set of q against the previous database db is:

q(Saturate(db)) = q(set(Saturate + (db))) = { doi 1 , _:b 0 , www2012, conference , doi 1 , confP , doi 1 , paper , _:b 2 , conference }.

Reformulation-based query answering

The second query answering technique is based on our Reformulate algorithm. Given a query q and a database db, Reformulate(q, db) reformulates q into a set of queries, such that the union of the non-standard evaluations (see below) of these queries on db produces q(db ∝ ), the answer set of the original query against the database.

Query reformulation

Our Reformulate algorithm exhaustively applies the set of rules shown in Figure 13, starting from a query q and a database db. Each rule defines a transformation of the form input output , where the input is of the form logical condition on db, logical condition on q and the output is a query q . Each but not both of the conditions in the input may be empty. Intuitively, each rule produces a new query when the rule's input conditions are satisfied, one by the database db, and the other by some query (either the original query q or a query q produced by a previous application of a rule). The set of all queries produced by applying the rules is the result of the reformulation of q w.r.t. db. Partially instantiated queries. We first introduce the notion of partially instantiated queries. Let q be a query. A partially instantiated query denoted q σ , is a query q σ (x σ ):-(t 1 , . . . , t α ) σ where σ assigns a subset of the variables and blank nodes in q to some values (URIs, blank nodes, literals). In a non-standard fashion, some distinguished variables of q σ can be bound. If σ = ∅, then q σ coincides with the original (non-instantiated) query q.

The notions of evaluation and answer set of BGP queries provided in Section 2.2 for graphs and in Section 4 for databases generalize to partially s y o . ∈ q σ q σ∪ν={y→rdf:type} (5)

s 1 p o 1 . ∈ db, s y o . ∈ q σ q σ∪ν={y→p} (6)
s 1 rdfs:subPropertyOf p . ∈ db, s y o . ∈ q σ q σ∪ν={y→p} (7)

p rdfs:subPropertyOf o 1 . ∈ db, s y o . ∈ q σ q σ∪ν={y→p} (8)
s 1 rdf:type c . ∈ db, s rdf:type z . ∈ q σ q σ∪ν={z→c} (9)

s 1 rdfs:subClassOf c . ∈ db, s rdf:type z . ∈ q σ q σ∪ν={z→c} (10)
c rdfs:subClassOf o . ∈ db, s rdf:type z . ∈ q σ q σ∪ν={z→c} (11)
s 1 rdfs:domain c . ∈ db, s rdf:type z . ∈ q σ q σ∪ν={z→c} (12)

s 1 rdfs:range c . ∈ db, s rdf:type z . ∈ q σ q σ∪ν={z→c} (13)

c 1 rdfs:subClassOf c 2 . ∈ db, s rdf:type c 2 . ∈ q σ q σ[s rdf:type c2 ./s rdf:type c1 .] (14)
p rdfs:domain c . ∈ db, s rdf:type c . ∈ q σ q σ[s rdf:type c ./s p y .]

p rdfs:range c . ∈ db, s rdf:type c . ∈ q σ q σ[s rdf:type c ./y p s .]

)

p 1 rdfs:subPropertyOf p 2 . ∈ db, s p 2 o . ∈ q σ q σ[s p1 o ./s p2 o .] (17)
Figure 13: Reformulation rules for a partially instantiated query q σ w.r.t. a database db.

instantiated queries as follows. Given a database db whose set of values (URIs, blank nodes, literals) is Val(db), a query q σ (x σ ):-(t 1 , . . . , t α ) σ whose set of variables and blank nodes is VarBl(q σ ), the evaluation of q σ against db is:

q σ (db) = {(x σ ) µ | µ : VarBl(q σ ) → Val(db) is a total assignment s.t. Inria ((t 1 , . . . , t α ) σ ) µ ⊆ db}.
The answer set of q σ against db is the evaluation of q σ against db ∝ , denoted q σ (db ∝ ). Reformulation rules. The rules ( 5)-( 13) reformulate queries by binding one of their variables, either to the built-in property rdf:type or to a class or property name picked in the database. The other rules ( 14)-( 17) replace some query triple with another, based on schema-level triples.

Consider for instance rule [START_REF] Baader | The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]. The rule says: if a triple of the form s y o ., i.e., having any kind of subject or object, but having a variable in the property position, appears in q σ , then create the new query q σ∪ν , which binds y to the built-in property rdf:type. Observe that if y was a distinguished variable in q σ , a head variable in q σ∪ν will be bound after the rule application. Now consider rule (6) on some query q σ . If q σ contains a triple of the same form s y o ., and the database db contains a triple with any p in the property position, the rule creates the new query q σ∪ν where y is bound to p. Rules ( 7) and ( 8) instantiate query variables appearing in the property position, to values appearing in a rdfs:subPropertyOf statement of db. The intuition is that both the subject and the object of a rdfs:subPropertyOf statements are properties, therefore they can be used to instantiate the property variable y.

Rules (9)-( 13) instantiate the variable z in a query triple of the form s rdf:type z . The RDF meta-model specifies that the values of the rdf:type property are classes. Therefore, the rules bind z to db values of which it can be inferred that they are classes, i.e., those appearing in specific positions in schema-level triples. For instance, if s 1 rdf:type c . ∈ db, then c is a class and z in rule (9) can be instantiated to c. Similarly, the subject and object of a rdfs:subClassOf statements are used in rules [START_REF] Goasdoué | View selection in semantic web databases[END_REF] and [START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF]. Finally, Rules ( 14)- [START_REF] Neumann | x-RDF-3X: Fast querying, high update rates, and consistency for RDF databases[END_REF] use schema triples to replace (denoted old triple / new triple) a triple in the input query with a new triple. Rule (14) exploits rdfs:subClassOf statements: if the query q σ asks for instances of class c 2 and c 1 is a subclass of c 2 , then instances of c 1 should also be returned, and this is what the output query of this rule does. The last three rules are similar.

Example 8 (Continued). Consider the previously introduced database db and query q(x, y, z):-x y z . asking for the triples of db (including the entailed ones). We show how some of the above rules can be used to reformulate q w.r.t. db.

1. Using q as input for rule (5) produces the query: q {y→rdf:type} , i.e., q(x, y, z):-x rdf:type z .

2. Using q {y→rdf:type} as input for rule [START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF] can lead to: q {y→rdf:type,z→confP} , i.e., q(x, rdf:type, confP):-x rdf:type confP .

3. Finally, using q {y→rdf:type,z→confP} as input for rule (14) can lead to: q(x, rdf:type, confP):-x rdf:type _:b 0 .

Query reformulation algorithm. For a query q and a database db, the output of Reformulate(q, db) is defined as the fixpoint Reformulate ∞ (q, db), where: [START_REF] Neumann | x-RDF-3X: Fast querying, high update rates, and consistency for RDF databases[END_REF] s.t. applying rule (i) on db and some query q σ ∈ Reformulate k (q, db) yields the query q σ } Theorem 5 shows that our reformulation algorithm terminates and provides an upper bound for the size of its output.

Reformulate 0 (q, db) = {q} Reformulate k+1 (q, db) = Reformulate k (q, db) ∪ {q σ | ∃i ∈ [5, . . . ,
Theorem 5. Given a BGP query q and a database db, the size (number of queries) of the output of Reformulate(q, db) is in O((6 * #db 2 ) #q ), with #db and #q the sizes (number of triples) of db and q respectively. Proof of Theorem 5. As in the proof for Theorem 2, a close examination of the reformulation rules also exhibits producer-consumer dependencies among rules.

Given the possible forms of query triples that trigger reformulation rules, we write the reformulation schemes based on these dependencies using regular expressions as follows.

Query triple Reformulation scheme s y o .

[( 5).((9) + ( 10) + ( 11) + ( 12) + ( 13)).( 14) * .(( 15) +( 16)).( 17) * ] + [(( 6) + ( 7) + ( 8)).( 17) * ] s rdf:type z . ((9) + ( 10) + ( 11) + ( 12) + ( 13)).( 14 This said, we provide now an upper bound for the size of Reformulate(q, db), when q contains a single triple s y o ., s rdf:type z ., s rdf:type c ., or s p o . Assume db = S, D and let #S and #D the sizes (number of triples) of S and D respectively. The triple s y o . can be either s y val . or s y z ., depending whether o is a value or a variable. In the former case, its reformulation scheme is reduced to [(5).( 14) * .((15) + ( 16)).( 17) * ] + [((6) + ( 7) + ( 8)).( 17) * ], while in the latter case its reformulation scheme is that shown in the above table.

As for s y val .,

• reformulating s y val . with (5) leads to 1 triple of the form s rdf:type val ., which can be reformulated at most 2 * #S times by the sequence (14) * .(( 15) + ( 16)).( 17) * , i.e., at most #S times for (14) * .( 15).( 17) * and for (14) * .( 16).( 17) * , as rules ( 14)-( 17) are based on schema-level triples (there is at most #S schema-level triples in db). Summing up, the number of reformulations obtained starting from rule ( 5) is at most: 1 + 2 * #S.

• reformulating s y val . with rule ( 6) leads to at most #D triples of the form s p val . (there is at most #D instance-level triples in db). In turn, those triples can be reformulated at most #S times by the sequence (17) * , as rule ( 17) is based on schema-level triples (there is at most #S schemalevel triples in db). Summing up, the number of reformulations obtained starting from rule (6) is at most: #D * (1 + #S).

• reformulating s y val . with rules ( 7) and ( 8) leads to at most 2 * #S triples of the form s p val . (there is at most #S schema-level triples in db, with at two properties per triple). In turn, those triples can be reformulated at most #S times by the sequence (17) * , as rule ( 17) is based on schema-level triples (there is at most #S schema-level triples in db). Summing up, the number of reformulations obtained starting from rule [START_REF] Broekstra | Inferencing and truth maintenance in RDF Schema: Exploring a naive practical approach[END_REF] or ( 8) is at most: 2 * #S * (1 + #S).

Inria

Summing up, the overall number of reformulations of s y val . is at most:

2 * #S 2 + 5 * #S + #D + 1.
As for s y z .,

• reformulating s y z . with (5) leads to 1 triple of the form s rdf:type z . In turn, that triple can be reformulated using rule (9) in at most #D triples of the form s rdf:type c . (there is at most #D instance-level triples in db). The triple s rdf:type z . can also be reformulated using the rules ( 10)-( 13) in at most 2 * #S triples of the form s rdf:type c . (there is at most #S schema-level triples in db, with at most two classes per triple). Finally, the triples resulting from rules (9)-( 13) can be reformulated at most 2 * #S times by the sequence (14) * .(( 15) + ( 16)).( 17) * , i.e., at most #S times for (14) * .( 15).( 17) * and for (14) * .( 16).( 17) * , as rules ( 14)-( 17) are based on schema-level triples (there is at most #S schema-level triples in db). Summing up, the number of reformulations obtained starting from rule ( 5) is at most:

1 + (#D + 2 * #S) * (1 + 2 * #S).
• reformulating s y z . with rule ( 6) leads to at most #D triples of the form s p z . (there is at most #D instance-level triples in db). In turn, those triples can be reformulated at most #S times by the sequence (17) * , as rule ( 17) is based on schema-level triples (there is at most #S schemalevel triples in db). Summing up, the number of reformulations obtained starting from rule ( 6) is at most: #D * (1 + #S).

• reformulating s y z . with rule [START_REF] Broekstra | Inferencing and truth maintenance in RDF Schema: Exploring a naive practical approach[END_REF] or ( 8) leads to at most 2 * #S triples of the form s p z . (there is at most #S schema-level triples in db, with at two properties per triples). In turn, those triples can be reformulated at most #S times by the sequence (17) * , as rule ( 17) is based on schema-level triples (there is at most #S schema-level triples in db). Summing up, the number of reformulations obtained starting from rule [START_REF] Broekstra | Inferencing and truth maintenance in RDF Schema: Exploring a naive practical approach[END_REF] or ( 8) is at most:

2 * #S * (1 + #S).
Summing up, the overall number of reformulations of s y z . is at most:

6 * #S 2 + 3 * #D * #S + 2 * #D + 4 * #S + 1.
We therefore get that the worst-case number of reformulations for s y o . is actually that of s y z .

By proceeding analogously with the other query triples, we show that the worst-case number of reformulations for a query triple is precisely that of s y z .

That is, for a query q made of a single triple, the overall upper bound for the size of the output of Reformulate(q, db) is:

1 + (6 * #S 2 + 3 * #D * #S + 2 * #D + 4 * #S + 1)
, where the leading 1 accounts for q itself.

The above result easily generalizes to a query of any size #q. Given that #db = #S + #D, the size of the output of Reformulate(q, db) is in O((6 * #db 2 ) #q ). Example 9 (Continued). The reformulation of the query q(x, y):-x rdf:type y . w.r.t. db, asking for all resources and the classes to which they belong, is in Figure 14.

From query reformulation to reformulation-based query answering

A requirement of any reformulation-based query answering technique is that the reformulated queries are equivalent to (or contained in) the original query (w.r.t. the database constraints), otherwise evaluating them might produce erroneous answers. It turns out that our query reformulation technique does not meet this requirement under the previously introduced definitions of evaluation and of answer set of a query against a database, as exemplified below.

Example 10 (Continued). Consider again the database db. For the previous query q(x, y):-x rdf:type y ., the evaluation of the queries in Reformulate(q, db), shown in Figure 14, yields erroneous answers. E.g., the tuple www2012, confP is an erroneous answer (see Example 7 for the correct answers) resulting from the evaluation against db of q(x, confP):-x rdf:type _:b 0 . in Reformulate 2 (q, db), with the assignment µ = {x → www2012, _:b 0 → conference}.

As the above example suggests, the issue is due to blank nodes. The semantics of blank nodes in BGP queries does not match the purpose for which they are brought into query reformulation by the Reformulate algorithm. Remember that the semantics of a blank node in a BGP query against a database is that of a non-distinguished variable. However, when our Reformulate algorithm brings a blank node in a query through a variable binding or a triple replacement, it refers precisely to that particular blank node in the database. In the above example, when q(x, confP):-x rdf:type _:b 0 . in Reformulate 2 (q, db) is produced by rule ( 14) from _:b 0 rdfs:subClassOf confP . ∈ db and q(x, confP):-x rdf:type confP . in Reformulate 2 (q, db), the goal is indeed to find conference paper values for x from the subclass _:b 0 of confP. Non-standard evaluation and answer set of a query against a database. To overcome the above issue, we introduce alternate notions of evaluation and of answer Inria set of a partially instantiated query against a database. The basic difference between the standard definitions from Section 7.1 and the alternate ones concerns blank nodes. Standard evaluation is based on assignments of VarBl(q), all the query's variables and blank nodes, into database values. In contrast, the alternate definition only seeks to assign the query variables; blank nodes are left untouched, like URIs and literals.

Given a database db whose set of values (URIs, blank nodes, literals) is Val(db) and a query q σ (x σ ):-(t 1 , . . . , t α ) σ whose set of variables (no blank nodes) is Var(q σ ), the non-standard evaluation of q σ against db is defined as:

qσ (db) = {(x σ ) µ | µ : Var(q σ ) → Val(db) is a total assignment s.t. ((t 1 , . . . , t α ) σ ) µ ⊆ db}.
The non-standard answer set of q σ against db is obtained by the non-standard evaluation of q σ against db ∝ , which using our notation is denoted qσ (db ∝ ).

The next Property shows how standard and non-standard definitions of query evaluation and answer set of queries are related. It follows directly from the fact that the assignments µ involved in non-standard evaluations, defined on Var(q) only, are a subset of those allowed in standard evaluations, defined on VarBl(q), as non-standard evaluations implicitly assign any URI, blank node, or literal to itself. Property 2. Let db be a database and q σ a (partially instantiated) query against db.

1. qσ (db) ⊆ q σ (db) and qσ (db ∝ ) ⊆ q σ (db ∝ ) hold.

2. If q σ does not contain blank nodes then qσ (db) = q σ (db) and qσ (db ∝ ) = q σ (db ∝ ).

With the above notion of non-standard evaluation in place, our reformulationbased query answering technique is: Theorem 6. Given a BGP query q without blank nodes and a database db, the following holds: q(db ∝ ) = q σ ∈Reformulate(q,db) q σ (db).

Proof of Theorem 6. Let us first show that q(db ∝ ) ⊇ q σ ∈Reformulate(q,db) q σ (db) holds. We actually show that q σ (db ∝ ) ⊆ q(db ∝ ) for any q σ ∈ Reformulate(q, db), since q σ (db) ⊆ q σ (db ∝ ) (1. in Property 2). The proof is by induction on the length l of a sequence of reformulation rules leading to q σ , starting from db, q .

Base step. For l = 0, we have q σ = q and q σ (db ∝ ) = q(db ∝ ), since q is blank node free (2. in Property 2).

Inductive step. For l < α, suppose that q σ (db ∝ ) ⊆ q(db ∝ ) holds. Now at l = α, q σ has been produced from q σ by the application a given rule. In turn, q σ has been produced from q by a sequence of rules starting from db, q . That sequence being of length < α, we get q σ (db ∝ ) ⊆ q(db ∝ ) by the induction hypothesis. We show that q σ (db ∝ ) ⊆ q σ (db ∝ ) to prove our claim. Let xσ be the (partially instantiated) output of q σ and xσ be that of q σ .

• Consider the case where q σ is obtained from q σ by a rule of the form t1∈db,t2∈qσ qσ∪ν that binds a variable of q σ using an assignment ν. Observe

RR n°8018

here that σ = σ ∪ {ν} holds. If (x σ ) µ ∈ q (db ∝ ), then µ ∪ {ν} is a total assignment of the variables of q σ such that (x σ ) µ = (x σ ) µ∪{ν} ∈ q σ (db ∝ ).

• Consider the case where q σ is obtained from q σ by a rule of the form

t1∈db,t2∈qσ q σ[t 2 /t 3 ]
that replaces a triple in q σ by another one. Observe here that σ = σ holds. If (x σ ) µ ∈ q σ (db ∝ ), then (t 3σ ) µ ∈ db ∝ and the immediate entailment rule t 1 , (t 3σ ) µ i RDF (t 2σ ) µ applies. As a result, (t 2σ ) µ ∈ db ∝ and µ is a total assignment of the variables of q σ (that may also assign an extra variable generated by the rule leading from q σ to q σ ) such that

(x σ ) µ = (x σ ) µ ∈ q σ (db ∝ ).
As there is no other form of rule that leads from q σ to q σ , we get q σ (db ∝ ) ⊆ q σ (db ∝ ) which concludes the proof of q(db ∝ ) ⊇ q σ ∈Reformulate(q,db) q σ (db).

Let us show now that q(db ∝ ) ⊆ q σ ∈Reformulate(q,db) q σ (db) holds. We actually show that qσ (db ∝ ) ⊆ q σ ∈Reformulate(q,db) q σ (db) holds with q σ a possibly partially instantiated query, for which q(db ∝ ) ⊆ q σ ∈Reformulate(q,db) q σ (db) is a special case when q σ is not partially instantiated (σ = ∅) and does no contain blank nodes (q(db ∝ ) = q(db ∝ ), 2. in Property 2).

Provided that q σ is of the form q(x σ ):-(t 1 , . . . , t n ) σ , suppose that (x σ ) µ is in qσ (db ∝ ) and let us show that there exists q σ ∈ Reformulate(q, db) such that (x σ ) µ is in q σ (db). We show this by induction on the length l of a (minimal) sequence of immediate entailment rules such that ((t 1 , . . . , t n ) σ ) µ ⊆ db l : for any l there exists a (possibly empty) sequence of reformulation rules leading to q σ , starting from db, q σ . Base step. For l = 0, we have ((t 1 , . . . , t n ) σ ) µ ⊆ db 0 , thus ((t 1 , . . . , t n ) σ ) µ ⊆ db, so for the empty sequence of reformulation rules we have q σ = q σ , and (x σ ) µ is in q σ (db).

Inductive step. For l < α, suppose that the above claim holds. Now at l = α, for 1 ≤ i ≤ n, t iσ matches (t iσ ) µ : it is either (t iσ ) µ or a generalization of (t iσ ) µ using one, two, or three (distinct) variables. Moreover, (t iσ ) µ has been added to the saturation at l ≤ α by an entailment rule of Figure 9. Indeed, the entailment rules of the other Figures do not need to be considered due to Theorem 1.

Consider the case of the rule: s rdfs:subClassOf o ., s 1 rdf:type s . i RDF s 1 rdf:type o . Assume that (t iσ ) µ = v rdf:type c 1 ., i.e., has been produced from {c 2 rdfs:subClassOf c 1 ., v rdf:type c 2 .} ⊆ db α-1 . Observe that v, c 1 , and c 2 can be blank nodes.

• If t iσ = v rdf:type c 1 . then consider the query q σ obtained from q using the reformulation rule [START_REF] Imielinski | Incomplete information in relational databases[END_REF], in which v rdf:type c 1 . is replaced by v rdf:type c 2 . As a result, (x σ ) µ is in q (db α-1 ) and, by the induction hypothesis, there exists a sequence of reformulation rules leading to q σ starting from db, q σ , thus from db, q σ , such that (x σ ) µ is in q σ (db).

• If t iσ = x rdf:type c 1 . then consider the query q σ obtained from q using the reformulation rule [START_REF] Imielinski | Incomplete information in relational databases[END_REF], in which x rdf:type c 1 . is replaced by x rdf:type c 2 . As a result, (x σ ) µ is in q (db α-1 ) and, by the induction hypothesis, there exists a sequence of reformulation rules leading to q σ starting from db, q σ , thus from db, q σ , such that (x σ ) µ is in q σ (db).

Inria

• If t iσ = v rdf:type x . then consider the query q σ obtained from q using the reformulation rules ( 11) then [START_REF] Imielinski | Incomplete information in relational databases[END_REF], in which v rdf:type x . is replaced by x rdf:type c 2 . As a result, (x σ ) µ is in q (db α-1 ) and, by the induction hypothesis, there exists a sequence of reformulation rules leading to q σ starting from db, q σ , thus from db, q σ , such that (x σ ) µ is in q σ (db).

• If t iσ = v x c 1 . then consider the query q σ obtained from q using the reformulation rules ( 5) then ( 14), in which v x c 1 . is replaced by v rdf:type c 2 . As a result, (x σ ) µ is in q (db α-1 ) and, by the induction hypothesis, there exists a sequence of reformulation rules leading to q σ starting from db, q σ , thus from db, q σ , such that (x σ ) µ is in q σ (db).

• If t iσ = x y c 1 . then consider the query q σ obtained from q using the reformulation rules ( 5) then ( 14), in which x y c 1 . is replaced by x rdf:type c 2 . As a result, (x σ ) µ is in q (db α-1 ) and, by the induction hypothesis, there exists a sequence of reformulation rules leading to q σ starting from db, q σ , thus from db, q σ , such that (x σ ) µ is in q σ (db).

• If t iσ = x rdf:type y . then consider the query q σ obtained from q using the reformulation rules ( 11) then ( 14), in which x rdf:type y . is replaced by x rdf:type c 2 . As a result, (x σ ) µ is in q (db α-1 ) and, by the induction hypothesis, there exists a sequence of reformulation rules leading to q σ starting from db, q σ , thus from db, q σ , such that (x σ ) µ is in q σ (db).

• If t iσ = v x y . then consider the query q σ obtained from q using the reformulation rules (5), then [START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF] then [START_REF] Imielinski | Incomplete information in relational databases[END_REF], in which v x y . is replaced by v rdf:type c 2 . As a result, (x σ ) µ is in q (db α-1 ) and, by the induction hypothesis, there exists a sequence of reformulation rules leading to q σ starting from db, q σ , thus from db, q σ , such that (x σ ) µ is in q σ (db).

• If t iσ = x y z . then consider the query q σ obtained from q using the reformulation rules (5), then [START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF] then [START_REF] Imielinski | Incomplete information in relational databases[END_REF], in which x y z . is replaced by x rdf:type c 2 . As a result, (x σ ) µ is in q (db α-1 ) and, by the induction hypothesis, there exists a sequence of reformulation rules leading to q σ starting from db, q σ , thus from db, q σ , such that (x σ ) µ is in q σ (db).

The rest of the proof is omitted here as it amounts to show, similarly as above, that the claim also holds at l = α for the three other entailment rules of Figure 9.

Note that Theorem 6 considers queries without blank nodes. This assumption is made without loss of generality, since blank nodes act as (thus can be equivalently replaced by) non-distinguished variables in BGP queries. We make this simplifying assumption so that at the end of the reformulation step, we do not have two kinds (thus two different treatments in query evaluation) of blank nodes: those coming from the original BGP query (i.e., non-distinguished variables) and those coming from the reformulation step (i.e., values referring to themselves in the database).

At a practical level, Theorem 6 reads as follows: to answer a query q against a database db, it suffices to (i) reformulate q w.r.t. db and (ii) evaluate each reformulated query on the original database db, using the non-standard evaluation. In other words, query reformulation (based on db) and non-standard evaluation of partially instantiated queries allow computing the exact answer set, without actually saturating the database. Importantly, based on Section 3, reformulation-based query answering can be delegated to any RDBMS by storing db in a Triple table, and then by evaluating queries using relational evaluation, without replacing blank nodes by fresh non-distinguished variables.

Example 11 (Continued). Consider again the query q(x, y):-x rdf:type y . The answer set of q against the previous database db is:

qσ∈Reformulate(q,db) qσ (db) = { doi 1 , _:b 0 , www2012, conference , doi 1 , confP , doi 1 , paper , _:b 2 , conference }.
Note that this answer set coincides with that obtained by saturation-based query answering in Example 7.

Experimental evaluation

We implemented our Saturate and Reformulate algorithms in Java 1.6 and deployed them on top of PostgreSQL v8.5 (using standard default settings).

Settings

Instance-level triples are stored in a Triple(s, p, o) table (Section 3). The setbased saturation is stored in a Sat(s, p, o) table, while the multiset-based saturation (allowing maintenance) is stored in a SatM(s, p, o, isDerived, count) table (Section 6). Each table is indexed by all permutations of the (s, p, o) columns, leading to a total of 6 indexes; the spo index is clustering. We adopted this indexing choice (inspired by [START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF]) to give PostgreSQL efficient query evaluation opportunities. Schema-level triples are kept in memory. All measured times are averaged over 10 executions.

We denote t sat the time to saturate a given database by Algorithm Saturate (Section 6.1), and t sat+ the time to saturate it by Algorithm Saturate + (Section 6.2).

Saturation

We evaluated our techniques on the graphs presented in Table 1. Saturation added between 10% and 41% to the database size. The column #Multiset counts: the explicit triples, plus each entailed triple, counted as many times as it is derived (entailed). As "Multiset increase" shows, this more than doubles the size of each graph as entailed triples can be derived in several ways. Table 1 also shows t sat and t sat+ for each graph. As expected, Saturate is (slightly) faster than Saturate + . However, if the graph is updated, one can maintain the saturation only if Saturate + was used, as explained in Section 6.2.

The size of the graphs makes it difficult for a Java program to process the whole data in memory in one pass. Therefore, we propose a partition-based

Inria

Graph

Barton [24] saturation method, which reads the graphs in partitions of a specified number of triples at a time. The positive logic nature of RDFS makes implementing incremental updates close to trivial [START_REF] Gutierrez | The meaning of erasing in RDF under the Katsuno-Mendelzon approach[END_REF]. Our partition-based approach can be seen as consecutive incremental updates made on the saturation table.

The time to saturate each graph using different partition sizes is shown in Figure 15. In the following experiments we will consider the saturation time obtained when reading the data in partitions of 500, 000 triples, values shown in Table 1.

Query answering times

We hand-picked a set of 26 queries for the DBLP graph aiming at a variety of behavior when reformulated against the DBLP schema. The queries have between 1 and 10 triple patterns (6 on average); all have non-empty results. Similarly, we chose 17 queries for the Barton graph and 21 queries for the DBpedia graph. The queries are detailed in Tables 234.

We obtained similar query answering times on the two saturation tables, Sat and SatM, therefore from this point further only the SatM results will be discussed. For a query q, we denote by t sat (q) the time to answer q against the already saturated database SatM, and t ref (q) the time to answer q through reformulation, i.e., reformulating q and evaluating its reformulation against the Triple table.

Figure 16 shows, for each query: the number of union terms in the reformulated query (in parentheses after the query name); the time t sat (q); the time t ref (q); the sum t sat (q) + t sat+ . As expected, t sat (q) is significantly smaller than t ref (q) for queries with large reformulations. However, if one factors in the saturation time t sat+ , the saturation-based approach becomes expensive. Inspecting the results, we also found small-result queries have small t sat and t ref , an encouraging sign that PostgreSQL's optimizer handled correctly both the original and the reformulated queries.

Update performance

We now compare our saturation and reformulation techniques upon graph updates. Updates have no impact on reformulation, but saturation needs to maintain SatM. To measure this overhead, we performed updates on the data, respectively, on the schema, by adding one triple, respectively, removing one triple from each. The target of our update (inserted, respectively, deleted triple) is chosen randomly based on the existing triples in the database: the triple we insert does not belong to the database, while for deletions, we ensure that we delete a triple which was present in the database. Moreover, the triples we added and removed in this experiment each have a distinct property value. As updates on the data, we ran overall 42 insertions and 42 deletions over the DBLP dataset, and 40 of each for the Barton and DBpedia datasets. For what concerns the schema updates, in the DBLP schema, we successively deleted each of the 41 schema triples (the schema was restored between every two deletions). For Barton we performed 26 schema deletions and 39 for DBpedia. The triples we added to the schemas were obtained by picking existing schema triples and slightly modifying them, changing their object value to ensure the added triple was not already in the schema. (2) Q 06 (x, y) :x mods:description y .

(2) Q 07 (x, z) :x rdf:type mods:T ext .,

x mods:language z . (414) Q 08 (y, z) :x rdf:type mods:T ext .,

x y z ., x mods:language language:f re .

(2) Q 09 (x, z) :x rdf:type mods:T ext .,

x role:creator z ., x mods:language language:f re . we list in parenthesis after the added/deleted triple name the triple property: "sp" for rdfs:subPropertyOf, "sc" for rdfs:subClassOf, "domain" for rdfs:domain and "range" for rdfs:range. The last column in each graph is an average over the observed triple insertion times.

(143) Q 10 (x,
The figures demonstrate that despite our careful implementation, index usage etc., the maintenance of SatM when the schema changes is quite expensive; moreover, maintenance in the case of deletions is at least one order of magnitude slower than in the case of insertions. This illustrates the inherent difficulty raised by the recursive process required to analyze the consequences of withdrawing one schema statement. Interestingly, modifying the schema of the DBpedia dataset incurs significantly lower costs than in the case of Barton and DBLP. This is because the DBpedia schema is simpler, in particular it does not feature rdfs:subPropertyOf statements.

The graphs in Figure 19 summarize our findings on the maintenance required by data and schema updates. The graphs show: 3: DBpedia queries and the size of their reformulation.

(9793) Q 01 (x,
• the average time to insert into (resp. delete from) the Triple table (we do not show the detailed times since they were all very similar to each other and thus close to the average, plotted in Figure 19)

• the average time to insert into (resp. delete from) and maintain the SatM table (the same comment applies)

• the average time to maintain the SatM table after an insertion (resp. deletion) made on the schema.

Recall that SatM triples may be simply updated e.g. to increase/decrease a derivation count. We see that handling SatM is slower than updating Triple, by one order of magnitude for instance insertions, and two orders of magnitude for instance deletions. This shows that while the saturation algorithm Saturate +

Inria

36) Q 23 (t, y, j, x) :p elm:creator a 1 ., a 1 f oaf :name "Grzegorz Rozenberg" ., p elm:creator a 2 ., a 2 f oaf :name "Azriel Rosenf eld" ., p elm:title t ., p dblp:year y ., p dblp:pages x ., p dblp:journal j ., p rdf:type dblp:Document . (1) Q 24 (t, y, j, x) :p elm:creator a 1 ., a 1 f oaf :name "Grzegorz Rozenberg" ., p elm:creator a 2 ., a 2 f oaf :name "Azriel Rosenf eld" ., p elm:title t ., p dblp:year y ., p dblp:pages x ., p dblp:journal j ., p rdf:type dblp:Article . (36) Q 25 (t, y, k, p, x):-b elm:creator a 1 ., a 1 f oaf :name "Christopher J. M atheus" ., b elm:creator a 2 ., a 2 f oaf :name "W illiam J. and the SatM table are required in order to avoid saturating from scratch, saturation maintenance may get costly due to the recursive nature of entailment. In particular, in the case of schema updates, maintaining the saturation may sometimes be more costly than re-saturating.

Saturation thresholds

We now study when saturation pays off over multiple query runs. We call the saturation threshold of a query q, or st(q), the smallest integer n such that: In other words, n is the minimum number of times one needs to run q in order for the whole saturation cost to amortize.

n × t ref (q) > n × t sat (q) + t sat+
Similarly, we study how many times q should run in order for the maintenance overhead due to one instance or schema update to pay off. We formalize this as follows. Let t + Triple be the time to insert one statement in Triple, and t + SatM be the time to propagate the insertion of one triple to the SatM relation. Then, the saturation threshold for an instance insertion, denoted st + i (q), is the smallest n for which: n × t ref (q) + t + Triple > n × t sat (q) + t + SatM . In other words, st + i (q) is the minimum number of times one needs to run q in order for the maintenance overhead due to the insertion of one triple (recall the graphs in Figure 19) to amortize. We similarly define the saturation threshold for an instance deletion, denoted st - i (q), as the smallest n for which: n × t ref (q) + t - Triple > n × t sat (q) + t - SatM . Schema updates do not affect the Triple table, since the schema is kept in memory, but they can have a big impact on SatM. Similar to st(q), we define the saturation threshold for a schema insertion st + s (q) and deletion st - s (q), as the minimum number of times one needs to run q in order for the schema update cost to amortize.

Figure 20 shows the 5 saturation thresholds for our queries. The vertical (log-scale) axis is limited to 10 5 (Barton) and 10 4 (DBpedia and DBLP) for readability. The thresholds follow a similar trend, strongly determined by the size of the reformulated query (shown in parentheses on the x axis). The larger the reformulated query, the lower the threshold: saturation pays off faster when reformulation is expensive, and this tends to happen when the queries are syntactically complex. We see that st(q) varies from 1 (Q 13 ) to more than 10 4 (Q 09 ) on the Barton dataset, with similar results for the DBpedia and DBLP graphs. For queries such as Q 04 (Barton), Q 09 (DBpedia), Q 04 (DBLP) etc., which are not affected by reformulation, the saturation cost can never be compensated. st is always higher than the update thresholds, which is normal since st runs offset the complete saturation cost, whereas st + i , st - i , st + s and st - s need to offset the cost of maintaining saturation for just one triple added or deleted. Finally, st + i is lower than st - i , and st + s is lower than st - s , meaning that saturation costs particularly penalize scenarios where deletions are frequent.

Conclusion of the experiments

Our experiments have shown that Saturate and Reformulate can be used to process BGP queries efficiently by exploiting an off-the-shelf RDBMS. However, they perform very differently depending on the query selectivity and the impact of the schema through reasoning: saturation is best for large-reformulation queries, while reformulation is efficient for small-to-moderate reformulation. With respect to updates, we have shown that saturation can be maintained at a reasonable cost for instance-level updates, while schema-level updates are much more expensive. Updates, however, have a small impact on reformulation making it appropriate for high update rates. When considering also repeated query runs, we have highlighted a number of thresholds determining when saturation pays off; these thresholds are strongly impacted by the query reformulation size and selectivity. While saturation is the default in many RDF platforms, our experiments demonstrate the practical interest of reformulation-based BGP query answering.

Related work

Many well-known SPARQL compliant RDF management systems, e.g., 3store

[23], Jena [26], OWLIM [27], Sesame [28], or Virtuoso [29], or research prototypes, e.g., Hexastore [START_REF] Weiss | Hexastore: sextuple indexing for Semantic Web data management[END_REF] or RDF-3X [START_REF] Neumann | x-RDF-3X: Fast querying, high update rates, and consistency for RDF databases[END_REF], either (i) ignore entailed triples or (ii) provide saturation-based query answering, based on (a subset of) RDF entailment rules.

The drawbacks of saturation w.r.t. updates have been pointed out in [START_REF] Broekstra | Inferencing and truth maintenance in RDF Schema: Exploring a naive practical approach[END_REF], which proposes a truth maintenance technique implemented in Sesame. It relies on the storage and management of the justifications of entailed triples (which triples beget them). While efficient on graphs with few entailed triples, the technique is pegged by the high overhead of handling justifications when their number and size grow. Therefore, [START_REF] Bishop | OWLIM: A family of scalable semantic repositories[END_REF] proposes to compute only the relevant justifications w.r.t. an update, at maintenance time. This technique is implemented in OWLIM, however [27] points out that schema-level deletions can lead to poor performance. In contrast, our saturation maintenance technique (Section 6.2) is based on the number of times triples are entailed; this is easier to store and manipulate. Our technique performs well for instance updates, while it has various behavior for schema updates. On average, it is worth maintaining the saturation, though in some cases it may be more costly than re-saturating (up to five times in our experiments). A distinct yet related problem studied in [START_REF] Gutierrez | RDFS update: From theory to practice[END_REF] is finding which triples to delete from a graph, so that an implicit triple no longer holds.

Reformulation-based query answering has been investigated in RDF fragments ranging from the Description Logic (DL) [START_REF] Baader | The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] one [START_REF] Adjiman | SomeRDFS in the semantic web[END_REF][START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF][START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF], i.e., modeling simple DL knowledge bases, to a slight extension thereof allowing values to be used both as constants and classes/properties [START_REF] Arenas | Foundations of RDF databases[END_REF][START_REF] Goasdoué | View selection in semantic web databases[END_REF][START_REF] Kaoudi | RDFS reasoning and query answering on DHTs[END_REF][START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF]. These two fragments of RDF impose restrictions on triples (no blank nodes) and on entailment (only the RDFS entailment rules are considered). Our DB fragment is strictly more expressive since it supports blank nodes.

Reformulation-based query answering in the DL fragment of RDF has been investigated for relational conjunctive queries [START_REF] Adjiman | SomeRDFS in the semantic web[END_REF][START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF][START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF], while the slight extension thereof considered in [START_REF] Arenas | Foundations of RDF databases[END_REF][START_REF] Goasdoué | View selection in semantic web databases[END_REF][START_REF] Kaoudi | RDFS reasoning and query answering on DHTs[END_REF][START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF] has been investigated for one-triple BGP queries [START_REF] Kaoudi | RDFS reasoning and query answering on DHTs[END_REF][START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF], BGP queries [START_REF] Goasdoué | View selection in semantic web databases[END_REF], and SPARQL queries [START_REF] Arenas | Foundations of RDF databases[END_REF]. Relational conjunctive queries are strictly less expressive than BGP queries, since the former only allow triples of the form s rdf:type c . and s p o ., ruling out the possibility to put variables in place of classes or properties.

The query reformulation algorithms of [START_REF] Adjiman | SomeRDFS in the semantic web[END_REF][START_REF] Goasdoué | View selection in semantic web databases[END_REF] are restrictions of our Reformulate. The same holds for the algorithms in [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF][START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF] when restricted to the DL fragment of RDF, whereas they are capable of handling complex DLs. Algorithms in [START_REF] Adjiman | SomeRDFS in the semantic web[END_REF][START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF][START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF] consider only our rules ( 14)-( 17) to reformulate relational conjunctive queries, while the algorithm in [START_REF] Goasdoué | View selection in semantic web databases[END_REF] needs two additional rules for BGP queries. These two rules actually correspond to our rules Inria (5)-( 13), under the simplifying assumption that part of the information needed for reformulation have been pre-computed. In [START_REF] Kaoudi | RDFS reasoning and query answering on DHTs[END_REF][START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF], atomic BGP queries are reformulated using a standard backward-chaining algorithm [START_REF] Russell | Artificial Intelligence -A Modern Approach[END_REF] on first order encodings of the entailment rules dedicated to RDFS. In [START_REF] Arenas | Foundations of RDF databases[END_REF], SPARQL queries are reformulated into nested SPARQL, i.e., an extension of SPARQL in which properties in triples can be nested regular expressions. While such nested reformulated queries are more compact, the queries we produce are more practical, since their evaluation can be directly delegated to any off-the-shelf RDBMS, or to an RDF engine such as RDF-3X [START_REF] Neumann | x-RDF-3X: Fast querying, high update rates, and consistency for RDF databases[END_REF] even if it is unaware of reasoning.

Conclusion

In this paper, we have extended the state of the art in BGP query answering against RDF graphs with updates. We have devised novel saturation-and reformulation-based query answering techniques robust to instance and schema updates, for an RDF fragment extending those known in the literature; we compared thoroughly their performance and identified the factors impacting the comparison. Notably, our techniques can be directly deployed on top of any off-the-shelf RDBMS. An automated strategy to chose between the two techniques is part of our future work.

Figure 1 :

 1 Figure 1: Outline of the positioning of our work.

Figure 2 := doi 1 _:b 0 "

 210 Figure 2: RDF statements.

Figure 3 :

 3 Figure 3: Alternative RDF graph representations.

Figure 5 :

 5 Figure 5: Extended RDF graph for Example 2.

Inria

Figure 6 :

 6 Figure 6: Schema-level entailment from a single schema-level triple.

Figure 9 :

 9 Figure 9: Instance-level entailment from combining schema and instance triples.

Figure 11 :

 11 Figure 11: Sample saturation of a database db.

( 4 )

 4 * .((2) + (3)).(1) * This said, we provide now an upper bound for the size of Saturate(db), when db contains the single instance-level triple s rdf:type o . or s p o . Assume db = S, D and let #S and #D the sizes (number of triples) of S and D respectively.

  ) * .((15)+ 16)).(17) * s rdf:type c . (14) * .((15) + (16)).(17) * s p o . (17) *

Figure 14 :

 14 Figure14: Sample reformulation of a query q w.r.t. the database of our running example.

Figure 15 :

 15 Figure 15: Saturation times.

  Figures 17 and 18 show the time to insert into, respectively delete from, and maintain SatM for each of the considered schema triples. Under each time bar, Inria (143) Q 01 (x, y) :x rdf:type y . (46) Q 02 (x) :x rdf:type mods:Item . (12) Q 03 (x) :x rdf:type mods:N ame . (1) Q 04 (x) :x rdf:type mods:T ext . (2) Q 05 (x, y) :x mods:language y .

  (n, t, k, p, x):-b elm:creator a ., a f oaf :name n ., b elm:title t ., b dblp:year "1991" ., b dblp:pages x ., b dblp:booktitle k ., b elm:publisher p ., b rdf:type dblp:Document . (36) Q 20 (t, y, p, x) :b elm:creator a ., a f oaf :name "W illiam J. F rawley" ., b elm:title t ., b dblp:year y ., b dblp:pages x ., b dblp:booktitle "Knowledge Discovery in Databases" ., b elm:publisher p ., b rdf:type dblp:Document . (1) Q 21 (n, t, k, p, x):-b elm:creator a ., a f oaf :name n ., b elm:title t ., b dblp:year "1991" ., b dblp:pages x ., b dblp:booktitle k ., b elm:publisher p ., b rdf:type dblp:Book . (1) Q 22 (t, y, p, x) :b elm:creator a ., a f oaf :name "W illiam J. F rawley" ., b elm:title t ., b dblp:year y ., b dblp:pages x ., b dblp:booktitle "Knowledge Discovery in Databases" ., b elm:publisher p ., b rdf:type dblp:Book .

  F rawley" ., b elm:title t ., b dblp:year y ., b dblp:pages x ., b dblp:booktitle k ., b elm:publisher p ., b rdf:type dblp:Document . (1) Q 26 (t, y, k, p, x):-b elm:creator a 1 ., a 1 f oaf :name "Christopher J. M atheus" ., b elm:creator a 2 ., a 2 f oaf :name "W illiam J. F rawley" ., b elm:title t ., b dblp:year y ., b dblp:pages x ., b dblp:booktitle k ., b elm:publisher p ., b rdf:type dblp:Book . elm http://purl.org/dc/elements/1.1/ f oaf http://xmlns.com/foaf/0.1/ dblp http://sw.deri.org/ aharth/2004/07/dblp/dblp.owl#Table 4: DBLP queries and the size of their reformulation. on saturation Query answering based on reformulation Query answering based on saturation with time to saturate DBpedia dataset answering based on saturation Query answering based on reformulation Query answering based on saturation with time to saturate Time (seconds) on saturation Query answering based on reformulation Query answering based on saturation with time to saturate Time (seconds)

Figure 16 :

 16 Figure 16: Query answering times.

Figure 17 :

 17 Figure 17: Schema triple insertion times.

Figure 18 :

 18 Figure 18: Schema triple deletion times.

Figure 19 :

 19 Figure 19: Update times.

Figure 20 :

 20 Figure 20: Saturation thresholds.

rdfs:subClassOf s 2 ., s rdf:type s 1 . s rdf:type s 2 . p 1 rdfs:subPropertyOf

  ., s 1 rdfs:subClassOf s 2 . s rdfs:subClassOf s 2 . p rdfs:subPropertyOf p 1 ., p 1 rdfs:subPropertyOf p 2 . p rdfs:subPropertyOf p 2 . p rdfs:domain s 1 ., s 1 rdfs:subClassOf s . p 2 ., s p 1 o . s p 2 o . p rdfs:domain s ., s 1 p o 1 . s 1 rdf:type s . p rdfs:range s ., s 1 p o 1 .

	Triple	Entailed triple ( i RDF )
	s rdf:type o . o rdfs:subClassOf o .
	s p o .	p rdfs:subPropertyOf p .
	Figure 7: Schema-level entailment from a single instance-level triple.
	Triples		Entailed triple ( i RDF )
	s rdfs:subClassOf s 1 p rdfs:domain s .
	p rdfs:range s 1 ., s 1 rdfs:subClassOf s .	p rdfs:range s .
	p rdfs:subPropertyOf p 1 ., p 1 rdfs:domain s .	p rdfs:domain s .
	p rdfs:subPropertyOf p 1 ., p 1 rdfs:range s .	p rdfs:range s .
	Figure 8: Schema-level entailment from two schema triples.
	Triples		Entailed triple ( i RDF )
	s 1

o 1 rdf:type s .

  4] s.t. applying rule (i) on some {t 1 , t 2 } ⊆ Saturate k + (db) produces t 3 with t 2 ∈ Saturate j<k + (db)} The following Property exhibits the obvious relationship between the setbased saturation and the multiset-based saturation of a database; set is the function giving the set of elements occurring in a given multiset. where the multiset D is {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on {t, t 2 } with t 2 ∈ Saturate + (db) yields t 3 }, if t is a schema-level triple.

	Saturate 0 + (db) = db Saturate 1 + (db) = Saturate 0 + (db)
	{doi 1 rdf:type confP .,
	doi 1 rdf:type paper .,
	doi 1 rdf:type paper .,
	doi 1 hasAuthor _:b 1 .,
	doi 1 rdf:type confP .,
	_:b 2 rdf:type conference .,
	_:b 2 rdf:type conference .}
	Saturate 2 + (db) = Saturate 1 + (db)
	{doi 1 rdf:type paper .
	doi 1 rdf:type paper .,
	doi 1 rdf:type paper .}
	Saturate 3 + (db) = Saturate 2

Property 1. Saturate(db) = set(Saturate + (db)) holds for any RDF database db. + (db) Figure 12: Sample multiset-based saturation. Example 6 (Continued). Consider again the previously introduced database db. Its multiset-based saturation is shown in Figure 12.

With the multiset-based saturation and Property 1 in place, Theorem 3 shows how saturation can be maintained upon update; \ + is the difference operator for multisets. Theorem 3. Let db = S, D be a database. Insertion: Saturate + (db ∪ {t}) = • Saturate + (db) if t ∈ db, otherwise, t ∈ db and • Saturate + (db) [Saturate + ( S, {t} ) \ + S] if t is an instance-level triple; • Saturate + (db) {t} t ∈D [Saturate + ( S, {t } )\ + S], Deletion: Saturate +

  The proof is by induction on the number k of saturation steps:

	Saturate k + ( S, D 1 D 2 ) = Saturate k + ( S, D 1 ) [Saturate k + ( S, D 2 )\ + S].
	Base step: By definition Saturate 0 + ( S, D 1 Saturate 0 + ( S, D 1 ) [Saturate 0 + ( S, D 2 )	D 2 ) = S, D 1	D 2 and

1. db is a set of triples and t ∈ db, so we have db ∪ {t} = db, thus Saturate + (db ∪ {t}) = Saturate + (db). 2. Given that t ∈ db and t is an instance-level triple, Saturate + (db ∪ {t}) = Saturate + (db) [Saturate + ( S, {t} ) \ + S] is proved by showing the more general result: Saturate + ( S, D 1 D 2 ) = Saturate + ( S, D 1 ) [Saturate + ( S, D 2 )\ + S]. Indeed, observe that Saturate + (db∪{t}) = Saturate + ( S, D {t}), since Inria t ∈ db.

  \ + S], where the multiset D is {t 3 | ∃i ∈[START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF][START_REF] Arenas | Foundations of RDF databases[END_REF] such that applying rule (i) on {t, t 2 } with t 2 ∈ Saturate + (db) yields t 3 }. We actually show this by induction on the number k of saturation steps: Saturate

4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + ( S, D 1 D 2 ) yields t 3 with t 2 ∈ Saturate j<α-1 + ( S, D 1 D 2 )} holds. Therefore, Saturate α + ( S, D 1 ) [Saturate α + ( S, D 2 ) \ + S] = Saturate α + ( S, D 1 D 2 ) holds. 3. Given that t ∈ db and t is a schema-level triple, we prove that Saturate + (db∪{t}) = Saturate + (db) {t} t ∈D [Saturate + ( S, {t } )

  such that applying rule (i) on {t, t 2 } yields t 3 with t 2 ∈ Saturate l-1 + (db) and t 2 ∈ Saturate j<l-1

	for l > 0. Indeed, observe that, by definition, D =	(db)} l=0 D l , i.e., whenever + ∞
	the saturation fixpoint is reached.
	Base step: By definition, Saturate 0 + (db ∪ {t}) = db ∪ {t} holds. In turn,
	by definition, Saturate 0 + (db) {t}

  4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + (db∪{t}) yields t 3 with t 2 ∈ Saturate j<α-1Let us now consider the three cases for deletions. 1. db is a set of triples and t ∈ db, so we have db \ {t} = db, thus Saturate Base step: By definition Saturate 0 + (db\{t}) = db\{t} and Saturate 0 + (db) \ + [Saturate 0 + ( S, {t} ) \ + S] = db \ + [ S, {t} \ + S] = db \ + {t} = db \ {t} since t ∈ db, thus Saturate 0 + (db \ {t}) = Saturate 0 + (db) \ + [Saturate 0 + ( S, {t} ) \ + S] holds. Inductive step: Suppose that Saturate k + (db \ {t}) = Saturate k + (db)\ + [Saturate k + ( S, {t} ) \ + S] for k < α and let us show that it still holds for k = α.

	{t}	α l=0 t l ∈D l	+ [Saturate α-l (db ∪ {t})} holds. Therefore, Saturate α + (db)
	By definition, Saturate α + (db) \ + [Saturate α + ( S, {t} ) \ + S]	=
	(Saturate α-1

+ ( S, {t l } ) \ + S] = Saturate α + (db ∪ {t}) holds. + (db \ {t}) = Saturate + (db). 2. Given that t ∈ db and t is an instance-level triple, Saturate + (db \ {t}) = Saturate + (db)\ + [Saturate + ( S, {t} ) \ + S] is shown on the number k of saturation steps: Saturate k + (db \ {t}) = Saturate k + (db)\ + [Saturate k + ( S, {t} ) \ + S]. + (db) {t 3 | ∃i ∈ [1, 4] such that applying rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + (db) yields t 3 with t 2 ∈ Saturate j<α-1

Table 1 :

 1 Graph characteristics; time to saturate.

	DBpedia [25]	DBLP [9]

Table 2 :

 2 Barton queries and the size of their reformulation.

  Q 10 (t, n, m) :x rdf:type dblp:Document ., x dblp:editor y ., x elm:creator z ., y f oaf :name n ., z f oaf :name m ., x elm:title t ., x dblp:objectF ield u . (36) Q 11 (t, y, j, x) :p elm:creator a ., a f oaf :name "Alison Cawsey" ., p elm:title t ., p dblp:year y ., p dblp:pages x ., p dblp:journal j ., p rdf:type dblp:Document . (36) Q 12 (t, y, x)

	(121) Q 01 (x, y, z)	:-x y z .
	(684) Q 02 (x, y)	:-x rdf:type dblp:Document ., x dblp:datatypeF ield y .
	(36) Q 03 (x)	:-x rdf:type dblp:Document ., x elm:publisher "Springer" .
	(1) Q 04 (x)	:-x rdf:type dblp:Book ., x elm:publisher "Springer" .
	(1) Q 05 (y, z)	:-x rdf:type f oaf :P erson ., x f oaf :name y ., x f oaf :homepage z .
	(19) Q 06 (y, u, t)	:-x dblp:datatypeF ield "Algorithmica" ., x elm:title y ., x elm:creator u .,
		x elm:date t .
	(4) Q 07 (y, u, t)	:-x dblp:objectF ield "Algorithmica" ., x elm:title y ., x elm:creator u .,
		x elm:date t .
	(19) Q 08 (u, z)	:-x dblp:editor y ., y f oaf :name z ., x elm:title u ., x dblp:datatypeF ield v .,
		x elm:publisher "Springer" .
	(4) Q 09 (u, z)	:-x dblp:editor y ., y f oaf :name z ., x elm:title u ., x dblp:objectF ield v .,
		x elm:publisher "Springer" .
	(138)

:p elm:creator a ., a f oaf :name "Hugh Darwen" ., p elm:title t ., p dblp:year y ., p dblp:pages x ., p dblp:journal "SIGM OD Record" ., p rdf:type dblp:Document . (36) Q 13 (t, j, x) :p elm:creator a ., a f oaf :name "Dana Randall" ., p elm:title t ., p dblp:year "2006" ., p dblp:pages x ., p dblp:journal j ., p rdf:type dblp:Document . (36) Q 14 (n, t, x) :p elm:creator a ., a f oaf :name n ., p elm:title t ., p dblp:year "1966" ., p dblp:pages x ., p dblp:journal "Inf ormation and Control" ., p rdf:type dblp:Document . (1) Q 15 (t, y, j, x) :p elm:creator a ., a f oaf :name "Alison Cawsey" ., p elm:title t ., p dblp:year y ., p dblp:pages x ., p dblp:journal j ., p rdf:type dblp:Article . (1) Q 16 (t, y, x) :p elm:creator a ., a f oaf :name "Hugh Darwen" ., p elm:title t ., p dblp:year y ., p dblp:pages x ., p dblp:journal "SIGM OD Record" ., p rdf:type dblp:Article . (1) Q 17 (t, j, x) :p elm:creator a ., a f oaf :name "Dana Randall" ., p elm:title t ., p dblp:year "2006" ., p dblp:pages x ., p dblp:journal j ., p rdf:type dblp:Article . (1) Q 18 (n, t, x) :p elm:creator a ., a f oaf :name n ., p elm:title t ., p dblp:year "1966" ., p dblp:pages x ., p dblp:journal "Inf ormation and Control" ., p rdf:type dblp:Article . (36) Q 19

RR n°8018

rule (i) on some {t 1 , t 2 } ⊆ Saturate α-1 + ( S, {t} ) yields t 3 with t 2 ∈ Saturate j<α-1 + ( S, {t} )}) \ + S] holds.

By the semantics of the and \ + operators, and since Saturate α-1 + ( S, {t} )

), where the multiset D l is ∅ for l = 0 and {t 3 | ∃i ∈ [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF][START_REF] Arenas | Foundations of RDF databases[END_REF] such that applying rule (i) on {t, t 2 } yields t 3 with t 2 ∈ Saturate l-1 + (db) and t 2 ∈ Saturate j<l-1 + (db)} for l > 0. Indeed, observe that, by definition, D = ∞ l=0 D l , i.e., whenever the saturation fixpoint is reached.

Base step: By definition, Saturate 0 + (db\{t}) = db∪{t} holds. In turn, by definition, (Saturate 0 + (db)\ + {t})\ + (