面向RDF图的多模式匹配方法

模式匹配问题指的是搜索所有同构于模式图的数据子图,它是一种典型的子图同构问题。多模式匹配问题是对模式匹配问题的一个扩展,其主要的挑战是多个模式图之间的并发执行策略。为了应对这个挑战,提出一种面向RDF图的模式匹配方法(M-PM)。通过计算多个模式图之间的公共查询子图,根据查询子图、模式图的包含关系构建依赖树;提出节点分片表的概念,用来扩展依赖树中单一的包含关系;设计了一种快速的多模式匹配算法,其通过对数据图的一次遍历便可以求得多个模式图的匹配子图。实验结果表明,M-PM方法比一般方法提高了约70%执行时间效率。在处理相同规模的模式图的情况下,M-PM方法执行效率只与残差边个数有关,残差边越少执行效率越高。