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

摘要： 随着语义网络中数据量的激增，在RDF数据集中高效查询数据已成为一个亟待解决的问题。传统的基于物化视图的RDF模式匹配方法虽然能降低表的自连接操作次数，加快查询模式重写过程，但在视图集中检索模式匹配的视图等价于子图同构这一NP-hard问题。为了减小查询模式重写代价，提高RDF模式匹配过程效率，引入可排序视图概念，设计包含映射发现算法contain及其扩展算法contain+，简化等长度模式间包含映射发现过程，同时保证模式间的匹配代价与输入数据的规模线性相关。此外，提出基于倒排表/MapReduce检索候选可排序视图的方法，实现RDF模式重写算法rewrite，用以处理不同规模数据集上的模式匹配问题。理论分析及实验证明，基于可排序视图的RDF模式匹配算法能有效地兼顾算法效率及算法可扩展性。

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