RDF Pattern Matching using Sortable Views

In the last few years, RDF is becoming the dominating data model used in semantic web for knowledge representation and inference. In this paper, we revisit the problem of pattern matching query in RDF model, which is usually expensive in efciency due to the huge cost on join operations. To alleviate the efciency pain, view materialization techniques are usually deployed to accelerate the query processing. However, given an arbitrary view, it remains dif-cult to identify how to reuse the view for a particular query, be-cause of the NP-hardness behind the algorithm matching patterns and views. To fully exploit the benet of the materialized views, we propose a new paradigm to enhance the effectiveness of the materialized view. Instead of choosing materialized views in ar-bitrary form, our paradigm aims to select the views only if they are sortable. The property of sortability raises huge gains on the pattern-view matching, bringing down the cost to linear complex-ity in terms of the pattern size. On the other side, the costs on identifying sortable views and searching over the views using in-verted index are affordable. Moreover, sortable views generally improve the overall performance of pattern matching, by means of a cost model used to optimize the query rewriting on the most ap-propriate views. Finally, we demonstrate extensive experimental results to verify the superiority of our proposal on both efciency and effectiveness