Matthieu Perrin

Achour Mostefaoui

Patricia Serrano Alvarado

Pierre

Lenny

Kevin Théo

Sometimes scientists change their minds. New developments cause a rethink. If this bothers you, consider how much damage is being done to the world by people for whom new developments do not cause a rethink.

Chapter 1 Introduction

Motivation

The original Web of documents [START_REF] Berners-Lee | World-wide web: The information universe[END_REF] is based on three key pillars. The first is the Unique Resource Identifier (URI) which associates each resource on the Web to unique identifiers. The most common form of an URI is a Uniform Resource Locator (URL), e.g., https://www.univ-nantes.fr is the URL of the welcome page of the University of Nantes website. The second pillar is the Hypertext Transfer Protocol (HTTP), which allows accessing a URL, and either the document identified by the URI, or an error code. For example, the famous 404 error code indicates that the requested resource does not exist. The third and final fundamental notion is the Hypertext Markup Language (HTML), a hypertext format used to describe the content of web pages.

However, conventional HTML documents are not expressive enough to unambiguously describe entities and their properties across the World Wide Web [START_REF] Bizer | Linked Data -The Story So Far[END_REF]. To this end, the Semantic Web [START_REF] Berners-Lee | The semantic web[END_REF] extends the classic Web of documents to create a Web of Data, where text documents are replaced by structured data that can be automatically processed by computers. It re-uses the first two fundamental notions (URLs and the HTTP protocol) from the Web of documents, but replaces the use of HTML documents by Resource Description Framework (RDF) documents [START_REF] Cyganiak | RDF 1.1 concepts and abstract syntax[END_REF]. The core structure of the RDF data model [START_REF] Cyganiak | RDF 1.1 concepts and abstract syntax[END_REF] is a set of RDF triples. A triple is composed of a subject, a predicate, and an object, and asserts facts about entites. Figure 1.1 shows some RDF triples extracted from DBpedia that asserts facts about the entity Neil Gaiman [START_REF] Wagner | Prince of Stories: The Many Worlds of Neil Gaiman[END_REF]: he is an author, he is named "Neil Gaiman" and he wrote the books Amercian Gods and Good Omens.

Tim Berners-Lee [START_REF] Berners-Lee | Linked data-design issues[END_REF] proposed four principles to publish RDF documents so that they become part of a single global data space: the Linked Open Data (LOD). These principles are as follows:

1. Introduction @prefix foaf: <http://xmlns.com/foaf/0.1/> @prefix dbo: <http://dbpedia.org/ontology/> @prefix dbr: <http://dbpedia.org/resource/> @prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> @prefix wikidata: <https://www.wikidata.org/entity/Q210059> dbr:Neil_Gaiman rdf:type dbo:Person . dbr:Neil_Gaiman foaf:name "Neil Gaiman" . dbr:Neil_Gaiman owl:sameAs wikidata:Q210059 . dbr:American_Gods dbo:author dbr:Neil_Gaiman . dbr:Good_Omens dbo:author dbr:Neil_Gaiman . PREFIX foaf: <http://xmlns.com/foaf/0.1/> PREFIX dbo: <http://dbpedia.org/ontology/> PREFIX dbr: <http://dbpedia.org/resource/> PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> SELECT ?author ?book WHERE { ?author rdf:type dbo:Person . ?author foaf:name ?name . ?book dbo:author ?author . } actors and their movies, you need to crawl the LOD to download every document that contains relevant informations, which is very costly considering the current size of the LOD. Alternatively, a collection of RDF documents can be hosted in a dedicated database and exposed using a SPARQL endpoint. A SPARQL endpoint follows the SPARQL protocol 4 , which "describes a means for conveying SPARQL queries and updates to a SPARQL processing service and returning the results via HTTP to the entity that requested them". Hence, users can send SPARQL queries to the endpoint, which are SQL-like queries that allow users to query RDF documents with an expressive query language. For example, the DBpedia SPARQL endpoint 5 enables data consumers to execute queries on the DBpedia dataset, composed of billions of facts retrieved from Wikipedia [START_REF] Auer | DBpedia: A Nucleus for a Web of Open Data[END_REF]. Figure 1.3 shows a SPARQL query that finds all authors and their books in the DBpedia dataset.

Formally, the SPARQL protocol defines a SPARQL query execution model with two actors: 1) A client (a human or a software) which wants to execute a SPARQL query. 2) A SPARQL endpoint, which is an HTTP server that evaluates SPARQL queries over an RDF dataset. To execute a SPARQL query, a web client sends a SPARQL query to the server through an HTTP GET or POST request. The SPARQL endpoint will evaluate it against a default RDF Graph, whose URI is set by the client, and then returns the SPARQL query results to the client.

Public SPARQL query servers, like SPARQL endpoints, are very important for the Web of Data, as they enable Web developers to write applications that re-use the billions of RDF triples available in the LOD cloud. For example, both the DBpedia [START_REF] Auer | DBpedia: A Nucleus for a Web of Open Data[END_REF] and Wikidata [START_REF] Vrandecic | Wikidata: a free collaborative knowledgebase[END_REF] SPARQL endpoints are used as backends by multilingual question answering platforms [START_REF] Diefenbach | QAnswer: A Question Answering prototype bridging the gap between a considerable part of the LOD cloud and end-users[END_REF][START_REF] Tanon | Demoing Platypus -A Multilingual Question Answering Platform for Wikidata[END_REF] and chatbots [START_REF] Athreya | Enhancing Community Interactions with Data-Driven Chatbots-The DBpedia Chatbot[END_REF]. However, providing a public service that allows anyone to execute any SPARQL query at any time is still an open issue [START_REF] Aranda | SPARQL Web-Querying Infrastructure: Ready for Action?[END_REF]. As public SPARQL query services can suffer from an unpredictable load of arbitrary SPARQL queries, the challenge is to ensure that the service remains available despite variation in terms of the arrival rate of requests and resources required to process queries. Providers often refer to this challenge as "maintaining a fair usage policy".

To achieve a fair usage policy, most SPARQL endpoints configure quotas on their servers to prevent the convoy effect and ensure a fair sharing of resources among end-users. If a SPARQL query exceeds one of these quotas, the server rejects it, and the web client receives an error. There exists many type of quotas, almost one set per data provider. Most commonly, data providers restrict: 1) The execution time of SPARQL queries, 2) The number of results sent per query, and 3) The arrival rate of queries per IP. For example, the DBpedia SPARQL endpoint does not allow queries to run for more than 120 seconds or return more than 10000 results 6 . Additionally, it only allows 50 parallel connections and 100 HTTP requests per second per IP address. The Wikidata SPARQL endpoint enforces even harder limitations, as it restricts SPARQL query execution time to 60 seconds with only one connection allowed per IP address 7 .

Some of these quotas are not disturbing for web clients, e.g., if the arrival rate is restricted, then clients only need to try again later. However, limiting the execution time of SPARQL queries causes some queries to deliver only partial results. To illustrate, consider the execution of the SPARQL query of Figure 1.3. When executed with a local SPARQL endpoint without any quotas nor limitations, the total number of results for this query is 35 215. However, when executed against the public DBpedia SPARQL endpoint, we found only 10 000 results out of 35 215 8 , because the query exceeded the maximum number of results to send per query. Delivering partial results is a severe limitation for a public SPARQL service, as it prevents users from building Web applications based on SPARQL endpoints, especially in the domain of Life Sciences [START_REF] Polleres | A More Decentralized Vision for Linked Data[END_REF].

However, without a quota policy, SPARQL endpoints can suffer from convoy effect [START_REF] Blasgen | The Convoy Phenomenon[END_REF], because they execute queries using a First-Come First-Served (FCFS) execution policy [START_REF] Fife | R68-47 Computer Scheduling Methods and Their Countermeasures[END_REF]: queries are executed in their order of arrival at the endpoint. Thus, one long-running query can occupy the server resources and prevents others from executing. Convoy effects can severely deteriorate query execution performance in terms of 1) average waiting time: the average time spent by queries in the server's waiting queue, 2) average time for first results: the average time between sending the query and receiving the first bytes of query results, and 3) average query completion time: the average time between sending the query to the server and receiving the last bytes of query results.

In the current state of the LOD, we face a dilemma. On one hand, we can build a responsive public SPARQL query server using a quota policy, but it can provide incomplete results. On the other hand, we can build a server that always delivers complete results, but can become unresponsive due to convoy effects. Neither solution is suitable for developping Web applications over the Web of data, as web developers need responsive SPARQL query servers that always deliver complete results.

Research outline and contributions

In this thesis, we choose to tackle the issue of building public SPARQL query servers that allow any data consumer to execute any SPARQL query with complete results. Existing approaches address this issue by decomposing SPARQL queries into subqueries that can be run under the quotas and produce complete results [7]. Finding such decomposition is hard in the general case, as quotas can be different from one server to another, both in terms of values and nature [7]. The Linked Data Fragments (LDF) approach [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF][START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF] tackles this issue by restricting the SPARQL operators supported by the server. For example, in the Triple Pattern Fragments (TPF) approach [START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF], a TPF server only evaluates triple patterns. However, current LDF approaches produce a large number of subqueries and substantial data transfer.

In this work, we choose to follow a different path from the state of the art, as we believe that the issue related to quotas is not interrupting a query but the impossibility for the client to resume the query execution afterward. In consequence, we propose Web Preemption, a new execution model for public SPARQL query servers, inspired by the works on time-sharing [START_REF] Anderson | Operating Systems: Principles and Practice[END_REF]. Web preemption is the capacity of a Web server to suspend a running query after a time quantum with the intention to resume it later. When suspended, the state S i of the query is returned to the Web client. Then, the client can resume query execution by sending S i back to the Web server. Compared to existing query execution models, Web Preemption ensures a fair allocation of Web server resources across queries, a better average query completion time per query, and a better time for first results.

However, our new model adds an overhead for the Web server to suspend the running query and resume the next waiting query. Consequently, the next scientific challenge here is to keep this overhead marginal, whatever the running SPARQL queries, to ensure top query execution performance. At this end, we propose SaGe, a preemptive SPARQL query engine that implements the Web Preemption model. We define a set of preemptable query operators for which 1.3. Thesis overview we bound the complexity of suspending and resuming of these operations, both in time and space. They allow us to build a preemptive Web server that supports a large fragment of the SPARQL query language. As not all SPARQL operations exhibit a low preemption overhead, we split the SaGe query engine into two components. First, a SaGe SPARQL query server uses our set of preemptable operators for executing a large fragment of the SPARQL query language under the Web Preemption model. Second, a SaGe Smart Web Client, executes the remaining SPARQL operations client-side and applies optimizations to reduce the data transfer. By combining the two components, we allow any user to evaluate any SPARQL 1.1 query under the Web Preemption model.

Finally, we provide a complete experimental study of the SaGe SPARQL query engine, client and server, compared to existing approaches used for hosting public SPARQL services. Experimental results demonstrate that SaGe outperforms existing approaches by several orders of magnitude in terms of the average total query execution time and the time for the first results.

Thesis overview

This thesis is constructed as follows.

Chapter 2 presents the background notions and the related work of this thesis. It provides background on the RDF data model, the formal semantics of the SPARQL query language, the main techniques for storing RDF data and the various methods for processing SPARQL query over RDF datasets hosted in a centralized database. It also provides related work on convoy effects, quotas policy and techniques to circumvent them.

Chapter 3 presents and motivates the Web preemption model, our first contribution of this thesis. It formalizes the Web Preemption model and presents the challenge related to its implementation.

Chapter 4 presents the SaGe preemptive SPARQL query engine, our second contribution of this thesis. It defines a set of preemptable physical SPARQL operators, used to evaluate SPARQL queries under the Web Preemption model. For each preemptable operator, we prove its space and time complexity. We also introduce the SaGe Smart Web Client, which comes with its own set of challenges regarding query performance, and presents the experimental study that compares SaGe to state of the art public SPARQL query servers.

Chapter 5 concludes this thesis and outlines perspective works.

Annex A provides a summary of this thesis in French.

1. Introduction

Publications

This thesis is primarily based on the following publication. During my thesis, I have also contributed to the following publications that do not directly relate to its core topic, presented in reverse chronological order follows.

Introduction

Abstract: Federated query engines have been enhanced to exploit new data localities created by replicated data, e.g., Fedra. However, existing replication aware federated query engines mainly focus on pruning sources during the source selection and query decomposition in order to reduce intermediate results thanks to data locality. In this paper, we implement a replication-aware parallel join operator: Pen. This operator can be used to exploit replicated data during query execution. For existing replication-aware federated query engines, this operator exploits replicated data to parallelize the execution of joins and reduce execution time. For Triple Pattern Fragment (TPF) clients, this operator exploits the availability of several TPF servers exposing the same dataset to share the load among the servers. We implemented Pen in the federated query engine FedX with the replicated-aware source selection Fedra and in the reference TPF client. We empirically evaluated the performance of engines extended with the Pen operator and the experimental results suggest that our extensions outperform the existing approaches in terms of execution time and balance of load among the servers, respectively. Chapter 2

Background and Related Works

In this chapter, we first present basic notions on the RDF data model and the SPARQL query language. Then, we review background on data management techniques for storing and querying RDF data under centralized approaches, i.e., data are stored in a single database system and queried using the SPARQL query language. Finally, we present related works on the thesis scientific challenge. We review techniques for circumventing quotas on public SPARQL endpoints, alternatives to SPARQL endpoints for hosting RDF data and we elaborate on the convoy effect and its roots in the Operating System community.

Background

The RDF data model

The core structure of the RDF data model [START_REF] Cyganiak | RDF 1.1 concepts and abstract syntax[END_REF] is a set of RDF triples, each composed of a subject, a predicate, and an object. A collection of such triples is called an RDF graph, and a set of RDF graphs is called an RDF dataset. Within such a dataset, each graph is identified by a URI (except for the default graph), hence talk about named RDF graph. In a way, an RDF graph is a directed and labeled multi-graph of nodes, where each RDF triple corresponds to a directed edge where the predicate is the label, the subject is the source node, and the object is the target node. There are three types of nodes in a graph: URIs, literals, and blank nodes. A URI or a Literal denotes that a specific resource, or entity, exists in the Web of Data: the resource indicated by a URI is called its referent, and the resource denoted by a literal is called its literal value. Unlike URIs and literals, blank nodes do not identify specific resources. Statements involving blank nodes say that something with the given relationships exists, without explicitly naming it.

@prefix foaf: <http://xmlns.com/foaf/0.1/> @prefix dbo: <http://dbpedia.org/ontology/> @prefix dbr: <http://dbpedia.org/resource/> @prefix owl: <http://www.w3.org/2002/07/owl#> @prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> @prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> @prefix wikidata: <https://www.wikidata.org/entity/Q210059> dbr:Neil_Gaiman rdf:type dbo:Person . dbr:Neil_Gaiman foaf:name "Neil Gaiman" . dbr:Neil_Gaiman dbo:author dbr:American_Gods . dbr:Neil_Gaiman dbo:author dbr:Good_Omens . dbr:Neil_Gaiman owl:sameAs wikidata:Q210059 . dbr:American_Gods dbo:author dbr:Neil_Gaiman . dbr:American_Gods rdfs:label "American Gods"@en . dbr:Good_Omens dbo:author dbr:Neil_Gaiman . dbr:Good_Omens dbo:author dbr:Terry_Pratchett . dbr:Good_Omens rdfs:label "Good Omens"@en . <http://dbpedia.org/resource/Neil_Gaiman> # Subject <http://dbpedia.org/ontology/author> # Predicate <http://dbpedia.org/resource/Good_Omens> # Object Asserting an RDF triple indicates that a relation, shown by the predicate, holds between the resources denoted by the subject and object. For example, the above RDF triple represents the fact that Neil Gaiman wrote the book Good Omens. By dereferencing the URI http://dbpedia.org/resource/Neil_Gaiman, we can access the RDF document that describes all the facts asserted about Neil Gaiman in the DBpedia dataset1 . Figure 2.1 shows an extract of this document in Turtle notation. Figure 2.2 shows the same data but represented as a directed, labeled RDF graph.

dbr:Neil_Gaiman dbo:Person "Neil Gaiman" dbr:American_Gods "American Gods"@en dbr:Good_Omens "Good Omens"@en dbr:Terry_Pratchett wikidata:Q210059

The SPARQL query language

The SPARQL query language [START_REF] Harris | SPARQL 1.1 query language[END_REF] allows data consumers to query RDF documents using more complex logic, similar to SQL queries for relational databases. The SPARQL query Q 1 from Figure 2.3 finds all authors with their names and the titles of their books. If we execute Q 1 on the set of RDF triples shown in Figure 2.1, we obtain the following results.

?author

?book_title <http://dbpedia.org/resource/Neil_Gaiman> "American Gods"@en <http://dbpedia.org/resource/Neil_Gaiman> "Good Omens"@en

The semantic of the SPARQL query language was formalized by Perez et al. in 13 2. Background and Related Works [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF], and further extended by Schmidt et al. in [START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF]. Let U, V, L be disjoint infinite sets of URIs, SPARQL variables, and literals, respectively. A SPARQL query is composed of SPARQL Graph patterns expressions, defined recursively as follows:

• A triple pattern tp ∈ (U ∪ V) × (U ∪ V) × (U ∪ L ∪ V) is a graph pattern.
• If P 1 and P 2 are graph patterns, then the expressions P 1 AND P 2 , P 1 UNION P 2 and P 1 OPT P 2 are graph patterns.

• If P is a graph pattern and R is a SPARQL built-in conditions, then P FILTER R is a graph pattern.

An expression P 1 AND P 2 AND . . . AND P N is often called a Basic Graph Pattern (BGP), i.e., a conjunctive query between several graph patterns. A SPARQL built-in condition is constructed using elements of the set U ∪ L ∪ V and constants, logical connectives ( =, ∧, ∨), inequality symbols (<, ≤, >, ≥), the equality symbol (=) and unary predicates2 .

The evaluation of a SPARQL graph pattern P against an RDF dataset D, denoted P D , produces a set of solution mappings. A solution mapping µ is a partial function that maps a set of variables to an RDF term. The domain of µ, denoted dom(µ), is the set of variables on which µ is defined. Two mappings µ and µ are compatible, denoted µ ∼ µ , if ∀x ∈ dom(µ) ∩ dom(µ ), µ(x) = µ (x). Furthermore, var(tp) denotes all variables in a triple pattern tp and µ(tp) denotes the RDF triple obtained by replacing the variables in tp according to µ.

Definition 1 gives the algebra of the SPARQL query language and Definition 2 gives the evaluation semantic of SPARQL graph patterns expressions.

Definition 1 (SPARQL algebra [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF][START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF]). Let Ω 1 , Ω 2 be sets of solutions mappings, R a filter condition, and V a finite set of variables. The expressions of the SPARQL algebra are defined as follows:

Ω 1 Ω 2 = {µ 1 ∪ µ 2 | µ 1 ∈ Ω 1 , µ 2 ∈ Ω 2 , µ 1 ∼ µ 2 } Ω 1 ∪ Ω 2 = {µ | µ ∈ Ω 1 or µ ∈ Ω 2 } Ω 1 \ Ω 2 = {µ 1 | µ 1 ∈ Ω 1 , µ 2 ∈ Ω 2 , µ 1 µ 2 } Ω 1 Ω 2 = (Ω 1 Ω 2 ) ∪ (Ω 1 \ Ω 2 ) σ R (Ω 1 ) = {µ | µ ∈ Ω 1 , µ |= R} π V (Ω 1 ) = {µ | ∃µ : µ ∪ µ ∈ Ω 1 ∧ dom(µ) ⊆ V ∧ dom(µ ) ∩ V = ∅}
where |= refers to built-in boolean functions defined in [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF].

Definition 2 (SPARQL semantics [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF][START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF]). Let D be an RDF dataset, tp a triple pattern, R a FILTER expression, V a finite set of variables, and P 1 , P 2 SPARQL graphs patterns. The evaluation of a graph pattern over D, denoted • D , is defined recursively as follows:

tp D = {µ | dom(µ) = var(tp) ∧ µ(tp) ∈ D} P 1 AND P 2 D = P 1 D P 2 D P 1 UNION P 2 D = P 1 D ∪ P 2 D P 1 OPT P 2 D = P 1 D P 2 D P 1 FILTER R D = σ R ( P 1 D ) SELECT V WHERE P D = π V ( P D )
To illustrate, consider again the SPARQL query from Figure 2.3. In the formal SPARQL semantic, the query is composed of a projection and a Basic Graph Pattern with the following four triple patterns:

tp 1 = ?

Linked Data Management

From a conceptual point of view, we can distinguish two distinct approaches for storing RDF data. The relational-based approach, which views the RDF dataset as a set of RDF triples and considers it as a particular case of the relational data model. The main advantage of this approach is that one can re-use all techniques for indexing, storing, and querying data developed for relational databases [START_REF] Garcia-Molina | Database systems -the complete book[END_REF][START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF]. This approach also highlights the similarities between SPARQL and SQL query languages. On the other hand, the graph-based approach considers an RDF graph through its graph-based representation and leverages graph-based algorithms to perform query processing. However, they are widely adopted for building public SPARQL endpoints. Consequently, in this thesis, we focus on the relationalbased approach because they allow building SPARQL query servers with complete SPARQL query processing capabilities. We now review the main approaches for storing RDF data under the relational-bases approach. Triple stores [START_REF] Erling | Virtuoso: RDF Support in a Native RDBMS[END_REF][START_REF] Harris | 3store: Efficient Bulk RDF Storage[END_REF][START_REF] Harth | YARS2: A Federated Repository for Querying Graph Structured Data from the Web[END_REF][START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF][START_REF] Weiss | Hexastore: sextuple indexing for semantic web data management[END_REF] put all RDF triples into a single table with three attributes: subject, predicate, and object. An optional fourth column, graph, can be used to record the named RDF graph that contains each triple of the dataset.

As in classical relational databases, query processing over a triple store can speed up drastically by defining indexes over the table attributes. Thus, many triple stores use a set of indexes on several combinations of the subject (S), predicate (P) and object (O) attributes. One of the first approaches [START_REF] Ma | RStar: an RDF storage and query system for enterprise resource management[END_REF] rely on the following fives distinct B+-trees [START_REF] Comer | The Ubiquitous B-Tree[END_REF]: 1) one of each attribute S, P and O, 2) a joint index on S and P, 3) a joint index on S and P and a separate index on O, 4) a joint index on P and O, 5) a joint index on S, P, and O. This indexing schema proved to be very efficient for executing simple lookup queries, i.e., scanning for a triple pattern, and queries with few joins.

To further speed up query processing, many approaches rely on clustered indexes, i.e., indexes that store multiples copies of the same data but in different orders. Such indexes allow us to look for random triple patterns in the RDF Graph efficiently and to use fast merge joins for executing queries with a large number of joins. Hexastore [START_REF] Weiss | Hexastore: sextuple indexing for semantic web data management[END_REF] relies on six B + -trees on all possible permutations of S, P, and O: SPO, SOP, POS, PSO, OSP, and OPS. Figure 2.4 shows how Hexastore stores the RDF data from Figure 2.1. For the sake of simplicity, we only show the SPO, POS, and OSP indexes. To evaluate a triple pattern tp against such indexes, Hexastore looks at the position of variables in tp, selects the appropriate index, and starts an Index Scan [START_REF] Garcia-Molina | Database systems -the complete book[END_REF][START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] over the index. For example, for scanning a triple pattern tp = ?s rdf:type ?o, Hexastore selects either the index POS or PSO, locates the record with key p = rdf:type and iterates over all matching RDF triples. Additionally, as Hexastore stores RDF triples in every possible order, the query engine can use very fast merge joins [START_REF] Garcia-Molina | Database systems -the complete book[END_REF][START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] to resolve joins between triple patterns. The theoretical upper bound on space consumption in Hexastore is equals to five times the size of the triple table, and much lower in practice, due to the skewed nature of RDF graphs.

RDF-3X [START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF] follows a similar aggressive indexing technique with the same indexes as Hexastore. Additionally, it also indexes all subsets of the (S, P, O) set, adding nine new partial indexes called aggregated indexes. These indexes associate the parts of RDF triples with their number of occurrences in the RDF dataset, which allows the query engine to estimate the cardinality of triple patterns. For example, the aggregated index SP stores, for each key s, p , the number of RDF triples whose subject is s and predicate is p (|{s | ∀ s, p, o ∈ G}|). The drawback of such aggressive indexing techniques is a significant space overhead, as clustered indexes stores multiples copies of the original data. To mitigate this overhead, RDF-3X relies on a delta compression of RDF triples in the B + -trees leaves. Since two adjacent triples are likely to share the same prefix, then only the difference (delta) between triples are stored, instead of the full triples.

Hexastore and RDF-3X are RDF databases that employ very aggressive indexing schemes. On the opposite, Virtuoso [START_REF] Erling | Virtuoso: RDF Support in a Native RDBMS[END_REF] uses a partial indexing scheme, with only two full indexes on PSOG and POGS, where G is the URI of the graph to which the triple belongs. Besides, Virtuoso also stores three partial indexes SP, OP, and GS, which allows it to evaluate any triple pattern by combining partial indexes.

Property tables rely on the vertical partitioning technique [1]. They group RDF triples per predicate value, and all triples within the same group are stored in a separate table, named after the predicate. Each table contains two attributes: subject and predicate, where at least the subject attribute is indexed using a (un)clustered B + -tree. The kind of approach can be implemented very efficiently in column-based stores [START_REF] Idreos | MonetDB: Two Decades of Research in Column-oriented Database Architectures[END_REF][START_REF] Sidirourgos | Column-store support for RDF data management: not all swans are white[END_REF]. Figure 2.5 shows how the RDF data from Figure 2.1 are stored using property tables.

Clustered-property tables [START_REF] Harris | 4store: The design and implementation of a clustered RDF store[END_REF][START_REF] Sintek | RDFBroker: A Signature-Based High-Performance RDF Store[END_REF][START_REF] Wilkinson | Efficient RDF Storage and Retrieval in Jena2[END_REF] extend the concept of property tables and groups RDF triples into classes based on the co-occurrence of sets of predicates in the dataset. Each table stores the triple that corresponds to a class, with

Subject Object

dbr:American_Gods "American Gods"@en dbr:Good_Omens "Good Omens"@en (e) Predicate rdfs:label attributes named after the predicates. The classes are usually computed using a clustering algorithm or by an expert. A major drawback of both property tables and clustered-property tables is that they offer poor performance when executing SPARQL queries that contain unbounded predicates. In this case, the query engine must scan all tables in the database to find matches, and then all results need to be re-combined using joins or unions. Additionally, each time we add a new predicate to the dataset, the RDF database needs to recompute the classes and the data partitions, as the content of some classes might evolve, which is very expensive for large RDF datasets. Due to these hard limitations, property tables and clustered-property tables have not become popular in RDF databases. Consequently, in this thesis, we focus on Linked Data Management using Triple stores.

SPARQL query processing in Triple Stores

Execution of SPARQL queries over RDF data is a process called SPARQL query processing, with a vast literature. A good survey on the whole field is in [START_REF]Linked Data Management[END_REF]. In this thesis, we focus on SPARQL query processing over Triple stores, as they are the most dominant RDF database systems for public SPARQL query servers.

Given a SPARQL query, a SPARQL query engine constructs a query execution plan and executes it on the RDF database to produce the query results. This process is called the optimize-then-execute paradigm [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF]. It allows the query engine to translates a program written in a high-level specification (the SPARQL query language) into an optimized low-level computer program (the query execution plan), and the execution of this program produces the query results. Figure 2.6 summarizes the overall process of SPARQL query processing.

Query decomposition

The first layer of SPARQL query processing parses the query and decomposes it into an intermediate representation. First, the query is parsed and normalized into an Abstract Syntax Tree (AST), more suitable for manipulation by the query engine. The AST is semantically analyzed so that incorrect queries are detected and rejected as early as possible.

Next, the query engine translates the AST into a representation called a join query graph [START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF], where each Basic Graph pattern is expanded into a set of triple patterns. The triple patterns are then turned into the edge of the join query graph, where two nodes of the graph are connected with an edge if the corresponding triple patterns share at least one SPARQL variable. This representation corresponds Next, given the join query graph, the SPARQL query engine constructs its algebraic representation [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF], called a join tree, composed of logical scan and join operators. The join tree is a binary tree whose leaves are the triple patterns, and inner nodes are joins. We distinguish two important class of join tree: 1) left-deep (linear) tree, where every join has one of its triple patterns has input, and 2) bushy trees, where no restriction applies.

Finally, the query engine completes the join tree with the other operators from the SPARQL query, e.g., OPTIONAL, UNION, or aggregations. These disjunctive parts of the query are treated as nested SPARQL subqueries, in that there inner basic graph patterns are translated and optimized separately. Then, the query engine combines these sub-parts with the join tree, producing a logical SPARQL query execution plan. Figure 2.7b shows the logical execution plan generated for the SPARQL query from Figure 2.3.

Query optimization

The goal of the second layer of SPARQL query processing is to find an execution strategy for the SPARQL query which is close to optimal [START_REF] Hartig | The SPARQL Query Graph Model for Query Optimization[END_REF][START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF], as finding the optimal execution plan is computationally intractable. Query optimization consists of finding the "best" ordering of operators in the query plan to minimize a cost function. This function, often defined in terms of time units, refers to computing resources such as disk space, disk I/Os, buffer space, CPU cost, etc. The most simple optimization techniques are based on SPARQL normal forms [START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF]. For example, the join distribution technique allows creating bushy trees from joins between UNION clauses. The FILTER push-down technique consists of splitting FILTER conditions into the conjunction of conditions and pushing these conditions as deep as possible towards the leaves of the join tree. These techniques are easy to apply, as they are syntactic: they are based on rules that transform the plan based on its shape, so they can be used by any SPARQL query engine.

One of the most critical optimizations done by the SPARQL query engine is called join ordering [START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF][START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF]. It consists of re-ordering the join sequence of triple patterns in each join tree to minimize the selectivity of each join operator. The cardinality of a triple pattern is the number of RDF triples that matches this pattern. Let c 1 , c 2 be the cardinality of two triple patterns tp 1 , tp 2 , then the selectivity of the join tp 1 tp 2 is defined as S(tp

1 tp 2 ) = |tp 1 tp 2 | c 1 × c 2 .
Typically, selectivities are estimated by the query optimizer using precomputed statistics [START_REF] Neumann | Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins[END_REF][START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF]. These selectivities provide a way to optimize the cardinality of intermediate results generated by a join tree. The state of the art techniques that solves this problem are based on dynamic programming algorithms [START_REF] Moerkotte | Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products[END_REF][START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF].

Building the physical SPARQL query execution plan

Once the optimized logical SPARQL query execution plan is produced, the SPARQL query optimizer invokes the last layer of SPARQL query processing to compile the logical plan into a physical SPARQL query execution plan. This plan is quite literally the software that needs to be executed to produce query results.

To produce this plan, the query engine performs a tree-traversal of the logical plan and, for each logical operation, selects a physical query operator to implement it. While the logical algebra used in the logical plan is the same for all SPARQL queries, the physical algebra is system-specific: different databases may implement the same logical operators using different physical operators [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF]. For example, a triple store can evaluate triple patterns using scan operators on the available indexes. In contrast, a database that relies on vertical partitioning will use operators specific to its partition layout.

As several physical operators can implement the same logical operator, the query engine relies on a cost-model to select the most efficient implementation for each operator. For example, the Merge join algorithm is more performant if both join inputs produce results sorted on the join variable. Figure 2.8 shows a SPARQL physical query execution plan compiled from the logical plan of Figure 2.7b. In this plan, triple patterns are evaluated using Index Scans, which scans B + -trees indexes to produces solutions mappings from relevant RDF triples. A Merge join implements the first join in the plan, as the solutions mappings produced by both its inputs are sorted on the ?author join variable. Remaining joins are done using [START_REF] Dewitt | Nested Loops Revisited[END_REF], a variant of the well-known loop join algorithm that leverages the indexes of our triple store to speed-up query processing. Finally, a Projection operator executes the logical π ?author,?book_title operation and produce the query solutions for the SPARQL query Q 1 .

Another choice made by the query engine during the plan compilation phase is how physical operators communicate between them. For example, given a query with two joins in sequence, how do the results of the first join are passed to the second one? The simplest method is to rely on temporary files to exchange intermediate results between operators. However, for queries with a large number of intermediate results, this method adds significant overhead in terms of data storage during query execution [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF]. Alternatively, many query engines follow the iterator model [START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF], where operators are connected as a pipeline and communicate in sequence. Each time an operator needs to produce some value, it pulls solutions from its predecessor(s) in the pipeline, computes the value, and then forward it to the next operator in the pipeline. Operators implemented with this model are called iterators and formalized in Definition 3. Table 2.1 shows some examples of physical operators implemented as iterators.

Definition 3 (Iterator). A physical operator that implements the iterator model supports the following operations:

• Open() which initialize the datastrucures used by the operator.

• GetNext() which produce an intermediate result.

• Close() which cleanup any datastrucure used by the operator.

Implementing physical operators as a pipeline of iterators provide several properties for query execution: 1) operators are implemented as individual units, independent of each other, 2) the whole query execution is executed by a single process in a coroutine-fashion, 3) operators produce one item at a time upon request, 4) intermediate results are passed directly between operators without the need for intermediate files, which makes this model very efficient in terms of memory costs, and 5) a pipeline of iterators naturally implements any shape of query plan.

However, a pipeline of iterators is quite inefficient in terms of CPU consumption, because GetNext functions will be called recursively for producing every single solution mappings. As each call to GetNext will cause a jump in the heap memory, queries with a large number of intermediate results can cause many round-trips in the CPU, deteriorating performance and generating poor code locality, which reduces optimizations from modern CPUs [START_REF] Neumann | Efficiently Compiling Efficient Query Plans for Modern Hardware[END_REF]. Nonetheless, this approach remains the most used implementation for physical query execution in most databases.

Related Works

Decomposing SPARQL queries to avoid quotas

A first approach to circumvent quotas is to decompose a SPARQL query that is interrupted by some quotas into a set of subqueries whose execution completes under the same quotas. In [7], Buil Aranda et al. study such type of evaluation strategies for federated SPARQL queries, but they can be generalized to nonfederated queries. The authors identify six distinct rewriting strategies, ranging from simple pagination to more complex query rewriting techniques.

Pagination (SYMHASHP)

The most straightforward technique to circumvent the limitations imposed by quotas is to paginate the query results using the LIMIT, OFFSET, and ORDER BY solution modifiers. We first sort all query results and then retrieve them by batches of fixed sizes. subqueries yields the final query results. The sorting phase is mandatory, because the SPARQL endpoint may not produce the results in the same order between each query. Figure 2.9 shows an example of a SPARQL query paginated with the SYMHASHP strategy, where we fetch query results per page of 10 000 results. However, while this approach is feasible, it is not applicable in general, as executing several consecutive ORDER BY queries might actually be quite expensive on the remote server and could trigger resource limits nonetheless. For example, the Virtuoso SPARQL endpoint [START_REF] Erling | Virtuoso: RDF Support in a Native RDBMS[END_REF], used as the backend for the DBpedia SPARQL endpoint, limits the amount of memory per query when sorting results. We can avoid such limitations if the endpoint already delivers sorted results, but it makes the approach very dependent on the actual server implementation.

Symmetric Hash Join (SYMHASH)

This strategy is applicable only for the evaluation of Basic Graph patterns, i.e., joins of triple/graph patterns. To evaluate a SPARQL query Q = P 1 P 2 , the client executes P 1 and P 2 on the server using two distinct requests, stores their results into two hash tables (one per subquery), and then joins the results using the Symmetric Hash Join algorithm [START_REF] Wilschut | Dataflow Query Execution in a Parallel Main-memory Environment[END_REF]. This strategy can be generalized for joining an arbitrary number of graph patterns. However, this join algorithm is expensive if the intermediate result sets are much larger then the join result size [START_REF] Wilschut | Dataflow Query Execution in a Parallel Main-memory Environment[END_REF] 2.10: A SPARQL query that "ships" solution bindings to perform a join server-side, following the VALUES, FILTER and UNION strategies [7]. may deteriorate query processing performance. This strategy also requires that the evaluations of both P 1 and P 2 deliver complete results under quotas, or the join results will be incomplete.

(| P 1 D | + | P 2 D | > | P 1 P 2 D |),
Nested Loop Join (NESTED) Similar to SYMHASH, the join between two graph patterns is done on the client-side using the Nested Loop Join algorithm [START_REF] Garcia-Molina | Database systems -the complete book[END_REF]. Given a query P = P 1 P 2 , the client evaluates P 1 , and then for each µ ∈ P 1 D , the client evaluates µ(P 2 ) using the server and produces the final join results. However, this approach faces three significant issues. First, the Nested Loop join algorithm is efficient only if the selectivity of the left join input is less than the selectivity of the right input [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF]

(| P 1 D | < | P 2 D |).
So, like the SYMHASH strategy, it can deteriorate query performance if the algorithm inputs do not meet these requirements. Second, this strategy sends an HTTP request to the server for each solution binding of P 1 . If P 1 has a high number of solutions, then the NESTED strategy can lead to denial of service attacks or trigger quotas on requestrate. For example, the DBpedia SPARQL endpoint does not allow more than 100 requests per second per IP address, with an initial burst of 120 requests. Finally, only a subclass of SPARQL queries called strongly bounded SPARQL queries are guaranteed to produce complete results with this technique, as shown in [7].

VALUES, FILTER, and UNION strategies The last three techniques improve on the NESTED strategy to reduce the data transferred between client and server. Instead of sending one HTTP request per solution of P 1 D , the client "ships" a set of solutions, using the VALUES operator, to perform the join between P 1 and P 2 server-side. A similar technique, called Bound join, is used by the FedX federated SPARQL query engine [START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF]. Given P = P 1 P 2 , the client sends a SPARQL query to the server to compute Ω = P 1 D , and then sends a second query P 2 VALUES Ω to perform the join server-side. Figure 2.10 shows a SPARQL query that performs data shipping. It computes the join between P 2 = ?actor rdfs:label ?name and the set of solutions Ω = {{?actor → dbp:David_Tennant}, {?actor → dbp:Michael_Sheen}} to finds the label of the actors David Tennant and Michael Sheen. As the VALUES operator is not widely available on current public SPARQL endpoints [START_REF] Aranda | SPARQL Web-Querying Infrastructure: Ready for Action?[END_REF], the authors propose equivalent strategies using the FILTER and UNION SPARQL operators. However, as before, this strategy requires that both queries sent to the server produce complete results under quotas.

Synthesis In summary, all of these strategies suffer from the same significant drawbacks. First, they need to know the server configuration in terms of quotas. This information might be unavailable, as data providers may not wish to publish their server's configuration. Second, they can require significant data transfer, which deteriorates SPARQL query processing performance. Finally, they can only be applied to the class of strongly bounded SPARQL queries to ensure complete and correct evaluation results.

Linked Data Fragments

Linked Data Fragments (LDF) [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF][START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF] restrict the server interface to a fragment of the SPARQL algebra, to reduce the complexity of queries evaluated by the server and increase its availability. LDF servers are no longer compliant with the W3C SPARQL protocol, and SPARQL query processing is distributed between an LDF server and a smart client. The latter acts as a SPARQL query engine hosted on the client-side. It decomposes the input SPARQL query to evaluate the fragment supported by the server and handles the remaining operations client-side.

Hartig et al. [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF] formalized this approach using the Linked Data Fragment machines (LDFM). An LFDM captures possible client-server systems that execute user queries, issued at the client-side, over a server-side RDF dataset. The client communicates with the server using a server language L S which represents the SPARQL operations supported by the server interface. Then, the client builds final query results from the server responses using a client response-combination language L C , which is an algebra over the server responses. Thus, an LDFM M is a tuple M = L S , L C . Notice that, if an LDFM wants to allow execution of any SPARQL queries, then it must hold that L S ∪ L C = CoreSPARQL, where CoreSPARQL is the full SPARQL query language [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF].

The Triple Pattern Fragments (TPF) approach [START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF] is one implementation of LDF where the server only evaluates paginated triple pattern queries. Formally, a TPF client-server is an LDFM M T P F where L S = {tp} and L C = CoreSPARQL \ L S . To evaluate Basic Graph Patterns, the TPF client follows an approach similar to the NESTED strategy from [7], illustrated in Figure 2.11. For a BGP P = {tp 1 , tp 2 }, the client first evaluates tp 1 using the paginated server interface, [START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF] retrieves pages of relevant RDF triples, and converts them into solution mappings for tp 1 . Then, for each mapping µ ∈ tp 1 D , it evaluates the subquery µ(tp 2 ) using the server interface, and for each µ ∈ µ(tp 2 ) D , it produces µ ∪ µ as a set of join results. For evaluating a Basic Graph Pattern of more than two triple patterns, the TPF client takes advantage of the metadata published by the TPF server to perform a client-side join ordering and always evaluates the most selective triple pattern. As paginated triple pattern queries can be evaluated in bounded time [START_REF] Heling | Querying Large Knowledge Graphs over Triple Pattern Fragments: An Empirical Study[END_REF], the server does not suffer from the convoy effect. But, as the client computes joins locally, the transfer of intermediate results leads to poor query execution performance. For example, the evaluation of the query Q 1 , from Figure 1.3, which finds all actors and their birth places in the DBpedia knowledge graph, using the TPF approach sends 507156 subqueries and transfers 2GB of intermediate results in more than two hours.

Other LDF approaches have introduced different trade-offs, compared to the original TPF approach, to reduce the overhead in data transferred. The Bindings-Restricted Triple Pattern Fragments (BrTPF) approach [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF] improves the TPF approach by using the bind-join algorithm [START_REF] Haas | Optimizing Queries Across Diverse Data Sources[END_REF] to reduce transferred data. While the extended server interface is resilient to convoy effects, the client still executes joins locally. In [2], Acosta et al. propose to use networks of Linked Data Eddies to allow the TPF client to switch between several join strategies. The smart client uses adaptive query processing techniques [START_REF] Avnur | Eddies: Continuously Adaptive Query Processing[END_REF][START_REF] Deshpande | Adaptive Query Processing[END_REF] to dynamically adapt query execution to adjust to changes in runtime execution and data availability. In scenarios with unpredictable transfer delays and data distributions, Linked Data Eddies outperform the existing LDF approach. However, the restricted server interface still leads to significant data transfers.

Synthesis While the LDF approaches remain limited by the high data transfer rates, they demonstrate that one can publish RDF data using a less expressive SPARQL query server but still allows the execution of the complete SPARQL query language. As hinted in [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF], a more efficient LFDM is a one that will enable for server-side processing of Basic Graph Patterns without generating convoy effects. To the best of our knowledge, none of the existing LDF approaches achieve that.

Q 1 Executing Q 2 Waiting Executing Q 3 Waiting Executing Q1 completed Q2 completed Q3 completed

Scheduling policies and Preemption

Operating systems have heavily studied First-Come First-Served (FCFS) scheduling policies and the convoy effect [START_REF] Blasgen | The Convoy Phenomenon[END_REF]. In a system where the duration of tasks varies, a long-running task can block all others, deteriorating the average completion time for all tasks and creating a convoy effect.

To illustrate, consider the execution scenario from Figure 2.12. Three distinct web clients want to execute one SPARQL query each, Q 1 , Q 2 , and Q 3 , using the same SPARQL endpoint. Q 1 , Q 2 , Q 3 execution times are respectively 20 seconds, 5 seconds, and 5 seconds. We also consider that the server only offers one worker thread, so it can only execute one query at a time. In this scenario, Q 1 arrives first at the server at t 1 and runs for 20 seconds. At t 3 , the server receives Q 2 , but has to wait for execution has the only worker is still busy with Q 1 . Similarly, Q 3 is received at t 4 and must wait. At t 20 , Q 1 execution completes, and the first client receives its results. Then, the server starts the execution of Q 2 , while Q 3 is still in the waiting queue. At t 25 , Q 2 execution completes, and the server begins the evaluation of Q 3 , which finishes at t 30 . In the end, the first web client has received its query results after 20 seconds, i.e., the execution time of Q 1 , while the two other clients have received their results after 25 seconds and 30 seconds, respectively. Hence, the execution of Q 2 and Q 3 have been delayed by the evaluation of Q 1 because the FCFS execution policy created a convoy effect. In terms of query execution performance, we have an average waiting time of 0+17+22 allocation of CPU between tasks, avoids convoy effect, reduces the waiting time, and provides excellent responsiveness. RR runs a job for a given time quantum, then suspends it and switches to the next task. It repeatedly does so until all tasks are finished. This action of suspending a task to resume it later is called preemption. Figure 2.13 shows the execution scenario from Figure 2.12 executed under a RR scheduling policy. Jobs run for a time quantum of 10 seconds, after which the scheduler triggers a context switch (CS) operation to suspend the current task and resume the next one. In our example, context switching takes about two seconds.

In the RR algorithm, the value of this time quantum is critical for its performance.

If it is too high, RR behaves like FCFS with the same issues, and when it is too low, the overhead of context switching dominates the overall performance. Scheduling algorithms to organise query execution at SPARQL endpoints [START_REF] Maali | Scheduling for SPARQL Endpoints[END_REF][START_REF] Torre-Bastida | Intelligent SPARQL Endpoints: Optimizing Execution Performance by Automatic Query Relaxation and Queue Scheduling[END_REF] has been considered to reduce the impact of convoy effects. However, all of these approaches require to know the cost of incoming SPARQL queries, e.g., the query execution time or the CPU and memory used. For a public SPARQL query server, this cost is hard to estimate as it can accept any type of query [START_REF] Hasan | Predicting query performance and explaining results to assist Linked Data consumption[END_REF]. Furthermore, these approaches only consider the scheduling issue at the scope of operating systems, i.e., only between running tasks, excluding those waiting in the server's queue. So, while the operating systems may use the RR algorithm, or any equivalent scheduling policy, the whole SPARQL query execution model still follows the FCFS policy. If we want to build a fully preemptive Web server, we need to "zoom-out" and consider the queries sent to the server as the tasks and the Web server as the resource that tasks competed to get access. Currently, no SPARQL query server provides such preemption.

Chapter 3 Web preemption for public SPARQL Query Servers

As stated before, quotas are an essential part of the Web ecosystem, as they allow data providers to regulate how users consume their services. In this thesis, we hypothesize that the issue with time quotas is not that they interrupt queries, but the impossibility for the client to resume the query execution afterward. Inspired by the work on time-sharing scheduling policies, we propose a new query execution model for SPARQL query servers, called Web Preemption.

We define Web preemption as the capacity of a Web server to suspend a running query after a fixed quantum of time and resume the next waiting query. When the server suspends a query, it returns the query's partial results and suspended state S i to the Web client, which can then resume query execution by sending S i back to the Web server. Compared to an FCFS scheduling policy, our results show that Web preemption provides a fair allocation of Web server resources across queries, a better average query completion time per query, and a better time for first results [START_REF] Anderson | Operating Systems: Principles and Practice[END_REF].

The Web preemption execution model

Model definition

We now formally define the Web preemption execution model. We consider a preemptive Web server, which hosts a read-only RDF dataset, and a smart Web client, that evaluates SPARQL queries using the server. The server has a pool of server workers parameterized with a fixed time quantum. Workers are in charge of query execution. The server also has a waiting queue to store incoming queries when all workers are busy. We consider an infinite population of clients, a finite server queue, and a finite number of server workers.

A preemptive Web server supports three operations: Execute, Resume, and Suspend. The Execute operation is used by the server to execute a query Q for a time quantum q. It takes as input a running query Q i represented by its physical query execution plan, denoted P Q i , and executes it for the duration q. Then, it produces a set of solution mappings ω i and the execution plan P Q i , which is the state of P Q i after the execution (Execute(P Q i ) = ω i , P Q i ). The Suspend operation, which saves the query execution state, is applied to P Q i and produces a saved state S i (Suspend(P Q i ) = S i ). The Resume operation, which resumes query execution from a saved state, is the inverse operation: it takes S i as a parameter and restores the physical query execution plan (Resume(S i ) = P Q i ).

Figure 3.1 presents possible states of a query. The transitions are executed either by the Web server or by the client. The Web server accepts, in its waiting queue, Web requests containing either SPARQL queries or suspended queries. If a worker is available, it picks a query from the waiting queue. For a query Q i , the worker produces a physical query execution plan P Q i using the optimize-then-execute paradigm [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] and starts its execution for a time quantum. For a saved state S i , the server resumes the execution of the corresponding query Q i using the Resume operation. The time to resume the physical query execution plan for a query is not deducted from the quantum.

If a query completes before the time quantum, then the server returns the results to the Web client, and the query execution is complete. If the time quantum is exhausted and the query is still running, then the server uses the Suspend operation to suspend execution and produce a saved state S i . The time to suspend and save the query is not deducted from the quantum. Next, the server returns a page of results p i to the client, which is a tuple p i = ω i , S i where ω i is the set of solution mappings produced during the time quantum q i , and S i is the saved plan obtained 3.1. The Web preemption execution model when suspending the running query at the end of q i . The Web client is then free to continue the query execution by sending S i back to the Web server.

Consequently, the evaluation of a SPARQL query using a preemptive Web server create a partition of solution mappings over time, where the Smart client retrieves partial set of solution mappings ω 1 , . . . , ω n over the duration of query execution. Given a RDF Dataset D and a preemptive Web Server with time quantum q. The correct evaluation of a SPARQL query Q over D using the server produces a finite set of pages P = {p 1 , . . . , p n } which have the following properties:

1.

Q D = ω i ,S i ∈P ω i .
2. It holds that, for p n = ω n , S n , S n = nil.

3. For every pair of two distinct pages p i = ω i , S i ∈ P, p j = ω j , S j ∈ P, it holds that S i = S j . 4. There exists a strict total order ≺ on P such as, ∀p i = ω i , S i ∈ P, ∃p j = ω j , S j ∈ P, where p j is the direct successor of p i according to ≺, it holds that Execute(Resume(S i )) = ω j , x and Suspend(x) = S j . Property 1 states that the client receives all query solutions ( Q D ) after the last page is produced. Property 2 asserts that the last page produced does not contains any saved state: query execution has completed and the server cannot resume it past this point. Properties 3 and 4 states that query execution progresses over time: all saved states are distinct and produced linearly in time.

Illustration

To illustrate our model, consider the execution scenario from Figure 3.2, which extends the one from Figure 2.12. Recall that we have three distinct web clients who want to execute one SPARQL query each, Q 1 , Q 2 , and Q 3 , and their execution times are respectively 20 seconds, 5 seconds, and 5 seconds. We also consider that the server only offers one worker thread, so it can only execute one query at a time. In this scenario, Q 1 arrives first at the server, then Q 2 and Q 3 arrive at t 3 and t 4 , respectively. We have seen in Chapter 1 that, if the server follows a First-Come First-Served scheduling policy, we have an average waiting time of 0+17+22 3 = 13 seconds, an average query completion time of 20+25+30 3 = 25 seconds and an average time for the first results of also 25 seconds. Now, we review the same execution scenario, but under the Web Preemption execution model, with a time quantum of 10 seconds. In this case, the server suspends the execution of Q 1 after 10 seconds, saves the execution state, and returns it to the client. Then, the server executes Q 2 and Q 3 in sequence, and both queries complete under the time quantum. At t 19 , the server has received the saved state of Q 1 , but Q 3 is still running, so the server put the saved state in the waiting queue. At t 23 , the server resumes the execution of Q 1 from its saved state, and the query runs for the remaining 10 seconds. For this scenario, we have an Notice that, in this scenario, suspending and resuming a query takes about 3 seconds. This duration is called the overhead of Web Preemption and significantly impacts query execution performance. Consequently, the main challenges with Web preemption are to bound the preemption overhead in time and space and determine the time quantum required to amortize the overhead.

Challenges of implementing the Web preemption model

The Web Preemption execution model presents several challenges when it comes to its implementation, which all relate to the minimization of the preemption overhead. We now review these challenges and will propose their solutions in the next chapter.

Minimizing the preemption overhead

As said before, the main bottleneck of the Web Preemption model is its overhead. So, we need to bound the time and space complexities of the Suspend and Resume operations to the smallest complexity possible. Informally, these complexities correspond to the following:

• The time complexity of Suspend is the complexity of interrupting and then saving a physical query execution plan.

• The time complexity of Resume is the complexity of resuming a physical query execution plan from a saved state.

• The space complexity of Suspend is the size of the saved state produced after saving a physical query execution plan.

Ideally, we want these complexities to only depends on the query evaluated, and not on the size of the RDF dataset. Otherwise, the preemption overhead will grow with the size of the data, which is intractable in the context of the Web of Data, where the data volume is always increasing [START_REF] Polleres | A More Decentralized Vision for Linked Data[END_REF][START_REF] Schmachtenberg | Adoption of the Linked Data Best Practices in Different Topical Domains[END_REF]. So, we want our complexities to near a complexity of O(|Q i |), where |Q i | is the number of operators in the physical query execution plan used to execute Q i . It requires to suspend, save, or resume the state of all physical query operators in any possible physical query execution plan in near-constant time, i.e., O(1).

However, some physical SPARQL query operators need to materialize data in their internal states, i.e., build collections of mappings collected from other operators to perform their actions. To illustrate, recall the Sort iterator from Table 2.1, used to evaluate the ORDER BY SPARQL operator. This physical operator first needs to store all input solution mappings in a table before producing any results. If the SPARQL query has n solution mappings, then the time complexity of suspending and saving the internal state of the Sort iterator is in O(n). Additionally, if we consider a stateful Web Preemption, we would need to ship these n results between the client and the server each time preemption occurs. This situation could generate significant data transfer and deteriorate query execution performance. For resuming physical operators, similar reasoning holds.

Consequently, we distinguish two categories of physical SPARQL query operators: mapping-at-a-time and full-mapping operators, formalized in Definition 4. Database systems made a similar distinction between tuple-at-a-time and full-relation operators [START_REF] Garcia-Molina | Database systems -the complete book[END_REF] (see Chapter 15.2).

Definition 4 (Types of physical query operators). A physical SPARQL query operator OP is a mapping-at-a-time operator if, at any time, it stores at most one set of solution mappings in its internal state. Otherwise, OP is a full-mappings operator.

From Definition 4, we have the intuition that full-mapping operators are going to be more expensive to suspend and resume than mapping-at-a-time operators. Thus, the first challenge of implementing the Web preemption model is to suspend and resume any kind of operators efficiently, to achieve the lowest bound on time and space complexities.

Choosing between stateless and stateful preemption

In the Web Preemption model, there are two possible modes for producing and storing saved states: stateless or stateful. In stateless mode, the server directly returns saved states to the client, alongside query results. This strategy, widely used for building public Web APIs, provides several properties:

• Fault-tolerance: As saved states are saved client-side, any client can resume query execution even if the server has restarted due to a crash.

• Scaling: The data provider can replicate the server to scale dynamically under the load without having to copy saved states across replicas.

• Load balancing: All preemptive Web servers that host the same RDF dataset can resume the same saved state. Thus, the data provider can balance the load of query processing across several replicated servers.

However, the stateless mode exhibits two main flaws. First, the server must send all saved states through the HTTP protocol, so the preemptive Web server needs to encode them in a compatible format. This serialization phase increases the time complexity of the Suspend and Resume operations, as more compressed formats are more expensive to encode and decode. Second, the size of saved states increases the data transfers between the client and the server. So, the preemptive Web server works under even stringent constraints on the space complexity of the Suspend operation, which further restricts the space of physical query operators available for SPARQL query processing. As an example, the Sort iterator, from Figure 2.1, can increase a lot the preemption overhead in stateless mode, as it needs to store all query results in its internal state. Hence, it might be excluded by the SPARQL query engine when evaluating an ORDER BY operator. At the opposite, in stateful mode, all saved states are stored server-side, and the clients receive only references. For example, saved states can be assigned unique identifiers and stored in a fast-access in-memory database. The clients then only receive these identifiers as saved states, and when they sends them back to the server, it accesses the in-memory database to get the associated saved plans. Stateful mode allows the preemptive Web server to use cheaper serialization strategy for saved states, as they never need to be transmitted over the network. It effectively removes the increased preemption overhead that occurs in stateless mode, and increase the space of physical query operators available to the server. However, in stateful mode, we lose the fault-tolerance, scaling, and load balancing properties compared to the stateless mode. As saved states are stored on the server-side, replication becomes more complex. We need to either replicate saved states or store them in a centralized location. In the case of server crashes, saved states can be lost, which forces the clients to restart their queries from the beginning.

Stateless and stateful modes present different tradeoffs when it comes to saving query execution plans and saving their saved states. So, an implementation of the Web Preemption model must choose between stateless preemption, and favor faulttolerance and scaling over query processing performance, or a stateful preemption, and choose the opposite tradeoff.

Communication between physical query operators

When the server saves the sate of a physical query execution plan, we also need to save the intermediate results exchanged between operators in the plan. So, the implementation chosen by the SPARQL query engine for communication inside the plan has a direct impact on the space complexity of the Suspend operation. If the query engine wants to use temporary files to store intermediate results, then we also need to save these files when preemption occurs, and in the case of stateless web preemption, we need to send them to the client.

Communication between operators has no direct relationship with the use of full mappings operators, as a plan entirely composed of mapping-at-a-time operators can create significant inter-operator communication. For example, under the Vectorized processing model [START_REF] Zukowski | MonetDB/X100 -A DBMS In The CPU Cache[END_REF], mapping-at-a-time operators can exchange large vectors of intermediate results while only saving a single set of solution mappings in their internal state. Thus, an implementation of the Web Preemption model has to care with how it handles inter-operator communication, as it impacts the preemption overhead.

Saving consistent states of the physical query execution plan

When suspending a physical query execution plan, the SPARQL query engine has to visit each operator in the plan and interrupt it a consistent state from which it can be resumed later. However, physical query operators may contain non-interruptible sections: query execution cannot be interrupted until exiting those sections. This concept is similar to the notion of kernel sections in operating systems [START_REF] Anderson | Operating Systems: Principles and Practice[END_REF], which are sections of code that cannot be interrupted by the scheduler. Non-interruptible sections can occur in any physical query operator. For example, an operator that reads data from the disk will want to consider the retrieval of each data item as a non-interruptible operation. Otherwise, the operator could be interrupted while reading bytes from the disk, which can result in a corrupted state or cancel the operation indefinitely. In a sense, non-interruptible sections help to provide progression to the query execution, as they define atomic units of progress in physical query operator.

However, the usage of these sections can have an unexpected side-effect on the preemption overhead. Indeed, when preemption occurs, if a physical query operator is in such a section, then the query engine must wait for the operator to exit the section before interrupting it. Thus, the time complexity of the non-interruptible sections impacts the time complexity of the Suspend operation: the longer these sections are, the longer it will take to suspend the running query. In the worst case, they can re-introduce convoy effects. In [START_REF] Blasgen | The Convoy Phenomenon[END_REF], Blasgen et al. observe this effect when the usage of locks in concurrency control adds unwanted waiting time in query processing. Thus, an implementation of Web Preemption must minimize the duration of non-interruptible sections, at the risk of increasing the preemption overhead.

Chapter 4

SaGe: A preemptive SPARQL query engine

The Web preemption model allows data providers to build SPARQL query servers that are not subject to convoy effects and always deliver complete results for any SPARQL queries. However, as seen at the end of the previous chapter, we are left with a significant issue related to the implementation of this model: Given a SPARQL query Q, we need to minimize the time and space complexities of the Suspend and Resume operations when applied to Q.

In this chapter, we propose SaGe, a SPARQL query engine that implements the Web Preemption model and solves the issue above. Our objective is to bound these complexities such that they depend only on the number of operations in the query plan. Consequently, the problem is to determine which physical query plans P Q has a preemption overhead bounded in O(|Q|), where |Q| denotes the number of operators in the expression tree of P Q .

Implementing the Web Preemption model

In the previous chapter, we have observed that the preemption overhead for full mappings physical operators is likely to exceed our target bound of O(|Q|).

To overcome this issue, we propose and motivate a serie of design choices for implementing the Web Preemption model, in order to minimize the preemption overhead. Bear in mind that we propose here one feasible implementation of the Web Preemption model, but no the only one.

First, to reduce the preemption overhead of full-mappings operators, we choose to distribute operators between a SaGe server and a SaGe Smart Web client as follows.

• Mapping-at-a-time operators are suitable for Web preemption, so they are PREFIX schema: <http://schema.org/contentSize/> PREFIX gr: <http://purl.org/goodrelations/> SELECT DISTINCT ?vo ?v1 WHERE { ?v0 gr:includes ?v1. # tp1 ?v1 schema:contentSize ?v3. # tp2 } supported by the SaGe server. They are a subset of CoreSPARQL [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF], composed of Triple Patterns, Basic Graph Patterns, UNION, FILTER, and SELECT operations. We explain how to implement them in Section 4.2.

• Full-mappings operators are not suitable for Web preemption, so they are implemented in the SaGe Smart Web client. They are physical operators used to implement OPTIONAL, SERVICE, ORDER BY, GROUP BY, DISTINCT, MINUS, FILTER EXIST, and aggregations operations(COUNT, AVG, SUM, MIN, MAX). We explain how to implement them in Section 4.3.

As proposed in LDF [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF][START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF], the collaboration of the SaGe client and the SaGe server allows to execute full SPARQL queries. Hence, SaGe is an LDFM M SaGe where L S ∪ L C = CoreSPARQL.

Regarding the communication between operators, we choose to follow the iterator model [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF][START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF] to avoid the materialization of intermediate results between physical operators. To support preemption, we extend standard iterators to preemptable iterators, formalized in Definition 5. As we connect iterators in a pipeline, we consider that each iterator is also responsible for recursively stopping, saving and resuming its predecessors.

Definition 5 (Preemptable iterator).

A preemptable iterator is an iterator that supports, in addition to the classic Open, GetNext, and Close methods [START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF], the following methods:

• Stop waits for all non-interruptible sections to complete, and then it interrupts the iterator and its predecessor(s).

• Save serializes the current state of the iterator and its predecessor(s) to produce a saved state.

• Load reloads the iterator and its predecessor(s) from a saved state.

Finally, we choose to implement the SaGe preemptive SPARQL query server under the stateless mode and return the saved pipeline of iterators to the client.

The SaGe preemptive SPARQL Query Server

The SaGe server supports the evaluation of SELECT, Triple Patterns, Basic Graph Patterns, UNION, and FILTER operations. The logical and physical query plans are built following the optimize-then-execute [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] each iterator recursively in the pipeline, and Resume reloads the pipeline in the suspended state using a saved state. To illustrate, consider the SaGe page shown previously in Figure 4.2. This page contains the plan that evaluates the SPARQL query Q 2 with |Q 2 | = 4 operators. A preemptable projection operator implements the SELECT operator, a preemptable Index Scan implements the evaluation of the evaluation tp 2 , and a preemptable Index loop join implements the join between tp 2 and tp 1 . In this saved state, the evaluation of tp 2 has been suspended after scanning 224 relevant triples, while the Index Loop join with tp 1 has been suspended after scanning two triples from the inner loop.

In the following, we review SPARQL operators implemented by the SaGe server as preemptable iterators. We modify the regular implementations of these operators to include a non-interruptible section when needed. Operations left unchanged are not detailed. Notably, this includes the Stop operation, as its algorithm is the same for every preemptable iterator: it waits for all non-interruptible sections to complete and then suspends the operator. Table 4.1 resumes the complexities related to the preemption of server operators, where S P and R P denote the time complexity for suspending and resuming the iterator P , respectively, |Q| denotes the number of operators in a plan, and |t| and |tp| denote the size of encoding an RDF triple and a triple pattern, respectively.

SPARQL query forms

The SPARQL language defines four query forms1 , which use the set of solutions mappings produced by the evaluation of the WHERE clause of the query to query results of various types. These query forms are:

• SELECT Returns a subset of the variables bound in a query group pattern [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF]. It is similar to the projection operator in relational databases [START_REF] Garcia-Molina | Database systems -the complete book[END_REF].

• CONSTRUCT Returns an RDF graph constructed by substituting variables in a set of triple templates [START_REF] Kostylev | CONSTRUCT Queries in SPARQL[END_REF].

• ASK Returns a boolean indicating whether a query pattern matches or not, i.e., if the evaluation of the query produces at least one result.

• DESCRIBE Returns an RDF graph that describes the resources found. The SaGe query server evaluates SELECT queries using the preemptable projection operator π V (P ) [START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF]. It performs the projection of mappings obtained from its predecessor P according to a set of projection variables V = {v 1 , . . . , v k }. Algorithm 2 gives the implementation of this iterator. In this algorithm, we need to ensure that, when preemption occurs, the operator does not discard mappings without applying projection to them. When the GetNext() is called, the operator checks if the local variable µ has a value. If not, it pulls a set of solution mappings from its predecessor in the pipeline and stores it in µ Then, at Lines 7-9, it uses a non-interruptible section to save the projection results in a temporary variable µ , then it discards the last µ read from the pipeline, and returns µ as a new query result. Thus, when preemption occurs during the execution of GetNext(), only two cases can arise: 1) µ has no value, so the iterator will restart by pulling a new value from the pipeline, and 2) µ has a value, so the iterator resume the projection operation.

The Save() and Load() method are simple for this operator: the first saves the current value of µ, and the latter reloads this value from the saved state. Propositions 1, 2, and 3 give the preemption overhead for the preemptable projection iterator. As the proofs of these propositions use the same structure as the other proofs in this chapter, we write them in detail, and we will simplify for the others. Proposition 2. The time complexity of the Suspend operation applied on a preemptable projection iterator π V (P ) is in O(|V |+S P ), where S P is the time complexity for suspending the iterator P . Proof. To compute the time complexity of the Suspend applied to a preemptable iterator, we need to compute bounds on: 1) the duration of the iterator's noninterruptible sections, 2) the time complexity of the iterator's Save function.

In Algorithm 2, there is only one non-interruptible section from Line 7 to 9. It contains three operations: a projection operation, an assignment, and a function return call. The first one selects a subset of the variables bound in a set of solution mappings (O(|V |)), while the other one performs an assignment to a variable ( (1)). So, the complexity of the projection predominates, and the non-interruptible section from Line 7 to 9 is bounded in O(|V |).

Next, for the Save function, its time complexity is dominated by the operation of saving the predecessor iterator P . So, if S P is the time complexity for suspending the iterator P , the time complexity of Save is bounded in O(S P ).

Consequently, the time complexity of suspending and saving a preemptable projection iterator π V (P ) is in O(|V | + S P ). Proof. The operation of resuming the predecessor iterator P dominates the time complexity of the Load() function in Algorithm 2. So, if R P is the time complexity for resuming the iterator P , then the time complexity of resuming the preemptable projection iterator π V (P ) is in O(R P ).

For evaluating CONSTRUCT, ASK, and DESCRIBE queries, we do not need dedicated physical query operators. Indeed, the SaGe Smart Web client can execute them using a single SPARQL SELECT query, followed by some lightweight clientside computation. Given a CONSTRUCT query Q c = CONSTRUCT H WHERE P , where H is a set of triple patterns and P is a graph pattern, the answers of [START_REF] Kostylev | CONSTRUCT Queries in SPARQL[END_REF]. Thus, to evaluate Q c , the Smart Web client needs to send a SPARQL query Q c = SELECT * WHERE P to the server, and then computes the answers of Q c locally from those of Q c . Evaluating an ASK query requires to find at least one solution mappings that satisfy the query group pattern. So, the client can simply send an equivalent SELECT query with a modifier LIMIT 1, and output True if it receives results. For DESCRIBE queries, the Smart Web client can rewrite them into equivalent CONSTRUCT queries and evaluate the rewritten queries as described before.

Q c are Q c D = {µ(tp) | ∀µ ∈ P D , ∀tp ∈ H, µ(tp) is well-formed}

Triple Pattern evaluation

The evaluation of a triple pattern tp requires sequentially reading an RDF dataset D, locate all matching RDF triples, and produce the corresponding set of solutions mappings. Suspending and resuming this process can be done by saving the last matching RDF triple read before preemption occurs and resume scanning from this triple, respectively. To do this, we choose to implement the SaGe server as an RDF triple store and rely on clustered indexes to locate RDF triples efficiently using index scans. For clustered indexes, we rely on B+-trees [START_REF] Comer | The Ubiquitous B-Tree[END_REF], as they offer excellent performance for index scans. We use three indexes SPO, OSP, and POS, to achieve optimal coverage for index scans with minimal space overhead [START_REF] Harth | YARS2: A Federated Repository for Querying Graph Structured Data from the Web[END_REF].

Algorithm 3 gives the implementation of a preemptable index scan for evaluating a triple pattern. The GetNext() function scans through RDF triples matching the triple pattern using the clustered index. At each call, it locates the next matching triple, and produces solutions mappings from it. The whole process is a non-interruptible section, as it represents the smallest unit of progression for this iterator. The Save() function stores the triple pattern tp and the last RDF triple t read. Using the indexes, the Load() function locates the last matching RDF triple read t. Propositions 5, 4, and 6 give the preemption overhead for the preemptable Index Scan iterator. Proof. The only non-interruptible section of Algorithm 3 is from Line 2 to 5. The operation that predominates the time complexity of this section is the production of the next matching RDF triple. Since we use three clustered indexes in our triple store, we always scan matching RDF triples as continuous sequences. Thus, when preemption occurs, we can distinguish two cases: 1) The iterator is locating the first matching RDF triple, and 2) The iterator is reading the next matching RDF triple. In the first case, the iterator uses a lookup in the appropriate B+-tree, which is in O(log b (|D|)) [START_REF] Comer | The Ubiquitous B-Tree[END_REF]. In the second case, the iterator jumps to the adjacent triple in the index, which is in O(1). So, in the worst case, preemption occurs when the iterator is locating the first matches, so the time complexity of suspending a call to GetNext() in Algorithm 3 is in O(log b (|D|)). From Proposition 5 and 6, we observe that the time complexity of suspending and resuming a preemptable index scan iterator depends on a logarithm of the size of the RDF dataset queried. As triple pattern evaluation is the basic building block of any physical SPARQL query execution plan, we conclude that we cannot meet our bound of O(|Q|) on the preemption overhead. Consequently, we propose a new target lower bound, in O(|Q| × log b (|D|)). It means that the preemption overhead must mostly depend on the number of operators required to evaluate the query Q, rather than the size of the RDF dataset.

Basic Graph pattern evaluation

The evaluation of a Basic Graph pattern corresponds to the evaluation of the natural join of a set of triple patterns. Physical join operators fall into three categories [START_REF] Garcia-Molina | Database systems -the complete book[END_REF]:

• Hash-based joins, which store data in hash tables to join results (Symmetric Hash join [START_REF] Wilschut | Dataflow Query Execution in a Parallel Main-memory Environment[END_REF], XJoin [START_REF] Urhan | XJoin: A Reactively-Scheduled Pipelined Join Operator[END_REF]).

• Sort-based joins, which take advantage of ordered relations (Merge join, ZigZag Merge join [START_REF] Garcia-Molina | Database systems -the complete book[END_REF][START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF]).

• Loop-based joins, which iterates over the inner relation in a loop fashion (Nested Loop join, Index Loop join [START_REF] Garcia-Molina | Database systems -the complete book[END_REF][START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF]).

Hash-based joins [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF][START_REF] Urhan | XJoin: A Reactively-Scheduled Pipelined Join Operator[END_REF][START_REF] Wilschut | Dataflow Query Execution in a Parallel Main-memory Environment[END_REF] operators are not suitable for preemption. As they build an in-memory hash table on one or more inputs to evaluate the join, they are full-mappings operators. However, the sort-based joins and loop joins are mapping-at-a-time operators, as they need to store only one set of solution mappings at a time in their internal state. Consequently, they are preemptible with low overhead. For sort-based joins, we can only consider merge joins, where joins inputs are already sorted on the join attribute. Otherwise, this will require to perform an in-memory sort on the inputs. In the following, we present algorithms for building preemptable Merge join and preemptable Index Loop join iterators. Preemptable Merge join The Merge join algorithm merges the solutions mappings from two join inputs, i.e., other operators that produce results sorted on the join attribute. SaGe extends the classic merge join [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] to the Preemptable Merge join iterator, as shown in Algorithm 4. The GetNext() function is very similar to its non-preemptible version [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF]: the main idea is to scan both join inputs until we found a match. We use two internal variables µ l and µ r to save the last set of solution mappings read from the inputs I lef t and I right , respectively. When the iterator needs to read new values from the inputs, we reset the values of µ l and/or µ r , which triggers recursive calls to I lef t .GetN ext() and I right .GetN ext(), respectively (Lines [START_REF] Dewitt | Nested Loops Revisited[END_REF][START_REF] Diefenbach | QAnswer: A Question Answering prototype bridging the gap between a considerable part of the LOD cloud and end-users[END_REF][START_REF] Erling | Virtuoso: RDF Support in a Native RDBMS[END_REF][START_REF] Fernández | Binary RDF representation for publication and exchange (HDT)[END_REF]. This way, we do not wrap these calls into non-interruptible sections; otherwise, we will have to wait for their completion when preemption occurs.

25 if µ l [v] = µ r [v] then 26 non interruptible 27 r ← µ l ∪ µ r 28 µ l ← nil 29 µ r ← nil 30 return r 31 else if µ l [v] < µ r [v] then
The Stop, Save, and Load functions recursively stop, save or load the joins inputs, respectively. Thus, the only internal data structures hold by the join operator are the two inputs and the last sets of solution mappings read from them. Propositions 7, 8, and 9 give the preemption overhead for this iterator.

Proposition 7. The space complexity of suspending a preemptable merge join operator M J(P 1 , P 2 ) is in O(| dom(P 1 )| + | dom(P 2 )|), where dom(P i ) is the set of variables bound in solution mappings produced by the predecessor iterator P i .

Proof. The Save() function of Algorithm 4 saves the state of both join inputs, and the last sets of solution mappings read from them. So, it space complexity is in

O(| dom(P 1 )| + | dom(P 2 )|).
Proposition 8. The time complexity of suspending a preemptable merge join operator M J(P 1 , P 2 ) is in O(S P 1 + S P 2 ), where S P i is the time complexity of suspending the iterator P i .

Proof. The non-interruptible sections of Algorithm 4 only contain assignments to local variables, so their duration is negligible. So, the time complexity of suspending the join inputs dominates the time complexity of suspending the iterator, i.e., O(S P 1 + S P 2 ). Proposition 9. The time complexity of resuming a preemptable merge join operator M J(P 1 , P 2 ) is in O(R P 1 + R P 2 ), where R P i is the time complexity of resuming the iterator P i .

Proof. The time complexity of resuming the join inputs dominates the time complexity of the Load() function from Algorithm 4, i.e., O(R P 1 + R P 2 ).

Preemptable Index Loop join The Index Loop join algorithm [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] exploits indexes on the inner triple pattern for efficient join processing. This algorithm has already been used for evaluating BGPs in [START_REF] Hartig | Executing SPARQL Queries over the Web of Linked Data[END_REF]. SaGe extends the classic Index Loop joins to a Preemptable Index join Iterator (PIJ-Iterator) presented in Algorithm 5. When executing, the iterator performs the same steps repeatedly until all solutions are produced: (1) It pulls solutions mappings µ c from its predecessor. A PIJ-Iterator supports preemption through the Stop, Save, and Load functions. The non-interruptible section of GetNext() only concerns a scan in the dataset. To save a PIJ Iterator, we keep the last set of solution mappings read from its predecessor and the state of the iterator used to scan the inner loop. And to resume such iterator, we resume the iterator of the inner loop where it was left Algorithm 5: A Preemptable Index Join Iterator I i : a preemptable join operator used by SaGe for BGP evaluation Require: I left : iterator responsible for the evaluation of the outer join input, tp r : inner join input, D: RDF dataset. Data: µ c : last set of solutions read from I left , I find : Preemptable Index Scan Iterator. 1 Function Open():

I left .Load(s) tp r ← tp if µ = nil then µ c ← µ I find ← Preemptable Index Scan Iterator over µ c (tp i ) D I find .Load(t)
reading when preemption occurred. Propositions 11, 10, and 12 give the preemption overhead for the preemptable Index Loop join iterator.

Proposition 10. The space complexity of suspending a preemptable Index Loop join iterator IJoin(P, tp) is in O(| dom(P )| + |tp| + |t|), where dom(P ) is the set of variables bound in solution mappings produced by the predecessor iterator P , and |t| and |tp| denote the size of encoding a RDF triple and a triple pattern, respectively.

Proof. The Save() function of Algorithm 5 saves the last set µ c of solutions mappings read from the predecessor, the triple pattern tp to join with, and the saved state of the preemptable Index Scan iterator I left . According to Proposition 4, the latter has a space complexity of O(|tp| + |t|). Thus, the space complexity of suspending a preemptable Index Loop join operator is in O(| dom(P )|+|tp|+|t|).

Proposition 11. The time complexity of suspending a preemptable Index Loop join iterator IJoin(P, tp) is in O(S P + log b |D|), where S P is the time complexity of suspending the iterator P .

Proof. The non-interruptible section of the GetNext() function in Algorithm 5 contains a call to the GetNext() function of a preemptable Index scan iterator. According to Proposition 5, the duration of this section is bounded in O(log b |D|). Next, the Save() method of Algorithm 5 saves the last RDF triple read by the inner loop, which is in constant time, and the predecessor P in the pipeline. So, if S P is the time complexity of suspending P , then the time complexity of suspending a preemptable Index Loop join iterator is in O(S P + log b |D|).

Proposition 12. The time complexity of resuming a preemptable Index Loop join iterator IJoin(P, tp) is in O(R P + log b |D|), where R P is the time complexity of resuming the iterator P .

Proof. The Load() method of Algorithm 5 has to resume the predecessor iterator P and resume the preemptable Index Scan iterator used to evaluate the inner loop. According to Proposition 6, the time complexity of the latter is in O(log b |D|. So, if R P is the time complexity for resuming P , then the time complexity of resuming a preemptable Index Loop join iterator is in O(R P + log b |D|).

UNION evaluation

A UNION operation is the union of solution mappings from two graph patterns. We consider a multi-set union semantic, as set unions require saving intermediate results and remove duplicates, and thus cannot be implemented as mapping-at-atime operators. The set semantics can be restored by the Smart Web client using the DISTINCT modifier on the client-side. Algorithm 6: A Preemptable Multi-Set Union Iterator M U nion(I 1 , I 2 ), merging the outputs of two iterators I 1 and I 2 .

Require: v: join variable, I 1 : left input, I 2 : right input. Data: µ 1 : last element read from I 1 , µ 2 : last element read from I 2 . 1 Function Open():

11 let s 1 ← I 1 .Save() 12 let s 2 ← I 2 .Save() 13 return s 1 , s 2 , µ 1 , µ 2 14 Function Load(s 1 , s 1 , µ 1 , µ 2 ): 15 I 1 .Load(s 1 ) 16 I 2 .Load(s 2 ) 17 µ 1 ← µ 1 18 µ 2 ← µ 2 19 Function GetNext(): 20 if µ 1 = nil ∧ I 1 .HasN ext() then 21 µ 1 ← I 1 .GetN ext() 22 else if µ 2 = nil ∧ I 2 .HasN ext() then 23 µ 2 ← I 2 .GetN ext() 24 non interruptible 25 µ ← nil 26 if µ 1 = nil then 27 µ ← µ 1 28 µ 1 ← nil 29 else if µ 2 = nil then 30 µ ← µ 2 31 µ 2 ← nil 32 return µ
Evaluating a multi-set union is equivalent to the sequential evaluation of all graph patterns in the union. Algorithm 6 gives the implementation of the Preemptable Multi-set Union iterator, which merges the output of two preemptable iterators under a multi-set semantic. It works similarly to the preemptable Merge join iterator. The GetNext() method sequentially produces all results from the first input I 1 , and then switches to the second input I 2 . As before, we use flags to notify that new sets of solution mappings must be pulled from the inputs, to avoid unnecessary non-interruptible sections. When preemption occurs, the iterator saves the state of its two inputs, and the last set of solution mappings read from them. When the iterator needs to be resumed, it reloads this information from the saved state. Propositions 14, 13, and 15 give the preemption overhead for this iterator.

Proposition 13. The space complexity of suspending a preemptable multi-set union iterator M U nion(P 1 , P 2 ) is in O(| dom(P 1 )| + | dom(P 2 )|), where dom(P i ) is the set of variables bound in solution mappings produced by the predecessor iterator P i .

A SPARQL FILTER is denoted F = σ R (P ), where P is a graph pattern, and R is a built-in filter condition. The evaluation of F yields the solutions mappings of P that verify R. The evaluation of some filter conditions requires to collect mappings, like the EXISTS filter, which involves the execution of a graph pattern. Consequently, we limit the filter condition to pure logical expressions (=, <, ≥, ∧, etc) as defined in [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF][START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF].

Algorithm 7 shows the implementation of a preemptable Filter operator, which is very similar to the preemptable projection iterator. It pulls a set of solutions mappings from its predecessor in the pipeline and forwards to the next iterator in the pipeline all sets of solutions that satisfy the logical expression R, denoted µ R [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF]. When preemption occurs, we save the predecessor, the last set of solutions read and the logical expression. Propositions 17, 16, and 18 give the preemption overhead for the preemptable filter iterator.

Proposition 16. The space complexity of suspending a preemptable filter operator

F (P, R) is in O(| dom(P )| + |R|)
, where dom(P ) is the set of variables bound in solution mappings produced by the iterator P and |R| denotes the size of encoding the logical expression R.

Proof. A preemptable filter operator saves the last set of solution mappings read from P and the logical expression evaluated by the iterator, so its space complexity is in O(| dom(P )| + |R|).

Proposition 17. The time complexity of suspending a preemptable filter operator F (P, R) is in O(S P ), where S P is the time complexity of suspending the iterator P .

Proof. The single non-interruptible section of Algorithm 7 (Lines 16 to 19) only contains assignments to local variables, so its time complexity is negligible. Next, the Save() function only needs to save its input, the set of solution mappings µ, and the logical expression R. The last two can both be saved in constant time. So, if S P is the time complexity of suspending the iterator P , then the time complexity of suspending a preemptable filter iterator F (P, R) is in O(S P ).

Proposition 18. The time complexity of resuming a preemptable filter operator F (P, R) is in O(R P ), where R P is the time complexity of resuming the iterator P .

Proof. The time complexity of resuming the iterator input dominates the time complexity of the Load() function from Algorithm 7, i.e., O(R P ).

Summary

Table 4.1 summarizes the time and space complexities of the Suspend and Resume operations for all preemptable iterators. We now compute the worst-case bounds on these operations when applied to a pipeline of preemptable iterators, i.e., a physical SPARQL query execution plan. We observe from Table 4.1 that preemptable Index Scans are the most costly preemptable iterators in regards to the preemption overhead. So, we deduce that the worst-case query for preemption is a query composed of a high number of index scans, which corresponds to a conjunctive SPARQL query evaluated using preemptable Index Loop joins.

Theorems 1, 2, and 3 give the preemption overhead for these worst-case queries. Overall, the complexity of Web preemption is higher than the initial O(|Q|) stated in Section 3.1. However, we demonstrate empirically in Section 4.4 that time and space complexity can be kept under a few milliseconds and kilobytes, respectively. Proof. A worst-case query Q is a SELECT query with a single Basic Graph Pattern B = {tp 1 , . . . , tp n }, where n = |Q|. To evaluate such query, we build a pipeline I of preemptable Index Loop join and Index Scans iterators such as I = IJoin n-1 (tp n , IJoin n-2 (tp n-1 , . . . , IJoin 1 (tp 2 , IScan(tp 1 )))). Thus, according to Propositions 4 and 10, the space complexity of suspending I is in

O(| dom(IJoin n-1 ))| + |tp n | + • • • + | dom(IJoin 1 ))| + |tp 2 | + |tp 1 |)
But we know that, as we progress in the pipeline of join iterators, the number of bound variables increases, i.e., dom(P 1 P 2 ) = dom(P 1 ) ∪ dom(P 2 ). Proof. As with the previous proofs, we consider a pipeline I of preemptable Index Loop join and Index Scans iterators for evaluating the worst-case query. According to Propositions 6 and 12, the time complexity of resuming I is in

O(log b |D| +R IJoin 1 + • • • + R IJoin n-1 ) = O(log b |D| + log b |D| + • • • + log b |D|) = O(|Q| × log b |D|)

The SaGe Smart Web client

The SaGe approach requires a Smart Web client for processing SPARQL queries for two reasons. First, the client must be able to continue query execution after receiving a saved plan from the server. Second, as the preemptable server only implements a fragment of SPARQL, the smart Web client has to implement the missing operators to support full SPARQL queries. It includes SERVICE, ORDER BY, GROUP BY, DISTINCT, MINUS, FILTER EXIST, and aggregations (COUNT, AVG, SUM, MIN, MAX), but also , ∪, and π to be able to recombine results obtained from the SaGe server. Consequently, the SaGe smart client is a SPARQL query engine that accesses RDF datasets through the SaGe server. Given a SPARQL query, the SaGe client parses it into a logical query execution plan, optimizes it and then builds its own physical query execution. The leafs of the plan must correspond to subqueries evaluable by a SaGe server. Compared to a SPARQL endpoint, processing SPARQL queries with the SaGe smart client has an overhead in terms of the number of requests sent to the server and transferred data2 . With a SPARQL endpoint, a web client executes a query by sending a single web request and receives only query results. The smart client overhead for executing the same query is the additional number of requests and data transferred to obtain the same results. Consequently, the client overhead has two components:

• The number of requests: To execute a SPARQL query, a SaGe client needs n ≥ 1 requests. We distinguish two cases: 1) The SaGe server supports the evaluation of the query, so n is equal to the number of time quantum required to process the query. latency twice per request.

2) The SaGe server does not support the evaluation of the query. Then, the client decomposes the query into a set of subqueries supported by the server, evaluate each subquery as in the first case, and recombine intermediate results to produce query results.

• Data transfer: We also distinguish two cases: 1) If the SaGe server supports the evaluation of the query, the only overhead is the size of the saved plan S i multiplied by the number of requests. Notice that the saved plan S i can be returned by reference or by value, i.e., saved server-side or client-side.

2) Otherwise, the client decomposes the query and recombines the results of subqueries. Among these results, some are intermediate results and part of the client overhead.

Consequently, the challenge for the smart client is to minimize the overhead in terms of the number of requests and transferred data. Of course, the data transfer can be reduced by using a stateful Web Preemption, but, as stated earlier, we choose a stateless implementation to preserve the scalability and fault-tolerance properties.

Experimental setup

Dataset and Queries: We use the Waterloo SPARQL Diversity Benchmark (WatDiv5 ) [4]. We re-use the RDF dataset and the SPARQL queries from the BrTPF [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF] experimental study 6 . The dataset contains 10 7 triples, and we arrange queries in 50 workloads of 193 queries each. They are SPARQL conjunctive queries with STAR, PATH, and SNOWFLAKE shapes. They vary in complexity, up to 10 joins per query with very high and very low selectivity. 20% of queries are executed in more than ≈ 30s to be executed using the Virtuoso server. All workloads follow nearly the same distribution of query execution times, as presented in Figure 4.5, where we measured the query execution times for one workload of 193 queries with SaGe and an infinite time quantum.

Approaches: We compare the following approaches:

• SaGe: We run the SaGe query engine with various time quantums: 75ms and 1s, denoted SaGe-75ms and SaGe-1s, respectively. HDT indexes are loaded in memory while HDT data is stored on disk.

• Virtuoso: We run the Virtuoso SPARQL endpoint [START_REF] Erling | Virtuoso: RDF Support in a Native RDBMS[END_REF] (v7.2.4), without any quotas or limitations.

• TPF: We run the standard TPF client (v2.0.5) and TPF server (v2.2.3) with HDT files as backend (same settings as SaGe).

• BrTPF: We run the BrTPF client and server used in [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF], with HDT files as backend (same settings as SaGe). BrTPF is currently the LDF approach with the lowest data transfer [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF].

Servers configurations:

We run all the servers on a machine with Intel(R) Xeon(R) CPU E7-8870@2.10GHz and 1.5TB RAM.

Clients configurations: To generate load over servers, we rely on 50 clients, each one executing a different workload of queries. All clients start executing their workload simultaneously. The clients access servers through HTTP proxies to ensure that client-server latency is around 50ms.

Evaluation Metrics: Presented results correspond to the average obtained of three successive execution of the queries workloads.

• Workload completion time (WCT): is the total time taken by a client to evaluate a set of SPARQL queries, measured as the time between the first query starting and the last query completing.

• Time for first results (TFR) for a sage:query: is the time between the query starting and the production of the first query's results.

• Time preemption overhead : is the total time taken by the server's Suspend and Resume operations.

• The number of HTTP requests: is the total number of HTTP requests sent by a client to a server when executing a SPARQL query.

• The data transfer : is the quantity of transferred bytes when executing a SPARQL query.

Experimental results

We first ensure that the SaGe approach yields complete results. We run both Virtuoso and SaGe and verify that, for each query, SaGe delivers complete results using Virtuoso results as ground truth.

What is the overhead in time of Web preemption? The overhead in time of Web preemption is the time spent by the Web server for suspending a running query and the time spent for resuming the next waiting query. To measure the overhead, we run one workload of queries using SaGe-75ms and measure time elapsed for the Suspend and Resume operations. time for SaGe Suspend and Resume operations using different sizes of the WatDiv dataset. Generally, the size of the dataset does not impact the overhead, which is around 1ms for Suspend and 1.5ms for Resume. As expected, the overhead is greater for the Resume operation than the Suspend operation, due to the cost of resuming Index scans in the plan. With a quantum of 75ms, the overhead is ≈ 3% of the quantum, which is negligible.

What is the overhead in space of Web preemption? The overhead in space of the Web preemption is the size of saved plans produced by the Suspend operation.

According to Section 4.2, we determined that the SaGe physical query plans can be saved in O(|Q|). To measure the overhead, we run a workload of queries using SaGe-75ms and measure the size of saved plans. We compress saved plans using Google Protocol Buffers7 . Table 4.2 shows the overhead in space for SaGe. As we can see the size of a saved plan remains very small, with no more than 6 kb for a query with ten joins. Hence, this space is indeed proportional to the size of the plan suspended.

Does Web preemption improve the average workload completion time?

The SaGe server has a restricted choice of physical query operators, so physical query execution plans generated by the SaGe server should be less performant than those produced by Virtuoso. This tradeoff only makes sense if the Web preemption compensates for the loss in performance. Compensation is possible only if the workload alternates long-running and short running queries. In the setup, each client runs a different workload of 193 queries that vary from 30s to 0.22s, following an exponential distribution. All clients execute their workload concurrently and start simultaneously. We experiment up to 50 concurrent clients by step of 5 clients.

As there is only one worker on the Web server and queries execution times vary, this setup is the worst case for Virtuoso. Figure 4.7 shows the average workload completion time obtained for all approaches, with a logarithmic scale. As expected, the convoy effect significantly impacts Virtuoso, and it delivers the worse WTC after 20 concurrent clients. TPF and BrTPF avoid the convoy and behave similarly. BrTPF is more performant thanks to its bind-join technique that group requests to the server. SaGe-75ms and SaGe-1s avoid the convoy effect and delivers better WTC than TPF and BrTPF. As expected, increasing the time quantum also increases the probability of convoy effect, and, globally, SaGe-75ms offers the best WTC. We rerun the same experiment with four workers for SaGe-75ms and Virtuoso. Figure 4.8 shows the average workload completion time obtained for both approaches. As we can see, both approaches benefit from the four workers. However, Virtuoso still suffers from the convoy effect. Does Web preemption improve the time for the first results? The Time for first results (TFR) for a query is the time between the query starting and the production of the first query's results. Web preemption should provide better a time for the first results. Avoiding the convoy effect allows us to start queries earlier 4.4 shows the results when evaluating OPTIONAL queries with OptJoin and BindLeftJoin approaches. We observe that, in general, OptJoin outperforms BindLeftJoin. Furthermore, OptJoin is improved when using a higher quantum, as the single subquery sent is evaluated more quickly. It is not the case for BindLeftJoin, as the number of requests still depends on the number of intermediate results.

Finally, we re-use 166 SELECT queries from Feasible [START_REF] Saleem | FEASIBLE: A Feature-Based SPARQL Benchmark Generation Framework[END_REF] with the DBpedia 3.5.1 dataset, generated from real-users queries. We excluded queries that time-out, identified in [START_REF] Saleem | FEASIBLE: A Feature-Based SPARQL Benchmark Generation Framework[END_REF], and measure the number of requests sent to the server. Table 4.3 shows the results. Of course, Virtuoso just send 166 requests to the server. We observe that the ratio of requests between SaGe-75 and TPF is nearly the same as the previous experiment. However, the marge between SaGe-1s and SaGe-75ms decrease, because most requests sent are produced by the decomposition of OPTIONAL and FILTER and not by the evaluation of BGPs.

Chapter 5 Conclusion

Summary of contributions

In this thesis, we choose to tackle the issue of building public SPARQL query servers that allows any data consumers to execute any SPARQL query with complete results while remaining available. Existing approaches ensure availability using a quota policy that restricts query execution. By following an approach based on time-sharing, similar to those used in operating systems, we made the following hypothesis We hypothesize that the issue related to quotas is not interrupting a query, but the impossibility for the client to resume the query execution afterward.

Based on this, we proposed a new query execution model called Web Preemption. Web preemption is the capacity of a Web server to suspend a running query after a time quantum with the intention to resume it later. When suspended, the server sends the saved state S i of the query to the Web client. Then, the client can resume query execution by sending S i back to the Web server. Compared to existing query execution models, Web Preemption ensures a fair allocation of Web server resources across queries, a better average query completion time per query, and a better time for first results.

This approach is original, as no other approach tackles the issue of time-sharing at the scale of SPARQL queries running in a public server. However, our new model adds an overhead for the Web server to suspend the running query and resume the next waiting query. Consequently, the next scientific challenge is to keep this overhead marginal, whatever the running SPARQL queries, to ensure good query execution performance.

SaGe is a SPARQL query engine that implements the Web Preemption model. To minimize the preemption overhead, SaGe distributes SPARQL query execution between a preemptive SPARQL query server and a smart Web client. The first supports the evaluation of all operators that can be suspended and resumed with a low preemption overhead, while the second supports the evaluation of all remaining operators. This way, SaGe supports allows for the execution of any SPARQL 1.1 query. Compared to SPARQL endpoint approaches without quotas, SaGe avoids the convoy effect and is a winning bet as soon as the queries of the workload vary in execution time. Compared to LDF approaches [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF][START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF], SaGe offers a more expressive server interface with join, union, and filter evaluated on the server side. Consequently, it considerably reduces data transfer and the communication cost, improving the execution time of SPARQL queries.

Perspective works

This section details the perspective works following the contributions of this thesis.

Updating Knowledge Graphs under the Web preemption model

A public SPARQL query server can receive two types of queries: read-only queries sent by data consumers to query the RDF dataset, and read-write queries sent by the data provider to update the hosted RDF data. In SaGe, we made the hypothesis that the server only receives read-only queries, but we could extend our model to supports the concurrent evaluation of both types of SPARQL queries. In database systems, the concurrent execution of read-only and read-write queries can lead to data consistency issues: if two queries are updating the same RDF triples, what happens? It is the goal of the database's concurrency control system [START_REF] Bernstein | Concurrency Control and Recovery in Database Systems[END_REF] to handle these issues, by imposing a set of constraints, called consistency criteria, that dictate how concurrent queries are executed [START_REF] Perrin | Distributed systems: concurrency and consistency[END_REF]. A query whose execution violates these constraints generates a conflict and is often aborted and rescheduled for execution. The most common consistency criterion is serializability [START_REF] Bernstein | Concurrency Control and Recovery in Database Systems[END_REF][START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF], implemented using database transactions. Each query is wrapped inside a transaction, and while it is executing, its results are not available to other concurrent queries. When a transaction completes, the concurrency control system invokes an algorithm called atomic commitment to ensure that all operations made by the transaction can be applied as a single unit of computation to the data.

In the context of Web Preemption, concurrency control is a challenging issue because it is impossible to suspend the atomic commitment algorithm. Indeed, this algorithm must run as a non-interruptible section, as it acquires locks on each data item that will be updated by the transaction. While the lock granularity can be very small [START_REF] Jacyntho | A multigranularity locking model for RDF[END_REF][START_REF] Neumann | x-RDF-3X: Fast Querying, High Update Rates, and Consistency for RDF Databases[END_REF], a transaction always needs to acquire locks, and it will only release them when it completes. So, locks cannot be released when preemption occurs, which generates convoy effects for long-running transactions, as reported by Blasgen et al. in [START_REF] Blasgen | The Convoy Phenomenon[END_REF].

We think that this issue can be solved by performing two modifications to the Web preemption model. First, we think that using two distinct pool of workers, one for each type of query, can remove convoy effects between read-write and read-only queries. Next, we need to ensure that read-only queries can always read a consistent snapshot of the database. However, a concurrent query might delete the information required to resume preemptable iterators. We think that a new multi-version concurrency control algorithm [START_REF] Bernstein | Concurrency Control and Recovery in Database Systems[END_REF][START_REF] Neumann | x-RDF-3X: Fast Querying, High Update Rates, and Consistency for RDF Databases[END_REF] can be developed, to ensure consistent reads under the Web preemption model.

Web Preemption for Web-querying languages

In this work, we implemented the Web Preemption model for the evaluation of SPARQL queries. But we could consider the execution of queries in other languages under the same model. GraphQL [39] is a recently proposed, and increasingly adopted, framework for providing a new type of data access interface on the Web. A core component of the GraphQL framework is a query language for expressing the data retrieval requests issued to GraphQL-aware Web servers, as in a graph-oriented database. However, as reported in [39], GraphQL query servers also face the issue of convoy effects and solve it using quotas. For example, Github enforces severe limitations on its GraphQL API1 and does not allow for complex queries or more than 5 000 authenticated requests per hour. We think that a preemptive GraphQL server could solve these issues like SaGe did for SPARQL queries. The challenges are the same as in SaGe: build preemptive GraphQL physical query operators to minimize the preemption overhead. Since most operators of the GraphQL language have SPARQL equivalents [START_REF] Taelman | GraphQL-LD: Linked Data Querying with GraphQL[END_REF], we think that we can obtain results close to those of SaGe.

Optimize client-side query processing for Smart Web clients

The SaGe Smart Web Client acts as a client-side SPARQL query engine that distributes query processing between the server and the client. In this thesis, we do not look at some unusual challenges regarding this execution workflow. First, we could extend the SPARQL optimizer used by the client to compute the optimal distribution of query processing between the client and the server, i.e., which subplans to ship to the SaGe server to minimize data transfers and SPARQL query execution times. It is a challenging issue because the client does not have access to the same statistics as the SaGe server. So, it will have to download histograms from the server, which increases the data transferred. To solve it, we could rely on adaptive query processing techniques [START_REF] Avnur | Eddies: Continuously Adaptive Query Processing[END_REF][START_REF] Deshpande | Adaptive Query Processing[END_REF] for client-side SPARQL processing. Federated SPARQL query processing [3] and smart LDF clients [2] successfully applied similar methods to perform on-the-fly query optimization without having to download too much statistics from the server.

Next, we could propose new rewriting techniques, like the OptJoin technique, to optimize the evaluation of full-mappings SPARQL operators. Aggregations operators (GROUP BY, COUNT, AVG, . . . ) are good candidates, as they are crucial to compute statistics over the Linked Data using SPARQL queries [START_REF] Hasnain | SPORTAL: Profiling the Content of Public SPARQL Endpoints[END_REF][START_REF] Soulet | Anytime Large-Scale Analytics of Linked Open Data[END_REF]. We think that an approach similar to Map-Reduce [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF][START_REF] Jesus | A Survey of Distributed Data Aggregation Algorithms[END_REF] is feasible to compute SPARQL aggregations more efficiently. The SaGe server will only compute partial aggregations over solutions mappings produced during a quantum. Then the smart client will merge partial results using client-side reducing functions to produce the final query results. This approach could drastically reduce the data transferred and the number of HTTP requests, speeding up the overall SPARQL query execution. However, distinct aggregations might create issues in terms of data transfer, as they need to deduplicate data beforehand, which requires to materialize the complete query results. utilisateurs à répondre à des questions complexes en utilisant le Web des données. Par exemple, si nous voulons obtenir la liste de tous les acteurs de cinéma, nous devons télécharger l'ensemble des documents RDF qui contiennent des triplets intéressants, ce qui est une opération complexe et très coûteuse en temps. Pour pallier à ce problème, une collection de documents RDF peut également être hébergée par un SPARQL endpoint, un système de bases de données spécialisé qui permet d'exécuter des requêtes complexes sur des triplets RDF. Les utilisateurs peuvent envoyer, via le protocole HTTP, des requêtes SPARQL, qui sont des requêtes type SQL qui permettent à l'utilisateur d'interroger des documents RDF via un langage de requête structuré. Par exemple, le DBpedia SPARQL endpoint1 permet à n'importe qui d'exécuter des requêtes sur le jeu de données DBpedia, qui contient des milliards de faits récupérés depuis Wikipedia [START_REF] Auer | DBpedia: A Nucleus for a Web of Open Data[END_REF]. La figure A.1 montre une requête SPARQL qui trouve tous les auteurs et leurs livres dans DBpedia.

Les services publics d'évaluations de requêtes SPARQL, comme les SPARQL endpoints, sont très importants pout le Web des données, car ils permettent de développer des applications qui ré-utilisent les milliards de triplets RDF disponibles dans le LOD. Par exemple, les SPARQL endpoints de DBpedia [START_REF] Auer | DBpedia: A Nucleus for a Web of Open Data[END_REF] et Wikidata [START_REF] Vrandecic | Wikidata: a free collaborative knowledgebase[END_REF] sont tous les deux utilisés comme bases de connaissances par des systèmes questionsréponses multilingues [START_REF] Diefenbach | QAnswer: A Question Answering prototype bridging the gap between a considerable part of the LOD cloud and end-users[END_REF][START_REF] Tanon | Demoing Platypus -A Multilingual Question Answering Platform for Wikidata[END_REF] et des agents conversationnels [START_REF] Athreya | Enhancing Community Interactions with Data-Driven Chatbots-The DBpedia Chatbot[END_REF]. Cependant, fournir un service public qui permet à n'importe quel utilisateur d'exécuter n'importe quelle requête SPARQL est encore un problème ouvert [START_REF] Aranda | SPARQL Web-Querying Infrastructure: Ready for Action?[END_REF]. Étant donné que ces services sont soumis à une charge imprévisible de requêtes SPARQL, le défi est d'assurer qu'ils restent disponibles malgré des variations dans les taux d'arrivée des requêtes et des ressources à leur disposition. Les fournisseurs de données se réfèrent souvent à ce défi comme la mise en place d'une politique d'accès équitable.

Pour mettre en place ce type de politique d'accès, la plupart des SPARQL endpoints sont configurés avec des politiques de quotas qui garantissent un partage équitable des ressources entre les utilisateurs. Si une requête SPARQL dépasse l'un de ces quotas, elle est interrompue par le serveur et l'utilisateur qui l'a émise reçoit une erreur. Il existe de nombreux types de quotas, mais les restrictions les plus communes concernent: 1) Le temps d'exécution des requêtes SPARQL, 2) Le nombre de résultats obtenus par requête, et 3) Le taux d'envoi de requêtes par adresse IP. Par exemple, le SPARQL endpoint de DBpedia ne permet pas d'exécuter des requêtes pendant plus de 120 secondes ou qui obtiennent plus de 10000 résultats2 . De plus, il ne permet pas plus de 50 connexions parallèles et plus de 100 requêtes HTTP par seconde par adresse IP.

Certains de ces quotas ne sont pas perturbants pour les utilisateurs, e.g., si le taux d'arrivée des requête est restreint, alors il suffit de réessayer plus tard. Cependant, les limites sur les temps d'exécution ou le nombre de résultats obtenus conduisent les services d'évaluation de requêtes à ne délivrer que des résultats partiels. Il s'agit d'une limite importante à l'utilisation de ces services, car il devient alors impossible de développer des applications basées dessus [START_REF] Polleres | A More Decentralized Vision for Linked Data[END_REF].

Cependant, sans ces politiques de quotas, les SPARQL endpoints deviennent sujet à un phénomène appelé effet convoi [START_REF] Blasgen | The Convoy Phenomenon[END_REF] car ils exécutent les requêtes entrantes en suivant une politique First-Come First-Served (FCFS) [START_REF] Fife | R68-47 Computer Scheduling Methods and Their Countermeasures[END_REF]. Commes les requêtes sont exécutées dans leur ordre d'arrivée au serveur, une requête longue peut occuper l'intégralité des ressources du serveur et empêcher les autres requêtes, même courtes, de s'exécuter.

Dans l'état actuel du LOD, nous somme donc face à un dilemne. D'un côté, nous pouvons construire un service d'évaluation de requêtes SPARQL performant grâce aux politiques de quotas, mais il peut fournir des résultats incomplets aux utilisateurs. De l'autre, nous pouvons construire un service qui fournit toujours des résultats complets, mais dont la disponibilité n'est pas garantie du fait des effets convois. Aucune de ces deux solutions n'est acceptable pour développer des applications basées sur le Web des données, car les développeurs ont besoin de services à la fois disponibles et qui délivrent toujours des résultats complets.

A.1.2 Contributions et contenu de cette thèse

Dans cette thèse, nous proposons de résoudre le problème relatif à la construction des services publics d'évaluation de requêtes SPARQL qui permettent à n'importe quel utilisateur d'exécuter n'importe quelle requête SPARQL en obtenant des résultats complets. Pour ce faire, nous proposons deux contributions. La première est un nouveau modèle d'exécution pour les requêtes SPARQL, dénommé la préemption Web, qui s'inspire des travaux sur les processeurs à temps partagé [START_REF] Anderson | Operating Systems: Principles and Practice[END_REF]. La préemption Web est la capacité d'un serveur Web à suspendre l'exécution d'une requête SPARQL après un temps donné, avec l'intention d'en reprendre l'exécution ultérieurement. Une fois suspendu, l'état S i de l'exécution est renvoyé au client qui a émis la requête, et il pourra en reprendre l'exécution en renvoyant S i au serveur. Comparée aux modèles existants, la préemption Web permet de garantir une allocation équitable des ressources du serveur entre les utilisateurs, un meilleur temps moyen d'exécution des requêtes et un meilleur temps d'obtention des premiers résultats.

Cependant, notre nouveau modèle d'exécution ajoute un surcoût au Web serveur, pour suspendre une requête en cours d'exécution et reprendre l'exécution de la suivante. Donc, le défi scientifique est de maintenir ce surcoût au minimum, pour garantir les meilleurs performances d'exécution des requêtes SPARQL. A ces fins, nous proposons SaGe, un moteur préemptif d'évaluation de requêtes SPARQL qui implémente le modèle de la préemption Web. Nous définissons un ensemble d'opérateurs interruptibles, utilisés pour évaluer les requêtes SPARQL, pour lesquels nous bornons le surcoût de préemption. Ces opérateurs permettent de construire un serveur Web préemptif qui supporte l'exécution d'une grande partie du langage de requête SPARQL. Étant donné que tous les opérateurs n'ont pas un surcoût de préemption raisonnable, nous divisons le moteur SaGe en deux composants : un serveur SPARQL préemptif, qui utilise nos opérateurs interruptibles pour exécuter des requêtes SPARQL selon le modèle de la préemption Web, et un client intelligent, qui exécute côté client les opérations non supportées par le serveur. En combinant ces deux composants, nous permettons l'évaluation de l'ensemble du langage de requête SPARQL selon notre nouveau modèle d'exécution.

Enfin, nous proposons une étude expérimentale complète du moteur SaGe (client et serveur), pour le comparer aux approches existantes utilisées pour construire des services publics d'évaluation de requêtes SPARQL. Nos résultats expérimentaux démontrent que SaGe est plus performant que les approches existantes, aussi bien en termes de temps moyen d'exécution des requêtes que de temps d'obtention des premiers résultats.

A.2 Le modèle d'exécution de la Préemption Web

Le modèle d'exécution de la préemtpion Web se définit formellement comme suit. Nous considérons un serveur Web préemptif, qui héberge un jeu de données RDF en lecture seule, et un client Web intelligent, qui évalue des requêtes SPARQL en utilisant le serveur. Ce dernier possède un ensemble de workers, tous paramétrés avec un même quantum de temps, qui sont chargés d'exécuter les requêtes. Le serveur possède également une file d'attente qui enregistre les requêtes entrantes lors tous les workers sont occupés. Nous considérons une population infinie de Pour réduire le surcoût de préemption de certains opérateurs physiques, nous choisissons de les répartir entre un serveur SaGe et un client intelligent SaGe. Comme proposé dans l'approche LDF [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF][START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF], la combinaison du serveur et du client intelligent permet l'exécution n'importe quelle requête SPARQL. La répartition des opérateurs est la suivante :

• Les opérateurs de type "mapping-at-a-time" ont un surcoût relativement faible, ils sont donc supportés par le serveur SaGe. Ces opérateurs forment un sous-ensemble de CoreSPARQL [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF], composé des opérateurs Triple Patterns, Basic Graph Pattern UNION, FILTER et SELECT.

• Les opérateurs de type "full-mappings" ont un surcoût trop élevés en moyenne, ils sont donc implementé dans le client intelligent SaGe. Il s'agit des opérateurs OPTIONAL, SERVICE, ORDER BY, GROUP BY, DISTINCT, MINUS, FILTER EXIST, ainsi que les opérateurs d'aggrégation (COUNT, AVG, SUM, MIN, MAX).

La table A.1 résume les complexités en temps et en espace des opérations Suspend et Resume pour tous les opérateurs. Nous observons que les opérateurs interruptibles Index Scans sont les plus coûteux vis à vis de la préemption Web. De manière générale, les complexité en temps et espace sont supérieures à notre cible initiale en O(|Q|). Néanmoins, nos résultats expérimentaux (Section 4.4) démontrent qu'en pratique, le surcoût en temps est inférieur à quelques millisecondes et celui en espace à quelques kilobytes.

Comparé aux SPARQL endpoints qui utilisent des politiques de quotas, SaGe évite les effets convois et c'est un pari gagnant dès le moment où les temps d'exécutions des requêtes SPARQL varient significativement. Comparé à des approches LDF [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF][START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF], SaGe offre une interface serveur plus expressive, avec le support de jointures, unions et filtres évalués côté serveur. En conséquence, il réduit considérablement le transfert de données entre client et serveur, ainsi que le coût de communication, améliorant le temps d'exécution des requêtes SPARQL.

La Préemption Web pour interroger le Web des Données

Mots-clés : Web sémantique • Gestion des données liées • Serveurs SPARQL publics Résumé : en suivant les principes du Linked Open Data, les fournisseurs de données ont publié des milliards de documents RDF via des services publics d'évaluation de requêtes SPARQL. Pour garantir la disponibilité et la stabilité de ces services, ils appliquent des politiques de quotas sur l'utilisation des serveurs. Les requêtes qui excèdent ces quotas sont interrompues et ne renvoient que des résultats partiels. Cette interruption n'est pas un problème s'il est possible de reprendre l'exécution des requêtes ultérieurement, mais il n'existe aucun modèle de préemption le permettant. Dans cette thèse, nous proposons de résoudre le problème relatif à la construction des services qui permettent à n'importe quel utilisateur d'exécuter n'importe quelle requête SPARQL en obtenant des résultats complets. Nous proposons la préemption Web, un nouveau modèle d'exécution qui permet l'interruption de requêtes SPARQL après un quantum de temps, ainsi que leur reprise sur demande des clients. Nous proposons également SaGe, un moteur d'évaluation de requêtes SPARQL qui implémente la préemption Web tout en garantissant un surcoût de préemption minimal. Nos résultats expérimentaux démontrent que SaGe est plus performant que les approches existantes, en termes de temps moyen d'exécution des requêtes et d'obtention des premiers résultats.

Web Preemption for Querying the Linked Open Data Keywords : Semantic Web • Linked Data Management • Public SPARQL servers Abstract: Following the Linked Open Data principles, data providers have published billions of RDF documents using public SPARQL query services. To ensure these services remains stable and responsive, they enforce quotas on server usage. Queries which exceed these quotas are interrupted and deliver partial results. Such interruption is not an issue if it is possible to resume queries execution afterward. Unfortunately, there is no preemption model for the Web that allows for suspending and resuming SPARQL queries. In this thesis, we propose to tackle the issue of building public SPARQL query servers that allow any data consumer to execute any SPARQL query with complete results. First, we propose a new query execution model called Web Preemption. It allows SPARQL queries to be suspended by the Web server after a fixed time quantum and resumed upon client request. Web preemption is tractable only if its cost in time is negligible compared to the time quantum. Thus, we propose SaGe: a SPARQL query engine that implements Web Preemption with minimal overhead. Experimental results demonstrate that SaGe outperforms existing SPARQL query processing approaches by several orders of magnitude in term of the average total query execution time and the time for first results.

Figure 1 . 1 :

 11 Figure 1.1: Turtle representation of RDF data about Neil Gaiman, retrieved from DBpedia [9].

Figure 1 . 2 :

 12 Figure 1.2: The LOD cloud diagram, as of March 2019.

Figure 1 . 3 :

 13 Figure 1.3: A SPARQL query that finds all authors and their books in the DBpedia dataset.

Figure 2 . 1 :

 21 Figure 2.1: Turtle representation of RDF data about Neil Gaiman and the book Good Omens and American Gods, retrieved from DBpedia.

Figure 2 . 3 :

 23 Figure 2.3: A SPARQL query that finds all authors with their names and the titles of their books.

Figure 2 . 4 :

 24 Figure 2.4: Storing RDF data from Figure 2.1 using a triple-store with three clustered indexes: SPO, POS and OSP.

Figure 2 . 5 :

 25 Figure 2.5: Storing RDF data from Figure 2.1 using property tables.

Figure 2 . 6 :

 26 Figure 2.6: Overview of SPARQL query processing

tp 1 :Figure 2 . 7 :

 127 Figure 2.7: Join query graph and logical query execution plan of SPARQL query Q 1 from Figure 2.3.

Figure 2 . 11 :

 211 Figure 2.11: Basic Graph Pattern evaluation using the TPF Smart client[START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF]

Figure 2 . 12 :

 212 Figure2.12: Execution of three SPARQL queries using the First-Come First-Served (FCFS) execution policy[START_REF] Fife | R68-47 Computer Scheduling Methods and Their Countermeasures[END_REF]

3 = 13

 313 seconds, an average query completion time of 20+25+30

Figure 2 . 13 :

 213 Figure 2.13: Execution of the three SPARQL queries from Figure 2.12 using the Round Robin scheduling policy.

Figure 3 . 1 :

 31 Figure 3.1: Possible states of query execution in a preemptive Web Server.

Figure 3 . 2 : 3 = 9 . 3 3 = 23 . 3 3 =

 3239332333 Figure 3.2: First-Come First-Served (FCFS) policy compared to Web Preemption (time quantum of 10s and overhead of 3s).

Figure 4 . 1 :

 41 Figure 4.1: SPARQL query Q 3 , from the WatDiv benchmark [4].

= 2 i

 2 µ c = { ?v0 → wm:Offer81505, ?v1 → wm:Product11, ?v3 → "4355" } Index Loop join µ c = { ?v1 → wm:Product12, ?v3 → "4356" } Index Scan tp 2 D t i = 224 s o u r c e Index Scan µ c (tp 1 ) D t i

Figure 4 . 2 :Algorithm 1 : 2 let root←first iterator in I 3 Call

 42123 Figure 4.2: A tree representation of a page returned by the SaGe server when executing SPARQL query Q 3 with the saved plan passed by value.

Algorithm 2 : 2 I

 22 A Preemptable Projection Iterator π V (P ) Require: V : set of projection variables, I: predecessor in the pipeline Data: µ: set of solution mappings 1 Function Open():

Proposition 1 .

 1 The space complexity of suspending a preemptable projection iterator π V (P ) is in O(|V | + | dom(P )|), where dom(P ) is the set of variables bound in solution mappings produced by the predecessor iterator P . Proof. The Save() function in Algorithm 2 saves the set of variables V and the current value of the local variable µ, which can either be nil or a set of solution mappings read from the predecessor iterator P . The space complexity of a set of solution mappings µ is in O(|dom (µ)|). So if we consider dom(P ) as the set of variables bound in solution mappings produced P , the space complexity of the Suspend() operation in Algorithm 2 is in O(|V | + | dom(P )|).

Proposition 4 .Proposition 5 .

 45 The space complexity of suspending a preemptable index scan iterator IScan(tp) is in O(|tp| + |t|), where |tp| and |t| denote the size of encoding a triple pattern and a RDF triple, respectively.Proof. The Save() function of Algorithm 3 saves the triple pattern evaluated, and the last RDF triple read before preemption occurs. Thus, its space complexity is in O(|tp| + |t|). The time complexity of suspending a preemptable index scan iterator IScan(tp) is in O(log b (|D|)), where b is the B+-tree order and D is the RDF dataset queried.

Proposition 6 .

 6 The time complexity of resuming a preemptable index scan iterator IScan(tp) is in O(log b (|D|)), where b is the B+-tree order and D is the RDF dataset queried. Proof. The Load() function of Algorithm 3 resumes triple pattern evaluation by locating the last RDF triple read before preemption occurs. As seen in the proof of Proposition 5, such lookup is in O(log b (|D|)).

Algorithm 4 : 2 µ l ← nil 3 µ r ← nil 4 Function 5 I 6 I 8 I 9 I 15 I 16 I 17 µ l ← µ l 18 µ r ← µ r 19 Function

 423456891516171819 A Preemptable Merge Join Iterator M Join, joining the output of two iterators I left and I right . Require: v: join variable, I left : outer join input, I right : inner join input. Data: µ l : last element read from I left , µ r : last element read from I right . 1 Function Open(): Close(): left .Close() right .Close() 7 Function Stop(): left .Stop() right .Stop() 10 Function Save(): 11 let s l ← I left .Save() 12 let s r ← I right .Save() 13 return s l , s r , µ l , µ r 14 Function Load(s l , s r , µ l , µ r ): left .Load(s l ) right .Load(s r ) GetNext(): 20 while I left .HasN ext() ∧ I right .HasN ext() do 21 if µ l = nil then 22 µ l ← I left .GetN ext() 23 if µ r = nil then 24 µ r ← I right .GetN ext()

( 2 )

 2 It applies µ c to tp i to generate a bound pattern b = µ c (tp i ). (3) If b has no solution mappings in D, it tries to read again from its predecessor (jump back to Step 1). (4) Otherwise, it reads RDF triples matching b in D, produces the associated set of solution mappings, and then goes back to Step 1.

2 I 3 µ c ← nil 4 I 6 I 7 I

 23467 left .Open() find ← Preemptable Index Scan Iterator over ∅ 5 Function Close(): left .Close() find .Close() 8 Function GetNext(): 9 while ¬I find .HasN ext() do µ c ← I left .GetN ext() if µ c = nil then return nil I find ← Preemptable Index Scan Iterator over µ c (tp r ) D non interruptible let µ ← I find .GetN ext() return µ ∪ µ c Function Stop(): I left .Stop() I find .Stop() Function Save(): let s ← I left .Save() let t ← I find .Save() return s, tp r , µ c , t Function Load(s, tp , µ , t):

2 µ 1 ← nil 3 µ 2 ← nil 4 Function 5 I 1 . 6 I 2 . 8 I 1 . 9 I 2 .

 2132451628192 Close(): Close() Close() 7 Function Stop(): Stop() Stop() 10 Function Save():

Theorem 1 .

 1 The space complexity of suspending a preemptable physical query execution plan is in O(| dom(Q)| + |Q| × |tp|), where dom(Q) is the set of variables bound in solution mappings produced by the evaluation of Q, |Q| denotes the number of operators in the plan and |tp| denotes the size of encoding a triple pattern.

Theorem 3 .

 3 So, we have | dom(IJoin 1 ))| | dom(IJoin 2 ))| • • • | dom(IJoin n-1 )|, which allows us to simplify the complexity asO(| dom(IJoin n-1 )| + |tp n | + |tp n-1 | + • • • + |tp 1 |) = O(| dom(Q)| + |Q| × |tp|)Theorem 2. The time complexity of suspending a preemptable physical query execution plan is in O(|Q| × log b |D|), where |Q| denotes the number of operators in the plan, b is the order of the B+-trees used and D is the RDF dataset queried.Proof. As with the previous proof, we consider a pipeline I of preemptable Index Loop join and Index Scans iterators for evaluating the worst-case query. According to Propositions 5 and 11, the time complexity of suspending I is inO(log b |D| +S IJoin 1 + • • • + S IJoin n-1 ) = O(log b |D| + log b |D| + • • • + log b |D|) = O(|Q| × log b |D|)The time complexity of resuming a preemptable physical query execution plan is in O(|Q| × log b |D|), where |Q| denotes the number of operators in the plan, b is the order of the B+-trees used and D is the RDF dataset queried.

Figure 4 .

 4 4 shows the execution plan build by the SaGe client for executing query Q 3 , from Figure 4.3.

Figure 4 . 3 :

 43 Figure 4.3: SPARQL query Q 3 : finds all actors with their names and their birth places, if they exist.

Figure 4 . 4 :

 44 Figure 4.4: Physical query execution plan used by the SaGe smart Web client for executing query Q 3 .

Figure 4 . 5 :

 45 Figure 4.5: Distribution of query execution time.

Figure 4 .6 shows the overhead in 1 1. 5

 415

Figure 4 . 7 :

 47 Figure 4.7: Average workload completion time per client, with up to 50 concurrent clients (logarithmic scale).

Figure 4 . 8 :

 48 Figure 4.8: Average workload completion time per client, with 4 workers (logarithmic scale).

Figure 4 . 9 :

 49 Figure 4.9: Average time for first results (over all queries), with up to 50 concurrent clients (linear scale).

  To provide stable and responsive public SPARQL query services, data providers enforce quotas on server usage. Queries which exceed these quotas are interrupted and deliver partial results. Such interruption is not an issue if it is possible to resume queries execution afterward. Unfortunately, there is no preemption model for the Web that allows for suspending and

	SaGe: Web Preemption for Public SPARQL Query services, by
	Thomas Minier, Hala Skaf-Molli and Pascal Molli. In Proceedings of the 2019
	World Wide Web Conference (WWW'19), San Francisco, United States, May
	13-17 (2019).
	Abstract:

resuming SPARQL queries. In this paper, we propose SaGe: a SPARQL query engine based on Web preemption. SaGe allows SPARQL queries to be suspended by the Web server after a fixed time quantum and resumed upon client request. Web preemption is tractable only if its cost in time is negligible compared to the time quantum. The challenge is to support the full SPARQL query language while keeping the cost of preemption negligible. Experimental results demonstrate that SaGe outperforms existing SPARQL query processing approaches by several orders of magnitude in term of the average total query execution time and the time for first results.

  Existing distributed query engines allow to go beyond quota limitations, but their data transfer and execution times are clearly prohibitive when processing aggregate queries. Following the web preemption model, we define a new preemptable aggregation operator that allows to suspend and resume aggregate queries. Web preemption allows to continue query execution beyond quota limits and server-side aggregation drastically reduces data transfer and execution time of aggregate queries. Experimental results demonstrate that our approach outperforms existing approaches by several orders of magnitude in terms of execution time and the amount of transferred data. Following the Triple Pattern Fragments (TPF) approach, intelligent clients are able to improve the availability of the Linked Data. However, data availability is still limited by the availability of TPF servers. Although some existing TPF servers belonging to different organizations already replicate the same datasets, existing intelligent clients are not able to take advantage of replicated data to provide fault tolerance and load-balancing.

	2. Intelligent clients for replicated Triple Pattern Fragments, by Thomas
	Minier, Hala Skaf-Molli, Pascal Molli and Maria-Esther Vidal. In Proceedings
	of the 15th European Semantic Web Conference (ESWC 2018), 400-414,
	Heraklion, Greece (2018).
	Abstract: actual
	load distribution and adapts to network conditions during SPARQL query
	processing.
	4. Parallelizing Federated SPARQL Queries in Presence of Replicated
	Data, by Thomas Minier, Gabriela Montoya, Hala Skaf-Molli and Pascal
	Molli. In ESWC 2017 -Revised Selected Papers. Springer, Cham, 2017. p.
	181-196 (2017).

1. Processing SPARQL Aggregates Queries with Web Preemption, by Arnaud Grall, Thomas Minier, Hala Skaf-Molli and Pascal Molli. In Proceedings of the 17th European Semantic Web Conference (ESWC 2020), Heraklion, Greece (2020).

Abstract: Executing aggregate queries on the web of data allows to compute useful statistics ranging from the number of properties per class in a dataset to the average life of famous scientists per country. However, processing aggregate queries on public SPARQL endpoints is challenging, mainly due to quotas enforcement that prevents queries to deliver complete results. In this paper, we propose Ulysses, an intelligent TPF client that takes advantage of replicated datasets to provide fault tolerance and load-balancing. By reducing the load on a server, Ulysses improves the overall Linked Data availability and reduces data hosting cost for organizations. Ulysses relies on an adaptive client-side load-balancer and a cost-model to distribute the load among heterogeneous replicated TPF servers. Experimentations demonstrate that Ulysses reduces the load of TPF servers, tolerates failures and improves queries execution time in case of heavy loads on servers. 3. Ulysses: an Intelligent client for replicated Triple Pattern Fragments, by Thomas Minier, Hala Skaf-Molli, Pascal Molli and Maria-Esther Vidal. In The Semantic Web: ESWC 2018 Satellite Events, Heraklion, Greece (2018).

Abstract: Ulysses is an intelligent TPF client that takes advantage of replicated datasets to distribute the load of SPARQL query processing and provides fault-tolerance. By reducing the load on a TPF server, Ulysses improves the Linked Data availability and distributes the financial costs of queries execution among data providers. This demonstration presents the Ulysses web client and shows how users can run SPARQL queries in their browsers against TPF servers hosting replicated data. It also provides various visualizations that show in real-time how Ulysses performs the

  Figure 2.2: Graph representation of the facts about Neil Gaiman and the books Good Omens and American Gods.

		DBpedia
			rdfs:label
		dbo:author	dbo:author
	Wikidata	owl:sameAs	rdf:type
			foaf:name
		dbo:author	dbo:author
		dbo:author	rdfs:label
	PREFIX foaf: <http://xmlns.com/foaf/0.1/> .
	PREFIX dbo:	<http://dbpedia.org/ontology/> .
	PREFIX rdf:

<http://www.w3.org/1999/02/22-rdf-syntax-ns#> . PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#> . SELECT ?author ?book_title WHERE { ?author rdf:type dbo:Person . ?author dbo:author ?book . ?book rdfs:label ?book_title . }

  author rdf:type dbo:Person tp 2 = ?author dbo:author ?book tp 3 = ?book rdf:type dbo:Book tp 4 = ?book rdfs:label ?book_title So, according to Definition 2, the SPARQL query is formally expressed as Q = SELECT {?author, ?book_title} WHERE {tp 1 AND tp 2 AND tp 3 AND tp 4 } = π ?author,?book_title (tp 1 tp 2 tp 3 tp4)

Table 2 .

 2 Figure 2.8: Physical query execution compiled from the logical plan of Figure 2.7b.

		P rojection(?author, ?book_title)
			IndexLoopJoin
		IndexLoopJoin	tp 4
		M ergeJoin	tp 3
		IndexScan(tp 1 ) IndexScan(tp 2 )
	Iterator Open()	GetNext()		Close()
	Scan	Get a pointer to the	Read the next match-	Release	the
		first matching RDF	ing RDF triple	pointer
		triple
	Filter	Open input	Read items from	Close input
			the input until one
			matches the SPARQL
			expression
	Sort	Read all items from	Read the next item	Cleanup	the
		the input, materialize	from the sorted table	sorted table and
		them into a table and			close input
		sort the table

1: Examples of Iterators for SPARQL query processing Index Loop joins

  The union of the solutions of all PREFIX dbo: <http://dbpedia.org/ontology/> PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>

	SELECT ?actor ?name WHERE {
	{
	SERVICE <http://dbpedia.org/sparql> {
	SELECT ?actor ?name WHERE {
	?actor a dbo:Actor. ?actor rdfs:label ?name.
	} ORDER BY ?actor ?name LIMIT 10000
	}
	} UNION {
	SERVICE <http://dbpedia.org/sparql> {
	SELECT ?actor ?name WHERE {
	?actor a dbo:Actor. ?actor rdfs:label ?name.
	} ORDER BY ?actor ?name OFFSET 10000 LIMIT 10000
	}
	}
	}
	Figure 2.9: A paginated SPARQL query

  and thus PREFIX dbo: <http://dbpedia.org/ontology/> PREFIX dbr: <http://dbpedia.org/resource/> PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>

	SELECT ?actor ?name WHERE {
	?actor rdfs:label ?name.
	VALUES ?actor { dbp:David_Tennant dbp:Michael_Sheen }
	}
	Figure

  Round Robin execution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

	Q 1	Executing		Waiting	CS	Executing
	Q 2	Waiting	CS	Executing
	Q 3		Waiting	CS	Executing
				Q2 completed	Q3 completed	Q1 completed

  FCFS execution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

	Q 1		Executing
	Q 2		Waiting			Executing
	Q 3			Waiting				Executing
						Q1 completed	Q2 completed	Q3 completed
				Web Preemption execution
		1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
	Q 1	Executing	Suspend	on client-side	Waiting	Resume	Executing
	Q 2	Waiting		Executing
	Q 3		Waiting		Executing
				Q2 completed	Q3 completed	Q1 completed

Table 4 .

 4 paradigm. Algorithm 1 presents the implementation of the Suspend and Resume operations for a pipeline of preemptable query iterators. Suspend simply stops and saves

	Preemptable	Space complexity of	Time complexity of
	iterator	Suspend	Suspend	Resume
	Projection	O(|V | + | dom(P )|)	O(|V | + S P )	O(R P )
	π V (P )	Proposition 1	Proposition 2	Proposition 3
	Index Scan	O(|tp| + |t|)	O(log b |D|)	O(log b |D|)
	IScan(tp)	Proposition 4	Proposition 5	Proposition 6
	Merge Join	O(| dom(P 1 )| + | dom(P 2 )|)	O(S P 1 + S P 2 )	O(R P 1 + R P 2 )
	M Join(P 1 , P 2 )	Proposition 7	Proposition 8	Proposition 9
	Index Loop Join	O(| dom(P )| + |tp| + |t|)	O(S P + log b |D|) O(R P + log b |D|)
	IJoin(P, tp)	Proposition 10	Proposition 11	Proposition 12
	Multi-set Union O(| dom(P 1 )| + | dom(P 2 )|)	O(S P 1 + S P 2 )	O(R P 1 + R P 2 )
	M U nion(P 1 , P 2 )	Proposition 13	Proposition 14	Proposition 15
	Filter	O(| dom(P )| + |R|)	O(S P )	O(R P )
	F ilter(P, R)	Proposition 16	Proposition 17	Proposition 18
	Physical plan	O(| dom(Q)| + |Q| × |t|)	O(|Q| × log b |D|) O(|Q| × log b |D|)
	P Q	Theorem 1	Theorem 2	Theorem 3

1: Complexities of preemption for preemptable iterators.

  Algorithm 3: A Preemptable Index Scan Iterator, evaluating a triple pattern tp using a clustered index over the RDF dataset Require: tp: triple pattern, D: RDF dataset, I tp : clustered index over tp Data: t: last matching RDF triple read 1 Function GetNext():

	2	non interruptible
	3	t ← next RDF triple matching tp in D
	4	let µ ← set of solutions mappings such as µ(t) = tp
	5	return µ
	6 Function Save():
	7	return tp, t
	8 Function Load(tp , t ):

9 tp ← tp 10 t ← I tp .Locate(t ) // Locate the last triple read Proposition 3. The time complexity of resuming a preemptable projection iterator π V (P ) is in O(R P ), where R P is the time complexity for resuming the iterator P .

  Notice that the client needs to pay the network

	PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
	PREFIX dbo: <http://dbpedia.org/ontology/>
	SELECT ?name ?place WHERE {
	?actor a dbo:Actor . # tp1
	?actor rdfs:label ?name . # tp2
	OPTIONAL {
	?actor dbo:birthPlace ?place . # tp3
	}
	}

Table 4 .

 4 2: Space of saved physical query execution plans.

	Avg. duration (ms)		1.44 1.15 1.66 0.89 0.85 1.51 Resume Suspend
	WatDiv Dataset size (nb of triples)
	Figure 4.6: Average preemption overhead.
	Mean	Min	Max	Standard deviation
	1.716 kb 0.276 kb 6.212 kb	1.337 kb

Table 4 .

 4 4: Comparison of the average number of HTTP requests sent to server when using the BindLeftJoin and OptJoin operators generate queries with OPTIONAL or FILTER operators. If the SaGe server supports some filters, the OPTIONAL operator and other filters impact the number of requests sent to the SaGe server, as explained in Section 4.3. First, we run an experiment to measure the number of requests for queries with OPTIONAL. We generate new WatDiv queries from one set of 193 queries, using the following protocol. For each query Q = {tp 1 , . . . , tp n }, we select tp k ∈ Q with the highest cardinality, then we generate Q = tp k (Q\tp k ). Such queries verify conditions for using BindLeftJoin and OptJoin. They are challenging for the BindLeftJoin as they generate many mappings; they are also challenging for the OptJoin as all joins yield results. Table

	Time quantum SaGe+BindLeftJoin SaGe+OptJoin
	75ms	72 489	5 656
	1s	70 964	511

  Figure A.1: Une requête SPARQL qui cherche tous les auteurs et leurs livres dans le jeu de données DBpedia.

	PREFIX foaf: <http://xmlns.com/foaf/0.1/>
	PREFIX dbo: <http://dbpedia.org/ontology/>
	PREFIX dbr: <http://dbpedia.org/resource/>
	PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
	SELECT ?author ?book WHERE {
	?author rdf:type dbo:Person .
	?author foaf:name ?name .
	?book dbo:author ?author .
	}

Table A .

 A dom(P 1 )| + | dom(P 2 )|) O(S P 1 + S P 2 ) O(R P 1 + R P 2 ) M Join(P 1 , P 2 ) P + log b |D|) O(R P + log b |D|) P 1 + S P 2 ) O(R P 1 + R P 2 ) M U nion(P 1 , P 2 ) 1: Complexités de préemption pour les itérateurs interruptibles. quels plans d'exécutions P Q ont un surcoût de préemption borné en O(|Q|), où |Q| est le nombre d'opérateurs dans le plan P Q . Nous observons que pour certains opérateurs physiques, leur surcoût de préemption dépasse très largement notre borne de O(|Q|). Pour résoudre ce problème, nous proposons avec SaGe une série de choix d'implémentation pour le modèle de la préemption Web, afin de miniser le surcoût de préemption 3 .

	Itérateur	Complexité en espace	Complexité en temps de
	interruptible	de Suspend	Suspend	Resume
	Projection	O(|V | + | dom(P )|)	O(|V | + S P )	O(R P )
	π V (P )	Proposition 1	Proposition 2	Proposition 3
	Index Scan	O(|tp| + |t|)	O(log b |D|)	O(log b |D|)
	IScan(tp)	Proposition 4	Proposition 5	Proposition 6
	Merge Join	O(| Proposition 7	Proposition 8	Proposition 9
	Index Loop Join O(S IJoin(P, tp) O(| dom(P )| + |tp| + |t|) Proposition 10 Proposition 11	Proposition 12
	Multi-set Union	O(1) O(S Proposition 13 Proposition 14	Proposition 15
	Filter	O(| dom(P )| + |R|)	O(S P )	O(R P )
	F ilter(P, R)	Proposition 16	Proposition 17	Proposition 18
	Physical plan	O(| dom(Q)| + |Q| × |t|)	O(|Q| × log b |D|) O(|Q| × log b |D|)
	P Q	Théorème 1	Théorème 2	Théorème 3

https://wiki.dbpedia.org

https://www.wikidata.org

The LOD cloud diagram is maintained by John P. McCrae for the Insight Centre for Data Analytics, and can be consulted at https://lod-cloud.net

https://www.w3.org/TR/2013/REC-sparql11-protocol-20130321

http://dbpedia.org/sparql

http://wiki.dbpedia.org/public-sparql-endpoint

https://www.mediawiki.org/wiki/Wikidata_Query_Service/User_Manual#Query_ limits

All results were obtained on DBpedia version 2016-04.

https://wiki.dbpedia.org/

https://www.w3.org/TR/sparql11-query/#SparqlOps

= 25 seconds and an average time for first results of also 25 seconds.To avoid convoy effects while preserving scheduling performance, researchers designed various families of scheduling algorithms, also called scheduling policies. In particular, the Round-Robin (RR) scheduling algorithm[START_REF] Kleinrock | Analysis of A time-shared processor[END_REF] provides a fair

https://www.w3.org/TR/rdf-sparql-query/#QueryForms

The client overhead should not be confused with the server overhead.

https://jena.apache.org/

https://github.com/sage-org/sage-experiments

http://dsg.uwaterloo.ca/watdiv/

http://olafhartig.de/brTPF-ODBASE2016

https://developers.google.com/protocol-buffers/

https://developer.github.com/v4

http://dbpedia.org/sparql

http://wiki.dbpedia.org/public-sparql-endpoint

Le lecteur notera que l'implémentation proposée dans ce manuscrit est une implémentation possible, mais pas la seule.

Remerciements

Proof. A preemptable multi-set union iterator saves the same information as a preemptable merge join iterator (Algorithm 4). Hence, following the proof of Proposition 7, the space complexity of suspending a multi-set union iterator is in O(| dom(P 1 )| + | dom(P 2 )|). Proposition 14. The time complexity of suspending a preemptable multi-set union iterator M U nion(P 1 , P 2 ) is in O(S P 1 + S P 2 ), where S P i is the time complexity of suspending the iterator P i .

Proof. The single non-interruptible section of Algorithm 6 (Lines 24 to 32) contains assignments to local variables, so its time complexity is negligible. Next, the Save() function only needs to save the union inputs. So, if S P i is the time complexity of suspending the iterator P i , then the time complexity of suspending a preemptable multi-set union iterator M U nion(P 1 , P 2 ) is in O(S P 1 + S P 2 ).

Proposition 15. The time complexity of resuming a preemptable union iterator M U nion(P 1 , P 2 ) is in O(R P 1 + R P 2 ), where R P i is the time complexity of resuming the iterator P i .

Proof. The time complexity of resuming the union inputs dominates the time complexity of the Load() function from Algorithm 4, i.e., O(R P 1 + S P 2 ). Require: P 1 , P 2 : SPARQL graph patterns, D: RDF dataset, S: URL of a SaGe server. Data:

FILTER evaluation

We observe that the primary source of client overhead comes from the decomposition made to support full SPARQL queries, as these queries increase the number of requests sent to the server. Some decompositions are more costly than others. To illustrate, consider the evaluation of (P 1 OPTIONAL P 2 ) where P 1 and P 2 are expressions supported by the SaGe server. A possible approach is to evaluate P 1 D and P 2 D on the server, and then perform the left outer join on the client. This strategy generates only two subqueries but materializes P 2 D on client. If there are no join results, P 2 D are just useless intermediate results.

Another approach is to rely on a nested loop join approach: evaluates P 1 D and for each µ 1 ∈ P 1 D , if µ 2 ∈ µ 1 (P 2) D then {µ 1 ∪ µ 2 } are solutions to P 1 P 2 . Otherwise, only µ 1 is a solution to the left-join. This approach sends at least as many subqueries to the server than there are solutions to P 1 D .

To reduce the communication, the SaGe client implements BindJoins to process local join in a block fashion, by sending unions of BGPs to the server. This technique is already used in federated SPARQL query processing [START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF] with bound joins and in BrTPF [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF]. Consequently, this approach reduces the number of requests sent to the SaGe server by a factor equivalent to the size of a block of mappings. However, the number of requests sent still depends on the cardinality of P 1 .

Consequently, we propose a new technique, called OptJoin, for optimizing the evaluation of a subclass of left-joins, i.e., SPARQL queries with OPTIONAL clauses. The approach relies on the fact that:

So we can deduce that:

Algorithm 8 presents the OptJoin algorithm. If both P 1 and P 2 are evaluable by the SaGe server, then the left-join is computed as follows. First, it sends the query (P 1 P 2 ) ∪ P 1 to the server (Line 3). Then, for each mapping µ received, it builds local materialized views for P 1 P 2 D and P 1 D (Lines 4 to 8). The client knows that µ ∈ P 1 P 2 D if dom (µ) ⊆ var (P 1 P 2 ) (Line 5), otherwise µ ∈ P 1 D . Finally, the client uses the views to process the left-join locally (Line 9). With this technique, the client only uses one subquery to evaluate the left-join and, in the worst case, it transfers P 1 P 2 D as additional intermediate results.

To illustrate, consider query Q 3 from Figure 4.3. Q 3 , with 88334 solutions. The cardinality of tp 1 tp 2 is also of 88334, as every actor has a birthplace. It is the worse case for a BindLeftJoin, which will require 88334 Block size additional requests to evaluate the left join. However, with an OptJoin, the client executes Q 3 using approximately 500 requests.

We implement both BindLeftJoin and OptJoin as physical operators to evaluate OPTIONALs, depending on the query. We also implement regular BindJoin for processing SERVICE queries.

Experimental study

We want to empirically answer the following questions: What is the overhead of Web preemption in time and space? Does Web preemption improve the average workload completion time? Does Web preemption enhance the time for the first results? What are the client overheads in terms of numbers of requests and data transfer? We use Virtuoso as the baseline for comparing with SPARQL endpoints, with TPF and BrTPF as the baselines for the LDF approach.

We implemented the SaGe client in Java, using Apache Jena 3 . As an extension of Jena, SaGe is just as compliant with SPARQL 1.1. The SaGe server is implemented as a Python Web service and uses HDT [START_REF] Fernández | Binary RDF representation for publication and exchange (HDT)[END_REF] (v1.3.2) for storing data. Note that the current implementation of HDT cannot ensure log b (n) access time for all triple patterns, like (?s p ?o). This impacts the performance of SaGe negatively when resuming some queries. The code and the experimental setup are available on the companion website 4 .

Dataset

Virtuoso and then get results earlier. We rerun the same setup as in the previous section and measure the time for the first results (TFR). Figure 4.9 shows the results with a linear scale. As expected, Virtuoso suffers from the convoy effect that degrades the TFR significantly when the concurrency increases. TPF and BrTPF do not suffer from the convoy effect, and TFR is stable over concurrency. The main reason is that delivering a page of result for a single triple pattern takes ≈ 5ms in our experiment, so the waiting time on the TPF server grows very slowly. BrTPF is better than TPF due to its bind-join technique. The TFR for SaGe-75ms and SaGe-1s increases with the number of clients and the slope seems proportional to the quantum, because the waiting time on the server increases with the number of clients, as seen previously. Reducing the quantum improves the TFR, but increases the number of requests and thus deteriorates the WTC.

What are the client overheads in terms of the number of requests and data transfer? The client overhead in requests is the number of requests that the smart client sent to the server to get complete results minus one, as Virtuoso executes all queries in one request. As WatDiv queries are pure conjunctive queries and supported by the SaGe server, the number of requests to the server is the number of time quantum required to evaluate the whole workload. We measure the number of requests sent to servers with one workload for all approaches, with results shown in Table 4.3. As expected, Virtuoso just sends 193 requests to the server. SaGe-75ms sends 4082 requests to the server, while TPF sends 2.55 × 10 5 requests to the TPF server. We can see also that increasing the time quantum significantly reduces the number of requests; SaGe-1s sends only 645 requests. However, this seriously deteriorates the average WCT and TFR, as presented before. To compute the overhead in data transfer of SaGe, we just need to multiply the number of requests by the average size of saved plans; for SaGe-75ms, the client overhead in data transfer is 4082 × 1, 3 kb = 5.45 Mo. As the total size of the results is 51Mo, the client overhead in data transfer is ≈ 10%. For TPF, the average size of a page is 7ko; 2.5 • 10 5 × 7k = 1.78 Go, so the data transfer overhead is ≈ 340% for TPF.

What are the client overheads in terms of numbers of requests and data transfer for more complex queries? The WatDiv benchmark does not Appendix A

Résumé en langue française

A. Cependant, les documents HTML classiques ne sont pas suffisamment expressifs pour permetre de décrire des entités et leurs propriétés sans aucune ambiguité [START_REF] Bizer | Linked Data -The Story So Far[END_REF]. Pour ce faire, le Web sémantique [START_REF] Berners-Lee | The semantic web[END_REF] étend le Web des documents pour créer un Web des données, où les documents texte sont remplacés par des données structurées qui peuvent être automatiquement analysés par des ordinateurs. Ce nouveau Web ré-utilise les deux premiers principes fondateurs du Web des documents (les URLs et le protocole HTTP), mais remplace l'usage de documents HTML par des documents RDF [START_REF] Cyganiak | RDF 1.1 concepts and abstract syntax[END_REF]. La structure du modèle de données RDF [START_REF] Cyganiak | RDF 1.1 concepts and abstract syntax[END_REF] est basée sur des triplets RDF. Un triplet est composé d'un sujet, d'un prédicat et d'un objet : il énonce un fait à propos d'une entité du Web. En suivant les principes du Linked Open Data (LOD), proposés en 2006 par Tim Berners-Lee [START_REF] Berners-Lee | Linked data-design issues[END_REF], les fournisseurs de données ont publié des milliards de documents RDF sur le Web [START_REF] Bizer | Linked Data -The Story So Far[END_REF][START_REF] Schmachtenberg | Adoption of the Linked Data Best Practices in Different Topical Domains[END_REF]. La plupart sont hébergés sous la forme de simples fichiers RDF, qui peuvent être téléchargés via leurs URIs. L'URI http://dbpedia.org/resource/Neil_Gaiman permet d'accéder à l'ensemble des triplets RDF sur l'auteur Neil Gaiman.

Cependant, l'hébergement de fichiers RDF réduit grandement la capacité des A. clients, une file d'attente de taille finie et un nombre fini de workers. Un serveur Web préemptif supporte trois opérations: Execute, Resume, and Suspend. L'opération Execute est utilisée pour exécuter une requête Q pour un quantum de temps q. Elle prend en entrée une requête, représentée par son plan d'exécution denoté P Q i , et l'exécute pour une durée égale à q. Ensuite, elle produit un ensemble de solutions ω i et le plan d'exécution P Q i , qui est l'état de P Q i après la fin de l'exécution (Execute(