Distributed RDF Query Processing and Reasoning in Peer-to-Peer Networks
Zoi Kaoudi · 2011
Abstract. With the vast amount of available RDF data sources on the Web increasing rapidly, there is an urgent need for RDF data manage-ment and RDFS reasoning. In this thesis, we focus on distributed RDF data management in peer-to-peer (P2P) networks. More specifically, we present results that advance the state-of-the-art in the research area of distributed RDF query processing and reasoning in P2P networks. We fully design and implement a P2P system, called Atlas, for the distributed query processing and reasoning of RDF and RDFS data. Atlas is built on top of distributed hash tables (DHTs), a commonly-used case of P2P networks. Initially, we study RDFS reasoning algorithms on top of DHTs. We design and develop distributed forward and backward chaining algo-rithms, as well as an algorithm which works in a bottom-up fashion using the magic sets transformation technique. We study theoretically the cor-rectness of our reasoning algorithms and prove that they are sound and complete. We also provide a comparative study of our algorithms both analytically and experimentally. In the experimental part of our study, we obtain measurements in the realistic large-scale distributed environment of PlanetLab as well as in the more controlled environment of a local cluster. Moreover, we propose algorithms for SPARQL query processing and optimization over RDF(S) databases stored on top of distributed hash tables. We fully implement and evaluate a DHT-based optimizer. The goal of the optimizer is to minimize the time for answering a query as well as the bandwidth consumed during the query evaluation. The optimization algorithms use selectivity estimates to determine the cho-sen query plan. Our algorithms and techniques have been extensively evaluated in a local cluster. 1