Multi-objective Linked Data Query Optimization : Technical Report

With the rapid proliferation of Linked Data on theWeb, the topic of Linked Data query processing has recently gained attention. Works in this direction do not assume full availability of SPARQL endpoints. As an alternative to federation over these endpoints, this new querying paradigm follows the Linked Data principles to use only HTTP lookups for accessing and querying Linked Data. Existing works focus on the ranking and pruning of sources behind the query URIs, or on the ecient processing of data after they have been retrieved from sources. However, there exists no systematic approach for query plan optimization, especially the kind that considers both of these problems in a holistic way. Further, observing that result completeness is no longer a strict requirement and that there is an inherent trade-o between completeness, execution cost and other criteria, we propose a multi-objective optimization framework. In experiments on real world Linked Data, Pareto-optimal plans computed by our approach show benets over suboptimal plans generated by existing solutions.