Keywords: Web sémantique, Optimisation des requêtes, Répondre à des requêtes en présence de contraintes, Reformulation des requêtes, Polystores Semantic Web, Query optimization, Query answering under constraints, Query reformulation, Hybrid stores . . . . . . ). . . . . . . . . . . .

iv (v) Nous appliquons cette technique à la Logique de Description DL-Lite R sous-jacente au langage OWL2 QL du W3C, et montrons expérimentalement ses avantages dans ce contexte.

Nous présentons également, brièvement, un travail en cours sur le problème consistant à fournir des chemins d'accès efficaces aux données dans les systèmes Big Data. Nous proposons d'utiliser un ensemble de systèmes de stockages hétérogènes afin de fournir une meilleure performance que n'importe lequel d'entre eux, utilisé individuellement. Les données stockées dans chaque système peuvent être décrites comme des vues matérialisées sur les données applicatives. Répondre à une requête revient alors à réécrire la requête à l'aide des vues disponibles, puis à décoder la réécriture produite comme un ensemble de requêtes à exécuter sur les systèmes stockant les vues, ainsi qu'une requête les combinant de fac ¸on appropriée.

Résumé

Répondre efficacement aux requêtes Big Data en présence de contraintes

Les contraintes sont les artéfacts fondamentaux permettant de donner un sens aux données. Elles garantissent que les données sont conformes aux besoins des applications. L'objet de cette thèse est d'étudier deux problématiques liées à la gestion efficace des données en présence de contraintes.

Nous abordons le problème de répondre efficacement à des requêtes portant sur des données, en présence de contraintes déductives. Cela mène à des données implicites dérivant de données explicites et de contraintes. Les données implicites requièrent une étape de raisonnement afin de calculer les réponses aux requêtes. Le raisonnement par reformulation des requêtes compile les contraintes dans une requête modifiée qui, évaluée à partir des données explicites uniquement, génère toutes les réponses fondées sur les données explicites et implicites. Comme les requêtes reformulées peuvent être complexes, leur évaluation est souvent difficile et coûteuse.

Nous étudions l'optimisation de la technique de réponse aux requêtes par reformulation dans le cadre de l'accès aux données à travers une ontologie, où des requêtes conjonctives SPARQL sont posées sur un ensemble de faits RDF sur lesquels des contraintes RDF Schema (RDFS) sont exprimées. La thèse apporte les contributions suivantes. (i) Nous généralisons les langages de reformulation de requêtes précédemment étudieés, afin d'obtenir un espace de reformulations d'une requête posée plutôt qu'une unique reformulation. (ii) Nous présentons des algorithmes effectifs et efficaces, fondés sur un modèle de coût, permettant de sélectionner une requête reformulée ayant le plus faible coût d'évaluation. (iii) Nous montrons expérimentalement que notre technique améliore significativement la performance de la technique de réponse aux requêtes par reformulation.

Au-delà de RDFS, nous nous intéressons aux langages d'ontologie pour lesquels répondre à une requête peut se réduire à l'évaluation d'une certaine formule de la Logique du Premier Ordre (obtenue à partir de la requête et de l'ontologie), sur les faits explicites uniquement. (iv) Nous généralisons la technique de reformulation optimisée pour RDF, mentionnée ci-dessus, aux formalismes pour répondre à une requête LPO-réductible.

iii I would like to start by thanking my advisors Ioana Manolescu and Franc ¸ois Goasdoué for sharing their passion and enthusiasm with me, as well as dedication and help through this journey. Completing this thesis would not have been possible, nor as fun as it was without them. It has been more than 3 years since they welcomed me in the OAK team as an intern. Many things changed, Franc ¸ois moved to Lannion, the team name changed to CEDAR, people graduated and new people joined the team, etc., however their support, guidance and hard-work attitude only growed with time. They were advisors in every meaning of the word, always encouraging me to give my best and improve myself, and guiding me during the process. Doing a PhD is a long-term, hard-working journey, which I was lucky to share with Ioana and Franc ¸ois. They were always demanding, but equally commited.

I am grateful to Thomas Neumann and Marie-Christine Rousset for thoroughly reading my thesis and for their valuable feedback. Further, I would like to thank Serge Abiteboul, Diego Calvanese, Dario Colazzo, and Christine Froidevaux for being part of my examining committee; I am very honored.

During the PhD, I was also fortunate to have productive collaborations with my colleagues from Inria, Université Paris-Sud and École polytechnique Stamatis Zampetakis, Francesca Bugiotti, Alessandro Solimando, Michaël Thomazo, Ioana Ileana and Alexandra Roatis. They are all contributors to this thesis. In addition, it was a pleasure to serve École polytechnique under the guidance of Yanlei Diao and Ioana. I keep great memories of my days of teaching service. Furthermore, I had the opportunity to be in contact with many people from other institutions and visit them. I want to thank Diego Calvanese for his invitation to visit KRDB at Free University of Bozen-Bolzano, and Martin Rezk, Davide Lanti, and Guohui Xiao for their valuable comments and feedbacks on efficient FOL reducible query answering. I want to thank Julien Leblay for inviting me to visit AIST Tokyo, it was a great experience discussing with him and the other people of his group about our research projects. Special thanks to Alin Deutsch for inviting me to visit UCSD and with whom we worked together in the Scalable Hybrid Stores project. Working with him has been a truly enriching experience, during which he provided a more formal perspective on the problems vii viii we were tackling, always in a patient and didactic way. Also want to thank Rana, it was a pleasure to work together both in UCSD and in Paris. They are also contributors to this thesis. Also want to thank to all the great people I was lucky to meet and share experiences with during my time in OAK and CEDAR. To Asterios, Jesus, Katerina, Juan, Raphael, Andrés, Danai, Zoi, Benjamin, Sofoklis, Sejla, Oscar, Tien Duc, Enhui, Soudip, Paul, Benoit, Tushar, Guillaume, Despoina, Javier, Swen and Gianluca... Thank you! Chapter 1

Introduction 1.1 Big Data

The Web 2.0, as it is popularly called, refers to a second stage of World Wide Web whose main ingredients are: (i) the apparition of dynamic content pages, services and applications providing the users a richer experience, (ii) the wide acceptance and (huge) growth of Software as a Service (SaaS), through lightweight integration protocols, web APIs, etc., (iii) massive participation, with a penetration of more than 46% of the world population, and (iv) a change in the user involvement and consumption paradigme, not being simple consumers but also content producers (e.g., Wikipedia, an online encyclopedia on which anyone can write or edit articles; Blogger, a blog-publishing service that allows users to create blogs entries as well as comment on them; Twitter, an online social networking service that enables users to share 140-character messages; Youtube, a video sharing plataform where users can also comment and rate the videos; WhatsApp Messenger, an instant message client to exchange text messages, audio messages, documents, images, video, etc. between two or more users; Facebook, a social networking service with more than 1.65 billion monthly active users as of March 31, 20161 etc.).

From a data management perspective, the Web 2.0 was disruptive in terms of data volume. We create 2.5 exabytes of data every day! In other words, 90% of the world's data was created in just the past 24 months2 . At the same time, hardware evolution brought cheaper and a continuous increase in the memory capacity, the emergence of a variety of computation and storage technologies, such as GPUs, FPGAs, etc. [START_REF] Stoica | Trends and challenges in big data processing[END_REF], high-speed networks (e.g., Infinibad), and finally but not less important cloud computing emerged. These events did not go unnoticed by the machine learning branch of the artificial intelligence community, nor by the the data management and distributed systems communities, which provided the systems and solutions (e.g., Hadoop, Spark, Flink, Kafka, etc.) 1 1.2. SEMANTIC WEB needed to support this new generation of Big Data (centric) applications.

Semantic Web

We live in times of the Third Generation Web: Web 3.0, also known as Semantic Web. Unlike traditional knowledge-representation systems, typically centralized [START_REF] Berners-Lee | The semantic web: A new form of web content that is meaningful to computers will unleash a revolution of new possibilities[END_REF], the Semantic Web is meant to be a world-wide distributed architecture; a step closer to Tim Berners-Lee dream back in 2000 [START_REF] Berners | Weaving the web -the original design and ultimate destiny of the World Wide Web by its inventor[END_REF]: where computers become capable of analyzing all the data on the Web.

The Semantic Web is an extension of the World Wide Web, in which the content is given structure, thus enabling a reliable way for the computers to process the semantics and therefore manipulate the data in a meaningful way. However, to accomplish such vision a set of data models and formats for specifying semantic descriptions of Web resources is needed. For such purpose the World Wide Web Consortium (W3C) presented the Resource Description Framework (RDF), on top of which the Semantic Web stack is built. RDF is a flexible data model that allows to express statements about resources (uniquely identified by their URI) in the form of subject-predicate-object expressions. To enhance the descriptive power of RDF datasets, the W3C proposed the RDF Schema (RDFS) [105] and Web Ontology Language (OWL) [102], facilitating the representation of semantic constraints (a.k.a. ontological constraints) between the classes and the properties used. The set of facts together with the logical statements on memberships of individuals and in classes or relationships between individuals form a knowledge base.

In a nutshell, current popularity and usage of ontologies in the Web is due to four major reasons [START_REF] Abiteboul | Web Data Management[END_REF]:

• Their flexible and natural way of structuring documents in multidimensional ways, allowing to find relevant information through very large documents collections.

• The logical formal semantics of ontologies provide means of inference, enabling reasoning. Therefore, it is possible for an ontology to be interpreted and processed by machines.

• Ontologies allow making concepts precise, improving Web search. For example, when searching for the word "aleph", we could specialize the concept in an ontology, book:aleph, resulting in the book written by J. L. Borges, the one from P. Coelho, etc., and avoiding unwanted answers where the term is used with another connotation (like those referring to the letter with the same name or to the sequence of numbers used to represent the cardinality of infinite sets that can be well-ordered).

• Ontologies serve as local join between heterogeneous information sources. Moreover, their inference potential helps to automatically integrate different data sources.

1.2. SEMANTIC WEB

For instance, if the famous argentinian writer J. L. Borges appears in a document, then he has an associated URI, through which all the other resources (books, articles, prizes, etc.) refer to him. Then, the RDF version of the British National Bibliography3 developed by British Library, and expressing relevant information about books, authors, publishers, etc., will contain the books written by Borges, the publishers of such books, publication place and year. At the same time, GeoNames 4 provides further information regarding the publication places, and DBPedia 5 (the semantic counterpart of Wikipedia6 ) will add more information about Borges, like his political opinion, family, etc. All the abovementioned interlinked datasets are part of Linked Open Data Figure 1.1 [START_REF] Schmachtenberg | Adoption of the linked data best practices in different topical domains[END_REF] illustrates some of the most well known (RDF) datasets in the Linked Open Data cloud as of April 2014. Each node in the graph corresponds to one RDF dataset, while the node diameter reflects the size of the respective dataset. In addition, there is an edge between two nodes if the two datasets have some URIs in common (i.e., the datasets are interlinked). As reported in [START_REF] Schmachtenberg | Adoption of the linked data best practices in different topical domains[END_REF], the size of the Semantic Web is growing, almost doubling its size every year.

MOTIVATIONS AND STUDIED PROBLEM

To exploit this wealth of data, the SPARQL query language has been defined [106]; subsequently, novel techniques and algorithms have been proposed for the processing of SPARQL queries, based on vertical partitioning [START_REF] Daniel | Scalable semantic web data management using vertical partitioning[END_REF], indexing [START_REF] Weiss | Hexastore: Sextuple indexing for Semantic Web data management[END_REF], efficient join processing [START_REF] Neumann | Scalable join processing on very large RDF graphs[END_REF], view selection [START_REF] Franc ¸ois Goasdoué | View selection in semantic web databases[END_REF], RDF management systems and optimized triple stores [108,110,113,[START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF], to name a few.

Motivations and studied problem

In this thesis, we consider the setting of ontology-based data access (OBDA) [START_REF] Lenzerini | Ontology-based data management[END_REF], which aims at exploiting a database, i.e., facts, on which hold ontological constraints, i.e., deductive constraints modeling the application domain under consideration. For instance, an ontology may specify that any author is a human, has a name, and must have authored some papers. Ontological constraints may greatly increase the usefulness of a database: for instance, a query asking for all the humans must return all the authors, just because of a constraint stating they are human; one does not need to store a human tuple in the database for each author. The data interpretations enabled by the presence of constraints has made OBDA a technique of choice when modeling complex real-life applications. For instance, in the medical domain, Snomed Clinical Terms is a biomedical ontology providing a comprehensive clinical terminology; the British Department of Health has a roadmap for standardizing medical records across the country, using this ontology etc.. While query answering under constraints is a classical database topic [3], research on OBDA has bloomed recently through many ontological constraints languages, e.g., Datalog ± [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF], Description Logics [START_REF] Baader | The DL Handbook: Theory, Implementation, and Applications[END_REF] and Existential Rules [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF], or RDF Schema for RDF graphs. OBDA query answering is the task of computing the answer to the given query, by taking into account both the facts and the constraints holding on them. In contrast, query evaluation as performed by database servers leads to computing only the answers derived from the data (facts), while ignoring the constraints.

Two main methods exist for OBDA query answering, both of which consists of a reasoning step, either on data or on queries, followed by a query evaluation step. A first reasoning method is data saturation (a.k.a. closure). This consists of pre-computing and adding to the data all its implicit information, to make it explicit. Answering queries through saturation, then, amounts to evaluating the queries on the saturated data. While saturation leads to efficient query processing, it requires time to be computed, space to be stored, and must be recomputed upon updates. Moreover, data saturation may not always be an option as it is infinite in many OBDA settings. The alternative reasoning step is query reformulation. This consists in turning a query into a reformulated query, which, evaluated against non-saturated data, yields the exact answers to the original query. Since reformulation takes place at query time, it is intrinsically robust to updates; the query reformulation process in itself is also typically very fast, since it only operates on the query, not on the data. However, reformulated queries are often much more complex than the original ones, thus their evaluation may be costly or even unfeasible.

CONTRIBUTIONS AND OUTLINE

This thesis addresses the problem of efficient OBDA query answering in RDF, the prominent W3C standard for the Semantic Web, and in the DL-Lite R description logic which underpins OWL2 QL, the W3C standard for semantic-rich data management.

Saturation-based query answering has received much attention in RDF, compared to reformulation-based query answering. In contrast, in DL-Lite R , since data saturation may be infinite, the focus is on reformulation-based query answering. In both data models, all the existing reformulation-based query answering techniques amounts to reformulating an incoming query with ontological constraints, so as to obtain a single reformulated query whose evaluation yields the correct answers. Importantly, the fact that there exists a single reformulated query results from the adopted query reformulation language.

The idea developed in this thesis to generalize the query reformulation languages used in the literature, in order to (i) encompass all the current reformulation-based query answering settings in RDF and DL-Lite R , and (ii) to allow a space of equivalent yet different reformulated queries, among which we can pick one with lowest (estimated) evaluation cost.

Contributions and outline

The report and the contributions to the above OBDA query answering problem are organized as follows:

Chapter 2 provides background about two well-known W3C's Semantic Web standards, the popular RDF data model and its associated SPARQL query languages, as well as the DL-Lite R description logic and conjunctive queries that underpins OWL2 QL for semantic-rich data management.

Chapter 3 considers optimizing reformulation-based query answering in a setting where SPARQL conjunctive queries are posed against RDF facts on which constraints expressed by an RDF Schema hold. The contributions of this chapter are the following:

• To generalize prior query reformulation languages, leading to investigating a space of reformulated queries, instead of a single reformulation.

• To introduce an effective and efficient cost-based algorithm for selecting from this space, the reformulated query with the lowest estimated cost.

• To present extensive experiments showing that our technique enables reformulationbased query answering where the state-of-the-art approaches are simply unfeasible, while it may decrease its cost by orders of magnitude in other cases.

CONTRIBUTIONS AND OUTLINE

Chapter 4 generalizes the idea developed in the preceding chapter to devise a novel optimization framework for reformulation-based query answering in First Order Logic (FOL) ontology-based data access settings. The contributions of this chapter are the following:

• To extend the language of FOL query reformulations beyond those considered so far in the literature, and investigate several (equivalent) FOL query reformulations of a given query, out of which we pick one likely to lead to the best evaluation performance.

• To apply the above mentioned framework to the DL-Lite R Description Logic underpinning the W3C's OWL2 QL ontology language.

• To demonstrate through experiments the framework performance benefits when two leading SQL systems, one open-source and one commercial, are used for evaluating the query reformulations.

Chapter 5 concludes this thesis and presents ongoing work as well as perspectives for future work.

Chapter 2 Preliminaries

This chapter presents the background needed by the presentation of the research work performed in the thesis. First, in Section 2.1 we introduce RDF, the graph-based data model promoted by the W3C standard for Semantic Web applications. Then, in Section 2.2 we revisit the DL-Lite R description logic underpinning the W3C's OWL 2 QL standard for semantic-rich data management.

RDF

The Resource Description Framework (RDF) is a graph-based data model promoted by the W3C as the standard for Semantic Web applications. Its associated query language is SPARQL. RDF graphs are often large and heterogeneous, i.e., resources described in an RDF graph may have very different sets of properties.

An RDF graph (or graph, in short) is a set of triples of the form s p o. A triple states that its subject s has the property p, and the value of that property is the object o. We consider only well-formed triples, as per the RDF specification [104], using uniform resource identifiers (URIs), typed or un-typed literals (constants) and blank nodes (unknown URIs or literals).

Blank nodes are essential features of RDF allowing to support unknown URI/literal tokens. These are conceptually similar to the variables used in incomplete relational databases based on V-tables [3,[START_REF] Imielinski | Incomplete information in relational databases[END_REF], as shown in [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF].

Notations. We use s, p, o and :b in triples as placeholders. Literals are shown as strings between quotes, e.g., "string". Finally, the set of values -URIs (U ), blank nodes (B), and literals (L) -of an RDF graph G is denoted Val(G). namespaces. We use these namespaces exactly for these classes and properties, e.g., rdf:type specifies the class(es) to which a resource belongs.

Example 1 (RDF graph). The RDF graph G below comprises information about a book, identified by doi 1 : its author (a blank node :b 1 related to the author name, which is a literal), title and date of publication.

G =

{doi 1 rdf:type Book, doi 1 writtenBy :b 1 , doi 1 hasTitle "El Aleph", :b 1 hasName "J. L. Borges", doi 1 publishedIn "1949"} An alternative, and sometimes more intuitive, way to visualize and represent all the triples information is using a graph, where there is a node for each (distinct) subject or object, labeled with its value; a triple is represented as a directed edge, labeled with the property value, between the subject node and the object node. Figure 2.2 presents an equivalent representation of G. Resources (URIs) are represented by blue roundednodes, blank nodes are illustrated with black rounded-nodes while literals are depicted with black square-nodes; black directed edges are use to exhibit the properties.

RDF Schema and entailment

A valuable feature of RDF is RDF Schema (RDFS) that allows enhancing the descriptions in RDF graphs. RDFS triples declare semantic constraints between the classes and the properties used in those graphs. The saturation of an RDF graph is unique (up to blank node renaming), and does not contain implicit triples (they have all been made explicit by saturation). An obvious connection holds between the triples entailed by a graph G and its saturation:

G RDF s p o if and only if s p o ∈ G ∞ .
RDF entailment is part of the RDF standard itself; in particular, the answers to a query posed on G must take into account all triples in G ∞ , since the semantics of an RDF graph is its saturation [106].

BGP Queries

We consider the well-known subset of SPARQL consisting of (unions of) basic graph pattern (BGP) queries, modeling the SPARQL conjunctive queries. Subject of several recent works [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF][START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF][START_REF] Franc ¸ois Goasdoué | View selection in semantic web databases[END_REF][START_REF] Franc ¸ois Picalausa | A structural approach to indexing triples[END_REF], BGP queries are the most widely used subset of SPARQL queries in real-world applications [START_REF] Franc ¸ois Picalausa | A structural approach to indexing triples[END_REF]. A BGP is a set of triple patterns, or triples/atoms in short. Each triple has a subject, property and object, some of which can be variables.

Notations. In the following we use the conjunctive query notation q(x):-t 1 , . . . , t α , where {t 1 , . . . , t α } is a BGP; the query head variables x are called distinguished variables, and are a subset of the variables occurring in t 1 , . . . , t α ; for boolean queries x is empty. The head of q is q(x), and the body of q is t 1 , . . . , t α . We use x, y, z, etc. to denote variables in queries. We denote by VarBl(q) the set of variables and blank nodes occurring in the query q.

Query evaluation. Given a query q and an RDF graph G, the evaluation of q against G is:

q(G) = {x µ | µ : VarBl(q) → Val(G) is a total assignment such that t µ 1 ∈ G, t µ 2 ∈ G, . . . , t µ α ∈ G} 2.1. RDF
where we denote by t µ the result of replacing every occurrence of a variable or blank node e ∈ VarBl(q) in the triple t, by the value µ(e) ∈ Val(G).

Note that evaluation treats the blank nodes in a query exactly as it treats non-distinguished variables [START_REF] Abiteboul | Web Data Management[END_REF]. Thus, in the sequel, without loss of generality, we consider queries where all blank nodes have been replaced by (new) distinct non-distinguished variables.

Query answering. The evaluation of q against G uses only G's explicit triples, thus may lead to an incomplete answer set. The (complete) answer set of q against G is obtained by the evaluation of q against G ∞ , denoted by q(G ∞ ).

Example 3 (Query answering). The following query asks for the names of authors of books somehow connected to the literal 1949:

q(x 3 ):-x 1 hasAuthor x 2 , x 2 hasName x 3 , x 1 x 4 "1949"
Its answer against the graph in Figure 2.3 is q(G ∞ ) = { "J L. Borges" }. The answer results from G RDF doi 1 hasAuthor :b 1 and the assignment µ = {x 1 ← doi 1 , x 2 ← :b 1 , x 3 ← "J L. Borges", x 4 ← publishedIn}. Observe that evaluating q directly against G leads to the empty answer, which is obviously incomplete.

Query answering techniques

Answering queries over data in the presence of deductive constraints requires a reasoning step in order to compute complete query answers. Two main query answering techniques exist: Saturation-based query answering. Compiles the constraints into the database by making all implicit data explicit. This method is straightforward and easy to implement. Its disadvantages are that dataset saturation requires computation time and storage space for all the entailed triples; moreover, the saturation must be recomputed upon every update. Incremental algorithms for saturation maintenance had been proposed in previous work [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF]. However, the recursive nature of entailment makes this process costly (in time and space) and this method not suitable for datasets with a high rate of updates. Further, for some ontology languages saturation may be infinite (see 2.2). Table 2.1, extracted from the cited work [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF], presents the characteristics of well-known datasets and shows that saturation adds between 10% and 41% to the dataset size, while multiset-based saturation (required for the incrementally maintaining the saturation technique presented by the authors) increase the size between 116% and 227%.

Reformulation-based query answering. Compiles the constraints into a modified query, which, evaluated over the explicit data only, computes all the answer due to explicit and/or implicit data. The main advantage of this method is that its robust to update, there is no need to (re)compute the closure of the dataset. On the other hand, in gen-

The database fragment of RDF

The database (DB) fragment of RDF [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF] is, to the best of our knowledge, the most expressive RDF fragment for which both saturationand reformulation-based RDF query answering has been defined and practically experimented. This DB fragment is defined by:

• Restricting RDF entailment to the RDF Schema constraints only (Figure 2.1), a.k.a. RDFS entailment. Consequently, the DB fragment focuses only on the application domain knowledge, a.k.a. ontological knowledge, and not on the RDF meta-model knowledge which mainly begets high-level typing of subject, property and object values found in triples with abstract RDF built-in classes, e.g., rdf:Resource, rdfs:Class, etc.

• Not restricting RDF graphs in any way. In other words, any triple allowed by the RDF specification is also allowed in the DB fragment.

In this DB fragment of RDF, Saturation-based query answering amounts to precomputing the saturation of a database db using its RDFS constraints in a forward-chaining fashion, so that the evaluation of every incoming query q against the saturation yields the correct answer set [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF]: q(db ∞ ) = q(Saturate(db)). This technique follows directly from the definitions in Section 2.1 and Section 2.1.2, and the W3C's RDF and SPARQL recommendations.

Reformulation-based query answering, in contrast, leaves the database db untouched and reformulates every incoming query q using the RDFS constraints in a backwardchaining fashion, Reformulate(q, db) = q ref , so that the relational evaluation of this reformulation against the (non-saturated) database yields the correct answer set [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF]: q(db ∞ ) = q ref (db). The Reformulate algorithm, introduced in [START_REF] Franc ¸ois Goasdoué | View selection in semantic web databases[END_REF] and extended in [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF], exhaustively applies a set of 13 reformulation rules. Starting from the incoming BGP query q to answer against db, the algorithm produces a union of BGP queries retrieving the correct answer set from the database, even if the latter is not saturated.

Example 4 (Query reformulation). The reformulation of q(x, y):-x rdf:type y w.r.t. the database db (obtained from the RDF graph G depicted in Figure 2.3), asking for all resources and the classes to which they belong, is:

2.2. DL-LITE R (0) q(x, y):-x rdf:type y ∪ (1) q(x, Book):-x rdf:type Book ∪ (2)
q(x, Book):-x writtenBy z ∪ (3) q(x, Book):-x hasAuthor z ∪ (4) q(x, Publication):-x rdf:type Publication ∪ (5) q(x, Publication):-x rdf:type Book ∪ (6) q(x, Publication):-x writtenBy z ∪ (7) q(x, Publication):-x hasAuthor z ∪ (8) q(x, Person):-x rdf:type Person ∪ (9) q(x, Person):-z writtenBy x ∪ (10) q(x, Person):-z hasAuthor x

The terms (1), ( 4) and (8) result from (0) by instantiating the variable y with classes from db, namely {Book, Publication, Person}. Item (5) results from (4) by using the subclass constraint between books and publications. (2), ( 6) and (9) result from their direct predecessors in the list, and are due to the domain and range constraints. Finally,

, ( 7) and (10) result from their direct predecessors and the sub-property constraint present in the database.

Evaluating this reformulation against db returns the same answer as q(G ∞ ), i.e., the answer set of q.

DL-Lite R

As commonly known, a Description Logic knowledge base (KB) K consists of a TBox T (ontology, or axiom set) and an ABox A (database, or fact set), denoted K = T , A , with T expressing constraints on A.

Most popular Description Logic dialects [START_REF] Baader | The DL Handbook: Theory, Implementation, and Applications[END_REF], and in particular DL-Lite R [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF], build T and A from a set N C of concept names (unary predicates), a set N R of role names (binary predicates), and a set N I of individuals (constants). The ABox consists of a finite number of concept assertions of the form A(a) with A ∈ N C and a ∈ N I , and of role assertions of the form R(a, b) with R ∈ N R and a, b ∈ N I . The TBox is a set of axioms, whose expressive power is defined by the ontology language. DL-Lite R description logic [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF], which is the first order logic foundation of the W3C's OWL2 QL standard for managing semantic-rich Web data, is a significant extension of the subset of RDF (comprising RDF Schema) which can be translated into description logics, a.k.a. the DL fragment of RDF; DL-Lite R is also a fragment of Datalog ± [START_REF] Calì | Datalog ± : a unified approach to ontologies and integrity constraints[END_REF].

Given a role R, its inverse, denoted R -, is the set:

{(b, a) | R(a, b) ∈ A}. We denote N ±
R the set of roles made of all role names, together with their inverses:

N ± R = N R ∪ {r -| r ∈ N R }.
For instance, supervisedBy and supervisedBy -, whose meaning is supervises, are in N ± R . A DL-Lite R TBox constraint is either:

2.2. DL-LITE R (T 1) PhDStudent Researcher (T 2) ∃worksWith Researcher (T 3) ∃worksWith - Researcher (T 4) worksWith worksWith - (T 5) supervisedBy worksWith (T 6) ∃supervisedBy PhDStudent (T 7) PhDStudent ¬∃supervisedBy - Table 2.2: Sample TBox T . (i) a concept inclusion of the form C 1 C 2 or C 1 ¬C 2 , where each of C 1 , C 2 is either a concept from N C , or ∃R for some R ∈ N ± R , and ¬C 2 is the complement of C 2 .
Here, ∃R denotes the set of constants occurring in the first position in role R (i.e., the projection on the first attribute of R). For instance, ∃supervisedBy is the set of those supervised by somebody, while ∃supervisedBy -is the set of all supervisors (i.e., the projection on the first attribute of supervisedBy -, hence on the second of supervisedBy);

(ii) a role inclusion of the form R 1 R 2 or R 1 ¬R 2 , with R 1 , R 2 ∈ N ± R .
Observe that the left-hand side of the constraints are negation-free; in DL-Lite R , negation can only appear in the right-hand side of a constraint. Constraints featuring negation allow expressing a particular form of integrity constraints: disjointness or exclusion constraints. The next example illustrates DL-Lite R KBs.

Example 5 (DL-Lite R KB). Consider the DL-Lite R TBox T in Table 2.2 expressing contraints on the Researcher and PhDStudent concepts, and the worksWith and supervisedBy roles. It states that PhD students are researchers (T 1), researchers work with researchers (T 2)(T 3), working with someone is a symmetric relation (T 4), being supervised by someone implies working with her/him (T 5), only PhD students are supervised (T 6) and they cannot supervise someone (T 7). Now consider the ABox A below, for the same concepts and roles:

(A1) worksWith(Ioana, Francois) (A2) supervisedBy(Damian, Ioana) (A3) supervisedBy(Damian, Francois)
It states that Ioana works with Franc ¸ois (A1), Damian is supervised by both Ioana (A2) and Franc ¸ois (A3).

The semantics of inclusion constraints is defined, as customary, in terms of their FOL interpretations. Tables 2.3 and 2.4 provide the FOL and relational notations expressing these constraints equivalently.

A KB K = T , A is consistent if the corresponding FOL theory, consisting of the A facts and of the FOL constraints corresponding to T , has a model. In this case, we

2.2. DL-LITE R DL constraint FOL constraint Relational constraint (under Open World Assumption) A A ∀x[A(x) ⇒ A (x)] A ⊆ A A ∃R ∀x[A(x) ⇒ ∃yR(x, y)] A ⊆ Π 1 (R) A ∃R - ∀x[A(x) ⇒ ∃yR(y, x)] A ⊆ Π 2 (R) ∃R A ∀x[∃yR(x, y) ⇒ A(x)] Π 1 (R) ⊆ A ∃R -A ∀x[∃yR(y, x) ⇒ A(x)] Π 2 (R) ⊆ A ∃R ∃R ∀x[∃yR (x, y) ⇒ ∃zR(x, z)] Π 1 (R ) ⊆ Π 1 (R) ∃R ∃R - ∀x[∃yR (x, y) ⇒ ∃zR(z, x)] Π 1 (R ) ⊆ Π 2 (R) ∃R -∃R ∀x[∃yR (y, x) ⇒ ∃zR(x, z)] Π 2 (R ) ⊆ Π 1 (R) ∃R -∃R - ∀x[∃yR (y, x) ⇒ ∃zR(z, x)] Π 2 (R ) ⊆ Π 2 (R) R R -or R -R ∀x, y[R(x, y) ⇒ R (y, x)] R ⊆ Π 2,1 (R ) or Π 2,1 (R) ⊆ R R R or R -R -∀x, y[R(x, y) ⇒ R (x, y)] R ⊆ R or Π 2,1 (R) ⊆ Π 2,1 (R )
A ¬A ∀x[A(x) ⇒ ¬A (x)] A ∩ A ⊆ ⊥ A ¬∃R ∀x[A(x) ⇒ ¬∃yR(x, y)] A ∩ Π 1 (R) ⊆ ⊥ A ¬∃R - ∀x[A(x) ⇒ ¬∃yR(y, x)] A ∩ Π 2 (R) ⊆ ⊥ ∃R ¬A ∀x[∃yR(x, y) ⇒ ¬A(x)] A ∩ Π 1 (R) ⊆ ⊥ ∃R -¬A ∀x[∃yR(y, x) ⇒ ¬A(x)] A ∩ Π 2 (R) ⊆ ⊥ ∃R ¬∃R ∀x[∃yR (x, y) ⇒ ¬∃zR(x, z)] Π 1 (R ) ∩ Π 1 (R) ⊆ ⊥ ∃R ¬∃R - ∀x[∃yR (x, y) ⇒ ¬∃zR(z, x)] Π 1 (R ) ∩ Π 2 (R) ⊆ ⊥ ∃R -¬∃R ∀x[∃yR (y, x) ⇒ ¬∃zR(x, z)] Π 2 (R ) ∩ Π 1 (R) ⊆ ⊥ ∃R -¬∃R - ∀x[R (y, x) ⇒ ¬∃zR(z, x)] Π 2 (R ) ∩ Π 2 (R) ⊆ ⊥ R ¬R -or R -¬R ∀x, y[R(x, y) ⇒ ¬R (y, x)] R ∩ Π 2,1 (R ) ⊆ ⊥ or Π 2,1 (R) ∩ R ⊆ ⊥ R ¬R or R -¬R - ∀x, y[R(x, y) ⇒ ¬R (x, y)] R ∩ R ⊆ ⊥ or Π 2,1 (R) ∩ Π 2,1 (R ) ⊆ ⊥

DL-LITE R

say also that A is T -consistent. In the absence of negation, any KB is consistent, as negation-free constraints merely lead to infering more facts. If some constraints feature negation, K is consistent iff none of its (explicit or inferred) facts contradicts a constraint with negation. An inclusion or assertion α is entailed by a KB K, written K |= α, if α is satisfied in all the models of the FOL theory corresponding to K.

Example 6 (DL-Lite R entailment). The KB K = T , A from Example 5 entails many constraints and assertions. For instance:

• K |= ∃supervisedBy ¬∃supervisedBy -, i.e., the two attributes of supervisedBy are disjoint, due to (T 6) + (T 7);

• K |= worksWith(Francois, Ioana), i.e., Franc ¸ois works with Ioana, due to (T 4)+ (A1);

• K |= PhDStudent(Damian), i.e., Damian is a PhD student, due to (A2) + (T 6);

• K |= worksWith(Francois, Damian), i.e., Franc ¸ois works with Damian, due to (A3) + (T 5) + (T 4).

Finally remark that A is T -consistent, i.e., there is no violation of its only constraint using negation (T 7), since the KB K does not entail that some PhD student supervises another.

Queries

DL-Lite R knowledge bases are queried with FOL queries. A FOL query is of the form q(x):-φ(x) where φ(x) is a FOL formula whose free variables are x; the query name is q, its head is q(x), while its body is φ(x). The answer set of a query q against a knowledge base K is:

ans(q, K) = { t ∈ (N I ) n | K |= φ( t)}, where K |= φ( t) means that every model of K is a model of φ( t).
If q is Boolean, ans(q, K) = { } encodes true, with the empty tuple, while ans(q, K) = ∅ encodes false. In keeping with the literature on query answering under ontological constraints, our queries have set semantics.

Example 7 (Query answering). Consider the FOL query q asking for the PhD students with whom someone works: q(x):-∃y PhDStudent(x) ∧ worksWith(y, x)

Given the KB K of Example 5, the answer set of this query is {Damian}, since K |= PhDStudent(Damian) and K |= worksWith(Francois, Damian) hold. Observe that evaluating q against K's ABox only yields no answer.

DL-LITE

R CQ q(x):-a 1 ∧ • • • ∧ a n SCQ q(x):-(a 1 1 ∨ • • • ∨ a k 1 1 ) ∧ • • • ∧ (a 1 n ∨ • • • ∨ a kn n ) UCQ q(x):-CQ 1 (x) ∨ • • • ∨ CQ n (x) USCQ q(x):-SCQ 1 (x) ∨ • • • ∨ SCQ n (x) JUCQ q(x):-UCQ 1 ( x1 ) ∧ • • • ∧ UCQ n ( xn ) JUSCQ q(x):-USCQ 1 ( x1 ) ∧ • • • ∧ USCQ n ( xn )
Table 2.5: FOL query dialects.

To simplify the reading, in what follows, we omit the quantifiers of existential variables, and simply write the above query as q(x):-PhDStudent(x) ∧ worksWith(y, x).

Query dialects. We will need to refer to several FOL query dialects, whose general forms are schematized in Notations. Unless otherwise specified, we systematically use q to refer to a CQ query, a 1 , . . . , a n to designate the atoms in the body of q, T to designate a DL-Lite R TBox, and A for an ABox.

Query answering techniques

In constrast to the RDF case, data saturation is not an option in DL-Lite R , as the saturation of a KB may be infinite. Indeed, think of a KB with TBox T = {∃R -∃R, A ∃R} and ABox A = {A(a)}. Clearly, the saturation of A w.r.t. the constraints in T is infinite: {A(a), R(a, w 0 )} ∪ ∞ i=0 {R(w i , w i+1 )} where the w i 's are existential variables. Settings in which query answering is said FOL-reducible have therefore been investigated, i.e., settings in which query reformulation is possible.

FOL-reducible query answering. In a setting where query answering is FOL-reducible, there exists a FOL query q FOL (computable from q and T ) such that: ans(q, T , A ) = ans(q FOL , ∅, A ) for any T -consistent ABox A. Thus, query answering reduces to: a first reasoning step to produce the FOL query from q and T (this is also known as reformulating the query using the constraints), and a second step which evaluates the reformulated query q FOL in the standard fashion, only on the ABox (i.e., disregarding the TBox constraints). This 2.2. DL-LITE R q 1 (x):-PhDStudent(x) ∧ worksWith(y, x) q 2 (x):-PhDStudent(x) ∧ worksWith(x, y) q 3 (x):-PhDStudent(x) ∧ supervisedBy(y, x) q 4 (x):-PhDStudent(x) ∧ supervisedBy(x, y) q 5 (x):-supervisedBy(x, z) ∧ worksWith(y, x) q 6 (x):-supervisedBy(x, z) ∧ worksWith(x, y) q 7 (x):-supervisedBy(x, z) ∧ supervisedBy(y, x) q 8 (x):-supervisedBy(x, z) ∧ supervisedBy(x, y) q 9 (x):-supervisedBy(x, x) q 10 (x):-supervisedBy(x, y) can be done for instance by translating it into SQL and delegating the evaluation to an RDBMS. From a knowledge base perspective, this allows to take advantage of highly optimized data stores and query evaluation engines to answer queries. From the database perspective, this two-step approach enhances the power of RDBMSs, as it allows to compute answers based only on data stored in the ABox (i.e., the database), but also taking into account the deductive constraints and all their consequences (entailed facts and constraints).

As DL-Lite R query answering is FOL reducible [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF], the literature provides techniques for computing FOL reformulations of a CQ in settings related to DL-Lite R . These techniques produce (i) a UCQ w.r.t. a DL-Lite R TBox, e.g., [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF]2,[START_REF] Pérez-Urbina | Efficient query answering for OWL 2[END_REF][START_REF] Chortaras | Optimized query rewriting for OWL 2 QL[END_REF][START_REF] Venetis | Incremental query rewriting for OWL 2 QL[END_REF], or extensions thereof using existential rules [START_REF] König | A sound and complete backward chaining algorithm for existential rules[END_REF] or Datalog ± [START_REF] De | NYAYA: A system supporting the uniform management of large sets of semantic data[END_REF][START_REF] Gottlob | Query rewriting and optimization for ontological databases[END_REF], (ii) a USCQ [START_REF] Thomazo | Compact rewriting for existential rules[END_REF] w.r.t. a set of existential rules generalizing a DL-Lite R TBox, and (iii) a set of alternative equivalent JUCQs w.r.t. an RDF database [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF], whose RDF Schema constraints are the following four, out of the twenty-two, DL-Lite R ones: (1) A A , (4) ∃R A, (5) ∃R -A and (11) R R .

CQ-to-UCQ reformulation for DL-Lite R [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF]. We present the pioneering CQ-to-UCQ technique on which we rely to establish our results. These results extend to any other FOL reformulation techniques for DL-Lite R , e.g., the above-mentioned ones, since they produce equivalent FOL queries.

The technique of [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF] relies on two operations: specializing a query atom into another by applying a negation-free constraint (recall Table 2.3) in the backward direction, and specializing two atoms into their most general unifier (mgu, in short). These operations are exhaustively applied to the input CQ; each operation generates a new CQ contained in the input CQ w.r.t. the TBox, because the new CQ was obtained by specializing one or two atoms of the previous CQ. The same process is then applied on the new CQs, and so on recursively until the set of generated CQs reaches a fixpoint. The finite union of the input CQ and of the generated ones forms the UCQ reformulation of the input CQ w.r.t. the TBox.

DL-LITE R

Example 8 (CQ-to-UCQ reformulation). Consider the query q(x):-PhDStudent(x) ∧ worksWith(y, x) and KB K of the preceding examples. The UCQ reformulation of q is: q UCQ (x):-10 i=1 q i (x) where q 1 -q 10 appear in Table 2.6. In the table, q 1 (x) has exactly the body of q. q 2 (x) is obtained from q 1 by applying the constraint (T 4): worksWith worksWith -, which is of the form [START_REF] Alagiannis | H2O: a hands-free adaptive store[END_REF] listed in Table 2.3. (T 4) is applied backward, in the following sense: the query asks for worksWith(y, x), and (T 4) tells us that one of the possible reasons why this may hold, is if worksWith(x, y) holds. Thus, q 2 is contained within q 1 , in the sense that if q 2 holds, q 1 is also sure to hold, but the opposite is not true; intuitively, "q 1 may hold for other reasons (thanks to other specializations of its atoms)" -and it is exactly the set of such other specializations which the technique explores.

Similarly, q 3 is obtained from q 1 by applying the constraint (T 5) backward on the atom worksWith(y, x), and q 4 from q 2 by applying (T 5) on worksWith(x, y). To obtain q 5 to q 8 , we apply (T 6) backward on the atom PhDStudent(x) in q 1 to q 4 . Finally, q 9 is obtained from q 7 through the mgu of its two atoms, namely supervisedBy(x, z) and supervisedBy(y, x); q 10 is similarly obtained from q 8 . Beyond FOL-reducible query answering. The so-called combined approach of [START_REF] Kontchakov | The combined approach to ontology-based data access[END_REF] computes a finite approximation of a (possibly infinite) KB' saturation, and then reformulates queries so that erroneous answers introduced by approximating the saturation are not returned.

Chapter 3 Efficient query answering in the presence of RDFS constraints

Answering queries over data in the presence of deductive constraints, which lead to implicit data that is entailed (derived) from the explicit data and the constraints, requires a reasoning step in order to compute complete query answers. Two main query answering techniques exist: data saturation compiles the constraints into the database by making all implicit data explicit, while query reformulation compiles the constraints into a modified query, which, evaluated over the explicit data only, computes all the answers due to explicit and/or implicit data. So far, reformulation-based query answering has received significantly less attention than saturation. In particular, reformulated queries may be complex, thus their evaluation may be very challenging.

In this chapter we focus on optimizing reformulation-based query answering in the setting of ontology-based data access, where SPARQL conjunctive queries are answered against a set of RDF facts on which RDFS constraints hold. We consider the setting in which conjunctive queries (CQ), once reformulated into unions of conjunctive queries (UCQ) or semi-conjunctive queries (SCQ), are handled for evaluation to a query evaluation engine, which can be an RDBMS, a dedicated RDF storage and query processing engine, or more generally any system capable of evaluating selections, projections, joins and unions. As our experiments show, the evaluation of reformulated queries may be very challenging even for well-established relational or native RDF processors, which may handle them inefficiently or simply fail to handle them, even on moderate-size datasets.

The approach we take is the following: given a SPARQL conjunctive query q and a query reformulation algorithm A which turns a CQ into a UCQ, we explore a novel, large space of alternative reformulations of q that we term JUCQ (for joins of unions of conjunctive queries, which captures the UCQ and SCQ reformulations, and from which we pick a JUCQ reformulation with lowest estimated cost. Each JUCQ reformulation is obtained based on a carefully chosen set of invocations of the algorithm A, guided by our cost model.

q ref c(q ref )
Query q, RDF data and constraints, CQ to UCQ reformulation algorithm q ref State of the art Our approach q 1 c(q 1 ) ≡ q best c(q best ) ≡ q n c(q n ) ≡ . . .

≡

. . .

≡ q best

Query optimizer Execution engine

Results

Query evaluation engine (σ, π, , ∪)

Figure 3.1: Outline of our approach for efficiently evaluating reformulated SPARQL conjunctive queries.

Contributions. The contributions we bring to the problem of efficiently answering SPARQL queries, through reformulation, can be outlined as follows (see Figure 3.1):

1. We generalize the query reformulation approach, by considering a large space of alternative (equivalent) JUCQ reformulations. This space corresponds to the yellow-background box in Figure 3.1; it includes and significantly generalizes the prior works based on UCQ or SCQ reformulation. We characterize the size of our space of alternatives, and show that it is oftentimes too large to be completely explored.

2. We define a cost model for estimating the evaluation performance of our reformulated queries through a relational engine; other functions can be used instead, and we show that an RDBMSs' internal cost model can easily be used, too.

3. We devise a novel algorithm which selects one alternative reformulated query, namely q best in Figure 3.1, which (i) computes the same result as the UCQ or SCQ reformulated query q ref , and (ii) reduces significantly the query evaluation cost (or simply makes it possible when evaluating q ref fails!)

4. We implemented this algorithm and deployed it on top of three well-established RDBMSs, which we show differ significantly in their ability to handle UCQ and SCQ reformulations. Our experiments confirm that our algorithm makes the most out of each of these engines by leveraging their strengths and avoiding their weaknesses thanks to the usage of our cost model, which we calibrate separately for each system. This makes reformulation feasible when UCQ and/or SCQ fail, and brings performance improvements of several orders of magnitude w.r.t. UCQ .

5. Finally, we put our efficient reformulation-based query answering technique in perspective by comparing it against saturation-based query answering, both based on PostgreSQL and through the dedicated Semantic Web data management platform Virtuoso. These experiments confirm the robustness and performance of our technique, showing in particular that in some cases its performance approaches that of saturation-based query answering. In the sequel, we characterize our solution search space and formalize our problem in statementSection 3.1. Section 3.2 introduces our cost model and solution search space exploration technique, which we evaluate through experiments in Section 3.3. We discuss related work in Section 3.4, then we conclude.

The work reported here is based on the EDBT paper [START_REF] Bursztyn | Optimizing reformulation-based query answering in RDF[END_REF], the VLDB demonstration [START_REF] Bursztyn | Reformulationbased query answering in RDF: alternatives and performance[END_REF] and ICDE tutorial [START_REF] Bursztyn | Reasoning on web data: Algorithms and performance[END_REF].

Motivation

We first introduce, by examples, the performance issues raised by the evaluation of stateof-the-art reformulated queries. We then introduce our novel reformulation search space and formalize our optimization problem.

Motivating Example 1. Consider the three triples query q 1 shown below:

q 1 (x, y) :-x rdf:type y, (t 1 ) x ub:degreeFrom "http : //www.U niv532.edu", (t 2 ) x ub:memberOf "http : //www.Dept1.U niv7.edu" (t 3 ) Table 3.1 gives some intuition on the difficulty of answering q 1 over an 10 8 triples LUBM [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF] benchmark dataset.

The state-of-the-art CQ to UCQ reformulation-based query answering needs to evaluate a reformulated query q 1 , which is a union of 2, 256 conjunctive queries, each of which consists of three triples (one for the reformulation of each triple in the original q 1 ). This query appears in Table 3.2, where all the triples t 1 , t 2 , t 3 are reformulated together by a CQ to UCQ reformulation algorithm denoted (.) ref . Observe that in q 1 , many subexpressions are repeated; for instance, the join over the single triples resulting from the reformulation of triples (t 2 ) and (t 3 ) will appear for each of the 188 reformulations of triple (t 1 ). Evaluating q 1 on the 100 million triples LUBM dataset takes more than 6 seconds.

Alternatively, one could consider the equivalent query q 1 = (t reformulates each triple (into, respectively, a union of 188, 4, and 3 queries), and then joins these unions. This query corresponds to the simple semi-conjunctive queries (SCQ) alternative proposed in [START_REF] Thomazo | Compact rewriting for existential rules[END_REF]. While this avoids the repeated work, its performance is much worse: in the same experimental setting, it takes about 1074 seconds to evaluate.

Let us now consider the following equivalent query q 1 = (t 1 , t 3 ) ref (t 2 ) ref where t 1 , t 2 , t 3 are the triples of the query q 1 . Evaluating q 1 in the same experimental setting takes 554 ms, more than 10 times faster than the initial reformulation. The performance improvement of q 1 over q 1 is due to the intelligent grouping of the triples t 1 and t 3 together. Such grouping of triples reduce the cardinality of the respective reformulated queries. Thus, (t 1 , t 3 ) ref has 2, 045 answers and 564 reformulations. Table 3.2 shows the number of reformulations and execution time for all the eight possible combinations of triples.

Motivating Example 2. Consider now the six triples query q 2 shown below: Statistics on the query triples, when evaluated over a 100 million triples LUBM dataset, appear in Table 3.3. The CQ to UCQ reformulation of q 2 , on the other hand, leads to a query q 2 corresponding to a union of 318, 096 six triples queries. Due to its complexity, q 2 could not be evaluated in the same experimental setting1 .

q 2 (x, u, y, v, z) :-x rdf:type u, ( t

MOTIVATION

Now consider the query

q 2 = (t 1 ) ref (t 2 ) ref (t 3 ) ref (t 4 ) ref (t 5 ) ref (t 6 ) ref ,
where t 1 , . . . , t 6 are the triples of q 2 ; again, this corresponds to the SCQ reformulation proposed in [START_REF] Thomazo | Compact rewriting for existential rules[END_REF]. q 2 is equivalent to q ref 2 , and in the same experimental setting, it is evaluated in 229 seconds. This is due to the large results of the (syntactically small) subqueries (t 1 ) ref , . . . , (t 6 ) ref (especially the first two, each with 33, 328, 108 results), which required some time to join.

Finally, consider the query

q 2 = (t 1 , t 3 ) ref (t 3 , t 5 ) ref (t 2 , t 4 ) ref (t 4 , t 6
) ref , also equivalent to q 2 . Evaluating q 2 takes 524 ms, more than 430 times faster than SCQ reformulation. As in the previous example, q 2 gains over q 2 by first, reducing repeated work, and second, intelligently grouping triples so that the query corresponding to each triple group can be efficiently evaluated and returns a result of manageable size. In particular, the biggest-size triples (t 1 ) and (t 2 ) had been grouped with (t 3 ) and (t 4 ) respectively, resulting in smaller intermediate results of 2, 296 and 2, 475 rows respectively, and improving the perfomance. Grouping triples (t 3 ) and (t 4 ) with the (t 5 ) and (t 6 ) respectively, yields analogous performance improvements.

As the above examples illustrate, generalizing the state-of-the-art query reformulation language of UCQs [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF][START_REF] Urbani | Dynamite: Parallel materialization of dynamic RDF data[END_REF][START_REF] Kaoudi | RDFS reasoning and query answering on DHTs[END_REF][START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF][START_REF] De | MASTRO: A reasoner for effective ontology-based data access[END_REF][START_REF] Adjiman | SomeRDFS in the semantic web[END_REF][START_REF] Franc ¸ois Goasdoué | View selection in semantic web databases[END_REF][START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF][START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF] or of SCQs [START_REF] Thomazo | Compact rewriting for existential rules[END_REF], to that of joins of UCQs, offers a great potential for improving the performance of reformulated queries. We introduce: Definition 3.1.1 (JUCQ). A Join of Unions of Conjunctive Queries (JUCQ) is defined as follows:

• any conjunctive query (CQ) is a JUCQ;

• any union of CQs (UCQ) is a JUCQ;

• any join of UCQs is JUCQ.

Next, we address the challenge of finding a best-performing JUCQ reformulation of a BGP query against an RDF database, among those that can be derived from a query cover. We define these notions as follows:

3.1. MOTIVATION Definition 3.1.2 (JUCQ reformulation). A JUCQ reformulation q JUCQ of a BGP query q w.r.t. a database db 1 is a JUCQ such that q JUCQ (db 2 ) = q(db ∞

2 ), for any RDF database db 2 having the same schema as db 1 .

Recall that two RDF databases have the same schema iff their saturations have the same RDFS statements.

BGP query covering is a technique we introduce for exploring a space of JUCQ reformulations of a given query. The idea is to cover a query q with (possibly overlapping) subqueries, so as to produce a JUCQ reformulation of q by joining the (state-of-the-art) CQ to UCQ reformulations of these subqueries, obtained through any reformulation algorithm in the literature (e.g., [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF]). Formally: Definition 3.1.3 (BGP query cover). A cover of a BGP query q(x):-t 1 , . . . , t n is a set C = {f 1 , . . . , f m } of non-empty subsets of q's triples, called fragments, such that m i=1 f i = {t 1 , . . . , t n }, no fragment is included into another, i.e., f i ⊆ f j for 1 ≤ i, j ≤ m and i = j, and: if C consists of more than 1 fragment, then any fragment joins at least with another, i.e., they share a variable.

For example, a cover of our query

q 1 is {{t 1 , t 2 }, {t 2 , t 3 }}. Definition 3.1.4 (Non-redundant BGP query cover). A non-redundant cover is a cover C such that there is no fragment f k ∈ C such that m i=1 f i = m i=1,i =k f i .
It can be easily shown that the reformulation based on a redundant cover C r performs at least as much work as the reformulation based on a non-redundant cover C derived from C r by removing one or more fragments until C is non-redundant. Therefore, in the sequel, we will only work with non-redundant covers; accordingly, we will explain how to ensure covers are and stay non-redudant, when presenting cover search algorithms.

Definition 3.1.5 (Cover queries of a BGP query). Let q(x):-t 1 , . . . , t n be a BGP query and C = {f 1 , . . . , f m } one of its covers. A cover query q |f i ,1≤i≤m of q w.r.t. C is the subquery whose body consists of the triples in f i and whose head variables are the distinguished variables x of q appearing in the triples of f i , plus the variables appearing in a triple of f i that are shared with some triple of another fragment f j,1≤j≤m,j =i , i.e., on which the two fragments join.

For example, the cover {{t 1 }, {t 2 , t 3 }} of our query q 1 leads to the cover queries:

q |f 1 (x, y):-x rdf:type y, and q |f 2 (x):-x ub:degreeFrom "http : //www.U niv532.edu", x ub:memberOf "http : //www.Dept1.U niv7.edu".

Query evaluation through an RDBMS is typically much more efficient when all the atoms of the query are connected through joins (in which case, properly optimized 3.1. MOTIVATION queries oftentimes run in linear time in the size of the data), than when the query comprises a cartesian product (which leads to unavoidable quadratic or higher complexity in the size of the data). Therefore, in this work, we only consider fragments which do not feature a cartesian product.

The theorem below states that evaluating a query q as the join of the cover queries resulting from one of its covers, yields the answer set of q: Theorem 3.1.1 (Cover-based reformulation). Let q(x):-t 1 , . . . , t n be a BGP query and C = {f 1 , . . . , f m } be any of its covers,

q JUCQ (x):-q UCQ |f 1 1 • • • 1 q UCQ |fm
is a JUCQ reformulation of q w.r.t. any database db, where every q UCQ |f i is a UCQ reformulation of the cover query

q |f i , for 1 ≤ i ≤ m.
Proof. The proof of Theorem 3.1.1 follows directly from the fact that any cover query q |f i , which is a CQ, can be equivalently reformulated w.r.t. db into a UCQ q UCQ |f i , e.g., using any state-of-the-art CQ to UCQ reformulation algorithm.

For any RDF graph G, the answer set to a BGP query q(x):-t 1 , . . . , t n is q(G ∞ ), where q(G ∞ ) is the relational evaluation of q against G ∞ [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF].

Let C = {f 1 , . . . , f m } be a cover for q, q (x):-

q |f 1 1 • • • 1 q |fm is
by definition a join decomposition of q. Therefore q(G ∞ ) = q (G ∞ ), hence q and q are equivalent.

We now want to show that q and q JUCQ are equivalent, and therefore q and q JUCQ also. Observe that for each fragment query q |f i in q we have q |f i (G ∞ ) = q UCQ |f i (G), thus q |f i and q UCQ |f i are equivalent, by the correctness of UCQ reformulation algorithms. Thus, replacing the fragment queries in q by their corresponding equivalent reformulations we obtain q JUCQ : q JUCQ (x):-

q UCQ |f 1 1 • • • 1 q UCQ |fm Threrefore, q JUCQ is equivalent to q.
An upper bound on the size of the cover-based reformulation space for a given query of n triples is given by the number of minimal covers of a set S of n elements [START_REF] Hearne | Minimal covers of finite sets[END_REF], i.e., a set of non-empty subsets of S whose union is S, and whose union of all these subsets but one is not S. This bound grows rapidly as the number n of triples in a query's body increases, e.g., 1 for n = 1, 49 for n = 4, 462 for n = 5, 6424 for n = 6 (http: //oeis.org/A046165). In practice, however, we require each fragment to share a variable with another (if any), so that cover queries, hence cover-based reformulations do not feature cartesian products. Therefore, the number of cover-based reformulations is smaller than the number of minimal covers.

In order to select the best performing cover-based reformulation within the above space, we assume given a cost function c which, for a JUCQ q, returns the cost c(q(db)) of

EFFICIENT QUERY ANSWERING

evaluating it through an RDBMS storing the database db. Function c may reflect any (combination of) query evaluation costs, such as I/O, CPU etc. As customary, we rely on a cost estimation function c , which statically provides an approximate value of c. For simplicity, in the sequel we will use c to denote the estimated cost.

The problem we study can now be stated as follows:

Definition 3.1.6 (Optimization problem). Let db be an RDF database and q be a BGP query against it. The optimization problem we consider is to find a JUCQ reformulation q JUCQ of q w.r.t. db, among the cover-based reformulations of q with lowest (estimated) cost.

Optimized queries vs. optimized plans. As stated above and illustrated in Figure 3.1, we seek a best query that is an optimized reformulation of q against db; we do not seek to optimize its plan, instead, we take advantage of existing query evaluation engines for optimizing and executing it. Alternatively, one could have placed this study within an evaluation engine and investigate optimized plans. We comment more the two alternatives in Section 3.4.

Efficient query answering

We present now the ingredients for setting up our cost-based query answering technique. Section 3.2.1 introduces our cost model for JUCQ reformulation evaluation through an RDBMS. We then provide, in Section 3.2.2, an exhaustive algorithm that traverses the search space of reformulated queries, looking for a cover-based reformulation with lower cost. Finally, in Section 3.2.3, we introduce a greedy, anytime algorithm that outputs a best query cover of the input BGP query, found so far. These algorithms are then used to evaluate the query as stated by Theorem 3.1.1.

Cost model

In this section we detail the cost of evaluating a JUCQ (reformulation) sent to an RDBMS. Such a query is a join of UCQs subqueries of the form:

q JUCQ (x):-q UCQ 1 • • • q UCQ m . The evaluation cost of q JUCQ is c(q JUCQ ) = c db + q UCQ i ∈q JUCQ (c eval (q UCQ i ) + c join (q UCQ i,1≤i≤m ) + c mat (q UCQ i,1≤i≤m,i =k )) + c unique (q JUCQ ) (3.1)
reflecting:

EFFICIENT QUERY ANSWERING

(i) the fixed overhead of connecting to the RDBMS c db ;

(ii) the cost to evaluate each of its UCQ sub-queries q UCQ i ;

(iii) the cost of eliminating duplicate rows from each of its UCQ sub-query results;

(iv) the cost to join these sub-query results;

(v) the materialization costs: the SQL query corresponding to a JUCQ may have many sub-queries. At execution time, some of these subqueries will have their results materialized (i.e., stored in memory or on disk) while at most one sub-query will be executed in pipeline mode. We assume without loss of generality, that the largest-result sub-query, denoted q UCQ k , is the one pipelined (this assumption has been validated by our experiments so far); and

(vi) the cost of eliminating duplicate rows from the result.

In the above, duplicates are eliminated because existing reformulation algorithms (and accordingly, our work) operate under set semantics.

Notations. For a given query q over a database db, we denote by |q| t the estimated number of tuples in q's answer set. Recall that q |{t i } stands for the restriction of q to its i-th triple. Using the notations above, the number of tuples in the answer set of

q |{t i } is denoted |q |{t i } | t .
Duplicate elimination costs. Assuming duplicate elimination is implemented by hashing, we estimate the cost of eliminating duplicate rows from q JUCQ (and q UCQ ) as:

c unique (q JUCQ ) = c l × |q JUCQ | t
where c l is the CPU and I/O effort involved in sorting the results.

When the results are large enough that disk merge sort is needed, we estimate the cost of eliminating duplicate rows from q JUCQ (and q UCQ as a particular case) result as:

c unique (q JUCQ ) = c k × |q JUCQ | t × log |q JUCQ | t
where c k is the CPU and I/O effort involved in (disk-based) sorting the results.

UCQ evaluation costs are estimated by summing up the estimated costs of the CQs:

c eval (q UCQ i ) = c unique (q UCQ i ) + q CQ ∈q UCQ i c eval (q CQ )
The cost of evaluating one conjunctive query c eval (q CQ ), where q CQ (x):-t 1 , . . . , t n , through the RDBMS is made of the scan cost for retrieving the tuples for each of its triples, and the cost of joining these tuples:

29 3.2. EFFICIENT QUERY ANSWERING c eval (q CQ ) = c scan (q CQ ) + c join (q CQ )
We estimate the scan cost of q CQ to:

c scan (q CQ ) = c t × t i ∈q CQ |q CQ |{t i } | t
where c t is the fixed cost of retrieving one tuple.

The join cost of q CQ represents the respective CPU and I/O effort; assuming efficient join algorithms such as hash-or merge-based etc. are available [START_REF] Ramakrishnan | Database Management Systems[END_REF], this cost is linear in the total size of its inputs:

c join (q CQ ) = c j × t i ∈q CQ |q CQ |{t i } | t
Therefore, we have:

c eval (q UCQ i ) = (c t + c j ) × q CQ ∈q UCQ i t i ∈q CQ |q CQ |{t i } | t (3.2)
UCQ join cost. As before, we consider the join cost to be linear in the total size of its inputs:

c join (q UCQ i,1≤i≤m ) = c j × q UCQ i q CQ ∈q UCQ i t i ∈q CQ |q CQ |{t i } | t (3.3)
UCQ materialization cost. Finally, we consider the materialization cost associated to a query q is c m × |q| t for some constant c m :

c mat (q UCQ i,1≤i≤m,i =k ) = c m × q UCQ i ,i =k q CQ ∈q UCQ i t i ∈q CQ |q CQ |{t i } | t (3.4)
where q UCQ k is the largest-result sub-query, and the one which is picked for pipelining (and thus not materialized).

Injecting the equations 3.2, 3.3 and 3.4 into the global cost formula 3.1 leads to the estimated cost of a given JUCQ. This formula relies on estimated cardinalities of various subqueries of the JUCQ, as well as on the system-dependent constants c db , c scan , c join and c mat , which we determine by running a set of simple calibration queries on the RDBMS being used. The details are straightforward and we omit them here.

EFFICIENT QUERY ANSWERING

Exhaustive query cover algorithm (ECov)

As a yardstick for the quality of the query covers we find, we developed an exhaustive query cover finding algorithm, called ECov, that traverses the search space of reformulated queries and outputs a query cover leading to a cover-based reformulation with lowest cost.

Given a BGP query q and a database db, ECov enumerates all the possible query covers, estimates the cost of the corresponding cover-based reformulations, and returns a query cover with the lowest estimated cost.

Possible moves based on the initial cover C 0 are developed and added to the list moves. Next (line 7), ECov starts exploring possible moves. It picks one from the moves list and applies it, leading to a new query cover C , and possible moves based on C are developed and added to the sorted moves list (lines 10-12). If its estimated cost is smaller than the best (least) cost encountered so far, the best solution is updated to reflect this C (lines [START_REF] Baader | The DL Handbook: Theory, Implementation, and Applications[END_REF][START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF]. Note that when the application of a move to a cover (line 9) leads to a redundant cover, all non-redundant covers that can be extracted from it, should be enumerated.

We use this cover as "golden standard", i.e., the best solutions based on our cost estimation function.

Greedy query cover algorithm (GCov)

We now present our optimized query cover finding algorithm, named GCov. Intuitively, GCov attempts to identify query covers such that the estimated evaluation cost of each cover fragment (once reformulated), together with the estimated cost of joining the results of these reformulated fragments, is minimized. Performance benefits in this context are attained from two sources: (i) avoiding the explosion in the size of the reformulated queries that results when many triples, each having many reformulations, are in the same fragment, and (ii) avoiding reformulated fragments with very large results, since materialising and joining them is costly. The key intuition for reaching these goals is to include highly selective, few-reformulations triples in several cover fragments. Observe that this is different from (and orthogonal to) join ordering, which the underlying query evaluation engine (RDBMS in this study) applies independently to each reformulated subquery.

GCov (Algorithm 2) starts with a simple cover C 0 consisting of one triple fragments (i.e., the SCQ reformulation), and explores possible moves starting from this state. A move consists of adding to one fragment, an extra triple connected to it by at least one join variable, such that the estimated cost associated to the cover-based reformulation thus obtained is smaller than that before the addition. Whenever apply (lines 6 and 9) leads to a redundant cover, a non-redundant cover is extracted out of the redundant one, in particular, the one with the least estimated cost. A move may reduce the cost in two 3.2. EFFICIENT QUERY ANSWERING Algorithm 1: Naïve cover algorithm (ECov)

Input : BGP query q(x:-t 1 , . . . , t n ), database db Output: Cover C for the BGP query q

1 C 0 ← C = {{t 1 }, {t 2 }, . . . , {t n }}; 2 T ← C = {t 1 , t 2 , . . . , t n }; 3 C best ← C 0 ; moves ← ∅; analysed ← ∅; 4 foreach f ∈ C 0 , t ∈ T s.t. t ∈ f ∧ connected(f, t) ∧ C 0 .add(f, t) ∈ analysed do 5 analysed ← analysed ∪ C 0 .add(f, t); 6 moves ← moves ∪ (C 0 , f, t); 7 while moves = ∅ do 8 (C, f, t) ← moves.head(); 9 C ← C.add(f, t); 10 foreach f ∈ C , t ∈ T s.t. t ∈ f ∧ connected(f, t) ∧ C .add(f, t) ∈ analysed do 11 analysed ← analysed ∪ C .add(f, t); 12 moves ← moves ∪ (C , f, t); 13 if C estimated cost < C best estimated cost then 14 C best ← C ; 15 return C best ;
ways: (i) by making a fragment more selective, and/or (ii) by leading to the removal of some fragments from the cover. For instance, let {{t 1 , t 2 }, {t 1 , t 3 }, {t 3 , t 4 }} be a cover of a four-triples query. The move which adds t 4 to the first fragment, also renders {t 3 , t 4 } redundant. Thus, the cover resulting from the move is:

{{t 1 , t 2 , t 4 }, {t 1 , t 3 }}.
Concretely, all the fragments of a cover are kept sorted in the decreasing order of their cost. Whenever the cover is updated, we check the fragments from the first to the last; when a fragment is found redundant (with respect to the other fragments in the cover), the fragment is removed.

Possible moves based on the initial cover C 0 are developed (i.e., all possible covers that result from the possible moves are created, and the estimate cost of executing its associated cover-based reformulation on top of an RDBMS is computed) and the one leading to the cover with lower estimated cost is assigned to move. Next (line 8), GCov starts examining possible moves. It applies move, if any, leading to a new query cover C best , updates the best solution to reflect this, and explores possible moves based on C best ; if a move resulting in a cover whose estimated cost is smaller than the best (least) cost encountered so far is found, then move is set with it.

GCov explores query covers in breadth-first and greedy fashion, adding to the moves list the possible moves starting from the current best cover, and selecting the next move

EXPERIMENTAL EVALUATION

Algorithm 2: Greedy query cover algorithm (GCov) Input : BGP query q(x:-t 1 , . . . , t n ), database db Output: Cover C best for the BGP query q with smallest cost. In practice, one could easily change the stop condition, for instance to return the best found cover as soon as its cost has diminished by a certain ratio, or after a time-out period has elapsed etc.

1 C 0 ← {{t 1 }, {t 2 }, . . . , {t n }}; 2 T ← {t 1 , t 2 , . . . , t n }; 3 C best ← C 0 ; move ← ∅; analysed ← ∅; 4 foreach f ∈ C 0 , t ∈ T s.t. t ∈ f ∧ connected(f, {t}) ∧ C 0 .add(f, t) ∈ analysed do 5 analysed ← analysed ∪ C 0 .add(f,

Experimental evaluation

We now present an experimental assessment of our approach. Section 3. Hardware. All the RDMBSs run on 8-core Intel Xeon (E5506) 2.13 GHz machines with 16GB RAM, using Mandriva Linux release 2010.0 (Official).

Datasets. We conducted experiments using DBLP (8 million triples) [38] and LUBM [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF] with 1 and 100 millions triples.

In our experiments, RDFS constraints are kept in memory, while RDF facts are stored in a Triples(s, p, o) table, indexed by all permutations of the s, p, o columns, leading a total of 6 indexes. Our indexing choice is inspired by [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], to give the RDBMS efficient query evaluation opportunities. Further, as in [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[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][START_REF] Franc ¸ois Goasdoué | View selection in semantic web databases[END_REF], for efficiency, the Triples(s, p, o) table's data are dictionary-encoded, using a unique integer for each distinct value (URIs and literals). The dictionary is stored as a separate table, indexed both by the code and by the encoded value.

Queries. We used 28 and 10 BGP queries for our evaluation on LUBM and DBLP datasets, respectively. The LUBM queries appear in Section A.1, Tables A.1-A.3 and the DBLP queries in Table A.4, while their main characteristics (number of union terms in their UCQ reformulation, denoted |q ref |, as well as the number of results when evaluated on our datasets) are shown in Table 3.4.

Some queries are modified versions of LUBM benchmark queries, in order to remove redundant triples2 . We designed the others so that (i) they have an intuitive meaning, (ii) they exhibit a variety of result cardinalities, (iii) they exhibit a variety of reformu- lations, some of which are syntactically complex, to allow a study of the performance issues involved and (iv) none of their triples is redundant.

All measured times are averaged over 3 (warm) executions. Moreover, queries whose evaluation requires more than 2 hours were interrupted; we point them out when commenting on the experiments' results.

Optimized reformulation

In this section, we compare our reformulation-based query answering technique with those from the literature based on UCQs and SCQs.

Effectiveness: is an optimizer needed? The first question we ask is whether exploring the space of JUCQ alternatives is actually needed, or could one just rely on a simple (fixed) query cover?

The UCQ reformulation used in many prior works is a particular case of the JUCQ reformulations we introduced in this work; it corresponds to a cover of a single fragment made of all the query triples (recall q 1 in Motivating Example 1, Section 3.1). From a database perspective, it corresponds to pushing the joins below a single (potentially large) union. At the other extreme, the SCQ reformulation proposed in [START_REF] Thomazo | Compact rewriting for existential rules[END_REF] is a particular case of JUCQ reformulation obtained from a cover where each query triple is alone in a fragment (recall q 1 in the same example). The SCQ reformulation can thus be thought of as pushing all unions below a the joins. Both the UCQ and SCQ reformulations correspond to a cover where each triple appears in exactly one fragment, whereas our JUCQs do not have this constraint; further, the UCQ and SCQ reformulations do not take into account quantitative information about the data and query.

We compared the performance of query answering through: (i) UCQ reformulation;

(ii) SCQ reformulation; (iii) the JUCQ recommended by the exhaustive ECov algorithm;

(iv) the JUCQ recommended by our greedy GCov algorithm. liable options. Indeed, UCQ is the slowest for many queries on DB2 and Postgres, sometimes by more than an order of magnitude, and it fails for Q 9 , Q 15 , Q 18 (f orLU BM 100M ), Q 19 and Q 28 on DB2, to which we add Q 6 , Q 14 and Q 16 on Postgres (for LUBM 100M). SCQ is very inefficient on MySQL, and also on Postgres for

Q 1 , Q 2 , Q 3 , Q 8 etc.
; it is almost always the worst choice for MySQL. In contrast, the GCov-chosen JUCQ always completes and is the fastest overall in all but Q 24 , Q 25 and Q 27 on Postgres. Figures 3.2 and 3.3 also shows that the GCov JUCQ performs as well as the ECov one, thus the greedy is making smart choices. In Figure 3.3, the GCov JUCQ is up to 4 orders of magnitude faster than the SCQ reformulation and two orders of magnitude faster than UCQ (on LUBM 1M, it wins by 3 orders of magnitude w.r.t. UCQ). We end by noting that the Q 16 cover chosen by ECov for Postgres has failed to execute due to insufficient memory in our runtime environment; we believe this could be avoided by further tuning the server execution parameters etc.

Figure 3.4 further highlights that no fixed reformulation technique is always the best. On DB2, SCQ performs very well for Q 5 , Q 6 and Q 7 , and very poorly for Q 8 and Q 9 ; on the latter, UCQ times out. In contrast, JUCQ performance is robust, the best in all cases but Q 6 GCov performance We now turn to considering the number of covers: overall (as explored by the exhaustive ECov), and the subset traversed by our greedy GCov; these are depicted in Figure 3.5 and 3.6, also in logarithmic scale. (Recall that UCQ and SCQ each correspond to one fixed cover.) While the search space can be very large (e.g., for LUBM Q 2 , Q 9 or Q 12 ), GCov only explores a reduced subset of this space. The same figures also show the running time of GCov and ECov, and the time to build the UCQ, respectively the SCQ reformulations (again, observe the logarithmic time axis). The time is spent to: obtain the statistics necessary for estimating the number of results of various fragments; reformulate each fragment, estimate its cost, and all other steps shown in Algorithms 1 and 2. We see that GCov's running time may be one order of magnitude less than the one of ECov; as expected, building the (cost-ignorant) UCQ and SCQ is quite faster, at the expense of their evaluation time and their unfeasibility to evaluate some queries. The highest running time is recorded for queries having a huge UCQ reformulation (LUBM Q 28 , respectively DBLP Q 10 , detailed in Table 3.4); the time is taken to build and estimate statistics for such very large UCQs. In particular, for DBLP Q 10 , the exhaustive ECov also runs out of memory building the very numerous reformulations.

Alternative: using the RDBMS cost estimation The second question we study is the quality of our cost estimation, that is crucial in guiding GCov decisions. The golden standard one can compare against is the RDBMS's internal cost estimation function: this is because any cover we chose is evaluated by sending it (as a SQL statement) to the system which optimizes it according to its internal cost model. Thus, the cost function used by GCov should be as close as possible to the RDBMS one.

For this comparison, whenever we needed to estimate the cost of a cover, we sent to Postgres an explain statement for the corresponding cover-based reformulation, and As explained in the Preliminaries, graph saturation and query reformulation are the two main techniques for answering queries under constraints. Saturation-based query answering can be very efficient, once the data is saturated; however, if the RDF graph is updated, the cost of maintaining the saturation may be very high [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF]. In contrast, query reformulation is performed directly at query time, and so it naturally adapts to the current state of the database. The performance trade-off between saturation-and reformulation-based query answering depends on the schema, on the nature of updates, and on the data statistics [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF].

Comparison with saturation

In this section, we show how our optimized JUCQ reformulation-based query answering technique impacts the performance comparison with saturation-based query answering. (iv) our GCov-chosen JUCQ. As expected, UCQ reformulation performs much worse than saturation-based query answering, and worse than the GCov JUCQ by up to three orders of magnitude. On some queries, such as Q 15 or Q 23 -Q 28 , saturation keeps its advantage even compared to our optimized JUCQ reformulation. However, on queries such as Q 3 -Q 14 and Q 16 -Q 22 , the JUCQ reformulation is close to (competitive with) saturation-based query answering, which is remarkable given that reformulation reasons at query time, and considering the performance gap observed between the two in previous works, e.g., [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF].

Experiment conclusion

Our experiments lead to the following conclusions.

(1). Confirming the intuition given by our example in Section 3.1, the space of JUCQ reformulation comprises alternative reformulations of a given BGP query w.r.t. the RDFS constraints, whose evaluation is (i) feasible when UCQ reformulation fails, and (ii) up to 4 orders of magnitude more efficient than a fixed reformulation strategy, such as UCQ or SCQ.

(2). While ECov is slow for large-reformulation queries, GCov identifies covers leading to efficient reformulations quite fast, confirming the feasibility of our optimized reformulation technique at query time.

(3). The cost model on which our search is based performs globally well; in particular, when calibrated for Postgres, we have shown it leads to chosing covers very close to the ones obtained when relying on Postgres' internal cost model. (4). While saturation-based query answering has reasons to be much more efficient than reformulation techniques (if one is willing to disregard the initial cost of saturating the database, as well as any cost related to saturation maintenance!), our efficient reformulation technique is in many cases competitive with saturation-based query answering, both through a relational server and through the native-RDF Virtuoso server. This confirms the important performance improvement brought by our work to reformulation-based query answering in RDF; recall that any CQ to UCQ reformulation algorithm could be used with our cost-based GCov optimization technique.

Related work

The context of our work is the problem of answering conjunctive queries against RDF facts, in the presence of RDFS constraints. As mentioned in the Preliminaries, solutions from the literature rely on RDF graph saturation, on query reformulation, or by mixing both [START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF]; our work focused on making query answering based on reformulation performant. Below, we position our work w.r.t. these two techniques.

Saturation-based query answering. When using graph saturation, all the implicit triples are computed and explicitly added to the database; query answering then reduces to query evaluation on the saturated database. Well-known SPARQL compliant RDF RDF platforms originating in the data management community, such as Hexastore [START_REF] Weiss | Hexastore: Sextuple indexing for Semantic Web data management[END_REF] or RDF-3X [START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF], ignore entailed triples and only provide query evaluation on top of the RDF graph, which is assumed to be already saturated.

The drawbacks of saturation w.r.t. updates have been pointed out in [START_REF] Broekstra | Inferencing and truth maintenance in RDF Schema: Exploring a naive practical approach[END_REF], which proposes a truth maintenance technique implemented in Sesame. It relies on the storage and management of the justifications of entailed triples (which triples beget them). This technique incurs a high overhead of handling justifications when their number and size grow. Therefore, [START_REF] Bishop | OWLIM: A family of scalable semantic repositories[END_REF] proposes to compute only the relevant justifications w.r.t. an update, at maintenance time. This technique is implemented in OWLIM, however [112] points out that updates upon RDFS constraint deletions can lead to poor performance. More efficient saturation maintenance techniques are provided in [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF][START_REF] Urbani | Dynamite: Parallel materialization of dynamic RDF data[END_REF] based on the number of times triples are entailed.

Reformulation-based query answering. When using query reformulation, a given BGP query is reformulated based on the RDFS constraints into a target language, such that evaluating the reformulated query through an appropriate engine yields the query answer.

UCQ reformulation [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF][START_REF] Urbani | Dynamite: Parallel materialization of dynamic RDF data[END_REF][START_REF] Kaoudi | RDFS reasoning and query answering on DHTs[END_REF][START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF][START_REF] De | MASTRO: A reasoner for effective ontology-based data access[END_REF][START_REF] Adjiman | SomeRDFS in the semantic web[END_REF][START_REF] Franc ¸ois Goasdoué | View selection in semantic web databases[END_REF][START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF][START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF] applies to various fragments of RDF, ranging from the Description Logics (DL) one up to the Database one, the largest for which this technique have been considered so far. UCQ reformulation corresponds in this work to a JUCQ reformulation obtained from a single fragment query cover. SCQ reformulation [START_REF] Thomazo | Compact rewriting for existential rules[END_REF] was defined for the DL fragment of RDF. In our setting, it corresponds to a JUCQ reformulation obtained from a query cover in which each triple is alone in a fragment. Our experiments have shown that the evaluation performance for both UCQ or SCQ reformulation can be very poor.

Among popular RDF data management systems, the only ones supporting reformulation-based query answering are Stardog, Virtuoso (which supports only the rdfs:subClassOf and rdfs:subPropertyOf RDFS rules) and AllegroGraph [109] (which supports the four RDFS rules but whose reasoning implementation is incomplete 4 ). Virtuoso is based on SCQ reformulation, while Stardog uses UCQ reformulation; we found no information about AllegroGraph's query reformulation language. Nested SPARQL is the target reformulation language in [START_REF] Arenas | Foundations of RDF databases[END_REF]; in contrast, we focus on translating into a commonly supported language such as JUCQs which in turn can be efficiently evaluated by an SQL engine. In [START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF], the schema is maintained saturated and reformulation is applied at runtime. Our approach could apply in that setting, to improve their reformulation performance.

CONCLUSION

Datalog has also been used as a target reformulation language. For instance, Presto [START_REF] De | MASTRO: A reasoner for effective ontology-based data access[END_REF][START_REF] Rosati | Improving query answering over DL-Lite ontologies[END_REF] reformulates queries in a DL-Lite setting into non-recursive Datalog programs. These DL-Lite formalisms are strictly more expressive from a semantic constraint viewpoint than the RDFS constraints we consider. Thus, their method could be easily transferred (restricted) to the DL fragment of RDF which, as previously mentioned, is a subset of the database fragment of RDF that we consider. However, these works did not consider cost-driven performance optimization based on data statistics and a query evaluation cost model as in our work.

From a database optimization perspective, the performance advantage we gain by adding selective triples next to very large ones within query covers' fragments is akin to the semi-join reducers technique, well-known from the distributed database context [START_REF] Özsu | Principles of Distributed Database Systems[END_REF]. It has been shown e.g., in [START_REF] Stocker | Integrating semi-join-reducers into state-of-the-art query processors[END_REF] that semi-join reducers can also be beneficial in a centralized context by reducing the overall join effort. In this work, we use a technique reminiscent of semi-joins in order to pick the best query-level formulation of a reformulated query, to make its evaluation possible and efficient; this contrasts with the traditional usage of semi-joins at the level of algebraic plans.

On one hand, working at the plan level enables one to intelligently combine traditional joins and semi-joins to obtain the best performance. On the other hand, producing (as we do) an output at the query (syntax) level (recall Figure 3.1) enables us to take advantage of any existing system, and of its optimizer which will figure out the best way to evaluate such queries, a task at which many systems are good once the query has a "reasonable" shape and size. As shown in [START_REF] Leis | How good are query optimizers, really? PVLDB[END_REF], providing the relational database systems queries of "manageable" size is key, as that RDBMSs' estimation errors grows fast with the increase of the number of joins, usually leading to bad plans and therefore poor performance. Further, expressing optimized reformulations as queries allows us not to (re-)explore the search space of join orders etc. together with the (already large) space of possible reformulated queries.

Conclusion

Our work is placed in the setting of query answering against RDF graphs in the presence of RDF Schema constraints. In particular, we focus on improving the performance of reformulation-based RDF query answering.

We have identified a space of alternative JUCQ reformulations, whose evaluation (based on a standard, semantics-unaware query processor) may be (i) feasible even when the prominent UCQ reformulation is not, and (ii) more efficient by up to three orders of magnitude. Further, we have presented a cost model for such JUCQ alternatives, and proposed an anytime greedy cost-based algorithm capable of identifying such efficient alternatives. Our technique may be used with any CQ-to-UCQ query reformulation algorithm (recall Figure 3.1) and thus we consider it a big step forward toward making 3.5. CONCLUSION reformulation-based query answering efficient. This is particularly useful in contexts when the data and/or constraints are updated, and saturation-based techniques incur high maintenance costs as illustrated e.g., in [START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF]; in contrast, applying at query time, reformulation-based query answering is naturally robust to updates, and (through costbased techniques such as the one described in our work) close to saturation-based performance but without its drawbacks.

Chapter 4 Efficient FOL reducible query answering

In this chapter we transfer the idea developed in the preceding chapter to the general setting of data model and query language pairs enjoying FOL reducibility of query answering (i.e., data model and query language pairs for which query answering can be reduced to evaluating a certain first-order logic formula, obtained from the query and ontology, against only the explicit facts), encompassing many knowledge base and deductive database settings, e.g., some Description Logics, Datalog ± and Existential Rules fragments.

We propose a query optimization framework for any logical OBDA setting enjoying FOL reducibility of query answering. We extend the language of FOL reformulations beyond those considered so far in the literature, and investigate several (equivalent) FOL reformulations of a given query, out of which we pick one likely to lead to the best evaluation performance. This contrasts with existing works from the semantic query answering literature (cf. Section 4.6), which use reformulation languages allowing single FOL reformulation (modulo minimization). Considering a set of reformulations and relying on a cost model to pick a most efficient one has a very visible impact on the efficiency and feasibility of query answering: indeed, picking the wrong reformulation may cause the RDBMS simply to fail evaluating it (typically due to very lengthy queries), while in other cases it leads to bad performance.

We apply this general framework to the DL-Lite R Description Logic [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF] underpinning the popular W3C's OWL2 QL standard for rich Semantic Web applications, demonstrating significant performance advantages in this setting. Query answering in DL-Lite R has received significant attention in the literature, notably techniques based on FOL reducibility, e.g., [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF]2,[START_REF] Pérez-Urbina | Efficient query answering for OWL 2[END_REF][START_REF] Rosati | Improving query answering over DL-Lite ontologies[END_REF][START_REF] Chortaras | Optimized query rewriting for OWL 2 QL[END_REF][START_REF] Venetis | Incremental query rewriting for OWL 2 QL[END_REF].

Contributions. We bring the following contributions to the problem of optimizing FOL reducible query answering (see Figure 4.1):

q, ontology C m . . . C 1 q FOL m . . . q FOL 1 C ≡ C n ... C 1 q FOL ≡ q FOL n . . . q FOL 1 SQL SQL SQL SQL SQL SQL RDBMS Data
SQL reform. of q with best est. cost

Query answer based on data and constraints 1. For logical formalisms enjoying FOL reducibility of query answering, we provide a general optimization framework that reduces query answering to searching among a set of alternative equivalent FOL reformulations, one with minimal evaluation cost in an RDBMS (Section 4.2). In Figure 4.1, from the query q and the set of ontological constraints T , we derive first, a space of query covers, shown in the top white-background box, and denoted C with some subscripts; from each such cover we show how to derive a FOL query that may be a FOL reformulation of q w.r.t. T .

q UCQ q USCQ C USCQ C UCQ SQL SQL

2.

We characterize interesting spaces of such alternative equivalent FOL queries for DL-Lite R (Section 4.3). First, we identify a sufficient safety condition to pick covers that for sure lead to FOL reformulations of the query. This condition is met by the covers in the top yellow box in Figure 4.1, and is not met by C ≡ above them. Our safe cover space allows considering FOL reformulations encompassing those previously studied in the literature. Second, we introduce a set of generalized covers (bottom yellow box in Figure 4.1) and a generalized cover-based reformulation technique, which always yields FOL query reformulations, oftentimes more efficient than those based on simple covers.

Our approach can be combined with, and helps optimizing, any existing reformulation technique for DL-Lite R .

3.

We then optimize query answering in the setting of DL-Lite R by enumerating simple and generalized covers, and picking a cover-derived FOL reformulation with lowest estimated evaluation cost w.r.t. an RDBMS cost model estimation (denoted by the bidirectional -labeled arrows in the figure). We provide two algorithms, an exhaustive and a greedy, for this task (Section 4.4).

EVALUATING REFORMULATED SUBQUERIES CAN BE (VERY) HARD

4. Evaluating any of our FOL reformulations through an RDBMS leads (thick arrows at the right of Figure 4.1) to the query answer reflecting both the data and the constraints. We demonstrate experimentally the effectiveness and the efficiency of our query answering technique for DL-Lite R , by deploying our query answering technique on top of Postgres and DB2, using several alternative data layouts (Section 4.5).

From a query processing and optimization perspective, our approach can be seen as belonging to the so-called strategic optimization stage introduced in [START_REF] Manegold | A multi-query optimizer for Monet[END_REF] (where application semantics is injected into the query); it is also similar in spirit to the syntax-level rewrites performed by optimizers such as Oracle 10g's [START_REF] Ahmed | Cost-based query transformation in Oracle[END_REF]. We share with [START_REF] Manegold | A multi-query optimizer for Monet[END_REF] the idea of injecting semantics first, and like [START_REF] Ahmed | Cost-based query transformation in Oracle[END_REF], we use cost estimation to guide our rewrites; a common theme is to rewrite before ordering joins, selecting physical operators etc.From this angle, our contribution can be seen as a set of alternatives (rewritings) with correctness guarantees and algorithms to guide such rewritings, for the special class of queries obtained from FOL reformulations of CQ against ontologies.

In the sequel, we detail the above contributions and discuss related work and conclude in Section 4.6.

The work reported here is based on the VLDB paper [START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF] and the ISWC demo [START_REF] Bursztyn | Optimizing FOL reducible query answering: Understanding performance challenges[END_REF].

Evaluating reformulated subqueries can be (very) hard

It is worth noting that the (naïve) exhaustive application of specialization steps leads, in general, to highly redundant reformulations w.r.t. the containment of their disjuncts. For instance, minimizing q UCQ introduced in Example 8 by eliminating disjuncts contained in another leads to: q UCQ min (x):-3 i=1 q i (x) ∨ q 10 (x) where the disjuncts appear in Table 2.6; they are all contained in q 10 . q 1 (x):-PhDStudent(x) ∧ worksWith(y, x) q 2 (x):-PhDStudent(x) ∧ worksWith(x, y) q 3 (x):-PhDStudent(x) ∧ supervisedBy(y, x) q 10 (x):-supervisedBy(x, y) Table 4.1: Union terms in minimized CQ-to-UCQ reformulation.

Minimal UCQ reformulations can be obviously processed more efficiently. However, they still repeat some computations, e.g., in the above minimized CQ-to-UCQ reformulation example, PhDStudent is read three times, worksWith twice etc.; in general, subqueries appearing in different union terms are repeatedly evaluated.

Common subexpression elimination (CSE) techniques aim at identifying repeated subex-4.2. OPTIMIZATION FRAMEWORK pressions in queries or plans, and reformulating them so that the expression is evaluated only once and its results are shared to increase performance; CSE is often used in a Multi-Query Optimization context (MQO). However, MQO is poorly supported in today's main RDBMS engines 1 As we will see, our approach, which starts with the TBox and data statistics, and ends by handing over a chosen reformulation to the RDBMS, never requires work to detect common (repeated) sub-expressions.

Another source of difficulty is the sheer size of reformulated queries; we exhibit some whose size (i.e., length of the SQL formulation) is above 2.000.000 characters. For instance, the minimal UCQ corresponding to query Q 9 in our experiments (Section 4.5) is a union of 145 CQs, and runs in 5665 ms on DB2 and a database of 100 million facts. In contrast, the SQL translation of the best FOL reformulation identified by our approach reduces this to 156 ms (36 times faster), just by giving the engine a different (yet equivalent) SQLized FOL reformulation.

From an optimization viewpoint, the problem we are facing can be seen as follows. We aim at answering queries through RDBMSs in the presence of constraints, for FOLreducible settings.

The standard UCQ reformulation (and other cost-ignorant ones) perform quite badly. The question is, then: is there an equivalent reformulation which would be evaluated more efficiently?

To answer this, one is faced with a set of FOL (or, alternatively, SQL) reformulations whose size is potentially very high: exponential in the query size for non-redundant queries, larger yet if one considers, for instance, queries featuring semijoins [START_REF] Bernstein | Using semi-joins to solve relational queries[END_REF]; each query therein may be (very) large, have many unions etc.. From these, one would need to find the one(s) best optimized and executed by the RDBMS; their very high number makes this utterly impractical.

The following sections present our alternative approach.

Optimization framework

The performance of evaluating (the SQL translation of) a given FOL reformulation of a query through an RDBMS depends on several factors: (i) data properties (size, cardinalities, value distributions etc.); (ii) the storage model, i.e., the concrete relations storing the ABox, possible indexes etc.; (iii) the optimizer's algorithm. Among these, (i) is completely determined by the dataset (the given ABox). On the storage model (ii), for generality, we make no assumption, other than requiring that FOL query reformulations can be translated into SQL on the underlying store. (We study several such concrete models experimentally, in Section 4.5). For what concerns optimizers (iii),

OPTIMIZATION FRAMEWORK

we note that off-the-shelf they perform very poorly on previously proposed FOL query reformulations, yet we would like to exploit their strengths when possible.

Approach: cover-based query answering. We identify and exploit a novel space of alternative FOL reformulations of the given input CQ. We estimate the cost of evaluating each such reformulation through the RDBMS using standard database cost formulas, and hand to the RDBMS one with the best estimation.

More specifically, a query cover defines a way to split the query into subqueries, that may overlap, called fragment queries, such that substituting each subquery with its FOL reformulation (obtained from any state-of-the-art technique) and joining the corresponding (reformulated) subqueries, may yield a FOL reformulation of the original query (recall also Figure 4.1).

We begin by recasting the specific query covers from the RDFS setting of the preceding chapter into the very general framework of FOL reducible query answering. Definition 4.2.1 (CQ cover). A cover of a query q, whose atoms are {a 1 , . . . , a n }, is a set C = {f 1 , . . . , f m } of non-empty subsets of atoms of q, called fragments, such that (i) m i=1 f i = {a 1 , . . . , a n }, (ii) no fragment is included into another, and (iii) the atoms of each fragment are connected through joins (common variables).

Example 9 (CQ cover). Consider the query q(x, y):-teachesTo(v, x) ∧ teachesTo(v, y), supervisedBy(x, w) ∧ supervisedBy(y, w)

C, below, is a query cover for q: C = {{teachesTo(v, x) ∧ supervisedBy(x, w)}, {teachesTo(v, y) ∧ supervisedBy(y, w)}} Definition 4.2.2 (Fragment queries of a CQ). Let C = {f 1 , . . . , f m } be a cover of q. A fragment query q |f i ,1≤i≤m of q w.r.t. C is the subquery whose body consists of the atoms in f i and whose free variables are the free variables x of q appearing in the atoms of f i , plus the existential variables in f i that are shared with another fragment f j,1≤j≤m,j =i , i.e., on which the two fragments join.

Example 10 (Fragment queries of a CQ). The fragment queries of the query q(x, y) w.r.t. the cover C (Example 9) are:

q |f 1 (x, v, w):-teachesTo(v, x) ∧ supervisedBy(x, w)
q |f 2 (y, v, w):-teachesTo(v, y) ∧ supervisedBy(y, w)

As we shall see in the next Section, not every cover of a query leads to a FOL reformulation. Specifically, we define: Definition 4.2.3 (Cover-based reformulation). Let C = {f 1 , . . . , f m } be a cover of q, and q FOL (x):-m i=1 q FOL |f i a FOL query, where q FOL |f i , for 1 ≤ i ≤ m, is a FOL reformulation w.r.t. T of the fragment query q |f i of q.

q FOL is a cover-based reformulation of q w.r.t. T and C if it is a FOL reformulation of q w.r.t. T .

To exemplify cover-based FOL reformulations, one needs to chose a specific KB dialect, among all those enjoying FOL reducibility; we present examples in the next Section, when instantiating our framework to the DL-Lite R setting.

For now, it helps to see how we derive the SQL query corresponding to the cover-based reformulation. Each reformulated fragment query q FOL |f i is translated into an SQL query SQL i ; then, for those RDBMSs enjoying Common Table Expressions (CTEs) the overall query is of the form:

WITH SQL 1 AS q FOL |f1 , SQL 2 AS q FOL |f2 , . . . , SQL n AS q FOL |fn SELECT DISTINCT x FROM SQL 1 , SQL 2 , . . . , SQL n WHERE cond(1, 2, .
. . , n) where cond(1, 2, . . . , n) is the conjunction of the join predicates between all the subqueries. This leads to all the WITH-introduced subqueries being evaluated and materialized into intermediary tables2 , while the one with the largest number of results is run in pipeline fashion. The way in which each subquery is evaluated, then their results are joined, is left to the DBMS to determine. The SELECT DISTINCT ensures set semantics for the query answers.

We picked this syntax after experimenting with other variants, which in our experience lead to similar or worse performance. In particular, we tried:

• using one subquery for each fragment query SQL i , and joining them. Our experiments showed no improvement in general,however it's a good variant for RDBMSs that do not support CTEs.

• defining each reformulated fragment query SQL i as a (virtual) view, and joining these views in the global reformulation. This gives the query processor more freedom as it does no longer force the materialization of SQL i but instead allows its evaluation to be blended with the evaluation of the joins across reformulated fragment queries. We noticed, however, that this did not overall improve performance.

• turning SQL i subqueries into nested ones introduced with EXISTS as soon as the subquery did not contribute variables to the head of reformulated query. We tried Problem statement. We assume given a query cost estimation function which, for any FOL query q, returns the cost of evaluating it through an RDBMS storing the ABox. Thus, reflects the operations (data access, joins, unions etc.) applied on the ABox to compute the answers of a q FOL reformulation. The cost estimation also accounts for the effort needed to join the reformulated fragment query answers, in the most efficient way.

Problem 1 (Optimization problem). Given a CQ q and a KB K, the cost-driven coverbased query answering problem consists of finding a cover-based reformulation of q based on K with lowest (estimated) evaluation cost.

A cost estimation function is provided by most RDBMSs storing the ABox for instance, in the case of Postgres, through the SQL explain directive. One can also estimate costs outside the engine using well-known textbook formulas, as in e.g., Chapter 3 (Section 3.2.1) and [START_REF] Leis | How good are query optimizers, really? PVLDB[END_REF]. We use both options in our experiments.

Cover-based query answering in DL-Lite R

We now instantiate our cover-based query answering technique to the popular setting of DL-Lite R . For establishing our results as well as for our examples we rely on the simple CQ-to-UCQ reformulation technique of [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF]. However, our approach applies to any other FOL reformulation techniques for DL-Lite R , e.g., optimized CQ-to-UCQ or CQ-to-USCQ reformulation techniques, since these produce equivalent (though possibly syntactically different) FOL queries.

Example 11 (Running example). Let K be the KB with TBox T = {Graduate ∃supervisedBy, supervisedBy worksWith} and ABox A = {PhDStudent(Damian), Graduate(Damian)} Consider the query q(x):-PhDStudent(x) ∧ worksWith(x, y) ∧ supervisedBy(z, y), whose answer against K is {Damian}.

The UCQ reformulation of q is q UCQ (x):-4 i=1 q i (x) with:

q 1 (x):-PhDStudent(x) ∧ worksWith(x, y) ∧ supervisedBy(z, y) q 2 (x):-PhDStudent(x) ∧ supervisedBy(x, y)
∧ supervisedBy(z, y) q 3 (x):-PhDStudent(x) ∧ supervisedBy(x, y) q 4 (x):-PhDStudent(x) ∧ Graduate(x) Above, q 1 has the body of q; q 2 is obtained from q 1 by specializing the atom worksWith(x, y) through a backward application of supervisedBy worksWith. q3 (highlighted in blue) results from q 2 by replacing supervisedBy(x, y) and supervisedBy(z, y) with their most general unifier 3 . Finally, q 4 is obtained from q 3 , by specializing supervisedBy(x, y) through the backward application of Graduate ∃supervisedBy; we also show q 4 in blue to highlight its connection with q 3 . Now let C 1 = {{PhDStudent(x), worksWith(x, y)}, {supervisedBy(z, y)}} be a cover of q. From Definition 4.2.2, the corresponding fragment queries are:

q 1 (x, y):-PhDStudent(x) ∧ worksWith(x, y)
q 2 (y):-supervisedBy(z, y)

The reformulation of q 1 using T is q UCQ 1 (x, y):-2 i=1 q i 1 (x, y), where

q 1 1 (x, y):-PhDStudent(x) ∧ worksWith(x, y) q 2 1 (x, y):-PhDStudent(x) ∧ supervisedBy(x, y)
q 2 1 is obtained from q 1 1 by the backward application of the constraint supervisedBy worksWith. The reformulation of q 2 using T is simply:

q UCQ 2 (y):-supervisedBy(z, y)
By Definition 4.2.3, the reformulation of q using C 1 is the conjunction q JUCQ C 1 (x):-q UCQ 1 (x, y)∧ q UCQ 2 (y), which is clearly equivalent to the following UCQ obtained by distributing ∧ over ∨: q UCQ C 1 (x):-(q 1 1 (x, y) ∧ q UCQ 2 (y)) ∨ (q 2 1 (x, y) ∧ q UCQ 2 (y)) where the first and second disjuncts correspond to the CQs:

q 1 C 1 (x):-PhDStudent(x) ∧ worksWith(x, y) ∧ supervisedBy(z, y) q 2 C 1 (x):-PhDStudent(x) ∧ supervisedBy(x, y)
∧ supervisedBy(z, y)

Above, q 1 C 1 (x) and q 2 C 1 (x) are exactly q 1 and q 2 from the UCQ reformulation of q; however, q 3 and q 4 are missing from q JUCQ C 1 (x). Since q 4 derives from q 3 , the absence of both can be traced to the absence of q 3 . The reason C 1 does not lead to q 3 is that supervisedBy(x, y)∧supervisedBy(z, y) is not obtained while reformulating q 1 (x, y), thus the unification of these two atoms (which could have lead to q 3 ) is missed. In the CQ-to-UCQ reformulation of q, supervisedBy(x, y)∧supervisedBy(z, y) appears in q 2

COVER-BASED QUERY ANSWERING IN DL-LITE R

because worksWith(x, y) ∧ supervisedBy(z, y) appears in q 1 . However, C 1 separates the worksWith and supervisedBy atoms in different fragments. Reformulating them independently misses exactly the opportunity to produce q 3 and q 4 . Due to these absent subqueries, q JUCQ C 1 is not a FOL reformulation of q w.r.t. T , i.e., it fails to compute q's answer: ans(q JUCQ C 1 , ∅, A ) = ∅ while the answer of q against K is {Damian}.

More generally, given an input CQ and a TBox, each pair of query atoms begetting unifications during the CQ-to-UCQ reformulation of the whole query must not be separated by (must not be in different fragments of) a cover, in order for the corresponding coverbased reformulation to be a FOL reformulation. When this is the case, we say the cover is safe for query answering. Thus, we are interested in a sufficient condition for a cover to be safe; intuitively, we must approximate (by some supersets) those sets of atoms which (directly or after some specializations) are pairwise unified by the CQ-to-UCQ algorithm, and ensure that each such atom set is in the same cover fragment.

Only atoms with the same predicate may unify. Thus, we identify for each predicate (i.e., concept or role name) occurring in a query, the set of all TBox predicates in which this predicate may turn through some sequence of atom specializations, i.e., backward constraint application and/or unification (the two operations applied by the technique of [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF] which we consider here). This is captured by the classical notion of dependencies between predicates within knowledge bases, Datalog programs, etc. In DL-Lite R , this notion translates into the following recursive definition. Given a TBox T , a concept or role name N depends w.r.t. T on the set of concept and role names denoted dep(N ) and defined as the fixpoint of:

dep 0 (N )= {N } dep n (N )= dep n-1 (N ) ∪ {cr(Y ) | Y X ∈ T and cr(X) ∈ dep n-1 (N )}
where cr(Y ) returns, for any input Y of the form Z, Z -or ∃Z (for some concept or role Z), the concept or role name Z itself. Definition 4.3.2 (Safe cover for query answering). A cover C of q is safe for query answering w.r.t. T (or safe in short) iff it is a partition of q's atoms such that two atoms whose predicates depend on a common concept or role name w.r.t. T are in a same fragment.

Note that while Definition 4.3.2 requires covers to be partitions, we will relax this restriction in Section 4.4.2.

Theorem 4.3.1 (Cover-based query answering). Let C be a safe cover for q w.r.t. T . The cover-based reformulation (Definition 4.2.3) of q based on C, using any CQ-to-UCQ (resp. CQ-to-USCQ) reformulation technique, yields a cover-based reformulation q FOL of q w.r.t. T .

Proof. The proof follows from that of correctness of the CQ-to-UCQ reformulation technique in [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF] for query answering. It directly extends to the use of any CQ-to-UCQ or CQ-to-USCQ reformulation technique for DL-Lite R , as, for any CQ and TBox, the FOL queries they compute are equivalent to the query produced by the technique described in [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF].

Soundness: for any T -consistent Abox A, ans(q FOL , ∅, A ) ⊆ ans(q, T , A ) holds.

Let t be a tuple in ans(q FOL , ∅, A ). From Definition 4.2.3, q FOL is q FOL (x):-m i=1 q FOL |f i , thus t results from t i ∈ ans(q FOL |f i , ∅, A ), for 1 ≤ i ≤ m. Therefore, for 1 ≤ i ≤ m, t i ∈ ans(q |f i , T , A ) holds, because of the soundness of the CQ-to-UCQ reformulation technique. Hence, from Definition 4.2.3, t ∈ ans(q, T , A ) holds.

Completeness: for any T -consistent Abox A, ans(q, T , A ) ⊆ ans(q FOL , ∅, A ) holds.

Let t be a tuple in ans(q, T , A ). Let q UCQ be its reformulation using the CQ-to-UCQ technique. From the completeness of this technique, t ∈ ans(q UCQ , ∅, A ) holds. Let q UCQ be α l=1 cq l , then necessarily for some l: t ∈ ans(cq l , ∅, A ) holds [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF]. Let q FOL be m i=1 q FOL |f i = m i=1 β i j=1 cq i,j . Since Definition 4.3.2 makes the reformulation of each fragment independent from another w.r.t. the CQ-to-UCQ technique, for any cq l in q UCQ : cq l = m i=1 cq i,k∈[1,β i ] holds. Hence, t ∈ ans(q FOL , ∅, A ) holds.

If a CQ-to-UCQ reformulation algorithm is used on fragment queries, the cover-based reformulation will be a JUCQ; otherwise, a CQ-to-USCQ reformulation of the fragment queries lead to a JUSCQ reformulation.

Note that the trivial one-fragment cover (comprising all query atoms) is always safe; in this case, our query answering technique reduces to just one reformulation, the CQ-to-UCQ one identified by previous reformulation algorithms from the literature.

COVER-BASED QUERY OPTIMIZATION IN DL-LITE R

Example 13 (JUCQ reformulation with a safe cover). We now consider the safe cover C 2 = {{PhDStudent(x)}, {worksWith(x, y), supervisedBy(z, y)}}. The cover-based reformulation based on C 2 is the JUCQ query q JUCQ (x):-q UCQ 1 (x) ∧ q UCQ 2 (x), where:

q UCQ 1 (x):-PhDStudent(x) q UCQ 2 (x):-(worksWith(x, y) ∧ supervisedBy(z, y)) ∨ (supervisedBy(x, y) ∧ supervisedBy(z, y)) ∨ supervisedBy(x, y) ∨ Graduate(x)
Observe that ans(q JUCQ , ∅, A ) = {Damian} = ans(q, T , A ).

Cover-based query optimization in DL-Lite R

We study now the query answering optimization problem of Section 4.2 for DL-Lite R . We analyze a first optimization space in Section 4.4.1, before extending our discussion to a larger space in Section 4.4.2. Finally, we describe our search algorithms in Section 4.4.3.

Safe covers optimization space

Below, we study the space of safe covers for a given query and TBox. We start by identifying a particularly interesting one: Definition 4.4.1 (Root cover). We term root cover for a query q and TBox T the cover C root obtained as follows. Start with a cover C 1 where each atom is alone in a fragment. Then, for any pair of fragments f 1 , f 2 ∈ C 1 and atoms a 1 ∈ f 1 , a 2 ∈ f 2 such that there exists a predicate on which those of a 1 and a 2 depend w.r.t. T , create a fragment

f = f 1 ∪ f 2 and a new cover C 2 = (C 1 \ {f 1 , f 2 }) ∪ {f }.
Repeat the above until the cover is stationary; this is the root cover, denoted C root .

It is easy to see that C root does not depend on the order in which the fragments are considered (due to the inflationary method building it). Further, C root is safe, given that it keeps in a single fragment any two atoms whose predicates may be unified.

The following important lemma characterizes the structure of C root fragments:

Lemma 1 (C root fragment structure). A fragment f in the root cover C root is of one of the following two forms:

1. a singleton, i.e., f = {a i } for some query atom a i ; 2. f = {a i 1 , . . . , a in }, for n ≥ 2, and for every atom a i 1 ∈ f , there exists one atom a i 2 ∈ f , and a predicate b j in the TBox, such that both the predicates of a i 1 and of a i 2 depend on b j .

Proof. The lemma follows directly from the definition of C root . Those atoms that do not share a dependency with any other atom appear in singleton fragments (case 1 above, as the construction of the root cover never groups them together). Atoms which share some dependencies (i.e., atoms whose predicates depend on one another) get unioned in fragments of the form 2 above.

Example Proposition 4.4.1 states that C root has the maximal number of fragments (equivalently, it has the smallest fragments) among all the safe covers for q and T ; its proof is based on Lemma 1.

Proposition 4.4.1 (Minimality of C root fragments). Let C root be the root cover for q and T , and C be another safe cover. For any fragment f ∈ C root , and atoms a i , a j ∈ f , there exists a fragment f ∈ C such that a i , a j ∈ f , in other words: any pair of atoms together in C root are also together in C.

Proof. For ease of explanation, in the proof, we rely on the graphical directed graph representation used in Figure 4.2 for dependencies between the predicates appearing in the atoms of a cover and/or other predicates from the KB.

Because f holds at least a i and a j , it must be a fragment of form 2, as stated in Lemma 1. It follows, thus, that in f there exists what we call an extended path e, going from a i to a j following the dependency edges either from source to target, or in the opposite direction; in other words, e alternately moves "up (or down) then down (or up)" a certain number of times in the fragment.

COVER-BASED QUERY OPTIMIZATION IN DL-LITE R

If e only contains edges in the same direction (either all are → or all are ←), it follows immediately that a i and a j are in the same fragment of C.

In the contrary case, there must exist some predicates in the TBox b 1 , . . . , b m , m ≥ 1, and some f atoms a 1 , . . . , a m-1 defining an extended path e from a i to a j in f , as follows:

1. Since C is safe, a i and a 1 must appear in the same fragment in C (and only in that fragment), because they both depend on b 1 .

a i → . . . → b 1 (a → path segment), or b 1 is the predicate used in a i ; 2. b k (1 ≤ k < m -1), is the predicate used in a l (k ≤ l < m -1), or b k ← . . . ← a l (a ← path segment); 3. b k ← . . . ← a l (a ← path segment), with 1 ≤ k < m -1 and k ≤ l < m -1,
For 1 ≤ i ≤ m -2, a i must appear in the same fragment as a i+1 (and only there), given that they both depend on b i .

Since C is safe, a j and a m-1 must appear in the same fragment of C (and only there).

From the above follows that {a i , a 1 , . . . , a m-1 , a j } are all in the same fragment of C, which contradicts our hypothesis.

From Proposition 4.4.1, we obtain:

Theorem 4.4.2 (Safe cover space). Let C be a safe cover and f one of its fragments. Then, f is the union of some fragments from C root .

Proof. Suppose that f is not a union of some fragments from C root , and let us show a contradiction. In this case, f necessarily contains a strict, non-empty subset of a fragment of C root . It follows that there are two atoms whose predicates depend on a common concept or role name w.r.t. T (as they were together in the fragment of C root ) that are not in a same fragment of C. Therefore C is not a safe cover, a contradiction.

Safe cover lattice. Theorem 4.4.2 entails that the safe covers of a query q form a lattice, denoted L q , whose precedence relationship is denoted ≺, where C 1 ≺ C 2 iff each fragment of C 2 is a union of some fragments of C 1 . The lattice has as lower bound the single-fragment cover, and as upper bound the root cover. For convenience, we also use L q to denote the set of all safe covers.

The size of the safe cover lattice is bounded by the number of partitions of the fragments in C root , i.e., by the number of partitions of the query atoms 4 , a.k.a. the Bell number B n for a query of n atoms; the bound occurs when there is no dependency between the atom predicates.

Generalized covers optimization space

A dependency-rich TBox leads to few, large fragments in C root , thus to a relatively small number of alternative cover-based reformulations. In this section, we explore a notion of generalized covers, and propose a method for deriving FOL query reformulations from such covers. This enlarges our space of alternatives and thus potentially leads to a better cost-based choice of reformulation.

We call generalized fragment of a query q and denote f g a pair of q atom sets such that g ⊆ f . A generalized cover is a set of generalized fragments C = {f 1 g 1 , . . . , f m g m } of a query q such that ∪ 1≤i≤m f i is the set of atoms of the query, and no f i is included in

f j for 1 ≤ i = j ≤ m.
To a generalized fragment f g of a generalized cover C, we associate: Definition 4.4.2 (Generalized fragment query of a CQ). The generalized fragment query q |f g of q w.r.t. C is the subquery whose body consists of the atoms in f , and whose free variables are the free variables of q appearing in the atoms of g, plus the variables appearing in an atom of g that are shared with some atom in g , for some other generalized fragment f g of C.

In a generalized fragment query, atoms from f \ g only reduce (filter) the answers, without adding variables to the head. In particular, if f = g, q |f g coincides with the regular fragment query (Definition 4.2.2).

Given a generalized cover, the generalized cover-based reformulation of a query q is the FOL query

q g (x):- m i=1 q FOL |f i g i if q g is a FOL reformulation.
If f i = g i for all the fragments f i g i , the generalized cover-based reformulation coincides with the regular cover-based one (Definition 4.2.3). As for simple cover-based reformulations, if fragments are reformulated into UCQs, the reformulated query is a JUCQ, whereas if they are reformulated into USCQs, the reformulated query is a JUSCQ.

COVER-BASED QUERY OPTIMIZATION IN DL-LITE R

The introduction of extra atoms in generalized fragments is reminiscent of the classical semijoin reducers [START_REF] Bernstein | Using semi-joins to solve relational queries[END_REF], whereas one computes R(x, y) y S(y, z) by (R(x, y) y π y (S(y, z))) y S(y, z)

where y denotes the left semijoin, returning every tuple from the left-hand side input that joins with the right-hand input. The semijoin filters ("reduces") the R relation to only those tuples having a match in S. If there are few distinct values of y in S, π y (S(y, z)) is small, thus the y operator can be evaluated very efficiently. Further, if only few R tuples survive the y , the cost of the y operator likely decreases with the size of its input.

While the benefits of semijoins are well-known, there are many ways to introduce them in a given query, increasing the space of alternative plans to be considered by an optimizer. While some heuristics have been proposed to explore only some carefully chosen semijoin plans [START_REF] Stocker | Integrating semi-join-reducers into state-of-the-art query processors[END_REF], we noted that RDBMS optimizers do not explore semijoin options, in particular for the very large queries resulting from the FOL reformulations of CQs.

Generalized fragments mitigate this problem by intelligently using semijoin reducers to fasten the evaluation of the FOL reformulation by the RDBMS.

Generalized search space. We now define the space G q of generalized covers for a given query q, based on the safe cover set L q . A generalized cover C = {f 1 g 1 , . . . , f m g m } is part of G q iff:

• The cover C s = {g 1 , . . . , g m } is safe, i.e., C s ∈ L q ;

• For each 1 ≤ i ≤ m, the atoms in f i form a connected graph.

Note that an atom a ∈ f , for f g ∈ C, has no impact on the head of the corresponding generalized fragment query; only the body of this query changes.

The size of G q obviously admits that of L q as a lower bound. For a query q of n atoms, a upper bound is B n * n * 2 n-1 , where B n is the n-th Bell number: for each safe cover C (of which there are at most B n , see the previous section), each of the n atoms may, in the worst case, be added or not to all the fragments to which it does not belong. In the worst case, there are n -1 such fragments.

The core result allowing us to benefit of the performance savings of generalized covers in order to efficiently answer queries is:

Theorem 4.4.3 (G q cover-based query answering). The reformulation of a query q based on T and a generalized cover C ∈ G q is a FOL reformulation of q w.r.t. T .

Proof. The proof follows from that of Theorem 4.3.1. It relies on the fact that, given a safe cover C = {g 1 , . . . , g m } of q and a generalized cover C = {f 1 ||g 1 , . . . , f m ||g m } of q, the queries q(x):-m i=1 q |g i and q (x):-m i=1 q |f i ||g i are equivalent, though each q |g i subsumes q |f i ||g i . Indeed, q is obtained from q by duplicating atoms already present in q, thus q e only adds redundancy w.r.t. q, hence remains equivalent to it.

COVER-BASED QUERY OPTIMIZATION IN DL-LITE R

Example 16 (Generalized cover-based reformulation). Recall the query and KB from Example 11. Let f 0 = {PhDStudent(x)} and f 1 = {worksWith(x, y), supervisedBy(z, y)} be the two fragments of the root cover C root . Consider also the generalized cover

C 3 = {f 1 f 1 , f 2 f 0 }, where f 2 = {PhDStudent(x), worksWith(x, y)}.
The generalized fragment query q |f 1 f 1 of q w.r.t. C 3 is the subquery q |f 1 f 1 (x):-worksWith(x, y) ∧ supervisedBy(z, y). Observe that y is not a free variable of q |f 1 f 1 , as it is neither a free variable of q nor a variable in f 0 , whereas f 2 f 0 is the only other fragment in the cover C 3 .

The generalized fragment query q |f 2 f 0 of q w.r.t. C 3 is the subquery q |f 2 f 0 (x):-PhDStudent(x) ∧ worksWith(x, y). Again, note that y is not a (free) variable of f 0 , and therefore it is not a free variable of q |f 2 f 0 .

Then, the generalized cover-based reformulation corresponding to C 3 is the FOL query:

q g (x):-q FOL |f 1 f 1 (x) ∧ q FOL |f 2 f 0 (x)
where:

q FOL |f 1 f 1 (x):-(worksWith(x, y) ∧ supervisedBy(z, y)) ∨ supervisedBy(x, y) ∨ Graduate(x) q FOL |f 2 f 0 (x):-(PhDStudent(x) ∧ worksWith(x, y)) ∨ (PhDStudent(x) ∧ supervisedBy(x, y)) ∨ (PhDStudent(x) ∧ Graduate(x))
Applying supervisedBy worksWith to q |f 1 f 1 leads to:

(worksWith(x, y) ∧ supervisedBy(z, y)) ∨ (supervisedBy(x, y) ∧ supervisedBy(x, y)) ≡ (worksWith(x, y) ∧ supervisedBy(z, y))

∨ supervisedBy(x, y)

Then, applying Graduate ∃supervisedBy, we obtain the reformulation of q |f 1 f 1 w.r.t. TBox T , i.e., q FOL |f 1 f 1 . Similarly, applying to q |f 2 f 0 the constraint supervisedBy worksWith and subsequently Graduate ∃supervisedBy leads to q FOL |f 2 f 0 . Note that ans(q g , ∅, A ) = {Damian} = ans(q, T , A ).

Cost-based cover search algorithms

Our first algorithm, EDL (Exhaustive Covers for DL), starts from C root and builds all L q covers by unioning fragments, and all G q covers by adding atoms (Algorithm 3).

Algorithm 3: Exhaustive Cover Search for DL-Lite R (EDL) The second one, GDL (Greedy Covers for DL) (Algorithm 4) works in a greedy fashion. It is based on exploring, from a given cover C, the set of possible next moves (lines 2-4 and 5-7); these are all the covers that may be created from C by unioning two of its fragments or by enlarging one of its fragments, i.e., turning a fragment f g into f ∪ {a} g for some query atom a sharing a variable with f . The best one seen at a given point (w.r.t. the estimated evaluation cost) is kept as the selected next move in the move variable. Lines 2 and 5, respectively, assign to move the move where the union of fragments f 1 and f 2 is performed on cover C, and the move enlarging fragment f with atom a on cover C.

Input : CQ q(x):-a 1 ∧ • • • ∧ a n , KB K Output: Best cover for reformulating for q 1 L q ← ∅; G q ← ∅ ; 2 F ← C root ; C best ← C root ; 3 foreach P = {s 1 , . . . , s |P | } distinct partition of F s.t
s i = {f 1 i , . . . , f n i i } ∈ P do 6 C P ← C P ∪ {f 1 i ∪ • • • ∪ f n i i }; 7 L q ← L q ∪ {C P }; 8 if C P estimated cost < C best estimated cost then 9 C best ← C P ; 10 foreach safe cover C = {f 1 , f 2 , . . . , f n } ∈ L q do 11 C ← {f 1 ||f 1 ,
At the end of this exploration step (line 9), the best move is applied, leading to the new best cover C from which the next exploration step starts. The exploration stops when no possible next move improves the cost of the currently selected best cover C.

When unioning two fragments, decreases if the resulting fragment is more selective 4.5. EXPERIMENTAL EVALUATION Algorithm 4: Greedy Cover Search for DL-Lite R (GDL) than the two fragments it replaces. Therefore, the RDBMS may find a more efficient way to evaluate the query reformulation of this fragment, and/or its result may be smaller, making the evaluation of q FOL based on the new cover C faster. When adding an atom to an extended fragment, decreases if the conditions are met for the semijoin reducer to be effective (Section 4.4.2). In our context, many such opportunities exist, as our experiments show.

Input : CQ q(x):-a 1 ∧ • • • ∧ a n , KB K Output: Best cover for reformulating q 1 C ← C root ; move ← ∅; 2 foreach f 1 , f 2 ∈ C do 3 if (move is empty and C.union(f 1 , f 2 ) est. cost ≤ C est. cost) or (C.union(f 1 , f 2 ) est. cost < apply(move) est. cost) then 4 move ← (C, f 1 , f 2 ); 5 foreach f ∈ C, a ∈ q s.

Experimental evaluation

We implemented our cover-based query answering approach in Java 8; the source code has about 10.000 lines, including the statistics and cost estimation (see below).

Experimental settings

RDBMSs and data layout. First, we used PostgreSQL v9.3.2 to store the data and evaluate FOL query reformulations. Our first data layout within Postgres stored all the assertions into a single triple table (where each C(x) ∈ A leads to a triple x type C and each R(a, b) ∈ A leads to a triple a R b), and built all six three-attribute indexes on this triple table [START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF]. Our second data layout stored a unary table for each concept and a binary table for each role, and built all one-and two-attribute indexes, respectively, 4.5. EXPERIMENTAL EVALUATION on those tables. Our tests showed that the second layout significantly outperformed the first; this is not surprising, as smaller tables lead to better performance, at the same time it reduces the number of query conditions (as some of them are encoded by accessing a certain table). Thus, for Postgres, we only report results based on the layout featuring role and concept tables.

Second, we used the IBM DB2 Express-C 10.5. We chose it because (i) we previously (Chapter 3) found out (and confirm below) that it evaluates large FOL reformulations better than Postgres, and (ii) it provides a relatively recent, smart storage layout for RDF graphs [START_REF] Mihaela | Building an efficient RDF store over a relational database[END_REF], intelligently bundling assertions into a small set of tables with potentially many attributes, so that the roles to which an individual participates are stored, to the extent possible, in the same tuple. This reduces the number of joins needed for query evaluation, and has been shown [START_REF] Mihaela | Building an efficient RDF store over a relational database[END_REF] to improve query performance. However, DB2 does not support reasoning, i.e., it only provides query evaluation. For DB2, we report results based on the concept and role tables (denoted simple layout) and on the RDF layout of [START_REF] Mihaela | Building an efficient RDF store over a relational database[END_REF].

In the simple layout, as customary in efficient Semantic Web data management systems, e.g., [START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF], facts are dictionary-encoded into integers, prior to storing them in the RDBMS. The TBox and predicates dependencies are stored in memory.

Hardware. The database servers ran on an 8-core Intel Xeon E5506 2.13 GHz machine with 16GB RAM, using Mandriva Linux r2010.0.

Datasets, queries, and reformulation engine. We used two LUBM ∃ 20 benchmark KBs, comprising a DL-Lite R TBox and two ABoxes of 15 million, respectively, 100 million facts, obtained using the EUDG data generator [START_REF] Lutz | The combined approach to OBDA: taming role hierarchies using filters[END_REF]. The TBox consists of 34 roles, 128 concepts and 212 constraints.

We devised a set of 13 CQs against this knowledge base, shown in the Section A.2, Tables A. [START_REF] Adjiman | SomeRDFS in the semantic web[END_REF] and A.6. The queries have between 2 and 10 atoms, with an average of 5.77 atoms. Their UCQ reformulations are unions of 35 to 667 CQs, 290.2 on average. This parameter characterizing the query can be seen as a (rough) measure of the complexity of its reformulation; it is shown in Table A.5 in the column |q UCQ |.

We relied on the RAPID [START_REF] Chortaras | Optimized query rewriting for OWL 2 QL[END_REF] CQ-to-UCQ reformulation tool to reformulate (simple or generalized) fragment queries (Definitions 4.2.2 and 4.4.2); any other CQ-to-UCQ or CQto-USCQ reformulation technique could have been used instead.

Cost estimation function. For the cost function estimation , we first used the RDBMS cost estimation for the SQL translation of each candidate FOL reformulation produced by our algorithms. For Postgres, we obtained this using explain5 , while for DB2 we used db2expln 6 .

Further, for the simple layout, we implemented our own Java-based cost estimation, based on statistics on the stored data (cardinality and number of distinct values in each stored table attribute), and on the uniform distribution and independent distributions assumptions. Better RDF cardinality estimation techniques such as [START_REF] Neumann | Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins[END_REF] may be used to improve the accuracy of our cost model.

For the sake of completeness, the next Section details how we compute the cost of evaluating a JUCQ (reformulation) sent to an RDBMS; this presentation is borrowed and adapted from Section 3.2.1.

Our cost estimation function

A JUCQ is a join of UCQs subqueries of the form:

q JUCQ (x):-q UCQ 1 • • • q UCQ m . The evaluation cost of q JUCQ is c(q JUCQ ) = c db + 1≤i≤m c eval (q UCQ i ) + i,1≤i≤m,i =k c mat (q UCQ i ) + c join (q UCQ i,1≤i≤m ) + c unique (q JUCQ ) (4.1)
reflecting:

(i) the fixed overhead of connecting to the RDBMS c db ;

(ii) the cost to evaluate each of its UCQ sub-queries q UCQ i ;

(iii) the materialization costs: the SQL query corresponding to a JUCQ may have many sub-queries. At execution time, some of these subqueries will have their results materialized (i.e., stored in memory or on disk) while at most one sub-query will be executed in pipeline mode. We assume without loss of generality, that the largest-result sub-query, denoted q UCQ k , is the one pipelined (this assumption has been validated by our experiments so far);

(iv) the cost to join these sub-query results; and (v) the cost of eliminating duplicates, in order to enforce our desired set semantics: from the results of each q UCQ i , and from the final results, by means of DISTINCT clauses. We found that this two-level elimination of duplicates lead to the best performance overall. Note that removing duplicates in the results of q UCQ i does not break an evaluation pipeline, as those results were materialized anyway. Notations. For a given query q over a database db, we denote by |q| t the estimated number of tuples in q's answer set. Also, q |{a i } stands for the restriction of q to its ith atom. Using the notations above, the number of tuples in the answer set of q |{a i } is denoted

|q |{a i } | t .
Duplicate elimination costs. Assuming duplicate elimination is implemented by hashing, we estimate the cost of eliminating duplicate rows from an SQL query q JUCQ and/or q UCQ i ) as:

c unique (q JUCQ ) = c l × |q JUCQ | t
where c l is the CPU and I/O effort involved in sorting the results.

When the results are large enough to require disk merge sort, we estimate the cost of eliminating duplicate rows from q JUCQ (and q UCQ i as a particular case) result as:

c unique (q JUCQ ) = c k × |q JUCQ | t × log |q JUCQ | t
where c k is the CPU and I/O effort involved in (disk-based) sorting the results.

UCQ evaluation costs are estimated by summing up the estimated costs of the CQs:

c eval (q UCQ i ) = q CQ ∈q UCQ i c eval (q CQ )
The cost of evaluating one conjunctive query c eval (q CQ ), where q CQ (x):-a 1 ∧ • • • ∧ a n , through the RDBMS is estimated by analyzing the selections (known attribute values) in each atom of q CQ , estimating (exactly -see below) how many triples match these atoms, and estimating the data access costs and the join costs together. The data layouts we consider feature indexes on the relations storing class and role instances; as soon as the query selections and joins allow it, the RDBMS heavily relies on the indexes to simultaneously join and access the data i.e., the plan chains index-based accesses and index-based joins. Assuming efficient join algorithms such as hash-or merge-based etc. are available [START_REF] Ramakrishnan | Database Management Systems[END_REF], the join-only cost of q CQ is linear in the total size of its inputs:

c join (q CQ ) = c j × a i ∈q CQ |q CQ |{a i } | t
where c j is a constant factor representing per-tuple join effort. Therefore, we have:

c eval (q UCQ i ) = (c t + c j ) × q CQ ∈q UCQ i a i ∈q CQ |q CQ |{a i } | t (4.2)
where c t is a constant representing the per-tuple I/O (access) effort.

UCQ join cost. As before, we consider the join cost to be linear in the total size of its inputs:

c join (q UCQ i,1≤i≤m ) = c j × m i=1 q CQ ∈q UCQ i a i ∈q CQ |q CQ |{a i } | t (4.3)
UCQ materialization cost. Finally, we consider the materialization cost associated to a query q is c m × |q| t for some constant c m :

c mat (q UCQ i,1≤i≤m,i =k ) = c m × m i=1,i =k q CQ ∈q UCQ i a i ∈q CQ |q CQ |{a i } | t (4.4)
where q UCQ k is the largest-result sub-query, and the one which is picked for pipelining (and thus not materialized).

Injecting the equations 4.2, 4.3 and 4.4 into the global cost formula 4.1 leads to the estimated cost of a given JUCQ. This formula relies on estimated cardinalities of various subqueries of the JUCQ, as well as on the system-dependent constants c db , c l , c k , c j , c t and c m , which we determine by running a set of simple calibration queries (inspired by the approach of [START_REF] Gardarin | Calibrating the query optimizer cost model of IRO-DB, an object-oriented federated database system[END_REF]) on the RDBMS being used; calibration details are straightforward and we omit them here.

For what concerns cardinality estimations, as in [START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF], RDBMS statistics provide, for each query atom, the exact number of triples matching it. Subsequently, textbook formulas are used to estimate the cardinality of more complex subqueries, based on statistics on the minimum and maximum value, and the number of distinct values in each attribute. We make the simple assumptions of uniform distribution of each attribute, and independent distributions among attributes. Any more refined RDF cardinality estimation technique, e.g., [START_REF] Neumann | Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins[END_REF], could be used to improve the estimation accuracy.

Search space and EDL running time

We first studied the number of covers in L q and G q (recall Section 4.4). Our workload features some queries of 2 atoms, and the immediately larger ones have 6; we quickly realized that the number of generalized covers is prohibitively high for 6 or more atoms.

To study this more closely, we derived from Q 1 a set of queries A i , 3 ≤ i ≤ 6, each of which is a star-join of i atoms on a common subject; in particular, A 6 is Q 1 . Star queries are frequent over Semantic Web Data, as noted e.g., in [START_REF] Weiss | Hexastore: Sextuple indexing for Semantic Web data management[END_REF][START_REF] Mihaela | Building an efficient RDF store over a relational database[END_REF]. The sizes of the resulting search spaces are reported in Table 4.2; for A 6 we stopped the search at 20.003 generalized covers (there were more). This demonstrates that exploring the full G q space is in general not feasible, as the overhead of examining so many options is 4.5. EXPERIMENTAL EVALUATION prohibitive. Thus, in the sequel, we do not use EDL for our tests, as it is impractical beyond (very) small queries. Table 4.2 also shows the number of covers explored by the greedy GDL: these grow very moderately with the query size.

Finally, for A 3 -A 6 , the running times of the best reformulation found by EDL and GDL (limited at 20.000 covers for A 6 ) coincided. In general this is not guaranteed, but it is still an encouraging indicator of the good options found by GDL. 1. the UCQ produced by the RAPID [START_REF] Chortaras | Optimized query rewriting for OWL 2 QL[END_REF] reformulation engine; 2. the JUCQ reformulation based on C root ; 3. a JUCQ reformulation corresponding to a best-performing (safe or generalized) cover, found by our algorithm GDL, using Postgres' cost estimation (RDBMS);

Evaluation time of reformulated queries

4. a JUCQ reformulation corresponding to a best-performing (safe or generalized) cover, found by our algorithm GDL, using our cost estimation (ext).

GDL running time is not reported in these graphs (see Section 4.5.5). We first analyze the top graph corresponding to LUBM ∃ 20 15 million triples. It shows, first, that the UCQ reformulation is inefficient (one order of magnitude slower than the best reformulation found, e.g., for Q 5 and Q 9 ). Second, the cover derived from C root may also be very inefficient, in some cases (Q 6 -Q 8 , Q 13 ) much worse than the UCQ. These are both very large and complex queries; Figure 4.3 demonstrates that Postgres' optimizer called directly on the fixed-form reformulation may performed quite poorly. The GDL-selected covers, in contrast, lead to the best-performing reformulations for all queries (often by an order of magnitude). Thus, our cost-based approach helps ask the RDBMS the optimization question it can best answer, among its equivalent formulations from the search space G q . Striking exceptions are Q 9 , Q 10 which have both many atoms and complex reformulations, and Q 11 which has 2 atoms but the maximum number (667) of reformulations. Here, the GDL reformulations selected using the RDBMS cost model perform very poorly, whereas the ones based on our own cost estimation are much faster. This may be because Postgres takes drastic shortcuts when estimating the cost of an extremely large query; in contrast, our cost estimation treats uniformly queries of all sizes. Recall that Postgres' optimizer always has the last word in chosing how to evaluate the reformulation we select, using its own cost model. Thus, the difference can only be attributed to the cost estimation. Evaluation on DB2. The graph at the top of Figure 4.5 shows the evaluation time for DB2, on LUBM ∃ 20 15 million triples, of seven reformulations: the same four which we ran on Postgres, to which we add, on the RDF layout [START_REF] Mihaela | Building an efficient RDF store over a relational database[END_REF]: the UCQ reformulation, the one based on C root , and the ones selected by GDL with the help of the RDBMS cost model. We did not code a cost estimation corresponding to this RDF-specific store, since (i) an accurate model of data access costs under such a complex layout (determined by running a linear programming solver etc..) seemed very hard to attain outside the server and (ii) DB2's cost model performed similarly to (or better than) ours for all the GDLselected covers, on the simple layout. Thus, replacing it with our own seemed unlikely to improve the performance. Note the logarithmic y axis of the graph.

The bottom graph in

First, note that five bars are missing (replaced by the vertical lines), one for Q 9 and four for Q 10 . They all correspond to reformulations against the RDF layout. The server error was "The statement is too long or too complex. Current SQL statement size is 2,247,118" for the UCQ of Q 9 , and the same error (with similar query sizes) in the other cases. This shows that the cummulated impact of, first, the DB2RDF storage layout (which leads to IF... THEN... ELSE and nesting in the SQL query corresponding to a simple CQ), and second, of ontology-based reformulation, yields queries too large for evaluation. For illustration, the SQL versions of Q 1 before and after UCQ reformulation on DB2's RDF store appear at http://bit.ly/1TqeVMA. In cases where DB2 handled them, the reformulations corresponding to the UCQ, C root and GDL on the RDF layout performed very poorly, up to 1 (UCQ) or even 4 (C root ) orders of magnitude worse than the best reformulations identified. Thus, our (somehow unexpected) conclusion is that the RDF-specific layout, while interesting for CQ evaluation, is not the best alternative when evaluating queries issued from reformulation against an ontology.

Focusing only on the simple layout, we see that the cost-unaware UCQ and C root -derived reformulations perform again poorly, while the GDL ones perform best and in many cases coincide. The two cost estimations behaved mostly the same, except that our estimation worked better for Q 8 and worse for Q 9 . Overall, our chosen reformulations lead to performance gains of up to a factor of 9 w.r.t. the UCQ and/or C root on the simple layout, for which we found DB2's cost estimation quite reliable.

At the bottom of Figure 4.5 we show the evaluation times on LUBM ∃ 20 100 million triples for the first eight among the ten reformulations shown in the top graph (we gave up GDL on the RDF layout, given our experience on the smaller 4.5. EXPERIMENTAL EVALUATION dataset). The four execution errors (grey vertical lines) on the UCQ and C root reformulations on the RDF layout are again due to overly large SQL queries. The first four alternatives are overall the worse, with C root and at a lesser extent UCQ on the RDF layout performing very poorly. When focusing on the simple layout only, we notice that the cost-based reformulations improve over the simple UCQ performance by a factor of up to 36 (4.85 on average). There is an exception for Q 8 , where the UCQ was best; in this case, both DB2's and our cost estimations were inaccurate, which we believe cannot be avoided in all cases. DB2's estimation lead to significantly better reformulations than ours for the queries Q 2 , Q 8 , Q 9 and Q 12 , while our cost model was clearly better for Q 13 . Overall, we found DB2's cost estimation more accurate than our own (while the opposite holds for Postgres). By inspecting query plans, we confirmed that DB2 and Postgres do not apply any CSE across union terms. The better performance of DB2 is likely due to efficient runtime support for repeated scans [START_REF] Lang | Increasing buffer-locality for multiple relational table scans through grouping and throttling[END_REF].

In all experiments presented in this section, GDL ran between 1 ms (for 2-atom queries) to 207 ms (for the larger Q 1 ); we discuss the running time of our optimization approach in more detail in Section 4.5.5.

Finally, always (when using our cost model) and about half of the time (with the RDBMS cost model), GDL picked a generalized cover. This confirms the interest of searching in the G q space. 4.5.5 Time-limited GDL Figure 4.6 shows the running time of algorithm GDL on the LUBM datasets of 15 million and 100 million triples, in four configurations: using no cost estimation (this artificial case where all costs are estimated to 0 was built to measure our algorithm's running time independently of the cost estimation time); using our own cost estimation (described in Section 4.5.2); using the cost estimation of Postgres; and finally, using the estimation of DB2. Note that the vertical axis is in logarithmic scale. The two graphs are similar, which is to be expected given that we measure optimization time, which is not (strongly) impacted by the data sizes. The times using Postgres' and DB2's cost estimations are not identical: internal heuristics in the Postgres and DB2 systems may have led to different plans shapes being explored for the different database sizes.

We make the following observations. 1. The running time of GDL without any cost estimation is very small, bounded by 23 ms.

2. Using our cost model has a discernible yet still small overhead, bringing the total running time of our optimization technique to about 207 ms.

3. Using Postgres' cost estimation time incurs a significant overhead, going up to 10, 100 and even (in the pathological case of Q 5 ) 1000 seconds, which is prohibitive for an optimization step.

EXPERIMENTAL EVALUATION

4. Using DB2's cost estimation is for many queries even more expensive. This is because the db2expln utility requires large queries to be written into an OS file given as parameter to the cost estimation, whose output must then be extracted from the detailed information db2expln returns. This is more expensive than Postgres' provided explainer functionality, which is accessible through the JDBC driver, without the need to make a runtime call from our Java optimizer code etc.. 5. GDL including DBMS cost estimation is visibly correlated with the size of the query; note the peaks for Q 5 , Q 9 and Q 10 , which are the most complex (as shown in Table A.5).

The graphs show that it is clearly preferrable to run GDL in a context where the cost estimation function is accessible without a high overhead. This was the case when using our own estimation, while the estimations of Postgres and especially DB2 were harder for us to access.

Time-limited GDL. Therefore, we investigated a time-limited version of GDL, which was allowed to explore only during 20 ms. Figure 4.7 compares the running time of the cover found by GDL after only 20 ms, with that of the cover found by GDL allowed to run to completion. We see that the running times are very close for Postgres, and also generally close for DB2, demonstrating that interesting covers are quickly found. This is because on our queries, the strongest reduction (mostly through reducing intermediary result sizes) are identified early during the greedy search, thus most of the performance benefits can be reaped early on. More generally, this corresponds to the good behavior of greedy algorithms when there are very advantageous moves to be made. Thus, we find time-limited GDL performs well in practice, for a modest overhead.

Against the expectation, in some cases, the limited GDL performed better than the unlimited one (for instance, on Q 5 and Q 7 on DB2 in Figure 4.7). This is an accident due to our cost model; it turns out that in these cases, the longer search ended up recommending a state whose cost was slightly worse.

Experiment conclusions

Our experiments show that plain UCQ reformulation is evaluated poorly by both Postgres and DB2, even more so (or even fails) on DB2's RDF-specific data layout. On the simple layout, the fixed cover-based reformulation corresponding to the root cover C root also performs very poorly. In contrast, GDL-selected reformulation improve over the UCQ in all 13 queries ×2 systems ×2 datasets but one, and they do so by up to a factor of 36. Our cost estimation helped w.r.t. Postgres' explain, but when using DB2, we find db2explain's estimation more accurate overall. The generalized cover space has prohibitive size, thus EDL is impractical. In contrast, our greedy GDL is efficient when used with a low-overhead cost estimation (such as

RELATED WORK AND CONCLUSION

the one we implemented), and effective in optimizing reformulated queries. GDL attains most of its cost reductions early on during the search, making it a robust tool for improving reformulated query answering performance.

Related work and conclusion

We proposed a novel framework for any OBDA setting enjoying FOL reducibility of query answering, for which we studied a space of alternative FOL reformulations to evaluate through an RDBMS. We applied this framework to the DL-Lite R description logic, and experimentally demonstrated its performance benefits.

Relationship with prior work on reformulation-based query answering

Our approach departs from the literature focused on a single FOL query reformulation, where optimization mainly reduces to producing fast a UCQ reformulation as minimized as possible: [

-Lite R , existential rules and Datalog ± . [START_REF] Thomazo | Compact rewriting for existential rules[END_REF] studies CQ-to-USCQ reformulation for existential rules encompassing DL-Lite R ; USCQ reformulations are shown to perform overall better than UCQ ones in an RDBMS. We build on these works to devise CQ-to-JUCQ and CQ-to-JUSCQ reformulation techniques, and used cost estimations to speed up reformulated query evaluation. In particular, our generalized covers can be seen as adapting semijoin-based reducers to the query answering setting. [START_REF] Rosati | Improving query answering over DL-Lite ontologies[END_REF] proposes a cost-unaware CQ-to-Datalog reformulation technique; it produces a non-recursive Datalog program, which amounts to a JUCQ.

One contribution of this work is an optimization framework (Section 4.2) for any formalism for which query answering is FOL-reducible, e.g., some Description Logics, Datalog ± and Existential Rules fragments. The work presented in Chapter 3 is a particular case of this framework for the RDFS ontology language, which corresponds only to the constraints 1, 4, 5 and 11 from Table 2.3, while the DL-Lite R language we use comprises 22 such constraints. When reformulating under this rich language, some covers are unsafe (recall Example 11), while in the work presented in the previous chapter any cover leads to a correct query reformulation for the 4 constraints considered there. DL-Lite R is important as it is provides the foundations for W3C's standard for very large Semantic Web data management OWL2 QL. Thus, the other contributions of our work are: to identify and characterize safe covers, guaranteed to lead to reformulations, and a carefully chosen extra space of generalized covers which lead to equivalent FOL reformulations and often improve query performance. Our EDL and GDL optimization algoritms (Section 4.4.3) respectively explore exhaustively and greedily this DL-Lite Rspecific space to speed up reformulation-based query answering under DL-Lite R constraints. Another difference w.r.t. the work introduced in the preceding chapter is that 4.6. RELATED WORK AND CONCLUSION this work explores the usage of DB2's RDF store, and find it unsuitable to the complex queries resulting from reformulation.

In the database and Semantic Web communities, there have been intense efforts invested in developing scalable RDF data management platforms, including distributed ones; see e.g., the survey [START_REF] Kaoudi | RDF in the clouds: a survey[END_REF]. However, these platforms do not take constraints into account, and thus only support query evaluation, not query answering. Our work is the first to consider optimized algorithms for answering queries under DL-Lite R constraints through relational databases.

Relationship with prior work on multi-query optimization

Generally speaking, the relationship can be stated as follows. Multi-query optimization (MQO) is interesting as soon as the query to be evaluated has redundant (repeated) subexpressions. In our setting, we distinguish:

Reformulation-induced redundancy refers to the repeated subexpressions appearing in a reformulated query due to the reformulation itself. The UCQ has most such redundancies, as illustrated e.g., in Table 3 in the paper.

Reformulation-independent redundancy designates the redundancy that a query may have regardless of the impact of reformulation; for instance, a query may feature repeated subexpressions prior to reformulation, even if the TBox is empty etc.

MQO vs. reformulation-independent redundancy. Any SQL processor capable of MQO can be profitably used to evaluate the cover-based reformulations we chose, in order to diminish or eliminate reformulation-independent redundancy. As mentioned in Section 4.1, there was no algebra-level MQO available in the free and commercial engine used in our study, thus our estimation for a cover-based reformulation cost does not take it into account (although some partial support is provided e.g., in Oracle [START_REF] Bellamkonda | Enhanced subquery optimizations in Oracle[END_REF]).

One reason why MQO performed during query optimization is complex is the difficulty of deciding equivalence between two logical expressions; under the set semantics used in our work, this is NP-hard even for CQ. Works such as [START_REF] Manegold | A multi-query optimizer for Monet[END_REF][START_REF] Bellamkonda | Enhanced subquery optimizations in Oracle[END_REF] use syntactic equality of plans, as a criterium for deciding semantic equivalence; this is sufficient in [START_REF] Manegold | A multi-query optimizer for Monet[END_REF] because of the focus restricted on select-group by queries over a single table, and in [START_REF] Bellamkonda | Enhanced subquery optimizations in Oracle[END_REF] because under bag semantics, equivalent conjunctive queries are isomorphic [START_REF] Chaudhuri | Optimization of Real Conjunctive Queries[END_REF]. Under set semantics, both approaches would lead to missing many equivalences, and thus many sharing opportunities. In [START_REF] Neumann | Generating optimal DAG-structured query evaluation plans[END_REF], a similar syntactic condition is used for efficiency, knowing that it may miss sharing opportunities.

If MQO-enabled systems became available, the cost estimation should also reflect its presence; this would be immediately the case for the system's own cost estimation, and would require a revision of our cost estimation function.

RELATED WORK AND CONCLUSION

We view the possible usage of an MQO-capable SQL engine to handle reformulationindependent redundancy in the query as orthogonal to our work. To avoid unwanted impact on our study, none of the queries used in our study featured reformulationindependent redundancy.

MQO vs. reformulation-induced redundancy. Reformulating a CQ against a TBox may introduce many repeated subexpressions. The UCQ has most such redundancies, as illustrated e.g., in Table 3 in the paper.

However, our technique applies before the common subexpression factorization stage; in the terms of [START_REF] Manegold | A multi-query optimizer for Monet[END_REF], our work belongs to the strategical optimization stage, which injects application knowledge and constraints into the optimization problem. Unlike the setting envisioned in [START_REF] Manegold | A multi-query optimizer for Monet[END_REF], however, we do not use such knowledge to create one plan, but several reformulations, each of which can be seen mid-way between a plan and a query. Indeed, while a cover-based reformulation is still a query, it does make some ordering decisions, in particular each reformulated fragment query is evaluated, and all but one are materialized, before the cover-based reformulation evaluation is finalized by a join. Thus, our approach, which starts with the TBox and data statistics, and ends by handing over a chosen reformulation to the RDBMS, never requires work to detect common (repeated) sub-expressions. Instead:

1. In the simpler setting of an RDFS TBox (Chapter 3), the so-called SCQ reformulation (which pushes all unions immediately above the scans [START_REF] Thomazo | Compact rewriting for existential rules[END_REF]) has the least possible repeated sub-expressions. For instance, on a query of two atoms a 1 , a 2 , such that a 1 reformulates into a 1 1 and a 2 reformulates into a 1 2 and a 2 2 , the SCQ reformulation is:

(a 1 ∨ a 1 1 ) ∧ (a 2 ∨ a 1 2 ∨ a 2 2 )
while the UCQ (featuring many repeated scans) is:

(a 1 ∧ a 2 ) ∨ (a 1 ∧ a 1 2 ) ∨ (a 1 ∧ a 2 2 ) ∨ (a 1 1 ∧ a 2 ) ∨ (a 1 1 ∧ a 1 2 ) ∨ (a 1 1 ∧ a 2 2 )
(For larger queries, the UCQ also features repeated joins.)

2. In the context of the present work, the SCQ may not be a FOL reformulation. When redundancy conflicts with correctness, we should clearly favor correctness first. The safe cover C root is the closest approximation of the SCQ in our context, as it applies the least amount of atom merging within fragments.

Fortunately, C root is very efficient to build from the TBox and the query: the complexity is O(|q| 2 ), since we need to compare all the pairs of atoms to see whether they depend on a same TBox predicate. This contrasts with the very high complexity of the abovementioned algebraic MQO techniques [START_REF] Zhou | Efficient exploitation of similar subexpressions for query processing[END_REF][START_REF] Neumann | Generating optimal DAG-structured query evaluation plans[END_REF].

RELATED WORK AND CONCLUSION

Interestingly, an Oracle 10g [START_REF] Ahmed | Cost-based query transformation in Oracle[END_REF] reference mentions MQO rewritings which factorize common join expressions across union terms. This would apply to the UCQ setting, however, as mentioned above, based on the TBox, we can much more efficiently minimize redundancy by chosing the C root cover. Also, according to [START_REF] Ahmed | Cost-based query transformation in Oracle[END_REF], MQO exploration would have to be drastically cut for queries with hundreds of union terms. Thus, our approach is more practical as it exploits information about the source of redundancy (namely the reformulation process using the ontology). In contrast, an optimizer has to deal with the consequences (detect redundant subexpressions).

The abovementioned Oracle work [START_REF] Ahmed | Cost-based query transformation in Oracle[END_REF] also mentions query transformations (rewrites) applied at the level of the syntax, in a bottom-up fashion; to learn if a certain subplan rewriting is profitable, the optimizer's cost estimation is used. This strategy of preprocessing of the query guided by the DBMS cost estimator is similar in spirit to our approach (Figure 4.1), and also comparable to the "strategical optimization" stage [START_REF] Manegold | A multi-query optimizer for Monet[END_REF] which applies first in the query optimization process, and injects data and application semantics into the plan.

Our approach could be profitably integrated as a rewrite specific to ontology-based reformulation, within a strong cost-based optimizer such as the one of Oracle [START_REF] Ahmed | Cost-based query transformation in Oracle[END_REF]. In particular, this would give us access to more sophisticated query cost estimations, while eliminating the overhead we currently pay to get them through a connection to the server.

Currently, we lack access to strong industrial optimizers such as the ones of DB2, SQL Server or Oracle; Postgres' optimizer is easier to extend, but our experiments have shown it is weaker than DB2's.

Other well-known MQO/CSE algorithms have been described e.g., in [START_REF] Giannikis | Shared workload optimization[END_REF][START_REF] Manegold | A multi-query optimizer for Monet[END_REF][START_REF] Neumann | Generating optimal DAG-structured query evaluation plans[END_REF][START_REF] Zhou | Efficient exploitation of similar subexpressions for query processing[END_REF].

Oracle includes several query rewrites to improve nested query performance, among which subquery coalesce reduces some redundancy and thus can be seen as related to CSE [START_REF] Bellamkonda | Enhanced subquery optimizations in Oracle[END_REF]. A different class of techniques [START_REF] Lang | Increasing buffer-locality for multiple relational table scans through grouping and throttling[END_REF][START_REF] Zukowski | Cooperative scans: Dynamic bandwidth sharing in a DBMS[END_REF] improve the performance of multiple concurrent reads of a table; this can be seen as a physical-level MQO only applying to one-table plans. Such techniques are implemented in DB2, and they indeed help evaluating our reformulations. However, as stated in Section 4.1, our approach does not require detecting repeated subexpressions.

Chapter 5

Conclusion and perspectives

In this chapter, we summarize the contributions previously presented (Section 5.1) and present perspectives for future work, divided in two main parts: ongoing work in a hybrid store project (Section 5.2), and perspectives connected to the main part of this thesis, namely efficient query answering in an ontology-based data access setting (Section 5.3).

Summary

This thesis provides solutions for efficient ontology-based data access query answering in RDF, the prominent W3C standard for the Semantic Web, and in the DL-Lite R description logic underpinning W3C's OWL2 QL standard for semantic-rich data management. We summarize the problems below.

Efficient query answering in the presence of RDFS constraints. We consider optimizing reformulation-based query answering in the setting of OBDA, where SPARQL conjunctive queries are posed against RDF facts on which constraints expressed by an RDF Schema hold. The literature provides query reformulation algorithms for many fragments of RDF. However, reformulated queries may be complex, thus may not be efficiently processed by a query engine; well established query engines even fail processing them in some cases.

1. We generalize the query reformulation approach, by considering a large space of alternative (equivalent) reformulations. We characterize the size of our space of alternatives, and show that it is oftentimes too large to be completely explored.

2. We define a cost model for estimating the evaluation performance of our reformulated queries through a relational engine; other functions can be used instead, and we show that an RDBMSs' internal cost model can easily be used, too.

3. We devise a novel algorithm which selects one alternative reformulated query 5.1. SUMMARY which (i) computes the same result as the reformulated query, q ref , produced by state-of-the-art reformulation algorithms, and (ii) reduces significantly the query evaluation cost (or simply makes it possible when evaluating q ref fails!)

4. We implemented this algorithm and deployed it on top of three well-established RDBMSs. Our experiments show that our technique enables reformulation-based query answering where the state-of-the-art approaches are simply unfeasible, while it may decrease its cost by orders of magnitude in other cases.

5. Finally, we compare our reformulation-based query answering technique against saturation-based query answering, both through an RDBMS and the native RDF platform Virtuoso. These experiments confirm the robustness and performance of our technique, showing in particular that in some cases its performance approaches that of saturation-based query answering.

Efficient FOL reducible query answering. We consider ontology languages enjoying FOL reducibility of query answering: answering a query can be reduced to evaluating a certain first-order logic (FOL) formula (obtained from the query and ontology) against only the explicit facts. We extend the language of FOL reformulations beyond those considered so far in the literature, and investigate several (equivalent) FOL reformulations of a given query, out of which we pick one likely to lead to the best evaluation performance. This contrasts with existing works from the semantic query answering literature, which use reformulation languages allowing single FOL reformulation (modulo minimization). Considering a set of reformulations and relying on a cost model to pick a most efficient one has a very visible impact on the efficiency and feasibility of query answering: indeed, picking the wrong reformulation may cause the RDBMS simply to fail evaluating it (typically due to very lengthy queries), while in other cases it leads to bad performance.

1. For logical formalisms enjoying FOL reducibility of query answering, we provide a general optimization framework that reduces query answering to searching among a set of alternative equivalent FOL reformulations, one with minimal evaluation cost in an RDBMS 2. We apply the above mentioned framework to the DL-Lite R Description Logic underpinning the W3C's OWL2 QL ontology language. We characterize interesting spaces of such alternative equivalent FOL queries for DL-Lite R reformulations, and then optimize query answering in such setting by picking an alternative equivalent FOL reformulation with lowest estimated evaluation cost w.r.t. an RDBMS cost model estimation. We provide two algorithms, an exhaustive and a greedy, for this task.

3. Evaluating any of our FOL reformulations through an RDBMS leads to the query answer reflecting both the data and the constraints. We demonstrate experimentally the effectiveness and the efficiency of our query answering technique for 5.2. ONGOING WORK: TOWARDS SCALABLE HYBRID STORES DL-Lite R , by deploying our query answering technique on top of Postgres and DB2, using several alternative data layouts.

Ongoing Work: Towards Scalable Hybrid Stores

Data management goes through interesting times 1 , as the number of currently available data management systems (DMSs) is probably higher than ever before. This leads to unique opportunities for data-intensive applications often involving diverse datasets, some very large while others may be of moderate size, some highly structured (e.g., relations) while others may have more complex structure (e.g., graphs) or little structure (e.g., text or log data), as some systems provide excellent performance on certain data processing operations. Yet, it also raises great challenges, as a system efficient on some tasks may perform poorly or not support other tasks, making it impossible to use a single DMS for a given application.

As part of my thesis, I have started to study the possibility to use different DMSs side by side in order to take advantage of their best performance, as advocated under terms such as hybrid or poly-stores. Observe that even once such a combination of stores is chosen, it may need to be changed over time, as the data or application needs change, as new more efficients system may become available, or on the contrary their usage needs to be discontinued (for instance due to changes in the application owner's IT policy, or in the pricing of a certain commercial system). In such cases, one should not have to modify (rewrite) the applications, but rather have it run and adapt seamlessly to the new context.

The work on ESTOCADA has lead to so far to a CIDR 2015 vision paper [START_REF] Bugiotti | Invisible glue: Scalable self-tunning multi-stores[END_REF] and the ICDE demonstration in 2016 [START_REF] Bugiotti | Flexible hybrid stores: Constraint-based rewriting to the rescue[END_REF]. Below, we motivate it through an example (Section 5.2.1), outline the core scientific problems and describe our architecture and state of advancement (Section 5.2.2). Finally, Section 5.2.3 places our work in the area of similar research projects.

Motivating Example and Challenges

We illustrate this through an example. Consider a traditional customer relationship management (CRM) application. While typically CRM needed to deal only with a relational data warehouse, now the application needs to incorporate new data sources in order to build a better knowledge of its customers: (i) information gleaned from social network graphs about clients' activity and interests, and (ii) log file from multiple e-commerce stores, characterizing the clients' purchase activity in those stores.

ONGOING WORK: TOWARDS SCALABLE HYBRID STORES

The in-house RDBMS performs well on the relational data. However, the social graph data fits badly in that system, and the company attempts to store it in a dedicated graph store, until an engineer argues that it should be decomposed and stored into a highlyefficient NoSQL key-value store system she has just experimented with. The storage and processing of log files is delegated to a Hive installation (over Hadoop), until the summer research intern observes that recent work [START_REF] Lefevre | MISO: souping up big data query processing with a multistore system[END_REF] has shown that some data from Hive should be lifted at runtime in the relational data warehouse to gain a few orders of magnitude of performance! Deploying and exploiting the CRM application for best performance is set to be a nightmare now. There is little consensus on what systems to use, if any; three successive engineers have recommended (and moved the social data into and out of) three different stores, one for graphs, one for key-value pairs, and the last an in-memory column database. Part of the log data has been moved in the in-memory column store, too, when the social data was stored there; this made their joint exploitation faster. But the whole log dataset could not fit in the single-node column store installation, and data migration fatigue had settled in before a suggestion was made (and rejected) to move everything to yet another cluster installation of the column store. The team working on the application feels battered and confused. The application is sometimes very slow. Migrating data is painful at every change of system; they are not sure the complete data set survived at each step, and data keeps accumulating. Yet, a new system may be touted as the most efficient for graph (or for log) data next week. The possibility that the next efficient store would drastically improve performance further confuses the situation as the teem sees it. Would it be faster? How to know?

My thesis research has contributed to designing and implementing ESTOCADA, a novel architecture for efficiently handling highly heterogeneous datasets based on a dynamic set of potentially very different data stores. While heterogeneous data integration is an old topic [START_REF] Levy | Querying Heterogeneous Information Sources Using Source Descriptions[END_REF][START_REF] Alon | Answering queries using views: A survey[END_REF][START_REF] Deutsch | MARS: A System for Publishing XML from Mixed and Redundant Storage[END_REF][START_REF] Manolescu | Answering XML queries on heterogeneous data sources[END_REF], the remark "one-size does not fit all" [START_REF] Stonebraker | One Size Fits All": An Idea Whose Time Has Come and Gone[END_REF] has been revisited for instance in the last CIDR [START_REF] Lim | How to Fit when No One Size Fits[END_REF][START_REF] Jindal | WWHow! Freeing Data Storage from Cages[END_REF][START_REF] Dittrich | Say No! No! and No! In CIDR[END_REF], and the performance advantages brought by multi-stores have been recently noted e.g., in [START_REF] Lefevre | MISO: souping up big data query processing with a multistore system[END_REF]. The set of features which, together, make ESTOCADA novel are:

Natively multi-model ESTOCADA supports a variety of data models, including flat and nested relations, trees and graphs, including important classes of semantic constraints such as primary and foreign keys, inclusion constraints, redundancy of information within and across distinct storage formats, etc. which are needed to enforce application semantics.

Application-invisible ESTOCADA provides to client applications access to each dataset in its native format. This does not preclude other mapping / translation logic above ESTOCADA' client API but we do not discuss them in this paper. Instead, our focus is on efficiently storing the data, even if in a very different format from its original one, as discussed below.

Fragment-based store Each data set is stored as a set of fragments, whose content may overlap. The fragmentation is completely transparent to ESTOCADA' clients, i.e., it is the system's task to answer queries based on the available fragments.

Mixed store Each fragment may be stored in any of the stores underlying a ESTOCADA installation, be it relational, tree-or graph-structured, based on key-value pairs etc., centralized or distributed, disk-or memory-based etc. Thus, potentially any piece of any dataset may reside in any of the available systems; each query may be answered by combining data from any set of systems. Query answering must be aware of the constraints introduced implicitly when storing fragments in nonnative models. For instance, when tree-structured data are stored in a relational store, the resulting edge relation satisfies the constraint that each node has at most one parent, the descendant and ancestor relations are inverses of each other and are related non-trivially to the edge relation, etc.

View-based rewriting and view selection

The invisible glue holding all the pieces together is view-based rewriting with constraints. Specifically, each data fragment is internally described as a materialized view over one or several datasets; query answering amounts to view-based query rewriting, and storage tuning relies on view selection. Describing the stored fragments as views over the data allows changing the set of stores with no impact on ESTOCADA' applications [START_REF] Alon | Answering queries using views: A survey[END_REF]; this simplifies the migration nightmare outlined above. Finally, our reliance on views gives sound foundation to efficiency, as it guarantees the complete storage of data, and the correctness of the fragmentation and query answering, among others.

Technical challenges

The ESTOCADA scenario involves the coexistence of a large number of materialized views mixing data formats (modeling the native sources) with significant redundancy between them (due to repeated migration and view selection arising organically over the history of the system, as opposed to clean-slate planning). While the problem of rewriting using views is classical, it has typically been addressed and practically implemented only in limited scenarios that do not apply here. These scenarios feature (i) only relatively small numbers of views; (ii) minimal overlap between views as their selection is planned ahead of time; (iii) views expressed over the same data model; (iv) rewriting that exploits only limited integrity constraints (typically only key/foreign key in existing systems). The large number of views and their redundancy notoriously contribute (at least) exponentially to the explosion in the search space for rewritings, even when working within a single data model.

Achitecture and state of advancement

We briefly recall the fundamental definitions of query equivalence and query containment [START_REF] Ashok | Optimal implementation of conjunctive queries in relational data bases[END_REF][START_REF] Aho | Efficient Optimization of a Class of Relational Expressions[END_REF][START_REF] Aho | Equivalences Among Relational Expressions[END_REF][START_REF] Johnson | Optimizing Conjunctive Queries that Contain Untyped Variables[END_REF][START_REF] Chaudhuri | Optimization of Real Conjunctive Queries[END_REF][START_REF] Libkin | Query Languages for Bags and Aggregate Functions[END_REF][START_REF] Chekuri | Conjunctive query containment revisited[END_REF]. We denote a database instance by D and use q(D) to denote the result of evaluating a query q over database D.

Definition 5.2.1 (Query equivalence). Two queries q 1 , q 2 are equivalent, denoted q 1 ≡ q 2 , iff q 1 (D) ≡ q 2 (D) for any database D.

Definition 5.2.2 (Query containment). A query q 1 is say to be contained in another query q 2 , denoted q 1 ⊆ q 2 , iif we have q 1 (D) ⊆ q 2 (D) for any database D.

Observe that if q 1 ⊆ q 2 and q 2 ⊆ q 1 , then q 1 ≡ q 2 . Based on the above: Definition 5.2.3 (Equivalent query rewriting). Given a query q and a set of views V, an equivalent rewriting of q using V is an expression e(v 1 , v 2 , . . . , v k ), v i ∈ V, 1 ≤ i ≤ k, over the views in V, which is equivalent to q. In other words, for any database D, e(v 1 , v 2 , . . . , v k )(D) = q(D).

Definition 5.2.3 covers full (complete) rewritings, which rely only on the materialized views. Partial rewritings, combining V views and the database D itself are also interesting. However, the rewritings that interest us in ESTOCADA are those considering the base data available and modeled by a set of views, i.e., complete rewritings.

Query rewriting using (materialized) views (a.k.a. view-based query rewriting, viewbased query reformulation) algorithms sought to find all the possible (equivalent) rewritings of a given query q using an specified set of views V [START_REF] Alon | Answering queries using views: A survey[END_REF].

We now explain how ESTOCADA aims at automating the solution to scenarios such as the one previously described.

Fragments described as materialized views. To adapt to changes in the datasets, workload, and set of DMSs being used, we chose to internally represent each data fragment as a materialized view over one or several datasets; thus, query answering amounts to view-based query rewriting. As is well-known from prior work in data integration, this local-as-view approach allows the application to remain unchanged as the underlying data collections are modified. Further, our reliance on views gives sound foundation to efficiency, as it guarantees the complete storage of data, and the correctness of the fragmentation and query answering.

To further simplify the development of applications, each dataset is accessed through a language specific to its native data model, be it SQL for relational stores, key-based search API for key-value data, etc. However, for efficiency, a fragment F of a dataset D (whose data model is M D ) may be stored in a data model M F different from M D ; similarly, a fragment F may store combined results from different datasets of possibly different data models, leading to more cross-model transformation of the data between the application dataset and the stored fragments.

Relational pivot model with constraints. To enable query rewriting over and across different data models, we translate into an internal pivot model the declarative specification of the data stored in each fragment, as well as the incoming query, formulated in the application dataset model; specifically, our pivot model is based on relational conjunctive queries. Further, to correctly account for the characteristics of each application data model M a and storage data model M s , we describe their specific features in the same pivot model, by means of powerful constraints.

For instance, we describe the organization of a document data model (whether this concerns M a or M s ) using a small set of relations such as Node(nID, name), Child(pID, cID), Descendant(aID, dID), etc. together with the constraints specifying that every node has just one parent and one tag, that every child is also a descendant. Such modeling had first been introduced in local-as-view data integration XML integration works [START_REF] Manolescu | Answering XML queries on heterogeneous data sources[END_REF][START_REF] Deutsch | MARS: A System for Publishing XML from Mixed and Redundant Storage[END_REF].

More generally, constraints allow a faithful internal modeling of datasets, since they can express functional dependencies and keys (for instance, node or tuple IDs) naturally present in many settings, be it relations, documents or graph stores. Also, importantly for the usage of key-value stores, we rely on an original encoding of access pattern restrictions such as "the value of the key must be specified in order to access the values associated to this key" into relations with constraints. This enables building only feasible rewritings, i.e., such that the information needed to access a given data source is either provided by the query, or has been obtained from data sources previously accessed while evaluating the rewriting.

Rewriting under constraints: optimized Chase & Backchase. To rewrite queries in the presence of constraints, the method of choice is known as Chase & Backchase (C&B, in short), a classical powerful tool long considered too inefficient to be of practical relevance. ESTOCADA exploits the very significant performance savings brought by the recent provenance-aware C&B algorithm (PACB, in short) [START_REF] Ileana | Complete yet practical search for minimal query reformulations under constraints[END_REF]. PACB drastically reduces the back-chase effort by keeping track of the results of the various chase steps applied during the algorithms, to avoid repeated and fruitless work; this results in rewriting speedups that can even outperform a commercial relational optimizer by 1-2 orders of magnitude (in terms of combined optimization and execution time).

Rewriting decoding. From the above, it follows that query rewriting takes place, first, at the level of our pivot relational conjunctive model endowed with constraints, and it leads to a rewriting which is a conjunctive query over the relations corresponding to the stored fragments.

Depending on the data model of these fragments, the relational atoms used in the rewritings may either correspond to actual relations, or to key-value collections which can be seen as relations with binding patterns, or to the virtual relations used to encode more complex data models, such as the Node, Child and Descendant relations mentioned above (the encoding of nested relations such as supported e.g., in Pig and HBase is very similar). From this relational, conjunctive rewriting, a rewriting translation step is performed to:

1. Group the rewriting atoms referring to each distinct fragment involved in the rewriting; for instance, it can be inferred that the three atoms Document(dID, "file.json"), Root(dID, rID), Child(rID, cID), Node(cID, book) found in a rewriting refer to a single document, by following the connections among nodes and 3. If several fragments are stored in the same underlying DMS, identify the largest subquery that can be delegated to that DMS, along the lines of query evaluation in wrapper-mediator systems [START_REF] Tomasic | Scaling heterogeneous databases and the design of disco[END_REF]. Observe that if the DMS has a distributed architecture, e.g., Spark deployed on a cluster, the delegated subquery will be evaluated in parallel fashion, allowing ESTOCADA to leverage its efficiency.

Evaluation of non-delegated operations. A decoded rewriting may be unable to push (delegate) some query operations to the DMS storing a fragment if the DMS does not support them; for instance, most key-value and document stores do not support joins.

Similarly, if a query on structured data requests the construction of new nested results (such as JSON or XML documents, or nested tuples), and if the inputs to this operation are not stored in a DMS supporting such result construction natively, it will have to be executed outside of the underlying DMSs. To evaluate such "last-step" operations, ESTOCADA comprises its own lightweight execution engine, based on a nested relational model, whose atomic types include constants, node IDs, and document types; it provides in particular implementations of the BindJoin operator needed to access data sources with access restrictions. The engine is a close variant of the one previously developed in the ViP2P project and used e.g., in [START_REF] Manolescu | Efficient xquery rewriting using multiple views[END_REF][START_REF] Karanasos | Vip2p: Efficient XML management in DHT networks[END_REF][START_REF] Karanasos | Delta: Scalable data dissemination under capacity constraints[END_REF].

Choice of the most efficient rewriting to use. For a given query and set of fragments, there may be several rewritings, each of which may lead to several evaluation plans of different performance. The problem of chosing the best rewriting and best evaluation plan in this setting is quite close to the one previously considered in distributed mediator systems [START_REF] Özsu | Principles of Distributed Database Systems[END_REF], with the extra difficulty that one needs to compare the performance of execution across a variety of stores. At the time of this writing, this part of the project is not complete, and thus will not delve upon it further; we expect it to be addressed in future work.

Architecture. Figure 5.1 outlines the architecture of our prototype based on the above discussion. We assume the typical application uses many data sets D 1 , D 2 , . . . , D n , even though our smart storage method may be helpful even for a single data set, distributing it for efficient access across many stores, potentially based on different data models.

The Storage Descriptor Manager stores information about the available data fragments D 1 /F

Related Work on Hybrid Stores

Heterogeneous data integration is an old topic [START_REF] Levy | Querying Heterogeneous Information Sources Using Source Descriptions[END_REF][START_REF] Alon | Answering queries using views: A survey[END_REF][START_REF] Deutsch | MARS: A System for Publishing XML from Mixed and Redundant Storage[END_REF][START_REF] Manolescu | Answering XML queries on heterogeneous data sources[END_REF] but the remark "one-size does not fit all" [START_REF] Stonebraker | One Size Fits All": An Idea Whose Time Has Come and Gone[END_REF] has been recently revisited [START_REF] Lim | How to Fit when No One Size Fits[END_REF][START_REF] Jindal | WWHow! Freeing Data Storage from Cages[END_REF]. The performance benefits of using multiple stores together (a Hadoop one and a relational database) have been demonstrated in [START_REF] Lefevre | MISO: souping up big data query processing with a multistore system[END_REF]; they select relational views to be materialized based on cost information, but do not handle multiple data models through a unified approach as we do. Polystores [START_REF] Elmore | A Demonstration of the BigDAWG Polystore System[END_REF][START_REF] Duggan | The BigDAWG polystore system[END_REF] allow querying heterogeneous stores by grouping similar-model platform into "islands" and explicitly sending queries to one store or another; data sets can also be migrated by the users. This contrasts with our LAV approach where the data store variety is hidden to the application layer. The integration of "NoSQL" stores has been considered e.g., in [START_REF] Atzeni | Uniform access to NoSQL systems[END_REF] again in a top-down GAV approach without considering materialized views.

Adaptive stores for a single data model have been studied e.g., in [START_REF] Idreos | Database Cracking[END_REF][START_REF] Alagiannis | H2O: a hands-free adaptive store[END_REF][START_REF] Dash | Cophy: A scalable, portable, and interactive index advisor for large workloads[END_REF][START_REF] Katsifodimos | Materialized view selection for XQuery workloads[END_REF][START_REF] Karpathiotakis | Justin-time data virtualization: Lightweight data management with ViDa[END_REF]; views have been also used in [START_REF] Shute | F1: A Distributed SQL Database That Scales[END_REF][START_REF] Agrawal | Asynchronous View Maintenance for VLSD Databases[END_REF] to improve the performance of a large-scale distributed relational store. The novelty of ESTOCADA here is to support multiple data models, by relying on powerful query reformulation techniques under constraints.

Data exchange tools such as Clio [START_REF] Fagin | Data exchange: Semantics and query answering[END_REF][START_REF] Haas | Clio grows up: from research prototype to industrial tool[END_REF] allow migrating data between two different schemas. We aim at providing to the applications transparent data access to heterogeneous systems, relying on fundamentally different rewriting techniques.

View-based rewriting and view selection are grounded in the seminal works [START_REF] Alon | Answering queries using views: A survey[END_REF][START_REF] Levy | Querying Heterogeneous Information Sources Using Source Descriptions[END_REF]; the latter focuses on maximally contained rewritings, while we target exact query rewriting, which leads to very different algorithms. Further setting our work apart is the scale and usage of integrity constraints. Our pivot model recalls the ones described in [START_REF] Deutsch | MARS: A System for Publishing XML from Mixed and Redundant Storage[END_REF][START_REF] Manolescu | Answering XML queries on heterogeneous data sources[END_REF] but ESTOCADA generalizes these works by allowing multiple data models both at the application and storage level.

To conclude, we believe hybrid (multi-store) architectures have the potential to bring huge performance improvements, since (redundant) views storing query results can increase the efficiency of query evaluation by many orders of magnitude. ESTOCADA supports this by a local-as-view approach whose immediate benefit is flexibility since it requires no work when the underlying data storage changes; we demonstrate its performance benefits and the interest of simple storage recommendation heuristics. Our work is ongoing toward a cost-based recommendation of optimal fragmentation.

PERSPECTIVES

Perspectives

Semantic Web data management as well as hybrid stores open numerous avenues for future research; we outline some of them below.

DAG plans for query answering in the presence of RDFS constraints. To improve the performance of reformulated query evaluation performance even further, a natural extension of the work presented in Chapter 3 is to consider not only joins of unions of conjunctive queries but all plans built using selections, projections, joins, semi-joins, unions and materialization operators (SPJUM), allowing DAG plans.

Materialization allows to save extra work in case of worth reuse opportunities for intermediate results, while join and union operators can appear in the computed plans at any level, differently from all the previous proposals in literature.

The sweet spot between Saturation-and Reformulation-based query answering. In Chapter 3, we consider the problem of efficient query answering in the presence of RDF Schema constraints. Two main query answering techniques exist, namely saturation and reformulation. In the saturation-based query answring approach the constraints are compiled into the database by making all implicit data explicit, while the reformulationbased query answering technique compiles the constraints into a modified query, which, evaluated over the explicit data only, computes all the answer due to explicit and/or implicit data. In this thesis we focus on optimizing reformulation-based query answering in the setting of ontology-based data access. However, a better study of the performance trade-offs between saturation-, reformulation-and mixed query answering approaches such as [START_REF] Urbani | QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[END_REF], in order to automatically recommend the best technique to use, and/or how to combine them to achieve better performance in a given application setting, could lead to even more efficient systems for query answering in the presence of constraints.

Efficient query answering for DL-Lite R in the presence of mappings. In Chapter 4, we have introduced a novel query optimization framework for ontology-based data access settings enjoying FOL reducibility and applied it to the DL-Lite R . However, OBDA setting also allows declarative specifications, known as mappings, connecting each concept and role in the ontology with a view over the data, materialized in relational databases. For such purpose the W3C introduced R2RML [103], a language expressing customized mappings from relational databases to RDF datasets. Early experiments shown the potential of extending our framework, to support mappings, thus providing efficient query answering for the wider OBDA setting.

Semantic constraints aware query rewriting. Among the RDF data management systems, some support reformulation-based query answering, e.g., Stardog, while others support reformulation-based query answering for a subset of the RDFS rules, e.g., Virtuoso (rdfs:subClassOf and rdfs:subPropertyOf). RDF platforms such as 3store [108], OWLIM [112], Oracle Semantic Graph [111] support saturation-based query answering, based on (a subset of) RDF entailment rules, and others such as Hexastore [START_REF] Weiss | Hexastore: Sextuple indexing for Semantic Web data management[END_REF] or RDF-3X [START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF], ignore entailed triples and only provide query evaluation on top of the RDF graph. Thus, query answering in the presence of semantic constraints requires hybrid store solutions, such as ESTOCADA, to be aware of the semantic capabilities of the underlying systems. In the case of ESTOCADA, this amounts to take into account the ontology, as well as the stores capabilities, while performing the query rewriting. In other words, it requires to encode the ontology into constraints, enabling efficient query answering using materialized conjunctive query views, which may partially or completely rewrite the conjunctive queries appearing in the reformulated fragments.

Storage advisor. In ESTOCADA, once the view-based rewriting part of the project is completed and complemented by a cost model to allow chosing the most efficient rewriting, the next step is to devise the automated storage tuning (storage advisor) which will recommend the views to materialize within each underlying data management system, so as to obtain the best performance for a given query workload.

A.2 Queries used in the Efficient query answering in settings where reformulation is FOL reducible experiments

This section lists the SPARQL queries used in the experimental section of Chapter 4.

We have shortened for presentation purposes some of the strings, e.g., AssociateProfes-sor2@Department1.University0.edu becomes AssocProf2@Dept1.Univ0.edu.

Query q |q UCQ | q 1 (u, i, n, e, t):ub:Professor(x) ∧ ub:degreeFrom(x, u) ∧ ub:researchInterest(x, i)∧ 145 ub:name(x, n) ∧ ub:emailAddress(x, e) ∧ ub:telephone(x, t) q 2 (x, e, t):ub:Professor(x)∧ 145 ub:degreeFrom(x,"http://www.University870.edu")∧ ub:researchInterest(x,"Research21") ∧ ub:name(x,"AssociateProfessor2")∧ ub:emailAddress(x, e) ∧ ub:telephone(x, t) q 3 (x):ub:Professor(x)∧ 145 ub:degreeFrom(x,"http://www.University870.edu")∧ ub:researchInterest(x,"Research21") ∧ ub:name(x,"AssociateProfessor2")∧ ub:emailAddress(x,"AssocProf2@Dept1.Univ0.edu")∧ ub:telephone(x,"xxx-xxx-xxxx")∧ q 4 (x, y):ub:Professor(x) ∧ ub:teacherOf(x, y)∧ 145 ub:degreeFrom(x,"http://www.University870.edu") ∧ ub:researchInterest(x,"Research21")∧ ub:name(x,"AssociateProfessor2")∧ub:telephone(x,"xxxxxx-xxxx")∧ ub:emailAddress(x,"AssocProf2@Dept1.Univ0.edu") q 5 (x, y, z):ub:Professor(x) ∧ ub:teacherOf(x, y)∧ 290 ub:worksFor(x, z)∧ ub:degreeFrom(x,"http://www.University870.edu")∧ ub:researchInterest(x,"Research21") ∧ ub:name(x,"AssociateProfessor2")∧ ub:emailAddress(x,"AssocProf2@Dept1.Univ0.edu")∧ ub:telephone(x,"xxx-xxx-xxxx") q 6 (x, n):ub:Faculty(x) ∧ ub:publicationAuthor(y, x)∧ 35 ub:researchInterest(x,"Research16")∧ ub:name(y, n)∧ ub:emailAddress(x,"AssocProf0@Dept0.Univ0.edu") q 7 (n):ub:Professor(x) ∧ ub:teacherOf(x, c)∧ 116 ub:memberOf(x,"http://www.Dep0.Univ0.edu") ∧ ub:name(x, n)∧ ub:emailAddress(x,"FullProf8@Dept0.Univ0.edu")∧ ub:telephone(x,"xxx-xxx-xxxx") • La fac ¸on souple et naturelle de structurer les documents de manière multidimensionnelle permet de trouver des informations pertinentes à travers des collections de documents très volumineux.

• La sémantique formelle logique des ontologies fournit des moyens d'inférence menant à un raisonnement. Ainsi, une ontologie peut être interprétée et traitée par des machines. c(q ref ) Query q, RDF data and constraints, CQ to UCQ reformulation algorithm q ref State of the art Our approach q 1 c(q 1 ) ≡ q best c(q best ) ≡ q n c(q n ) ≡ . . .

≡

B.3 Répondre efficacement à une Requête réductible FOL

Dans ce chapitre, nous transférons l'idée développée dans le chapitre précédent au paramétrage du modèle de données et des paires de langages de requête bénéficiant de la réductibilité FOL dans le cadre de la réponse aux requête (i.e. le modèle de données et les paires de langages de requête peuvent être réduits à l'évaluation d'une formulation logique de premier ordre, obtenue à partir de la requête et ontologie, contre les faits explicites seulement), englobant de nombreuses bases de connaissances et des paramètres de la base de données, tels que Description Logics, Datalog ± et des fragments Existential Rules.

Nous proposons un cadre d'optimisation des requêtes pour tout paramètre logique OBDA en profitant de la réductibilité FOL de réponse aux requêtes. Nous étendons le langage des reformulations FOL au-delà des reformulations précédemment envisagées et cherchons plusieurs reformulations FOL d'une requête donnée. Celle susceptible de mener au meilleur résultat sera choisie. Ceci contraste avec les travaux existants à partir de la requête sémantique Littérature (voir la section 4.6), qui utilise des langages de reformulation permettant une seule reformulation FOL (minimisation modulo). Considérer un ensemble de reformulations et s'appuyer sur un modèle de coût pour en choisir un plus efficace a un impact très visible sur l'efficacité et la faisabilité des réponses aux requêtes. En effet, choisir la mauvaise reformulation peut provoquer l'échec d'évaluation du RDBMS (généralement en raison de requêtes très longues) ou de mauvaises performances.

Nous appliquons ce cadre général à la DL-Lite R Description Logic [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF] sous-jacent à la célèbre norme W3C OWL2 QL pour les applications Web sémantiques riches ce qui a démontré des avantages significatifs de performance dans ce contexte. Répondre aux requêtes en DL-Lite R a fait l'objet d'une attention significative dans la littérature, notamment sur la réductibilité FOL, par exemple, [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF]2,[START_REF] Pérez-Urbina | Efficient query answering for OWL 2[END_REF][START_REF] Rosati | Improving query answering over DL-Lite ontologies[END_REF][START_REF] Chortaras | Optimized query rewriting for OWL 2 QL[END_REF][START_REF] Venetis | Incremental query rewriting for OWL 2 QL[END_REF]. Du point de vue du traitement des requêtes et de l'optimisation, notre approche peut être considérée comme appartenant à l'étape dite d'optimisation stratégique introduite dans [START_REF] Manegold | A multi-query optimizer for Monet[END_REF] (où l'application sémantique est injectée dans la requête). Cela est similaire dans l'esprit à la réécriture du niveau de syntaxe effectué par des optimiseurs tels que Oracle 10g's [START_REF] Ahmed | Cost-based query transformation in Oracle[END_REF]. Nous partageons avec [START_REF] Manegold | A multi-query optimizer for Monet[END_REF] l'idée d'injecter la sémantique d'abord, et comme [START_REF] Ahmed | Cost-based query transformation in Oracle[END_REF], nous utilisons l'estimation des coûts pour guider nos réécritures. Un thème commun est de réécrire avant de commander des unions, de sélectionner des opérateurs physiques, etc...

B.4 Conclusion

Cette thèse fournit des solutions pour répondre efficacement aux requêtes portant sur des données fondées sur l'ontologie en RDF, la norme W3C de premier plan pour le Web sémantique, et dans la logique de description DL-Lite R qui sous-tend la norme OWL2 QL du W3C pour la gestion des données à la sémantique riche. Résumons les problèmes ci-dessous.

Répondre efficacement aux requêtes en présence de contraintes RDFS. Nous envisageons d'optimiser la réponse aux requêtes fondées sur la formulation dans le cadre de l'OBDA où les requêtes conjonctives SPARQL sont posées contre des faits RDF sur lesquels pèsent des contraintes exprimées par un Schéma RDF.

La littérature fournit des algorithmes de reformulation pour beaucoup de Fragments RDF. Toutefois, les requêtes reformulées peuvent être complexes, mais ne pas être efficacement traitées par un moteur de requête. Même les moteurs de requêtes bien établis échouent parfois dans leur traitement. Abstract : Constraints are the essential artefact for giving meaning to data, ensuring that it fits real-life application needs, and that its meaning is correctly conveyed to the users. This thesis investigates two fundamental problems related to the efficient management of data in the presence of constraints.

We address the problem of efficiently answering queries over data in the presence of deductive constraints, which lead to implicit data that is entailed (derived) from the explicit data and the constraints. Implicit data requires a reasoning step in order to compute complete query answers, and two main query answering techniques exist. Data saturation compiles the constraints into the database by making all implicit data explicit, while query reformulation compiles the constraints into a modified query, which, evaluated over the explicit data only, computes all the answer due to explicit and/or implicit data. So far, reformulation-based query answering has received significantly less attention than saturation. In particular, reformulated queries may be complex, thus their evaluation may be very challenging.

We study optimizing reformulation-based query answering in the setting of ontology-based data access, where SPARQL conjunctive queries are answered against a set of RDF facts on which constraints hold. When RDF Schema is used to express the constraints, the thesis makes the following contributions. (i) We generalize prior query reformulation languages, leading to a space of reformulated queries we call JUCQs (joins of unions of conjunctive queries), instead of a single fixed reformulation.

(ii) We present effective and efficient cost-based algorithms for selecting from this space, a reformulated query with the lowest estimated cost. (iii) We demonstrate through experiments that our technique drastically improves the performance of reformulation-based query answering while always avoiding "worst-case" performance.

Moving beyond RDFS, we consider the large and useful set of ontology languages enjoying FOL reducibility of query answering: answering a query can be reduced to evaluating a certain first-order logic (FOL) formula (obtained from the query and ontology) against only the explicit facts. (iv) We generalize the above-mentioned JUCQ-based optimized reformulation technique to improve performance in any FOL-reducible setting, and (v) we instantiate this framework to the DL-LiteR Description Logic underpinning the W3C's OWL2 QL ontology language, demonstrating significant performance advantages in this setting also.

We also report on current work regarding the problem of providing efficient data access paths in Big Data stores. We consider a setting where a set of different, heterogeneous storage systems can be used side by side to provide better performance than any of them used individually. In such a setting, the data stored in each system can be described as views over the application data. Answering a query thus amounts to rewrite the query using the available views, and then to decode the rewriting into a set of queries to be executed on the systems holding the views, and a query combining them appropriately.

Figure 1 . 1 :

 11 Figure 1.1: The Linked Open Data cloud as of April 2014.

Figure 2 . 1 (

 21 Figure 2.1 (top) shows how to use triples to describe resources, that is, to express class (unary relation) and property (binary relation) assertions. The RDF standard [104] provides a set of built-in classes and properties, as part of the rdf: and rdfs: pre-defined

Figure 2 . 1 (

 21 Figure 2.1 (bottom) shows the allowed constraints and how to express them; domain and range denote respectively the first and second attribute of every property. The RDFS constraints (Figure 2.1) are interpreted under the open-world assumption (OWA) [3].

Figure 3 . 2 :

 32 Figure 3.2: LUBM 1 million triples query answering through UCQ, SCQ, ECov and GCov JUCQ reformulations, against DB2, Postgres and MySQL.

Figure 3 . 3 :

 33 Figure 3.3: LUBM 100 million triples query answering through UCQ, SCQ, ECov and GCov JUCQ reformulations, against DB2, Postgres and MySQL.

Figures 3 .Figure 3 . 4 :

 334 Figures 3.2 and 3.3 shows the evaluation times for LUBM queries on the 1 million triples and 100 million triples datasets respectively, on the three RDBMSs we tested; observe the logarithmic time axis. Missing bars correspond to executions which timed out or were infeasible. Figures 3.2 and 3.3 shows that neither UCQ nor SCQ reformulation are re-

Figure 3 . 5 :

 35 Figure 3.5: Number of query covers explored by the algorithms (top) and algorithm running times (bottom) for the LUBM queries.

Figure 3 . 6 :

 36 Figure 3.6: Number of query covers explored by the algorithms (top) and algorithm running time (bottom) for DBLP queries.

Figure 3 . 7 :

 37 Figure 3.7: Cost model comparison.

3. 3 Figure 3 .

 33 Figure 3.7 shows the evaluation time of the JUCQ reformulations chosen by ECov and GCov, based on one hand on our cost function, and on the other hand on the Postgres one. Most of the time, the results are similar, demonstrating that our cost model is indeed close to the one of Postgres. In a few cases (LUBM Q 12 and Q 16 ), using Postgres' cost model helped avoid bad ECov decisions; however, for the LUBM queries Q 9 , Q 15 , Q 18 , Q 19 , Q 26 and Q 28 , as well as the DBLP queries Q 8 and Q 10 , the ECov JUCQ chosen based on Postgres' cost estimation timed out before completing.

Figure 3 .

 3 Figure 3.7 demonstrates that our cost model (Section 3.2.1) has lead our algorithm to evaluation choices very similar to the ones that Postgres made, validating its accuracy.

Figure 3 . 8 :

 38 Figure 3.8: Query answering through Virtuoso and Postgres (via saturation, respectively, optimized reformulation).

Figure 3 .

 3 8 compares on the LUBM 1 million triples dataset: (i) UCQ reformulation; (ii) saturation-based query answering based on Postgres; (iii) saturation-based query answering based on Virtuoso v6.1.6 (open-source, multithreaded edition); and 3.4. RELATED WORK

Figure 4 . 1 :

 41 Figure 4.1: Optimized FOL reformulation approach.

4. 3 .

 3 COVER-BASED QUERY ANSWERING IN DL-LITE Rthis both on the WITH version and on the view-based versions; we did not notice significant improvements.

51 4. 3 .

 513 COVER-BASED QUERY ANSWERING IN DL-LITE R

Definition 4 . 3 . 1 (

 431 Concept and role dependencies w.r.t. a TBox).

a 1 /b 1 a 4 /b 4 a 3 /b 3 a 2 /b 2 a 5 /b 5 a 6 /b 6 a 7 /b 7 b x a 8 /b 8 a 9 /b 9 a 10 /b 10 f 1 f 2 f 3 Figure 4 . 2 :

 433225566789102342 Figure 4.2: Sample C root cover. Example 15 (Complex root cover).Figure 4.2 depicts a possible C root cover of a 10atoms query; the cover has 3 fragments, each shown in a rectangle. Every a i /b i denotes a query atom a i whose predicate is b i ; a plain arrow from a node to another denotes that the predicate of the first depends on the predicate of the second. The predicate b x appears in the TBox but does not appear in the query. In this example, b 1 , b 2 , b 4 and b 5 depend on b 3 ; b 5 and b 7 depend on b 6 ; b 7 and b 8 on b x etc.. Fragment f 1 corresponds to case 2 of Lemma 1, while fragments f 2 and f 3 correspond to its first case.

Figure 4 .

 4 2 depicts a possible C root cover of a 10atoms query; the cover has 3 fragments, each shown in a rectangle. Every a i /b i denotes a query atom a i whose predicate is b i ; a plain arrow from a node to another denotes that the predicate of the first depends on the predicate of the second. The predicate b x appears in the TBox but does not appear in the query. In this example, b 1 , b 2 , b 4 and b 5 depend on b 3 ; b 5 and b 7 depend on b 6 ; b 7 and b 8 on b x etc.. Fragment f 1 corresponds to case 2 of Lemma 1, while fragments f 2 and f 3 correspond to its first case.

  and a l → . . . → b k+1 . :4. b m-1 is the predicate used in a m-1 or b m-1 ← . . . ← a m-1 , then a m-1 → . . . → b m ; 5. b m is the predicate used in a j or b m ← . . . ← a jObserve that items (2) and (3) can repeat (alternately) until b m-1 is reached.

9 C 10 move ← ∅; 11 /

 91011 t. a is connected to f do 6 if (move is empty and C.enlarge(f, a) est. cost ≤ C est. cost) or (C.enlarge(f, a) est. cost < apply(move) est. cost) then 7 move ← (C, f, {a}); 8 while move = ∅ do ← apply(move); // the cover obtained from that move / Gather move starting from C as was done at lines 2-7 above 12 return C;

64 4. 5

 645 . EXPERIMENTAL EVALUATIONIn the above, duplicates are eliminated because existing reformulation algorithms (and accordingly, our work) operate under set semantics.

Figure 4 .

 4 Figure 4.3 depicts the evaluation time, using Postgres with the simple layout, of four FOL reformulations:

Figure 4 .

 4 3 corresponds to LUBM ∃ 20 100 million triples; note the logarithmic y axis. Overall, the findings are the same: the UCQ and (especially in this4

Figure 4 . 3 :

 43 Figure 4.3: Evaluation time (ms) on Postgres on LUBM ∃ 20 15 million (top) and 100 million (bottom) triples.

Figure 4

 4 Figure 4.4: First caption

Figure 4 . 5 :

 45 Figure 4.5: Evaluation time (ms) on DB2 and LUBM ∃ 20 15 million (top) and 100 million (bottom) triples.

69

 69

  Q05 Q06 Q07 Q08 Q09 Q10 Q11 Q12 Q13 GDL exec 7me without cost es7ma7on (ms) GDL exec 7me with cost model es7ma7on (ms) GDL exec 7me with Postgres cost func7on es7ma7on (ms) GDL exec 7me with DB2 cost func7on es7ma7on

Figure 4 . 6 :

 46 Figure 4.6: GDL running time (ms) on LUBM ∃ 15 million (top) and 100 million (bottom) triples.

Figure 4 . 7 :

 47 Figure 4.7: Query evaluation time of GDL-selected covers, without time limits, and limited to 20 ms for Postgres (top) and DB2 (bottom).

Contributions. 3 : 1 . 3 .

 313 Nous apportons les contributions suivantes au problème de l'optimisation des requêtes FOL (voir Schéma B.3): B.3. R ÉPONDRE EFFICACEMENT À UNE REQU ÊTE R ÉDUCTIBLE FOL Approche de reformulation optimisée des FOL. Pour les formalismes logiques bénéficiant de la réductibilité FOL dans la réponse aux requêtes, nous fournissons un cadre général d'optimisation qui réduit la réponse aux requêtes à la recherche d'autres reformulations équivalentes aux reformulations FOL, l'une d'entre elles avec un coût d'évaluation minimal dans un RDBMS. Dans le schéma B.3, à partir de la requête q et de l'ensemble des contraintes ontologiques T , on déduit d'abord un espace de recouvrements de requêtes, représenté dans le rectangle horizontal blanc, et noté C avec quelques indices. Nous montrons alors comment dériver une requête FOL pouvant être une reformulation FOL de q liée à T . 2.. Nous caractérisons des espaces intéressants pour les requêtes alternatives à la reformulation FOL, soit pour DL-Lite R . Tout d'abord, nous identifions une condition de sécurité suffisante pour choisir des couvertures qui conduisent à une reformulation FOL de la requête. Cette condition est remplie par les couvertures dans le rectangle jaune du haut dans le Schéma B.3, mais n'est pas satisfaite par C ≡ au-dessus. Notre espace de couverture sécuritaire englobe toutes les reformulations FOL, y compris celles déjà étudiées dans la littérature. Ensuite, nous introduisons un ensemble de couvertures généralisées (rectangle jaune en bas dans le SchémaB.3) et une technique généralisée de reformulation donnant toujours une reformulation aux requêtes FOL. Cela est souvent plus efficace que les couvertures simples. Notre approche peut être combinée et permet d'optimiser toute reformulation technique existante pour DL-Lite R . Nous optimisons alors la réponse aux requêtes dans le cadre de DL-Lite R en énumérant des couvertures simples et généralisées, et en choisissant une couverture dérivée de la reformulation FOL au plus bas coût estimé d'évaluation en relation à une estimation du modèle de coût RDBMS (désigné par les flèches bidirectionnelles dans le Schéma). B.4. CONCLUSION Nous fournissons deux algorithmes, un exhaustif et un gourmand, pour cette tâche. 4. L'évaluation de nos reformulations FOL à travers le RDBMS (flèches épaisses à droite du Schéma B.3) conduit à une réponse reflétant les données et les contraintes. Nous démontrons expérimentalement l'efficacité et l'efficience de notre technique de réponse aux requêtes pour DL-Lite R en déployant notre technique de réponse aux requêtes audessus de Postgres et DB2, et en utilisant des configurations alternatives de données.

  Au-delà de RDFS, nous nous intéressons aux langages d'ontologie pour lesquels répondre à une requête peut se réduire à l'évaluation d'une certaine formule de la Logique du Premier Ordre (obtenue à partir de la requête et de l'ontologie), sur les faits explicites uniquement. (iv) Nous généralisons la technique de reformulation optimisée pour RDF, mentionnée ci-dessus, aux formalismes pour répondre à une requête LPO-réductible. (v) Nous appliquons cette technique à la Logique de Description DL-LiteR sous-jacente au langage OWL2 QL du W3C, et montrons expérimentalement ses avantages dans ce contexte.Nous présentons également, brièvement, un travail en cours sur le problème consistant à fournir des chemins d'accès efficaces aux données dans les systèmes Big Data. Nous proposons d'utiliser un ensemble de systèmes de stockages hétérogènes afin de fournir une meilleure performance que n'importe lequel d'entre eux, utilisé individuellement. Les données stockées dans chaque système peuvent être décrites comme des vues matérialisées sur les données applicatives. Répondre à une requête revient alors à réécrire la requête à l'aide des vues disponibles, puis à décoder la réécriture produite comme un ensemble de requêtes à exécuter sur les systèmes stockant les vues, ainsi qu'une requête les combinant de façon appropriée. Title : Efficient Big Data query answering in the presence of constraints Keywords : Semantic Web, Query optimization, Query answering under constraints, Query reformulation, Hybrid stores

  7

  RDF s p o, if and only if there is a sequence of applications of immediate entailment rules that leads from G to s p o (where at each step of the entailment sequence, the triples previously entailed are also taken into account).

	2.1. RDF 2.1. RDF
	"1949" Publication	Book rdfs:domain	hasAuthor
		publishedIn rdfs:subClassOf rdf:type	rdfs:subPropertyOf
	"1949"	rdf:type	doi 1 Book	writtenBy rdfs:domain	:b 1 writtenBy
	publishedIn	hasTitle rdf:type	hasName rdfs:range
		doi 1	"El Aleph" writtenBy hasAuthor	:b 1	"J. L. Borges" Person rdf:type
	"El Aleph" hasTitle	"J. L. Borges" Figure 2.2: Sample RDF graph. hasName
	Figure 2.3: Sample RDF graph with RDFS constraints.
	Example 2 (RDFS). Assume that the RDF graph G in Example 1 is extended with the
	following constraints.
	• books are publications:
	Book rdfs:subClassOf Publication
	• writing something means being an author:
	writtenBy rdfs:subPropertyOf hasAuthor
	• books are written by people:
	writtenBy rdfs:domain Book
	writtenBy rdfs:range Person
	The resulting graph is depicted in Figure 2.3. Constraints are represented by blue edges
	while its implicit triples are those depicted by gray dashed-line edges.

More specifically, when working with the RDF data model, if the triples hasFriend rdfs:domain Person and Anne hasFriend Marie hold in the graph, then so does the triple Anne rdf:type Person. The latter is due to the rdfs:domain constraint in Figure

2

.1.

RDF entailment. Implicit triples are an important RDF feature, considered part of the RDF graph even though they are not explicitly present in it, e.g., Anne rdf:type Person above. W3C names RDF entailment the mechanism through which, based on a set of explicit triples and some entailment rules, implicit RDF triples are derived. We denote by i RDF immediate entailment, i.e., the process of deriving new triples through a single application of an entailment rule. More generally, a triple s p o is entailed by a graph G, denoted G Saturation. The immediate entailment rules allow defining the finite saturation (a.k.a. closure) of an RDF graph G, which is the RDF graph G ∞ defined as the fixed-point obtained by repeatedly applying i RDF rules on G.

Table 2 .

 2

	Constraints	Data
		Answer
	Query	Query'
	Figure 2.5: Reformulation-based query answering overview.

1: Datasets and saturation characteristics

[START_REF] Franc ¸ois Goasdoué | Efficient query answering against dynamic RDF databases[END_REF]

. eral, reformulated queries are complex, hence inefficiently handled by modern query processing engines.

Table 2 .

 2 3: DL-Lite R inclusion constraints without negation in FOL, and in relational notation; A, A are concept names while R, R are role names. For the relational notation, we use 1 to designate the first attribute of any atomic role, and 2 for the second.

	DL constraint	FOL constraint	Relational	constraint
			(under Open World
			Assumption)

Table 2

 2

	.4: DL-Lite R inclusion constraints with negation, i.e., disjointness constraints, in
	FOL and relational notation. ⊥ denotes the empty relation.

Table 2

 2 CQs with the same arity, where the atom is either of the form A(t) or of the form R(t, t ) as above; the bound variables of SCQs are also existentially quantified. Unions of CQs (UCQs) are disjunctions of CQs with same arity. Unions of SCQs (USCQs), Joins of UCQs (JUCQs), and finally Joins of USCQs (JUSCQs) are built on top of simpler languages by adding unions, respectively joins. All the above dialects directly translate into SQL, and thus can be evaluated by an RDBMS.

	.5. Conjunctive Queries (CQs), a.k.a. select-project-
	join queries, are conjunctions of atoms, where an atom is either A(t) or R(t, t ), for
	some t, t variables or constants. Semi-Conjunctive Queries (SCQs) are joins of unions
	of single-atom

Table 2 .

 2 6: Union terms in CQ-to-UCQ reformulation (Example 8).

Table 3 .

 3 1: Characteristics of the sample query q 1 .

	3.1. MOTIVATION
	Triple	#answers #reformulations #answers after
				reformulation
	(t 1 ) 18, 999, 082	188	33, 328, 108
	(t 2 )	0	4	3, 223
	(t 3 )	396	3	683

Table 3 .

 3 1 ) ref (t 2 ) ref (t 3 ) ref ,which joins the CQ to UCQ reformulation of each query's triple. In other terms, q 1 first 2: Sample reformulations of q 1 .

	3.1. MOTIVATION
		Joins of UCQs	#reformulations exec.time (ms)
	q 1	(t 1 , t 2 , t 3 ) ref	2, 256	6, 387
	q 1 (t 1 ) ref 1 (t 2 ) ref 1 (t 3 ) ref	195	1, 074, 026
		(t 1 , t 2 ) ref 1 (t 3 ) ref	755	1, 968
		(t 1 ) ref 1 (t 2 , t 3 ) ref	200	846, 710
	q 1	(t 1 , t 3 ) ref 1 (t 2 ) ref	568	554
		(t 1 , t 2 ) ref 1 (t 1 , t 3 ) ref	1, 316	2, 734
		(t 1 , t 2 ) ref 1 (t 2 , t 3 ) ref	764	2, 289
		(t 1 , t 3 ) ref 1 (t 2 , t 3 ) ref	576	588

Table 3 .

 3 3: Characteristics of the sample query q 2 .

	Triple	#answers #reformulations #answers after
				reformulation
	(t 1 ) 18, 999, 082	188	33, 328, 108
	(t 2 ) 18, 999, 082	188	33, 328, 108
	(t 3 )	476	1	476
	(t 4 )	509	1	509
	(t 5 )	7, 299, 701	3	7, 803, 096
	(t 6 )	7, 299, 701	3	7, 803, 096

Table 3 .

 3 4: Characteristics of the queries used in our study.

	3.3.1 Settings

Software. We implemented our reformulation-based query answering framework in Java 7, on top of three well-known RDBMSs, namely: PostgreSQL v9.3.2, IBM DB2 Express-C v10.5, and MySQL Community Server v5.6.20. For each RDBMS, we instantiated the cost formulas introduced in Section 3.2.1 with the proper coefficients, learned by running our calibration queries on that system.

  14 (Root cover). On the query and TBox from Example 11, the root cover is C 2 from Example 13; worksWith(x, y) and supervisedBy(z, y) are in the same C 2 fragment because worksWith depends on supervisedBy (cf. Example 12).

  . the atoms of all the fragments in each set s i , for 1 ≤ i ≤ |P |, are connected do

4

C P ← ∅; 5 foreach fragment set

Table 4 .

 4 2: Search space sizes for queries A 3 to A 6 .

	4.5. EXPERIMENTAL EVALUATION
	Query	A 3 A 4	A 5	A 6
	|L q |	2	7	71	93
	|G q |	4 67 5674 > 20000
	L q covers explored by	2	5	11	18
	GDL
	G q covers explored by	4 12	27	59
	GDL

  1 , D 1 /F 2 , . . ., D 1 /F n , D 2 /F 1 , . . . etc., and where they are stored in the underlying DMSs, illustrated by a NoSQL store, a key-value store, a document store, one for nested relations, and finally a relational one. For each data fragment D i /F j residing in the store S Execution Engine then translates such rewritings into excutable ones as described above and evaluates them.

k , a storage descriptor sd(S k , D i /F j ) is produced. The descriptor specifies what data (the fragment D i /F j ) is stored where within S k . The what part of the descriptor is specified by a query over the data set D i , following the native model of D i . The fragment can 5.2. ONGOING WORK: TOWARDS SCALABLE HYBRID STORES

Table A .

 A Dans le cadre de la troisième génération Web, le Web 3.0 est également appelé Web sémantique. Contrairement aux systèmes traditionnels de représentation des connaissances généralement centralisés[START_REF] Berners-Lee | The semantic web: A new form of web content that is meaningful to computers will unleash a revolution of new possibilities[END_REF], le Web sémantique est conc ¸u pour être une architecture distribuée mondialement. C'est une avancée supplémentaire dans la direction du rêve de Tim Berners-Lee en 2000[START_REF] Berners | Weaving the web -the original design and ultimate destiny of the World Wide Web by its inventor[END_REF]: le moment où les ordinateurs deviennent capables d'analyser toutes les données du Web. Le Web sémantique est une extension du World Wide Web dans lequel le contenu a une structure permettant aux ordinateurs de traiter avec fiabilité la sémantique et donc de manipuler les données de manière sensée. Toutefois, afin qu'une telle vision se réalise, un ensemble de modèles de données et de formats pour spécifier les descriptions sémantiques des ressources Web est nécessaire.

	B.1. INTRODUCTION
	et l'émergence du cloud computing. Ces événements ne sont pas passés inaperc ¸us dans
	le domaine de l'apprentissage automatique ni dans ceux de la gestions de données et
	de systèmes distribués, qui avaient fourni les systèmes et les solutions nécessaires (par
	exemple, Hadoop, Spark, Flink, Kafka, etc...) pour soutenir cette nouvelle génération
	d'applications Big Data.
	B.1.2 Semantic Web
	5: LUBM ∃ 20 queries Q1-Q7.

Dans cette optique, le World Wide Web Consortium (W3C) a présenté le Resource Description Framework (RDF) servant de base au Web sémantique. Le RDF est un modèle de données flexible, permettant d'exprimer des déclarations portant sur des ressources (uniquement identifiées par leur URI) sous la forme d'expressions sujet-prédicat-objet. Pour améliorer la puissance descriptive des ensembles de données RDF, le W3C a proposé le schéma RDF (RDFS) [105] et le Web Ontology Language (OWL) [102], facilitant la représentation de contraintes sémantiques (i.e. contraintes ontologiques) entre les classes et les propriétés utilisées. L'ensemble des faits ainsi que les règles logiques sur l'appartenance d'individus en classes ou en relations formées entre eux, constituent une base de connaissances. Finalement, la popularité actuelle et l'utilisation d'ontologies dans le Web est due à quatre raisons majeures [4]:

•

  Les ontologies permettent de préciser les concepts et d'améliorer la recherche sur le Web. Par exemple, lors de la recherche du mot "aleph", nous pourrions spécialiser le concept dans l'ontologie livre: aleph, ce qui aboutirait aux livres écrits par JL Borges, P. Coelho, etc..., et éviter les réponses indésirables où le terme est utilisé avec une autre connotation (comme ceux se rapportant à la lettre B.1. INTRODUCTION portant le même nom ou à la séquence des nombres utilisés pour représenter la cardinalité des ensembles infinis qui peuvent être bien ordonnés).Par exemple, si le célèbre écrivain argentin J.L. Borges apparaît dans un document, alors il a un URI associé, auquel toutes les autres ressources (livres, articles, Prix, etc...) se réfèrent. La version RDF de la British National Bibliography développée par British Library 3 exprime des informations pertinentes sur les livres, auteurs, éditeurs, etc..., et contiendra les livres écrits par Borges, les éditeurs de ces livres, leur lieu de publication et année. En parallèle, GeoNames 4 fournit des informations sur les lieux de publication, et DBPedia 5 (la contrepartie sémantique de Wikipédia 6 ) donnera davantage d'informations sur Borges, comme son opinion politique, sa famille, etc...Tous les ensembles de données interconnectés susmentionnés font partie de Linked Open Data 7 .B.2. R ÉPONDRE EFFICACEMENT AUX REQU ÊTES EN PR ÉSENCE DE CONTRAINTESble de données en RDF, alors que le diamètre du noeud reflète la taille de l'ensemble des données. En outre, il y a un espace commun entre deux noeuds si les deux ensembles de données ont des URI en commun. Les ensembles de données sont alors interconnectés. Comme indiqué dans[START_REF] Schmachtenberg | Adoption of the linked data best practices in different topical domains[END_REF], la taille du Web sémantique est en pleine croissance, doublant de taille presque chaque année.Pour exploiter cette richesse de données, le langage de requête SPARQL a été défini[106]. Par la suite, de nouvelles techniques et algorithmes ont été proposés pour le traitement des requêtes SPARQL, fondés sur le partitionnement vertical[START_REF] Daniel | Scalable semantic web data management using vertical partitioning[END_REF], l'indexation[START_REF] Weiss | Hexastore: Sextuple indexing for Semantic Web data management[END_REF], le traitement de jointure efficace[START_REF] Neumann | Scalable join processing on very large RDF graphs[END_REF], la technique de view-selection[START_REF] Franc ¸ois Goasdoué | View selection in semantic web databases[END_REF], les systèmes de gestion RDF[108, 110, 113,[START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF], pour n'en citer que quelques-uns.B.2 Répondre efficacement aux requêtes en présence de contraintesRépondre à des requêtes portant sur des données en présence de contraintes déductives, ce qui mène à des données implicites dérivant de données explicites et de contraintes, implique une étape de raisonnement afin de calculer les réponses aux requêtes. Deux techniques de réponse existent : la saturation des données compile les contraintes dans la base de données en rendant explicites toutes les données implicites, tandis que la reformulation de requêtes compile les contraintes dans une requête modifiée, qui, évaluée uniquement sur les données explicites, calcule toutes les réponses que les données soient explicites ou implicites. Jusqu'à présent, répondre aux requêtes fondées sur la reformulation a rec ¸u beaucoup moins d'attention que la saturation. En particulier, les requêtes reformulées peuvent être complexes et leur évaluation peut donc être très difficile.Dans ce chapitre, nous nous concentrons sur l'optimisation de la réponse aux requêtes fondées sur la reformulation dans le paramétrage des accès aux données fondées sur l'ontologie, lorsqu'il est répondu aux requêtes conjonctives SPARQL via un ensemble de données RDF sur lesquelles les contraintes RDFS ont un impact.Nous considérons le contexte dans lequel les requêtes conjonctives (CQ), une fois reformulées en unions de requêtes conjonctives (UCQ) ou semi-conjonctives (SCQ), sont traitées pour évaluation d'une requête par un RDBMS, un dépôt de données RDF dédié et un module de traitement des requêtes, ou plus généralement par tout système capable d'évaluer les sélections, projections, jointures et unions. Comme le montrent nos expériences, l'évaluation de requêtes reformulées peut être très difficile, même pour des processeurs RDF relationnels ou natifs, qui peuvent les gérer de manière inefficace ou échouer à les gérer, même sur des ensembles de données de taille modérée.

	B.2. R ÉPONDRE EFFICACEMENT AUX REQU ÊTES EN PR ÉSENCE DE
	CONTRAINTES
	q ref
	• Les ontologies servent de lien local entre des sources d'information hétérogènes.
	De plus, leur potentiel d'inférence permet d'intégrer automatiquement différentes
	sources de données.
	100

L'approche sélectionnée est la suivante: étant donné une requête conjonctive SPARQL q et un algorithme de reformulation de requête A qui transforme un CQ en UCQ, nous explorons un grand espace de reformulations alternatives de q que nous appelons JUCQ (pour des unions jointes de requêtes conjonctives), qui reprennent les reformulations UCQ

  Schéma B.2: Notre approche d'évaluation efficace des requêtes conjonctives SPARQL reformulées. et SCQ, et dont nous choisissons une reformulation JUCQ avec le coût estimé le plus bas. Chaque reformulation JUCQ est obtenue à partir d'un ensemble soigneusement choisi d'invocations de l'algorithme A guidé par notre modèle de coût. Contributions. Les contributions que nous apportons au problème de répondre de manière efficace aux requêtes SPARQL, via la reformulation, peuvent être décrites comme suit (voir Schéma B.2): 1. Nous généralisons l'approche de reformulation des requêtes, en considérant un espace étendu des reformulations alternatives (équivalentes) JUCQ. Cet espace correspond au carré jaune du Schéma B.2. Elle inclut et généralise de fac ¸on significative les travaux antérieurs fondés sur la reformulation UCQ ou SCQ. Nous caractérisons la taille de notre espace d'alternatives, et montrons qu'il est souvent trop grand pour être complètement exploré. 2. Nous définissons un modèle de coût pour estimer la performance d'évaluation de nos requêtes reformulées par un moteur relationnel. D'autres fonctions peuvent être utilisées à la place, et nous montrons qu'un modèle de coût interne RDBMS peut être facilement utilisé. 3. Nous concevons un nouvel algorithme qui sélectionne une requête reformulée alternative, appelée q best dans le Schéma B.2, qui (i) calcule le même résultat que la requête reformulée q ref UCQ ou SCQ, et (ii) réduit significativement le coût d'évaluation de la requête (ou simplement le rend possible lorsque l'évaluation q ref échoue!) 4. Nous avons mis en oeuvre cet algorithme et l'avons déployé en plus de trois RDBMS qui diffèrent significativement dans leur capacité à gérer les reformulations UCQ et SCQ. Nos expériences confirment que notre algorithme est celui permettant de tirer le maximum de chacun de ces modules, en tirant parti de leurs forces et en évitant leurs faiblesses via l'utilisation de notre modèle de coût, que nous calibrons séparément pour chaque système. Cela rend la reformulation pos-B.3. R ÉPONDRE EFFICACEMENT À UNE REQU ÊTE R ÉDUCTIBLE FOL sible lorsque UCQ et/ou SCQ échouent, et apporte des améliorations de performance de plusieurs ordres de grandeur en relation avec UCQ. 5. Enfin, nous avons mis en perspective notre technique efficace de réponse aux requêtes fondées sur la reformulation en la comparant à la réponse aux requêtes fondées sur la saturation en se fondant sur PostgreSQL et via la plate-forme Virtuoso dédiée à la gestion de données Web sémantique. Ces expériences confirment la robustesse et la performance de notre technique, montrant en particulier que dans certains cas sa performance approche celle de la réponse aux requêtes fondées sur la saturation.

		Query evaluation engine
	. . . ≡	Query optimizer (σ, π, , ∪) engine Execution
	q best
	Results

  De ce point de vue, notre contribution peut être considérée comme un ensemble d'alternatives (réécritures) avec des garanties d'exactitude et des algorithmes guidant ces réécritures pour une classe spéciale de requêtes obtenues à partir de reformulations FOL de CQ contre des ontologies.

  1. Nous généralisons l'approche de reformulation de requêtes en considérant un grand espace de reformulations alternatives (équivalentes). Nous caractérisons la taille de notre espace d'alternatives et montrons qu'il est souvent trop grand pour être complètement exploré. 104 B.4. CONCLUSION 2. Nous définissons un modèle de coût pour estimer la performance d'évaluation de nos requêtes reformulées via un moteur de recherche relationnel. D'autres fonctions peuvent être utilisées à la place et nous montrons qu'un modèle de coût interne RDBMS peut également être facilement utilisé. 3. Nous concevons un nouvel algorithme qui sélectionne une autre requête alternative reformulée qui (i) calcule le même résultat que la requête reformulée, q ref , produit par des algorithmes de reformulation, et (ii) réduit de fac ¸on significative le coût d'évaluation de la requête (ou tout simplement le rend possible lorsque l'évaluation q ref échoue!) 4. Nous avons implémenté cet algorithme et l'avons déployé en sus de trois SGBDR déjà bien établis. Nos expériences montrent que notre technique permet de répondre à des requêtes fondées sur la reformulation lorsque des approches classiques sont irréalisables, tout en diminuant le coût dans certains cas. 5. Enfin, nous comparons notre technique de réponse aux requêtes fondées sur la reformulation avec les réponses aux requêtes fondées sur la saturation via un RDBMS et la plateforme RDF Virtuoso. Ces expériences confirment la robustesse et la performance de notre technique, montrant en particulier que dans certains cas sa performance approche celle de la réponse aux requêtes fondées sur la saturation. Répondre efficacement aux requêtes FOL réductibles. Nous considérons les langages d'ontologie jouissant de réductibilité FOL dans la réponse à une requête: répondre à une requête peut être réduit à évaluer une certaine formule logique de premier ordre (FOL) (obtenue à partir de la requête et de l'ontologie) et des faits explicites. Nous étendons le langage des reformulations FOL au-delà de celles considérées jusqu'à présent dans la littérature, et étudions plusieurs reformulations FOL (équivalentes) d'une requête donnée dont nous choisissons celle susceptible de conduire à la meilleure performance. Cela contraste avec les travaux existants de la littérature sur la réponse aux requêtes sémantiques qui utilisent des langages de reformulation permettant une reformulation FOL unique (module minimisation). En considérant un ensemble de reformulations et en s'appuyant sur un modèle de coût pour choisir la plus efficace a un impact très visible sur l'efficacité et la faisabilité de la réponse à une requête. En effet, choisir la reformulation erronée peut mener le RDBMS à échouer à l'évaluer (généralement en raison de requêtes très longues), ou conduire à une mauvaise performance. 1. Pour les formalismes logiques bénéficiant de la réductibilité FOL dans la réponse aux requêtes, nous fournissons un cadre d'optimisation général qui réduit la réponse aux requêtes à la recherche parmi un ensemble de reformulations FOL équivalentes, l'une avec une évaluation minimale dans un RDBMS. Répondre efficacement aux requêtes Big Data en présence de contraintes Mots clés : Web sémantique, Optimisation des requêtes, Répondre à des requêtes en présence de contraintes, Reformulation des requêtes, Polystores Résumé : Les contraintes sont les artéfacts fondamentaux permettant de donner un sens aux données. Elles garantissent que les données sont conformes aux besoins des applications. L'objet de cette thèse est d'étudier deux problématiques liées à la gestion efficace des données en présence de contraintes. Nous abordons le problème de répondre efficacement à des requêtes portant sur des données, en présence de contraintes déductives. Cela mène à des données implicites dérivant de données explicites et de contraintes. Les données implicites requièrent une étape de raisonnement afin de calculer les réponses aux requêtes. Le raisonnement par reformulation des requêtes compile les contraintes dans une requête modifiée qui, évaluée à partir des données explicites uniquement, génère toutes les réponses fondées sur les données explicites et implicites. Comme les requêtes reformulées peuvent être complexes, leur évaluation est souvent difficile et coûteuse. Nous étudions l'optimisation de la technique de réponse aux requêtes par reformulation dans le cadre de l'accès aux données à travers une ontologie, où des requêtes conjonctives SPARQL sont posées sur un ensemble de faits RDF sur lesquels des contraintes RDF Schema (RDFS) sont exprimées. La thèse apporte les contributions suivantes. (i) Nous généralisons les langages de reformulation de requêtes précédemment étudieés, afin d'obtenir un espace de reformulations d'une requête posée plutôt qu'une unique reformulation. (ii) Nous présentons des algorithmes effectifs et efficaces, fondés sur un modèle de coût, permettant de sélectionner une requête reformulée ayant le plus faible coût d'évaluation. (iii) Nous montrons expérimentalement que notre technique améliore significativement la performance de la technique de réponse aux requêtes par reformulation.

Titre :

https://newsroom.fb.com/company-info/

https://www-01.ibm.com/software/data/bigdata/what-is-big-data.html

http://www.bl.uk/bibliographic/datafree.html

www.geonames.org/

http://wiki.dbpedia.org/

https://en.wikipedia.org/wiki/Main_Page

http://lod-cloud.net/

Concretely, a stack depth limit exceeded error was thrown by the DBMS. Further, other queries presented I/O exceptions thrown by the DBMS, in connection with a failed attempt to materialize an intermediary result. While it may be possible to tune some parameters to make the evaluation of such queries possible, the same error was raised by many large-reformulation queries, a signal that their peculiar shape is problematic.

A query triple is redundant when it can be inferred from the others based on the RDFS constraints. For instance, when looking for x such that x is a person and x has a social security number, if we know that only people have such numbers, the triple "x is a person" is redundant.

Doing this for every examined cover slowed down our search significantly, thus we do not recommend actually running GCov out of a RDBMS based on the RDBMS's internal cost model.

As stated at http://franz.com/agraph/support/ documentation/v4/reasoner-tutorial.html#fnr0-2014-09-16

We checked this on Postgres, DB2, and MySQL plans; according to Paul Larson (among the authors of[START_REF] Zhou | Efficient exploitation of similar subexpressions for query processing[END_REF]), no major RDBMS engine as of April

has a comprehensive MQO approach.

These SQL subqueries are of the form SELECTDISTINCT in order to reduce the size of the intermediate materialized results; this choice lead to the fastest execution in our experiments.

In this case, the mgu is supervisedBy(x, y) because x is the head variable. Also, q 3 is equivalent to (and a minimal form of) q 2 , but in general, q 3 is only guaranteed to be contained in (or equivalent to) q 2 .

See https://oeis.org/A000110.

See http://www.postgresql.org/docs/9.1/static/sql-explain.html.

See http://www-01.ibm.com/support/knowledgecenter/SSEPGG 10.5.0/ com.ibm.db2.luw.admin.cmd.doc/doc/r0005736.html.

Alludes to the so-called Chinese curse "may you live in interesting times" (see e.g., https://en.wikipedia.org/wiki/May you live in interesting times).

Acknowledgements

I am deeply grateful to all those who helped and supported me during these years, leading to the completion of this thesis.

thus be seen as a materialized view over D i . The where part of the descriptor is structured according to the organization of data within S k . For instance, if S k is a relational store, the where information consists of the schema and table name, whereas if S k is a key-value store, it could hold the name of the collection, attribute name, etc. Finally, the descriptor sd(S k , D i /F j ) also specifies the data access operation supported by S k which allows retrieving the D i /F j data (such as: a table scan, a look-up based on a collection name, column group name, and column name in a key-value store, etc.), as well as the access credentials required in order to connect to the system and access it.

The Storage Advisor recommends dropping redundant fragments that are rarely used or under-performing, and adding new fragments that fit recently heavy-hitting queries. To solve this problem across data models, we once again exploit our pivot model to reduce to the novel setting of relational view selection under constraints.

The Query Evaluator receives application queries. If a query carries over a single source D i , the query will likely be in the native language of D i . If the query carries over multiple sources having different data models, this assumes the existence of a global-as-view integration layer on top of the (application-transparent) local-as-view approach internally followed by ESTOCADA. While we do not focus on this (optional) global-as-view integration layer, in such a case we assume the query is specified by combining algebraic operations (such as filter, join, union, etc.) on top of individual queries carrying over each dataset. It is rather straightforward then to translate such a query in the pivot model, by focusing first on the queries confined to a data source, and then on the combination operators. The evaluator looks up the storage descriptors corresponding to fragments of the queried datasets, calls the PACB engine to obtain rewritings. The Runtime Appendix A

Detailed queries

A.1 Queries used in the efficient query answering in the presence of RDFS constraints experiments

This section lists the SPARQL queries used in the experimental section of Chapter 3. For readability and without loss of information, the URIs starting with "http://www.lehigh.edu" were slightly shortened by eliminating a few /-separated steps.

Q01(?X ?Y ) :-?X "http://www.w3.org/1999/02/22-rdf-syntax-ns#type" "http://www.lehigh.edu/univ-bench.owl#Employee", ?X "http://www.lehigh.edu/univ-bench.owl#worksFor" "http://www.Department0.University0.edu", ?X "http://www.lehigh.edu/univ-bench.owl#degreeFrom" ?Y Q02(?X ?Y ?U ?V ?W ) :-?X "http://www.w3.org/1999/02/22-rdf-syntax-ns#type" "http://www.lehigh.edu/univ-bench.owl#Employee", ?X "http://www.lehigh.edu/univ-bench.owl#worksFor" "http://www.Department0.University0.edu", ?X "http://www.lehigh.edu/univ-bench.owl#degreeFrom" ?Y, ?X "http://www.lehigh.edu/univ-bench.owl#name" ?U, ?X "http://www.lehigh.edu/univ-bench.owl#emailAddress" ?V, ?X "http://www.lehigh.edu/univ-bench.owl#telephone" ?W Q03(?X ?Y ) :-?X "http://www.w3.org/1999/02/22-rdf-syntax-ns#type" "http://www.lehigh.edu/univ-bench.owl#Employee", ?X "http://www.lehigh.edu/univ-bench.owl#worksFor" "http://www.Department0.University0.edu", ?X "http://www.lehigh.edu/univ-bench.owl#doctoralDegreeFrom" ?Y Q04(?X ?Y ?Z ) :-?X "http://www.w3.org/1999/02/22-rdf-syntax-ns#type" ?Y, ?X "http://www.lehigh.edu/univ-bench.owl#doctoralDegreeFrom" ?U, ?X "http://www.lehigh.edu/univ-bench.owl#memberOf" ?Z Q05(?X ?Y ?Z ) :-?X "http://www.w3.org/1999/02/22-rdf-syntax-ns#type" "http://www.lehigh.edu/univ-bench.owl#Student", ?X "http://www.lehigh.edu/univ-bench.owl#advisor" ?Y, ?Y "http://www.lehigh.edu/univ-bench.owl#teacherOf" ?Z, ?X "http://www.lehigh.edu/univ-bench.owl#takesCourse" ?Z Q06(?X ?W ?Y ?Z ) :-?X "http://www.w3.org/1999/02/22-rdf-syntax-ns#type" ?W, ?X "http://www.lehigh.edu/univ-bench.owl#advisor" ?Y, ?Y "http://www.lehigh.edu/univ-bench.owl#teacherOf" ?Z, ?X "http://www.lehigh.edu/univ-bench.owl#takesCourse" ?Z