Rakebul Hasan
email: hasan.rakebul@inria.fr

Fabien Gandon
email: fabien.gandon@inria.fr

A Machine Learning Approach to SPARQL Query Performance Prediction

In this paper we address the problem of predicting SPARQL query performance. We use machine learning techniques to learn SPARQL query performance from previously executed queries. Traditional approaches for estimating SPARQL query cost are based on statistics about the underlying data. However, in many use-cases involving querying Linked Data, statistics about the underlying data are often missing. Our approach does not require any statistics about the underlying RDF data, which makes it ideal for the Linked Data scenario. We show how to model SPARQL queries as feature vectors, and use k-nearest neighbors regression and Support Vector Machine with the nu-SVR kernel to accurately predict SPARQL query execution time.

I. INTRODUCTION

In the recent years, we have seen a sharp growth of publishing Linked Data from community driven efforts, governmental bodies, social networking sites, scientific communities, and corporate bodies [START_REF] Bonatti | Robust and scalable linked data reasoning incorporating provenance and trust annotations[END_REF]. Data publishers from these different domains publish their data in an interlinked fashion 1 using RDF data model and provide SPARQL endpoints to enable querying their data. This global space presents tremendous potential for large-scale data integration over cross domain data to support a new generation of intelligent application [START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF]. In this context, it increasingly important to develop efficient ways of querying Linked Data [START_REF] Huang | Scalable SPARQL querying of large RDF graphs[END_REF]. Central to this problem is knowing how a query would behave prior to executing the query [START_REF] Hartig | The sparql query graph model for query optimization[END_REF]. This enables us to adjust our queries accordingly.

Current generation of SPARQL query cost estimation approaches are based on data statistics and heuristics. Statisticsbased approaches have two major drawbacks in the context of Linked Data [START_REF] Tsialiamanis | Heuristics-based query optimisation for SPARQL[END_REF]. First, the statistics (e.g histograms) about the data are often missing in the Linked Data scenario because they are expensive to generate and maintain. Second, due to the graph-based data model and schema-less nature of RDF data, what makes effective statistics for query cost estimation is unclear. Heuristics-based approaches generally do not require any knowledge of underlying data statistics. However, they are based on strong assumptions such as considering queries of certain structure less expensive than others. These assumptions may hold for some RDF datasets and may not hold for others.

We take a rather pragmatic approach to SPARQL query cost estimation. We learn SPARQL query performance metrics from already executed queries. Recent work [START_REF] Ganapathi | Predicting multiple metrics for queries: Better decisions enabled by machine learning[END_REF], [START_REF] Gupta | PQR: Predicting query execution times for autonomous workload management[END_REF], [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF] in database research shows that database query performance metrics can be accurately predicted without any knowledge of data statistics by applying machine learning techniques on the query logs of already executed queries. Similarly, we apply machine learning techniques to learn SPARQL query performance metrics from already executed queries. SPARQL query optimizers can use these predictions to choose among alternative query plans. In addition, they can be also used for workload allocation or to meet specific QoS targets [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF]. We consider query execution time as the query performance metric in this paper.

The rest of this paper is structured as following: in section II we briefly introduce the RDF data model and the SPARQL query language. In section III we describe our approach to modeling SPARQL query execution. In section IV we present our experiments and results. In section V we describe the related work. Finally, in section VI we conclude and outline the future work.

II. PRELIMINARIES

Before we present our approach to query performance prediction, we briefly introduce the RDF data model and the SPARQL query language. For more detailed introduction to RDF and SPARQL, please refer to the cited W3C specification documents.

The Resource Description Framework (RDF) data model is a W3C recommended standard for representing information about resources in the World Wide Web [START_REF]RDF 1.1 concepts and abstract syntax[END_REF]. RDF is a graphbased data model where vertices represent entities and edges represent relationships between entities.

Definition 1 (RDF graph). Let I be the set of IRIs, L be the set of literals, and B be the set of blank nodes. An RDF triple (s,p,o) is a member of the set (I ∪B)×I ×(I ∪L∪B). An RDF graph is a set of RDF triples. For an RDF triple (s,p,o), the element s is called subject, the element p is called predicate, and the element o is called object. SPARQL is the W3C recommended query language for RDF. As the SPARQL 1.1 specification describes [START_REF]SPARQL 1.1 Query Language[END_REF], SPARQL query solving is based around graph pattern matching. SPARQL queries allow specifying sets of triple patterns know as basic graph patterns. Triple patterns are similar to RDF triples but the subject, predicate, and object can be variables. A basic graph pattern may match a subgraph from the RDF data and substitute the variables by RDF terms from that matched subgraph. The native SPARQL query engines perform a series of steps to execute a query [START_REF]SPARQL 1.1 Query Language[END_REF]. First, parsing the query string into an abstract syntax form. Next, transforming the abstract syntax to SPARQL abstract query. Finally, optimizing and evaluating the SPARQL abstract query on an RDF dataset.

Definition 2 (SPARQL abstract query). A SPARQL abstract query is a tuple (E, DS, QF) where E is a SPARQL algebra expression, DS is an RDF dataset, QF is a query form.

The algebra expression E is evaluated against RDF graphs in the RDF dataset DS. The query form QF (SELECT, CONSTRUCT, ASK, DESCRIBE) uses the solutions from pattern matching to provide result sets or RDF graphs. The algebra expression E includes graph patterns and operators such as FILTER, JOIN, and ORDER BY

(T ∪ V ) × (I ∪ V ) × (T ∪ V ). The set of RDF terms T is the set I ∪ L ∪ B.
The set V is the set of query variables where V is infinite and disjoint from T .

A group graph pattern combines all other types of graph patterns. An optional graph pattern contains a graph pattern which is optional to match for a query solution. Alternative graph patterns provide a means to take union of the solutions of two or more graph patterns. Patterns on named graphs provide a means to match patterns against graphs when querying a collection of graphs. The outer-most graph pattern in a SPARQL query is known as the query pattern. A query pattern is a group graph pattern.

III. MODELING SPARQL QUERY EXECUTION

As in the common machine learning approaches, our query performance prediction approach includes two main phases: training and testing. In the training phase, we derive a prediction model from a training dataset containing previously executed queries and the observed performance metric values (execution times) for those queries. We represent the queries as feature vectors. The goal of the training phase is to create an accurate model that maps the feature vectors to the performance metric data points. We use regression for this purpose. We define feature vectors, x = (x 1 , x 2 , ...x n ), where x ∈ R n and each x i is a SPARQL query feature. The performance metric, query execution time, is the variable y. We learn a function f (x) = y, i.e. the function maps a feature vector x to y, using regression. We provide more details on the types of regression we use in section IV-C. In the testing phase, we use the trained model to predict query performance metric values for unforeseen queries. Additionally, we tune our model parameters using cross-validation. We use two types of query features: SPARQL algebra features and graph pattern features.

A. SPARQL Algebra Features

We use the frequencies of all the SPARQL algebra operators except the SLICE operator as query features. The SLICE operator is the combination of OFFSET and LIMIT SPARQL keywords. We use the sum of all the SLICE operator cardinalities appearing in the algebra expression as the feature representing the SLICE operator. In addition, we use two more features: the depth of the algebra expression tree and the number of triple patterns. Figure 1 shows an example of extracting the SPARQL algebra features vector from a SPARQL query. First we transform a query into an algebra expression tree. Then we extract the features and represent the query as a feature vector. We use the Jena ARQ SPARQL parser 3 to transform query strings to SPARQL algebra expressions.

B. Graph Pattern Features

The SPARQL algebra features do not represent graph patters appearing in SPARQL queries. Transforming graph patterns to vector space is not trivial because the space is infinite. To address this, we create a query pattern vector representation relative to the query patterns appearing in the training data. First, we cluster the structurally similar query patterns in the training data into K gp number of clusters. The query pattern in the center of a cluster is the representative of query patterns in that cluster. Second, we represent a query pattern as a K gp dimensional vector where the value of a dimension is the structural similarity between that query pattern and the corresponding cluster center query pattern. To compute the structural similarity between two query patterns, we first construct two graphs from the two query patterns, then compute the graph edit distance [START_REF] Bunke | Similarity measures for structured representations[END_REF] between these two graphs. We compute the structural similarity by inverting the edit distance. The graph edit distance between two graphs is the minimum amount of distortion needed to transform one graph to another. The minimum amount of distortion is the sequence of edit operations with minimum cost. The edit operations are deletions, insertions, and substitutions of nodes and edges. A well known method for computing graph edit distance is using the A* search algorithm to explore the state space of possible mappings of the nodes and edges of the source graph to the nodes and edges of the target graph. However, the computational complexity of this edit distance algorithm is exponential in the number of nodes of the involved graphs, irrespective of using A* search with a heuristic function to govern the tree traversal process. Therefore we use the polynomial time suboptimal solution of graph edit distance that Riesen and Bunke [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF], [START_REF] Riesen | A novel software toolkit for graph edit distance computation[END_REF] propose. The computational complexity this polynomial time suboptimal solution is O n 3 , where n is the number of nodes of the involved graphs. To construct a graph from a query pattern, we take all the triple patterns in the query pattern and construct a graph from these triple patterns. As in RDF graphs, the subject and the object of a triple pattern represent vertices of the graph and the predicate represents an edge of the graph. After constructing such a graph, we replace the labels of vertices and edges representing variables by a fixed symbol -the symbol '?'. This ensures that the graph has separate vertices and edges for each variable appearing in the query but an unified labeling. We call such a graph a query graph. Figure 2 shows an example of extracting graph pattern features for a query. First step shows the constructed query graph. The clustered queries box shows the clusters of training queries where each circle is a cluster of query graphs with their cluster centers shown in blue color. We use the k-mediods [START_REF] Kaufman | Clustering by means of medoids[END_REF] clustering algorithm to cluster the query graphs of training data. We use k-mediods because it chooses data points as cluster centers and allows using an arbitrary distance function. As we mention before, we use the suboptimal graph edit distance algorithm as the distance function for k-mediods. For the K gp dimensional vector representation of query pattern, we compute the structural similarity between a query graph p i and the k th cluster center query graph C(k) as below:

sim(p i , C(k)) = 1 1 + d(p i , C(k)) (1)
The term d(p i , C(k)) is the graph edit distance between query graphs p i and C(k). This formulation gives us a similarity score within the range of 0 to 1. A similarity score of 0 being the least similar and a score of 1 being the most similar.

The extracted feature vector in figure 2 shows the computed similarity values using equation 1 for the example query.

IV. EXPERIMENTS AND RESULTS

We use the DBPSB benchmark [START_REF] Morsey | Dbpedia SPARQL benchmark performance assessment with real queries on real data[END_REF] queries on a Jena-TDB triple store [START_REF] Owens | Clustered TDB: A clustered triple store for Jena[END_REF] to evaluate our approach. DBPSB includes 25 query templates which cover most commonly used SPARQL query features in the queries sent to DBPedia4 . We generate our training, validation, and test queries from these query templates. We use query execution time as the query performance metric. The details of our experimental setup is as below.

A. Triple Store and Hardware

We use Jena-TDB 1.0.0 as a triple store. We allow Jena-TDB to use 16 GB of memory. We execute all the queries in a commodity server machine with a 4 core Intel Xeon 2.53 GHz CPU, 48 GB system RAM, and Linux 2.6.32 operating system.

B. Datasets

As the RDF dataset, we use the DBpedia 3.5.1 dataset with 100% scaling factor -provided by the DBPSB benchmark framework. We generate our training, validation, and test queries from the 25 DBPSB query templates. To generate queries, we assign randomly selected RDF terms from the RDF dataset to the placeholders in the query templates. We generate 205 queries for each template and then execute them to build our training, validation, and test datasets. Before executing the queries, we restart the triple store to clear the caches. Then we execute total 125 queries in our warm-up phase to measure query performance under normal operational conditions. Our warm-up queries include the first 5 queries from each of the 25 templates. To generate the training queries, we execute the next 120 queries from each template and take the first 60 queries for each template which return at least 1 result and finish executing within a reasonable time. We specify a 300 second timeout for a query execution. We follow the same process to generate 20 validation queries from the next 40 queries for each template and 20 test queries from the last 40 queries for each template. In this setting, none of the queries from template 2, 16, and 21 returned any result. All the queries from template 20 were interrupted because of timeout. This process resulted 1260 training queries, 420 validation queries, and 420 test queries. We execute each of these training, validation, and test queries 5 times and record the average execution time in milliseconds (ms) for each query. Figure 3 shows the average, minimum, and maximum execution times for the queries from our test dataset. As the figure shows, we have a mix of long and short running queries. Queries belonging to templates 4, 10, and 24 have more than 1000 ms of average execution time. The queries from the other query templates have less than 1000 ms of average execution time.

C. Prediction Models

To predict query execution time, we experiment with two regression models. We first experiment with Weka's [START_REF] Hall | The WEKA data mining software: an update[END_REF] implementation of k-nearest neighbors (k-NN) regression [START_REF] Aha | Instance-based learning algorithms[END_REF], [START_REF] Altman | An introduction to kernel and nearest-neighbor nonparametric regression[END_REF]. The k-NN algorithm predicts based on the closest training data points. It uses a distance function to compute these closest data points. We use Euclidean distance as the distance function in our experiments. For predictions, we use the weighted average of the k nearest neighbors -weighted by the inverse of the distance from the querying data point. This ensures that the nearby neighbors contribute more to the prediction than the faraway neighbors. We use the k-dimensional tree (k-d tree) [START_REF] Friedman | An algorithm for finding best matches in logarithmic expected time[END_REF] data structure to compute the nearest neighbors. For N training samples, k-d tree can find the nearest neighbor of a data point with O (log N ) operations. We also experiment with the libsvm [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] implementation of Support Vector Machine (SVM) with the nu-SVR kernel for regression [START_REF] Shevade | Improvements to the SMO algorithm for SVM regression[END_REF]. The approach in SVM regression is to map the features to a higher dimensional space and perform a regression in that space. The predictions in SVM are based on a subset of data points known as support vectors.

D. Evaluation Metrics

We use the coefficient of determination, denoted as R 2 , to evaluate our models. R 2 is a widely used evaluation measure for regression. R 2 measures how well future samples are likely to be predicted. We compute R 2 as:

R 2 (y, ŷ) = 1 - n i=1 (y i -ŷi ) 2 n i=1 (y i -ȳ) 2
The vectors y and ŷ represent the actual values and predicted values respectively for n queries. ȳ is the mean of actual values. An R 2 score close to 1 indicates near perfect prediction. R 2 scores however can be misleading in many cases. As R 2 depends on the scale and statistical characteristics of the whole dataset, it can have low errors even if the predictions have high errors [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF]. Therefore we use another evaluation metric, root mean squared error (RMSE), as our error metric:

RM SE(y, ŷ) = n i=1 (y i -ŷi ) 2 n

E. Predicting Query Execution Time

We show the results of our experiments in Figure 4 and Figure 6. The results include R 2 and RMSE values using k-NN and SVM with SPARQL algebra features and graph pattern features. Below we discuss these results.

1) Predicting with SPARQL Algebra Features:

For k-NN with SPARQL algebra features, we select k, the number of neighbors, by cross-validation. As Table I shows, different values of k do not have any effect on RMSE and R 2 on our validation dataset. Therefore we select k = 2. We achieve an R 2 value of 0.96645 and an RMSE value of 395.5125 on the test dataset using k-NN with SPARQL algebra features. Figure 4(a) shows the comparison between predicted and actual execution times using k-NN with SPARQL algebra features. Figure 4(b) shows that the queries from template 15 has the highest RMSE. The execution time for queries from template 15 range from 2 ms to 382.4 ms with an average of 69.09 ms. Because of the high error for queries from template 15, there are overestimated data points in this interval in Figure 4(a). We achieve an improved R 2 value of 0.98142 and a lower RMSE value of 294.3532 on the test dataset using SVM with SPARQL algebra features. Figure 4(c) shows the comparison between predicted and actual execution times using SVM with SPARQL algebra features. Figure 4(d) shows the RMSE values by query template for this model. As the figures show, the error for queries from template 15 decreases. Therefore the overestimated data points in the interval 2 ms to 382.4 ms move towards the perfect prediction line. However, the error for template 8 and 24 slightly increases.

2) Predicting with SPARQL Algebra and Graph Pattern

Features: For k-NN with SPARQL algebra features and graph pattern features, we have two parameters: the number of clusters K gp and the number of neighbors k. Again we select them by cross-validation. Figure 5(a) shows the RMSE values on the validation dataset for different K gp and k, and Figure 5(b) shows the R 2 values on the validation dataset for different K gp and k. The Figure 5 shows, k again does not have any impact. We get lowest K gp and highest R 2 values at K gp = 10 and K gp = 25 for all k values. Therefore we select K gp = 10 and k = 2 for our predictions with k-NN on the test dataset. Figure 6(a) and Figure 6(b) shows the prediction results on the test dataset using k-NN with K gp = 10 and k = 2. We get a slightly less R 2 value for this model than k-NN with SPARQL algebra features. This is because of the increase in RMSE values for queries from template 9, 17, and 24.

For SVM with SPARQL algebra features and graph pattern features, we select the value of K gp by cross-validation. Table II shows RMSE and R 2 values on the validation dataset for different K gp using SVM. We select K gp = 25 because it gives use the lowest RMSE value 528.9321 and highest R 2 value 0.9422 on the validation dataset. Figure 6(c) and Figure 6(d) shows the prediction results on the test dataset using SVM with K gp = 25. We get the overall best R

F. Required Time for Training and Prediction

Table III shows the total training time and average prediction time per query for the models we experimented with. Models with SPARQL algebra features take very low prediction time per query. Training time is also low. Models with graph pattern features take longer time to train. This is because the training time includes generating the distance matrix using approximated graph edit distance. This process itself takes 3293 seconds on average for 1260 queries. Also it includes the time required to cluster the training queries. However the average prediction time per query using models with graph pattern features is within the limit of 100 milliseconds, which is reasonable especially for query solving over Linked Data. The average prediction time per query using models with graph pattern features increase from the models with only algebra features because of the similarity computations using approximated edit distance. It is important to note that the training phase is an offline process and hence it does not influence query prediction time.

V. RELATED WORK

Recent work on predicting database query performance [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF], [START_REF] Ganapathi | Predicting multiple metrics for queries: Better decisions enabled by machine learning[END_REF], [START_REF] Gupta | PQR: Predicting query execution times for autonomous workload management[END_REF] has argued that the cost models used by the current generation query optimizers are good for comparing alternative query plans, but ineffective for predicting actual query performance metrics such as query execution time. These cost models are unable to capture the complexities of modern database systems [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF]. To address this, database researchers have experimented with machine learning techniques to learn query performance metrics. Ganapathi et al. [START_REF] Ganapathi | Predicting multiple metrics for queries: Better decisions enabled by machine learning[END_REF] use Kernel Canonical Correlation Analysis (KCCA) to predict a set of performance metrics. For the individual query elapsed time performance metric, they were able to predict within 20% of the actual query elapsed time for 85% of the test queries. Gupta et al. [START_REF] Gupta | PQR: Predicting query execution times for autonomous workload management[END_REF] use machine learning for predicting query execution time ranges on a data warehouse and achieve an accuracy of 80%. Akdere et al. [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF] study the effectiveness of machine learning techniques for predicting query latency of static and dynamic workload scenarios. They argue that query performance prediction using machine learning is both feasible and effective.

Related to the Semantic Web query processing, SPARQL query engines can be categorized into two categories: SQLbased and RDF native query engines [START_REF] Tsialiamanis | Heuristics-based query optimisation for SPARQL[END_REF]. SQL-based query engines rely on relational database systems storage and query optimization techniques to efficiently evaluate SPARQL queries. They suffer from the same problems mentioned above. Furthermore, due to the absence of schematic structure in RDF, costbased approaches -successful in relational database systems -do not perform well in SPARQL query processing [START_REF] Tsialiamanis | Heuristics-based query optimisation for SPARQL[END_REF]. RDF native query engines typically use heuristics and statistics about the data for selecting efficient query execution plans [START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF]. Heuristics-based optimization techniques include exploiting syntactic and structural variations of triple patterns in a query [START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF], and rewitting a query using algebraic optimization techniques [START_REF] Frasincar | RAL: An algebra for querying RDF[END_REF] and transformation rules [START_REF] Hartig | The sparql query graph model for query optimization[END_REF]. Heuristicsbased optimization techniques generally work without any knowledge of the underlying data. Stocker et al. [START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF] present optimization techniques with pre-computed statistics for reordering triple patters in a SPARQL query for efficient query processing. However, in many use-cases involving querying Linked Data, statistics are often missing [START_REF] Tsialiamanis | Heuristics-based query optimisation for SPARQL[END_REF]. This makes these statistics-based approaches ineffective in the Linked Data scenario. Furthermore, as in the case of relation database systems, these existing approaches are unable to predict actual query performance metrics such as query execution time for a given configuration.

VI. CONCLUSION AND FUTURE WORK

We present an approach to predict SPARQL query execution time using machine learning techniques. We learn query execution times from already executed queries. This approach can be useful where statistics about the underlying data are unavailable We discuss how to model SPARQL queries as feature vectors, and show highly accurate results.

In future, firstly we would like to compare our approach to traditional query cost estimation techniques in the Linked Data scenario -e.g. join order optimization in federated query processing. State of the art Linked Data query processing approach FedX [START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF] uses variable count selectivity estimation [START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF] optimization for efficient join ordering of grouped triple pattern execution. We would like to compare our approach to such approaches. Second, we plan to systematically generate training queries for two scenarios: (a) given query logs of real queries (b) given a small set of sample queries. We plan to apply query log mining techniques to systematically generate training queries. Recent [START_REF] Arias | An empirical study of real-world SPARQL queries[END_REF] work on query log mining shows that the majority of SPARQL queries share some common characteristics. We plan to consider those statistically significant common characteristics in refining training queries from massive query logs and generating training queries from a small set of sample queries. We would also explore how these common characteristics can be used as query features. Third, we would like to investigate online machine learning techniques for our models. Our goal would be to refine our prediction models based on the new predictions and their actual values. Finally, we would like to include load and availability related features. In this direction, we plan to execute the training queries every hour and include features such as time, day, and month. This would help us to model workload patterns for public SPARQL endpoints.

Fig. 1 .

 1 Fig. 1. Extracting SPARQL algebra features from a SPARQL query.

Fig. 2 .

 2 Fig. 2. Example of extracting graph pattern features.

Fig. 3 .

 3 Fig. 3. Average, minimum, and maximum execution times for the queries belonging to different query templates in the test dataset.

Fig. 4 .

 4 Fig. 4. Query execution time predictions with SPARQL algebra features using k-NN (with k = 2) and SVM models.

Fig. 5 .

 5 Fig. 5. RMSE and R 2 values on the validation dataset for different Kgp and k.

Fig. 6 .

 6 Fig. 6. Query execution time predictions with SPARQL algebra features and graph pattern features using k-NN (Kgp = 10 and k = 2) and SVM (Kgp = 25).

  2 . SPARQL allows forming graph patterns by combining smaller patterns: basic graph patterns, group graph patterns, optional graph patterns, alternative graph patterns, and patterns on named graphs. A basic graph pattern contains a set of triple patterns.

	Definition 3 (Triple pattern). A triple pattern is a member of
	the set:

TABLE I .

 I

RMSE AND R 2 VALUES FOR DIFFERENT k FOR k-NN ON THE VALIDATION DATASET.

  2 value

		Kgp=5	Kgp=10 Kgp=15 Kgp=20 Kgp=25
	RMSE	530.9169 546.7406 547.6764 547.4219 528.9321
	R 2	0.9418	0.9383	0.9381	0.9381	0.9422

TABLE II .

 II RMSE AND R 2 VALUES ON THE VALIDATION DATASET FOR DIFFERENT Kgp USING SVM. 0.98526 and the overall lowest RMSE value 262.1869 with this model. This is an improvement from the SVM with SPARQL algebra features model. The main reason for this is the decrease in RMSE for queries from template 12 and 24.

TABLE III .

 III REQUIRED TIME FOR TRAINING AND PREDICTIONS.

See http://richard.cyganiak.de/2007/10/lod/ for a graph linking these datasets.

http://dbpedia.org

ACKNOWLEDGMENT

This work is supported by the ANR CONTINT program under the Kolflow project (ANR-2010-CORD-021-02).


Rakebul Hasan
email: hasan.rakebul@inria.fr

Generating and Summarizing Explanations for Linked Data

Keywords: Explanation, summarization, Linked Data

Linked Data consumers may need explanations for debugging or understanding the reasoning behind producing the data. They may need the possibility to transform long explanations into more understandable short explanations. In this paper, we discuss an approach to explain reasoning over Linked Data. We introduce a vocabulary to describe explanation related metadata and we discuss how publishing these metadata as Linked Data enables explaining reasoning over Linked Data. Finally, we present an approach to summarize these explanations taking into account user specified explanation filtering criteria.

Introduction

In the recent years, we have seen a growth of publishing Linked Data from community driven efforts, governmental bodies, social networking sites, scientific communities, and corporate bodies [START_REF] Bonatti | Robust and scalable linked data reasoning incorporating provenance and trust annotations[END_REF]. These data publishers from various domains publish their data in an interlinked fashion1 using vocabularies defined in RDFS/OWL. This presents opportunities for large-scale data integration and reasoning over cross-domain data. In such a distributed scenario, consumers of these data may need explanations for debugging or understanding the reasoning behind producing the data; they may need the possibility to transform long explanations into more understandable short explanations [START_REF] Mcguinness | Infrastructure for web explanations[END_REF]. Much of the previous work on explanations for the Semantic Web does not address explanation in a distributed environment [START_REF] Hasan | A Brief Review of Explanation in the Semantic Web[END_REF]. The Inference Web [START_REF] Mcguinness | Infrastructure for web explanations[END_REF] approach proposes a centralized registry based solution for publishing explanation metadata from distributed reasoners. We propose a decentralized solution to this problem. In essence, we discuss how to explain Linked Data in a decentralized fashion and how to summarize the explanations.

To explain Linked Data in a decentralized fashion, we publish explanation related metadata as Linked Data. In this approach, there is no constrain to publish the explanation metadata in a centralized location like in the Inference Web approach. To generate explanations, we retrieve the metatada by following their dereferenceable URIs and present them in a human understandable form. For publishing explanation related metadata, we present a vocabulary to describe explanation metadata and guidelines to publish these metadata as Linked Data. To provide short explanations, we summarize the explanations by centrality, coherence, abstractness, and concept filtering.

The structure of the rest of this paper is as follows: in section 2, we present the related work. In section 3, we discuss how to represent and generate explanations for Linked Data. In section 4, we present our approach to summarize explanations. In section 5, we evaluate our summarization approach. Finally, we conclude and discuss the future work in section 6.

Related Work

Inference Web [START_REF] Mcguinness | Infrastructure for web explanations[END_REF][START_REF] Mcguinness | Explaining semantic web applications[END_REF][START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF] is an explanation infrastructure which addresses explanation requirements of web services discovery, policy engines, first order logic theorem provers, task execution, and text analytics. Information manipulation traces of these various kinds of systems are encoded using Proof Markup Language (PML) [START_REF] Pinheiro Da Silva | A proof markup language for semantic web services[END_REF]. Inference Web provides a set of software tools and services for building, presenting, maintaining, and manipulating PML proofs. PML is an explanation interlingua consisting of three OWL ontologies: PML provenance ontology (PML-P), PML justification ontology (PML-J), and PML trust ontology (PML-T). Inference Web authors define justification as a logical reasoning step, or any kind of computation process, or a factual assertion or assumption. Inference Web proposes a centralized registry based solution for publishing explanation metadata from distributed reasoners. In contrast, we propose a decentralized solution to address explanations in the distributed setting of Linked Data. The WIQA (Web Information Quality Assessment) framework [START_REF] Bizer | Quality-Driven Information Filtering in the Context of Web-Based Information Systems[END_REF] provides explanations of information filtering process for supporting information consumers in their trust decisions. WIQA exposes its explanations in RDF using the Explanation (EXPL) Vocabulary 2 . Forcher et al. [START_REF] Forcher | Explanation-aware system design of the semantic search engine koios[END_REF] present the explanation-aware semantic search engine called KOIOS. The keyword search result explanations include information on how keywords are mapped to concepts and how concepts are connected. KOIOS uses a set of ontologies to formally describe the content of explanations in RDF. Both WIQA and KOIOS provide application specific explanations which include process descriptions of specific algorithms. In contrast, our explanations are suitable for generic Linked Data scenarios. Horridge et al. [START_REF] Horridge | Laconic and precise justifications in OWL[END_REF] present justification based explanation techniques. The authors define a justification for an entailment in an ontology as "a minimal subset of the ontology that is sufficient for the entailment to hold". The authors present laconic and precise justifications which are fine-grained justifications consisting of axioms with no superfluous part. The authors present an optimized algorithm to compute laconic justifications showing the feasibility of computing laconic justifications and precise justifications in practice. We do not focus on the theoretical 2 http://www4.wiwiss.fu-berlin.de/bizer/triqlp/ aspects of the justifications such as the minimal parts of axioms in a justification which are required to hold an entailment. Rather, we focus on the aspects related to publishing and consuming explanation metadata in a distributed environment. Other notable works on explanations in the Semantic Web literature include OntoNova [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF] and Knowledge in a Wiki (KiWi) [START_REF] Kotowski | A perfect match for reasoning, explanation and reason maintenance: OWL 2 RL and semantic wikis[END_REF]. OntoNova and KiWi provide explanations of their reasoning. However, they do not represent their explanation metadata using standard data formats. This is an undesirable situation for Linked Data scenarios because data consumers would not be able to process such non standard explanation metadata.

To the best of our knowledge, there is no comparable published work on summarizing explanations in the Semantic Web literature. But researchers have studied ontology summarization. RDF Sentence graph based summarization [START_REF] Zhang | Ontology summarization based on RDF sentence graph[END_REF] extracts RDF sentences based on centrality measures. Our work has a similar approach to sentence graph summarization approach. However, we define new measures for summarizing explanations. Peroni et al. [START_REF] Peroni | Identifying key concepts in an ontology, through the integration of cognitive principles with statistical and topological measures[END_REF] discuss how to identify key concepts in an ontology. They draw summarization criteria from cognitive science (natural categories), network topology (density and coverage), and lexical statistics (term popularity). Alani et al. [START_REF] Alani | Winnowing ontologies based on application use[END_REF] discuss shrinking an ontology by analyzing the usage of the ontology.

Explaining Linked Data

We follow the Linked Data principles [START_REF] Berners-Lee | Linked Data. W3C Design Issues[END_REF] to publish our explanation metadata. We describe these metadata using our proposed vocabulary Ratio4TA3 . We generate explanations by retrieving the explanation metatada by following their dereferenceable URIs and presenting them in a human understandable form.

Representing and Publishing Explanation Metadata

Ratio4TA (inter linked explanations for triple assertions) is an OWL ontology for describing explanation metadata. Ratio4TA extends the W3C PROV Ontology4 . This promotes interoperability by enabling data consumers process explanation metadata according to W3C PROV standards. Consumers of these explanation metadata can use their preferred tools to present and visualize explanations. Figure 1 shows the core concepts and relations of Ratio4TA. They allow describing data, reasoning processes, results, data derivations, rules, and software applications. The ExplanationBundle concept allows to define named graph containers for RDF statements representing explanation metadata.

We publish the explanation metadata as Linked Data. This means that all the resources in our explanation metadata have dereferenceable HTTP URIs. We avoid using blank nodes to keep the resources globally dereferenceable. We use the named graph mechanism [START_REF] Carroll | Named graphs, provenance and trust[END_REF] to make statements about RDF triples. Using named graph allows us to associate explanation metadata for data with different level of granularity -explanation metadata for a triple or a graph containing more than one triple. Furthermore, we use named graphs to group together explanation metadata and make the metadata for an explanation referenceable by a single URI. Listing 1.1 shows an extract of an explanation described using Ratio4TA in TriG [START_REF] Carroll | Named graphs, provenance and trust[END_REF] notation. The example in this listing shows the explanation metadata for the derived triple lodapp:data1. The named graph lodapp:explanation1 contains the explanation metadata. The metadata include links to the reasoning process, the input data, the rule, the software application, and the result to which the derivation contributes.

Listing 1.1: Extract from the explanation metadata for a derivation Why a New Ontology? Proof Markup Language (PML) [START_REF] Pinheiro Da Silva | A proof markup language for semantic web services[END_REF] and the AIR Justification Ontology (AIRJ) [START_REF] Kagal | Gasping for AIR -why we need linked rules and justifications on the semantic web[END_REF] are important previous works on representing explanation metadata. PML allows describing provenance metadata, justifications for derivations of conclusions, and trust related metadata. Additionally, a light weight variant of PML known as PML-Lite [START_REF] Pinheiro Da Silva | Inference web in action: Lightweight use of the proof markup language[END_REF] presents a simple subset of PML. AIRJ extends PML-Lite and provides primitives to represent the different events and the operations performed by reasoners. PML and AIRJ use RDF container concepts. RDF containers use blank nodes to connect a sequence of items [START_REF]RDF semantics[END_REF]. However, as a common practice, blank nodes are avoided while publishing Linked Data [START_REF] Heath | Linked Data: Evolving the Web into a Global Data Space[END_REF]. It is not possible to make statements about blank nodes as they do not have identifiers. Therefore, blank nodes make data integration harder in the global dataspace of Linked Data. Additionally, the existing ontologies do not use any common data interchanging standard such as W3C PROV-O. This makes it hard for applications across the web to make sense of the explanation metadata.

Generating Explanation

We generate explanations from the published explanation metadata by recursively following the links between the involved explanation metadata and the data they describe. For a derived RDF statement dst, we crawl through the related metadata with a maximum depth limit and collect the set of explanation meta statements, and the set of RDF statements from which the derived RDF statement dst is derived. In the remaining for this paper, we refer to the derived RDF statement (the initial dst) that we are explaining as the root statement rs. We refer to the set of RDF statements from which rs is derived as knowledge statements KST . The RDF knowledge graph KG is the graph formed by union of KST and the root statement: KG = RDF Graph(KST ∪ rs). We generate natural language descriptions from the RDF statements in KG (using rdfs:label property values) and present them as explanations for human end-users. Figure 2 shows an example of our explanation for a derived statement that "Bob is a British Scientist". Each derivation contains a link to the natural language representation of the used rule. Although this kind of explanations with the details of all the steps may be useful for expert users, they may overwhelm non-expert users with too much information [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF][START_REF] Hasan | A Brief Review of Explanation in the Semantic Web[END_REF][START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF]. We provide summarized explanations to address this problem. Figure 3 shows an example of a summarized explanation for "Bob is a British Scientist". Users can switch to the full explanation by clicking on the "more details" link. In the next section, we discuss our approach to summarizing explanations.

Summarizing Explanations

In [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF][START_REF] Hasan | A Brief Review of Explanation in the Semantic Web[END_REF][START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF], researchers discuss the importance of providing short explanations rather than overwhelming the end-users with too much information. The authors of [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF] also discuss filtering information in explanations in order to provide more relevant explanations. We propose an approach to summarizing explanations taking into account user specified filtering criteria. More formally, let KG = (R, T ) be an RDF knowledge graph, where R is the set of resources and literals and T is the set of RDF statements. Let rs be the root statement (therefore the knowledge statements KST = T \ rs). We provide summarized explanations by summarizing RDF statements from KST . We use the term "oriented graph" to refer to KG throughout the paper. Our summarization approach includes first a ranking step and then a re-ranking step. It is important to note that our summarized explanations may not always conform to the correctness of deductions from a logical point of view. Our summarized explanations are not aimed at explaining the correct deduction steps. Rather the aim is to provide a short overview of the background information used in a deduction. We describe below the measures we use for summarizing explanations.

Measures for Ranking

We rank the statements in KST based on their scores we compute using our summarization measures. The scores are normalized and range from 0.0 to 1.0. A higher score for a statement means that the statement is more suitable for a summary. Taking n statements, where n <| KST |, or statements with scores greater than a threshold value will give a summarized list of statements which can explain rs. For the ranking step, we compute the scores by using three measures: salience (S SL ), similarity (S SM ), and abstractness (S AB )

Salient RDF Statements The salience of an RDF statement indicates the importance of the RDF statement in the oriented graph. We use normalized degree centrality, C DN (v), to compute salience of RDF statements. Degree centrality of a vertex in a graph is the number of links the vertex has. We compute the salience S SL (i) of an RDF statement i using [START_REF]RDF semantics[END_REF].

S SL (i) = θ 1 × C DN (subjectOf (i)) + θ 2 × C DN (objectOf (i)) (1)
In (1), i θ i = 1 and ∀ i : θ i ≥ 0 i.e. we take the weighted average of the normalized degree centrality of the subject and the object of the RDF statement i. The subjectOf (i) and the objectOf (i) functions return respectively the subject resource and the object resource of the RDF statement i. We did not use the centrality of the predicate of statement while computing S SL because we wanted an importance score representing the importance of the information in a statement but not the importance of the relation between the information. The centrality values of predicates in a RDF graph often do not change as they are directly used from the schemata. In contrast, every new RDF statement changes the centrality values of its subject and object.

Similar RDF Statements

The consumers of our explanations can specify a set of classes, F L, as their filtering criteria, where F L ⊆ SC and SC is the set of all classes in the schemata used to describe KG. We rank the more similar statements to the concepts given in filtering criteria higher. We use the approximate query solving feature [START_REF] Corby | Searching the Semantic Web: approximate query processing based on ontologies[END_REF] of Corese5 to compute similarity. The approximate query solving feature is a semantic distance-based similarity feature to compute conceptual similarity between two classes in a schema. For a statement i and a set of classes as filtering criteria F L, we compute similarity S SM (i, F L) using [START_REF] Alani | Winnowing ontologies based on application use[END_REF].

S SM (i, F L) = θ 1 × similarity node (subjectOf (i), F L) + θ 2 × similarity node (predicateOf (i), F L) + θ 3 × similarity node (objectOf (i), F L) (2)
The function predicateOf (i) returns the predicate of the statement i. We compute similarity node (j, F L) where j ∈ R ∪ SC as following:

similarity node (j, F L) = similarity type ({j}, F L) if j ∈ SC similarity type (typesOf (j), F L) if j / ∈ SC (3)
In (3), for the case j ∈ SC, we compute the similarity between the class j and the set of classes in F L. For the case j / ∈ SC, we compute the similarity between the set of classes of which j is an instance and the set of classes in F L. The similarity type function takes as arguments a set of classes T P ∈ SC and the set of filtering criteria F L, and returns the similarity value between them. The typesOf (j) function for a resource j ∈ R returns the set of classes of which j is an instance. The similarity type function in (4a) computes its value by taking the average of all the values of maxSimilarity type (m, T P ) where m ∈ F L and T P ∈ SC. The maxSimilarity type function in (4b) returns the maximum similarity value between a class m and all the classes in T P . This is to ensure that when a resource is an instance of multiple classes, we filter it by the class which is more similar to the filtering criteria. The similarity type function calculates a combined similarity score of T P with respect to all the classes in F L. Again, we consider the weighted average, and therefore i θ i = 1 and ∀ i : θ i ≥ 0 in [START_REF] Alani | Winnowing ontologies based on application use[END_REF]. Abstract Statements We consider a statement that is close to the root, rs, in corresponding proof tree is more abstract than a statement that is far from the root rs. We define the distance of a node in the proof tree from the root node as the level of the tree to which the node belongs. The root node belongs to level one in the proof tree. The root node is derived from the nodes in level two. A node in level two is derived from the nodes in level three, and so on. For a statement i ∈ KST , we compute the abstraction score S AB (i) using [START_REF] Berners-Lee | Linked Data. W3C Design Issues[END_REF].

S AB (i) = 1 level(i) (5)
The function level(i) returns the proof tree level to which the statement i belongs. The S AB (i) measure gives a value greater than 0.0 and less than or equal to 1.0, where a smaller value means less abstract and a larger value means more abstract.

Measures for Re-Ranking

We use two more measures to improve the rankings produced by the combinations of three measures we presented so far.

Subtree Weight in Proof Tree For a subtree of the proof tree with root i, we compute the subtree weight of the statement i by taking the average score of all the statements in that subtree.

score

ST (i) = j∈subtree(i) score(j) | subtree(i) | (6)
The subtree(i) function returns the RDF statements from the subtree of proof tree with root i. The score(j) for a statement j here can be computed by combinations of the measures we present in section 4.1. We discuss more about how to combine the different measures in section 5.

Coherence Previous works in text summarization [START_REF] Eduard | Text summarization[END_REF] and ontology summarization [START_REF] Zhang | Ontology summarization based on RDF sentence graph[END_REF] have shown that coherent information are desirable in summaries.

We consider an RDF statement x to be coherent to an RDF statement y if x is directly derived from y. Let RL be a ranked list of RDF statements; S be a list of already selected RDF statements in the summary; i be the next RDF statement to be selected in S. We re-rank RL by repeatedly selecting next i with | RL | repetitions using [START_REF] Bonatti | Robust and scalable linked data reasoning incorporating provenance and trust annotations[END_REF].

i = arg max j∈RL\S (λ 1 × score(j) + λ 2 × reward(j, S)) (7)
Again, the score(j) for a statement j here can be computed by combinations of the measures we presented before. We take the weighted average of score(j) and reward(j, S) in [START_REF] Bonatti | Robust and scalable linked data reasoning incorporating provenance and trust annotations[END_REF], therefore i λ i = 1 and ∀ i :

λ i ≥ 0. reward(j, S) = 1 - coherent(S) coherent(S ∪ j) (8)
As [START_REF] Carroll | Named graphs, provenance and trust[END_REF] shows, the reward score of a statement j is the amount of potential contribution value -ranging from 0.0 to 1.0 -to the total coherence of the summary if j is added to S. The function coherent(S) in ( 8) returns the number of coherent statements in the summary S.

Evaluation

Ontology summarization [START_REF] Li | Evaluations of user-driven ontology summarization[END_REF] and text summarization [START_REF] Eduard | Text summarization[END_REF][START_REF] Steinberger | Evaluation measures for text summarization[END_REF] technologies are evaluated by measuring agreements between human-generated summaries -known as "ground truths" -and automatically generated summaries. We obtained our ground truths by surveying 24 people: 17 computer scientists, 1 chemist, 1 social scientist, 1 mathematician, 1 journalist, 1 psychologist, 1 biologist, and 1 business administrator. 18 participants in our survey had knowledge of RDF and 6 participants did not have any knowledge of RDF. The ages of the participants range from 22 to 59. 20 participants were male and 4 were female. The explanations, the questionnaires, the responses, and the results of the evaluation are publicly available online6 . We selected a subset of geographical locations from GeoNames7 and a subset of artists, events, and places from DBPedia8 , then derived new information from these selected subsets. Our ad-hoc reasoner infers new RDF statements with respect to RDFS type propagation; and owl:sameAs and transitivity of the parentFeature property of GeoNames schema. In addition, the reasoner generates explanations for each derivation it performs. We used three test cases -three queries with their results along with the explanations for the results. Each query result is an inferred statement by our reasoner.

Each test case has two scenarios: without filtering criteria F L, and with filtering criteria F L. Each participant answered questions for one test case. We randomly assigned a test case to a participant. We ask the participants to rate, from a scale of 1 to 5, the need for each of the statements in the explanation. For, the scenario with filtering criteria F L, we give the query, the answer, and the explanation but with a user's filtering criteria class taken from the schemata used in the reasoning process. The ratings of the explanation statements are our ground truths. We compute the ground truth rankings of explanation statements by ordering them by their rating values.

Comparing Summarization Measures

We evaluate different combinations of the summarization measures we define.

In equation ( 9), we compute score S SL (i) for a statement i considering salience of the statement. We always include S SL in our measure combinations. The motivation is to first include the salient statements in a summary and then find the statements with other measure combination scores (e.g. S AB or S SM or S AB +S SM ) in those salient statements. Equations ( 10), [START_REF] Forcher | Explanation-aware system design of the semantic search engine koios[END_REF], and ( 12) show three more combinations of measures that we consider for our evaluation. In [START_REF] Eduard | Text summarization[END_REF], we compute score SL+AB (i) for a statement i considering salience and abstractness of the statement. In [START_REF] Forcher | Explanation-aware system design of the semantic search engine koios[END_REF], we compute the score SL+SM (i) for a statement i considering the salience (S SL ), and the similarity (S SM ) with respect to user's filtering criteria F L. In ( 12), we compute score SL+AB+SM (i) for a statement i considering the salience (S SL ), the abstractness (S AB ), and the similarity (S SM ) with respect to user's filtering criteria F L.

score

SL (i) = S SL (i) (9)
score

SL+AB (i) = λ 1 × S SL (i) + λ 2 × S AB (i) (10)
score

SL+SM (i) = λ 1 × S SL (i) + λ 2 × S SM (i, F L) (11)
score

SL+AB+SM (i) = λ 1 × S SL (i) + λ 2 × S AB (i) + λ 3 × S SM (i, F L) (12)
These combinations are combinations of ranking measures we present in section 4.1. For re-ranking, we first compute the score using any of ( 9), ( 10), [START_REF] Forcher | Explanation-aware system design of the semantic search engine koios[END_REF], and ( 12), then we re-rank using [START_REF] Bizer | Quality-Driven Information Filtering in the Context of Web-Based Information Systems[END_REF], or [START_REF] Bonatti | Robust and scalable linked data reasoning incorporating provenance and trust annotations[END_REF]. In remaining of this paper, we denote subtree weight measure as S ST , and coherence measure as S CO . For the scenario without F L, we compare our summaries to sentence graph summarization [START_REF] Zhang | Ontology summarization based on RDF sentence graph[END_REF] -denoted as S SG . As the authors of sentence graph summarization approach suggest, we use 0.8 as the navigational preference p parameter value. We implemented sentence graph summarization using degree centrality as the authors found degree centrality performs better than other centrality measures in general, and for its simplicity. We do not consider sentence graph summarization for the scenarios with F L because sentence graph summarization does not have a feature for filtering information using ontology concepts as filtering criteria. In [START_REF] Eduard | Text summarization[END_REF], [START_REF] Forcher | Explanation-aware system design of the semantic search engine koios[END_REF], and ( 12), i λ i = 1 and ∀ i : λ i ≥ 0. Thus we take the weighted averages of the measure combinations. For this evaluation, we use equal weights in [START_REF] Eduard | Text summarization[END_REF], ( 11), ( 12), ( 1), (2), and [START_REF] Bonatti | Robust and scalable linked data reasoning incorporating provenance and trust annotations[END_REF]. Therefore, we set ∀ i : 10), ( 11), [START_REF] Hasan | A Brief Review of Explanation in the Semantic Web[END_REF], and [START_REF] Bonatti | Robust and scalable linked data reasoning incorporating provenance and trust annotations[END_REF] where N λ = number of λ parameters in the corresponding equations; and ∀ i :

λ i = 1 N λ in (
θ i = 1 N θ in (1)
, and (2) where N θ = number of θ parameters in the corresponding equations. However, one can use parameter estimation techniques for finding the optimal parameter values.

Analysis of Ground Truths

We use cosine similarity to measure the agreements between rating vectors. Cosine similarity values in positive space are in the interval 0 to 1. Table 1 shows the total average agreement measured by cosine similarity and standard deviations for two scenarios -without filtering criteria F L and with filtering criteria F L. The average agreements for both the scenarios are more than 0.8 which is considerably high. However, the standard deviation is higher for the scenario with F L. The reason for this higher standard deviation is that the participants had to consider the highly subjective [START_REF] Araújo | Towards semantics-based ontology similarity[END_REF] factor of similarity and therefore their ratings had more variance for the scenario with F L.

Evaluating the Rankings

We use normalized discounted cumulative gain to evaluate ranking quality. Discounted cumulative gain (DCG) [START_REF] Järvelin | Cumulated gain-based evaluation of IR techniques[END_REF][START_REF] Mcsherry | Computing information retrieval performance measures efficiently in the presence of tied scores[END_REF] measures the quality of results of an information retrieval system in a ranked list. DCG assumes that judges have graded each item in a list of results. Using these grades, DCG measures the usefulness, or gain, of a ranked list of results. DCG penalizes high quality results appearing lower in a ranked list of results. Normalized discounted cumulative Gain (nDCG) allows to calculate and compare this measure across multiple lists of results where each of the lists might have different length. nDCG values are in the interval 0.0 to 1.0. An nDCG p value of 1.0 means that the ranking is perfect at position p with respect to the ideal ranking -ranking based on grades. The nDCG p value 0.0 means that the ranking is completely imperfect at position p with respect to the ideal ranking. In our study, the average of ratings by all the survey participants for a statement s is the grade for the statement s. This means that the participants consider central (with respect to the oriented graph and the proof tree), abstract, and coherent information as necessary information in explanation summaries for the scenario without F L. This also holds for the scenario with F L with the added observation that the participants also consider similar information as necessary information. The nDCG values for these measure combinations are higher than 0.9 for all ranks. This means that the rankings by these measure combinations are highly similar to the ground truth rankings. In contrast, the sentence graph summarization ranking has low nDCG values compared to all the other rankings for the scenario without F L. This shows that our explanation summarization algorithms produce much higher quality rankings than sentence graph summarization algorithm.

Evaluating the Summaries

We evaluate the summaries using Recall and P recision composite scores as in text summarization [START_REF] Eduard | Text summarization[END_REF]. Recall and P recision quantify how closely the algorithm generated summaries correspond to the human produced summaries. Recall reflects how many good statements the algorithm missed, and P recision reflects how many of the algorithm's selected statements are good. F-score is the composite measure of Recall and P recision. We use the basic F-score as in [START_REF] Steinberger | Evaluation measures for text summarization[END_REF]: F-score = 2×P recision×Recall P recision+Recall . We measure F-score for summarized explanations with different compression ratios, CR, to evaluate summaries of different sizes. Compression ratio CR is the ratio of the size of the summarized explanation to the size of original explanation. We evaluate the summarized explanations produced by different measure combinations by comparing them to human generated summarized explanations (i.e. ground truth summarized explanations) using F-score. To generate the ground truth summarized explanation for an explanation, we include a statement in the ground truth summarized explanation if its rating is greater than or equal to the average rating of all the statements in the original explanation. F-scores reflects the accuracy of automatically generated summaries with respect to the ground truth summary. A desirable situation would be a summarized explanation with high F-score and low CR. Figure 5 shows the average F-scores for different measure combinations for summaries with different sizes for the three test cases. The x-axis represents compression ratio CR. The y-axis represents F-scores. For the scenario without F L (the fig- ure on the left), the best F-score is 0.72 when CR value is 0.33 by the measure combinations S SL + S AB + S ST and S SL + S AB + S ST + S CO . This is a desirable situation with a high F-score and low CR. The sentence graph summarization performs poorly with a best F-score value of 0.34 in the CR interval 0.05 to 0.3. This shows that our summarized explanations are more accurate than the summarized explanations generated by sentence graph summarization algorithm. For the scenario with F L (the figure on the right), the best F-score is 0.66 at CR values 0.53 and 0.55 by the measure combinationS SL + S SM . However, the Fscore 0.6 at CR value 0.3 by the measure combination S SL + S AB + S SM + S CO is more desirable because the size of the summary is smaller. As expected, our summarization approach perform worse in the scenario with F L where we use S SM . This is due to the fact that the survey participants had to consider the highly subjective factor of similarity.

Conclusion and Future Work

In this paper, we discuss how to generate and summarize explanations for Linked Data. We present an ontology to describe explanation metadata and discuss publishing explanation metadata as Linked Data. In addition, we presented five summarization measures to summarize explanations. We evaluate different combinations of these measures. The evaluation shows that our approach produces high quality rankings for summarizing explanation statements. Our summarized explanations are also highly accurate with F-score values ranging from 0.6 to 0.72 for small summaries. Our approach outperforms the sentence graph based ontology summarization approach.

In the future work, we would like to explore how we can effectively present explanations and summarized explanations using different kinds of user interfaces and user interactions. We would like to explore how we can effectively use the summarization rankings while presenting information in personalized scenarios. Finally, we are going to evaluate the impact of explanations and summarized explanations on end-users.

Fig. 1 :

 1 Fig. 1: The core classes and properties of Ratio4TA.

Fig. 2 :

 2 Fig. 2: Full explanation. Fig. 3: Summarized explanation.

  similarity type (T P, F L) = m∈F L maxSimilarity type (m, T P ) | F L | (4a) maxSimilarity type (m, T P ) = max n∈T P (similarity corese (m, n)) : (4b) For a class m ∈ F L and a class n ∈ T P , similarity corese (m, n) computes the similarity score between class m and n ranging from 0.0 to 1.0 using SPARQL similarity extension of Corese. A value of 1.0 represent exact match and a value of 0.0 represents completely not similar. The S SM score for a statement indicates the similarity of the information in the statement to the information specified in F L.

  Figure 4 shows the average nDCG values of the three test cases for different rankings by different measure combinations. The x-axis represents ranks and the y-axis represents nDCG. We plot 21 ranks in the x-axis because the shortest explanation among the three test cases had 21 statements. For the scenario without F L (the figure on the left), the measure combinations S SL +S AB +S CO , S SL +S AB +S ST , and S SL + S AB + S ST + S CO produce more closer rankings to the ground truth rankings. For the scenario with F L (the figure on the right), the same three measure combinations with added S SM measure have the best nDCG values.

Fig. 4 :

 4 Fig. 4: Comparison of rankings.

Fig. 5 :

 5 Fig. 5: Compression ratio (CR) vs F-score.

  Alani et al. analyze the query log against an ontology to understand the important parts of the ontology. Peroni et al. and Alani et al. focus on a concept level summarization of ontologies. In contrast, our focus is on statement level summarization.

Table 1 :

 1 Average agreements between ratings measured by cosine similarity.

		avg.	std. dev.
	Without F L 0.836	0.048
	With F L	0.835	0.065

See http://richard.cyganiak.de/2007/10/lod/ for a graph linking these datasets.

http://ns.inria.fr/ratio4ta/

http://www.w3.org/TR/prov-o/

http://wimmics.inria.fr/corese

http://ns.inria.fr/ratio4ta/sm/

http://www.geonames.org/

http://dbpedia.org/

Acknowledgments: This work is supported by the ANR CONTINT program under the Kolflow project (ANR-2010-CORD-021-02).


Rakebul Hasan
email: hasan.rakebul@inria.fr

Predicting SPARQL Query Performance and Explaining Linked Data ⋆

Keywords: Query performance, explanation, summarization

As the complexity of the Semantic Web increases, efficient ways to query the Semantic Web data is becoming increasingly important. Moreover, consumers of the Semantic Web data may need explanations for debugging or understanding the reasoning behind producing the data. In this paper, firstly we address the problem of SPARQL query performance prediction. Secondly we discuss how to explain Linked Data in a decentralized fashion. Finally we discuss how to summarize the explanations.

Introduction

As the complexity of the Semantic Web increases, it is becoming increasingly important to develop efficient ways to query the Semantic Web data [START_REF] Huang | Scalable SPARQL querying of large RDF graphs[END_REF]. Central to this problem is knowing how a query will behave prior to executing it [START_REF] Hartig | The sparql query graph model for query optimization[END_REF]. Moreover, data publishers publish their data in an interlinked fashion using vocabularies defined in RDFS/OWL [START_REF] Bonatti | Robust and scalable linked data reasoning incorporating provenance and trust annotations[END_REF]. This presents opportunities for large-scale data integration and reasoning over cross-domain data. In such a distributed scenario, consumers of these data may need explanations for debugging or understanding the reasoning behind producing the data; they may need the possibility to transform long explanations into more understandable short explanations [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF][START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF].

In this paper, firstly we address the problem of SPARQL query performance prediction. Inspired by database research for accurate query performance prediction [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF][START_REF] Ganapathi | Predicting multiple metrics for queries: Better decisions enabled by machine learning[END_REF][START_REF] Gupta | PQR: Predicting query execution times for autonomous workload management[END_REF], we use machine learning techniques to predict SPARQL query execution time. Secondly we propose a decentralized solution to explanation for Linked Data. We discuss how to explain Linked Data in a decentralized fashion and how to summarize the explanations.

The structure of the rest of this paper is as follows: in section 2, we present the state of the art on related work. In section 3, we present the problems we address and our contributions. In section 4, we present our approach to the problems we address. In section 5 we present our preliminary results. In section 6 we present our future evaluation plan. Finally, we conclude in section 7.

State of the Art

Recent work on predicting database query performance [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF][START_REF] Ganapathi | Predicting multiple metrics for queries: Better decisions enabled by machine learning[END_REF][START_REF] Gupta | PQR: Predicting query execution times for autonomous workload management[END_REF] has argued that the analytical costs models used by the current generation query optimizers are good for comparing alternative query plans, but ineffective for predicting actual query performance metrics such as query execution time. Analytical cost models are unable to capture the complexities of modern database systems [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF]. To address this, database researchers have experimented with machine learning techniques to learn query performance metrics. Ganapathi et al. [START_REF] Ganapathi | Predicting multiple metrics for queries: Better decisions enabled by machine learning[END_REF] use Kernel Canonical Correlation Analysis (KCCA) to predict a set of performance metrics. For the individual query elapsed time performance metric, they were able to predict within 20% of the actual query elapsed time for 85% of the test queries. Gupta et al. [START_REF] Gupta | PQR: Predicting query execution times for autonomous workload management[END_REF] use machine learning for predicting query execution time ranges on a data warehouse and achieve an accuracy of 80%. Akdere et al. [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF] study the effectiveness of machine learning techniques for predicting query latency of static and dynamic workload scenarios. They argue that query performance prediction using machine learning is both feasible and effective.

Related to the Semantic Web query processing, SPARQL query engines can be categorized into two categories: SQL-based and RDF native query engines [START_REF] Tsialiamanis | Heuristics-based query optimisation for SPARQL[END_REF]. SQL-based query engines rely on relational database systems storage and query optimization techniques to efficiently evaluate SPARQL queries. They suffer from the same problems mentioned above. Furthermore, due to the absence of schematic structure in RDF, cost-based approaches -successful in relational database systems -do not perform well in SPARQL query processing [START_REF] Tsialiamanis | Heuristics-based query optimisation for SPARQL[END_REF]. RDF native query engines typically use heuristics and statistics about the data for selecting efficient query execution plans [START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF]. Heuristics-based optimization techniques include exploiting syntactic and structural variations of triple patterns in a query [START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF], and rewriting a query using algebraic optimization techniques [START_REF] Frasincar | RAL: An algebra for querying RDF[END_REF] and transformation rules [START_REF] Hartig | The sparql query graph model for query optimization[END_REF]. Heuristics-based optimization techniques generally work without any knowledge of the underlying data. Stocker et al. [START_REF] Stocker | SPARQL basic graph pattern optimization using selectivity estimation[END_REF] present optimization techniques with pre-computed statistics for reordering triple patterns in a SPARQL query for efficient query processing. However, in many use-cases involving querying Linked Data, statistics are often missing [START_REF] Tsialiamanis | Heuristics-based query optimisation for SPARQL[END_REF]. This makes these statistics-based approaches ineffective in the Linked Data scenario. Furthermore, as in the case of relation database systems, these existing approaches are unable to predict actual query performance metrics such as query execution time for a given configuration.

Related to explanations for the Semantic Web, Inference Web [START_REF] Mcguinness | Explaining semantic web applications[END_REF][START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF] explanation infrastructure addresses the explanation requirements of Semantic Web applications and exposes its explanation metadata in RDF using Proof Markup Language (PML) [START_REF] Pinheiro Da Silva | A proof markup language for semantic web services[END_REF]. Inference Web provides a set of software tools for building, presenting, maintaining, and manipulating PML proofs. Inference Web provides a centralized registry based solution for publishing explanation metadata from distributed reasoners. The WIQA (Web Information Quality Assessment) framework [START_REF] Bizer | Quality-Driven Information Filtering in the Context of Web-Based Information Systems[END_REF] and KOIOS semantic search engine [START_REF] Forcher | Explanation-aware system design of the semantic search engine koios[END_REF] provide explanations of their reasoning and expose their explanation metadata in RDF. However, they provide application specific explanations which include process descriptions of specific algorithms. Although researchers [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF][START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF] highlighted the need for short explanations, previous work has not addressed the problem of providing short explanations. But researchers have studied ontology summarization. A notable work on ontology summarization is RDF sentence graph-based summarization [START_REF] Zhang | Ontology summarization based on RDF sentence graph[END_REF]. This work extracts and summarizes RDF sentences based on centrality measures.

Problem Statement and Contributions

We address the problems of SPARQL query performance prediction and explaining reasoning over Linked Data. Our aim is to assisting users in querying and consuming Linked Data. In querying Linked Data, we provide performance related information to help understand how a query may behave. Users can use this information for query construction and refinement, workload management, and query scheduling. Also, SPARQL query optimizers can use our prediction models for query plan selection. In consuming Linked Data, we explain how a given piece of data was derived. Users can use such explanations to understand and debug Linked Data. In contrast to the previous work, we propose a decentralized solution to address explanations in the distributed setting of Linked Data. Our explanations are suitable for generic Linked Data scenarios; unlike WIQA and KOIOS. Finally, we address the problem of summarizing explanations. The main goal of summarizing explanations is twofold: (a) providing a brief overview of the background information used in the reasoning, (b) providing an entry point to the full explanation. Our approach is similar to sentence graph summarization. However, we define new measures for summarizing explanations. As an application of our research, we aim to apply our methodologies and strategies for processing and explaining distributed queries on Linked Data.

Research Methodology and Approach

Predicting SPARQL Query Performance

To predict query performance metrics prior to query execution, we apply machine learning techniques on the logs of executed queries. We work with query execution time as the query performance metric. We treat the SPARQL engine as a black box and learn query behaviors from the behaviors of already executed queries. This approach does not require any statistics of the underlying RDF data, which makes it ideal for the Linked Data scenario. A key challenge in applying machine learning for SPARQL query performance prediction is to represent SPARQL queries as feature vectors. We use the frequencies and the cardinalities of SPARQL algebra operators1 of a query as its features. Additionally, to represent the query patterns as features, we first cluster the training queries based on the structural similarities between the graphs constructed from the query patterns of the training queries. Each dimension of the query pattern feature vector for a query is the structural similarity score between the graph represented by the query pattern belonging to a cluster center query and the graph represented by the query pattern belonging to the query. We use a polynomial time suboptimal solution of approximate graph edit distance problem [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] to compute the structural similarities between the graphs represented by query patterns. We use the k -mediods [START_REF] Kaufman | Clustering by means of medoids[END_REF] clustering algorithm with approximate graph edit distance as the distance function to cluster the training queries. Figure 1 shows an example of extracting the feature vector from a SPARQL query. We experiment on predicting query execution times using the support vector machine regression (SVR) [START_REF] Shevade | Improvements to the SMO algorithm for SVM regression[END_REF] with the SPARQL algebra features, using SVR with SPARQL algebra and query pattern features, using multiple SVRs for queries with different execution time ranges with SPARQL algebra and query pattern features, and finally a single k-nearest neighbors regression (k -NN) [START_REF] Altman | An introduction to kernel and nearest-neighbor nonparametric regression[END_REF] with SPARQL algebra and query pattern features. We describe the results of our experiments in section 5.1.

Generating and Summarizing Explanations

We follow the Linked Data principles [START_REF] Berners-Lee | Linked Data. W3C Design Issues[END_REF] to publish explanation metadata. We describe these metadata using our proposed vocabulary Ratio4TA 2 . We generate explanations by retrieving the explanation metatada by following their dereferenceable URIs and presenting them in a human understandable form. We define Ratio4TA as an extension of the W3C PROV Ontology 3 . This promotes interoperability by enabling data consumers to process explanation metadata according to W3C PROV standards. Ratio4TA allows describing data, reasoning processes, results, data derivations, rules, and software applications. We use the named graph mechanism [START_REF] Carroll | Named graphs, provenance and trust[END_REF] to make statements about RDF triples. Using named graph allows us to associate explanation metadata for data with different levels of granularity -explanation metadata for a triple or a graph containing more than one triple. Furthermore, we use named graphs to group together explanation metadata and make the metadata for an explanation referenceable by a single URI. We opt for our own vocabulary because the prominent previous work PML has limitations with respect to Linked Data common practices. PML uses RDF container concepts. RDF containers use blank nodes to connect a sequence of items [START_REF]RDF semantics[END_REF]. However, as a common practice, blank nodes are avoided while publishing Linked Data [START_REF] Heath | Linked Data: Evolving the Web into a Global Data Space[END_REF].

We define five measures to summarize explanations: salience (S SL ), similarity (S SM ), abstractness (S AB ), salience with respect to proof tree (S ST ), and coherence (S CO ). We compute salience of an RDF statement by combining the normalized degree centrality scores of the subject and the object of the statement. We use the measures salience, similarity, and abstractness for ranking. For the similarity measure, users can specify a set of concepts as their explanation filtering criteria. We rank the more similar statements to the concepts given in filtering criteria higher. We use the approximate query solving feature of Corese [START_REF] Corby | Searching the Semantic Web: approximate query processing based on ontologies[END_REF] for similarity computations. For abstractness, we consider a statement that is close to the root in corresponding proof tree is more abstract than a statement that is far from the root. We use salience with respect to proof tree and coherence measures to re-rank already ranked statements. We compute salience with respect to proof tree for an RDF statement by taking the average score (computed using combinations of ranking measures) of all statements of the tree that the statement roots in the corresponding proof tree. Finally we consider an RDF statement to be coherent to an RDF statement if the first statement is directly derived from the second statement. We summarize the RDF statements in an explanation using combinations of these measures.

Preliminary Results

Query Performance Prediction Results

We randomly select 6000 queries from DBPSB [START_REF] Morsey | Dbpedia SPARQL benchmark performance assessment with real queries on real data[END_REF] DBpedia4 query log dataset. Then we run them on a locally loaded DBpedia 3.8 into a Jena TDB triple store5 to record their execution times. We split the 6000 queries into 60% training, 20% validation, and 20% test splits. We use R 2 (coefficient of determination) values to evaluate our regression predictions. R 2 measures how well the regression approximates the real data points. An R 2 value of 1 means that the regression perfectly fits the data. Figure 2 shows log-log plots of the predicted and actual query execution times for the test queries for different learning methods we experimented with. Our first experiment using SVR with only SPARQL algebra features performs poorly with a low R 2 value of 0.004492. We experiment with another SVR using SPARQL algebra features and query pattern features. The R 2 value improves to 0.124204 which is still very low with outliers -highlighted in red -far from the perfect prediction line. A possible reason for this is the fact that our training dataset has queries with various different time ranges. Fitting a curve in such irregular data points is often inaccurate. To address this, we first split our training data according to execution time ranges, then we train different regressions for different time ranges. We cluster the training data into X clusters based on the execution times using x-means [START_REF] Pelleg | X-means: Extending K-means with efficient estimation of the number of clusters[END_REF] clustering algorithm. We use x-means because it automatically chooses the number of clusters. We then train X number of SVM regressions with training queries corresponding to cluster for each regression. As features, we use SPARQL algebra and query pattern features. Then we train a Support Vector Machine (SVM) classifier [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] with a training dataset containing all the training queries and the cluster number of each query as the label for the queries. For an unseen query, we first predict the cluster for the query using the SVM classifier, then we predict the execution time using the SVM regression that corresponds to the predicted cluster for that query. The accuracy of the SVM classifier on our test dataset is 96.0833%. This means that we can accurately predict the execution time ranges of unseen queries. The overall R 2 value on our test dataset with this approach jumps to 0.83862. This is demonstrated by the long running queries moving very close to the perfect prediction line. Also more queries moved towards the perfect prediction line than before. In our final experiment, we train the regression variant of k -NN algorithm with SPARQL algebra and query pattern features. We achieve an R 2 value of 0.837 on the test dataset. The result of k -NN and multiple regressions are almost same. However, the complexity of training the k -NN regression is less. Also the concentration of the short running queries near the perfect prediction line is more for k -NN.

Explanation Summarization Results

We evaluate our summarization approach by comparing the summarized explanations generated by our approach and ground truth summarized explanations generated by humans. We obtained our ground truths by surveying 24 people from different backgrounds. We used three test cases -three queries with their results along with the explanations for the results. Each query result is an inferred statement by our reasoner. Each test case has two scenarios: without filtering criteria F L, and with filtering criteria F L. Each participant answered questions for one test case. We randomly assigned a test case to a participant. We ask the participants to rate, from a scale of 1 to 5, the need for each of the statements in the explanation. For, the scenario with filtering criteria F L, we give the query, the answer, and the explanation but with a user's filtering criteria class taken from the schemata used in the reasoning process. The explanations, the questionnaires, the responses, and the results of the evaluation are publicly available online 6 . We evaluate different combinations of the summarization measures we define. For the scenario without F L, we also compare our summaries to sentence graph summarization -denoted as S SG . We evaluate evaluate summaries of different sizes by measuring F-score for summarized explanations with different compression ratios, CR. To generate the ground truth summarized explanation for an explanation, we include a statement in the ground truth summarized explanation if its rating is greater than or equal to the average rating of all the statements in the original explanation. F-scores reflects the accuracy of automatically generated summaries with respect to the ground truth summary. A desirable situation would be a summarized explanation with high F-score and low CR. Figure 3 shows the average F-scores for different measure combinations for summaries with different sizes for the three test cases. As expected, our summarization approach perform worse in the scenario with F L where we use S SM . This is due to the fact that the survey participants had to consider the highly subjective factor of similarity. An overview of our work on generating and summarizing explanations for Linked Data is available in [START_REF] Hasan | Generating and summarizing explanations for linked data[END_REF].

Evaluation Plan

Our future plan includes evaluating three more aspects. First, we would like to evaluate our prediction methods using SPARQL benchmark queries. DBPSB includes 25 query templates for evaluating SPARQL engines with DBPedia dataset. Our aim would be to generate training, validation, and test datasets from these query templates and evaluating our approach using them. Second, we would like to evaluate our prediction methods for query plan selection for SPARQL query processing over Linked Data. A possible direction for this would to use our query performance prediction approach for selecting efficient query plans in federated SPARQL query processing. Third, we will evaluate the impact of explanations and summarized explanations on end-users for a selected domain.

Conclusion

In this paper, firstly we study the techniques to predict SPARQL query performance. We learn query execution times from query history using machine learning techniques. This approach does not require any statistics of the underlying RDF data, which makes it ideal for the Linked Data scenario. We achieved high accuracy (R 2 = 0.84) for predicting query execution time.

Secondly we discuss how to generate and summarize explanations for Linked Data. We present an ontology to describe explanation metadata and discuss publishing explanation metadata as Linked Data. In addition, we presented five summarization measures to summarize explanations. We evaluate different combinations of these measures. The evaluation shows that our approach produces high quality rankings for summarizing explanation statements. Our summarized explanations are also highly accurate with F-score values ranging from 0.6 to 0.72 for small summaries. Our approach outperforms the sentence graph based ontology summarization approach.

Fig. 1 .

 1 Fig. 1. Example of extracting SPARQL feature vector from a SPARQL query.

Fig. 2 .

 2 Fig. 2. Comparison of learning methods.

  The x-axis represents compression ratio CR. The y-axis represents F-scores. For the scenario without F L, the best F-score is 0.72 when CR value is 0.33 by the measure combinations S SL + S AB + S ST and S SL + S AB + S ST + S CO . This is a desirable situation with a high F-score and low CR. The sentence graph summarization performs poorly with a best F-score value of 0.34 in the CR interval 0.05 to 0.3. For the scenario with F L, the best F-score is 0.66 at CR values 0.53 and 0.55 by the measure combinationS SL + S SM . However, the F-score 0.6 at CR value 0.3 by the measure combination S SL + S AB + S SM + S CO is more desirable because the size of the summary is smaller.

⋆ Advisors: Fabien Gandon and Pierre-Antoine Champin

http://www.w3.org/TR/sparql11-query/#sparqlQuery

http://ns.inria.fr/ratio4ta/

http://www.w3.org/TR/prov-o/

http://dbpedia.org

Jena TDB: http://jena.apache.org/documentation/tdb

http://ns.inria.fr/ratio4ta/sm/

Acknowledgments: This work is supported by the ANR CONTINT program under the Kolflow project (ANR-2010-CORD-021-02).