关键词: 可排序视图, 倒排表, Mapreduce, 模式重写

Abstract: Along with the rocketing amount of data in semantic web, querying in RDF data set has become a urgent problem to be solved. Traditional RDF pattern matching methods based on materialized views can reduce the times of table joining, speed up the rewriting process of query pattern, but the problem of retrieving matching views in view sets is equivalent to subgraph isomorphism, which is NP-hard. In order to reduce the cost of query pattern rewriting, and improve the efficiency of RDF pattern matching, the concept of sorted view is introduced, contain mapping discovery algorithm is designed and it simplifies the process of contain mapping discovery between patterns with the same length and ensures linear correlation between the matching price and the scale of input data. Furthermore methods of searching candidate sorted views through inverted list or MapReduce are proposed and RDF pattern rewriting algorithm is implemented to solve pattern matching problem in different data sets. Theoretical analysis and experimental results demonstrate that the RDF pattern matching algorithms based on sorted view can reach the trade-offs between efficiency and scalability.

Key words: sorted view, inverted list, MapReduce, pattern rewriting