Problem Statement and Motivation In the last decade, the traditional Web is evolved in the Web of Data, where huge collections of structured data are gathered over distributed, heterogeneous sources. These datasets are often exploited much below their potential due to difculties in accessing them. Processing complex requests on diverse and dynamic sources requires: (i) source selection; (ii) actual processing of the request on the relevant, and usually big in size, sources. The overall process may not guarantee user satisfaction, since the request may be processed on inaccurate, incomplete, unreliable data; or the processing time may be inadequate to the query urgency. In [1], the authors claimed that user pro les and request contexts, data and processing quality, and information about similar requests recurring over time could be exploited to inform query processing and cope with these issues. In this thesis, we focus on recurring retrieval needs for improving query processing. Recurring retrieval needs have been considered in query processing for a very long time in terms of materialized views and caching approaches. Both of them su er from some problems when applied to the reference scenarios. Materialized views associate a result with a given query even if, for improving e ciency, additional information could be of interest (e.g., the set of used data sources). On the other hand, caching approaches usually rely on precise query matching, not always suitable in the reference environments, and, similarly to materialized views, cached queries are usually associated with query results. The aim of the thesis is to exploit how information about similar requests recurring over time can be exploited in order to e ciently and e ectively process complex requests on heterogeneous and dynamic data sources, while guaranteeing user satisfaction and limiting as much as possible user interactions. In particular, we propose a new smart caching technique that gets over the limitations of current approaches by: (i) taking advantage of prior processing in order to obtain shortcuts to di erent points in the query processing stack, with a special emphasis on source selection, thus providing a multilayer caching approach;
(ii) relying on relaxed matches; (iii) providing a human-in-the-loop solution by which user feedback as well as query and data contexts are taken into account in cache management.
We claim that the proposed approach could be quite e ective in processing complex requests on diverse and dynamic sources. Indeed, by maintaining not only query results but also more general processing information collected during processing, like the set of selected sources, in distinct but related caches, we will be able to cope with the trade-o between data dynamicity and accuracy of the result. By exploiting relaxation, performance can also be improved, since the number of cache hits will increase. Relaxation, as well as the adoption of a human-in-the-loop solution, can nally increase user satisfaction, in terms of both quality of data (accuracy and completeness of the result) and quality of service (execution time).
Our smart cache approach is also quite innovative: as far as we know, no multilayer caching approach, taking into account source selection, has been proposed so far. The exploitation of relaxation and human-in-the-loop features in cache management is also quite original, moving to a traditional physical task features that are typical of higher level processing steps.
The proposed approach is an instantiation of the framework proposed in
[
We rst introduce the reference architecture for source selection caching we rely on in the overall multilayer approach. Then, a preliminary proposal for relaxed cache matches is discussed. 1 A RDF set of triples available on the Web.
E cient and E ective Source Selection in the Web of Data
Reference architecture. We extend the caching framework for RDF data and
SPARQL queries in [
Fig. 1 shows the resulting reference architecture. Given a query Q as input,
the Dynamic Programming Planner module, from [
In order to design a cache for source selection, we rst modi ed the cache
module with the aim of associating sets of source identi ers, instead of sets of
data items, to cached queries. All cached queries sharing a common structure
(called skeleton) are cached together, relying on a tree structure. The
processing engine has then been modi ed to cope with source selection execution. To
this aim, we relied on the index-based source selection approach proposed in [
The problem is now the following: given a query Q and n cached queries Q1,...,Qn, nd Q 2 fQ1; :::; Qng such that Q generalizes Q and it has the minimum relaxation cost relax C from Q, i.e., relax C(Q; Q) = minin=1relax C(Q; Qi): The relaxation cost is de ned on query canonical representations. relax C(Q1; Q2) returns 1 if Q2 does not generalize Q1 (i.e., it is not possible to nd in Q2, for each triple pattern in Q1, a triple pattern with a more general predicate, according to the taxonomy O, and with the same subject and object). Otherwise, the returned value depends on how "far" is each triple pattern in Q2 from the corresponding one in Q1. Distance is de ned in terms of the path length between predicates in the taxonomy O.
In order to e ciently select query Q as described above, we assume that cached queries are indexed by a tree, where each node corresponds to a query triple pattern and each path from the root to a leaf corresponds to a cached query. The cached query at the minimum cost is then selected by a variation of the A algorithm.
We are currently working on an extension of this algorithm to take into account not only the generalization cost but also the cost for accessing sources. To this purpose, we plan to associate some statistics related to sources with each index leaf and use them, combined with the generalization cost, in computing the total cost. Another relevant extension concerns the usage of more generic ontologies for de ning relaxed matches.
We plan to extend the work presented in Section 2 in several directions: { Integrating the relaxation approach in the reference architecture. { Integrating the source cache with a traditional cache for query processing over Linked Data and de ning speci c cache policies for a combined usage of both caches, depending on data dynamicity and target result accuracy, for both precise and relaxed queries. { Extending the proposed smart caching approach so that the choice of the queries to cache is not only based on a recurrence principle, but also on a diversi cation principle, thus avoiding to keep in cache queries that are too similar or one is a slight relaxation of the other. { Extending the proposed smart caching approach to bring the human in the loop, through the usage of speci c cache management policies taking care of user feedbacks as well as query and data contexts. { Experimentally evaluating the proposed approach, with reference to Linked Data sets, di erent query patterns, and di erent recurrence patterns. We will start with a synthetic workload but we will then look for a real workload. The main aim of the evaluation will be to measure the increase in e ciency (in terms of source selection and overall query processing costs), with varying amounts of available space, and the result accuracy due to the degree of approximation introduced by relaxation.