RDF concrete syntax (Turtle)

JSON-LD and RDFa

JSON-LD and RDFa are further two new different syntaxes that the previously introduced in this chapter, and we only mention the purpose of these two syntaxes here.

JSON-LD is a JSON syntax for encoding RDF graphs. This also allows to change JSON document into RDF document with minimal changes.

RDFa is used to embed RDF data within HTML and XML documents. They can serve as metadata for search engines while crawling the web.

Abstract:

Data structured in the Resource Description Framework (RDF) are increasingly available in large volumes. This leads to a major need and research interest in novel methods for query analysis and compilation for making the most of RDF data extraction. SPARQL is the widely used and well supported standard query language for RDF data. In parallel to query language evolutions, schema languages for expressing constraints on RDF datasets also evolve. Shape Expressions (ShEx) are increasingly used to validate RDF data, and to communicate expected graph patterns. Schemas in general are important for static analysis tasks such as query optimisation and containment. Our purpose is to investigate the means and methodologies for SPARQL query static analysis and optimisation in the presence of ShEx schema constraints.

Our contribution is mainly divided into two parts. In the first part we consider the problem of SPARQL query containment in the presence of ShEx constraints. We propose a sound and complete procedure for the problem of containment with ShEx, considering several SPARQL fragments. Particularly our procedure considers OPTIONAL query patterns, that turns out to be an important feature to be studied with schemas. We provide complexity bounds for the containment problem with respect to the language fragments considered. We also propose alternative method for SPARQL query containment with ShEx by reduction into First Order Logic satisfiability, which allows for considering SPARQL fragment extension in comparison to the first method. This is the first work addressing SPARQL query containment in the presence of ShEx constraints.

In the second part of our contribution we propose an analysis method to optimise the evaluation of conjunctive SPARQL queries, on RDF graphs, by taking advantage of ShEx constraints. The optimisation is based on computing and assigning ranks to query triple patterns, dictating their order of execution. The presence of intermediate joins between the query triple patterns is the reason why ordering is important in increasing efficiency. We define a set of well-formed ShEx schemas, that possess interesting characteristics for SPARQL query optimisation. We then develop our optimisation method by exploiting information extracted from a ShEx schema. We finally report on evaluation results performed showing the advantages of applying our optimisation on the top of an existing state-of-the-art query evaluation system.

Résumé:

La disponibilité de gros volumes de données structurées selon le modèle Resource Description Framework (RDF) est en constante augmentation. Cette situation implique un intérêt scientifique et un besoin important de rechercher de nouvelles méthodes d'analyse et de compilation de requêtes pour tirer le meilleur parti de l'extraction de données RDF. SPARQL est le plus utilisé et le mieux supporté des langages de requêtes sur des données RDF. En parallèle des langages de requêtes, les langages de définition de schéma d'expression de contraintes sur des jeux de données RDF ont également évolués. Les Shape Expressions (ShEx) sont de plus en plus utilisées pour valider des données RDF et pour indiquer les motifs de graphes attendus. Les schémas sont importants pour les tâches d'analyse statique telles que l'optimisation ou l'injection de requêtes. Notre intention est d'examiner les moyens et méthodologies d'analyse statique et d'optimisation de requêtes associés à des contraintes de schéma.

Notre contribution se divise en deux grandes parties. Dans la première, nous considérons le problème de l'injection de requêtes SPARQL en présence de contraintes ShEx. Nous proposons une procédure rigoureuse et complète pour le problème de l'injection de requêtes avec ShEx, en prenant en charge plusieurs fragments de SPARQL. Plus particulièrement, notre procédure gère les patterns de requêtes OPTIONAL, qui s'avèrent former un important fonctionnalité à étudier avec les schémas. Nous fournissons ensuite les limites de complexité de notre problème en considération des fragments gérés. Nous proposons également une méthode alternative pour l'injection de requêtes SPARQL avec ShEx. Celle-ci réduit le problème à une satisfiabilité de Logique de Premier Ordre, qui permet de considérer une extension du fragment SPARQL traité par la première méthode. Il s'agit de la première étude traitant l'injection de requêtes SPARQL en présence de contraintes ShEx.

Dans la seconde partie de nos contributions, nous proposons une méthode d'analyse pour optimiser l'évaluation de requêtes SPARQL groupées, sur des graphes RDF, en tirant avantage des contraintes ShEx. Notre optimisation s'appuie sur le calcul et l'assignation de rangs aux triple patterns d'une requête, permettant de déterminer leur ordre d'exécution. La présence de jointures intermédiaires entre ces patterns est la raison pour laquelle l'ordonnancement est important pour gagner en efficicacité. Nous définissons un ensemble de schémas ShEx bienformulés, qui possède d'intéressantes caractéristiques pour l'optimisation de requêtes SPARQL. Nous développons ensuite notre méthode d'optimisation par l'exploitation d'informations extraites d'un schéma ShEx. Enfin, nous rendons compte des résultats des évaluations effectuées, montrant les avantages de l'application de notre optimisation face à l'état de l'art des systèmes d'évaluation de requêtes.

Motivation and Objectives

The World Wide Web Consortium (W3C) [Berners- Lee and Jaffe, 1994] is an international organization that works to develop Web standards. W3C's mission is to lead the Web to its full potential by developing protocols and guidelines that ensure the long-term growth of the Web.

The term "Semantic Web" refers to W3C's vision of the Web of linked data. It was coined by Tim Berners-Lee, the inventor of the World Wide Web and director of W3C. It is a Web of data where the Resource Description Framework (RDF) provides its essential mean of data representation and publishing. RDF, with other semantic web technologies, aims at describing the Web in a meaningful way, by standardizing their representations, structuring them, establishing relations and links between them, providing inference rules within them, and providing easy ways to access them. The Semantic Web can be seen as an extension to the classic Web of documents, not an alternative for it.

The essential goal of the Semantic Web is to enable automation of the data on the web by defining standards and to develop systems that can support trusted interactions over the network.

A pre-RDF ground work started in 1997. RDF was adopted as a W3C recommendation in 1999. In 2013, more than four million Web domains contained Semantic Web markup according to keynote by Ramanathan V. Guha at ISWC 2013 (The 12th International Semantic Web Conference) [Guha, 2013].

If the Semantic Web is viewed as a global database, then it is easy to understand why one would need a query language for that data. SPARQL is the query language for the Semantic Web.

The architecture of the Semantic Web can be viewed as a series of layers, where each layer serves some purpose in the definition of the Semantic Web. This idea is known as the Semantic Web Layer Cake, and is attributed to Tim Berners-Lee. A representation of the Semantic Web Layer Cake is shown in Figure 1.1. Each layer is less general than the layers below it.

The W3C provides standards within the stack of the Semantic Web Layer Cake like RDF (a data interchange), SPARQL (a query language for RDF), and OWL (an ontology language which extends the semantics of RDF).

Some of the challenges for the Semantic Web include vastness, vagueness, uncertainty, inconsistency, and deceit. With the increased importance and growth of the Semantic Web on the other hand, research investigations within its technologies and standards become essential.

Several studies have been accomplished concerning semantic web technologies, where some of these studies represent a milestone for RDF. For example in [START_REF] Schmidt | Foundations of sparql query optimization[END_REF] the authors define the evaluation complexity bounds for different fragments of SPARQL, and many of its sub-fragments. In [Graux et al., 2016a] an optimised implementation of SPARQL queries was provided with distributed data architecture for huge data. In [START_REF] Pérez | Semantics and complexity of sparql[END_REF] the authors identify a well-designed fragment of SPARQL that has many evaluation and query analysis advantages for improved evaluations. In [Chekol et al., 2012a] the authors proposed a procedure for deciding the containment of SPARQL queries in the presence of RDF Schema (RDFS). Yet the Semantic Web is still being improved, and more research interests become open whenever new technologies are proposed within this community.

Our objectives in this dissertation include studying the interaction between three different technologies within the Semantic Web: RDF, SPARQL, and ShEx. ShEx [START_REF] Prud'hommeaux ; Prud'hommeaux | Shape expressions (shex) primer[END_REF] is a constraint language for RDF being currently promoted by a W3C working group, providing draft reports like the ShEx Primer draft [START_REF] Prud'hommeaux ; Prud'hommeaux | Shape expressions (shex) primer[END_REF], and the ShEx Specification draft [START_REF] Prud'hommeaux | Shape expressions language 2.0[END_REF]. ShEx would belong to a layer just above the "Data interchange" layer of Fig. 1.1. This technology is designed to be different than RDFS and OWL, which unlike ShEx are not focused on RDF constraints validation. The need of a constraint language for RDF, and the emergence of ShEx as a constraint language open opportunities for investigating its effects, interactions, and the possible improvements within the existing architecture of RDF and SPARQL. To the best of our knowledge this is the first work that consider ShEx with SPARQL in a common framework.

Summary of Contributions

The contributions in this thesis concern the analysis of SPARQL queries in the presence of ShEx constraints, and can be divided in two sub-directions. First, we consider containment of SPARQL queries in the presence of ShEx constraints. In the second direction we consider optimizing the evaluation of SPARQL queries in the presence of ShEx constraints. The set of contributions can be summarized as follows:

• We propose a sound and complete procedure for the problem of containment with ShEx, for the well-designed OPTIONAL SPARQL fragment extended with external UNIONs. We implemented this procedure and test results were provided.

• We define the complexity of containment with ShEx for the following SPARQL fragment: the BGP fragment (NP-Complete), the well-designed OPTIONAL fragment (NP-Complete), and the well-designed OPTIONAL fragment extended with external UNIONs (Π P 2 -Complete).

• We reduce the SPARQL query containment with ShEx constraints into the First Order Logic (FOL) satisfiability problem. We show that our method can be done in an FOL fragment with only two variables whose satisfiability problem is decidable. While the satisfiability of this fragment is NEXP-Complete, the proposed method allows to consider the containment of a large SPARQL fragment, namely the well-designed OPTIONAL SPARQL fragment extended with external UNIONs, MINUS feature, property path patterns, and a fragment of the FILTER feature. We implemented this procedure and test results were provided.

• We defined a set of well-formed ShEx and RDF pairs, where this set provides interesting characteristics for inferring the relative frequency of occurrence of ShEx types. Based on our previous definition we propose a SPARQL query planning procedure that ranks triple patterns. Ranks are used to decide the order of execution of these triples, which according to our experimentation provides a 25% of query evaluation time gain on average for large amounts of data.

1.3

Thesis Outline

Part I -State-of-the-Art

In Chapter 2 we introduce RDF which is the main data interchange technology for the Semantic Web.

In Chapter 3 we introduce SPARQL which is the standard query language for RDF. We concentrate on the fragments and features that we are going to use this thesis.

In Chapter 4 we describe different Schema languages and Ontology languages for RDF, and we explain the intrinsic differences between these two types of technologies.

In Chapter 5 we introduce First Order Logic and we provide a survey on the different fragments whose satisfiability problem are decidable.

In Chapter 6 we present the most important results on query containment from the literature.

In Chapter 7 we present the most important results on query optimisation from the literature.

Part II -Contribution I

In Chapter 8 we present our procedure for solving query containment for the well-designed OPTIONAL SPARQL fragment extended with UNIONs and in the presence of ShEx constraints. We also define the complexity bounds for the following fragments: the BGP fragment, the well-designed OPTIONAL fragment (NP-Complete), and the well-designed OPTIONAL fragment extended with external UNIONs. We implement the described procedure and we present test results using our implementation.

In Chapter 9 we provide FOL encoding for the problem of SPARQL queries in the presence of ShEx constraints for the the well-designed OPTIONAL SPARQL fragment extended with external UNIONs, MINUS feature, property path patterns, and a fragment of the FILTER feature. We implement the described procedure, we present test results, and we draw a comparison with the results, expressivity and complexity between this procedure and the procedure presented in the previous chapter.

Part III -Contribution II

In Chapter 10 we define ranking procedure for the triple patterns of SPARQL queries based on ShEx constraints. The ranking presented in turns allows for an optimised evaluation of SPARQL queries on large amounts of RDF data.

Finally, in Chapter 11 we conclude our work in this thesis, and we provide the perspectives for future works.

Introduction

The Resource Description Framework (RDF) is a standard model for data interchange on the Web. Resources described by RDF can be anything, including documents, people, physical objects, and abstract concepts [START_REF] Schreiber | RDF 1.1 primer[END_REF].

RDF data describes data by identifying resources, assigning properties to them, and establishing relationships between them. A resource is defined using identifiers -known as Internationalized Resource Identifiers (IRIs) -or literals. A relationship between two resources is known as a triple (<subject> <predicate> <object>), making a directed relation from the <subject> to the <object> using the <predicate>. This linking structure forms a directed, labeled multigraph, where the edges represent the named link between two resources, represented by the graph nodes.

Listing 2.1 and Figure 2.1 shows an informal RDF example consisting of triples and its corresponding graph representation respectively. RDF provides a standards-compliant way for exchanging data. Using this simple model, it allows structured and semi-structured data to be mixed, exposed, and shared across different applications. Examples of using RDF may be adding machine-readable information to Web pages, and enriching a dataset by linking it to third-party datasets. RDF has features that facilitate data merging even if the underlying schemas differ, and it specifically supports the evolution of schemas over time without requiring all the data consumers to be changed (i.e. the data always has the triple structure).

<Bob > < is a > < person >. <Bob > < is a friend of > < Alice >. <Bob > < is born on > <
RDF consists of a suite of W3C recommendations published in 2004 (known as RDF 1.0). In 2014, a second suite of W3C recommendations was additional Working Group Notes were published defining a more recent version known as RDF 1.1. This latest suite includes (but is not limited to) RDF 1.1 Concepts and Abstract Syntax [START_REF] Cyganiak | RDF 1.1 concepts and abstract syntax[END_REF], RDF 1.1 XML Syntax, RDF 1.1 Semantics [Patel-Schneider and Hayes, 2014] and other recommendations related to RDF serialisation. The Working Group mission was to extend RDF to include features desirable and important for interoperability, but without a negative effect on deployment.

RDF is currently widely spread on the web and applications exists in several domains. Examples of RDF data available publicly include (but not limited to):

• The project DBpedia which aims at extracting RDF structured content from the information available on the Wikipedia project.

• Bio2RDF which is a biological database based on RDF and semantic web technologies.

• UniProt which provides a comprehensive, high-quality and freely accessible resource of protein sequence and functional information.

• LinkedGeoData which uses the information of the OpenStreetMap project and makes it available in RDF.

In addition, Linking Open Data (LOD) is an initiative and community project to connect related data on the web using RDF (according to the Linked Data format) and making it freely available to everyone. Each node in the diagram of Fig. 2.2 represents an RDF dataset in some domain or special field. These datasets are connected to each where such relation exists. In the current state of the LOD cloud, there are 1,139 interconnected datasets.

RDF 1.1 Formal Definition

Abstract Syntax

The document [START_REF] Cyganiak | RDF 1.1 concepts and abstract syntax[END_REF] defines the abstract syntax of RDF 1.1. In this section we introduce the abstract syntax similar to the later. We first introduce the terminology for the elements over which RDF graphs are constructed. Definition 2.2.1 (RDF terminology). Three pairwise disjoint infinite sets of terms are defined as follows:

• I: The set of IRIs 1 identifying RDF resources.

• L: The set of literals, where a literal may be either a plain or a typed literal.

• B:

The set of blank nodes, where a blank node is locally scoped for the RDF graph, and does not identify any resource.

Now we give the definition of an RDF triple whose elements belong to the previously defined sets.

Definition 2.2.2 (RDF triple

). An RDF triple consists of three components:

1 An IRI (Internationalized Resource Identifier) within an RDF graph is a Unicode string that conforms to the syntax defined in RFC 3987 [START_REF] Duerst | RFC 3987: Internationalized Resource Identifiers (IRIs)[END_REF]. IRIs are a generalization of URIs that permits a wider range of Unicode characters. Every absolute URI and URL is an IRI, but not every IRI is an URI. • Exactly one default graph, being an RDF graph. The default graph does not have a name and may be empty.

• Zero or more named graphs. Each named graph is a pair consisting of a name n ∈ (I ∪B) (the graph name), and an RDF graph. Graph names are unique within an RDF dataset.

Interpretation of RDF

The semantics of RDF 1.1 is defined in [START_REF] Patel-Schneider | RDF 1.1 semantics. W3C recommendation, W3C[END_REF].

In this section we introduce the interpretation of an RDF graph, which is the basis for all other semantic notions discussed for RDF graphs, and also the basis for all the semantics of vocabulary extensions. This interpretation is known as simple interpretation for RDF graphs.

An interpretation of an RDF graph in general is a mapping from IRIs and literals into a set, together with some constraints upon the set and the mapping.

All semantic extensions of any vocabulary or higher-level notation encoded in RDF must conform to the minimal truth conditions defined by the simple interpretation. Other semantic extensions may extend and add to these, but they must not modify or negate them.

Definition 2.3.1 (Simple interpretation).

A simple interpretation Int of an RDF graph is a structure consisting of:

• IR: The universe of Int. A non-empty set of resources.

• IP : The set of properties of Int. (IP ⊆ IR)

Datatypes for Literals

Datatypes are used with RDF literals to represent values such as strings, numbers and dates.

The datatype abstraction used in RDF is compatible with XML Schema. These datatypes are known as XSD (XML Schema Definitions) datatypes.

The list of the RDF-compatible XSD types are given in Table 2.1.

RDF Serialization

RDF 1.1 offers several serialization syntaxes (concrete syntaxes), defined within its W3C recommendations suite. An RDF document in concrete syntax encodes an RDF graph or an RDF dataset which enables their storage and their exchange between systems. However, different ways of writing down the same graph lead to exactly the same triples, and are thus logically equivalent.

The different syntaxes are summarized as follows:

1 We notice in Fig. 2.3 that foaf:, xsd:, schema:, dcterms:, wd: are known as prefixes.

Each of them is expanded to form with its successor complete IRIs, but this is a way to make RDF terms more readable. The prefix notion can be utilized in some of the concrete syntaxes as well be seen in the examples that follows.

We also mention that blank nodes may have several representations which are syntax dependent. An explicit occurrence of a blank node (lets say x) is given by the following syntax: _:x .

N-Triples, N-Quads, Turtle and TriG

These four syntaxes belong to the same family called the Turtle family. Some of these are subsets of others in the same family, the simplest of which is N-Triples, and it belongs to all other syntaxes in the Turtle family.

The example of Fig.

RDF/XML

RDF/XML was the only syntax adopted when RDF was originally introduced in 1990s [START_REF] Schreiber | RDF 1.1 primer[END_REF] 8 6 18 9 3 8 F 4 1 17 0 2 5 F 1 7 A 8B 8 1 3 C 5 F 9 AA 4 D 6 1 9

Introduction

In 2004, the W3C launched the Data Access Working Group for designing an RDF query language, called SPARQL. SPARQL 1.0 [START_REF] Prud'hommeaux | SPARQL query language for RDF[END_REF] became an official W3C Recommendation in 2008, and SPARQL 1.1 [START_REF] Harris | SPARQL 1.1 query language[END_REF] in 2013.

In this chapter we define the syntax and semantics of the SPARQL query language. SPARQL 1.1 extends SPARQL 1.0 by adding features to the query language such as aggregates, subqueries, negation, property paths, and an expanded set of functions and operators. Any of these extensions, if described in this section, will be mentioned explicitly as belonging to SPARQL 1.1. Otherwise, the syntax and semantics are common between the two versions.

For a complete description of SPARQL, the reader is referred to the SPARQL 1.1 specification document [START_REF] Harris | SPARQL 1.1 query language[END_REF] or to [START_REF] Pérez | Semantics and complexity of sparql[END_REF], Polleres, 2007] for its formal semantics.

Abstract Syntax

In this section we define an abstract syntax for SPARQL (as commonly found in the literature, for example in [START_REF] Pérez | Semantics and complexity of sparql[END_REF]) which will be used throughout the remaining part of this dissertation.

First we define query variables. A SPARQL query may contain variables that will be bound to values to give a solution for the query.

Definition 3.2.1 (Query Variable1 ). A query variable is a member of an infinite set that is disjoint from the set of RDF terms. We write V for the set of variable names.

Definition 3.2.2 (Triple pattern).

A triple pattern consists of three components:

• The subject s ∈ I ∪ L ∪ V • The predicate p ∈ I ∪ V • The object o ∈ I ∪ L ∪ V Definition 3.2.3 (Basic Graph Pattern). A Basic Graph Pattern is a set of Triple Patterns.
SPARQL is based around graph pattern matching (Fig. 3.1). Complex graph patterns can be formed by combining smaller patterns in various ways. We define the following graph patterns used in SPARQL:

• Basic Graph Pattern (BGP), where a set of triple patterns must match. It combines triple patterns by conjunction.

• Group Graph Pattern, where a set of graph patterns must all match. It combines graph patterns by conjunction. (For this we use the keyword AND)

• Optional Graph pattern, where additional patterns may extend the solution. (For this we use the keyword OPTIONAL or OPT for conciseness)

• Alternative Graph Pattern, where two or more possible patterns are tried. It provides a means of combining graph patterns so that one of several alternative graph patterns may match. If more than one of the alternatives matches, all the possible pattern solutions are retrieved. (For this we use the keyword UNION)

• Excluded Graph Pattern (MINUS), where an exclusion of results occurs based on removing matches of the evaluation of a graph pattern from another graph pattern.

(For this we use the keyword MINUS)

• Filtered Graph Pattern, where boolean-valued expressions (resembling constraints) limit the number of answers to be returned. Each answer has a set of bindings of variables to RDF terms. Filters restrict solutions to those for which the filter expression evaluates to TRUE. (For this we use the keyword FILTER) • every basic graph pattern is a SPARQL graph pattern.

• if P and P are SPARQL graph patterns and K is a SPARQL constraint, then (P AND P ), (P UNION P ), (P OPT P ), (P MINUS P ), and (P FILTER K) are SPARQL graph patterns.

SPARQL Query

SPARQL has four query forms. These query forms use the solutions from pattern matching to form result sets or RDF graphs. The query forms are:

• SELECT: Returns all, or a subset of, the variables bound in a query pattern match.

• CONSTRUCT: Returns an RDF graph constructed by substituting variables in a set of triple templates.

• ASK: Returns a boolean indicating whether a query pattern matches or not.

• DESCRIBE: Returns an RDF graph that describes the resources found.

Definition 3.3.1 (SPARQL query). Given a SPARQL graph pattern P , a sequence B of variables in P , an IRI µ, and a basic graph pattern Q,

• ASK FROM µ WHERE P • SELECT B FROM µ WHERE P • CONSTRUCT Q FROM µ WHERE P • DESCRIBE B FROM µ WHERE P are SPARQL queries.
In our studies in this thesis we only work with SELECT queries, since this type queries are the most relevant to the query static analysis targeted in this thesis, namely the problem of query containment and query evaluation.

3.4

Well-Designed OPT Patterns.

Well-designed OPT patterns define a class of OPTIONAL patterns that have several desired properties [START_REF] Pérez | Semantics and complexity of sparql[END_REF]. This fragment can be evaluated efficiently, and it provides a pattern that can be easily handled in static analysis tasks.

A query q is well-designed if for every subpattern q = (q 1 OP T q 2 ) of q and every variable x occurring in q, it holds that: if x occurs inside q 2 and outside q , then x also occurs inside

q 1 .
It is also shown in [START_REF] Pérez | Semantics and complexity of sparql[END_REF] that any well-designed graph pattern can be equivalently rewritten in the normal form:

(. . . (t1 AN D . . . AN D t k ) OP T O1) OP T O2) . . . ) OP T On)
where each t i is a triple pattern, and each O j has the same form (also in normal form).

These normal forms can be represented as pattern trees as described in [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF]. For example, a query of the form ((P 1 OP T (P 11 OP T P 111 OP T P 112 )) OP T P 12 ) OP T P 13 , where each P i is a BGP, can be represented as a pattern tree as in Fig. 3.2.

We use well-designed OPT patterns as the fragment considered for the study of SPARQL query containment in Chap. 8 and 9. RPQs, NREs, and GXPath are graph query languages based on the idea of using regular expressions to specify patterns that must be matched by paths in the input graph. Given a query q, the result of its evaluation over a graph G is always a set of node pairs (v, v ) such that v and v are connected by a path p in G matching the query q. These languages mainly differ in the class of supported regular expressions.

Regular Path Queries (RPQs) [START_REF] Mendelzon | Finding regular simple paths in graph databases[END_REF] are the most basic language including concatenation, alternative, and recursion operators.

Nested Regular Expressions (NREs) [START_REF] Pérez | nSPARQL: A Navigational Language for RDF[END_REF] extend RPQs to introduce the ability of traversing edges backwards, as well as the ability of specifying conditions inside paths.

GXPath [START_REF] Libkin | Querying graph databases with XPath[END_REF] is essentially an adaptation of XML Path language (XPath) [START_REF] Robie | XML path language (XPath) 3.1. W3C recommendation, W3C[END_REF] to data graphs. With respect to the previous languages, GXPath introduces the complement operator, data tests on the values stored into nodes, as well as counters, which generalize the Kleene star.

NREs form the basis of Property Path Patterns, the path language of SPARQL 1.1. In a SPARQL query triple pattern, the predicate position may be a path (called Property Path) based on regular expressions whose definition is given in Def. 3.5.1.

Definition 3.5.1 (Property Path). A Property Path p is defined inductively as:

p ::= I | ˆp | !p | (p/p) | (p|p) | p? | p *
where I ∈ I, ˆp is the inverse property, !p is an excluded property, / is a path concatenation symbol, | is an alternative path symbol, ? is optional and * is the Kleene star.

SPARQL Semantics

In this section we provide a semantic interpretation for SPARQL evaluation. Similar semantic descriptions are common in the literature. Here we mainly follow the semantics provided in [START_REF] Pérez | Semantics and complexity of sparql[END_REF], in addition to the semantics of property path patterns from [Chekol, 2016].

Let µ be a mapping (partial function) from V to the set of RDF terms (I ∪ L ∪ B). dom(µ) is the subset of V where µ is defined. Given a triple t, µ(t) is the triple obtained by replacing the variables in t according to µ. Similarly we define µ(P ) for a basic graph pattern P .

Two mapping µ 1 and µ 2 are compatible if for all x ∈ dom(µ 1 )∩dom(µ 2 ), µ 1 (x) = µ 2 (x).

Let Ω 1 and Ω 2 be sets of mappings. We adopt the the definition for the join, union, difference, and outer-join as follows:

•

Ω 1 1 Ω 2 = {µ 1 ∪ µ 2 | µ 1 ∈ Ω 1 , µ 2 ∈ Ω 2 and µ 1 , µ 2 are compatible} • Ω 1 ∪ Ω 2 = {µ | µ ∈ Ω 1 or µ ∈ Ω 2 } • Ω 1 \Ω 2 = {µ ∈ Ω 1 | for all µ ∈ Ω 2
, µ and µ are not compatible mappings}

• Ω 1 Ω 2 = (Ω 1 1 Ω 2 ) ∪ (Ω 1 \Ω 2 )
We use the previous definitions to further define the evaluation of a SPARQL graph pattern in Def. 3.6.1.

Definition 3.6.1 (SPARQL Graph Pattern Evaluation). Let G be an RDF graph. The evaluation of a graph pattern P over G, denoted by P G , can be defined inductively as follows:

• (x, I, y) G = {µ | (µ(x), µ(I), µ(y)) ∈ G} • (x, p?, y) G = {µ | µ(x) = µ(y)} ∪ (x, p, y) G • (x,ˆp, y) G = (y, p, x) G • (x, p 1 |p 2 , y) G = (x, p 1 , y) G ∪ (x, p 2 , y) G • (x, p 1 /p 2 , y) G = ∃n : (x, p 1 , n) G 1 (n, p 2 , y) G • (x, p * , y) G = {µ | µ(x) = µ(y)} ∪ i≥1 (x, p i , y) G • P 1 AND P 2 G = P 1 G 1 P 2 G • P 1 UNION P 2 G = P 1 G ∪ P 2 G • P 1 OPT P 2 G = P 1 G P 2 G • P 1 MINUS P 2 G = P 1 G \ P 2 G • P FILTER K G = {µ ∈ P G | µ |= K}
Where I ∈ I, K is a SPARQL constraint, p is a property path, and p i is the composition of p i times (p/p/ . . . /p).

Preparing Required Fragments for the Rest of this Thesis

In order to reference different SPARQL fragments later, we define them as follows:

• BGP: This is the conjunctive fragment of SPARQL, i.e. the fragment that only allows using the AND operator between triples.

• AND-OPT: The fragment of SPARQL allowing the AND and OPT operators only. We particularly consider the well-designed patterns within this fragment (already defined).

• AND-OPT-(UNION):

The AND-OPT fragment extended with UNION on the top level only (external).

• AND-OPT-(UNION)-FILTER: The AND-OPT-(UNION) fragment extended with the FILTER operator for a particular fragment of constraints. These constraints will be defined hereafter (Section 3.7.1).

• AND-OPT-(UNION)-PP:

The AND-OPT-(UNION) fragment extended with property path patterns from the SPARQL 1.1 syntax. These are regular expressions allowed in the predicate position.

• AND-OPT-(UNION)-MINUS:

The AND-OPT-(UNION) fragment extended with the MINUS operator which puts constraints on situations that must not occur in the results.

Allowed SPARQL Filters

For our up-coming work in this thesis, we are interested in the filter feature to be considered for the SPARQL query containment problem that will be studied. We only consider filters that are decidable for query satisfiability given in [START_REF] Zhang | On the satisfiability problem for sparql patterns[END_REF], which is a necessary requirement for query containment as will be discussed in Chapter 9, Section 9.5.2. Accordingly we define only these filter fragments as follows:

• F ILT ER(bound, =, = c ): The filter fragment only allowing the operators bound, =, and = c .

• F ILT ER(bound, =, = c ): The filter fragment only allowing the operators bound, =, and = c .

Where bound(?x) means that the variable ?x should be bound to a value in the query results. =/ = are the equality/inequality relations between variables. = c is the inequality of variable with respect to a constant belonging to (I ∪ L).

Introduction

In this chapter we are going to mainly concentrate on ShEx, a schema language for RDF.

Later in this book, we are going to use ShEx for static analysis and optimisation of SPARQL queries. In Sect. 4.4 we introduce another schema language called SHACL and compare it to ShEx. We then introduce ontology languages and explain how they are different from schema languages although they may have common characteristics. We give two examples of ontology languages, RDFS and OWL.

ShEx (or Shape Expressions) is intended to be an RDF constraint language. Logical operators in Shape Expressions such as grouping, conjunction, disjunction and cardinality constraints, are defined to make as closely as possible to their counterparts in regular expressions and grammar languages like BNF [START_REF] Prud'hommeaux | Shape expressions: An rdf validation and transformation language[END_REF]. Shape Expressions correlate an ordered pattern of pairs of predicate and object classes (called NameClass and ValueClass) and logical operators against an unordered set of edges in a graph. In the example Listing 4.1, Shape1 is a definition of a shape in ShEx, where a ShEx document contains definitions of several shapes. In the previous example, ex:name and ex:phone are NameClasses and xsd:string is a Val-ueClass. This definition means that for a node belonging to this shape there must strictly exist the predicates ex:name and ex:phone, each once. The objects corresponding to these predicates must be of type xsd:string. ShEx may be serialised using any of three interchangeable concrete syntaxes:

• Shape Expressions Compact Syntax (ShExC), a compact syntax meant for human eyes and fingers. (As in the example of Listing 4.1)

• ShExJ, a JSON-LD [START_REF] Kellogg | JSON-LD 1.0. W3C recommendation, W3C[END_REF] syntax meant for machine processing.

• ShExR, the RDF interpretation of ShExJ expressed in RDF Turtle syntax.

The complexity of RDF validation against ShEx is shown to be NP-complete in [START_REF] Staworko | Complexity and Expressiveness of ShEx for RDF[END_REF].

ShEx is an emerging schema language which has been recently used in several applications including:

ValueAny

A matching triple has any object except those terms or stems excluded by the '-' operator.

ValueReference @<UserShape>

The object of a matching triple is an IRI or blank node and the that node is the subject of triples matching the referenced shape expression.

Rule Types

ArcRule

No references

Allowed 

No title

Not Allowed 

Duplicate title

Not Allowed  • FHIR [HL7, 2017], a platform specification that defines a set of capabilities use across the healthcare process, in all jurisdictions, and in lots of different contexts (clinical, diagnostics, medications, workflow, financial...).

• WebIndex data [World Wide Web Foundation, 2014], which are data intended as a measure of the World Wide Web's contribution to social, economic and political progress in countries across the world.

Abstract Syntax

Given a finite set of edge labels Σ and a finite set of types Γ, we define a shape expression e over Σ × Γ as follows:

e ::= | Σ × Γ | e * | (e|e ) | (e e )
where "|" denotes disjunction, "||" denotes unordered concatenation, and " * " denotes zero or more repetitions. From this definition we also further define the following operators as macros:

• e ? := ( | e) (optional)

• e + := (e || e * ) (repetition for a positive number of times)

• e [m;n] (e repeated i times with i in the interval from m to n)

which are also parts of the ShEx syntax. In the sequel we write a :: t as a shorthand for (a, t) ∈ Σ × Γ.

We denote by Ψ(Σ, Γ) the set of all possible shape expressions over Σ × Γ.

A ShEx schema is a tuple S = (Σ, Γ, δ), where Σ is a finite set of edge labels, Γ is a finite set of types, and δ is a type definition function that maps elements of Γ to elements of Ψ(Σ, Γ), i.e. δ : Γ → Ψ(Σ, Γ).

We notice that a ShEx shape (or simply a shape) is itself a type. While a shape is considered as a user-defined type, more generally a type may also be a built-in type (like xsd:string in the concrete syntaxes of ShEx).

A ShEx schema must have at least one ShEx shape. An empty ShEx schema is a ShEx schema where for each ShEx shape t in it, δ(t) = .

Semantics

[ [START_REF] Prud'hommeaux | Shape expressions: An rdf validation and transformation language[END_REF] Semantically, an RDF graph is valid against a ShEx schema if it is possible to assign types to the nodes of the graph in a manner that satisfies the type definitions of the schema.

We assume a fixed graph G = (V, E) which resembles an RDF graph, and a fixed schema S = (Σ, Γ, δ). A typing of G w.r.t. S is a function λ : V → 2 Γ that associates with every node of G a set of types.

Next, the conditions that a typing needs to satisfy are identified. Given a typing λ and a node n ∈ V we define the neighborhood-typing of n w.r.t. λ as bag (i.e. multiset) over Σ × 2 Γ as neighborT yping λ G (n) = ⦃a :: λ(m) | (n, a, m) ∈ E⦄. We note by L(e) the bag language of a shape expression e, i.e. L(e) is the set of bags allowed by the language of e. Now, λ is a valid typing of S on G if and only if every node satisfies the type definitions of its associated type i.e., for every n ∈

V , neighborT yping λ G (n) ∈ L(δ(t)), for all t ∈ λ(n).

4.4

Other Schema and Ontology Languages for RDF

In this section we are going to describe SHACL, an alternative schema language for RDF.

We then describe two ontology languages, RDFS and OWL, and show how they are different from schema languages.

SHACL

Shapes Constraint Language (SHACL) is a W3C recommendation since the 20th of July 2017 [START_REF] Knublauch | Shapes constraint language (SHACL). W3C recommendation, W3C[END_REF]. SHACL, similarly to ShEx, is a language for validating RDF graphs against a set of conditions. It is being used/supported by several applications like:

• TopBraid Composer [TopQuadrant, 2001] • RDFUnit [START_REF] Aksw | RDFUnit: An RDF Unit Testing Suite[END_REF] • OpenPublicData [START_REF] Istanduk | Open Public Data[END_REF] • Schema.org [Knublauch, 2017].

ShEx can be used as a surface syntax for SHACL. Although ShEx is not yet a W3C recommendation, it is being promoted and expanded by a W3C community group [Kontokostas, 2017].

There are several reasons why ShEx has an advantage over SHACL to be considered for static analysis, we list them here:

1. SHACL can be translated to ShEx, and thus all the static analysis tools for the latter can also be used for the former.

2. ShEx (boolean operators, grammar based operators, and shapes recursion) is more expressive than SHACL (boolean operators).

3. While both ShEx and SHACL can be used for RDF validation, ShEx specifications are designed to be used for a wider set of applications (to generate data, or drive user interfaces). SHACL focuses on validation errors. With ShEx, after validation, an enriched graph is usually obtained; it contains valid nodes and their shapes.

4. ShEx syntax and semantics are based on mathematical concepts, while SHACL original syntax is verbose (Listing 4.3) and its semantics are based on textual descriptions.

(Later SHACL adopted a compact syntax copied from ShEx)

For more information on the comparison between ShEx and SHACL refer to [Gayo, 2016, Gayo, 2015].

Consider an example which is written in both ShExC (Listing 4.2) and SHACL (Listing 4.3). An :Item shape must have a property rdf:type with value :Item and either :source with an IRI or a :computation with a value of shape :Computation. The example shows how the ShExC syntax, which is driven by regular expressions intuition, is human-readable and easy to handle for purposes like mathematical static analysis in comparison to SHACL.

On the other hand, Listing 4.4 is a ShExC example that cannot be expressed in SHACL. The example defines a <Parent> shape as nodes that have one or more combination of properties :hasSon with any value and :sonBirthDate with xsd:date value. In SHACL we cannot express that equivalent number of :hasSon and :sonBirthDate properties should occur.

A SHACL to ShExC syntax translator Scala implementation is available at [Gayo, 2017].

Ontology Languages

Ontology languages allow the encoding of knowledge about specific domains and often include reasoning rules that support the processing of that knowledge. Unlike schema languages, RDF ontology languages (like RDFS and OWL) have semantics that provide extended entailment regimes for the SPARQL query language.

Although ontology languages have some capabilities of modeling languages, they have different purposes and characteristics. The main differences in this sense can be summarized as follows:

• Ontology languages are tailored to describe a domain while schema languages are tailored to describe RDF graphs. The domain of discourse of ontology languages is more related to the problem domain in which one is working like people, organizations, etc. while the domain of discourse of schema languages is the RDF graph that one is trying to describe.

• Ontology languages are usually based on Open World Assumption, while schema languages are usually based on Closed World Assumption.

• Ontology languages are usually based on Non-Unique Name Assumption, while schema languages are usually based on Unique Name Assumption.

These inherent differences make it more difficult to use ontology languages as a constraint validation language.

RDF Schema (RDFS)

RDFS [START_REF] Brickley | RDF schema 1.1. W3C recommendation, W3C[END_REF] is an ontology language for RDF. It extends the basic RDF vocabulary to allow, for example, semantic distinctions between classes and properties, structuring classes into hierarchies, and constraining the domains and ranges of properties within these classes and other basic RDF datatypes. With RDFS entailment, the same set of RDF triples inherits an extended meaning when a SPARQL query is executed on it. To illustrate the differences between simple, RDF, and RDFS entailment, consider the data of Listing 4.5 and its graphical representation in Figure 4.2.

In RDFS, the vocabularies rdf:type, rdfs:subClassOf, and rdfs:range are attributed a special meaning, and thus allows to extend the set of data as shown in Figure 4.2. That is to say that new implicit RDF triples are added to form the intended meaning which is inferred from the vocabulary.

Web Ontology Language (OWL)

OWL [START_REF] Owl | OWL 2 web ontology language document overview[END_REF] is also an ontology language that provides an extended entailment regime to SPARQL queries. OWL has richer vocabulary than RDFS, and is not limited to the general semantical structure. For example it allows to define property restrictions that are local to a class. For example:

• It can define cardinalities.

• It can express that if "A isMarriedTo B" then this implies "B isMarriedTo A".

• It can express that if "A isAncestorOf B" and "B isAncestorOf C" then "A isAncestorOf C".

• It can express that two things are the same, this is very helpful for joining up data expressed in different schemas. You can say that relationship "sired" in one schema is owl:equivalentProperty "fathered" in some other schema. You can also say that two things are the same using owl:sameAs, such as the "Elvis Presley" on wikipedia is the same one on the BBC.

Although the rich vocabulary of OWL allows to express a wide set of constraints, it is not designed to be used as a constraint validation language. To show the point the same set of constraints are expressed in ShExC (Listing 4.6) and in OWL (Listing 4.7). So, although in OWL all the needed constraints (in the given example) are possible to be expressed, yet it is clear how the concentration on many constraints makes the process complicated. Also because it is based on Open World Assumption, the last two lines are required to insist on the functionality of our properties.

Conclusion

In this chapter we first described ShEx which is a constraint language for RDF. This schema language is emerging, and among others, it is interesting to study this language and its applicabilities. Particularly we are going to use ShEx for static analysis and optimisation of SPARQL queries. We compared ShEx to another schema language that seems to be less interesting for our purpose. We also showed that although ontology languages may be interesting as well, they serve different purposes than schema languages. Studies on SPARQL containment with RDFS and OWL have been done in the literature. We are going to consider ShEx for our studies with SPARQL queries, which is to our best of knowledge, the first work considering ShEx with queries. In this chapter we are going to present our survey done on the characteristics of several FOL fragments, and then particularly introduce FOL with two variables (FOL 2 ) which we analyze to be suitable (sufficient expressivity and good performance) for the encoding used in our work to solve SPARQL query containment with ShEx constraints.

FOL Survey

Some fragments of FOL are decidable, while others are not. On the other hand, decidable FOL fragments have different satisfiability complexities. Our interest in a decidable logic with rich features while keeping the satisfiability complexity acceptable for applications led us to make a survey on the decidable FOL fragments from the literature.

In the Table 5.1 we give a summary of the decidable fragments of FOL, with their characteristics and their known satisfiability complexity bounds.

FOL 2

FOL 2 (FOL with two variables) is a decidable fragment of FOL that allows no more than 2 interacting variables. This fragment is attractive from a theoretical point of view due to its expressivity, adding that it has been proven that it is still decidable with equality/inequality and counting quantifiers (e.g. ∃ <n ). [START_REF] Grädel | On the decision problem for two-variable first-order logic[END_REF]][Grädel and Otto, 1999][Etessami et al., 2002] The presence of more than two variables in a formula is not an evidence that the formula does not belong to FOL 2 . Thus the expressivity of FOL 2 may not be intuitive. Consider the following example expression that can be expressed in FOL 2 : "There exists a path of length 4"

• Form 1: ∃x∃y∃z∃w∃v(R(x, y) ∧ R(y, z) ∧ R(z, w) ∧ R(w, v)) • Form 2: ∃x∃y(R(x, y) ∧ ∃z(R(y, z) ∧ ∃w(R(z, w) ∧ ∃v R(w, v)))) • Form 3: ∃x∃y(R(x, y) ∧ ∃x(R(y, x) ∧ ∃y(R(x, y) ∧ ∃x R(y, x))))
The three forms are equivalent to each other, and they belong to FOL 2 .

FOL Theorem Provers Implementations and Serialisations

The CADE ATP System Competition (CASC) can be considered as the world championship for automated theorem proving. CASC is held at each CADE and IJCAR conference. CASC evaluates the performance of sound, fully automatic, classical logic Automated Theorem Proving systems.

There are many FOL Theorem Provers, which are highly optimised, and participate every year in CASC. Examples of such systems are: SPASS, E Theorem Prover, Vampire, iProver, and others. For a complete list of competing systems and the annual competition results please refer to the CASC website [Sutcliffe, 2017a].

All competing systems uses a syntax called TPTP (Thousands of Problems for Theorem Provers) [START_REF] Sutcliffe ; Sutcliffe | TPTP Format for Problems[END_REF].

A TPTP problem is a set of formulae. A formula has the form: language(name, role, f ormula)

• language: The languages currently supported are THF -Typed Higher-order Form, TFF -Typed First-order Form, FOF -(full) First-Order Form, and CNF -in Clause Normal Form.

• name: The name is a word starting lower case, e.g., original_f1, or a single quoted word, e.g., 'A crazy $ name'.

• role: The role is typically one of axiom for axioms, conjecture for conjectures, or negated_conjecture for negated conjectures. A full list of the possible roles is in the TPTP syntax [START_REF] Sutcliffe ; Sutcliffe | TPTP Format for Problems[END_REF].

• f ormula: The logical formula uses a consistent and easily understood notation that can be seen in the Backus-Naur form (BNF) [START_REF] Sutcliffe ; Sutcliffe | TPTP Format for Problems[END_REF].

In THF, TFF, and FOF the formulae are typically any number of axioms and one conjecture. In CNF the formulae are typically any number of axioms and one or more negated conjectures.

An example of a TPTP problem in the FOF language is given with its description at the heading (% is used for comments) in Listing 5.1.

Conclusion

In this chapter we investigated several FOL decidable fragments, and we further commented on FOL 2 which will be used in our work for encoding the problem of SPARQL query containment with ShEx constraints. We also presented the implementations available for -------------------------------------------------------------------Listing 5.1: TPTP problem in the FOF language. Source: http://www.cs.miami.edu/~tptp/ TPTP/QuickGuide/Problems.html FOL, and a syntax called TPTP that will be used in our work as well for experimenting our encoding methods.

% -------------------------------------------------------------------- % All
& H != john ) ) ) . % -

Introduction

Query containment is the problem of statically deciding, given two queries, whether the results of one of them is always contained in the results of the other. Query satisfiability on the other hand is the problem of deciding wether a single query might always return an empty result (for example if it contains a contradiction). Unsatisfiable queries are always contained in any arbitrary query. Query equivalence is yet another problem, that can also be reduced form query containment by checking if two queries are contained in each other.

All these query static analysis tasks are useful for query optimization. In [START_REF] Colazzo | Typing regular path query languages for data graphs[END_REF], the authors proposed a schema language for edge-labeled data graphs (like RDFs), and then studied the satisfiability of 3 different classes of query languages (RPQs, NREs, and CRPQs) when such constraints are considered, but this study did not include containment. In [Genevès andLayaïda, 2006, Genevès andLayaïda, 2007] the authors studied static analysis aspects of XPath using µ-calculus and Monadic Secondorder Logic respectively, then the authors provided in [START_REF] Genevès | Xml reasoning made practical[END_REF] a tool related to their studies. XPath is a query language on tree structures.

The work in [START_REF] Chekol | PSPARQL query containment[END_REF] studied containment of PSPARQL, an extension of SPARQL 1.0 with paths and path constraints. In [START_REF] Kostylev | SPARQL with property paths[END_REF], the authors explored the complexity of containment and evaluation problems for fragments of SPARQL 1.1 property paths.

The study in [START_REF] Pichler | Containment and equivalence of well-designed sparql[END_REF] provides complexity analysis for several fragments of SPARQL. Additionally, in [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF] the containment of well-designed OPT queries is investigated. None of these works consider schemas in the study of containment.

The works in [Chekol, 2016, Chekol et al., 2012a, Chekol et al., 2012b] study the containment problem with ontology languages and entailment regimes (SHI, RDFS, OWL...).

Ontology languages put constraints on data, like schemas, but also allows for entailment of implicit data relations. The works on containment with ontology languages focus on entailment regimes employed in these languages, but this study considers a respectively small fragment without OPT patterns.

Major results on query containment are summarised in Table 6.1. A study on the satisfiability of RPQs, NREs and GXPATH was done in [START_REF] Colazzo | Typing regular path query languages for data graphs[END_REF] with PTIME complexity. On the study of query containment, one of the first studies on Conjunctive Queries (CQs) was done in [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF] with complexity bounds proven to be NP-Complete. The containment of the the well-designed SPARQL fragment (with OPTs) was shown to be Π P 2 -Complete in [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF]. Containment of CQs and Unions of CQs in the presence of OWL DL can be done in EXPTIME without inverse and in 2EXPTIME with inverse in [Lutz, 2008]. Containment of SPARQL (AND and UNION fragment) in the presence of RDFS (rdfs:subclass, rdfs:subproperty, rdfs:domain and rdfs:range) was shown to be solved using µ-calculus (+nominals +converse) satisfiability in 2EXPTIME [Chekol et al., 2012b]. The RDFS fragment mentioned can be translated to the SHI Description Logic fragment. µ-calculus(+nominals+converse).

2EXPTIME

In the rest of this chapter we are going to present the containment procedure for the well-designed OPTIONAL SPARQL fragment [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF] (since this is the main fragment of our work in Chap. 8), and the containment procedure based on encoding to µ-calculus with OWL constraints [Chekol et al., 2012b] (since we are going also to use logical encodings, FOL encodings in our case, in Chap. 9).

6.2

Containment of the SPARQL OPT Fragment

In [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF], the authors studied the problem of SPARQL query containment from the fragment comprising the AND and OPT operators. Their procedure is based on the well-designed OPT patterns described in Section 3.4. The procedure is based on homomorphism between pattern trees, and the authors proved that their procedure is sound and complete. The same authors then showed that the problem for the considered fragment is NP-complete and for the same fragment extended with external UNION is Π P 2 -complete [START_REF] Pichler | Containment and equivalence of well-designed sparql[END_REF].

We present the containment procedure in the following lemma taken from [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF]. The lemma provides the necessary and sufficient conditions for the deciding containment of a well-designed OPT SPARQL queries. The conditions are formulated in terms of pattern trees. Lemma 6.2.1. Consider two well-designed pattern trees T 1 and T 2 with roots r 1 and r 2 , respectively. Then T 1 is contained in T 2 , written as T 1 T 2 , if and only if for every subtree T 1 of T 1 rooted at r 1 , there exists a subtree T 2 of T 2 rooted at r 2 such that:

1. vars(T 1 ) ⊆ vars(T 2 ) , and 2. there exists a homomorphism from the triple patterns in T 2 to the triple patterns in T 1 that is the identity over vars(T 1 ).

We notice that a pattern tree containment relation T 1 T 2 also yields the query containment corresponding to these pattern trees (lets say q 1 q 2 ) [ [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF].

Containment of SPARQL with RDFS Entailment

In [Chekol et al., 2012a] the authors proposed a procedure for deciding the containment of some classes of SPARQL queries with RDF Schema (RDFS) entailment using the modal µ-calculus.

The modal µ-calculus is a formal logic that extends the classical propositional modal logic with least fixpoint and greatest fixpoint. The syntax of a µ-calculus formula ϕ can be defined inductively as follows:

ϕ := | ⊥ | p | X | ¬ϕ | ϕ ∨ ψ | ϕ ∧ ψ | a ϕ | [a]ϕ | µXϕ | νXϕ
where p is an atomic proposition, X is a variable, a is a program (for navigation), and µ and ν are the least and greatest fixpoint operators respectively.

The µ-calculus is an expressive logic, and its usage for solving containment allows for expressing an expressive fragment of SPARQL (e.g. Property Path Patterns).

The SPARQL containment decision procedure in [Chekol et al., 2012a] is given by Theorem 6.3.1, where q S rdf s q means that q is contained in q in the presence of a schema S under RDFS entailment regime. Theorem 6.3.1 ([Chekol et al., 2012a]). Given SPARQL queries q and q and a schema S, Φ(S, q, q ) is unsatisfiable if and only if q S rdf s q .

where Φ(S, q, q ) is a µ-calculus formula comprising the encoding of the two queries (A(q) and A(q , m)), the RDFS schema (Φ S ), the RDFS inference rules(Φ R ), and finally a restriction formula (ϕ r ). As a complete formula it is given as follows:

Φ(S, q, q ) = A(q) ∧ ¬A(q , m)

∧ Φ S ∧ Φ R ∧ ϕ r
The authors also proved that their procedure is sound and complete.

Conclusion

In this chapter we introduced the problem of query containment which has been the subject of several previous studies in the literature. We presented two different containment procedures proposed in [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF] and [Chekol et al., 2012a]. The first study considers the well-designed OPTIONAL SPARQL fragment, while the second study does not consider OPTIONAL operators. The later however considers RDFS constraints and entailment rules.

None of the studies available in the literature consider both OPTIONAL operators and typing constraints in the same time. This will be the topic of our contribution in Chap. 8 and 9.

Introduction

Query optimization for the RDF data model has been studied with various approaches in the literature. Most existing works are based on scanning the data a priori and either saving new pieces of information about it, or providing alternative data representations. The works in [START_REF] Goasdoué | Cliquesquare: efficient hadoop-based rdf query processing[END_REF], Huang et al., 2011, Lee and Liu, 2013, Neumann and Weikum, 2008, Papailiou et al., 2013] are based on techniques that mainly focus on join optimizations by indexing the data. These works do not consider structured data and data typing. Another approach that also does not consider the query structure, yet provides optimized query processing, is vertical data partitioning [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF].

The works in [START_REF] Fernández | Binary rdf representation for publication and exchange (hdt)[END_REF], Joshi et al., 2013, Pan et al., 2015, Pham et al., 2015] also provide query optimization techniques, by proposing new data representations that are more compact after scanning the data. Additionally, in [START_REF] Zhang | Eagre: Towards scalable I/O efficient sparql query evaluation on the cloud[END_REF], Zou et al., 2011, Kim et al., 2017] the authors study the structure of the data and provide structural summaries or representative schemas. None of these works is based on a given schema, and thus they require an extensive data scan.

For works based on typed data, an approach was proposed in [START_REF] Benzaken | Optimizing XML querying using type-based document projection[END_REF]] that considers typed XML data trees. Unlike RDF, the tree data-type model of XML allows for extremely efficient subtree pruning. In [START_REF] Aberer | Semantic query optimization for methods in object-oriented database systems[END_REF] semantic query optimization for object-oriented databases is considered. In [START_REF] Schmidt | Foundations of sparql query optimization[END_REF], Serfiotis et al., 2005] the authors consider query optimization for typed RDF graphs. These works are mainly oriented towards schema violations.

In [Graux et al., 2016a] the authors provide a SPARQL query evaluator, SPARQLGX, that relies on a translation of SPARQL queries into executable Spark code that adopts evaluation strategies according to the storage method used and statistics on data. Within the system, optimized joins are considered by reordering BGP triple patterns by combining those with common variables. Their approach scales better than the state-of-the-art systems they compare with (RYA, S2RDF, CliqueSquare, PigSPARQL, RDFHive, SDE) [Graux et al., 2016a].

In [START_REF] Schmidt | Foundations of sparql query optimization[END_REF] the authors give Figure 7.1 with the evaluation complexity bounds for different fragments of SPARQL, where A, U, O, F are the AND, UNION, OPT, and FILTER fragments respectively. π as a superscript means the corresponding fragment with projection, and the subscript define the number of variables where such constraint holds. This work is a milestone for any optimization efforts within these fragments.

In the rest of this chapter we are going to present two main query optimization techniques.

The first is based on data indexing and query planning [START_REF] Papailiou | H2RDF+: High-performance distributed joins over large-scale RDF graphs[END_REF], because we will work on query planning for our own optimizations but based on ShEx constraints instead.

The second work we will discuss is SPARQLGX [Graux et al., 2016a], over which we will implement our optimization technique. An example of a query evaluation systems that performs query planning based on data indexing is H 2 RDF+ [START_REF] Papailiou | H2RDF+: High-performance distributed joins over large-scale RDF graphs[END_REF]. The main contribution of this system is to deal and scale well with substantially complex, non-selective joins in queries which normally result in exponential growth of execution times. H 2 RDF+ utilizes distributed MapReduce processing and HBase [START_REF] Foundation | Apache HBase[END_REF] indexes.

H 2 RDF+ plans the execution order of the different joins so as to minimize the total query execution time. To find the optimal join order one have to consider the different combinations in which the joins can be performed, whose quantity grows exponentially to the number of joining variables, making the problem computationally expensive. H 2 RDF+ uses a greedy, cost-based planner that chooses the join that will be executed in every step of the query.

There are two cost models used by H 2 RDF+ depending on whether intermediate results exists or not. The two cost models are given in [START_REF] Papailiou | H2RDF+: High-performance distributed joins over large-scale RDF graphs[END_REF] as follows:

Merge join cost model: (no intermediate results)

M Jcost(Q) = i∈Q ReadKeys(Q, i)/thr ReadKeys(Q, i) = min{(min j∈Q n j ).o i .SeekOverhead, n i o i }

Sort-Merge join cost model: (with intermediate results

)

SM Jcost(Q, I) = (2 i∈I n i o i + i∈Q ReadKeys(Q ∪ I, i))/thr
where • Q: input query.

• I: input intermediate results

• n i : number of join variable's bindings for the i th query.

• o i : average bindings of the non-joining variables corresponding to one join variable binding. Refers to the i th query.

• thr: the scan throughput.

• SeekOverhead: the seek overhead (6,400 key-values)

• ReadKeys(Q, i): the number of key-values that will be read from the i th query.

H 2 RDF+ tries to store intermediate data that maintain grouped results as much as possible. Figure 7.2 shows how grouped results are stored. Figure 7.3 shows the join procedure on the grouped results. In the map phase, it splits the group according to the join variable, so it creates one group for each department. In the reduce phase groups of professors are retrieved from the index and are merged with the inputs to form the resulting outputs.

Typed Data

An example of SPARQL query optimization with typed data is proposed in [START_REF] Schmidt | Foundations of sparql query optimization[END_REF]. Typed data in other words mean data with constraints to which they comply. The study in [START_REF] Schmidt | Foundations of sparql query optimization[END_REF] did not consider a specific schema or constraint language RDF data, rather it considered any constraint that can be expressed in First Order Logic (FOL).

The optimization proposed in the later study leads to the elimination of some query triple patterns based on static analysis. Elimination only occurs when such triple patterns does not affect the results according to the given FOL constraints.

An example given in [START_REF] Schmidt | Foundations of sparql query optimization[END_REF] uses entailment rules of RDFS encoded in FOL, which we also present here. Consider the following two RDFS triples: The optimization in this system is based on eliminations, similar to the elimination given in the previous example.

7.4

Distributed RDF Store and Triple Pattern Ordering (SPARQLGX)

SPARQLGX is a SPARQL query evaluation system that shows to be more efficient than other competing query evaluation systems for the GBP fragment on large-scale datasets.

The optimization resulting from this system relies in the storage method used, the query translation, and data statistics collected [Graux et al., 2016a].

SPARQLGX stores RDF data in a distributed architecture based on Apache Spark [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF]. It uses existing Hadoop [START_REF] Foundation | Apache Hadoop[END_REF] infrastructures to evaluate SPARQL queries.

Where there are many other query evaluation systems based on distributed datastores, the main optimization resulting from this system relies on the following:

• Storage Model: SPARQLGX takes advantage of a vertical partitioning architecture for RDF datasets, introduced by [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF]. This vertical partitioning is based on storing a triple (spo) in a file named p whose contents stores only the values of s and o. Thus RDF triples having a common predicate are stored in a common file. This method of storage takes advantage of the fact that often in RDF datasets the number of distinct predicates are few relative to the number of distinct subjects and objects. Therefore the storage model leads to a compression of data since the predicate column is removed, while the conversion to this model is straightforward and linear.

• SPARQL query translation: SPARQLGX compiles SPARQL conjunctive queries and generates Scala code that is directly executed by the Spark infrastructure (Spark Scala API). Spark is set up to use the Hadoop Distributed File System (HDFS). Given a conjunctive SPARQL query, SPARQLGX translates the first triple pattern then searches for common a common variable in the other triple patterns to make a join. This allows to obtain optimizations based on join commutativity.

• Data statistics: SPARQLGX also collects data statistics that allows to define a selectivity rank for each triple pattern, and thus ordering triple patterns according to their selectivity values before they are translated.

Figure 7.4 presents the experimental results of SPARQLGX in comparison to other query evaluation systems. In the experimental setup described in [START_REF] Graux | SPARQLGX in action: Efficient distributed evaluation of SPARQL with apache spark[END_REF] a dataset of 109 Million RDF triples was used from the WatDiv benchmark its 20 different queries. Part II Contribution I -SPARQL Query Containment with ShEx Constraints

Introduction

In this chapter we investigate the SPARQL query containment with ShEx constraints. Given two SPARQL queries, and a set of ShEx constraints, our purpose is to statically analyze such queries, namely determining the containment relation between them before being actually executed on the data.

For the fragments of SPARQL including OPTIONAL patterns, the containment of queries is normally investigated with the notion of subsumption because queries with OPTIONAL patterns may return results where not all the query variables are bound to values [START_REF] Arenas | Querying semantic web data with SPARQL[END_REF].

A solution mapping is a mapping from a set of variables to a set of values, thus designating an answer for a query. A solution mapping σ 1 is subsumed by another solution mapping σ 2 written as σ 1 σ 2 if all the variables of σ 1 are also in σ 2 and have the same mapping values. Given a set of mappings Ω 1 (resembling a SPARQL query solution), it is subsumed by another set of mappings Ω 2 written as Ω 1 Ω 2 if for every

σ 1 ∈ Ω 1 there exists σ 2 ∈ Ω 2 such that σ 1 σ 2 .
The consideration of ShEx constraints in query containment is important, because such constraints may affect the results of containment checking. For instance consider the following two SPARQL query graph patterns:

Q 1 : {?x :producer :p1 . ?x :feature "feature1"} OPT {?x :feature "feature2" . ?x :expiryDate ?d} Q 2 : {?x :producer ?y . ?x :feature "feature1"} Without constraints, no containment relation holds between these two queries. However, consider the following ShEx constraints defined for a P roduct node type: <Product> { :name xsd:string , :expiryDate xsd:date ? , :producer @<Company> + , :feature xsd:string } The previous ShEx shape definition means that a node of type "Product" should have a name of type string, optionally have an expiry date, have at least one producer which belongs to another ShEx shape Company , and have exactly one feature of type string. Given that these ShEx constraints apply to the data, we can deduce that a containment relation Q 1

Q 2 holds between the two queries. This is due to the constraint that a "feature" predicate is allowed to occur only once, and thus in query Q 1 the right hand side of the optional pattern will never return results. In such case, we can deduce that the containment relation Q 1 Q 2 holds between the two queries.

There are several kinds of ShEx constraint violations that may lead to a new conclusion about the containment of two queries. These include (1) cardinality constraint violations, (2) basic data type constraint violations (like xsd:string, xsd:data . . . ), and (3) ShEx type definition violations (like @ Company type).

Data on the web are getting larger, and distribution of data is getting more applicable. Different data sources are often being managed by different authorities. The need of schemas becomes increasingly necessary in order to manage the big amounts of data. While different sources in the same domain may share the same vocabulary, their constraints on data may vary. While these slight differences in data shapes may become a hassle for users to track individually, the use of OPT patterns in SPARQL provides a way to ask for constraints that are not necessarily applicable, and that is why the study of the optional fragment is particularly interesting.

In this chapter we define a sound and complete procedure for containment of several SPARQL query fragments in the presence of a ShEx schema, based on the usage of ShEx validators and query containment solvers that don't consider any schema constraints. We also study the complexity of the problem. The results vary from NPTIME-Complete to Π P 2 -Complete according to the fragment considered.

8.2

Containment Procedure Overview

The containment problem we are considering takes two input queries and an input ShEx schema.

In order to perform our containment, the procedure we propose requires a ShEx validator and query containment solver. The ShEx validator is used in order to transform the input queries, a process which also depends on an input ShEx schema. Parts of the queries are first transformed into RDF triples, and validated against the ShEx document. We use the validation results to transform the original queries by eliminating their invalid parts. The two new queries obtained are then given to the query containment solver in order to decide the containment result. The procedure is described in the diagram of Figure 8.1. In Section 8.3 we describe the query transformation procedure. Then in Section 8.4 we explain how to use the transformed queries, and we prove that our method is sound and complete. In Sect. 8.5 we study the complexity of SPARQL containment with ShEx with respect to different SPARQL fragments up to AND-OPT-(UNION). In Sect. 8.6 we present our implementation of the procedure and the results of our experimentation.

Q 1 S' Q' 1

Query Transformation

Query transformation under ShEx constraints is a process in which we rewrite a query, where the resulting query is equivalent to the original query given that the ShEx constraints hold on the data sets. Two queries are considered to be equivalent if they always give the same execution results.

The resulting query transformations defined in this section have several utilizations, namely for optimization purposes, especially that they are equivalent to and smaller than the original queries. We use them in this chapter particularly for defining containment in Section 8.4.

Before defining the transformation procedures, we give some preliminary definitions. According to the previous definition, there always exists a homomorphism from the triples graph of P to the triples graph of P = RDF(P ). In fact, P is an RDF data set that can be validated against a ShEx schema as will be seen later.

BGP Transformation

Query transformation of a BGP query is based on the RDF document validation. RDF validation against ShEx is defined with its NP-complete complexity in [START_REF] Staworko | Complexity and Expressiveness of ShEx for RDF[END_REF].

Definition 8.3.4 (Query Transformation). For a BGP SPARQL query Q and a ShEx schema S, the query transformation function T S is defined as follows:

T S (Q) =    Q, if RDF(Q) is valid w.r.t. MIN 0 (S)
empty query, otherwise

The validation against MIN 0 (S) is due to the fact that the query triples do not catch the complete data structure. Indeed, queries by nature are just partial representations of the constraints on the data that should be extracted.

AND-OPT Transformation

We extend the BGP transformation to a more interesting SPARQL fragment for our problem, the AND-OPT fragment. The results in this case will be a modified AND-OPT query that is equivalent to the original query, by applying two steps: (1) Eliminating non-valid OPT patterns, and ( 2) replacing some OPT operators with AND operators.

For the step ( 1), if we find out that some OPTIONAL patterns will never return results due to the ShEx constraints, the new query that results from this transformation is obtained by omitting these OPTIONAL patterns.

Consider the following SPARQL query:

Q: {:p1 :producer ?y} OPT {:p1 :review ?z} and the following ShEx schema (a minimals discarding ShEx schema):

<product> { :name xsd:string ? , :expiryDate xsd:date ? , :producer @<company> * , :feature xsd:string ? }

We consider two triple sets for validation against the ShEx schema, {:p1 :producer :y} which is valid, and {:p1 :producer :y. :p1 :review :z} -the optional graph pattern with its parent graph pattern -which is not valid. As a result of this validation step, we rewrite the query by removing the optional pattern which corresponds to the triple set which is not valid, and thus we get:

Q : {:p1 :producer ?y}
Query Q is always equivalent to the original query Q for a dataset using the previous ShEx definition, due to the validation process we applied before eliminating non-valid parts.

In general, given a well-designed OPT pattern in normal form, we apply a validation step for each node of its pattern tree representation. The validation of a node considers its own triples, and all the triples of its ancestors up to the root. Now consider the pattern tree example of Fig. 8.2.

• If the BGP P 1 is not valid, then the whole query will never return results.

• If the BGP (P 1 ∪ P 11 ) is not valid, then node P 11 and all its descendants must be eliminated.

• If the BGP (P 1 ∪ P 11 ∪ P 111 ) is not valid, then node P 111 must be eliminated, and so on... We notice that the union operator used above (∪) is the set union operator, and should not be misinterpreted as the SPARQL's UNION operator. In the previous examples the union (∪) of two sets of triple patterns (each is a BGP) is a bigger set of triple patterns (also a BGP).

After eliminating non-valid OPT patterns, a new well-designed pattern tree will be obtained.

The new resulting pattern tree resembles the graph pattern of the new query on which we proceed for the following steps of our procedure. For step (2), we check if it is possible to replace some OPT operators with the AND operator.

Considering the pattern tree representation of a query this operation can be described by uniting two directly connected nodes into one node, one of which is a child node, and the other is its parent node.

To show this by example, consider the following query:

Q: {?x :name ?n} OPT {?x :phone ?p} and the following ShEx shape:

<Person> { :name xsd:string , :phone xsd:string }

According to this ShEx shape definition, we know that :name and :phone will always occur together. Thus the right hand side of the OPT pattern will always occur with the left hand side of it. We therefore deduce that the previous query Q is equivalent to another query Q without an OPT pattern.

Q : {?x :name ?n. ?x :phone ?p}

Two nodes in a query pattern tree must be merged into one node (the parent node), if and only if the triples of the child node will necessarily return results whenever the parent node returns results. We apply this check on every pair of parent-child nodes in the query pattern tree in order to get the final transformation of the query.

The transformations described in the latter examples for the AND-OPT SPARQL fragment are given formally in Definition 8.3.6.

Definition 8.3.5. Given a pattern tree P, and a node n of P , we define R P (n) to be the union of the set of triples of n and the set of triple of all its parent nodes up to the root node.

Definition 8.3.6 (Query Transformation). For an AND-OPT SPARQL query Q, its pattern tree representation P, and a ShEx schema S, the query transformation function T S is defined by the following steps:

1. For each node n of P, if R P (n) is not valid w.r.t. MIN 0 (S), then eliminate n and all its descendants from P. Let P be the new pattern tree after the validation of all the nodes of P.

2. For each pair of nodes n 1 and n 2 of P , such that n 1 is the parent of n 2 , if it is necessary for every complement of RDF(n 1 ) to include the RDF triples of RDF(n 2 ) according to S, then merge n 1 and n 2 into one node. Let P be the new pattern tree obtained.

We define T S (P) = P .

AND-OPT-(UNION) Transformation

For the AND-OPT SPARQL fragment extended with UNION at the top level, the same procedure can be applied on each UNION pattern separately.

Consider a query pattern Q having the following structure:

Q = Q 1 UNION Q 2 UNION . . . UNION Q n
UNION at top level means that every Q i in Q is a query pattern in the AND-OPT fragment. Now we define the query transformation of the AND-OPT-(UNION) SPARQL fragment.

Definition 8.3.7 (Query Transformation). For an AND-OPT-(UNION) SPARQL query pattern

Q = Q 1 UNION Q 2 UNION . . . UNION Q n ,
the pattern tree representation P for Q, and P i for each Q i , and a ShEx schema S, the query transformation function T S for P is defined as follows:

T S (P) = T S (P 1 ) UNION T S (P 2 ) UNION . . . UNION T S (P n )

Query Containment with ShEx

In this section we show how SPARQL query containment with ShEx can be done by benefiting from the transformations of Sect. 8.3.

We first apply the transformation procedure on the two queries to be checked for containment based on a given ShEx schema. The resulting transformations are then checked for containment without considering the ShEx document using query containment solvers as the one proposed in [START_REF] Pichler | Containment and equivalence of well-designed sparql[END_REF]. If the containment of the query transformations holds, then the containment of the original queries with the consideration of ShEx holds.

Definition 8.4.1. Given two queries q 1 and q 2 , we define the relation q 1 S q 2 to mean that q 1 q 2 holds in the presence of a ShEx schema S.

Theorem 8.4.1. Given two queries q 1 and q 2 , and their corresponding transformations q 1 and q 2 according to a ShEx schema S, the containment relation q 1 S q 2 holds if and only if q 1 q 2 holds.

Proof. The soundness of our procedure is evident from the fact that the transformations are equivalent to the original queries in the presence of the ShEx constraints. We use the empty schema as a transformation, or we eliminate parts of the queries only when we are sure that these parts will not return results according to the given schema.

For the completeness of the procedure, we prove it according to the corresponding fragment for each case.

1. For the BGP SPARQL fragment, assume we have two BGP queries q 1 and q 2 and their corresponding transformations q 1 and q 2 according to a ShEx schema S. For the completeness of the procedure, our purpose now is to prove that if q 1 q 2 , then q 1 S q 2 . For the case where q 1 is transformed into the empty query, q 1 q 2 always holds, since the empty query is contained in every other query, and therefore the assumption condition can never happen. For the case where q 1 is not empty and q 2 is empty, that means that also q 2 will never return results due to a violation to the ShEx rules. No query can be contained in a query that does not return results except the empty query, and since we know that q 1 may return results due to the absence of any ShEx violation, then q 1 S q 2 always holds. The final case is when both q 1 and q 2 are kept exactly the same as q 1 and q 2 . In the latter case, if q 1 q 2 , then there exists no homomorphism from q 2 to q 1 . Given that the triples of q 1 don't violate the ShEx schema rules, then there exists a data set D which is a complement of RDF(q 1 ) w.r.t. S. BGP query solving is based on homomorphism from the set of query triple patterns to the set of RDF triples ( [START_REF] Seaborne | SPARQL 1.1 query language[END_REF]). A solution for q 1 necessarily exists in the proposed data set since the homomorphism exists by our proposal. Now we assume that the same solution also holds for q 2 and conclude a contradiction. If the same solution holds for q 2 , then there exists a homomorphism from its triples patterns to D. Since all variables of q 1 are replaced with fresh IRIs, then a homomorphism is also necessary to hold from the triple patterns of q 2 to the triple patterns of q 1 , and thus we conclude a contradiction because this homomorphism is a sufficient condition for deriving that the containment q 1 q 2 holds (condition from [START_REF] Pichler | Containment and equivalence of well-designed sparql[END_REF]).

2. For the AND-OPT SPARQL fragment, assume we have two AND-OPT queries q 1 and q 2 and their corresponding transformations q 1 and q 2 according to a ShEx schema S.

We show that for a transformation q of any query q as proposed in Sect. 8.3, the containment q q always holds. This follows from the fact that our transformation includes only elimination of optional parts of the query and transformation of other optional conditions into necessary conditions (transformation of OPT operators into AND operators). Both transformations make the query more restrictive in the meaning that they eliminate some solutions but never add solutions to the original query. Assume q 1 q 2 , our purpose is to show that q 1 S q 2 . Since q 1 q 2 , then for some subtree T 1 of q 1 , there doesn't exist a subtree of q 2 with the homomorphism condition of Lemma 6.2.1. On the other hand, there exists a data set D which is a complement of RDF(T 1 ) w.r.t. S. A solution for q 1 necessarily exists in D. If this solution is also a solution for q 2 , and thus for q 2 , then a homomorphism must hold from T 2 of q 2 to the D, and thus there exists a homomorphism from T 2 to T 1 , that necessarily doesn't hold due to the fact that q 1 q 2 , and therefore a contradiction is derived.

3. For the AND-OPT-(UNION) SPARQL fragment, the same proof holds as for the AND-OPT fragment, except that instead of proposing a complement data set that has a solution for q 1 , leading to a contradiction when assuming it to have a solution for q 2 , we alternatively propose multiple data sets, each corresponding to a top level UNION part of the query, and deriving a contradiction for each of the proposed data sets.

Complexity

In this section we study the complexity of SPARQL query containment with ShEx with respect to different SPARQL fragments.

We show that the complexity varies from NP-complete to Π P 2 -complete for the SPARQL fragments BGP, AND-OPT, and AND-OPT-(UNION). We also extend these fragments to include filter, property path patterns, and the MINUS operator whose containment problem is in the NEXP time complexity class, yet this is not shown to be a lower bound.

SPARQL AND-(OPT)-(UNION) Fragments

Theorem 8.5.1. Containment with ShEx for the SPARQL BGP fragment is NP-complete.

Proof. The complexity of containment of the SPARQL BGP fragment is NP-complete [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]. In the presence of ShEx constraints, a sufficient procedure to check containment is to first validate the BGP of each of the considered queries against the ShEx document. RDF validation against ShEx is NP-complete. An invalid query will return no results, and thus is contained in any other query. Otherwise, the normal containment procedure (without ShEx) is applied. Then the BGP fragment containment with ShEx is also in NP.

To prove the NP-hardness of the problem, it is sufficient to show that the containment with ShEx is at least as hard as containment without ShEx which is shown to be NP-complete for the considered fragment. A reduction from the containment problem to the containment with ShEx problem can be easily shown by assuming an empty schema.

Theorem 8.5.2. Containment with ShEx for the well-designed OPT SPARQL fragment is NP-complete.

Proof. In [START_REF] Pichler | Containment and equivalence of well-designed sparql[END_REF], the authors studied the problem of containment of well-designed OPT SPARQL queries. The authors provide a procedure for solving the problem, and show the complexity of the problem to be NP-complete for this fragment.

The procedure we follow for deciding query containment of this SPARQL fragment with ShEx is based on both the query transformation described previously in this chapter, and the query containment procedures of [START_REF] Pichler | Containment and equivalence of well-designed sparql[END_REF]. Given two SPARQL queries in the well designed OPT fragment, their containment with ShEx can be decided by the two following steps:

1. Transform both queries. The results of these transformations are two new queries equivalent to the original queries respectively.

2. The two new resulting queries from the first step are used as an input of a general SPARQL containment solver (like the solver described in [START_REF] Pichler | Containment and equivalence of well-designed sparql[END_REF] for this fragment).

Validation of an RDF document against a ShEx document is NP-complete [START_REF] Staworko | Complexity and Expressiveness of ShEx for RDF[END_REF]. Therefore, step (1) of the procedure is a series of ShEx validations each of which is in NP.

The number of validations considered is polynomial since for a given query pattern tree, the validation occurs on all possible branches, rather than subtrees. While the number of subtrees is exponential in a pattern tree, the number of branches is polynomial. As each branch is validated independently, so the result of each branch validation doesn't affect the ones of other branches. Step (2), which is the query containment problem, is NP-complete for the well-designed OPT fragment. Thus the complexity of containment with ShEx is in NP for this fragment.

To prove the NP-hardness of the problem, it is sufficient to show that the containment with ShEx is at least as hard as the containment without ShEx which is shown to be NP-complete for the considered fragment. A reduction from the containment problem to the containment with ShEx problem can be easily shown by assuming an empty schema. Proof. In [START_REF] Pichler | Containment and equivalence of well-designed sparql[END_REF], the authors also studied the problem of containment of the AND-OPT-(UNION) fragment. The authors provide a procedure for solving the problem, and show the complexity of the problem to be Π P 2 -complete.

The procedure we follow to for deciding query containment of this fragment with ShEx is similar to the one followed for the AND-OPT fragment, except that in step ( 2) we use the solver designed for the corresponding fragment. The usage of such solver will rise the complexity to Π P 2 .

To prove the Π P 2 -hardness of the problem, it is sufficient to show that the containment with ShEx is at least as hard as containment without ShEx which is shown to be Π P 2 -complete for the considered fragment. A reduction from the containment problem to the containment with ShEx problem can be easily shown by assuming an empty schema. Table 8.1 summarises our complexity results for the containment problem studied for the different fragments in this chapter.

Implementation and Experimentation

In order to implement the procedure described in this chapter for SPARQL containment with ShEx, we needed a ShEx validator and a containment solver:

• We used a ShEx validator provided by the authors of [START_REF] Boneva | Validating RDF with shape expressions[END_REF].

• We used a containment solver for well-designed SPARQL queries (called SPAM tool) provided by the authors of [START_REF] Pichler | Containment and equivalence of well-designed sparql[END_REF].

The whole procedure, which implements the query transformation and the query containment, is combined into a common Java framework, while using Jena ARQ [The Apache Software Foundation, 2011] as a SPARQL parser.

For the testing of our containment tool, we prepared a test set of 5 pairs of different queries among which we want to check the containments. The containment is considered for each pair against the empty schema (equivalent to containment without schema), in addition to 4 prepared different ShEx schemas.

The queries used are a collection from the Berlin SPARQL Benchmark [START_REF] Bizer | The Berlin SPARQL benchmark[END_REF], where the 4 different schemas are constructed by us with varying type and cardinality constraints in order to study the effect of such constraints.

The queries are presented in the appendix 8.2.

The results with our implementation are shown in Table 8.3. The total run-time varies between 756 ms and 995 ms for the cases considered in the test. It is also obvious form the results that the majority of time is spent on the transformation of the queries.

Conclusion

In this chapter we studied the problem of SPARQL query containment with ShEx constraints, and the OPT patterns were shown to be particularly interesting for this study, due to their flexibility with constraints. We showed how transformation of queries can be done based on customized validation procedures. Then we proposed a procedure for the problem of containment with ShEx, and the complexity related to the AND-OPT SPARQL fragment was shown to be NP-complete, and that of the AND-OPT SPARQL fragment extended with external UNION to be Π P 2 -complete. With our proposed query transformation, no complexity

Introduction

In this chapter we provide an alternative method for solving our SPARQL query containment with ShEx constraints. We encode the problem into an FOL formula and we check its satisfiability with existing automated theorem provers.

Encoding the problem into a logical formula allows the use of existing and highly optimized automated theorem provers. It also allows for extending the SPARQL fragment with additional features, which will be discussed in this chapter.

Since FOL satisfiability is not decidable in general, we propose an encoding based on FOL 2 (FOL with 2 variables only), which is a decidable fragment. After a survey done on the decidable fragments of FOL and presented in Chap. 5, we found that FOL 2 provides the sufficient conditions for encoding our problem.

The problem encoding is divided into two formulas. An axiom formula which resembles the encoding of the ShEx document constraints (ζ), and another conjecture formula expressing the problem of the containment of two well-designed OPT queries (A(Q 1 ) ∧ ¬A(Q 2 )). These two formulas (the axiom and the conjecture) can be given to an automated theorem prover to check the validity of the whole problem. The procedure is described in the diagram of Figure 9.1.

Q 1 Q 2

Queries encoding function

Schema encoding function

Schema (S)

FOL Automated Theorem Prover We notice that if no input ShEx document is given, the set of axioms in our problem would be empty. The same procedure can be used without axioms (i.e. only the conjecture) to check the containment of queries without ShEx.

We explain the ShEx document encoding in Section 9.2, and the queries encoding in Section 9.3. In Section 9.4 we describe our implementation of this procedure and the test results obtained. In Section 9.5 we discuss the possible extensions in the SPARQL fragment within this containment procedure. Finally in Section 9.6 we give a conclusion that summarizes the results of this chapter and provides a comparison with the procedure of Chap. 8 where applicable.

ShEx Document Encoding

To start defining the encoding, we first define for each ShEx shape a primitive relation S i (x) meaning that the RDF term x has the shape S i .

Let P i be the set of predicates allowed in a shape S i . Let R be a relation of arity 3 for expressing triple pattern relations (subject, predicate, object). Let O p be a relation of arity 1, describing the type of restriction of the predicate p on the object (e.g. String, Date, IRIInstance . . . ). For each shape S i we define the following implication rule:

∀x S i (x) → (∀y (S Allowed (x, y)) ∧ S Cardinality (x))
Where:

S Allowed (x, y) = {R(x, p, y) → O p (y)|p ∈ P i }
The cardinality formula depends on the form of the shape definition expression, and thus must be defined inductively taking into account the ShEx connectives that may occur.

S Cardinality ≡ δ(e)

Where δ(e) is the expansion of the shape expression e, defined recursivly as follows:

δ((p :: o) [m;n] ) = ∃ ≤n y R(x, p, y) δ((p :: o) * ) = δ(e 1 || e 2 ) ≡ δ(e 1 ) ∧ δ(e 2 ) δ(e 1 | e 2 ) ≡ δ(e 1 ) ∨ δ(e 2 ) δ((e 1 || e 2 ) * ) ≡ δ((e 1 ) * ) ∧ δ((e 2 ) * ) δ((e 1 | e 2 ) * ) ≡ δ((e 1 ) * ) ∧ δ((e 2 ) * ) δ(((p :: o) [m;n] ) * ) ≡ δ((p :: o) * )
Notice that we only care about maximal cardinality constraints, because if this number is exceeded in the query, we know that the query will not return results for this part of the query. While in the case of minimal cardinality constraints, it does not matter for the query (the constraints should apply on the RDF document, not the query).

We also notice that Kleene closure will be transmitted from complex shape expressions into the atomic symbols of the expression as shown in the definition of δ(e). Using this transmission has a semantical loss for the original expression. For example if we have ((p1 :: o1) || (p2 :: o2)) * , this signifies that the number of occurrences of p1 and p2 should be the same. This piece of information is lost after the expansion of the expression by δ, yet this information should be discarded when dealing with queries, such constraint should apply on the RDF document complete data, not the query. Now we define the FOL axiom expressing the ShEx constraints by the disjunction of all the shapes:

ζ ≡ ∀x S 1 (x) ∨ S 2 (x) ∨ • • • ∨ S n (x)
The encoding described previously is always within the FOL 2 fragment. There is no case where more than two variables are needed.

To show an example of the encoding in practice, consider the following ShEx schema having a single shape: This will be translated into the following FOL axiom:

∀x Product(x) ∧ Product(x) → ∀y R(x, name, y) → string(y) ∧ R(x, expiryDate, y) → date(y) ∧ R(x, producer, y) → string(y) ∧ R(x, feature, y) → string(y) ∧ ∃ ≤1 y R(x, name, y) ∧ ∃ ≤1 y R(x, expiryDate, y) ∧ ∃ ≤1 y R(x, feature, y)

Query Encodings

In [START_REF] Letelier | Static analysis and optimization of semantic web queries[END_REF] the authors provide a method for well-designed OPT query containment based on homomorphism between the two pattern trees corresponding to the two queries in question, and they provide a proof for the correctness of their method. In this section we formulate the homomorphism between the two pattern trees in the FOL logic, allowing us to use the formula as a conjecture in our problem to check the containment in the presence of the ShEx constraints axiom. The final containment conjecture formula, similar to the work in [Chekol, 2016], is given as the following combined encoding, where A(Q 1 ) is the encoding of the first query, and A(Q 2 ) is the encoding of the second query:

A(Q 1 ) ∧ ¬A(Q 2 )
In the following, we define the encoding A(Q) of a query Q.

Given a query, each variable in it will be given an IRI referring to its name. This encoding will not use FOL variables, it is just a set of axioms. We define the encoding of a query A(Q) as follows, where P is a BGP, and each W i is a well-designed OPT pattern:

A(P ) = {R(s, p, o) | {s, p, o} ∈ P } A(P OP T W 1 OP T . . . OP T W n ) ≡ A(P ) ∨ (A(P ) ∧ (A(W 1 ) ∨ ... ∨ A(W n )))
The idea from the second formula of the encoding, i.e. for queries with OPT patterns, is to expand the pattern with ∨'s (disjunctions) at each level, because when used for containment checking with another query, it suffices that each branch of the first query pattern tree is contained in at least one branch of the second query pattern tree. The disjunction provides this condition at each level. The previous equation is actually recursive, and for deeper pattern trees more recursion and thus expansion will occur.

To show a simple example of the encoding in practice, consider the following SPARQL query:

Q 1 : {:p1 :producer ?y} OPT {:p1 :review ?z}

This will be translated into the following FOL formula as follows:

R(p1, producer, y) ∨ (R(p1, producer, y) ∧ R(p1, review, z))

The previous FOL formula represents A(Q 1 ). With another query Q 2 we can form our conjecture

A(Q 1 ) ∧ ¬A(Q 2 ) to check the containment Q 1 Q 2 .
The query encoding described until now assumes that there are no variables in the predication position. We next explain how such variables can be adopted in our encoding.

Predicates as Variables

Normally, if a predicate variable is substituted by an IRI as followed for other variables, this IRI will not match to any of the predicates of the ShEx document, and thus will be treated as a violation of the ShEx rules.

This problem can be solved by substitution. For the set of predicate variables, we substitute them by all the possible combinations of the predicate IRIs that are mentioned in the ShEx document. This means that the containment test should be repeated several times, as much as there are different combinations. While it is possible to be expressed (by disjunctions), yet the size of the encoding will increase dramatically.

Without using substitution, expressing predicate variables as variables in the logic can serve our need except that there is a limitation by the FOL 2 fragment -it does not allow more than two variables. Some encodings in this case may give a formula out of the scope of FOL 2 , and thus may make our problem undecidable.

Although several solutions may be adopted, we propose a restriction on the query form that keeps the encoding size with no expansion at all. The restriction states that the predicate variables may only appear in the predicate positions in the query. In this case, it would be possible to treat these variables as variables in FOL and existentially quantify them (∃p 1 ∃p 2 ∃p 3 . . . ). Although more than two predicate variables may occur in the query, yet the encoding still belongs to FOL 2 because these variables are not interacting in a single relation R, and thus can be separated into sets of triples each including only a single predicate variable.

Yet a less tight restriction can be used instead, which states that a predicate variable can be connected to at most two other predicate variables by the relation R. Connected to at most 2 other variables, this allows us to represent the connections as a chain, and thus make it possible to be expressed in FOL 2 .

"Containing Query" Variables

By containing query, we mean the query on the right hand side of the containment symbol (Q lef t Q right ). The variables of Q right which also appear in Q lef t will be substituted by IRIs corresponding to them. For other variables of Q right we substitute them by all the possible combinations from the IRIs of Q lef t .

To reduce the number of combinations to be considered, we limit the substitutes of a variable relative to the position it occurs on (subject, predicate, or object position).

Implementation and Experimentation

In order to implement the procedure described in this chapter for SPARQL containment with ShEx, we need to provide an FOL encoding for the queries and the schemas:

• We used Jena ARQ as a query parser in Java.

• We write our query encoding as a problem conjecture in the FOF TPTP syntax, which is an FOL syntax accepted by the majority of automated theorem provers.

• For the ShEx constraints document encoding into a TPTP axiom set, we use a ShEx syntax expressed in JSON, where there are several tools available for converting from/to ShEx JSON syntax to/from ShEx compact syntax [Prud'hommeaux, 2017a]. (FOF TPTP encoding of our test schemas are given in Chap. A)

• The resulting TPTP axioms and conjecture are then given to an automated theorem prover. (In our experiments we use two different automated theorem provers, namely SPASS [START_REF] Weidenbach | SPASS version 3.5[END_REF]] and E Theorem Prover [Schulz, 2013], to validate our encodings in practice)

For the testing of our containment tool which is based on FOL encoding, we used the same set of query pairs and schema that are used in the experiment of Chap. 8 Sect. 8.6.

Tables 9.1, 9.2, 9.3, and 9.4 show our results with the tool built for the procedure with FOL theorem provers.

Formula execution time on SPASS (ms)

QaQb1 ≈ 10 (with all schemas) QaQb2 ≈ 20 (with all schemas) QaQb3 ≈ 10 (S0, S1) ≈ 20 (with other schemas) QaQb4 ≈ 20 (with all schemas) QaQb5 ≈ 20 (S0) ≈ 30 (with other schemas)

The results shows that a better performance is achieved for the cases considered with the FOL implementation than with the former implementation (Chap. 8). We notice that although the theoretical execution of the second method is NEXPTIME-Complete, the Satisfiability problem of the FOL formula, yet in practice we get better execution time by almost half the execution time compared to the other method which is theoretically in Π P 2 . We expect such results due to the high optimization techniques used in the automated theorem provers, and due to the fact that realistic queries (even relatively big queries) are small with respect to the problem considered. Validation of a whole set of data in contrast with FOL may be tedious to the huge amount of data deployed in such cases, while by nature, queries are relatively concise. It is also clear from the previous results that most of the time is spent on parsing the queries and encoding them, and not in the automated theorem prover itself.

Extensions

In this section we are going to study the potentials of extending our SPARQL fragment for our containment problem. The method based on FOL provides better expressivity, than the former solving method, for dealing with the new fragments.

We study the extension of 3 features separately: Property Path Patterns from SPARQL 1.1, Filter operator, and Minus operator.

Property Path Patterns

In order to adopt property path patterns into our system, we are going to modify the proposed query encoding. The modification will take place only on the first rule of the query encoding. Given a BGP P the encoding becomes as follows:

A(P ) ≡ {A({s, p, o}) | {s, p, o} ∈ P } A({s, p, o}) ≡ R(s, p, o) , if p is simple ≡ A({s, p 1 , o}) ∨ A({s, p 2 , o}) , if p = p 1 |p 2 ≡ ∃z A({s, p 1 , z}) ∧ A({z, p 2 , o}) , if p = p 1 /p 2 ≡ A({o, q, s}) , if p = ˆq ≡ ¬A({s, q, o}) , if p =!q ≡ A({s, q, o}) ∧ A({s, q, o}) → (s = o) ∨ ∃z A({s, q, z}) ∧ Ā({z, q, o}) , if p = q *
Where we define the encoding Ā similarly, but by using another relation R (which corresponds to closure patterns) as follows:

Ā({s, p, o}) ≡ R(s, p, o) , if p is simple ≡ Ā({s, p 1 , o}) ∨ Ā({s, p 2 , o}) , if p = p 1 |p 2 ≡ ∃z Ā({s, p 1 , z}) ∧ Ā({z, p 2 , o}) , if p = p 1 /p 2 ≡ Ā({o, q, s}) , if p = ˆq ≡ ¬ Ā({s, q, o}) , if p =!q ≡ Ā({s, q, o}) ∧ Ā({s, q, o}) → (s = o) ∨ ∃z A({s, q, z}) ∧ Ā({z, q, o}) , if p = q *

Filters

In [START_REF] Zhang | On the satisfiability problem for sparql patterns[END_REF] the satisfiability of SPARQL queries with filters was studied. Consider the following unsatisfiable SPARQL query pattern:

((?x, a, ?y) U N ION (?x, b, ?z)) F ILT ER (bound(?y) & bound(?z))
We know that such example is unsatisfiable due to the inappropriate usage of the FILTER. This result will also affect the results of containment study, and for this reason we study the fragments with FILTER operations.

For some FILTER constructs, the authors showed the satisfiability of SPARQL is undecidable.

We know from our study of containment that deciding satisfiability is necessary for deciding containment. This can be shown by giving a query that is undecidable for satisfiability, and another query that we know is unsatisfiable. In this case deciding the satisfiability of the first query is important for us to know if it is contained in the second query, otherwise our containment procedure is undecidable.

In the following table we present the FILTER fragments that we will consider, by keeping the decidability results from satisfiability. For example, in the table below, Filter(bound, =, = c ) means the fragment of SPARQL with filters only allowing the constructs bound, = (variables equality), and = c (variable inequality to constants).

Filter fragment Decidable FOL 2 encoding complexity

Filter(bound, =, = c ) yes PTIME Filter(bound, =, = c ) yes PTIME Filter(¬bound) no × Filter(= c ) no × Filter(=, =)
no ×

Now we explain how we can extend our encoding for SPARQL containment to adopt filters using the FOL method. We first associate to every pattern P a set Γ(P ) of sets of constraints. (V is the set of variables)

• If P is a triple pattern (s, p, o), then Γ(P ) := {{s, p, o} ∩ V}

• Γ(P 1 U N ION P 2 ) := Γ(P 1 ) ∪ Γ(P 2 )

• Γ(P 1 AN D P 2 ) := {S 1 ∪ S 2 | S 1 ∈ Γ(P 1 ) and S 2 ∈ Γ(P 2 )} • Γ(P 1 OP T P 2 ) := Γ(P 1 AN D P 2 ) ∪ Γ(P 1 ) • Γ(P 1 F ILT ER C) := {S = δ(S, C) | S ∈ Γ(P 1
)}, where δ(S, C) is defined as follows: The final step is applied even if a filter condition does not exist on a studied pattern. A FILTER with the empty condition C empty is considered in this case.

-δ(S, C) = δ(S, C 1 ) ∪ δ(S, C 2 ) , if C = C 1 &C 2 -δ(S, C) = δ(S, C 1 ), δ(S, C 2 ) , if C = C 1 |C 2 -δ(S, C) = equal(x, c) , if C is ?x = c and ?x ∈ S -δ(S, C) = ¬equal(x, c) , if C is ?x = c and ?x ∈ S -δ(S, C) = equal(x, y) , if C is ?x =?
Now the results of the previous procedure are sets whose members will be considered as relations in the FOL encoding (example: equal(x, y)). We present the new query encodings based on these associated sets as follows:

A(P ) = {R(

Minus

In this section we write down a straightforward method for dealing with the M IN U S operator of SPARQL. The M IN U S operator is semantically described as a negation based on testing whether a pattern exists in the data, given the bindings already determined by the query pattern. Starting from our first simplest encoding, we can adopt this operator in the FOL query encoding as follows:

A(P ) = {R(s, p, o) | {s, p, o} ∈ P } A(P 1 M IN U S P 2 ) ≡ A(P 1 ) ∧ ¬A(P 2 )
A(P OP T P 1 OP T..OP T P n ) ≡ A(P ) ∨ (A(P ) ∧ (A(P 1 ) ∨ ... ∨ A(P n )))

Conclusion

In this chapter we showed how the SPARQL containment problem can be solved by generating a corresponding logical formula, using the FOL 2 fragment, and checking its validity.

In a wider comparison, we combine the results of this chapter with the previous chapter (Chap. 8). We developed two radically different approaches for solving the problem and we evaluated them. The first approach relies on the joint use of a ShEx validator and a tool for checking query containment without constraints. In a second approach, we show how the problem can be solved by a reduction to a fragment of first-order-logic with two variables. This alternative approach allows to take advantage of any of the many existing FOL theorem provers in this context. According to the evaluation of how the two approaches compare experimentally, it was shown that the FOL implementation has a better practical performance for the cases considered although it has a higher theoretical complexity.

In addition, with the FOL satisfiability approach, it was possible to adopt extensions (FILTER, MINUS, and property path patterns) that are not supported in the other procedure. Table 9.5 gives an upper bound complexity summary of the results of containment procedures from Chap. 8 and In Chap. 9, and the supported fragments within each. In this chapter we investigate how the evaluation of SPARQL queries [START_REF] Seaborne | SPARQL 1.1 query language[END_REF] can be optimized in the presence of ShEx constraints. We propose a method for optimizing the order of evaluation of subqueries, by taking advantage of the information on the data described in ShEx. While SPARQL query optimization by static analysis is important and well-studied, the emergence of constraint languages (such as ShEx) raises new questions on how the knowledge of additional constraints can be effectively leveraged as a part of the static analysis and optimization. In this work, we focus on the logical query structure and in particular on subquery ordering that can be automatically inferred from a set of data constraints. More specifically, we consider SPARQL basic graph patterns (BGPs), and we focus on the order of execution of triple patterns by ranking them, which aims to minimize the overall execution cost of the query.

We postulate that ShEx constraints contain useful information for selecting the order of execution of triple patterns. Optimization opportunities arise from the presence of joins between query triple patterns, and common variables. In several situations, the order of execution of triple patterns can be rearranged so that the size of intermediate results for join variables are minimized. Consider the arbitrary query example of Listing 10.1 with 3 triple patterns and a join on the variable ?x.

SELECT ? x WHERE { ? x : p1000 : a .

? x : p700 : b .

? x : p1 : c . } Listing 10.1: SPARQL query example Assume that we know that the triple with predicate : p1000 will return 1000 values for ?x, that of : p700 will return 700, and that of : p1 will return 1. The join between the first two triple patterns may give up to 700 values which should be reserved in memory for another join with the third triple. A wise choice in this case is to reorder the triple patterns execution, knowing that the third triple is more selective than the other two triples. Executing the third triple first will guarantee that at most one value will be reserved in the memory for the next join. Such an order will provide an optimized execution of the whole query.

Hence, our main purpose in this work is to infer better execution orders for triple patterns in more general queries, based on the knowledge extracted from a ShEx document. We first define a set of well formed ShEx schemas, that possess interesting characteristics for deciding optimal execution orders. We then define our optimization method by exploiting information extracted from a ShEx schema. To the best of our knowledge, this is the first work addressing SPARQL query optimization based on ShEx. We implemented our procedure on the top of SPARQLGX, which is one of the most efficient engine for distributed SPARQL evaluation and known to outperform many competitors in the field [Graux et al., 2016a]. SPARQLGX already implements various query optimization techniques including reordering triple patterns [Graux et al., 2016a], but without considering schema constraints. We show that our technique further improves the efficiency of query execution times. With large amounts of data, the optimization may exceed 85% for queries that are highly affected by the triple patterns execution order, and by 25% on average. The rest of the chapter is organised as follows: In Sect. 10.2 we introduce some preliminaries necessary for understanding the rest of the paper. In Sect. 10.3 we define well-formation rules for a data-schema pair that are of interest for our optimization process. In Sect. 10.4 we define a graph representation of a ShEx schema. In Sect. 10.5 we formally define our optimization process based on ranking triple patterns. In Sect. 10.6 we report on experimental results with our optimization technique. Finally, we conclude in Sect. 10.7.

Definitions

Abstract Syntax of the Considered ShEx Fragment

In this section we define a variation of the abstract syntax of ShEx. The definition presented here is similar to the abstract syntax defined in Chap. 4 Sect. 4.2, except that here a shape expression e is defined inductively in terms of e + , and then e * is defined as a syntactic sugar, while in the former definition the inverse was adopted (i.e. e was defined in terms of e * , and then e + was defined as a syntactic sugar). The purpose of adopting this variation in this chapter is to allow us to design Def. 10.2.1 and Def. 10.2.2 in terms of the semantics of e + , which would be otherwise complicated to define in terms of the semantics of e * . Thus we recall the definition of the abstract syntax with the adopted variation.

Given a finite set of edge labels Σ and a finite set of types Γ, we define a shape expression e over Σ × Γ as follows:

e

::= | Σ × Γ | e + | (e|e ) | (e e )
where "|" denotes disjunction, "||" denotes unordered concatenation, and " + " denotes repetition for a positive number of times. From this definition we also further define the following operators as macros:

• e ? := ( | e) (optional)

• e * := ( | e + ) (unordered Kleene star)

• e [m;n] (e repeated i times with i in the interval from m to n)

which are also parts of the ShEx syntax. In the sequel we write a :: t as a shorthand for (a, t) ∈ Σ × Γ.

A shape expression schema (ShEx), or simply schema, is a tuple S = (Σ, Γ, δ), where Σ is a finite set of edge labels, Γ is a finite set of types, and δ is a type definition function that maps elements of Γ to shape expressions e over Σ × Γ. If the δ is not defined for some type t ∈ Γ, the default definition is δ(t) = .

Preliminary Definitions

In accordance with the abstract syntax, we define the following shape expression inclusion relation which we use in the rest of the chapter. We also define the following shape expression optional condition. Representing data using RDF, as well as with other semantic web technologies or database systems, is a design issue. The same pieces of information may be represented in different ways according to the designer choices. In addition, given a definite data graph representation, different point of views may be raised on how it is constrained. Thus different ShEx schemas, all of which correctly describe the same data graph, may be suggested as the schemas constraining them. Accordingly, we introduce a notion of well-formed data-schema pairs. The set of rules that will be introduced on the data-schema pairs in this section will help us to better identify efficient SPARQL query designs, by static analysis of the schema.

The rules for well-formation warantee that the necessary information needed for our ranking can be deduced from the ShEx schema, yet the ranking procedure is not deterministic. For some shapes, the relations attached to them are not indicative for the selectivity of those shapes. We also define in this section the schema formation rules that make our shape ranking procedure deterministic.

Definition 10.3.1 (Well-Formed Data-Schema Pair). A data-schema pair (G, S) is wellformed if and only if the following rules hold.

1. Cardinality rule: Every m-to-n relation between two schema shapes in S, where m > n or m is not bound, is modeled from the m-sided shape to the n-sided shape.

Shape distinction rule:

For every 4 schema shapes s 1 , s 2 , so 1 , so 2 ∈ S (not necessarily distinct), and for every 2 predicates p a and p b (not necessarily distinct), so 1 and so 2 are distinct if the following conditions hold:

• (p a , so 1 ) ∈ δ(s 1 )

• (p b , so 2 ) ∈ δ(s 2 )
• O 1 is the set of nodes of G which occur as objects of p a whose subject belongs to the shape s 1

• O 2 is the set of nodes of G which occur as objects of p b whose subject belongs to the shape s 2

• O 1 ∩ O 2 = ∅
The well-formation rules impose a schema design that gives preference to some constraints among others, all of which are respected in the data-schema pair, but it does not force new constraints to be added. Well-formed data-schema pairs provide the maximal set of desired information that can be inferred from the ranking procedure described in Sect. 10.5, without adding new constraints.

Although the well-formation rules are sufficient for optimization of real life data-schema examples, the ranking system is not totally deterministic. A restrictive set of rules on a data-schema pair that make our ranking system deterministic are given in the following definition.

Definition 10.3.2 (Ranking-Deterministic Data-Schema Pair). A data-schema pair (G, S) is ranking-deterministic if and only if the following rules hold.

In the following subsections (10.3.1, 10.3.2, and 10.3.3), we give examples and additional descriptions of the well-formedness and ranking-deterministic rules, aiding to understand how they contribute to our ranking procedure. Indeed, the well-formation cardinality rule helps us to determine the relative quantity of shape occurrences in the data. For example Schema proposition 1 allows us to know that the Student instances definitely occur in the data more than School instances.

Shape Distinction

A shape in a ShEx schema can be as general as allowing any node in any RDF graph to belong to it. The more the shape has restrictions, the more it describes a specific type of nodes. The well-formation shape distinction rule puts restrictions on shapes that seem to be too general that they surely miss expressing some constraints that are inherent in the data.

Example

Data Nodes Isolation

The data nodes isolation rule for deterministic ranking states that a data instance shall not be isolated from other data instances unless isolation is required by the given schema. If we have many isolated nodes (let us say many isolated shcools), the number of schools in the data may be more than the number of students, which renders our ranking procedure unuseful, since it does not reflect the correct relative frequencies of the data.

Shape Relation Graph

In this section we define a shape graph representation that we use to assign ranks to shapes in Sect.

Ranking

In order to decide the order of execution of query triple patterns, we assign them ranks inferred from the analysis of the ShEx document. These ranks are based on two main concepts:

1) The hierarchical relations between ShEx shapes, and 2) The predicate distributions among ShEx shapes.

The first concept gives rankings to shapes, and the second concept gives ranking to predicates. The ranking of query triple patterns is based on the product of the two rankings.

Hierarchical Relations between ShEx Shapes

In ShEx, the definition of a shape may be based on other shapes defined in the same schema. This notion, called shape inclusion, is explicitly represented by the edges of the shape relation graph defined in Sect. 10.4. Such edge relations between shapes allow us to infer information about the relative frequency of data corresponding to these shapes.

Consider Schema proposition 1 in of Example 10.3.1. Representing it as a shape relation graph, School is a child of Student . Each student in the data should have exactly one registered school, and multiple students may be registered in the same school according to the schema. Such a relation between shapes allows us to know that a student instance occurs more in the database than a school instance. Actually the number of schools is at most equivalent to the number of students, where this is a worst case assumption -each student has a unique school. It is evident that this is an extreme case that should not be considered as an average distribution. Thus, it is important to study the hierarchical relations between ShEx shapes. In the example we give the School shape a priority ranking, since we know that they occur less than the Student shape, and thus rendering variables corresponding to it more selective.

Concerning cardinality, we notice that a higher cardinality is independent on the actual number of data instances of a shape. For example, if we have :registeredIn @<School> {1,3} instead of :registeredIn @<School>, that does not necessarily mean an increase in the number of schools; the same set of schools may apply in both cases. For the ranking system it is sufficient to consider the relation structure rather than the structure and cardinalities together, and that is why we ignore explicit cardinalities of edges in the shape relation graph defined in Sect. 10.4.

The ranking procedure we propose starts from the root shapes (root nodes as defined in Definition 10.4.2). A root shape will have a ranking of 1. Going down through the descendant shapes from the root shape the ranking increases. If there are two (or more) incoming edges to a shape, the lower ranking is transferred. A problem in such a procedure is when there is a cycle between shapes in the graph representation of the schema, that means that the ranking will propagate forever. In such case there is no preference for any of the shapes in the cycles, and all of them must have the same ranking. In some cases, a cycle has an optional relation(s) within it, given by the cardinalities "?", "*", or "{0,n}". In such case, we know that a cut in the cycle can only occur at these points. For asserting the strength of normal relations against such optional relations, the preference for ranking is to actually cut the cycles at these points and apply the ranking system by avoiding such kind of cycles. Now we formally define all the procedures described.

Schema Graph Adjustment

First, given the shape relation graph G of a ShEx schema, we modify it by detecting optional relations and cycles.

For each cycle

C i (N i , E i ) ∈ C(G):
• For all predicate p, if there exist nodes n 1 , n 2 ∈ N i such that there exists an edge E(n 1 , p opt , n 2 ), then remove this edge. Let the new resulting graph be G nor .

For each cycle

C i (N i , E i ) ∈ C(G nor ):
• Merge all the nodes x ∈ N i into a single node c i .

Schema Shapes Ranking

Now let the output of the Schema Graph Adjustment be G adj (N, E). We define the ranking function δ S (x) for all x ∈ N as follows:

1. For each node r ∈ R(G adj ), δ S (r) = 1 2. For each node r ∈ R(G adj ), apply the procedure P (r) defined next.

Given a node x ∈ N , the procedure P (x) is defined as follows:

• For each s ∈ N , and for each predicate p where there exists an edge E(x, p, s)

1. If δ S (s) is not initialised: δ S (s) = δ S (x) + 1 2. If δ S (x) + 1 < δ S (s), then δ S (s) = δ S (x) + 1 3. Apply P (s)
Finally, we transmit the cycle rankings to the original nodes.

• For each cycle C i (N i , E i ) in G nor : -For each node x ∈ N i , δ S (x) = δ S (c i )

Predicate Distributions Among ShEx Shapes

In the previous section we ranked shapes according to their relative frequency of occurrences based on relations between them. Such a ranking is not sufficient for deciding rankings of triple patterns in a query since such ranking is also affected by the uniqueness versus globality of predicates within shapes.

Given a predicate p used in the shapes s 1 , s 2 , . . . , s n . The ranking of p within a shape s, denoted as δ P (p, s) is defined as follows.

δ P (p, s) = δ S (s) δ S (s 1 ) × δ S (s 2 ) × • • • × δ S (s n ) , if s ∈ {s 1 , s 2 , . . . , s n } δ P (p, s) = 1 δ S (s 1 ) × δ S (s 2 ) × • • • × δ S (s n ) , otherwise
The previous formula works by reducing the ranking of a predicate when it is more global, i.e. when it is used with more shapes. With more shapes the factors in the denominator will increase and thus reducing the overall ranking. Such predicates are frequent, they are used every where, and this means there will be a large set of nodes in the database associated with this predicate. The ranking system tends to leave such predicates to be executed lastly, and that is why the modelled function reduces its ranking. On the other hand, if a predicate is unique for a certain shape, its ranking tends to be bigger by reducing the number of denominators to only one, which is the shape it corresponds to.

We notice that if a predicate p corresponds to only one shape s m , then the ranking corresponding to it will be always 1, where this value represents the highest ranking possible.

δ P (p, s m ) = δ S (s m ) δ S (s m ) = 1
On the other hand, the lowest possible ranking is when the predicate p is used globally in all the shapes defined in the ShEx document, and particularly when the shape considered for the current ranking is a root node, which have the lowest possible shape ranking of 1, and the denominator is the largest possible which is the product of all the shape rankings.

δ P (p, s root ) = 1 ∀i, where s i is a shape δ S (s i )

SPARQL Query Triple Rankings

Now our purpose is to rank the triple patterns given a BGP query. Triple patterns with higher ranking will be executed first. Before ranking triples, we need to validate the BGP against the ShEx document, and for each subject in the triple patterns the ShEx validator will decide to which shapes this subject may belong. A subject may belong to multiple shapes at the same time. Thus, for each subject s occurring in the triple patterns we have a set C(s) of candidate shapes for s. For convenience, given a triple pattern t, we define C(t) = C(s) if s is a subject of t. We also define p(t) as the predicate of the triple t.

To define the triple ranking function, we use the two ranking functions δ S and δ P defined previously.

Given a BGP B and a triple pattern t ∈ B, we define the ranking of the triple t w.r.t. a ShEx schema, denoted by δ T (t), as follows:

δ T (t) = Avg δ S (S i ) × δ P (p(t), S i ) ∀i, S i ∈C(t)
For a given triple t, the previous function is the average of the product δ S × δ P by considering all the possible candidate shapes for the subject of t.

Evaluation

We prepared experiments with different setups that show the advantageous effects of the optimization procedure described in this chapter. Both experiments use real ShEx schema examples (Web Index [World Wide Web Foundation, 2014] and LDCB SNB [START_REF] Erling | The ldbc social network benchmark: Interactive workload[END_REF] respectively) and a benchmark data generator for each of them.

In the first experiment, the queries are designed by us to utilize different combinations of the schema types. In addition to showing the results of this experiment, the main purpose of hand-crafting queries is to allow readers to investigate the queries in a clear way, where the variable names in the queries are indicative to the type they belong to.

In the second experiment, the queries are generated by a specific benchmarking tool (gMark [START_REF] Bagan | gMark: Schema-driven generation of graphs and queries[END_REF]). This setup is more realistic and convincing concerning the obtained results. Queries generated by the gMark tool are of different structures and sizes, and thus are suitable for benchmarking purposes.

Experiment 1: With Web Index Schema

In this experiment we generate data according to a real example ShEx schema, using a generator called wiGen (or WebIndex Data Generator) [START_REF] Gayo | Validating and describing linked data portals using rdf shape expressions[END_REF]. We make our own set of 12 queries which are of different sizes, and designed to utilise all schema shapes defined in the ShEx schema of wiGen. The generator allows the user to define the number of instances needed for each shape in the schema. We generated 15M nodes, and the resulting RDF dataset is about 80M RDF triples.

Queries

The set of queries we use for this experimentation is shown in with their order of triple patterns computed by our ranking system. Our purpose is to compare each query with counter part queries, which are just equivalent to the original ones, with different order of their triple patterns. The number of permutations for each query depends on the number of triples. For 4 triple patterns there are 24 different permutations, while for 7 triple patterns there are 5040. In our experiment we generate all the permutations if there are less than 50 of them, and otherwise we generate 50 random permutations.

SPARQLGX

An advantage of our optimization technique is that it can be applied on the top of query systems like SPARQLGX [Graux et al., 2016a]. This system in turns is based on SPARK coding with Hadoop underlying infrastructure for evaluating SPARQL queries [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF]. SPARQLGX is known to outperform many competitors in the field concerning conjunctive is 9.8%. We notice that in this calculation we did not consider query Q12 which has a theoretical 98% improvement average. The purpose of Q12 was to show that if the query is unsatisfiable according to the ShEx schema (it violates it), then we do not execute it and the time considered is the validation time of the query. In Q12 the last triple pattern has foaf:homePage in the predicate position and the string "homepageOrg988" in the object position, while the object of foaf:homePage should be an IRI according the ShEx schema.

Experiment 2: With LDBC SNB Schema and gMark Queries

In this experiment we generate data according to the Social Network Benchmark (SNB) schema of the Linked Data Benchmark Council (LDBC). The data and queries are generated by gMark [START_REF] Bagan | gMark: Schema-driven generation of graphs and queries[END_REF]. gMark is a graph and query workload generator based on an input schema. Technically the setup is comparable to that of Experiment 1 except that in Experiment 2 queries are generated by the benchmarking tool rather than being hand-crafted.

In addition Experiment 2 is applied on 4 different dataset of different sizes, thus we show 4 different charts corresponding to the datasets, and therefore allowing to further comment on the effect of data size. Using gMark, we also generated a set of 12 SPARQL queries based on the LDBC SNB schema. We setup the sizes of queries such that in each query there are between 6 and 10 triple patterns, and there are between 4 and 6 distinguished variables. The choice of the query size is to allow for structures to form within the schema hierarchy, and not to limit it to simple variable relations. Going beyond the size where such hierarchies form is pointless for our evaluation, yet we give a small range to provide a variety of formation choices.

As in Experiment 1, we generated 50 random triple pattern permutations of each query.

Results

The results of our query evaluation with the 4 datasets are presented in 4 charts (Figsures 10.2,10.3,10.4,and 10.5), where each is similar to the chart described in Experiment 1.

The results show a faster execution of some queries (Q1, Q9, Q10, Q11, and Q12), while it preserves or slightly improves the execution time of the other queries when run using our methodology. Some queries do not show significant improvement due to the structure of the query and its selectivity. For example if a query is asking for the results concerning two pair of variables signifying the relation between countries and languages. The results of such query is small and constant, since the number of countries and languages is constant; they do not vary even when the dataset size is exponentially increased, and thus such results are expected for some of the generated queries. Actually these kinds of queries are intentionally generated by gMark for benchmarking purposes (check [START_REF] Bagan | gMark: Schema-driven generation of graphs and queries[END_REF]).

Concerning the dataset sizes, it is clear from the charts that our optimization is less evident when the 5M nodes dataset is compared to the bigger datasets. Compared to system S2 in Figure 10.2, the optimized orderings of queries Q1, Q10, and Q12 showed a slight improvement. In Figure 10.3 the improvement is more significant with the latter queries, in addition to the new improvements in queries Q9 and Q11. By further increasing the size of the datasets, the improvement almost stay the same (or precisely it barely increases), which shows a threshold where the gain, although significant, is stabilized.

The average of the improvement of our system (Optimized) compared to avg(S2) is given as follows:

• Dataset 5M nodes: Improvement of queries ranged between 1.2% and 20.5%. The mean improvement of all test queries is 3.8%.

• Dataset 30M nodes: Improvement of queries ranged between 1.6% and 87%. The mean improvement of all test queries is 23.5%.

• Dataset 50M nodes: Improvement of queries ranged between 1.4% and 84.6%. The mean improvement of all test queries is 25.2%.

• Dataset 100M nodes: Improvement of queries ranged between 1.6% and 85.1%. The mean improvement of all test queries is 25.7%.

Conclusion

We studied a method for SPARQL query optimization based on ranking triple patterns in order to select their execution order. The originality of our approach is that rankings generated by our system are based on information inferred from a schema expressed in ShEx, which is an emerging schema language for RDF data. To the best of our knowledge, this is the first attempt of leveraging ShEx constraints for SPARQL query optimization.

We first defined a well-formation notion for data-schema pairs that is useful for inferring quantitative information about data instances. We then defined a procedure for determining rankings. We implemented a prototype of our system on top of the SPARQLGX query evaluation engine, which is known to outperform many competitors in the field. We compared the rankings found by our system, owing to the analysis of ShEx constraints, to the original reordering method of SPARQLGX in terms of query evaluation times, and with datasets of various sizes. Preliminary experimental results indicate that most rankings found by our system lead to improvements in query execution times. This illustrates the interest of considering ShEx constraints for SPARQL query optimization.

Summary

In this thesis, our objective was to study three layers of the Semantic Web, and the interactions between them, leading to interesting results in query analysis and optimization. The three layers mainly included the RDF standard (a data interchange standard), SPARQL (the standard query language for RDF), and ShEx (a constraint language for RDF being currently promoted by a W3C community group).

In the first part of the thesis we introduced these technologies, as well as main results in the literature about two important issues of the Semantic Web (and databases in general), which are query containment and query optimization.

For the part about our contributions on query containment (Part II), we considered the problem of SPARQL query containment in the presence of ShEx constraints. We first proposed a sound and complete procedure for the problem of containment with ShEx, considering several SPARQL fragments. Particularly our procedure considers OPTIONAL query patterns, that turns out to be an important fragment to be studied with schemas.

We then showed that the complexity of our problem for the BGP SPARQL fragment is NP-Complete, for the well-designed OPTIONAL fragment is NPTIME-Complete, and for the well-designed OPTIONAL fragment extended with external UNIONs is Π P 2 -Complete. As an alternative approach, we reduced the SPARQL query containment with ShEx constraints into First Order Logic (FOL) satisfiability problem. We showed that our method can be done in an FOL fragment with only two variables whose satisfiability problem is decidable. While the satisfiability of this fragment is NEXPTIME-Complete, the proposed method allows to consider the containment of a large SPARQL fragment, namely the well-designed OPTIONAL SPARQL fragment extended with external UNIONs, MINUS feature, property path patterns, and a fragment of the FILTER feature. This is the first work addressing SPARQL query containment in the presence of ShEx constraints, and it is the first work addressing the SPARQL OPTIONAL patterns with any kind of schema or ontology language.

For the part about our contributions on query optimization (Part II), we optimized the evaluation of BGP SPARQL queries, on RDF graphs, by taking advantage of ShEx constraints. Our optimization is based on computing and assigning ranks to query triple patterns, dictating their order of execution. For achieving that we first defined a set of well-formed ShEx schemas, that possess interesting characteristics for SPARQL query optimization, more precisely it allows to infer the relative frequency of occurrence of ShEx types. We then define our optimization method by exploiting information extracted from a ShEx schema. We finally reported on evaluation results performed showing the advantages of applying our optimization on top of SPARQLGX (an existing state-of-the-art query evaluation system). According to our experimentation, with large amounts of data, the optimization with our system may exceed 85% for queries that are highly affected by the triple patterns execution order, and by 25% on average. In [Chekol, 2016] the authors studied the problem of SPARQL query containment with an OWL entailment fragment. In this thesis on the other hand, we investigated the problem of SPARQL query containment in the presence ShEx constraints.

Perspectives

ShEx and OWL have different purposes. While the first is an RDF constraint language and adopts the Closed World Assumption, OWL is an ontology language associated with an entailment regime and adopts the Open World Assumption. These two languages exhibit different features useful for different purposes and one language is not meant to replace the other.

It was shown in Chap 4 that it is very verbose to express ShEx constraints in OWL. We also discussed how OWL differs from constraint languages like ShEx. On the other hand, these two technologies are not contradictory, and they can be used together in a common framework to serve the targets of each. Moreover, even if it was hard to use OWL as a constraint language, its ability to express constraint makes it interesting to further characterise the intersection of the respective expressive powers of ShEx and OWL.

In situations where both ShEx and OWL are deployed in a common framework, it becomes necessary to consider the problem of query containment from the point of view of the combination of both technologies. Gathering there constraints together is important, because these becomes the whole set of constraints, and their combination may produce more containment cases. Keeping these constraints separate means that we are losing semantics at some place.

In this context, it may be worth explaining the following research questions:

• How can we define the intersections between ShEx and OWL (intersections in terms of expressive power)?

• How can we process the expressive power intersections between ShEx and OWL to serve SPARQL query containment?

• Although it is hard to express ShEx constraints in OWL, is it possible at the first place for the whole ShEx fragment?

• If it is possible to express all ShEx constraints in OWL, is it worth doing it? side of it. We therefore deduce that the previous query Q is equivalent to another query Q without an OPT pattern.

Q : {?x :name ?n. ?x :phone ?p}

It is known from [START_REF] Pérez | Semantics and complexity of sparql[END_REF] that the evaluation of the AND-OPT fragment is in Π P 2 while the evaluation of the BGP fragment is in PTIME. This means that Q evaluation can be optimized by evaluating Q which is equivalent to it in the context of the ShEx constraints.

One interesting perspective for further work would be to study the following research questions:

• How to leverage the full potential of ShEx constraints:

1. in order to obtain SPARQL query transformations of different types?

1 Contents 1 . 1

 111 Introduction Motivation and Objectives . . . . . . . . . . . . . . . . . . . . . . . .

1. 2

 2 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Part I -State-of-the-Art . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Part II -Contribution I . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Part III -Contribution II . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Semantic Web Layer Cake Source: https://www.w3.org/TR/2014/NOTE-rdf11-primer-20140624/

2 . 1 :Figure 2 . 1 :

 2121 Figure 2.1: RDF graph example Source: https://www.w3.org/TR/2014/NOTE-rdf11-primer-20140624/

Figure 2 .

 2 Figure 2.2 shows datasets that are published in Linked Data format and are interlinked with other datasets in the cloud.

Figure 2 . 2 :

 22 Figure 2.2: The LOD cloud diagram Source: http://lod-cloud.net/ (Last updated: 2017-02-20)

  . Turtle family of RDF languages (N-Triples, N-Quads, Turtle and TriG) 2. RDF/XML (XML syntax for RDF) 3. JSON-LD (JSON-based RDF syntax) 4. RDFa (for HTML and XML embedding) Since the semantics of RDF is based on assigning IRIs to the RDF terms, the concrete syntaxes also explicitly use IRI definitions for the non-literal nodes of an RDF graph. The example of Fig. 2.1 is annotated with IRIs and is shown in Fig. 2.3. The examples of the concrete syntaxes in this section are based on this annotation.

Figure 2 . 3 :Listing 2 . 2 :

 2322 Figure 2.3: RDF graph example Source: https://www.w3.org/TR/2014/NOTE-rdf11-primer-20140624/

Figure 3 . 1 :

 31 Figure 3.1: SPARQL query matching

Figure 3 . 2 :

 32 Figure 3.2: Pattern tree example

Listing 4 . 1 :

 41 Simple ShEx example

Figure 4 .

 4 Figure 4.1 shows some ShEx validation examples simple RDF graphs.

Figure 4 . 1 :

 41 Figure 4.1: ShEx validation examples

2 :

 2 ShExC: Exclusive Or example. Source: https://github.com/labra/ShExcala/ wiki/ShExC-vs-SHACL

Figure 4 . 2 :

 42 Figure 4.2: A graphical representation of the RDF graph for the example where green dashed lines indicate RDF-entailed triples and red dashed lines indicate triples that are also RDFS-entailed. Source: https://www.w3.org/TR/sparql11-entailment/ Note: This is a modified version of the original figure in the source, since it was reported as an erratum.

Figure 6 . 1 :

 61 Figure 6.1: An example benefit for query containment

Figure 7 . 1 : 2

 712 Figure 7.1: SPARQL query evaluation complexity summary

Figure 7 . 2 :

 72 Figure 7.2: Grouped intermediate results[START_REF] Papailiou | H2RDF+: High-performance distributed joins over large-scale RDF graphs[END_REF]

Figure 7 . 3 :

 73 Figure 7.3: Join on grouped intermediate results[START_REF] Papailiou | H2RDF+: High-performance distributed joins over large-scale RDF graphs[END_REF]

1 3 :

 3 foaf : knows rdfs : domain foaf : Person 2 foaf : knows rdfs : range foaf : Person Listing 7.1: RDFS Example RDFS entailment rules that is applied for rdfs:domain and rdfs:range can be expressed in FOL as follows: ϕ d := ∀p, c, x, y(T (p, rdf s:domain, c), T (x, p, y) → T (x, rdf :type, c)) ϕ r := ∀p, c, x, y(T (p, rdf s:range, c), T (x, p, y) → T (y, rdf : type, c)) Now consider the SPARQL query of Listing 7.2.The optimization suggested for this query is by eliminating the 2 nd and the 3 rd triple patterns. The query of Listing 7.2 is logically equivalent to the query of Listing 7.3 and will return the same results according to the RDFS constraints. SPARQL query example (optimized)

Figure 7 . 4 :

 74 Figure 7.4: Query response times with WatDiv1k[START_REF] Graux | SPARQLGX in action: Efficient distributed evaluation of SPARQL with apache spark[END_REF]

Figure 8 . 1 :

 81 Figure 8.1: Containment Procedure Diagram

Figure 8 . 2 :

 82 Figure 8.2: Pattern tree example (well-designed OPT pattern in normal form)

Theorem 8 . 5 . 3 .

 853 Containment with ShEx for the well-designed OPT SPARQL fragment extended with top level UNION is Π P 2 -complete.

  Figure A.1 and the schemas used in our benchmark are presented in Figure A.2. The expected (valid) results are shown in Table

Figure 9 . 1 :

 91 Figure 9.1: Containment Procedure Diagram by Encoding to FOL

  <Product> { :name xsd:string , :expiryDate xsd:date ? , :producer xsd:string * , :feature xsd:string }

  y and ?x, ?y ∈ S δ(S, C) = ¬equal(x, y) , if C is ?x =?y and ?x, ?y ∈ S δ(S, C) = equal(x, any) , if C is bound(?x) and ?x ∈ S -Finally: δ(S, C) = δ(S, C) ∪ {equal(x, any) |?x is not in C and ?x ∈ S}

  s, p, o) | {s, p, o} ∈ P } ∧ ( {α(S) | S ∈ Γ(P F ILT ER C empty )}) where: α(S) = {c | c ∈ S} A(P OP T P 1 OP T..OP T P n ) ≡ A(P ) ∨ (A(P ) ∧ (A(P 1 ) ∨ ... ∨ A(P n )))

Fig. B. 2 .

 2 The variable names in the queries are hand-crafted to indicate a schema type from the schema of Fig. B.1 (?d: DataSet, ?s: Slice, ?o: Observation, ?c: Country, ?comp: Computation, ?i: Indicator, ?org: Organization). The focus of our study is on BGP queries, and thus all of them are within this fragment. The queries of Fig. B.2 are given in their optimized form i.e.

Figure 10 . 1 :

 101 Figure 10.1: Comparing ranking-optimized query evaluation with other systems (WebIndex data)

10. 6 . 2 . 1

 621 Generated dataUsing the gMark tool, we generated 4 datasets, all according to the LDBC SNB schema (check the schema in Figure B.3 and the corresponding well-formed shape relation graph in Figur B.4). The tool allows users to define the dataset size by indicating the number of nodes to be generated, in our case 5M, 30M, 50M, and 100M nodes scenarios are used, corresponding to about 11M, 67M, 113M, and 227M RDF triples respectively.

Figure 10 . 2 :Figure 10 . 3 :Figure 10 . 4 :Figure 10 . 5 :

 102103104105 Figure 10.2: Comparing ranking-optimized query evaluation with other systems (SNB data 5M nodes)

11. 2 . 1

 21 SPARQL Containment with the mixture of ShEx and OWL

2 .Figure B. 1 :Figure B. 4 :

 214 Figure B.1: Shape relation graph (WebIndex)

  If G is an RDF graph, we use I(G), L(G) and B(G) to respectively denote the set of IRIs, Literals and Blank nodes that appear in at least one triple of G.As RDF graphs are sets of triples, they can be combined easily, supporting the use of data from multiple sources. Nevertheless, it is sometimes desirable to work with multiple RDF graphs while keeping their contents separate. RDF datasets support this requirement.

• The subject s ∈ I ∪ B • The predicate p ∈ I • The object o ∈ I ∪ L ∪ B An RDF triple is usually written in the order (s, p, o), like in the W3C recommendations for RDF concrete syntaxes. Definition 2.2.3 (RDF graph). An RDF graph is a finite set of RDF triples. Definition 2.2.4 (RDF dataset). An RDF dataset is a collection of RDF graphs, and comprises:

Table 2 . 1 :

 21 RDF-compatible XSD types

		Datatype	Value space (informative)
		xsd:string	Character strings (but not all Unicode character strings)
	Core types	xsd:boolean xsd:decimal	true, false Arbitrary-precision decimal numbers
		xsd:integer	Arbitrary-size integer numbers
	IEEE floating-point numbers	xsd:double xsd:float	64-bit floating point numbers incl. +-Inf, +-0, NaN 32-bit floating point numbers incl. +-Inf, +-0, NaN
		xsd:date	Dates (yyyy-mm-dd) with or without timezone
	Time and date	xsd:time xsd:dateTime	Times (hh:mm:ss.sss. . . ) with or without timezone Date and time with or without timezone
		xsd:dateTimeStamp	Date and time with required timezone
		xsd:gYear	Gregorian calendar year
		xsd:gMonth	Gregorian calendar month
		xsd:gDay	Gregorian calendar day of the month
	Recurring and partial dates	xsd:gYearMonth xsd:gMonthDay	Gregorian calendar year and month Gregorian calendar month and day
		xsd:duration	Duration of time
		xsd:yearMonthDuration Duration of time (months and years only)
		xsd:dayTimeDuration	Duration of time (days, hours, minutes, seconds only)
		xsd:byte	-128?+127 (8 bit)
		xsd:short	-32768. . . +32767 (16 bit)
		xsd:int	-2147483648. . . +2147483647 (32 bit)
		xsd:long	-9223372036854775808. . . +9223372036854775807 (64 bit)
		xsd:unsignedByte	0. . . 255 (8 bit)
	Limited-range integer numbers	xsd:unsignedShort xsd:unsignedInt	0. . . 65535 (16 bit) 0. . . 4294967295 (32 bit)
		xsd:unsignedLong	0. . . 18446744073709551615 (64 bit)
		xsd:positiveInteger	Integer numbers >0
		xsd:nonNegativeInteger Integer numbers ?0
		xsd:negativeInteger	Integer numbers <0
		xsd:nonPositiveInteger	Integer numbers ?0
	Encoded binary data	xsd:hexBinary xsd:base64Binary	Hex-encoded binary data Base64-encoded binary data
		xsd:anyURI	Absolute or relative URIs and IRIs
		xsd:language	Language tags per [BCP47]
		xsd:normalizedString	Whitespace-normalized strings
	Miscellaneous XSD types	xsd:token	Tokenized strings
		xsd:NMTOKEN	XML NMTOKENs
		xsd:Name	XML Names
		xsd:NCName	XML NCNames

  http :// example . org / bob # me > < http :// www . w3 . org /1999/02/22 -rdf -syntax -ns # type > < http :// xmlns . com / foaf /0.1/ Person > < http :// example . org / bob > . < http :// example . org / bob # me > < http :// xmlns . com / foaf /0.1/ knows > < http :// example . org / alice # me > < http :// example . org / bob > . < http :// example . org / bob # me > < http :// schema . org / birthDate > "1990 -07 -04"^^< http :// www . w3 . org /2001/ XMLSchema # date > < http :// example . org / bob > . < http :// example . org / bob # me > < http :// xmlns . com / foaf /0.1/ topic_interest > < http :// www . wikidata . org / entity / Q12418 > <

	http :// example . org / bob > .
	< http :// www . wikidata . org / entity / Q12418 > < http :// purl . org / dc / terms / title > " Mona Lisa " < https :// www . wikidata . org /
	wiki / Special : EntityData / Q12418 > .
	< http :// www . wikidata . org / entity / Q12418 > < http :// purl . org / dc / terms / creator > < http :// dbpedia . org / resource /
	Leonardo_da_Vinci > < https :// www . wikidata . org / wiki / Special : EntityData / Q12418 > .
	< http :// data . europeana . eu / item /04802/243 F A

. It is simply an XML syntax for RDF graph encoding. An example in RDF/XML syntax is given in Listing 2.6. <

Table .

 .

4.1 gives the ShEx vocabulary with simple examples.

Table 4 . 1 :

 41 ShEx Vocabulary Source: https://www.w3.org/2001/sw/wiki/index.php?title=ShEx&oldid=5008

	Feature	Example	Description
			Matching a Predicate to a NameClass
	NameTerm	ex:state	The predicate of any matching triple is the same as the NameTerm IRI.
	NameStem	ex:~	The predicate of any matching triple starts with the IRI.
			A matching triple has any predicate except those
	NameAny	. -rdf:type -ex:~	terms NameTerms or NameStems excluded by the
			'-' operator.
			Matching an Object to a ValueClass
	ValueType	xsd:dateTime	The object of any matching triple is the same as the ValueType IRI.

ValueSet

(ex:unassigned ex:assigned) The object of any matching triple is one of the list of triples in the ValueSet.

ValueStem ex:~

The object of any matching triple starts with the IRI.

Table 5 . 1 :

 51 Survey on the decidable FOL fragments Decidable

FOL Fragment (description)

		allowed/ arity	Functions	arity	Predicate	# of vars	quantifiers	Counting	allowed	(In)equality	property	Finite model	property	Tree model
	FOL guarded fragment			∞	∞					
	The fragment with only guarded quantification:												(g)
	∀ 𝑦 𝛼 𝑥, 𝑦 → 𝜑 𝑥, 𝑦
	and
	∃ 𝑦 𝛼 𝑥, 𝑦 ∧ 𝜑 𝑥, 𝑦
	where guards 𝛼: atomic formulae containing all free
	variables of 𝜑.
	SAT(FOL): 2EXPTIME-complete
	SAT(FOL): EXPTIME-complete for formulae of
	bounded width.
	References (with equality): [Ganzinger 1999]
	FOL with only 2 variables (L 2 )			∞	2				
	SAT(FOL): NEXPTIME-complete
	References: [Vardi 1997]
	FOL with only 2 variables (C 2 )			∞	2		
	Is an extension of (L 2 ) with counting quantifiers
	References: [Baader 2002]
	Monadic predicate logic	1	1	∞				
	The fragment in which all relation symbols in the
	signature are monadic (that is, they take only one
	argument)
	References: [Löwenheim 1915], [Kalmár 1929]
	References (with equality): [Bachmair 1993]
	The prefix class (∃ References:[Ackermann 1928], [Gurevich 1973]		∞	∞ 	
	References (with equality): [Fermuller 1993]
	The prefix class (∃ ∞	∞
	The prefix class (∃ * )		∞	∞ 	
	References: [Gurevich 1976]
	Propositional Modal Logic											
	-Is a fragment of the (guarded fragment)
	-Is a fragment of the (2 variable fragment L 2 )
	SAT(FOL): PSPACE-complete
	References: [Hustadt 2000]

* ∀ * ) References: [Bernays, Schönfinkel 1928], [Ramsey 1932] ∞ ∞  

The prefix class (∃ * ∀∃ * ) * ∀ 𝟐 ∃ * )

References:

[Gödel 1932

],

[Kalmár 1933

],

[Schütte 1934]

  humen are created equal . John is a human . John got an F grade . % There is someone ( a human ) who got an A grade . An A grade is not % equal to an F grade . Grades are not human . Therefore there is a % human other than John .

	fof ( all_created_equal , axiom ,(
	! [ H1 , H2 ] :
	( ( human ( H1 )
	& human ( H2 ) )
	= > created_equal ( H1 , H2 ) ) ) ) .
	fof ( john , axiom ,(
	human ( john ) ) ) .
	fof ( john_failed , axiom ,(
	grade ( john ) = f ) ) .
	fof ( someone_got_an_a , axiom ,(
	? [ H ] :
	( human ( H )
	& grade ( H ) = a ) ) ) .
	fof ( distinct_grades , axiom ,(
	a != f ) ) .
	fof ( grades_not_human , axiom ,(
	! [ G ] : ~human ( grade ( G ) ) ) ) .
	fof ( someone_not_john , conjecture ,(
	? [ H ] :
	( human ( H )

Table 6 . 1 :

 61 Query containment complexity results from the literature

	Features

  The indexing scheme used by H 2 RDF+ HBase. HBase is a distributed, NoSQL key-value store that can handle large amounts of data. H 2 RDF+ uses an HBase table for each index.

It uses IDs instead of IRIs and long literals, and keep two separate HBase tables that work as dictionaries to translate string values to IDs and vice versa. The indexes generated by H 2 RDF+ includes information about the count of combinations of each two terms occurring together as s-p, s-o, and o-p. It also includes the average of the count of the third term that occurs in RDF triples.

Definition 8.3.2. Given

two sets of RDF triples D 1 and D 2 and a ShEx schema S, we say that D 2 is a complement of D 1 w.r.t. S, if: 1. D 1 ⊆ D 2 2. D 2 is valid w.r.t. S Definition 8.3.3. Given a ShEx schema S, the minimals discarding ShEx schema of S is given by the function MIN 0 (S), and is defined by replacing all minimal cardinality constraints of S by zeros. (i.e. all cardinality constraints [m, n], + and 1 respectively, are replaced with [0, n], * and ? (optional) respectively).

Table 8 .1: Containment complexity

 8

	SPARQL Fragment	Without(ShEx)	With(ShEx)
	BGP	[Chandra, 1977] NPTIME-Complete NPTIME-Complete
	AND-OPT	[Pichler, 2014] NPTIME-Complete NPTIME-Complete
	AND-OPT-(UNION)	[Pichler, 2014] Π P 2 -Complete	Π P 2 -Complete

Table 8 . 2 :

 82 Experiment containment results

	No Schema S1 S2 S3 S4
	Q1a Q1b
	Q2a Q2b
	Q3a Q3b
	Q4a Q4b
	Q5a Q5b

Table 8 . 3 :

 83 Containment execution results with respect to different stages original problem of containment is required. In the next chapter we show how query containment with ShEx can be encoded into an FOL satisfiability problem. The encoding of the problem with FOL allows for further extensions in the SPARQL fragment considered to include the FILTER, MINUS, and the property path patterns features.

	Cont.	Queries	Con.	Total
	without Transformation with	(Valid+Con.)
	Schema Time	Schema (ms)
	(ms)	(ms)	(ms)
	QaQb1:S1 45	723	44	767
	QaQb1:S2 45	714	42	756
	QaQb1:S3 45	738	41	779
	QaQb1:S4 45	724	42	766
	QaQb2:S1 51	837	53	890
	QaQb2:S2 51	851	52	903
	QaQb2:S3 51	840	57	897
	QaQb2:S4 51	870	53	923
	QaQb3:S1 44	740	44	784
	QaQb3:S2 44	725	43	768
	QaQb3:S3 44	766	44	810
	QaQb3:S4 44	754	44	798
	QaQb4:S1 47	786	43	829
	QaQb4:S2 47	736	0	736
	QaQb4:S3 47	815	45	860
	QaQb4:S4 47	861	45	906
	QaQb5:S1 59	897	57	954
	QaQb5:S2 59	913	57	970
	QaQb5:S3 59	861	47	908
	QaQb5:S4 59	942	53	995

Table 9 . 1 :

 91 Queries encoding time

	Queries encoding time (ms)
	QaQb1 367
	QaQb2 371
	QaQb3 366
	QaQb4 368
	QaQb5 368

Table 9 .2: Schemas encoding time Schemas encoding time (ms)

 9

	Schema 1 25
	Schema 2 25
	Schema 2 25
	Schema 2 25

Table 9 . 3 :

 93 Formula execution time on SPASS

Table 9 . 4 :

 94 Formula execution time on E Theorem Prover

	Formula execution time on E Theorem Prover (ms)
	No Schema S1 S2 S3 S4
	QaQb1 7	8	8	8	8
	QaQb2 10	12 11 12 12
	QaQb3 9	10 10 10 10
	QaQb4 11	12 12 13 13
	QaQb5 15	18 17 18 17

Table 9 .5:

 9 Comparing the upper bound complexities of the two different containment methods for the supported fragments

		Method from Chap. 8 Method from Chap. 9 (FOL)
	SPARQL Fragment	Without/With(ShEx)	Without/With(ShEx)
	BGP	NP	NEXP
	AND-OPT	NP	NEXP
	AND-OPT-(UNION)	Π P 2	NEXP
	AND-OPT-(UNION)-Minus	[not supported]	NEXP
	AND-OPT-(UNION)-FILTER	[not supported]	NEXP
	AND-OPT-(UNION)-PP	[not supported]	NEXP
	AND-OPT-(UNION)-MINUS-FILTER-PP	[not supported]	NEXP

  Definition 10.2.1. Given a shape expression e, an edge label p and a ShEx shape s. The inclusion relation (p, s) ∈ e is defined inductively as follows: • (p, s) ∈ e if e = (p, s) • (p, s) ∈ e if e = e + 1 and (p, s) ∈ e 1 • (p, s) ∈ e if e = e 1 | e 2 , and (p, s) ∈ e 1 or (p, s) ∈ e 2 • (p, s) ∈ e if e = e 1 || e 2 , and (p, s) ∈ e 1 or (p, s) ∈ e 2

  Definition 10.2.2. Given a shape expression e, an edge label p and a ShEx shape s, we say that the atomic shape expression (p, s) is optional in e, written as (p, s) ∈ opt e if: • e = e 1 | e 2 and (p, s) ∈ e 1 and (p, s) ∈ e 2 , OR • e = e 1 | e 2 and (p, s) ∈ e 1 and (p, s) ∈ e 2 , OR • e = e 1 | e 2 and (p, s) ∈ opt e 1 or (p, s) ∈ opt e 2 , OR • e = e 1 || e 2 and (p, s) ∈ opt e 1 and (p, s) ∈ opt e 2 , OR

	• e = e + 1 and (p, s) ∈ opt e 1
	10.3 Well-Formed Data-Schema Pairs

  As it is evident from Example 10.3.1, the well-formation cardinality rule tries to avoid the usage of positive and Kleene closures (+, * ). Formally, the semantics of the two proposed schemas are different. Schema proposition 1 is more restrictive. Schema proposition 2 misses the restriction that a student should belong to 1 and only 1 school, although it is still an acceptable schema even if this restriction is inherent in the data.

	10.3.1 Cardinality Constraints
	Example 10.3.1. Assume we want to model a schema describing the relation between
	students and schools. If we know that the relation in the data between schools and students
	will be 1-to-many, then the following two schema examples are legitimate, but only the first
	one is well-formed w.r.t. the data.
	Schema proposition 1: (Well-Formed)
	<Student> { :name xsd:string , :school @<School> }
	<School> { :name xsd:string }
	Schema proposition 2: (Not Well-Formed)
	<Student> { :name xsd:string }
	<School> { :name xsd:string , :student @<Student> * }

  In Example 10.3.2, Schema proposition 2 will not allow us to determine the relative quantity of Student instances to those of Establishment instances in the data, while with Schema proposition 1 we are sure that the quantity of Student instances are more than that of School instances (and similarly between Researcher and Company ).

	Schema proposition 2: (Not Well Formed)
	<Student> { :name xsd:string , :school @<Establishment> }
	<Researcher> { :name xsd:string , :company @<Establishment> }
	10.3.2. Assume we want to model a schema describing the relation between
	students and researchers to their corresponding schools and research companies. Knowing
	that schools are not research companies, then the following two schema examples are legitimate,
	but only the first one is well formed w.r.t. the data.
	Schema proposition 1: (Well Formed)
	<Student> { :name xsd:string , :school @<School> }
	<Researcher> { :name xsd:string , :company @<Company> }

  InExample 10.3.3, :schoolA is isolated, and thus the data-schema pair are not rankingdeterministic.

	Example 10.3.3. Assume we have a schema describing the relation between students and
	schools, and a set of data as described below.
	Schema proposition:
	<Student> { :name xsd:string , :school @<School> }
	<School> { :name xsd:string }
	RDF data:
	:schoolA :name "School example isolated"
	:schoolB :name "School example unisolated"
	:student1 :name "Alice"
	:student2 :name "Bob"
	:student3 :name "Alain"
	:student4 :name "Marion"
	:student1 :school :schoolB
	:student2 :school :schoolB
	:student3 :school :schoolB
	:student4 :school :schoolB

  Definition 10.4.1 (Shape Relation Graph). Given a ShEx document S, we define a shape relation graph G = SRG(S) as a tuple (N, E) of set of nodes N , each corresponding to a ShEx shape, and a labelled directed relation E between nodes such that:• E(n 1 , x, n 2 ) defines an edge from n 1 to n 2 labelled with x. • Given any two nodes n 1 , n 2 ∈ N , and any predicate p, then E(n 1 , p, n 2 ) if and only if (p, n 2 ) ∈ δ(n 1 ) and (p, n 2 ) ∈ opt δ(n 1 ) • Given any two nodes n 1 , n 2 ∈ N , and any predicate p, then E(n 1 , p opt , n 2 ) if and only if (p, n 2 ) ∈ opt δ(n 1 ) Figure B.1 (appendix) shows the shape relation graph of a real life schema used in our experimentation (Section 10.6). User-defined types are shown as ovals while built-in types (like xsd:string) and IRIs are shown as rectangles. For visualization reasons, we also replicate some type nodes in the mentioned figure.

10.5

. A shape relation graph is a graphical representation focusing only on the relations existing between shapes in a ShEx document, discarding cardinalities.

We define the set of root nodes of a shape relation graph.

Definition 10.4.2. Given a shape relation graph G(N, E), we define R(G) as the set of all root nodes of G. A node s ∈ N is considered a root node if and only if it has no incoming edges in G.

We also define the set of cycles of a shape relation graph. Definition 10.4.3. Given a shape relation graph G(N, E), we define C(G) as the set of all cycles in G. A cycle is a subgraph of shape relation graph. A subgraph C(N C , E C ) of G is a cycle if and only if the set of edges E C defines a directed path that starts and ends with the same node n ∈ N , and N C is the set of all nodes that can be visited by the set of edges E C , where |N C | = |E C |.

  Generated datawiGen is a generator of random data that can be used to benchmark RDF schema languages. The data model used by it is inspired by the WebIndex data, which are data intended as a measure of the World Wide Web's contribution to social, economic and political progress in countries across the world [World WideWeb Foundation, 2014]. The ShEx schema utilised by wiGen is represented as a shape relation graph in Fig. B.1.

	10.6.1.1

Resource Description Framework (RDF)

In SPARQL, a query variable is marked by the use of either "?" or "$"; the "?" or "$" is not part of the variable name. In a query, $abc and ?abc identify the same variable.

Schema and Ontology Languages for RDF

Acknowledgments

First of all, I would like to thank l'Université Grenoble Alpes and l'Ecole Doctorale Mathématiques, Sciences et Technologies de l'Information, Informatique that gave me the opportunity to be enrolled as a PhD student, and financed my stay in France for 3 years. I want to express my gratitude to my supervisors Dr. Nabil Layaïda, Dr. Pierre Genevès, and Prof. Cécile Roisin for their support, constructive remarks, and continuous sharing of knowledge and expertise along this work. I would not forget to thank Prof. Jérôme Euzenat who was already available to help, and his supervision during my internship was a great launch and motivation for my research career.

I thank Inria Grenoble Rhône-Alpes for providing a very causal and comfortable working atmosphere.

I thank my colleagues that I have met during the 3 years, and of course I thank my family and friends for their great support all the time.

Finally, the warmest acknowledgment is for the French community which accepted my presence, and helped me at work, and outside work.

Contents

List of Figures xi

Part I

State-of-the-Art 10. Selectivity Estimation for SPARQL Triple Patterns queries [Graux et al., 2016a]. In our experiment we show how the application of our technique further decreases the average run time for SPARQLGX in the presence of a ShEx document.

SPARQLGX, in the current state, has a basic triple pattern ordering strategy that is based on grouping triple patterns with common join variables together. This ordering is not deterministic for a set of triple patterns; it also depends on their initial ordering given by the input SPARQL query. In our experiments we show that this ordering itself is important for obtaining improved results, yet we show that using our ranking strategy based on the ShEx information further improves the results.

We define 3 systems that are included in our experiment as follows:

• S1: Is SPARQLGX with its ordering strategy turned off (the system itself provides a configuration that stops reordering triple patterns and keeps the original ordering of the query triple patterns).

• S2: Is SPARQLGX with its ordering strategy turned on.

• Optimized: Is an extension of SPARQLGX. It extends it with the application of our ordering strategy based on the ShEx information.

Results

The results of our query evaluations are presented in Figure 10.1 which is explained as follows:

• The blue area is the runtime range of system S2 concerning the different permutations of each test query.

• avg(S2) marks the average runtime of all the permutations of each test query with system S2.

• avg(S1) marks the average runtime of all the permutations of each test query with system S1.

• Finally, the green bars shows the runtime of each input query with our optimized system that has a single deterministic triple patterns ordering for each test query.

For each query run we set an evaluation timeout of 200 seconds. Some queries times out, and the query run time is considered 200 seconds for calculating the average. In our given chart if the average is shown to be 80 seconds (the top of the chart), then this means it is ≥ 80 seconds.

We notice that we don't show the runtime range of the queries with system S1 (as done with system S2) since there are always input permutations that times out for the considered test queries, and thus we only show the average for this system.

The average of the improvement of query executions by our system (Optimized) compared to avg(S2) ranged between 3.7% and 18%. The mean improvement of all test queries

RDF Distributed Data ShEx Validation

The ShEx validation semantics are well defined for single source RDF graph. Yet there exist many RDF storage systems where data are distributed [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF], Graux et al., 2016a]. Such systems are acquiring increased importance as the databases are growing in size, and the need to handle these large amounts becomes essential. They provide optimized storage and retrieval methods.

In this context it is important to define a validation procedure for these situations.

• Can we find a distributed algorithm for handling distributed data validation with ShEx?

• If the process should be applied in a series (one machine after the other), what is the amount of information that should be transferred within the process? And how can we represent it?

We should even be more aware about the fact that most distributed storage systems keeps replicates of the data.

• How to avoid constraint violations due to data replicates?

All these aspects are implementation dependent (for eg. vertical partitioning versus horizontal partitioning). Yet it is interesting to find a global approach that takes the distribution scheme as an input, and handles the validation problem accordingly.

SPARQL Optimization by Transformations with ShEx

In Chapter 10 we proposed a method for optimizing SPARQL query evaluation based on triple patterns ranks that are retrieved with the help of the ShEx definitions. Yet other options for such optimization may be inferred from the ShEx document.

In Chapter 8 we provided a query transformation procedure that we use for the containment problem solving. One of the transformations defined can be considered itself an optimization procedure, where in that transformation some OPT operators are transformed into AND operators. To recall, consider the following query:

Listing A.3: Schema 3: Encoding into FOF TPTP Syntax as Axioms

Listing A.