一种基于可排序视图的RDF模式匹配算法

摘要

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