Characteristic sets profile features: Estimation and application to SPARQL query planning

RDF datasets are summarized in RDF dataset profiles that consist of profile features describing the characteristics and entities of the dataset. In the area of traditional relational database theory, a statistical profile is defined as a “complex object composed of quantitative descriptors” that “summarizes the instances of a database” [23]. These quantitative descriptors can cover different characteristics of the instances, for example:

The specific characteristics covered in such profiles depend on the downstream application, for example, the statistical features required by a query optimizer that uses the profile to devise efficient query plans. Similar to relational databases, statistic profiles are also commonly used for a variety of applications in the realm of RDF datasets. These applications range from centralized RDF data management solutions [28] and RDF graph compression [14] to query optimization for both centralized and federated query processing [16,24,26]. For instance, a common application of such statistical profiles in query optimization is the estimation of join cardinalities for subqueries.

The terminology for such statistical profiles varies according to their application [9,13,43]. In this work, we follow the terminology introduced by Ellefi et al. [13]: An RDF dataset profile is a formal representation of a set of dataset profile features. Moreover, we focus on statistical profile features and define them as follows.

As previously mentioned, computing these profile features can be challenging because accessing and processing the entire datasets is difficult and/or costly. Therefore, we investigate profile feature estimation without requiring access to the complete RDF graph.

2.2. Profile feature estimation

Addressing the limitation of requiring access to the entire RDF dataset for computing statistical profile features, we propose the concept of Profile Feature Estimation. Profile feature estimations aim to estimate a statistical profile features of RDF datasets using a subset of the data only. The goal is to generate a profile feature estimation that is as similar as possible to the original profile feature while requiring access to a subset of the dataset only. In particular, we propose an approach that relies on a sample from the original RDF graph in combination with a projection function to extrapolate the true profile feature. Consequently, we define a profile feature estimation as follows.

In an ideal situation, the estimated profile feature is identical to the true original profile feature (computed over the complete RDF graph). However, the profile feature to be estimated and the properties of both the subgraph H and the projection function ϕ may affect the differences between the true and the estimated feature. For example, given a larger subgraph, the estimation might be more accurate than for a smaller subgraph, as the larger subgraph potentially covers more characteristics of the original graph. The problem is finding an estimation for the profile feature which maximizes the similarity to the profile feature of the original RDF graph. To this aim, we introduce the concept of a similarity function δ that maps two profile features to a similarity value. The profile feature estimation problem is given as finding a profile feature estimation that maximizes the similarity to the original profile feature.

In order to maximize the similarity, the sampling algorithm for obtaining H and the projection function ϕ need to be chosen appropriately. The particular method to measure the similarity δ depends on the actual profile feature to be estimated with potentially several similarity functions for the same profile feature. Take for example a profile feature F ( G ) that counts all literal values in an RDF dataset and F ˆ ( G ) estimating the count based on a sample of G. The similarity to determine how well the count is estimated could be calculated as the absolute difference or the relative difference between the true count and the estimated count. In other words, the similarity function measures the representativeness of the profile feature estimation F ˆ with respect to F. In network theory, the representativeness of a sample is commonly assessed by how well it captures the structural properties of the original graph [5,21,33]. As we focus on a more comprehensive profile feature based on the characteristic sets – which capture structural and semantic features of the graph’s entities– considering only structural features of the sample and the graph may not be sufficient to assess how representative a sample is and, thus, a feature estimation for an RDF graph is. Note that in the remainder of this work, we only focus on this specific profile feature and investigate how the estimated profile feature can be leveraged in federated query processing. Nonetheless, the presented approach can be adapted and applied to other statistical profile features potentially supporting other applications as well.

3.1. Characteristic sets profile feature

The concept of characteristic sets for RDF graphs was introduced by Neumann et al. [27]. In their work, the authors used characteristics sets for query planning as they capture the co-occurrences of predicates in RDF graphs. The idea of characteristic sets is describing semantically similar entities by grouping them according to the set of predicates the entities share. Furthermore, the number of entities in each group are counted as well as the average usage of their predicates. As a result, the characteristic sets capture both statistical information on the data distribution as well as semantic information on the entities in an RDF graph.

In an RDF graph, the statistical information determined for the characteristic sets typically includes the number of occurrences (count) of a given characteristic set as well as the multiplicities of the predicates within each characteristic set. These statistics are used in both centralized triple stores and federated query engines because they allow to determine exact join cardinalities for specific Distinct queries and to compute cardinality estimations for non-distinct queries [16,24,26,27]. Similar to Neumann et al. [27], we define the number of occurrences count ( S ) of a characteristic set S = { p 1 , p 2 , … } in an RDF graph G as (1) | { s ∣ ∃ p , o : ( s , p , o ) ∈ G ∧ S C ( s ) = S } |

In addition, in this work, we focus on the occurrences of predicates in characteristic sets by considering their mean multiplicity. The mean multiplicity multiplicity ( p i , S ) for p i in S is given by (2) | { ( s , p i , o ) ∣ ( s , p i , o ) ∈ G ∧ S C ( s ) = S } | count ( S )

In other words, for a given characteristic set, the multiplicity measures how often each predicate occurs on average. Combining the count and mean multiplicity statistics of a characteristic set, we can compute the number of triples that are covered by it. The relative coverage coverage ( S , G ) of a characteristic set S ∈ S C ( G ) in an RDF graph G is computed as (3) ∑ p ∈ S multiplicity ( p , S ) · count ( S ) | G |

For example, consider the characteristic set S 1 = { lmdb:hasPhotoCollection , owl:sameAs } from our introductory example taken from LinkedMDB with

The statistics indicate that 9838 entities in the LinkedMDB graph belong to S 1 and each of those entities has exactly one lmdb:hasPhotoCollection and on average two owl:sameAs predicates. Moreover, the coverage indicates that 0.5 % of the triples in LinkedMDB belong to entities with S 1 as their characteristic set.

Finally, we introduce the notion of exclusive characteristic sets. An exclusive characteristic set occurs only once in an RDF graph and is defined as the following.

For example, in the LinkedMDB graph there exists only one entity with the predicates lmdb:relatedBook and lmdb:language. Therefore, the characteristics set S 4 = { lmdb:relatedBook , lmdb:language } is an exclusive characteristic set.

Based on these definitions, the statistical aspects of characteristics sets can be combined to formally define the characteristic sets profile feature (CSPF) as follows.

We now present the individual steps of our approach for estimating the CSPF of a given RDF graph.

Overview of the approach We propose a sampling-based approach that is shown in Fig. 1. Given a graph G, the approach generates a sample H ⊂ G using an RDF graph sampling method. We present the sampling methods in Section 3.2. Thereafter, the approach computes the CSPF F ( H ) for the sample H (Section 3.3). Finally, a projection function ϕ is applied to extrapolate the feature observed in H to an estimation ϕ ( F ( H ) ) for F ( G ) of the original graph. We propose different projection functions tailored to the CSPF in Section 3.4. Moreover, to assess the representativeness of the feature estimations, we propose a selection of structural and statistical similarity measures in Section 3.6.

OPEN IN VIEWER

Fig. 1.

Overview of the approach: a sample H is taken from the original graph G. The profile feature F ( G ) is created and projected to obtain the profile feature estimation ϕ ( F ( H ) ) = F ˆ ( G ) … (based on [17]).

The first step of our approach is obtaining a representative sample of the original RDF graph that provides a suitable foundation for estimating the profile feature. Before collecting data from a population in a sample, an appropriate sampling method needs to be chosen. Accordingly, we focus on sampling methods suitable for estimating the CSPF. Since characteristic sets capture the attributes of the entities in an RDF graph, we focus on entity-centered sampling methods in the following. Each entity (i.e., subject) is associated with exactly one characteristic set, thus, we define the population to be sampled from as the set of entities in the given graph: E : = { s ∣ ( s , p , o ) ∈ G } . The input of the sampling method is an RDF graph G and a sample size n ′ and its output is a subgraph H induced by n ′ entities of G. Let E ′ ⊂ E be the set of sampled entities with | E ′ | = n ′ , then the sample H is given as H : = { ( s , p , o ) ∣ ( s , p , o ) ∈ G ∧ s ∈ E ′ } . We present three entity-centered sampling methods differing in the probabilities of an entity being sampled. Thus, they allow for exploring different parts of the search space of possible characteristic sets during sampling.

Unweighted sampling The unweighted sampling method selects n ′ entities with equal probability from the population E. Thus, the probability Pr ( e ) of e ∈ E being a part of the sample is independent of any other property of the entity with Pr ( e ) = 1 | E | .

Weighted sampling The weighted sampling method is a biased sampling method, where the probability of an entity to be part of the sample is proportional to its out-degree. As a result, the more central an entity is in the graph with respect to its out-degree centrality [29], the more likely it is part of the sample. In this way, entities that appear in many triples of the graph in the subject position, have a higher probability of being selected. The out-degree of each entity e given by deg + ( e ) : = | { ( e , p , o ) ∣ ( e , p , o ) ∈ G } | . The probability Pr ( e ) of e ∈ E being sampled is given as Pr ( e ) = deg + ( e ) | G | .

Hybrid sampling The hybrid sampling method combines the previous two sampling methods. From the original graph, β · n ′ entities are selected using the unweighted method and ( 1 − β ) · n ′ entities using the weighted method. Accordingly, the probability Pr ( e ) of entity e being selected is given as Pr ( e ) = β · 1 | E | + ( 1 − β ) · deg + ( e ) | G | , β ∈ [ 0 , 1 ] .

The β parameter allows for favoring either the weighted or the unweighted method.

3.3. Profile feature creation

After obtaining a subgraph H using a sampling method, the characteristic sets profile feature F ( H ) is computed. Similar to [24], we compute F ( H ) by first sorting the triples in H by subjects and then iterating all triples. While iterating the triples, we determine the characteristic set for each subject in H and compute the count and multiplicity values for them. For details, please refer to the Appendix.

3.4. Profile feature projection

Given the profile feature F ( H ) , the goal of a projection function is to extrapolate the statistical properties observed in sample H to the target population, which is the original graph G. Given the profile feature F ( H ) = ( S , c , m ) , the projection profile feature is applied to F ( H ) to obtain an estimation of the original profile feature F ˆ ( G ) = ϕ ( F ( H ) ) . In the case of the characteristic sets profile feature (CSPF), the projection function aims to extrapolate the counts c of the observed characteristic sets to estimate the counts in the original graph. The multiplicity statistic m does not need to be extrapolated by the projection function, as it is a relative measure that captures the mean occurrence of a predicate in a characteristic set.

We now present two classes of projection functions for the count values of the characteristic sets in the sample. The first class, which we denote basic projection functions, only relies on information contained within the sample and the size of the original graph. The second class, which we denote as statistics-enhanced projection functions also relies on high-level information on the original dataset in addition to the information contained in the sample.

Basic projection function The basic projection function extrapolates the count values for the given characteristic sets profile feature F ( H ) based on the relative size of the sample. The relative sample size r t is given as the ratio of the number of triples in the original graphs and in the sample r t : = | G | | H | . We define the projection function ϕ 1 as ϕ 1 ( F ( H ) ) : = ( S , r t · c , m )

The assumption of the basic projection function is that the characteristic sets observed in a sample occur proportionally more often in the original graph. However, as exemplified in the introduction, the distributions of the counts may be potentially skewed which is not considered by this projection function. Moreover, this function neglects the fact that some characteristics sets might not have been sampled and merely distributes the proportional counts across the characteristic sets in the sample. As a result, it is likely that the counts for the characteristic sets is overestimated, especially if just a small portion of characteristics sets from the original graph are captured. To address this shortcoming, we introduce two statistic-enhanced projection functions that leverage high-level information to reduce the probability of overestimating the counts.

Statistics-enhanced projection functions The second class of projection functions incorporates additional high-level information about the original graph. In particular, we consider the number of triples per predicate in the original graph as this high-level statistic. The rationale for this particular statistic is that it potentially yields a good trade-off between the effort to obtain the statistic and the benefit it provides for the projection function. The number of triples for predicate p ′ is given by t ( p ′ ) : = | { ( s , p ′ , o ) ∣ ( s , p ′ , o ) ∈ G } | .

The first statistic-enhanced projection function, ϕ 2 applies a true upper bound for the counts of the characteristics sets in the following way. ϕ 2 ( F ( H ) ) : = ( S , c ˙ , m ) , with c ˙ ( S C ) : = min ( r t · c ( S C ) , min p ′ ∈ S C t ( p ′ ) )

The idea of this projection function is that the predicate occurrence statistics of the original graph allows for limiting the estimated counts for characteristic sets containing that predicate. If a predicate p ′ is part of a characteristic set S C , then S C may occur at most t ( p ′ ) times and consequently c ( S C ) ⩽ t ( p ′ ) . This reduces the likelihood of overestimating counts without increasing the likelihood of underestimating them. The effectiveness of this upper bound, however, strongly depends on the predicates that occur in a given characteristic set. For instance, in the case that a characteristic set contains common predicates, such as rdf:type or rdfs:label, the upper bound determined by ϕ 2 might be rather high, even though the predicates potentially occur in a number of other characteristic sets as well. Therefore, we propose a second statistics-enhanced projection function ϕ 3 which distributes the upper bound for a predicate p ′ by considering the sum of counts of the characteristic sets in which the predicate p ′ occurs. To achieve this, we first sum up the counts of all characteristic sets which p ′ occurs in as S C p ′ : = ∑ S C ′ ∈ S ∧ p ′ ∈ S C ′ c ( S C ′ )

The projection function ϕ 3 then adjusts the upper bound by multiplying t ( p ′ ) with the ratio of the count c ( S C ) of the given characteristic set S C and the sum of counts for all characteristic sets p ′ occurs in S C p ′ . ϕ 3 ( F ( H ) ) : = ( S , c ¨ , m ) , with c ¨ ( S C ) : = min ( r t · c ( S C ) , min p ′ ∈ S C ( t ( p ′ ) · c ( S C ) S C p ′ ) )

In contrast to ϕ 2 , this approach applies a stricter upper bound by considering all characteristic sets a predicate occurs in and reducing the upper bound accordingly. However, a drawback is that the projection function ϕ 3 increases the likelihood of underestimating the count of characteristic sets by assuming an equal distribution of the predicates.

Concluding this section on the projection functions, we want to note that further functions may be applied to potentially improve the estimation of the profile feature. For example, the characteristic sets sizes or additional statistics about the predicate distribution in the sample could be considered. However, we chose not to include them since they are likely to just produce accurate estimation under certain conditions and, therefore, do not generalize well for other datasets. Moreover, further improvements in the estimations do not necessarily imply the same improvements in the downstream applications that use the feature estimations.

3.5. Sampling RDF graphs in practice

The presented sampling approaches define the process for selecting entities to be sampled from the original graph but they do not encode how the samples are generated in practice. The implementation of the sampling approaches depends on the access methods to the given RDF graph. In the case of centralized RDF graphs, the sampling approach has access to the entire dataset and could potentially exploit existing data structures (e.g., indices) to efficiently access the entities in the graph. However, in decentralized scenarios as federations, the sampling methods have only access to parts of the RDF graphs and their implementation depends on the expressivity, capabilities, and configuration of the access interfaces. While it is out of the scope of this work to present specific implementations for each access interface, in the following, we provide insights into the considerations when implementing these sampling methods over remote SPARQL endpoints and Triple Pattern Fragments (TPF) servers.

SPARQL endpoints The expressivity of endpoints allows for selecting the entities to be sampled and then obtaining the subgraph induced by those entities.

The unweighted sampling method can be implemented over a SPARQL endpoint as follows. (i) Query all unique subjects (i.e., with Select and Distinct). If the number of entities exceeds the number of answers allowed per response, the implementation can retrieve all the entities by ‘paginating’ the results by ordering them with Order By and using Limit and Offset. (ii) Select n ′ subjects from the resulting set of entities. In the case that the endpoint supports the Rand6

In the weighted sampling method, the out-degree of an entity determines its probability to be sampled. To avoid computing the out-degree for each entity, it is possible to implement a simple heuristic that relies on the following assumption: The higher an entity’s out-degree, the more triples with it in the subject positions are present in the graph. Therefore, to obtain a weighted sample, the approach can randomly select triples from the graph and obtain the subjects of those triples. This can be achieved in endpoints using a query that matches any triple in the graph, a Limit of 1, and a random Offset value between 0 and the size of the graph | G | . This should be repeated until collecting n ′ entities.

Finally, after the entities have been selected, the induced subgraph of the entities can be obtained using either a Construct query or a Select query. That is, all triples where the entities are in the subject position will be constructed. This can be achieved with a Filter or, if supported, with the Values keyword with the list of selected entities from the previous step to instantiate the entities in the query.

Triple pattern fragments (TPF) TPF servers support triple pattern-based querying of RDF graphs. Since TPF servers do not provide the same expressivity as SPARQL endpoint for accessing the RDF graphs, the sampling methods need to be implemented accordingly.

Because TPF servers do not support Select or Distinct, the implementation of the unweighted sampling method over TPF servers should be realized differently from the one discussed for SPARQL endpoints. To obtain entities in the RDF graph, the method could request individuals of classes using the rdf:type predicate. Thereafter, duplicate entities can be removed locally and the sample of size n ′ can be drawn from these results. While this method disregards entities that do not belong to classes, it still allows for easily obtaining a subset of entities for the sample from TPF servers.

For implementing the weighted sampling method, a similar heuristic to the one presented for SPARQL endpoints can be followed. Instead of computing the out-degrees of each entity, the approach can randomly select triples from the RDF graph: entities with higher out-degrees have a higher probability of being chosen with this approach, as they appear more frequently in the triples. Random selection of triples is implemented over TPF servers by randomly selecting a page from the range 1 to the number of pages in the fragment, which can be obtained from the metadata void:triples and hydra:itemsPerPage provided by the server. Then, from the triples in the selected page, randomly select one triple to obtain the entity in the subject position. This process should be repeated until obtaining n ′ entities.

Finally, the induced subgraph of the entities can be obtained by querying all the triples where the subject corresponds to each selected entity.

Finally, we define similarity measures that quantify the similarity between the estimated profile feature and the feature of the original graph. A higher similarity value indicates a more representative feature estimation. According to our problem definition (Definition 2.3) in Section 2.2, the goal is obtaining an estimator F ˆ ( G ) = ϕ ( F ( H ) ) for the characteristic F which maximizes the similarity δ between the estimated and the original profile feature. As previously mentioned, methods to quantify the similarity depend on the particular profile feature. We now propose measures that are tailored to the characteristic sets profile feature (CSPF). Due to the diverse nature of the graph’s characteristics captured in the CSPF, we propose multiple measures to determine the similarity δ ( F ( G ) , F ˆ ( G ) ) between the original CSPF F ( G ) = ( S , c , m ) and an estimated CSPF F ˆ ( G ) = ( S ˆ , c ˆ , m ˆ ) . The proposed similarity measures capture both structural as well as statistical aspects of the CSPF. All measures take values in [ 0 , 1 ] with larger values indicating a higher similarity. An overview of all similarity measures is given in Table 2.

Structural similarity measures The first category of similarity measures focuses on the structural information captured in the characteristic sets. We propose four measures that consider the mean out-degree, the predicates covered, and the absolute and relative number of covered characteristics sets. The out-degree similarity measure δ od determines how well the mean out-degree of the original graph is captured in the estimated profile feature. The mean out-degree deg ‾ + can be computed for a CSPF F ( G ) in the following way. deg ‾ + ( F ( G ) ) : = | G | ∑ S C ∈ S c ( S C )

Note that deg ‾ + ( F ˆ ( G ) ) is computed analogously for the estimated features using H, S ˆ , and c ˆ instead. The out-degree similarity measure is computed as (4) δ od ( F ( G ) , F ˆ ( G ) ) : = 1 − | deg ‾ + ( F ( G ) ) − deg ‾ + ( F ˆ ( G ) ) | max ( deg ‾ + ( F ˆ ( G ) ) , deg ‾ + ( F ( G ) ) )

The second structural measure focuses on the predicates captured in the characteristic sets of the CSPF. The predicate coverage similarity δ pc is calculated as the ratio of the number of predicates covered in the estimation and the number of predicates in the original profile feature. (5) δ pc ( F ( G ) , F ˆ ( G ) ) : = | { p ∣ p ∈ S C ∧ S C ∈ S ˆ } | | { p ∣ p ∈ S C ∧ S C ∈ S } | A higher ratio indicates that a larger portion of the terminology used to describe the entities in the graph is captured in the estimated CSPF.

The final two structural measures address characteristic sets themselves and determine how many of them are covered in the CSPF F ˆ ( H ) . First, the absolute set coverage similarity δ ac is computed as the ratio of the number of characteristic sets in the estimation to those in the original statistic profile: (6) δ ac ( F ( G ) , F ˆ ( G ) ) : = | S ˆ | | S |

However, this measure does not reflect the importance of the characteristic sets captured in estimated CSPF with respect to their coverage . A characteristic set S C can be considered to be more important if it represents a larger portion of a given graph G. Therefore, the relative set coverage similarity δ rc of F ˆ ( G ) is calculated as the number of triples induced in the original graph with all characteristic sets in S ˆ of the estimation. (7) δ rc ( F ( G ) , F ˆ ( G ) ) : = ∑ S C ∈ S ˆ coverage ( S C , G ) | G |

Note that the characteristic sets of the estimation S ˆ are taken as the basis for computing the measure, while their coverage (c.f. Equation (3)) is computed based on the original graph, i.e. ∑ p ∈ S C m ( p , S C ) · c ( S C ) . In this way, δ rc reflects the importance of the characteristic sets captured in the sample. For example, consider an RDF graph G with two characteristic sets S 1 and S 2 , where S 1 covers 90 % and S 2 10 % of all triples in G. Assume that we obtain two estimations with S ˆ 1 = { S 1 } and S ˆ 2 = { S 2 } . Both S ˆ 1 and S ˆ 2 have the same absolute set coverage δ ac = 0.5 because they both contain one characteristic set. If we take the relative set coverage into consideration, we can determine that S ˆ 1 should be considered more representative for the original graph G as its characteristic set S 1 covers 90 % of its triples.

Statistical similarity measures The second category of similarity measures focuses on the statistical aspects covered in the feature estimations, namely the counts of the characteristic sets and the multiplicity of predicates. Depending on the distribution of the characteristics sets in the original graph, an accurate estimation of both counts and multiplicity values can be challenging. As a consequence, for some characteristic sets, the estimations can be accurate, while for others large estimation errors can occur. We propose statistical similarity measures that capture the estimation accuracy on the level of individual characteristics sets. To better understand the estimation error distribution across all characteristic sets in a sample, different aggregation functions, such as mean or median, may be applied afterward.

We propose a similarity measure for the count values that is the inverse of the count estimation q-errors. The q-error [25] is the maximum of the ratios between true and estimated count and vice versa. Given a profile feature F ( G ) and an estimation F ˆ ( G ) , the count value q-errors are computed for all S C ∈ S ˆ as q-error c ( S C ) : = max ( c ( S C ) c ˆ ( S C ) , c ˆ ( S C ) c ( S C ) ) .

Higher q-errors indicate a higher discrepancy between the true value and the estimation, and a q-error of 1 indicates that the estimation is correct. We take the inverse of the q-error to map it to the similarity measure range [ 0 , 1 ] (8) δ S C count ( F ( G ) , F ˆ ( G ) ) : = 1 q-error c ( S C ) .

Note that the q-error only measures the magnitude of the estimation error but does not indicate whether values are over- or underestimated. As a result, when aggregating the similarity measures across all characteristic sets of a given feature estimation S ˆ , this property avoids overestimated counts to cancel out underestimated counts and vice versa.

The proposed similarity measure for the predicate multiplicities is also based on the q-error and is defined on the level of characteristic sets. Given a profile feature F ( G ) , an estimation F ˆ ( G ) and a characteristic set S C in F ˆ ( G ) , this q-error is computed as the mean of the multiplicity q-errors of all predicates in S C q-error m ( S C ) : = 1 | S C | ∑ p ∈ S C max ( m ˆ ( p , S C ) m ( p , S C ) , m ( p , S C ) m ˆ ( p , S C ) ) .

Analogously, to the count values, the similarity measure for the multiplicities is the inverse of the q-error (9) δ S C multiplicity ( F ( G ) , F ˆ ( G ) ) : = 1 q-error m ( S C ) .

In summary, the characteristic sets in a CSPF captures various characteristics of RDF graphs, ranging from out-degree distribution to predicate co-occurrence. As a result, a combination of similarity measures needs to be taken into account to assess the representativeness of an estimation of a CSPF. To this end, we have proposed four structural and two statistical similarity measures. The importance of the individual measures depends on the application. In the following section, we present one potential application of the CSPF estimations in federated query planning.

4.1. CSPF estimation-based federated query planner

We propose a heuristic-based query planner to determine efficient query plans based on CSPF estimations. We adapt the notation from [2] and define a federation of SPARQL endpoints (sources) as F = ( EP , g ) , where EP = { ep 1 , … , ep k } ⊂ I is a set of IRIs that identify the SPARQL endpoints, and g : I → G a function mapping each endpoint ep i to its (default) RDF graph. Given a basic graph pattern P and a federation F , the federated query planner performs source selection, query decomposition, and join ordering to obtain a query plan. We now detail how the planner leverages the estimated CSPF in all three steps for BGPs.

Source selection and query decomposition The source selection and query decomposition step determine which subexpressions of a given BGP P should be evaluated at which members of the federation F . The output of this process is a query decomposition, which we define as follows.

The challenge of query decomposition based on estimated statistics is the fact that the planner does not know what is not captured in the estimations. For example, this is the case when determining the relevant sources. In the following, we assume a source ep i to be relevant, if there is a subexpression P ′ in the BGP P such that the evaluation of P ′ over g ( ep i ) produces solution mappings. That is, ∃ P ′ ⊆ P : ⟦ P ′ ⟧ g ( ep i ) ≠ ∅ . Our query planner leverages the estimated CSPF to determine these relevant sources. To this end, it follows a conservative strategy to distinguish between relevant and non-relevant sources. It assumes all sources to be relevant, in case none of them is relevant according to the estimated (potentially incomplete) statistics.

The source selection and query decomposition process are shown in Algorithm 1. The goal of the approach is to merge multiple triple patterns into larger subexpressions to reduce the number of subexpressions to be evaluated over the sources. Our planner focuses on subject-based star-shaped basic graph pattern. That is, BGPs where all triple patterns share the same RDF term or variable in the subject position [41]. These subject-based star-shaped basic graph patterns are obtained by the function getSubjectStars in Line 3. For each such pattern SSP of the given BGP P, the decomposer leverages the characteristic sets to determine whether any subset SSP ′ ⊆ SSP of q triple patterns can be evaluated jointly at any source (Line 7). This is the case, if for a source ep ∈ EP with F ˆ ( g ( ep ) ) = ( S C ˆ , c ˆ , m ˆ ) , there exists at least one characteristic set S ˆ ∈ S ˆ such that all predicates of SSP ′ are contained within S ˆ : preds ( SSP ′ ) ⊆ S ˆ (Line 11). In this case, the subquery SSP ′ is added to the decomposition with the corresponding relevant sources R ′ and the process continues with the remaining triple patterns of the original star-shaped BGP: SSP ∖ SSP ′ (Line 16). If SSP ′ only consists of a single triple pattern and no relevant source could be determined (Line 18), i.e. R = ∅ , all sources need to be considered as relevant R = EP . This is the case, if either the predicate p in the triple pattern does not occur in a characteristic set of any source or if p is a variable, i.e. p ∈ V . However, for the cardinality estimation in the next step, we need to be able to distinguish this case from the case where all sources are known to be relevant according to the estimated CSPF. For example, all sources could be known to be relevant for common terminology, such as rdf:type. Therefore, if the estimated statistics do not allow for determining which sources are relevant, we set the relevant sources in the decomposition to be the empty set (Line 19). Note that because potentially not all predicates are covered in the sample from which the estimated CSPF is derived, we cannot assume that no source is relevant.7

OPEN IN VIEWER

Algorithm 1:

Query decomposer

Cardinality estimation Given a query decomposition, the query planner estimates the cardinalities of all subexpressions in the decomposition. Given these estimations, the planner determines an efficient join order for the subexpressions. To this end, the subexpressions are ordered by increasing cardinality to minimize the number of intermediate results to be transferred during query execution. For a given subexpression SE i in a decomposition D, the cardinality estimation distinguishes two cases:

For the first case, we apply the StarJoinCardinality algorithm proposed by Neumann and Moerkotte [27] to estimate the cardinality for each source ep according to the estimated CSPF F ˆ ( g ( ep ) ) . As suggested in [27], we also use the absolute predicate multiplicity to compute the conditional selectivity in the case of a bound object as sel ( ? o = x ∣ ? p = p ) = 1 count ( S C ) · multiplicty ( p , S C )

We then sum up the estimations to aggregate the cardinalities across all sources: card ( SE i , R i ) = ∑ ep ∈ R i S TAR J OIN C ARDINALITY ( F ˆ ( g ( ep ) ) , SE i )

In the second case ( R i = ∅ ), the subexpression consists of a single triple pattern according to the decomposition algorithm and all sources need to be considered relevant for that triple pattern. In this case, we leverage the information from the estimated CSPF to estimate the expected number of solutions produced by the triple pattern. We distinguish the following types of triple patterns to estimate their cardinalities:

For all remaining types of triple patterns, we estimate the cardinality to be 1.

Join ordering and query plan generation After estimating the cardinalities of all subexpressions in the decomposition, the query planner iteratively builds a left-deep plan by joining subexpressions ordered by increasing cardinality. In this query plan, each tuple ( SE i , R i ) of the query decomposition is evaluated as the union of SE i over all sources in R i . The resulting solution mappings are joined for all tuples in the decomposition. This corresponds to the evaluation of the following algebraic expression. ⋈ ( SE i , R i ) ∈ D ( ⋃ r j ∈ R i ⟦ SE i ⟧ r j ) .

Limitations Note that the proposed query planner does not guarantee to obtain query plans that produce complete answers. This is due to two main reasons. First, the planner may fail to identify a source as relevant in the case that the relevant characteristic set is missing in the CSPF estimation. While the planner assumes all sources to be relevant in the case that none of the estimations include a matching predicate, it might be the case that the a CSPF estimation for one source is missing the relevant information and for another sources it does not.

Second, the greedy nature of our query decomposition approach presented in Algorithm 1 may produce query decompositions that yield incomplete results. For example, the decomposer may find a star-shaped subquery SSP ′ of SSP with size q whose predicates are in the characteristic set of one source. In this case, | R ′ | > 0 and the decomposer continues with subset of size q ′ = | todo ∖ SSP ′ | (Line 16 and Line 17), even though there might be a subset | SSP ″ | of | SSP | with | SSP ″ | = q ∗ and q ′ < q ∗ < q for which there is a relevant source. In this case, the decomposer does not identify this relevant source. This greedy approach reduces the computational effort as fewer subsets need to be considered. Yet, the algorithm may be adjusted to consider all true subsets of SSP if necessary.

We first empirically evaluate the different components of our approach to estimate the Characteristic Sets Profile Feature (CSPF). In the evaluation, we focus on the following core questions:

We first present the setup of our experiments and analyze the results in Sections 5.1.1 and 5.1.2. Based on our findings, we answer the core questions in the final discussion in Section 5.1.3.

OPEN IN VIEWER

Fig. 2.

The cumulative relative coverage curve shows the ratio of triples covered with respect to the characteristic sets ordered by decreasing relative coverage.

RDF graphs We select the six cross-domain and three Life Science RDF graphs from the FedBench benchmark [37] for our evaluation. An overview of the graphs’ properties is given in Table 3. The graphs differ in their general properties: the number of triples, the number of distinct subjects, predicates, and objects as well as the out-degree distribution. Moreover, the graphs differ with respect to their characteristic sets. The number of characteristic sets ranges from 42 to more than 160000. Theoretically, the number of potential characteristic sets in a graph is bound by the power set of its predicates. In practice, however, the number of distinct subjects in the graph is a stricter upper bound. Therefore, we provide the ratio of characteristic sets and distinct subjects ( | S | / # Subjects [ % ] ) as a measure of the characteristic sets’ diversity (higher values indicating a higher diversity). Additionally, the graphs differ in the proportion of exclusive characteristics sets. These exclusive characteristic sets, which only occur once in the graph, introduce further challenges when estimating the CSPF. If an exclusive characteristic set is sampled, the projection function likely overestimates its counts. In principle, it is unlikely to sample exclusive characteristic sets as they only occur once. However, in graphs with a large portion of those sets, the likelihood of sampling and overestimating those exclusive sets increases. Depending on the application of the estimations, it is potentially less important to correctly project the exclusive characteristic sets due to their lower coverage in comparison to other characteristic sets.

Figure 2 shows the cumulative coverage curve of the characteristic sets for all graphs. The curve plots the cumulative coverage of the characteristics sets in a graph sorted by decreasing coverage (c.f. Equation (3)). f ( x ) = ∑ S C ∈ S C x coverage ( S C , G ) , with S C x : = { S C ∈ S C ( G ) ∣ rank ( S C ) ⩽ x } , where rank ( S C ) computes the relative rank of the characteristic sets by decreasing coverage. The curve allows for visualizing the distribution of characteristic sets in a graph. A diagonal line indicates all characteristic sets covering the same number of triples. The stronger the curve is bent towards the upper left corner the more unevenly is the coverage of the characteristic sets, i.e., a few characteristic sets covering a large portion of the graph and many covering a small fraction of the graph. For instance, comparing GeoNames in Fig. 2b and NY Times in Fig. 2e, we observe that in both graphs the characteristic set with the highest coverage covers ≈ 30 % of all triples in the graph. However, the distribution of characteristic sets differs as in GeoNames 20 % of the characteristics sets cover ≈ 90 % of all triples, while in NY Times they only cover ≈ 80 % . We use the area under the cumulative coverage AUC to quantify this property (cf. Table 5).

Sampling methods We study the presented unweighted, weighted, and hybrid sampling methods. We chose β = 0.5 for the hybrid sampling method equally balancing the weighted and unweighted method. We investigate four different sample sizes defined relative to the total number of entities | E | in the graph. We chose n ′ = { 0.1 ‰ · | E | , 0.5 ‰ · | E | , 1 ‰ · | E | , 5 ‰ · | E | } (Note: 10‰ = 1 % ). We generate 30 samples per RDF graph, sampling method, and sample size resulting in a total of 30 · 9 · 3 · 4 = 3240 samples. For the sake of comparability, we reuse the samples and CSPF estimations created in this evaluation as the basis for the evaluation of our federated query planner.

OPEN IN VIEWER

Table 4

Mean similarity values δ od , δ pc , δ ac , δ rc (higher is better) and mean sampled triples ratio | H | / | G | in permille (‰) by sample size and sampling method. Best values per RDF graph and similarity measure are indicate in bold

5.1.1. Structural similarity measures

Table 4 shows the structural similarity measures out-degree δ od , predicate coverage δ pc , absolute set coverage δ ac , and relative set coverage δ rc for the different sampling methods and sample sizes. As descriptive statistics of the samples, we additionally computed the ratios of sampled triples and triples in the original graph | H | / | G | [‰]. Comparing the different sample sizes (Q1), the results show an improvement in the similarity measures with an increasing sample size in the majority of cases. More importantly, we observed that the magnitude of the improvements depends on the properties of the original graphs. For example, the overall smallest improvements are achieved for GeoNames, where the similarity w.r.t δ od , δ pc , and δ rc only slightly improves with larger sample sizes. However, for GeoNames the similarity measures are on average already on a high level in comparison to the other graphs, showing the best overall results for δ od and δ rc . Combining the results with the distribution of characteristic sets in the original graph, we find that GeoNames shows the highest AUC , the smallest characteristic set diversity, and a low exclusive set ratio. In contrast, the lowest relative set coverage δ rc values are observed for Drugbank, which also has the smallest AUC and largest characteristic sets diversity.

Interestingly, there are also few cases where a higher sample size yields worse similarity results. For instance, the out-degree similarity δ od decreases for KEGG and does not improve for ChEBI with the weighted sampling method. Again, the properties of the original graphs help explain those results (Q4). In particular, the dispersion of the out-degree distribution provides further insights. We can measure the dispersion with the coefficient of variation: cv deg + = deg std + deg ‾ +

The two graphs KEGG and ChEBI have a high dispersion of the out-degree distribution with cv deg + > 19 for ChEBI and cv deg + > 5 for KEGG. As a result, the weighted sampling method, which favors high out-degree nodes, is biased more strongly due to this graph property. Regarding the predicate coverage similarity δ pc , we also observe that an increasing sample size improves the similarities in all cases. For five graphs, all predicates are covered by at least one sampling method with the largest sample size. The remaining four graphs (Drugbank, DBpedia, LinkedMDB, and SW Dog Food) have the highest number of distinct predicates (Q4) which reduces the probability of sampling them all.

Considering the absolute ( δ ac ) and relative set coverage ( δ rc ), similar results can be observed for the majority of graphs: Even if only a few characteristic sets are sampled (low δ ac ), the number of triples covered by those sets in the original graph covered is very high (high δ rc ). Take, for example, the unweighted sampling with 5.0‰sample size for DBpedia. On average, the samples contain only 7 % ( δ ac = 0.07 ) of all characteristics sets which cover 83 % ( δ rc = 0.83 ) of the triples in the original graph. The cumulative coverage curve of the original graph (Q4) helps to explain these results. For instance, lets compare the curve for SW Dog Food (Fig. 2f) and LinkedMBD (Fig. 2d). The SW Dog Food curve indicates a more uneven distribution of characteristic sets and, as a result, even though more characteristics sets are sampled for SW Dog Food ( δ ac = 0.07 ) than for LinkedMDB ( δ ac = 0.05 ), they cover a smaller portion of the original graph: SW Dog Food δ rc = 0.38 vs. LinkedMDB δ rc = 0.90 .

Comparing the different sampling methods (Q2), we observe that the unweighted sampling method outperforms the other methods for the out-degree similarity δ od . This is due to the fact, that subjects are sampled with equal probability irrespective of their out-degree which leads to more representative samples. We illustrate this observation in Fig. 3 by comparing the characteristic sets that are obtained by the weighted and unweighted sampling methods (in color) in comparison to the characteristic sets of the original graph (in gray). The characteristic sets sampled by the weighted method (Fig. 3b) tend to have a larger set size as indicated by the rectangle, while the unweighted sampling (Fig. 3a) captures more average-sized characteristic sets.

OPEN IN VIEWER

Fig. 3.

Sampled characteristic sets for Drugbank for one sample with a n ′ = 0.5 ‰. The figures show the sampled characteristic sets in blue with respect to the number of their predicates ( | S C | ) and their count ( count ( S C ) ) on a log-scale. Indicated in gray are all sets of the original dataset.

Except for LinkedMDB, the unweighted sampling method exhibits the lowest predicate coverage similarity ( δ pc ) in comparison to the other two approaches. The highest difference between the unweighted and weighted sampling method in δ pc is measured for DBpedia, which is the graph with the largest number of distinct predicates. For the remaining graphs, the difference is smaller than 2 percentage points. Combining this observation with Fig. 3, we conclude that the unweighted sampling method fails to obtain those predicates used in characteristic sets with high degrees.10

¹⁰

The degree of a characteristic set is given by the average degree of the entities belonging to it. The degree is therefore a combination of its size (number of predicates) and the predicates’ multiplicity .

Comparing the sampling methods (Q2), similar results for absolute δ ac and relative set coverage δ rc are observed as the unweighted method is outperformed by the other methods. Similar to the predicate coverage, the δ rc values are only slightly lower. When taking the number of triples in the samples into consideration ( | H | / | G | ), we find that the weighted sampling method yields the largest subgraphs. Therefore, if we consider the structural similarity results with respect to the number of triples, we find that even though the unweighted sampling method does not yield the best overall results, it still captures the properties of the original graph at least as accurately requiring a smaller subgraph. We observe that the sample sizes also reflect the structural properties of the original graph (Q4). For instance, the out-degree and its dispersion ( cv deg + ) are reflected in the differences in the sample size between the weighted and unweighted method. For example, the samples of the weighted sampling method for the ChEBI graph with deg ‾ + = 94.55 are more than 100 times large than those of the unweighted method. Finally, the results of the structural similarity measures indicate that hybrid sampling yields samples that balance the properties of the weighted and unweighted samples. Nonetheless, it outperforms neither of the other two methods.

OPEN IN VIEWER

Fig. 4.

Box plots of the count estimation q-errors (lower is better) for each dataset, projection function, sample size and sampling method.

5.1.2. Statistical similarity measures

We now focus on the statistical similarity measures that assess the accuracy of the count and multiplicity estimations. In this evaluation, we concentrate on the q-errors due to their more natural interpretation, rather than the proposed similarity measures δ count and δ multiplicity which are the inverse of the q-error. We start by discussing the results for the counts: q-error c . The results for all RDF graphs, sampling methods, sample sizes, and projection functions are visualized in Fig. 4. To investigate the results on the level of samples, we aggregated the q-errors for each sample. Therefore, Fig. 4 shows the mean q-errors of the 30 samples per group which is computed as 1 | S ˆ | ∑ S ˆ C ∈ S ˆ q-error c ( S ˆ C )

OPEN IN VIEWER

Fig. 5.

Box plots of the q-errors (lower is better) of the predicate multiplicity estimations for each dataset, sample size and sampling method.

Similar to the structural similarity measures, the results indicate an improvement in the estimations with larger sample sizes (Q1) in the majority of cases. Regarding the projection functions, this observation holds for the basic projection function ϕ 1 for all datasets, except Drugbank. For the projection function ϕ 2 , there are more graphs for which the increased sample size does not yield better count estimations. Finally, especially for the projection function ϕ 3 , we observe that increasing sample size does not necessarily reduce the q-errors. Regardless of the projection function, when investigating larger sample sizes, we also need to consider the percentage of characteristic sets that are sampled as indicated by the absolute set coverage δ ac in Table 2. For example, if we consider the SW Dog Food graph, we observe less accurate estimation for the projection function ϕ 1 and ϕ 2 with increasing sample size. However, when comparing the number of sampled characteristics sets, we find that the largest samples capture ≈ 36 times more characteristic sets than the smallest samples ( ≈ 0.18 % vs. ≈ 6.5 % ).

Comparing the different sampling methods (Q2), we observe a tendency of the smaller q-errors for the unweighted sampling method, especially for the basic projection function ϕ 1 . At the same time, the results also show that the unweighted sampling method is substantially outperformed for DBpedia and Drugbank. This could be due to the large portion of exclusive characteristic sets that are sampled more frequently by the unweighted method. For graphs with fewer exclusive characteristic sets, such as KEGG and Jamendo, the unweighted sampling method yields better results.

Considering the characteristic set diversity of the graphs | S C | / # Subjects (Q4), we find that the projection function ϕ 3 yields better results that are comparable or better than the other projection functions for graphs with a larger diversity (e.g., Drugbank, SW Dog Food). For graphs with small diversity, such as GeoNames or Jamendo, ϕ 3 yields the highest q-errors w.r.t. the other projection functions. The results of the other statistic-enhanced projection function ϕ 2 , are not as strongly affected by the characteristic set diversity and yields the best results on average. Consequently, in case the additional high-level statistics for the statistic-enhanced projection functions are available, the function ϕ 2 should be chosen over ϕ 3 (Q3). While the basic projection function ϕ 1 is slightly outperformed by ϕ 2 , it still yields comparable results in the majority of cases without requiring additional statistics.

Summarizing the results across all datasets for the count q-errors (cf. Fig. 4j), we observe that an increase in sample size (Q1) reduces the q-errors while simultaneously generating estimations for more characteristic sets. The unweighted sampling method (Q2) yields the lowest q-errors in the majority of cases and ϕ 2 (Q3) shows the best results regarding the average q-errors (lower median) and their dispersion (fewer outliers).

Next, we focus on the estimations of the predicate multiplicities within the characteristic sets. Analogous to the count statistic, we concentrate on the q-errors in the evaluation and aggregate the values per sample by computing the mean over all its characteristic sets: 1 | S ˆ | ∑ S ˆ C ∈ S ˆ q-error m ( S ˆ C )

The box plots of the samples’ mean q-errors are shown in Fig. 5 for all graphs, sample sizes, and sampling methods. The first obvious observation is the substantially lower q-errors in comparison to the count statistic. This is because the range of the value to be estimated is lower. Typically, the same predicate is only used a few times for the same subject, with some exceptions that occur multiple times, such as rdf:type or rdfs:label. This is also reflected in the absolute differences, where the multiplicity q-errors are less affected by the sampling method and sample size. This indicates a uniform predicate usage within the characteristic sets with few outliers. In line with the results for the count statistic, in the majority of cases, an increasing sample size (Q1) improves the results. The results for the different sampling methods show better results for the unweighted sampling method for the majority (seven) of the graphs. The weighted sampling method shows slightly better results for DBpedia and Drugbank. Comparable to the results for the count statistics, the hybrid sampling method finds a balance between the other two sampling methods. Furthermore, the results indicate that multiplicities are more challenging to estimate for graphs with a high out-degree dispersion (Q4), such as ChEBI and KEGG. The best overall estimations are observed for GeoNames, which also has the lowest out-degree dispersion ( cv deg + = 0.19 ).

Concluding, as the summarized results in Fig. 5j show, the multiplicity statistic are estimated more accurately than count statistic with improving estimations for larger sample sizes (Q1), marginal differences comparing the sampling methods (Q2), and less diverse results for the different graph (Q4).

5.2. Federated query planner evaluation

After investigating the effectiveness of our approach to estimate profile features according to the similarity measures, we now focus on a particular application of the estimated features. We, therefore, study the performance of the proposed federated query planning approach that relies on CSPF estimations. In particular, we want to study the following core questions.

We begin by introducing our experimental setup. We then provide a detailed evaluation and discussion of our experimental results in Section 5.2.1, which we conclude by answering our core questions in Section 5.2.2.

Benchmark and sampled statistics We study the effectiveness of the proposed query planning approach using the FedBench benchmark [37]. The benchmark consist of the 9 interlinked RDF graphs that are listed in Table 3, and which were also investigated in the previous evaluation. We selected 25 queries from the Cross Domain (CD1-CD7), Life Science (LS1-LS7), and Linked Data (LD1-LD11) queries. We used a subset of the estimated CSPF generated from the samples of the previous evaluation. In particular, we only considered the weighted and unweighted sampling methods, leading to a total of 2160 estimated CSPF.11

As a baseline, we additionally computed the complete CSPF for all RDF graphs. In accordance with previous approaches [26,27], we reduce the number of characteristics sets in the profile feature to a maximum of 10000 characteristic sets per RDF graph.

Implementation We implemented the proposed federated query planning approach based on CROP [18] and nLDE [3]. We extended the query engine with an access operator for SPARQL endpoints and implemented our source selection, query decomposition, and left-linear query plan optimizer to create query execution plans. The RDF graphs in the federation are deployed with a single SPARQL endpoint per graph using Virtuoso v7.2..12

We study the performance on each of the 30 samples for the 2 sampling methods (weighted and unweighted), 4 sample sizes ( n ′ = { 0.1 ‰ · | E | , 0.5 ‰ · | E | , 1 ‰ · | E | , 5 ‰ · | E | } ), and 3 projection function ( ϕ 1 , ϕ 2 , ϕ 3 ). This results in a total of 30 · 2 · 4 · 3 = 720 configurations for the estimated CSPF. An additional configuration is given by the complete statistics. Moreover, we repeated the execution of each query (25) in each configuration 3 times, resulting in a total of 3 · 25 · 721 = 54075 query execution measurements. We set a timeout of 120 seconds per query for the engine.

Evaluation metrics We study the following metrics:

Execution Time: Elapsed time spent by the engine to complete the evaluation of a query in seconds. This includes time spent on query planning.

5.2.1. Experimental results

An overview of the experimental results is provided in Table 5. The table shows the mean and median execution times, the mean number of requests, the mean percentage of answers produced, and the mean percentage of query executions reaching the timeout. We start with the results for the unweighted sampling method (Q5). Regarding the mean execution time, we observe the best performance for the unweighted sampling method with the largest sample size 5.0‰and the projection function ϕ 1 . This configuration overall outperforms the other sampling methods and also the baseline with complete statistics. The execution times for the other projection functions ϕ 2 and ϕ 3 are only slightly higher in this case (Q7). Also, these configurations yield the lowest number of requests while producing 100% of all answers with none of the executions reaching the timeout. Moreover, a continuous improvement in all evaluation metrics with increasing sample size (Q6) is visible for the unweighted sampling method. Both the mean execution times and the mean number of requests are about 5 times lower for the largest sample size. At the same time, the answer completeness increases by almost 30 percentage points, and the number of queries that reach a timeout are reduced from 3.6 % to 0 % . These results indicate that larger sample sizes in combination with the unweighted sampling method allows for obtaining more efficient query plans since the planner can identify relevant sources more accurately, larger subexpression, and a more efficient join order.

OPEN IN VIEWER

Table 5

Overview for the FedBench Queries. Mean and median execution times, mean number of requests, mean percentage of answers produces, and mean percentage of queries reaching the timeout. Best values per table are indicated in bold

	Unweighted												Baseline
	0.1‰			0.5‰			1.0‰			5.0‰			1000‰
	ϕ 1	ϕ 2	ϕ 3	ϕ 1	ϕ 2	ϕ 3	ϕ 1	ϕ 2	ϕ 3	ϕ 1	ϕ 2	ϕ 3	–
Mean execution time [s]	7.09	6.69	6.77	4.75	4.69	4.65	3.33	3.34	3.33	1.53	1.54	1.54	8.43
Median execution time [s]	0.66	0.63	0.64	0.42	0.44	0.44	0.42	0.43	0.46	0.62	0.61	0.63	1.01
Mean number of requests	241.95	229.97	229.76	159.46	159.06	155.02	113.94	113.95	111.2	45.69	45.69	45.7	173.92
Answers [%]	72.13	72.09	72.13	90.13	90.13	90.09	96.53	96.53	96.53	100.0	100.0	100.0	100.0
Timeouts [%]	3.6	3.6	3.6	1.47	1.47	1.47	0.93	0.93	0.93	0.0	0.0	0.0	4.0

	Weighted												Baseline
	0.1‰			0.5‰			1.0‰			5.0‰			1000‰
	ϕ 1	ϕ 2	ϕ 3	ϕ 1	ϕ 2	ϕ 3	ϕ 1	ϕ 2	ϕ 3	ϕ 1	ϕ 2	ϕ 3	–
Mean execution time [s]	9.24	7.61	8.46	2.84	1.89	1.98	4.45	4.13	4.49	6.08	6.11	6.45	8.43
Median execution time [s]	0.56	0.55	0.56	0.43	0.45	0.56	0.57	0.58	0.68	0.76	0.77	0.77	1.01
Mean number of requests	170.94	171.75	174.21	64.08	64.14	64.16	178.27	178.18	192.06	256.97	257.02	257.32	173.92
Answers [%]	81.33	81.73	81.69	97.2	98.0	98.0	96.8	97.07	96.8	96.0	96.0	96.0	100.0
Timeouts [%]	5.73	4.36	5.07	1.07	0.27	0.27	2.8	2.53	2.8	4.13	4.13	4.13	4.0

In contrast, the performance results differ for the weighted sampling method (Q5). The weighted sampling method with the second smallest sample size (0.5‰) yields the best performance. When comparing the results for the projection functions (Q7), we find similar results as for the unweighted sampling method, with only slight differences for the different projection functions. The results for the sample size (0.5‰) show the lowest average execution times and number of requests. Moreover, the query execution plans obtained for this sample size yields the highest answer completeness with ≈ 98 % and the fewest queries that reach the timeout ( 0.27 % ). With an increasing sample size > 0.5 ‰, the mean execution times increase. However, when combining the observations of the mean with the median execution times, we find that the increase in the median execution times is substantially smaller. This indicates, that for a large number of queries the execution time only slightly increases, while for a few queries the execution time is significantly higher.

Hence, we focus on the results for the weighted sampling method in more detail to investigate the following observations: (i) a larger sample size in the weighted sampling does not entail better query execution performance, and (ii) the query planner with complete statistics is outperformed by the majority of configurations with estimated statistics. The mean execution times and mean number of requests (both log scale) per query and sample size for the weighted sampling method (all projection functions) are shown in Fig. 6. The trend of an increase in execution time with larger samples sizes is observable especially for the queries CD4 and LS3. For the majority of the remaining queries, we see a similar or even better performance with larger sample sizes according to execution times and number of requests. The observation that few outliers (especially CD4 and LS3) skew the overall average performance results is also true for the performance of the planner with the complete statistics.13

¹³

Note that the query planner is designed to handle estimated statistics. Therefore, a query planner that fully leverages the complete statistics, e.g., with the (federated) characteristic pairs, would potentially obtain a more efficient query plan.

Taking a closer look at the results for LS3, we find that for the sample size 0.5‰, the engine times out 3 times. Intriguingly, for the largest sample size (5.0‰) and also for the complete statistics, it reaches the timeout for all 90 executions. Similarly, for query CD4, larger sample sizes also lead to several executions reaching the timeout. The reason for these results lies in the cardinality estimation approach. We observe that CD4 and LS3 have a selective triple pattern in which the object is bound. The StarJoinCardinality algorithm tends to overestimate the cardinalities for stars with such triple patterns and the tendency of overestimating is higher with more characteristics sets that are taken into consideration.14

¹⁴

This is due to the fact that the number of relevant characteristic sets for a triple pattern ( ? x p o ) increases while the conditional selectivity sel ( ? o = x ∣ ? p = p ) only slightly decreases.

As a result, this overestimation in the query CD4 and LS3 leads to a sub-optimal join ordering. For example, Fig. 7 shows the join ordering for CD4 obtained with one weighted sample with size 0.5‰and 5.0‰. The estimated cardinalities (in blue) and true cardinalities (in parenthesis) in this example reveal that due to the overestimation of the subexpression with the bound object (“Tarzan”), the planner chooses a sub-optimal join order in the case of the larger sample.

OPEN IN VIEWER

Fig. 6.

Mean performances for all FedBench queries for the weighted sampling method and averaged across all projection functions.

OPEN IN VIEWER

Fig. 7.

CD4: Join Ordering obtained by the query planner based on the estimated CSPF from one of the weighted samples. Indicate below is the estimated cardinality (blue) and the actual cardinality(in brackets).

OPEN IN VIEWER

Fig. 8.

Relation between the answer completeness and the number of subexpression of the query plans and the structural similarity measures for the estimated CSPF. Sample size are indicated in color.

Finally, we want to examine whether the proposed structural similarity measures (c.f. Section 3.6) reflect the performance of the query plans obtained by our planning approach (Q8). To this end, we compare the impact of the out-degree similarity ( δ od ), predicate coverage ( δ pc ), absolute set coverage ( δ ac ), and relative set coverage ( δ rc ) on the query decompositions of our query planner. Specifically, we focus on their impact on the number of subexpressions in the decomposition and the percentage of answers produced by the query plans. For each of the 720 configurations, we compute the mean similarity measure values for all RDF graphs in the federation and the mean answer completeness and number of subqueries for all queries in the benchmark. Figure 8 shows the relation between these measures. As a quantitative measure to assess whether the values are correlated, we compute the Pearson correlation coefficient ( PCC ). We start with the number of subexpressions in the query decompositions as a way to assess how well the predicate co-occurrence is captured in the profile estimations. Fewer subexpressions indicate that the query planner can merge more triple patterns into larger subexpressions to be evaluated jointly according to the characteristic sets in the CSPF (Line 11 in Algorithm 1). This allows for reducing the number of requests as well as the number of intermediate results that need to be transferred. Inspecting the number of subexpressions (Fig. 8a), there is no correlation between the out-degree similarity and the number of subexpression with PCC = − 0.01 . For the other measures, however, there is a negative correlation with PCC = − 0.854 for δ pc , PCC = − 0.746 for δ ac , and PCC = − 0.814 for δ rc . The correlation indicates higher similarity values yield decomposition with fewer subexpression. Hence, these measures reflect how well the predicate co-occurrence is captured in the profile feature estimations, allowing the query planner to obtain efficient query plans.

Similar to this observation, the results in Fig. 8b show that, there is no correlation between the answer completeness and the out-degree similarity δ od with PCC = 0.039 . For the other similarity measures, we observe a positive correlation of the similarity measure and the answer completeness, which is also reflected in the correlation coefficients with PCC = 0.856 for δ pc , PCC = 0.643 for δ ac , and PCC = 0.743 for δ rc . The results indicate that estimated characteristic sets profile features with higher predicate and (absolute and relative) characteristic sets coverage help the query planner to obtain query plans that produce more answers.

6.1. Statistical profiling

In the realm of statistical feature profiling for RDF graphs, a variety features and tools to assess them have been proposed. Zloch et al. [44] investigate statistical features of RDF graphs with the focus on the topological graph structure including degree-based, edge-based, centrality, and descriptive statistical measures. Consequently, these measures are not specific to RDF graphs and, in contrast to our work, do not capture the semantics on the instance or schema level of the data. Complementary, Fernández et al. [14] focus on RDF-specific measures. They propose various schema- and instance-level metrics to characterize RDF datasets that incorporate the particularities of RDF graphs. The metrics and the resulting statistics are tailored to the development of better RDF data storage solutions including data structures, indexes, and compression techniques by considering RDF data characteristics.

LODStats [6] is a statement-stream-based approach for gathering comprehensive statistics of RDF datasets. They present 32 instance- and schema-level statistical criteria covering both RDF-specific metrics as well as topological graph metrics. The authors aim to improve reuse, linking, revising, or querying Linked Open Data sources but do not discuss specific applications.

ProLOD + + [1] is a tool to support various profiling, mining, and cleansing functionalities for RDF datasets. It is an extension of ProLOD [7] that computes profiles at domain, schema, and data (i.e., instance) level of datasets. ProLOD + + supports browser-based visualizations of these characteristics with the goal to better support data consumers in understanding, consuming, and integrating Linked Open Data sources.

Finally, ExpLOD [20] is a tool for generating summaries of RDF datasets combining text labels and bisimulation contractions. These summaries include schema-level statistical information such as the class, predicate, and interlinking usage in the dataset. Similar to ProLOD + + [1], the goal of the created summaries is to facilitate the understanding the RDF usage, such as vocabulary usage and links between datasets.

In this work, we propose a novel schema-level statistical profile feature based on characteristic sets that captures both the topological structure of the graph as well as its semantics. This statistical feature has not yet been addressed in related work. We demonstrate an application of estimations of this feature in federated query planning.

6.2. Graph sampling

Next, we focus on sampling approaches for graphs. We start by introducing related work on sampling large graphs and networks. Thereafter, we analyze RDF-specific sampling approaches and their applications.

Graph sampling A variety of approaches for sampling large non-RDF graphs have been proposed. Leskovec et al. [21] provide an overview of approaches suitable for obtaining representative samples from large graphs for scale-down sampling for static graphs and back-in-time sampling for evolving graphs. They consider the distributions of different structural properties of the graphs, denoted static graph patterns, as the criteria for evaluating the representativeness of the samples for scale-down sampling. These static graph patterns include, among others, the in-degree, out-degree, and cluster coefficient distributions. As a similarity measure to assess the representativeness of samples, they use the Kolmogorov-Smirnov D-statistic of the graph patterns’ distribution. They present three major categories of sampling approaches: (i) random node selection, (ii) random edge selection, and (iii) graph exploration. The results of their evaluation reveal that there is no single best solution and the authors conclude that an appropriate sampling algorithm and sample size depends on the specific application.

Ahmed et al. [5] present a detailed framework for the problem of graph sampling that focuses on large scale graphs. They identify two models of computation that are relevant when sampling from large graphs. The static model of computation allows for randomly accessing any location in the graph. The streaming model of computation merely allows for accessing edges in a sequential stream of edges. In their evaluation, the authors show that the proposed methods preserve key graph statistics of the graph (e.g., degree distributions, cluster coefficient distribution). Moreover, they demonstrate low space- and runtime-complexity that is in the order of edges in the sample for these methods.

Our sampling methods are a special case scale-down sampling of random node selection approaches according to [21], that only sample specific nodes, the entities of an RDF graph. However, in contrast to traditional graph sampling, we aim to generate representative samples for our specific statistical graph feature. Hence, the representativeness of a sample is given by the accuracy of the profile feature estimation.

RDF graph sampling Sampling approaches for RDF graphs have been proposed and applied to different problems as well. In the following, we will analyze example applications and show how sampling approaches are chosen according to those applications.

Debattista et al. [11] propose approximating specific quality metrics for large, evolving datasets based on samples. They argue that the exact computation of some quality metrics is too time-consuming and that an approximation is usually sufficient. In particular, they apply a sampling-based approach for the quality metrics (i) dereferenceability of URIs, and (ii) links to external data providers. They use the reservoir sampling approach [42] which randomly selects n items from a set of N elements with the equal probability 1 / N . In their evaluation, the authors studied how well the ratios measured by quality metrics can be estimated based on the samples. Therefore, the similarity of estimated and true ratio reflects their notion of representativeness. In contrast to our work, the authors apply sampling to reduce the computational effort for quality metrics, and therefore, the sampling methods do not need to capture the semantics or structural features of the dataset.

In their work, Rietveld et al. [34] aim to obtain samples that entail as many of the original answers to typical SPARQL queries. They use query logs from SPARQL endpoints to determine such typical queries. The sampling pipeline proposed by the authors consists of four steps and aims to obtain the parts of the graph that are relevant for answering the queries. First, they rewrite the original RDF graph as a directed unlabeled graph. On the resulting graph, they then compute the structural graph metrics PageRank, in-degree, and out-degree for all nodes. Thereafter, they use the structural graph metrics to rank the triples in the graph and generate the sample by selecting the top-k percent of all triples. The authors aim to obtain samples with a “more manageable size” [34] that produce answers to common SPARQL queries and hence, the samples’ representativeness is measured by the recall for those queries. As a result, the resulting samples may be biased towards more prominent entities in the graphs and less suitable to capture long-tail entities [8]. Different from our work, the goal is obtaining relevant samples which allow answering common queries. Therefore, these samples are not representative in our sense with regards to the semantic and statistical features.

Soulet et al. [39] focus on analytical queries, which are typically too expensive to be executed directly over public SPARQL endpoints. They propose separating the computation of such expensive queries by executing them over random samples of the RDF graph. Due to the properties of the queries, the values for the aggregations converge as they are executed over increasingly larger portions of the graph. As a result, the authors do not rely on the necessity of each sample to be representative according to the aggregates, but rely on the convergence of the aggregates towards the true value with an increasing number of samples. Similar to Soulet et al. [39], our work is motivated by the restrictions that occur especially in decentralized scenarios with large, evolving datasets where it is not feasible to have local access to every dataset. Different from [39], we aim to sample the data in such a fashion that a single sample can be used to estimate the statistical profile feature and do not rely on the convergence properties induced by increasing sample sizes.

6.3. Profiling-based federated query processing

We demonstrate how the profile features estimations can be applied to federated query processing. Therefore, in this section, we analyze other types of pre-computed statistics leveraged by federated query engines to determine efficient plans.

ANAPSID [4] is an adaptive federated query engine that leverages a Catalog with high-level statistics on the members in the federation. This catalog contains a list of the predicates present in each data member in the federation and is used by the engine to perform the source selection and query decomposition.

More fine-grained statistics are leveraged by the following approaches. SPLENDID [15] uses indexes built from VoID descriptions for query planning. These indexes additionally hold information on the occurrences of predicates within the classes of the sources. In combination with ASK queries, the indexes are used to decompose the query into subqueries to be evaluated at the sources in the federation. HiBISCuS [35] is a source selection approach that employs data summaries to prune the relevant sources. The data summaries are comprised of the capabilities of a data source which consists of the subject and object authorities for all predicates in a data source. These summaries allow for deciding which source will contribute to the final query answers according to the authorities of the subjects and objects they contain. CostFed [36] is a cost model-based planner using an index with statistic profiles on the sources, so-called Data Summaries. They extend the data summaries from HiBISCus with additional information on both the distribution of objects and subjects per predicates. In addition to source selection and query decomposition, the additional statistics are used in their cost model to estimate the cost of alternative query plans. Similar to CostFed, SemaGrow [10] leverages a metadata to estimate the cost of alternative query plans. The statistics include the number of distinct subjects, predicates, and objects as well as the total number of triples that match a given triple pattern. These statistics are used to estimate the join cardinalities in their cost model. Finally, Odyssey [26] relies on the characteristic sets of the federation members. Additionally, the characteristics pairs and federated characteristic pairs are used to capture links between entities within and across the federation members.

Our approach also uses statistics to perform source selection, query decomposition, and join ordering to obtain efficient query plans. Specifically, our approach leverages characteristics sets similar to Odyssey [26]. In contrast to the aforementioned approaches, however, our approach does not require the complete statistics but is specifically designed to handle estimated statistics from RDF graph samples. As a result, our approach aims to leverage the estimated statistics as much as possible and is also able to cope with potentially misestimated or missing statistics.