A Proposal of CS-index Approach for SPARQL Queries Considering Chain and Star Shaped Subgraphs
Khin Myat Kyu, Kay Thi Yar, Aung Nway Oo · 2018
The interlinking nature of web-scale RDF data makes a challenge on storage and retrieving of these data efficiently. Even though different storage and query processing techniques have been proposed, query processing on complex linking structured (RDF) data requires many join operations when the input query is large (with respect to number of triple patterns). One solution to this problem is to reduce the number of joins by indexing. Indexing is an effective technique to reduce data searching space and retrieve data as fast as possible. In this paper, we propose an indexing scheme of chain and star (CS-index) and querying approach for SPARQL queries. The proposed approach could support both chain and star shaped queries. It employs graph pattern based technology: the RDF data graph is firstly decomposed into chain and star shaped subgraphs based on the structural information of each vertex. These subgraphs are stored as index, called CS-index. When a SPARQL query is given, it is decomposed into query subgraphs based on common join variable among all triple patterns. And the query results are retrieved by matching these query subgraphs against with CS-index. The proposed approach tends to minimize the query execution time by reducing the number of join operations as well as reduce memory usage for storing data.