Rewriting (SPARQL) Queries on SPARQL Views

Wangchao Le, Songyun Duan, Anastasios Kementsietsidis, Feifei Li and Min Wang

[Overview] [Papers and Talks] [Source Code] [Contacts]

Overview

The problem of answering SPARQL queries over virtual SPARQL views is commonly encountered in a number of settings, including while enforcing security policies to access RDF data, or when integrating RDF data from disparate sources. We approach this problem by rewriting SPARQL queries over the views to equivalent queries over the underlying RDF data, thus avoiding the costs entailed by view materialization and maintenance. We show that SPARQL query rewriting combines the most challenging aspects of rewriting for the relational and XML cases: like the relational case, SPARQL query rewriting requires synthesizing multiple views; like the XML case, the size of the rewritten query is exponential to the size of the query and the views. In this paper, we present the first native query rewriting algorithm for SPARQL. For an input SPARQL query over a set of virtual SPARQL views, the rewritten query resembles a union of conjunctive queries and can be of exponential size. We propose optimizations over the basic rewriting algorithm to (i) minimize each conjunctive query in the union; (ii) eliminate conjunctive queries with empty results from evaluation; and (iii) efficiently prune out big portions of the search space of empty rewritings. The experiments, performed on two RDF stores, show that our algorithms are scalable and independent of the underlying RDF stores. Furthermore, our optimizations have order of magnitude improvements over the basic rewriting algorithm in terms of both the rewriting size and evaluation time.

Paper and Talk

Rewriting (SPARQL) Queries on SPARQL Views,

    Final version:   Talk:   

Source Code

Rewriting [.tgz]

Readme

There is a Makefile in the tarball, simply command 'make' to build. Most likely, you will encounter errors the first few times you build, please follow the message to modify the Makefile and make other necessary changes, e.g., setting the correct environment variables. There are also a simple query and a simple view provided in the tarball. The tarball also contains our implementation for AKMV synopses.

If you find our work useful, please kindly cite our paper!

Contacts

You can send an email to Wangchao Le      


Last Updated: Dec 2014