RDF partitioning for scalable SPARQL query processing

• Published in: Frontiers of Computer Science 2015-12, Vol.9 (6), p.919-933
• Main Authors: WANG, Xiaoyan, YANG, Tao, CHEN, Jinchuan, HE, Long, DU, Xiaoyong
• Format: Article
• Language: English
• Subjects: Algorithms; Cloud computing; Computer Science; data partitioning; Datasets; Partitioning; Queries; Query processing; RDF; RDF data; Redundancy; Research Article; SPARQL query; Workload; 分区方案; 可扩展性; 影响系统; 数据冗余度; 方式划分; 查询处理; 计算平台
• ISSN: 2095-2228; 2095-2236
• DOI: 10.1007/s11704-015-4104-3

The volume of RDF data increases dramatically within recent years, while cloud computing platforms like Hadoop are supposed to be a good choice for processing queries over huge data sets for their wonderful scalability. Previous work on evaluating SPARQL queries with Hadoop mainly focus on reducing the number of joins through careful split of HDFS files and algorithms for generating Map/Reduce jobs. However, the way of partitioning RDF data could also affect system performance. Specifically, a good partitioning solution would greatly reduce or even totally avoid cross-node joins, and significantly cut down the cost in query evaluation. Based on HadoopDB, this work processes SPARQL queries in a hybrid architecture, where Map/Reduce takes charge of the computing tasks, and RDF query engines like RDF-3X store the data and execute join operations. According to the analysis of query workloads, this work proposes a novel algorithm for automatically partitioning RDF data and an approximate solution to physically place the partitions in order to reduce data redundancy. It also discusses how to make a good trade-off between query evaluation efficiency and data redundancy. All of these proposed approaches have been evaluated by extensive experiments over large RDF data sets.