基于嵌套正则表达式的RDF图数据属性路径查询及推理

Nested Regular Expression Based Property Paths Querying and Reasoning on RDF Graph Data

SPARQL 1.1引入的属性路径查询提供了大规模RDF图数据上进行路径查询的支持.现有的属性路径查询实现方案均基于多重索引,经过多次迭代查询实现,效率低下,且只能对显式的RDF三元组进行查询,不具备推理能力.嵌套正则表达式可以支持全部的RDFS推理,并在多项式时间复杂度内执行路径查询.因而,将属性路径查询转化为嵌套正则表达式的求值,可以提高查询效率,挖掘隐藏信息.实现了RDFS-Plus原型系统,包括属性路径查询的解析器和基于嵌套正则表达式的查询引擎,采用基于自动机的图算法,避免了求RDF图闭包.最后,提供了与ARQ和Sesame的对比实验.实验表明,提出的基于嵌套正则表达式的RDF图数据属性路径查询方法不仅可以支持推理,而且维持了多项式的计算复杂度.

SPARQL 1.1 introduces Property Paths, which supports querying on large-scale RDF graph. All the existing implementations of Property Paths query are based upon multiple indexes and iterations. Those systems can only query on explicit RDF triples inefficiently and not support reasoning features. The nested regular expression provides the reasoning features for RDFS and the complexity of path querying operation is polynomial. To obtain the efficiency of querying and mine the implicit information, we translate the Property Path queries to the evaluation of Nested Regular Expression. We implement the RDFS Plus prototype system including a Property Paths Parser and a nested regular expression query engine. Our algorithm is based on automaton and avoids the computation of RDF graph closure. We perform a comparative experiments compared with ARQ and Sesame. The experimental result shows that our algorithm can support reasoning in polynomial time.