As RDF becomes more widely established and the amount of linked data is rapidly increasing, the efficient querying of large amount of data becomes a significant challenge. In this paper, we propose a family of algorithms for querying large amount of linked data in a distributed manner. These query evaluation algorithms are independent of the way the data is stored, as well as of the particular implementation of the query evaluation. We then use the MapReduce paradigm to present a distributed implementation of these algorithms and experimentally evaluate them, although the algorithms could be straightforwardly translated into other distributed processing frameworks. We also investigate and propose multiple query decomposition approaches of Basic Graph Patterns (subclass of SPARQL queries) that are used to improve the overall performance of the distributed query answering . A deep analysis of the effectiveness of these decomposition algorithms is also provided.

In this paper we investigate within-record referential constraints on tree-structured data. We consider an SQL-like query language such that the one used in Dremel and we call it tree-SQL. We show how to define and process a query in tree-SQL in the presence of referential constraints. We give the semantics of tree-SQL via flattening and show how to produce equivalent semantics using the notion of tree-expansion of a query in the presence of referential constraints.

In this paper, we study the problem of finding an equivalent rewriting of an XPath query using multiple views, and we show that the union operator may be required in order to find such a rewriting. In particular, focusing on the fragment of XPath containing both descendant edges and wildcard labels, we propose an algorithm that outputs a union of single-view rewritings (if there exists any) which equivalently rewrites a given query. For the same fragment of XPath, we give necessary and sufficient conditions for query containment and equivalence of unions of queries.