Abdullah Abbas

Pierre Genevès

Cécile Roisin

Nabil Layaïda

Selectivity Estimation for SPARQL Triple Patterns with Shape Expressions

Keywords: SPARQL evaluation, ShEx, Shape Expressions, RDF constraints

ShEx (Shape Expressions) is a language for expressing constraints on RDF graphs. In this work we optimize the evaluation of conjunctive 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. We first define a set of well formed ShEx schemas, that possess interesting characteristics for SPARQL query optimization. We then define our optimization method by exploiting information extracted from a ShEx schema. We finally report on evaluation results performed showing the advantages of applying our optimization on the top of an existing state-of-the-art query evaluation system.

INTRODUCTION

The Shape Expressions (ShEx) language [START_REF] Prud'hommeaux | Shape Expressions: An RDF Validation and Transformation Language[END_REF] allows to describe constraints on RDF graph structures [START_REF] Schreiber | RDF 1.1 Primer[END_REF]. These descriptions identify predicates and their associated cardinalities and datatypes. ShEx shapes can be used to validate RDF documents, generate RDF documents, or communicate expected graph patterns associated with some process or interface.

In this work we investigate how the evaluation of SPARQL queries [START_REF] Seaborne | SPARQL 1.1 Query Language[END_REF] on big RDF graphs 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, especially in the context of big data structures and the increased attention to its applications. 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 that aim 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 1 with 3 triple patterns and a join on the variable ?𝑥.

SELECT ? x WHERE { ? x : p1000 : a . ? x : p700 : b . ? x : p1 : c . }

Listing 1: SPARQL query example

Assume that we know that the triple with predicate : 𝑝1000 will return 1000 values for ?𝑥, that of : 𝑝700 will return 700, and that of : 𝑝1 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 pattern 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.

Contribution. 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 [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]. SPARQLGX already implements various query optimization techniques including reordering triple patterns [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF], 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.

Outline. The rest of the paper is organized as follows: In Sect. 2 we review the closest related works. In Sect. III we introduce some preliminaries necessary for understanding the rest of the paper. In Sect. IV we define well-formation rules for a data-schema pair that are of interest for our optimization process. In Sect. V we define a graph representation of a ShEx schema. In Sect. VI we formally define our optimization process. In Sect. VII we report on experimental results with our optimization technique. Finally, we conclude in Sect. VIII.

RELATED WORKS

Query optimization for the RDF data model has been studied with various different 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][START_REF] Huang | Scalable SPARQL Querying of Large RDF Graphs[END_REF][START_REF] Lee | Scaling Queries over Big RDF Graphs with Semantic Hash Partitioning[END_REF][START_REF] Neumann | RDF-3X: A RISCstyle Engine for RDF[END_REF][START_REF] Papailiou | H2RDF+: High-performance distributed joins over large-scale RDF graphs[END_REF] 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] Daniel | Scalable Semantic Web Data Management Using Vertical Partitioning[END_REF] (which is already used in SPARQLGX [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]).

The works in [START_REF] Fernández | Binary RDF Representation for Publication and Exchange (HDT)[END_REF][START_REF] Amit | Logical Linked Data Compression[END_REF][START_REF] Pan | Graph Pattern Based RDF Data Compression[END_REF][START_REF] Pham | Deriving an Emergent Relational Schema from RDF Data[END_REF] also provide query optimization techniques, by proposing new data representations that are more compact after scanning the data. Additionally, in [START_REF] Kim | Type-based Semantic Optimization for Scalable RDF Graph Pattern Matching[END_REF][START_REF] Zhang | EAGRE: Towards scalable I/O efficient SPARQL query evaluation on the cloud[END_REF][START_REF] Zou | gStore: Answering SPARQL Queries via Subgraph Matching[END_REF] 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. An important advantage of our approach is that optimizations are computed by analysing only a schema (whose size is much smaller than the actual data); and our optimizations remain valid in the presence of data updates.

For works based on typed data, an approach was proposed in [START_REF] Véronique 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 objectoriented databases is considered. In [START_REF] Schmidt | Foundations of SPARQL Query Optimization[END_REF][START_REF] Serfiotis | Containment and Minimization of RDF/S Query Patterns[END_REF] the authors, as in our work, consider query optimization for typed RDF graphs. These works are mainly oriented towards schema violations. In our work, we mainly assume non-violating queries, and we study the effect of reordering which is not studied in the previous works.

In [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF] 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, but this reordering does not consider the selectivity of triples based on the structure of the RDF data. Their approach scales better than the state-of-the-art systems they compare with [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]. For this reason we implemented and tested our optimization technique on the top of this system. In the experimental part, we compare the results that we obtain with and without our optimizations to the results obtained with SPARQLGX.

A novelty of our work is that it provides a new optimization technique that is based on a simple analysis of a given schema. optimizations hold as long as the data conform to the schema, i.e. possibly at no cost in the presence of updates. Our work could also be applied as a supplement to a wide range of other previously known optimizations techniques like [START_REF] Daniel | Scalable Semantic Web Data Management Using Vertical Partitioning[END_REF][START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF].

DEFINITIONS 3.1 SPARQL

SPARQL is an RDF query language and a W3C Recommendation, where RDF is a directed, labeled graph data format for representing information in the web [START_REF] Lanthaler | RDF 1.1 Concepts and Abstract Syntax[END_REF][START_REF] Schreiber | RDF 1.1 Primer[END_REF]. SPARQL contains capabilities for querying required and optional graph patterns along with their conjunctions and disjunctions [START_REF] Seaborne | SPARQL 1.1 Query Language[END_REF].

A SPARQL graph pattern is defined inductively from triple patterns. Given disjoint infinite sets of IRIs -Internationalised Resource Identifiers -(𝐼), blank nodes (𝐵), literals (𝐿), and variables (𝑉 ), a triple pattern is defined as an instance of (𝐼 ∪𝐵∪𝑉 )(𝐼 ∪𝑉 )(𝐼 ∪𝐵∪𝐿∪𝑉 ) denoted by 𝐼𝐵𝑉 ×𝐼𝑉 ×𝐼𝐵𝐿𝑉 .

In this work we focus on the conjunctive SPARQL fragment, including only BGPs (basic graph patterns), which can be defined abstractly as 𝑞 ::= 𝑡 | 𝑞 𝐴𝑁 𝐷 𝑞 ′ where 𝑡 is a triple pattern.

ShEx

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] Staworko | Complexity and Expressiveness of ShEx for RDF[END_REF]. A Shape Expression has a name and describes the constraints associated with a subject RDF node. For example, Listing 2 shows a definition of a shape in ShEx, where ex:name and ex:phone are predicates and xsd:string is a basic type. This definition means that for an RDF node 𝑛 to satisfy the requirements of Shape1, there must exist two outgoing edges starting from 𝑛 and labeled with predicates ex:name and ex:phone, each one being connected to exactly one object node. The objects corresponding to these predicates must be of type xsd:string. In general, a ShEx document may define several shapes, built with more sophisticated logical operators, which we now define more formally. For a more complete definition of ShEx please refer to [START_REF] Staworko | Complexity and Expressiveness of ShEx for RDF[END_REF]. Given a finite set of edge labels Σ and a finite set of types Γ, we define a shape expression 𝑒 over Σ × Γ as follows:

𝑒 ::= 𝜖 | Σ × Γ | 𝑒 + | (𝑒|𝑒 ′ ) | (𝑒‖𝑒 ′ )
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:

• 𝑒 ? := (𝜖 | 𝑒) (optional)

• 𝑒 * := (𝜖 | 𝑒 + ) (unordered Kleene star)

• 𝑒 [𝑚;𝑛] (𝑒 repeated 𝑖 times with 𝑖 in the interval from 𝑚 to 𝑛) which are also parts of the ShEx syntax. In the sequel we write 𝑎 :: 𝑡 as a shorthand for (𝑎, 𝑡) ∈ Σ × Γ.

A shape expression schema (ShEx), or simply a schema, is a tuple 𝑆 = (Σ, Γ, 𝛿), 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 𝑒 over Σ × Γ. If 𝛿 is not defined for some type 𝑡 ∈ Γ, the default definition is 𝛿(𝑡) = 𝜖.

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 basic built-in type (like xsd:string in the concrete syntaxes of ShEx). [START_REF] Staworko | Complexity and Expressiveness of ShEx for RDF[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 𝐺 = (𝑉, 𝐸) which resembles an RDF graph, and a fixed schema 𝑆 = (Σ, Γ, 𝛿). A typing of 𝐺 w.r.t. 𝑆 is a function 𝜆 : 𝑉 → 2 Γ that associates with every node of 𝐺 a set of types. Next, the conditions that a typing needs to satisfy are identified. Given a typing 𝜆 and a node 𝑛 ∈ 𝑉 we define the neighborhoodtyping of 𝑛 w.r.t. 𝜆 as bag (i.e. multiset) over Σ × 2 Γ as 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑇 𝑦𝑝𝑖𝑛𝑔 𝜆 𝐺 (𝑛) = {|𝑎 :: 𝜆(𝑚) | (𝑛, 𝑎, 𝑚) ∈ 𝐸|}. We note by 𝐿(𝑒) the bag language of a shape expression 𝑒, i.e. 𝐿(𝑒) is the set of bags allowed by the language of 𝑒. Now, 𝜆 is a valid typing of 𝑆 on 𝐺 if and only if every node satisfies the type definitions of its associated type i.e., for every 𝑛 ∈ 𝑉 , 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑇 𝑦𝑝𝑖𝑛𝑔 𝜆 𝐺 (𝑛) ∈ 𝐿(𝛿(𝑡)), for all 𝑡 ∈ 𝜆(𝑛).

Semantics of ShEx

Preliminary Definitions.

In accordance with the aforementioned abstract syntax and semantics, we define the following shape expression inclusion relation which we use in the rest of the paper. Definition 1. Given a shape expression 𝑒, a predicate 𝑝 and a ShEx shape 𝑠. The inclusion relation (𝑝, 𝑠) ∈ 𝑒 is defined inductively as follows:

• (𝑝, 𝑠) ∈ 𝑒 if 𝑒 = (𝑝, 𝑠) • (𝑝, 𝑠) ∈ 𝑒 if 𝑒 = 𝑒 + 1 and (𝑝, 𝑠) ∈ 𝑒1 • (𝑝, 𝑠) ∈ 𝑒 if 𝑒 = 𝑒1 | 𝑒2, and (𝑝, 𝑠) ∈ 𝑒1 or (𝑝, 𝑠) ∈ 𝑒2 • (𝑝, 𝑠) ∈ 𝑒 if 𝑒 = 𝑒1 || 𝑒2, and (𝑝, 𝑠) ∈ 𝑒1 or (𝑝, 𝑠) ∈ 𝑒2
We also define the following shape expression optional condition.

Definition 2. Given a shape expression 𝑒, a predicate 𝑝 and a ShEx shape 𝑠, we say that the atomic shape expression (𝑝, 𝑠) is optional in 𝑒, written as (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒 if:

• 𝑒 = 𝑒1 | 𝑒2 and (𝑝, 𝑠) ̸ ∈ 𝑒1 and (𝑝, 𝑠) ∈ 𝑒2, OR • 𝑒 = 𝑒1 | 𝑒2 and (𝑝, 𝑠) ∈ 𝑒1 and (𝑝, 𝑠) ̸ ∈ 𝑒2, OR • 𝑒 = 𝑒1 | 𝑒2 and (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒1 or (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒2, OR • 𝑒 = 𝑒1 || 𝑒2 and (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒1 and (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒2, OR • 𝑒 = 𝑒 +
1 , and (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒1

WELL FORMED DATA-SCHEMA PAIRS

Using RDF as a data format often raises a number of data modelling issues for which choices must be made. The same information might end up being represented in different ways according to the designer choices. In addition, different point of views might be considered for processing the same graph data, yielding to different sets of constraints for the same information. Thus, different ShEx schemas -all of which correctly and usefully describe different aspects of the same data graph -might be suggested. 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 guarantee 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 makes our shape ranking procedure deterministic. Definition 3 (Well-Formed Data-Schema Pair). A data-schema pair (𝐺, 𝑆) is well-formed if and only if the following rules hold.

(1) Cardinality rule: Every 𝑚-to-𝑛 relation between two schema shapes in 𝑆, where 𝑚 > 𝑛 or 𝑚 is not bound, is modelled from the 𝑚-sided shape to the 𝑛-sided shape.

(2) Shape distinction rule: For every 4 schema shapes 𝑠1, 𝑠2, 𝑠𝑜1, 𝑠𝑜2 ∈ 𝑆 (not necessarily distinct), and for every 2 predicates 𝑝𝑎 and 𝑝 𝑏 (not necessarily distinct), 𝑠𝑜1 and 𝑠𝑜2 are distinct if the following conditions hold:

• (𝑝𝑎, 𝑠𝑜1) ∈ 𝛿(𝑠1) • (𝑝 𝑏 , 𝑠𝑜2) ∈ 𝛿(𝑠2)
• 𝑂1 is the set of nodes of 𝐺 which occur as objects of 𝑝𝑎 whose subject belongs to the shape 𝑠1

• 𝑂2 is the set of nodes of 𝐺 which occur as objects of 𝑝 𝑏 whose subject belongs to the shape 𝑠2

• 𝑂1 ∩ 𝑂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. 6, 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 4 (Ranking-Deterministic Data-Schema Pair). A data-schema pair (𝐺, 𝑆) is ranking-deterministic if and only if the following rules hold.

(1) Well-formedness: (𝐺, 𝑆) is well-formed.

(2) Cardinality rule: There is no closure cardinality (+,*) in 𝑆.

(3) Shape distinction rule: For every 3 shapes 𝑠𝑜, 𝑠1, 𝑠2 ∈ 𝑆 (not necessarily distinct), if there exist 2 predicates 𝑝𝑎 and 𝑝 𝑏 (not necessarily distinct) where (𝑝𝑎, 𝑠𝑜) ∈ 𝛿(𝑠1) and (𝑝 𝑏 , 𝑠𝑜) ∈ 𝛿(𝑠2), then 𝑠1 and 𝑠2 refers to the same shape, and 𝑝𝑎 and 𝑝 𝑏 refers to the same predicate. (4) Data nodes isolation rule: For every data IRI instance 𝑑, every 2 shapes 𝑠1, 𝑠2 ∈ 𝑆, and every predicate 𝑝, if (𝑝, 𝑠2) ∈ 𝛿(𝑠1) and 𝑑 belongs to the shape 𝑠2, then there exists a data IRI instance 𝑑 ′ such that the RDF triple ⟨𝑑 ′ , 𝑝, 𝑑⟩ ∈ 𝐺.

In the following subsections (4.1, 4.2, and 4.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.

Cardinality

Example 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) As it is evident from Example 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.

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 ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩ instances definitely occur in the data more than ⟨𝑆𝑐ℎ𝑜𝑜𝑙⟩ 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. In Example 2, Schema proposition 2 will not allow us to determine the relative quantity of ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩ instances to those of ⟨𝐸𝑠𝑡𝑎𝑏𝑙𝑖𝑠ℎ𝑚𝑒𝑛𝑡⟩ instances in the data, while with Schema proposition 1 we are sure that the quantity of ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩ instances are more than that of ⟨𝑆𝑐ℎ𝑜𝑜𝑙⟩ instances.

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.

SHAPE RELATION GRAPH

In this section we define a shape graph representation that we use to assign ranks to shapes in Sect. 6. A shape relation graph is a graphical representation focusing on the relations existing between shapes in a ShEx document. It is an intermediate structure that will be used later on for selectivity estimation analyses.

Definition 5 (Shape Relation Graph). Given a ShEx document 𝑆, we define a shape relation graph 𝐺 = 𝒮ℛ𝒢(𝑆) as a tuple (𝑁, 𝐸) of set of nodes 𝑁 , each corresponding to a ShEx shape, and an labelled directed relation 𝐸 between nodes such that:

• 𝐸(𝑛1, 𝑥, 𝑛2) defines an edge from 𝑛1 to 𝑛2 labeled with 𝑥. • Given any two nodes 𝑛1, 𝑛2 ∈ 𝑁 , and any predicate 𝑝, then 𝐸(𝑛1, 𝑝, 𝑛2) if and only if (𝑝, 𝑛2) ∈ 𝛿(𝑛1) and (𝑝, 𝑛2) ̸ ∈𝑜𝑝𝑡 𝛿(𝑛1)

• Given any two nodes 𝑛1, 𝑛2 ∈ 𝑁 , and any predicate 𝑝, then 𝐸(𝑛1, 𝑝 𝜖 , 𝑛2) if and only if (𝑝, 𝑛2) ∈𝑜𝑝𝑡 𝛿(𝑛1)

Figure 6 shows the shape relation graph of a real life schema used in our experimentation (Sect. 7). User-defined types are shown as ovals while built-in types (like xsd:string) and IRIs are shown as rectangles.

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

Definition 6. Given a shape relation graph 𝐺(𝑁, 𝐸), we define ℛ(𝐺) as the set of all root nodes of 𝐺. A node 𝑠 ∈ 𝑁 is considered a root node if and only if it has no incoming edges in 𝐺.

We also define the set of cycles of a shape relation graph.

Definition 7. Given a shape relation graph 𝐺(𝑁, 𝐸), we define 𝒞(𝐺) as the set of all cycles in 𝐺. A cycle is a subgraph of shape relation graph. A subgraph 𝐶(𝑁𝐶 , 𝐸𝐶 ) of 𝐺 is a cycle if and only if the set of edges 𝐸𝐶 defines a directed path that starts and ends with the same node 𝑛 ∈ 𝑁 , and 𝑁𝐶 is the set of all nodes that can be visited by the set of edges 𝐸𝐶 .

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 both rankings together.

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. 5. 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 1. Representing it as a shape relation graph, ⟨𝑆𝑐ℎ𝑜𝑜𝑙⟩ is a child of ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩. 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 ⟨𝑆𝑐ℎ𝑜𝑜𝑙⟩ shape a priority ranking, since we know that they occur less than the ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩ 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 means 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. [START_REF] Erling | The LDBC Social Network Benchmark: Interactive Workload[END_REF].

The ranking procedure we propose starts from the root shapes (root nodes as defined in Definition 6). 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.

6.1.1 Schema Graph Adjustment. First, given the shape relation graph 𝐺 of a ShEx schema, we modify it by detecting optional relations and cycles.

(1) For each cycle 𝐶𝑖(𝑁𝑖, 𝐸𝑖) ∈ 𝒞(𝐺):

• For all predicate 𝑝, if there exist nodes 𝑛1, 𝑛2 ∈ 𝑁𝑖 such that there exists an edge 𝐸(𝑛1, 𝑝 𝜖 , 𝑛2), then remove this edge. Let the new resulting graph be 𝐺𝑛𝑜𝑟.

(2) For each cycle 𝐶𝑖(𝑁𝑖, 𝐸𝑖) ∈ 𝒞(𝐺𝑛𝑜𝑟):

• Merge all the nodes 𝑥 ∈ 𝑁𝑖 into a single node 𝑐𝑖.

6.1.2 Schema Shapes Ranking. Now let the output of the Schema Graph Adjustment be 𝐺 𝑎𝑑𝑗 (𝑁, 𝐸). We define the ranking function 𝛿𝑆(𝑥) for all 𝑥 ∈ 𝑁 as follows:

(1) For each node 𝑟 ∈ ℛ(𝐺 𝑎𝑑𝑗 ), 𝛿𝑆(𝑟) = 1 (2) For each node 𝑟 ∈ ℛ(𝐺 𝑎𝑑𝑗 ), apply the procedure 𝑃 (𝑟) defined next.

Given a node 𝑥 ∈ 𝑁 , the procedure 𝑃 (𝑥) is defined as follows:

• For each 𝑠 ∈ 𝑁 , and for each predicate 𝑝 where there exists an edge 𝐸(𝑥, 𝑝, 𝑠)

(1) If 𝛿𝑆(𝑠) is not initialised: 𝛿𝑆(𝑠) = 𝛿𝑆(𝑥) + 1 (2) If 𝛿𝑆(𝑥) + 1 < 𝛿𝑆(𝑠), then 𝛿𝑆(𝑠) = 𝛿𝑆(𝑥) + 1 (3) Apply 𝑃 (𝑠)
Finally, we transmit the cycle rankings to the original nodes.

• For each cycle 𝐶𝑖(𝑁𝑖, 𝐸𝑖) in 𝐺𝑛𝑜𝑟:

-For each node 𝑥 ∈ 𝑁𝑖, 𝛿𝑆(𝑥) = 𝛿𝑆(𝑐𝑖)

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 𝑝 used in the shapes 𝑠1, 𝑠2, . . . , 𝑠𝑛. The ranking of 𝑝 within a shape 𝑠, denoted as 𝛿𝑃 (𝑝, 𝑠) is defined as follows.

𝛿 𝑃 (𝑝, 𝑠) = 𝛿 𝑆 (𝑠) 𝛿 𝑆 (𝑠1) × 𝛿 𝑆 (𝑠2) × • • • × 𝛿 𝑆 (𝑠𝑛) , if 𝑠 ∈ {𝑠1, 𝑠2, . . . , 𝑠𝑛} 𝛿 𝑃 (𝑝, 𝑠) = 1 𝛿 𝑆 (𝑠1) × 𝛿 𝑆 (𝑠2) × • • • × 𝛿 𝑆 (𝑠𝑛) , 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 𝑝 corresponds to only one shape 𝑠𝑚, then the ranking corresponding to it will be always 1, where this value represents the highest ranking possible.

𝛿𝑃 (𝑝, 𝑠𝑚) = 𝛿𝑆(𝑠𝑚) 𝛿𝑆(𝑠𝑚) = 1
On the other hand, the lowest possible ranking is when the predicate 𝑝 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.

𝛿𝑃 (𝑝, 𝑠𝑟𝑜𝑜𝑡) = 1 ∏ ∀𝑖, where 𝑠 𝑖 is a shape 𝛿𝑆(𝑠𝑖)

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 𝑠 occurring in the triple patterns we have a set 𝐶(𝑠) of candidate shapes for 𝑠. For convenience, given a triple pattern 𝑡, we define 𝐶(𝑡) = 𝐶(𝑠) if 𝑠 is a subject of 𝑡. We also define 𝑝(𝑡) as the predicate of the triple 𝑡.

To define the triple ranking function, we use the two ranking functions 𝛿𝑆 and 𝛿𝑃 defined previously.

Given a BGP 𝐵 and a triple pattern 𝑡 ∈ 𝐵, we define the ranking of the triple 𝑡, denoted by 𝛿𝑇 (𝑡), as follows:

𝛿𝑇 (𝑡) = 𝐴𝑣𝑔 [ 𝛿𝑆(𝑆𝑖) × 𝛿𝑃 (𝑝(𝑡), 𝑆𝑖) ] ∀𝑖, 𝑆 𝑖 ∈𝐶(𝑡)
For a given triple 𝑡, the previous function is the average of the product 𝛿𝑆 × 𝛿𝑃 by considering all the possible candidate shapes for the subject of 𝑡.

EVALUATION

We prepared an experiment that proves the soundness of the optimization procedure described in this paper. This experiment uses a real ShEx schema example. We generate data according to the Social Network Benchmark (SNB) schema of the Linked Data Benchmark Council (LDBC) [START_REF] Erling | The LDBC Social Network Benchmark: Interactive Workload[END_REF].

The data and the workload tests 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. . Our experiment demonstrates 4 different datasets of different sizes, thus we show 4 different charts corresponding to the datasets, and therefore allowing to further comment on the effect of the data size.

Generated data

Using the gMark tool, we generated 4 datasets, all according to the LDBC SNB schema (check the schema in Fig. 5 and the corresponding well-formed shape relation graph in Fig. 6).

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.

Workload

Using gMark, we also generated a workload consisting of 12 conjunctive SPARQL queries based on the LDBC SNB schema. We setup the sizes of the 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. The generated queries are given in the appendix (Section C).

Our purpose is to compare, for each query, the evaluation of the optimized triple patterns order resulting from our method with that of counter part queries, which are just equivalent to the optimized ones but with different order of their triple patterns. In our experiment we generate 50 random permutations for each query of the workload.

SPARQLGX

An advantage of our optimization technique is that it can be applied on the top of query systems like SPARQLGX [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]. 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 queries [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]. 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, but the order of the groups themselves is not considered, and thus the 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 following:

• 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. • Optimised: 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 workload query evaluations with the 4 datasets are presented in Figs. 1, 2, 3, and which are 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 optimised system that has a single deterministic triple patterns ordering for each test query.

For each query run we set an evaluation timeout, which is a maximal value result (𝑡𝑡𝑖𝑚𝑒𝑜𝑢𝑡 = 15, 110, 110, and 130 seconds respectively) near the top of each presented results chart. Some queries timeout, and the query run time is considered equivalent to the timeout value for calculating the average. In our given charts if the average is shown to be at the top of the chart, then this means it is ≥ 𝑡𝑡𝑖𝑚𝑒𝑜𝑢𝑡 (timeout value).

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 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 Fig. 1, the optimized orderings of queries Q1, Q10, and Q12 showed a slight improvement. In Fig. 2 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 stabilised.

The average of the improvement of our system (Optimised) 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%.

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.

  xsd : string , ex : phone xsd : string } Listing 2: Sample Shape in ShEx 3.2.1 Abstract Syntax of the Considered ShEx Fragment.

  <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> +}

Example 2 .

 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>} Schema proposition 2: (Not Well Formed) <Student>{:name xsd:string,:school @<Establishment>} <Researcher>{:name xsd:string,:company @<Establishment>}

Figure 1 :

 1 Figure 1: Comparing ranking-optimised query evaluation with other systems (SNB data 5M nodes)

Figure 2 :Figure 3 :

 23 Figure 2: Comparing ranking-optimised query evaluation with other systems (SNB data 30M nodes)

Figure 4 :

 4 Figure 4: Comparing ranking-optimised query evaluation with other systems (SNB data 100M nodes)

Figure 5 :Figure 6 :

 56 Figure 5: Schema (LDBC SNB) Source: https://github.com/ldbc/ldbc snb docs


Abdullah Abbas

Pierre Genevès

Cécile Roisin

Nabil Layaïda

Optimising SPARQL Query Evaluation in the Presence of ShEx Constraints Optimisation de l'évaluation de requêtes SPARQL en présence de contraintes ShEx

Keywords: SPARQL optimisation, SPARQL evaluation, ShEx, Shape Expressions, RDF constraints

ShEx (Shape Expressions) is a language for expressing constraints on RDF graphs. In this work we optimise the evaluation of conjunctive SPARQL queries, on RDF graphs, by taking advantage of ShEx constraints. Our optimisation is based on computing and assigning ranks to query triple patterns, dictating their order of execution. We first define a set of well formed ShEx schemas, that possess interesting characteristics for SPARQL query optimisation. We then define 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é]. Nous nous intéressons dans ce travail à l'optimisation de l'évaluation de requêtes SPARQL conjonctives sur des graphes RDF en présence d'un schema de ShEx (Shape Expressions). ShEx est un langage qui sert à exprimer des contraintes sur les graphes RDF et notre optimisation s'appuie sur ces contraintes pour classer les triple patterns composant la requête. Notre plan optimisé d'exécution de la requête est déduit de ce classement. Dans un premier temps, nous définissons un ensemble de schémas ShEx bien formés possédant des caractéristiques intéressantes pour l'optimisation de requêtes SPARQL. Ensuite, nous introduisons une méthode d'optimisation qui exploite les informations extraites du schéma ShEx. Enfin, nous présentons le résultat de nos expérimentations mettant en évidence les gains de performance obtenus par notre optimisation dans un évaluateur distribué performant.

INTRODUCTION

The Shape Expressions (ShEx) language [START_REF] Prud'hommeaux | Shape Expressions: An RDF Validation and Transformation Language[END_REF] allows to describe constraints on RDF graph structures [START_REF] Schreiber | RDF 1.1 Primer[END_REF]. These descriptions identify predicates and their associated cardinalities and datatypes. ShEx shapes can be used to validate RDF documents, generate RDF documents, or communicate expected graph patterns associated with some process or interface.

In this work 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 or evaluation of subqueries, by taking advantage of the information on the data described in ShEx. While SPARQL query optimisation 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 that aim 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. Optimisation 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 1 with 3 triple patterns and a join on the variable ?𝑥.

Assume that we know that the triple with predicate : 𝑝1000 will return 1000 values for ?𝑥, that of : 𝑝700 will return 700, and that of : 𝑝1 will return 1. The join between the first two SELECT ? x WHERE { ? x : p1000 : a . ? x : p700 : b . ? x : p1 : c . } Listing 1: SPARQL query example 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 pattern 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 optimised execution of the whole query.

Contribution. 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 optimisation method by exploiting information extracted from a ShEx schema. To the best of our knowledge, this is the first work addressing SPARQL query optimisation 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 [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]. SPARQLGX already implements various query optimisation techniques including reordering triple patterns [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF], but without considering schema constraints. We show that our technique further improves the efficiency of query execution times from 5% up to 17%.

Outline. The rest of the paper is organized as follows: In Sect. 2 we review the closest related works. In Sect. 3 we introduce some preliminaries necessary for understanding the rest of the paper. In Sect. 4 we define well-formation rules for a data-schema pair that are of interest for our optimisation process. In Sect. 5 we define a graph representation of a ShEx schema. In Sect. 6 we formally define our optimisation process. In Sect. 7 we report on experimental results with our optimisation technique. Finally, we conclude in Sect. 8.

RELATED WORKS

Query optimisation for the RDF data model has been studied with various different 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][START_REF] Huang | Scalable SPARQL Querying of Large RDF Graphs[END_REF][START_REF] Lee | Scaling Queries over Big RDF Graphs with Semantic Hash Partitioning[END_REF][START_REF] Neumann | RDF-3X: A RISCstyle Engine for RDF[END_REF][START_REF] Papailiou | H2RDF+: High-performance distributed joins over large-scale RDF graphs[END_REF] are based on techniques that mainly focus on join optimisations 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 optimised query processing, is vertical data partitioning [START_REF] Daniel | Scalable Semantic Web Data Management Using Vertical Partitioning[END_REF] (which is already used in SPARQLGX [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]).

The works in [START_REF] Fernández | Binary RDF Representation for Publication and Exchange (HDT)[END_REF][START_REF] Amit | Logical Linked Data Compression[END_REF][START_REF] Pan | Graph Pattern Based RDF Data Compression[END_REF][START_REF] Pham | Deriving an Emergent Relational Schema from RDF Data[END_REF]] also provide query optimisation techniques, by proposing new data representations that are more compact after scanning the data. Additionally, in [START_REF] Kim | Type-based Semantic Optimization for Scalable RDF Graph Pattern Matching[END_REF][START_REF] Zhang | EAGRE: Towards scalable I/O efficient SPARQL query evaluation on the cloud[END_REF][START_REF] Zou | gStore: Answering SPARQL Queries via Subgraph Matching[END_REF] 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. An important advantage of our approach is that optimisations are computed by analysing only a schema (whose size is much smaller than the actual data); and our optimisations remain valid in the presence of data updates.

For works based on typed data, an approach was proposed in [START_REF] Véronique 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 optimisation for objectoriented databases is considered. In [START_REF] Schmidt | Foundations of SPARQL Query Optimization[END_REF][START_REF] Serfiotis | Containment and Minimization of RDF/S Query Patterns[END_REF] the authors, as in our work, consider query optimisation for typed RDF graphs. These works are mainly oriented towards schema violations. In our work, we mainly assume non-violating queries, and we study the effect of reordering which is not studied in the previous works.

In [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF] 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, optimised joins are considered by reordering BGP triple patterns by combining those with common variables, but this reordering does not consider the selectivity of triples based on the structure of the RDF data. Their approach scales better than the state-of-the-art systems they compare with [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]. For this reason we implemented and tested our optimisation technique on the top of this system. In the experimental part, we compare the results that we obtain with and without our optimisations to the results obtained with SPARQLGX.

A novelty of our work is that it provides a new optimisation technique that is based on a simple analysis of a given schema. Optimisations hold as long as the data conform to the schema, i.e. possibly at no cost in the presence of updates. Our work could also be applied as a supplement to a wide range of other previously known optimisations techniques like [START_REF] Daniel | Scalable Semantic Web Data Management Using Vertical Partitioning[END_REF][START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF].

DEFINITIONS 3.1 SPARQL

SPARQL is an RDF query language and a W3C Recommendation, where RDF is a directed, labeled graph data format for representing information in the web [START_REF] Lanthaler | RDF 1.1 Concepts and Abstract Syntax[END_REF][START_REF] Schreiber | RDF 1.1 Primer[END_REF]. SPARQL contains capabilities for querying required and optional graph patterns along with their conjunctions and disjunctions [START_REF] Seaborne | SPARQL 1.1 Query Language[END_REF].

A SPARQL graph pattern is defined inductively from triple patterns. Given disjoint infinite sets of IRIs -Internationalised Resource Identifiers -(𝐼), blank nodes (𝐵), literals (𝐿), and variables (𝑉 ), a triple pattern is defined as an instance of (𝐼 ∪𝐵∪𝑉 )(𝐼 ∪𝑉 )(𝐼 ∪𝐵∪𝐿∪𝑉 ) denoted by 𝐼𝐵𝑉 ×𝐼𝑉 ×𝐼𝐵𝐿𝑉 .

In this work we focus on the conjunctive SPARQL fragment, including only BGPs (basic graph patterns), which can be defined abstractly as 𝑞 ::= 𝑡 | 𝑞 𝐴𝑁 𝐷 𝑞 ′ where 𝑡 is a triple pattern.

ShEx

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] Staworko | Complexity and Expressiveness of ShEx for RDF[END_REF]. A Shape Expression has a name and describes the constraints associated with a subject RDF node. For example, Listing 2 shows a definition of a shape in ShEx, where ex:name and ex:phone are predicates and xsd:string is a basic type. This definition means that for an RDF node 𝑛 to satisfy the requirements of Shape1, there must exist two outgoing edges starting from 𝑛 and labeled with predicates ex:name and ex:phone, each one being connected to exactly one object node. The objects corresponding to these predicates must be of type xsd:string. In general, a ShEx document may define several shapes, built with more sophisticated logical operators, which we now define more formally. For a more complete definition of ShEx please refer to [START_REF] Staworko | Complexity and Expressiveness of ShEx for RDF[END_REF]. Given a finite set of edge labels Σ and a finite set of types Γ, we define a shape expression 𝑒 over Σ × Γ as follows:

𝑒 ::= 𝜖 | Σ × Γ | 𝑒 + | (𝑒|𝑒 ′ ) | (𝑒‖𝑒 ′ )
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:

• 𝑒 ? := (𝜖 | 𝑒) (optional) • 𝑒 * := (𝜖 | 𝑒 + ) (unordered Kleene star) • 𝑒 [𝑚;𝑛] (𝑒 repeated 𝑖 times with 𝑖 in the interval from 𝑚 to 𝑛)
which are also parts of the ShEx syntax. In the sequel we write 𝑎 :: 𝑡 as a shorthand for (𝑎, 𝑡) ∈ Σ × Γ.

A shape expression schema (ShEx), or simply a schema, is a tuple 𝑆 = (Σ, Γ, 𝛿), 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 𝑒 over Σ × Γ. If 𝛿 is not defined for some type 𝑡 ∈ Γ, the default definition is 𝛿(𝑡) = 𝜖. 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). [START_REF] Staworko | Complexity and Expressiveness of ShEx for RDF[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 𝐺 = (𝑉, 𝐸) which resembles an RDF graph, and a fixed schema 𝑆 = (Σ, Γ, 𝛿). A typing of 𝐺 w.r.t. 𝑆 is a function 𝜆 : 𝑉 → 2 Γ that associates with every node of 𝐺 a set of types. Next, the conditions that a typing needs to satisfy are identified. Given a typing 𝜆 and a node 𝑛 ∈ 𝑉 we define the neighborhoodtyping of 𝑛 w.r.t. 𝜆 as bag (i.e. multiset) over Σ × 2 Γ as 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑇 𝑦𝑝𝑖𝑛𝑔 𝜆 𝐺 (𝑛) = {|𝑎 :: 𝜆(𝑚) | (𝑛, 𝑎, 𝑚) ∈ 𝐸|}. We note by 𝐿(𝑒) the bag language of a shape expression 𝑒, i.e. 𝐿(𝑒) is the set of bags allowed by the language of 𝑒. Now, 𝜆 is a valid typing of 𝑆 on 𝐺 if and only if every node satisfies the type definitions of its associated type i.e., for every 𝑛 ∈ 𝑉 , 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑇 𝑦𝑝𝑖𝑛𝑔 𝜆 𝐺 (𝑛) ∈ 𝐿(𝛿(𝑡)), for all 𝑡 ∈ 𝜆(𝑛).

Semantics of ShEx

Preliminary Definitions.

In accordance with the aforementioned abstract syntax and semantics, we define the following shape expression inclusion relation which we use in the rest of the paper. Definition 3.1. Given a shape expression 𝑒, a predicate 𝑝 and a ShEx shape 𝑠. The inclusion relation (𝑝, 𝑠) ∈ 𝑒 is defined inductively as follows:

• (𝑝, 𝑠) ∈ 𝑒 if 𝑒 = (𝑝, 𝑠) • (𝑝, 𝑠) ∈ 𝑒 if 𝑒 = 𝑒 + 1 and (𝑝, 𝑠) ∈ 𝑒1 • (𝑝, 𝑠) ∈ 𝑒 if 𝑒 = 𝑒1 | 𝑒2, and (𝑝, 𝑠) ∈ 𝑒1 or (𝑝, 𝑠) ∈ 𝑒2 • (𝑝, 𝑠) ∈ 𝑒 if 𝑒 = 𝑒1 || 𝑒2, and (𝑝, 𝑠) ∈ 𝑒1 or (𝑝, 𝑠) ∈ 𝑒2
We also define the following shape expression optional condition. Definition 3.2. Given a shape expression 𝑒, a predicate 𝑝 and a ShEx shape 𝑠, we say that the atomic shape expression (𝑝, 𝑠) is optional in 𝑒, written as (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒 if:

• 𝑒 = 𝑒1 | 𝑒2 and (𝑝, 𝑠) ̸ ∈ 𝑒1 and (𝑝, 𝑠) ∈ 𝑒2, OR • 𝑒 = 𝑒1 | 𝑒2 and (𝑝, 𝑠) ∈ 𝑒1 and (𝑝, 𝑠) ̸ ∈ 𝑒2, OR • 𝑒 = 𝑒1 | 𝑒2 and (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒1 or (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒2, OR • 𝑒 = 𝑒1 || 𝑒2 and (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒1 and (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒2, OR • 𝑒 = 𝑒 +
1 , and (𝑝, 𝑠) ∈𝑜𝑝𝑡 𝑒1

WELL FORMED DATA-SCHEMA PAIRS

Using RDF as a data format often raises a number of data modeling issues for which choices must be made. The same information might end up being represented in different ways according to the designer choices. In addition, different point of views might be considered for processing the same graph data, yielding to different sets of constraints for the same information. Thus, different ShEx schemas -all of which correctly and usefuly describe different aspects of the same data graph -might be suggested. 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 guarantee 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 makes our shape ranking procedure deterministic. Definition 4.1 (Well-Formed Data-Schema Pair). A dataschema pair (𝐺, 𝑆) is well-formed if and only if the following rules hold.

(1) Cardinality rule: Every 𝑚-to-𝑛 relation between two schema shapes in 𝑆, where 𝑚 > 𝑛 or 𝑚 is not bound, is modelled from the 𝑚-sided shape to the 𝑛-sided shape. (2) Shape distinction rule: For every 4 schema shapes 𝑠1, 𝑠2, 𝑠𝑜1, 𝑠𝑜2 ∈ 𝑆 (not necessarily distinct), and for every 2 predicates 𝑝𝑎 and 𝑝 𝑏 (not necessarily distinct), 𝑠𝑜1 and 𝑠𝑜2 are distinct if the following conditions hold:

• (𝑝𝑎, 𝑠𝑜1) ∈ 𝛿(𝑠1) • (𝑝 𝑏 , 𝑠𝑜2) ∈ 𝛿(𝑠2)
• 𝑂1 is the set of nodes of 𝐺 which occur as objects of 𝑝𝑎 whose subject is valid w.r.t. the shape 𝑠1. • 𝑂2 is the set of nodes of 𝐺 which occur as objects of 𝑝 𝑏 whose subject is valid w.r.t. the shape 𝑠2.

• 𝑂1 ∩ 𝑂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. 6, without adding new constraints.

Although the well-formation rules are sufficient for optimisation 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 4.2 (Ranking-Deterministic Data-Schema Pair).

A data-schema pair (𝐺, 𝑆) is ranking-deterministic if and only if the following rules hold.

(1) Well-formedness: (𝐺, 𝑆) is well-formed.

(2) Cardinality rule: There is no closure cardinality (+,*) in 𝑆.

(3) Shape distinction rule: For every 3 shapes 𝑠𝑜, 𝑠1, 𝑠2 ∈ 𝑆 (not necessarily distinct), if there exist 2 predicates 𝑝𝑎 and 𝑝 𝑏 (not necessarily distinct) where (𝑝𝑎, 𝑠𝑜) ∈ 𝛿(𝑠1) and (𝑝 𝑏 , 𝑠𝑜) ∈ 𝛿(𝑠2), then 𝑠1 and 𝑠2 refers to the same shape, and 𝑝𝑎 and 𝑝 𝑏 refers to the same predicate. (4) Data nodes isolation rule: For every data IRI instance 𝑑, every 2 shapes 𝑠1, 𝑠2 ∈ 𝑆, and every predicate 𝑝, if (𝑝, 𝑠2) ∈ 𝛿(𝑠1) and 𝑑 belongs to the shape 𝑠2, then there exists a data IRI instance 𝑑 ′ such that the RDF triple ⟨𝑑 ′ , 𝑝, 𝑑⟩ ∈ 𝐺.

In the following subsections (4.1, 4.2, and 4.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. As it is evident from Example 4.3, 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.

Cardinality

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 ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩ instances definitely occur in the data more than ⟨𝑆𝑐ℎ𝑜𝑜𝑙⟩ 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 4.4. 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> } Schema proposition 2: (Not Well Formed) <Student> {:name xsd:string, :school @<Establishment>} <Researcher> {:name xsd:string, :company @<Establishment>} In Example 4.4, Schema proposition 2 will not allow us to determine the relative quantity of ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩ instances to those of ⟨𝐸𝑠𝑡𝑎𝑏𝑙𝑖𝑠ℎ𝑚𝑒𝑛𝑡⟩ instances in the data, while with Schema proposition 1 we are sure that the quantity of ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩ instances are more than that of ⟨𝑆𝑐ℎ𝑜𝑜𝑙⟩ instances.

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.

SHAPE RELATION GRAPH

In this section we define a shape graph representation that we use to assign ranks to shapes in Sect. 6. A shape relation graph is a graphical representation focusing only on the relations existing between shapes in a ShEx document, discarding cardinalities.

Definition 5.1 (Shape Relation Graph). Given a ShEx document 𝑆, we define a shape relation graph 𝐺 = 𝒮ℛ𝒢(𝑆) as a tuple (𝑁, 𝐸) of set of nodes 𝑁 , each corresponding to a ShEx shape, and an labelled directed relation 𝐸 between nodes such that:

• 𝐸(𝑛1, 𝑥, 𝑛2) defines an edge from 𝑛1 to 𝑛2 labeled with 𝑥. We define the set of root nodes of a shape relation graph.

Definition 5.2. Given a shape relation graph 𝐺(𝑁, 𝐸), we define ℛ(𝐺) as the set of all root nodes of 𝐺. A node 𝑠 ∈ 𝑁 is considered a root node if and only if it has no incoming edges in 𝐺.

We also define the set of cycles of a shape relation graph.

Definition 5.3. Given a shape relation graph 𝐺(𝑁, 𝐸), we define 𝒞(𝐺) as the set of all cycles in 𝐺. A cycle is a subgraph of shape relation graph. A subgraph 𝐶(𝑁𝐶 , 𝐸𝐶 ) of 𝐺 is a cycle if and only if the set of edges 𝐸𝐶 defines a directed path that starts and ends with the same node 𝑛 ∈ 𝑁 , and 𝑁𝐶 is the set of all nodes that can be visited by the set of edges 𝐸𝐶 .

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 both rankings together.

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. 5. 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 4.3. Representing it as a shape relation graph, ⟨𝑆𝑐ℎ𝑜𝑜𝑙⟩ is a child of ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩. 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 assumptioneach student has a unique school. It is clear 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 ⟨𝑆𝑐ℎ𝑜𝑜𝑙⟩ shape a priority ranking, since we know that they occur less than the ⟨𝑆𝑡𝑢𝑑𝑒𝑛𝑡⟩ 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 means 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. [START_REF] Erling | The LDBC Social Network Benchmark: Interactive Workload[END_REF].

The ranking procedure we propose starts from the root shapes (root nodes as defined in Definition 5.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.

6.1.1 Schema Graph Adjustment. First, given the shape relation graph 𝐺 of a ShEx schema, we modify it by detecting optional relations and cycles.

(1) For each cycle 𝐶𝑖(𝑁𝑖, 𝐸𝑖) ∈ 𝒞(𝐺):

• For all predicate 𝑝, if there exist nodes 𝑛1, 𝑛2 ∈ 𝑁𝑖 such that there exists an edge 𝐸(𝑛1, 𝑝 𝜖 , 𝑛2), then remove this edge. Let the new resulting graph be 𝐺𝑛𝑜𝑟.

(2) For each cycle 𝐶𝑖(𝑁𝑖, 𝐸𝑖) ∈ 𝒞(𝐺𝑛𝑜𝑟):

• Merge all the nodes 𝑥 ∈ 𝑁𝑖 into a single node 𝑐𝑖.

6.1.2 Schema Shapes Ranking. Now let the output of the Schema Graph Adjustment be 𝐺 𝑎𝑑𝑗 (𝑁, 𝐸). We define the ranking function 𝛿𝑆(𝑥) for all 𝑥 ∈ 𝑁 as follows:

(1) For each node 𝑟 ∈ ℛ(𝐺 𝑎𝑑𝑗 ), 𝛿𝑆(𝑟) = 1 (2) For each node 𝑟 ∈ ℛ(𝐺 𝑎𝑑𝑗 ), apply the procedure 𝑃 (𝑟) defined next.

Given a node 𝑥 ∈ 𝑁 , the procedure 𝑃 (𝑥) is defined as follows:

• For each 𝑠 ∈ 𝑁 , and for each predicate 𝑝 where there exists an edge 𝐸(𝑥, 𝑝, 𝑠)

(1) If 𝛿𝑆(𝑠) is not initialised: 𝛿𝑆(𝑠) = 𝛿𝑆(𝑥) + 1 (2) If 𝛿𝑆(𝑥) + 1 < 𝛿𝑆(𝑠), then 𝛿𝑆(𝑠) = 𝛿𝑆(𝑥) + 1 (3) Apply 𝑃 (𝑠)
Finally, we transmit the cycle rankings to the original nodes.

• For each cycle 𝐶𝑖(𝑁𝑖, 𝐸𝑖) in 𝐺𝑛𝑜𝑟:

-For each node 𝑥 ∈ 𝑁𝑖, 𝛿𝑆(𝑥) = 𝛿𝑆(𝑐𝑖)

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 𝑝 used in the shapes 𝑠1, 𝑠2, . . . , 𝑠𝑛. The ranking of 𝑝 within a shape 𝑠, denoted as 𝛿𝑃 (𝑝, 𝑠) is defined as follows.

𝛿𝑃 (𝑝, 𝑠) = 𝛿𝑆(𝑠) 𝛿𝑆(𝑠1) × 𝛿𝑆(𝑠2) × • • • × 𝛿𝑆(𝑠𝑛) , if 𝑠 ∈ {𝑠1, 𝑠2, . . . , 𝑠𝑛} 𝛿𝑃 (𝑝, 𝑠) = 1 𝛿𝑆(𝑠1) × 𝛿𝑆(𝑠2) × • • • × 𝛿𝑆(𝑠𝑛)
, 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 𝑝 corresponds to only one shape 𝑠𝑚, then the ranking corresponding to it will be always 1, where this value represents the highest ranking possible.

𝛿𝑃 (𝑝, 𝑠𝑚) = 𝛿𝑆(𝑠𝑚) 𝛿𝑆(𝑠𝑚) = 1
On the other hand, the lowest possible ranking is when the predicate 𝑝 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.

𝛿𝑃 (𝑝, 𝑠𝑟𝑜𝑜𝑡) = 1 ∏

∀𝑖, where 𝑠 𝑖 is a shape 𝛿𝑆(𝑠𝑖)

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 𝑥 occurring in the triple patterns we have a set 𝐶(𝑥) of candidate shapes for 𝑥. For convenience, given a triple pattern 𝑡, we define 𝐶(𝑡) = 𝐶(𝑥) if 𝑥 is a subject of 𝑡. We also define 𝑝(𝑡) as the predicate of the triple 𝑡.

To define the triple ranking function, we use the two ranking functions 𝛿𝑆 and 𝛿𝑃 defined previously.

Given a BGP 𝐵 and a triple pattern 𝑡 ∈ 𝐵, we define the ranking of the triple 𝑡, denoted by 𝛿𝑇 (𝑡), as follows:

𝛿𝑇 (𝑡) = 𝐴𝑣𝑔 [ 𝛿𝑆(𝑆𝑖) × 𝛿𝑃 (𝑝(𝑡), 𝑆𝑖) ] ∀𝑖, 𝑆 𝑖 ∈𝐶(𝑡)
For a given triple 𝑡, the previous function is the average of the product 𝛿𝑆 × 𝛿𝑃 by considering all the possible candidate shapes for the subject of 𝑡.

EVALUATION

We prepared two different two experiments with different setups that show the advantageous effects of the optimisation procedure described in this paper. Both experiments use real ShEx schema examples (Web Index [START_REF]WEB INDEX[END_REF] 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 utilise 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] Emilio | 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.

7.1.1 Generated data. wiGen 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 [START_REF]WEB INDEX[END_REF]. The ShEx schema utilised by wiGen is represented as a shape relation graph in Fig. 6.

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.

7.1.2 Queries. The set of queries we use for this experimentation is shown in Fig. 7. The variable names in the queries are hand-crafted to indicate a schema type from the schema of Fig. 6 (?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. 7 are given in their optimised form i.e. 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.

7.1.3 SPARQLGX. An advantage of our optimisation technique is that it can be applied on the top of query systems like SPARQLGX [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]. 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 queries [START_REF] Graux | SPARQLGX: Efficient Distributed Evaluation of SPARQL with Apache Spark[END_REF]. In our experiment we show how the application of our technique further decreases the average run time for SPAR-QLGX 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, but the order of the groups themselves is not considered, and thus the 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 following:

• 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. • Optimised: Is an extension of SPARQLGX. It extends it with the application of our ordering strategy based on the ShEx information.

7.1.4 Results. The results of our query evaluations are presented in Fig. 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 optimised 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 (Optimised) compared to avg(S2) ranged between 3.7% and 18%. The mean improvement of all test queries 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.

7.2.1 Generated data. Using the gMark tool, we generated 4 datasets, all according to the LDBC SNB schema (check the schema in Fig. 8 and the corresponding well-formed shape relation graph in Fig. 9). 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. 7.2.2 Queries. Using gMark, we also generated a set of 12 SPARQL queries based on the LDBC SNB schema. We setup the 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. 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 optimisation is less evident when the 5M nodes dataset is compared to the bigger datasets. Compared to system S2 in Fig. 2, the optimised orderings of queries Q1, Q10, and Q12 showed a slight improvement. In Fig. 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 stabilised.

The average of the improvement of our system (Optimised) 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%.

CONCLUSION

We studied a method for SPARQL query optimisation 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 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 optimisation.

  xsd : string , ex : phone xsd : string } Listing 2: Sample Shape in ShEx 3.2.1 Abstract Syntax of the Considered ShEx Fragment.

Example 4 . 3 .

 43 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> + }

Figure 6 (

 6 Figure 6 (appendix) shows the shape relation graph of a real life schema used in our experimentation (Sect. 7). Userdefined types are shown as ovals while built-in types (like xsd:string) and IRIs are shown as rectangles. For visualisation reasons, we also replicate some type nodes in the mentioned figure.We define the set of root nodes of a shape relation graph.

Figure 1 :

 1 Figure 1: Comparing ranking-optimised query evaluation with other systems (WebIndex data)

7. 2 . 3

 23 Results. The results of our query evaluation with the 4 datasets are presented in 4 charts (Figs.2, 3, 4, and 5), where each is similar to the chart described in Experiment 1.

Figure 2 :

 2 Figure 2: Comparing ranking-optimised query evaluation with other systems (SNB data 5M nodes)

Figure 3 :Figure 4 :Figure 5 :

 345 Figure 3: Comparing ranking-optimised query evaluation with other systems (SNB data 30M nodes)

Figure 6 :

 6 Figure 6: Shape relation graph (WebIndex)

Figure 8 :Figure 9 :

 89 Figure 8: Schema (LDBC SNB) Source: https://github.com/ldbc/ldbc snb docs

•

  Given any two nodes 𝑛1, 𝑛2 ∈ 𝑁 , and any predicate 𝑝, then 𝐸(𝑛1, 𝑝, 𝑛2) if and only if (𝑝, 𝑛2) ∈ 𝛿(𝑛1) and (𝑝, 𝑛2) ̸ ∈𝑜𝑝𝑡 𝛿(𝑛1) • Given any two nodes 𝑛1, 𝑛2 ∈ 𝑁 , and any predicate 𝑝, then 𝐸(𝑛1, 𝑝

𝜖 , 𝑛2) if and only if (𝑝, 𝑛2) ∈𝑜𝑝𝑡 𝛿(𝑛1)