The popularity of the Resource Description Framework (RDF) and SPARQL has thrust the development of high-performance systems to manage data represented with this model. Former approaches adapted the well-established relational model applying its storage, query processing, and optimization strategies. However, the borrowed techniques from the relational model are not universally applicable in the RDF context. First, the schemafree nature of RDF induces intensive joins overheads. Also, optimization strategies trying to find the optimal join order rely on error-prone statistics unable to capture all the correlations among triples. Graph-based approaches keep the graph structure of RDF representing the data directly as a graph. Their execution model leans on graph exploration operators to find subgraph matches to a query. Even if they have shown to outperform relationalbased systems in complex queries, they are barely scalable and optimization techniques are completely system dependent. In this paper, we propose optimization strategies for graph-based RDF management systems. We intend to take the strengths of relational databases and propose logical structures generically depicting graph-based query execution. First, we define novel statistics collected for clusters of triples to better capture the dependencies found in the original graph. Second, we redefine an execution plan based on these logical structures. Finally, we introduce an algorithm for selecting the optimal execution plan based on a customized cost model.
The versatility of the Resource Description Framework (RDF) has contributed to its rapid expansion not only as a standard data model in the semantic Web but also as the preferred representation for data from diverse domains (e.g. genetics, biology). The RDF model uses triples consisting of a subject, a predicate and an object < s, p, o > to represent data and SPARQL as its query language. Currently, public RDF data sets (known as knowledge bases) with billions of triples are extensive sources of information (e.g. DBPedia1, Bio2RDF2) popularly queried and aggregated. As
2https://bio2rdf.org/ the volume of available RDF data grows, the need for high performance RDF data management systems becomes more noticeable.
To cope with the proliferation of RDF datasets, early works
used the well-established relational model as backend, storing
RDF triples directly into tables (single-table [
Furthermore, these strategies are not universally applicable in
the RDF context. Firstly, because they rely on statistics that are
very error-prone since they are gathered on the entire collection
of data (contrary to the relational model where statistics are
calculated per table entity). Capturing statistics for datasets without
an explicit schema is not a simple task. Former approaches
collected statistics at the predicate level and assumed independence
between triples. However, as shown later by [
Graph-based processing systems (e.g. [
In this paper, we propose optimization strategies for graphbased RDF management systems. Our strategies fit both centralized and distributed approaches. We took the strengths of the logical execution modeling from the relational databases and propose rfist logical structures to portray the query execution based on the exploration of the query and input graphs. We redefine an execution plan based on these structures and present an algorithm that generates and picks based on a cost model the optimal execution plan for a given query. Our cost model relies on statistics, but in contrast to former approaches estimating statistics on the global graph we collect them for clusters of triples (that we named graph fragments G f ) logically connected in the original graph. Our cost model considers the interactions between graph fragments to estimate the network and disk costs of a given query plan.
The contributions of the paper are summarized as follows: (1) We formalize a logical model describing the query execution of RDF systems based on graph exploration methods. (2) We present the essential statistics collected for each graph fragment. (3) We detail what is to the best of our knowledge the first cost model to compare execution plans based on the disk and network costs in graph-based systems. (4) We present a study of the problem allowing to choose the optimal execution plan. We prove its complexity and profer a branch and bound like algorithm to eficiently explore and select the optimal execution plan in terms of our logical structures.
The rest of the paper is organized as follows. First, Section 2 presents the state of the art of the optimization strategies proposed for RDF systems. Then, Section 3, introduces the preliminary definitions used to describe the query execution based on graph exploration. Section 4 presents the cost model allowing to compare the equivalent plans and introduces an algorithm to find the best execution plan. Next, section 5 presents the experimental study. Finally, Section 6 summarizes the work and gives insights on future researches. 2
In this section, we summarize the most relevant optimization strategies adopted by triple stores in the state of the art. We classify them according to whether the strategy is applied before or during the query execution (BQE and DQE respectively). In the ifrst category we consider approaches of organization, indexing and distribution of data; all of them have been implemented by diferent systems with the aim of finding the best query performance. The second category depicts optimization strategies at query runtime. 2.1
BQE strategies
2.1.1 Data organization. The earliest RDF processing systems
adapted the prominent relational model. The naïve approach
embraced by Sesame [
Before describing optimization strategies applied during query
execution, let us classify SPARQL evaluation approaches. In
centralized systems, the evaluation is either join-based (e.g. [
The static query optimization strategies use maintained statistics about the data to determine an optimal query plan. The estimation of the cardinality is the base measure used to evaluate and compare execution plans for a specific query.
Cardinality Estimation in RDBMS. It has been longly seen as a
key component in the query optimization and it is a well
established field in the the relational database world[
Cardinality Estimation in SPARQL. Currently, several studies
have investigated the cardinality estimation issues for SPARQL
queries. A line of work uses very simplistic models based on
RDF-specific statistical synopses including counters of frequent
predicate-sequences in paths of the data graph[
Contrarily to existing techniques, the set of strategies proposed in this paper are independent of the physical storage and query evaluation models of any system. Our assumptions are only that the data are logically clustered based on the predicates and that the main query evaluation operator is based on a graph exploration strategy. We propose a set of techniques allowing to find the best way to explore the data graph in order to evaluate a SPARQL query. We rely on a novel cost model that takes into account the correlation between predicates and nodes. Our proposal is not only adapted to centralized systems but also to parallel systems that rely on graph exploration as query evaluation technique. In this kind of systems, our cost model will consider the interactions between fragments to estimate the disk and network costs. 3 3.1
The Resource Description Framework (RDF) has been widely accepted as the data model for the Linked Open Data and the semantic Web. The model uses triples consisting of a subject, a predicate and an object < s, p, o > as its main abstract structure. The model provides flexibility without explicitly enforcing a schema. A collection of interlinked RDF triples could be represented as a graph as shown in Figure 1. The graph of the example contains data related to air trafic control. The RDF graph is formally defined in Definition 3.1.
Definition 3.1. (RDF Graph) An RDF graph is denoted as G = ⟨Vc , LV , E, LE ⟩ where Vc is a collection of vertices corresponding to all subjects and objects, LV is a collection of vertex labels, E is a collection of directed edges that connect the corresponding subjects and objects, and LE is a collection of edge labels. Given an edge e ∈ E, its edge label is its property .
SPARQL is the most popular query language for RDF. A simple SPARQL query consists of a query form (e.g. SELECT in Figure 2), a Basic Graph Pattern (BGP) and a set of SPARQL operations (e.g. FILTER). A Basic Graph Pattern is composed of triple patterns (TPs). TPs are expressed in a triple form and they are composed of at least one of S, P, O being a variable. An example query with three TPs and its graph representation is shown in Figure 2. In our work, we consider only SPARQL queries with bounded predicates. A SPARQL query can also be represented as a graph as described in Definition 3.2.
Definition 3.2. (Graph Query) A Graph Query is denoted as Q = (V , LV , E, LE ), where V = Vp ∪ Vc is the union of the sets of variable and bounded vertices. LV is the set of vertex labels, the labels of variable vertices are distinguished with a leading question mark symbol. E and LE represent the set directed edges between vertices and its labels respectively. 3.2
In this section, we discuss the main definitions allowing to model the logical organization of data in clusters keeping its graph structure. Then, we detail the query evaluation operators based on graph exploration on the clustered data.
3.2.1 Graph storage. In contrast to several of the approaches mentioned in Section 2.1.1 in which the graph structure of the loaded RDF data is broken, we strive to preserve it. The storage model groups RDF data first such that implicit structures within the data are automatically discovered. Data are firstly grouped has_flight plane_mohdaes_llfight
"ORY" iata_code ?c Star and Backward Data Star to the sets D−→S(x ) = {(x, p, o)|∃p,o : (x, p, o) ∈ G } and D←−S(x ) = {(s, p, x )|∃s,p : (s, p, x ) ∈ G } respectively.
Data Stars extend the notion of a record in the relational database model. The primary key of a DS(x ) corresponds to its head x . Records are grouped in tables in a RDBMS, following this logic we group records describing similar entities into sets named Graph Fragments.
When building the Graph Fragments, ontologies could be
applied since they intend to provide an overall schema of the data
stored in an RDF graph. However, several studies show that
there is still a very partial use of ontology classes and sometimes
subjects share triples with properties coming from diferent
ontological sources [
Each subject s in the graph G has a characteristic set defined as →c−s (s) = {p |∃o : (s, p, o) ∈ G }. Similarly, for the objects we define c←−s (o) = {p |∃s : (s, p, o) ∈ G }. A Forward Graph Fragment G−−→f groups Forward Data Stars having the same characteristic set. Backward Graph Fragment G←−−f are formed similarly. Its formal definition is given in Definition 3.4.
G←−−f = {D←−S(x )|∀i,j c←−s (xi ) = c←−s (xj )}.
Definition 3.4. (Graph Fragment) A Graph Fragment is a set of Data Stars, it is named a Forward Graph Fragment G−−→f if it groups Forward Data Stars such that G−−→f = {D−→S(x )|∀i,j →c−s (xi ) = →c−s (xj )}. Likewise, a Backward Graph Fragment G←−−f is defined as
It is shown that indexing and compressing the data of
fragments in B+Trees improves significantly the performance at
query runtime[
3.2.2 Query execution. In this section we formalize the logical
structures used to describe the query evaluation. As previously
mentioned, a SPARQL query can also be represented as a directed
graph whose nodes are either variables (e.g. ?f, ?m in Figure 2)
or bounded values (e.g. <El Prat>). Let us first recall how a
SPARQL query is evaluated in most of the state-of-the-art
systems. Traditionally, a SPARQL query is evaluated in a TP by TP
manner [
To shorten the logical query plan, TPs can be grouped if they share a common variable on the subject (or object). We name these structures Forward Query Stars and Backward Query Stars if they group the triples on subject or object respectively. Furthermore, as it will be shown later, with these structures the query execution can be easier tracked following a graph exploration approach. Both structures are formally described in Definition 3.5.
Definition 3.5. (Query Star) Let Q be the SPARQL query graph. A Forward Query Star Q−→S(x ) is the set of triple patterns such that Q−→S(x ) = {(x, p, o)|∃p,o : (x, p, o) ∈ Q }, x is named the head of the Query Star. Likewise, a Backward Query Star Q←−S(x ) is Q←−S(x ) = {(s, p, x )|∃s,p : (s, p, x ) ∈ Q }. We use Q−→S, Q←−S to denote the set of forward and backward graph stars and qs to denote indistinctly a forward and backward query star.
The execution of a query can be expressed as a join of Query Stars. Since we consider two copies of the data, (one copy stored as G−−→f and another as G←−−f), the execution plans consider both types of Query Stars. An execution plan is composed of a sequence of joined Query Stars as shown in Definition 3.6.
Definition 3.6. (Execution Plan) An execution plan is an order function applied on a set of Query Stars. The function denotes the order in which the mappings for each Query Star will be found. We denote by P = [QS1, QS2, ..., QSn ] the plan formed by executing QS1, then QS2,..., and finally QSn .
Let us consider for instance that the optimal query plan for the query of Figure 2 is P1 = [Q←−S(?m)1, Q−→S(?f )2, Q←−S(?f )3]. The execution engine starts processing Q←−S(?m)1 by loading all the backward fragments whose characteristic set contains all the predicates (in this case only the plane_model predicate) of Q←−S(?m)1. Assuming that the backward fragments G←−−f11 and G←−−f12 are the only backward fragments matching the predicates of the query star, the execution scans both fragments and finds the mappings G←−f−11 G←−f−12
Q−−→S(?f ) G−−→f 13 G−−→f 14 G−−→f 15 G←−f−16 G←−f−17
G←−f−18 to the variables ?m and ?f. These mappings are sent to the forward graph fragments whose characteristics match the predicates of the second Query Star Q−→S(?f )2. In this way, only the pertinent mappings with respect to Q←−S(?m)1, Q−→S(?f )2 are kept. The process continues similarly for the following query stars.
It is evident that an Execution Plan represents a way to explore the graph. Indeed, finding the optimal execution plan conveys to ifnd the best way to explore the data graph. In the next section we detail the optimization strategy followed to find the optimal query plans in terms of Query Stars. We define an acceptable query plan and then depict the algorithm used to generate them. Then we present the cost model in terms of disk and network cost applied to decide on the optimal plan. 4
GRAPH-BASED QUERY OPTIMIZATION In this section, we present our cost-based optimization strategy which allows comparing execution plans (based on Query Stars). Firstly, we define an acceptable plan and we detail the statistics allowing to evaluate the cost of an execution plan based on the disk and network cost. Next we define the problem of finding an optimal plan and we describe a branch and bound based algorithm used to generate the list of candidate execution plans. 4.1
In the last section, we defined an Execution Plan P as an order function applied to a set of Query Stars. An execution plan P is called an Acceptable Execution Plan if it fulfills the following conditions: (1) Coverage: All nodes and predicates of the given query are covered by the set of Query Stars of the plan. For example, for the query of Figure 2, the execution plan [Q←−S(?m), Q−→S(?f )] is not a valid plan since the node ?c and the edge has_flight are not covered by the plan. (2) Instantiated head: This condition guarantees that for a plan P = [SQ1, ..., SQn ], ∀i >1SQ, the head of the SQi must be already instantiated. We use this condition to avoid to a cartesian product when mappings are exchanged between two star queries. For example, the plan shown in Figure 4a is not acceptable since the head of the second query star (Q−→S(?c) is not instantiated before finding the mappings for this query star. A plan in which the head has been instantiated is shown in Figure 4b.
The formal definition of an Acceptable Plan is given in Proposition 4.1.
Proposition 4.1. (Acceptable Plan) AP Let us consider Q as a given query, Q−→S and Q←−S as the sets of forward and backward dept. pl_m pl_m ▷◁
hs_fl (a) [Q−−→S (?f ), Q−−→S (?c )] dept.
hs_fl (b) [Q−−→S (?f ), Q←−−S(?f )] In this section, we present a novel cost model used to compare execution plans P. As for distributed databases, the cost is expressed with respect to the estimated total time. The total time is the sum of all time components (CPU, I/O, Communication), however, the I/Os and the communication costs are generally the dominant factors. Our cost estimation considers both the disk and communication costs for each query star on the plan as shown in Equation 1. The parameters TI /0 and TT R are the time of a disk I/0 and the time to transmit a data unit from one site to another respectively. The estimated number of of I/O’s and network packets transmitted are represented by D C and N C and their calculation is described in the next sections.
Both the disk and network costs are estimated based on statistical information about each graph fragment G f (Definition 3.4). For the disk cost, the statistics allow estimating the number of Data Stars loaded on each fragment that contains potential query matches. Likewise, for the network cost, the number of intermediate results exchanged between fragments at diferent sites is estimated based on the same statistics. In the next section, we describe the statistical data collected for each graph fragment.
4.2.1 Fragment statistics. We rely on statistical data are collected for each Graph Fragment G fk . The statistical data collected for a graph fragment G fk (forward or backward) whose characteristic set is cs = {p1, ..., pm }, considering that pi ∈ cs are summarized in Table 1. Some examples of statistics for the example graph of Figure 1 are given in Figure 5.
Let us consider the statistics shown in Figure 5. The statistics for the backward graph fragment G←−−f4 are shown in Figure 5a.
←−− The dist (G f 4) is 3 since the fragment contains three data stars whose heads are AF37, IB62 and IB83. Both count (pi , G fk ) and dist _N E(pi , G fk ) are calculated only for the predicate has_flight (identified as 1 in the Figure) since it is the only predicate in the fragment’s characteristic set. There are three edges in the fragment having has_flight as a predicate, therefore count (pi , G fk ) = 3. For this fragment, dist _N E(pi , G fk ) = 2 since there are two distinct nodes (Air France and Iberia) linked to the data star heads of G←−−f4.
The selectivity factor SF (G fk , G fj , p) between two graph fragments with respect to a predicate is the ratio of the number of edges in a node pointing to the data star’s head located in another fragment. For example, in Figure 5c, the selectivity factor SF (G←−−f5, G←−−f4, 2) (2 is the id of the predicate arrival) is 2/2 since out of the 2 edges of the predicate arrival in G←−−f5, 2 nodes (AF37 and IB83) are the heads of data stars located in G←−−f4.
For simplicity and to keep the same notation, the selectivity of two graph fragments sharing the same head is represented as SF (G fk , G fj , −1). For example, the selectivity factor SF (G−−→f 3, G←−−f5, −1) in Figure 5b is 1/2 since out of the two heads in G−−→f 3, one of them is a head of a data star in the graph fragment G←−−f5 (shown in Figure 5c).
4.2.2 Disk cost. We present in this section the diferent
formulations that allow estimating the number of pages targeted by
a plan. We assume that the data on each fragment are stored as
a clustered B+Tree as done in [
D C(qsi ) =
Õ (Gf j ,kj )∈ input qsi
ND P (G f j , kj ) (2) IB62 IB83
Iberia (a) 3 pi (b) (c) 1 3 2 (1) BGfj : number of disk pages in the last level. (2) HGfj : number of levels. (3) ri : reduction factor for the ith level. Given two levels "i" and "i + 1", and "Z " and L as the number of pages for the level "i" and "i + 1" respectively, ri is defined as by Z /L. (4) NGfj : number of data stars in the fragment G f (i.e., number of keys in the leaf level of the B+Tree). (5) rf (i): is the number of pages to be manipulated at the ith tree level.
As it is shown in last equation, the number of pages N P is the sum of the number of pages manipulated at all levels.
The number of data stars k. In this part we explain the procedure to obtain the number of data stars per each star query (represented as k). To better understand the procedure, let us recall the graph exploration execution model illustrated in Figure 3. For a given plan, the execution is done finding the mappings of one query star after another. This execution model guides the estimation of data stars per query stars. We start calculating the number of data stars for the first query star ( Input). Then we estimate the number of data stars that we get after executing this query star(Valid Input). Next, we estimate the number of data stars sent to the next query star for each predicate (Output). Finally, using the selectivity factor and the output, we calculate the input of the next query star. This procedure continues until the last query star.
Let us introduce the estimation of the Input of the first query star. We distinguish two cases: (i) If the head of the star query is a variable:
input _DSqs1 = {(G fj , k)|G fj |= qs1 ∧ k = dist (GFj )} input _DSqs1 = {(G fj , 1) | Head(qs1) ∈ GFj ∧ G fj |= qs1} The input of a query star is expressed as a set of tuples (G f j , kj ). G f j is a Fragment satisfying the predicates of qs1 and kj is the number of data stars targeted by this query.
The Valid input data stars is calculated for each (G fj , k) ∈ input _DSqsi and it is expressed as follows: valid_DSqsi = {(G fj , k ′) | k ′ = ⌈k ∗ min e ∈Edдes(qsi ) f (e)⌉ } Where f (e) = (
1 dist _N E(e .l abel ,Gfj ) 1 , i f e .node is constant , otherwise In the f (e) function, we calculate a reduction factor for each predicate (e .label ) to consider an estimation of the number of data stars found in the fragment after the execution of the star query.
For each tuple (G f j , k ′) ∈ valid_DSqsi , we calculate the output _DSqsi expressed as a set of triplets (G f j , pi , k ′′) where G f j is the fragment from the input, pi is a predicate of the qsi and k ′′ is the number of distinct edдe .node related to pi with respect to the valid input. The Output is calculated as follows: output _DSqsi = {(G f j , pi , k ′′)|pi ∈ edдes(qsi )∧k ′′ = ⌈N DSpi ⌉ } Where N DSpi = ( 1 , i f e .node is const , otherwise k′ dist (Gfj ) ∗ dist _N E(pi , G fj ) N DSpi is the number of data stars head related to each predicate.
After computing the output of the first query star, We can now compute the input of the second query star. For each star order greater than one in the plan, the input is computed as follows:
To calculate the Input we of qsi if the head of the query star is a variable we consider two cases:
(i) Neighbor star queries: In this case, the last evaluated query star is a neighbor of the current query star, therefore in this case we can use the selectivity factors. The data stars heads targeted in the fragment "G fj " are computed as follows: Õ k ′′ ∗ SF (G fk , G fj , p) Where p is the edge between qsi and qsi−1.
(ii) Same head star queries: In this case, the current query star has the same head of the last evaluated query star so there is no link between the star queries. In this case, when Head(qsi ) is restricted, the number of data stars is equal to the product (Gf k ,p,k′′)∈output qsi−1 between the selectivity of the query star head in the fragment that satisfies qsi . 4.2.3 Net cost. We present in this section the formulations to estimate the number of network packets exchanged between fragments in diferent machines. Unlike the Disk Cost in which we estimate the number of data stars loaded by each graph fragment in a query star, the Network Cost aims to estimate the number of mappings sent from one graph fragment to another.
As a recall, a mapping is a binding between the nodes of the query star and the corresponding values in the input graph. For example, the mappings of the first query star of Figure 3 are the bindings for variables ?m and ?f in the input graph (e.g. ?m → B737, ?f → IB83). As illustrated in Figure 3, these mappings are sent to the graph fragments of the following query stars. The total network cost is equivalent to the sum of mappings exchanged between fragments located in diferent sites (illustrated with dotted arrows in Figure 3).
The network cost is shown in Equation 3 as the sum of exchanged packages between graph fragments. The function NN P returns the number of packages exchanged between two fragments given a number of mappings M and its size S.
N C(qsi ) =
NN P (G f k , G f j , M) (3) Õ (Gf k ,Gf j ,M ) ∈ output _M P qsi
Number of exchanged packages. Let us detail the function NN P calculating the number of packages as the product between the number of mappings M, its size S and the output of the function loc(G fk , G fj ) returning 1 if the fragments are located on distinct sites and 0 otherwise. Its formulation is as follows:
NN P (G f k , G f j , M) = M ∗ sizei ∗ loc(G f k , G f j ) /sizepack The parameter sizei represents the size of a single mapping for the current query star and all the previously found mappings and sizepack indicates the size of a single package transmitted over the network.
The estimation of the number of mappings M from one query star to another is done at the graph fragment level of each query star. We start calculating the number of data stars loaded per graph fragment for the first query star ( input _MP ). Then, based on this input, we estimate for each graph fragment the number of mappings produced after the execution of the first query star (valid_MP ). These mappings, named valid mappings, are multiplied by the selectivity factors between the graph fragments of the first and second query stars to obtain the output mapping for each pair of graph fragments. The output mapping of the ifrst query star becomes the input of each fragment in the following query star. The next mappings are estimated following the same methodology (calculating the input mappings, valid input mappings and the output mappings for each fragment in the query stars). Next, we detail the formulas used to calculate the mappings at each step.
Input mapping: The input of the first query star is computed similarly as the inputs of the first query star for the disk cost in which we distinguish two cases: (i) If the head of the query star is a variable:
input _MPqs1 = {(G fj , M)|G fj |= qs1 ∧ M = dist (GFj )} (ii) If the head of the star query is a constant: input _MPqs1 = (G fj , 1) | Head(qs1) ∈ GFj ∧ G fj |= qs1 (G fj , 0) | Head(qs1) ∈ GFj ∧ G fj ̸|= qs1
Valid mapping: The valid mapping of the query star is computed using the input mapping calculated in the previous step. The valid input estimates how many variable bindings exist after executing the current query star. For each input ((G fj , M)) we calculate the product between the number of mappings in the input M and the estimated number of mappings after the execution of the current query star. The valid input is calculated for each input (G f j , M) as follows:
valid_MPqsi = {(G f j , M ′) | M ′ = M ∗ P (qsi , G f j )} The number of mappings after the execution of the current query star are the product of the mappings for each edge of the query star. For each edge e of the query, we calculate a permutation between n and k where n is the diference of the mean number of edges on each data star of the fragment having the same predicate as e .label and the number of edges in the query star pointing to a constant node. The value of k equals to the number of edges in the query pointing to a variable node. More precisely, P (qsi , G f j ) = Ö
n! e ∈Edдes(qsi ) (n − k)! where, n = count (e .label, G fj )/dist (G fj ) − N _const (e .label, qsi ) k = count (e .label, qsi ) − N _const (e .label, qsi ) and N_const is a function returning the number of edges labeled as e .label in the query star pointing to a bounded node.
Output mapping: After computing the valid_MP of the first query star, we calculate the number of exchanged results between fragments using the selectivity factor. This value is calculated for each graph fragment from the current query star qsi to the graph fragments of the next query star qsi+1. For each valid mapping found previously, the output mapping is a set of triples defined as follows: output _MPqsi = {(G fk , G fj , M ′′)|G fj |= qsi+1 ∧M ′′ = ⌈Int MP ⌉ }
The intermediate mappings Int MP is a function returning the number of mappings sent to each graph fragment based on the selectivity factor.
Int MP =
M ′ ∗ SF (G fk , G fj , p) M ′ ∗ SF (G fk , G fj , −1) , i f qsi has neiдhbor , otherwise The input of the following query star is calculated as follows: N br _MP (G fj ) = input _MPqsi = {(G fj , M) | G fj |= qsi ∧ M = N br _MP (G fj )} The total number of mappings for a single graph fragment is the sum of all the mappings received from all the graph fragments in the previous query star. It is calculated as: Õ
M ′′ (Gfk ,Gfi ,M′′)∈output _M P qsi−1 ∧Gfi =Gfj Several execution plans can be used to evaluate a given query. In Section 4.2 we develop a cost model allowing to compare equivalent plans for a query. Finding an optimal acceptable execution plan AP∗ consists in selecting the acceptable plan for a given query such that it minimizes a given cost function (defined in Equation 1). We name this problem as the Stars Ordering and Selection problem since we seek to find the optimal ordering of Query Stars in the plan. Its definition and complexity are given in Proposition 4.2 and Theorem 1 respectively.
Proposition 4.2. Stars Ordering and Selection (SOS) problem Given a query q, find an acceptable plan P∗ such that: minimize (Eq. 1)
T otal _Cost (P∗)
Theorem 1. The Stars ordering and Selection (SOS) problem is NP-Hard.
Theorem 1 is explained as follows: our problem is as dificult as the well-known problems belonging to the NP-Hard class. There is no eficient (polynomial) algorithm that can solve this problem. Then we face two cases: either an exact and exponential algorithm or a polynomial and not exact algorithm. In the next section we describe a branch and bound based algorithm allowing to find the optimal query plan based on some parameters. Due to the lack of space the proof of this theorem is found online 3. 4.4
We present in this section our parametric algorithm allowing to find the best plan for a given query. Our algorithm relies on a branch and bound strategy to enumerate candidate solutions. To prune invalid execution plans it relies on the concepts of Allowed_Stars and Star_Distance defined next.
Allowed Stars. This concept guarantees that all the generated execution plans are acceptable plans APs. For a given plan X , an Allowed_Star is the set containing the query stars (forward and backward) such that any of them can be added to X and produce an AP. For the example query of Figure 2, the Allowed_Star set for the plan [Q−→S(?c)] is {Q−→S(?f ), Q←−S−(El Prat)} since both plans ([Q−→S(?c), Q−→S(?f )], [Q−→S(?c), Q←−S(El Prat)]) are acceptable. The formal definition is given in Proposition 4.3.
Proposition 4.3. (Allowed stars) Let X be a valid plan, the allowed stars set is defined as follows: Allowed_stars(X ) = {qs |qs ∈ QS ∪ Q←−S and [X , qs] is an AP } −→
Stars Distance. This user-defined parameter allows skipping some combination that the user does not want to explore based on the concept of distance. The distance between two stars in a query graph is the number of edges separating the heads of the star queries by considering the shortest path. For example, for the query in Figure 2, the distance between the star queries Q−→S(?c) and Q←−S(?m) is 2 since between the heads of both heads there are two predicates (has_flight and plane_model). The distance between stars allows considering only plans that privilege to evaluate neighbors’ stars. The formal definition is given in Proposition 4.4.
Proposition 4.4. (Stars Distance) Given two query stars QS(x ) and QS(y), the distance between both queries is given by: distance(QS(x ), QS(y)) = |{p |p is a path between x and y}| 3Theorem 1’s proof & Experimental Queries: https://www.lias-lab.fr/~amesmoudi/ papers/dolap2020/SOS-NP-hardness-proof.pdf C[−So−→Qst(?=cc)]1
Algorithm overview. The optimal execution plan discovery algorithm follows a branch and bound strategy in which the set of candidate plans is enumerated in a decision tree. The root of the tree contains the union of the sets of forward and backward query stars for a specific query. Each node of the decision tree contains a candidate plan, the Allowed_stars set for this plan and its cost (cost function described in Section 4.2). The children nodes are the execution plans resulting from adding a query star from the set of Allowed_stars to the execution plan of the parent node. The Allowed_stars set is empty if the node’s plan is an AP. If the cost of the plan in the node is greater than the cost of the best plan (at that moment), then the node will not be expanded to its children nodes even if there are still query stars in the Allowed_stars set. The cost of the best plan is initialized to infinite so the first AP generated becomes the best plan at an early exploration.
Let us consider the example tree shown in Figure 6 in which the the first star query to be explored is S−→Q(?c), with Allowed_Stars = {S←Q−(El Prat), S−→Q(?f )} and with a cost c1. Since c1 is not greater than infinite, we must continue expanding the node to the query stars in the Allowed_Stars set of S−→Q(?c). The tree is expanded and the child node contains the plan [SQ(?c), S−→Q(?f )] which is −→ an AP because its Allowed_stars is empty. Since the cost c2 of the plan is lower than infinite, the plan of the node becomes the best query plan (at the moment). The tree continues to expand creating the child [S−→Q(?f ), S←Q−(El Prat)]. Assuming that the cost c3 > c2, the node will not be expanded even if the star query S−→Q(?f ) is still in the Acceptable_stars set of the node. The algorithm continues exploring similarly until no more star queries in the root could be expanded and the best possible plan has been found.
The tree exploration technique is given in Algorithm 1. The initialization is done in steps 1-3. We start by creating a node under the root of the decision tree (step 5). Each node of the decision tree is characterized by three elements: the plan, the allowed query stars and the cost. In steps 6-8 we initialize the elements for the node created in step 5. Then in step 9, we call a function named Add_Query_Star for each query star. This function is described in Algorithm 2.
The Add_Query_Star function (Alg. 2) receives as parameters a query star, the node of the decision tree, the best plan (at the moment) and the stars distance. It starts calculating the node’s elements: it adds the query star to the plan (step 1), then calculates the allowed star (step 2) and the cost as defined in Section 4.2 (step 3). Next, if the cost of the plan is smaller than the cost of the plan defined as best plan then we call the Enumerate_Child_Branch function (step 5) defined in Algorithm 3. If the cost is greater, then it exits (step 7).
The Enumerate_Child_Brach (Alg. 3) function has as inputs the node of the decision tree, the best plan at the moment and the Algorithm 1: Optimal P Finding stars distance. If the set of allowed stars is empty, we consider the plan of this node and its cost as the new best plan and minimal cost respectively (steps 1-3). If there are query stars in the allowed stars set, then for each element that fulfills the distance constraint we call the Add_Query_Star function (steps 5-11).
Algorithm 3: Enumerate_Child_Branch
INPUTS: N : decision Tree node, P: Best Plan, d: stars distance 1: if N .Allowed_QSs is empty then 2: P.Plan ←− N .Plan 3: P.Cost ←− N .Cost 4: else 5: for qs ∈ N .Allowed_QSs do 6: qsl ←− last query star in N .Plan 7: if distance(head(qsl ), head(qs) ≤ d) then 8: N’ ←− a copy of N 9: Add_Query_Star (qs, N ′, P) 10: end if 11: end for 12: end if 5
We conducted our experiments in the QDAG system [
Query 1 2 4
Pr ecision(P) = (#Plans − Pos(P))/(#Plans − 1) where Pos is a function returning the plan’s rank with respect to the sorted plans in terms of execution time. The results for each dataset are shown in Figure 8. For all datasets, the prediction of the best execution time escapes is either the best possible plan (according to the execution time) or one of the top best. 6
In this paper, inspired from the relational model, we first provided logical structures to model the execution plan based on graph exploration techniques. Then, we proposed a novel cost model comparing equivalent logical execution plans based on statistics collected for clusters of triples (that we denoted graph fragments). The cost model estimates the disk and network interactions for a specific logical plan. Furthermore, we studied formally the complexity of the problem related to the choice of the best execution plan and we proposed a branch and bound like algorithm allowing to find the best plan for a specific query. For experimentations, we used synthetic and real datasets. The results showed that cardinality estimations based on our model are very precise even if the collected statistics’ size is negligible.
For future work, we plan to explore other optimization strategies such as real time execution plan auto-adaptation, also we plan to use Machine Learning techniques on runtime logs.