You are here

A Storing Scheme and A Merge Join Algorithm for RDF Query Processing

21st October: Akiyoshi Matono (from AIST)

Today, RDF (Resource Description Framework) is used as a foundation of description of resources. The amount of RDF data has grown extraordinarily, such as Linked Open Data. Therefore, the query processing for RDF data is an essential issue. In this talk, I present two approaches for RDF query processing; namely a storing scheme and a merge join algorithm. Our proposed storing scheme is based on the structure of given RDF documents. RDF documents consists of a set of segments which are structured to be easily understood by human. In other words, some joins have already been performed in each segment. Our storing scheme stores the RDF segments in RDF documents into their corresponding relational tables as they are. Thus, our approach can reduce the number of join operations. Our proposed merge join algorithm can reduce the I/O cost by skipping unnecessary data. For this algorithm, we extend Bloom filter to be able to be used for disjoint test and also extend B+ tree to make each internal node possess the extended Bloom filters in order to represent its descendant keys. Our join algorithm traverses the two extended B+ trees while comparing two nodes of them in order to check whether an intersection exists in descendant keys.

PDF icon 2111-10-21_Edinburgh.pdf539.62 KB