Web规模RDF图数据的高效率路径查询及推理研究

作为语义Web的数据基础，RDF图数据在链接数据运动推动下规模已达百亿条三元组。在Web规模RDF图上高效率导航式路径查询扮演着重要角色。但RDF标准查询语言SPARQL不支持路径查询，造成任意长度导航和本体层语义查询及推理无法通过实例层查询来表达。本项目提出利用嵌套正则表达式为SPARQL子图模式匹配引入路径查询语法并精确定义其语义，在保证路径查询核心表达力的同时，将复杂度类控制为PTIME；提出基于图论的节点编码和路径索引方案，设计高效率路径查询处理算法，利用近似方法将查询执行复杂度降为与RDF图大小成线性关系以下，以适应Web规模RDF数据量；提出使用路径查询表达本体层RDFS和OWL推理，将推理融入到查询中，为领域用户提供知识发现的新工具。本项目利用开源RDF数据库Virtuoso作为实验平台并在其上开发原型系统，实现高效率的支持本体层语义查询及推理的RDF导航式路径查询机制。

作为语义Web的数据基础，RDF图数据在“关联数据”运动的推动下，规模已达百亿条三元组。在Web规模RDF图上高效率导航式路径查询扮演着重要角色。本项目研究支持本体层语义查询及推理的高效率RDF导航式路径查询处理机制。本项目自2012年1月1日开始执行至2014年12月31日结束，3年来项目依照《资助项目计划书》执行，取得了一系列有价值的重要成果。. (1) RDF图数据上路径查询的语法和语义定义. 定义了与标准SPARQL 兼容的路径查询语法，使导航式查询无缝地集成到了现有的标准SPARQL子图模式匹配中。基于形式化的数学方法，利用嵌套正则表达式给出了RDF路径查询语法和语义的严格定义；以此为理论依据，对路径查询表达力和复杂度的权衡进行了精确量化评估，为RDF路径查询提供无二义性的准确语法和语义，证明了其计算复杂度为多项式级别的，为其高效率实现奠定计算复杂度的理论基础。. (2) RDF图数据的节点编码、路径索引和路径查询处理算法. 结合RDF图节点编码设计出一种RDF路径索引，利用局部路径的索引信息快速回答全局路径查询问题。利用有限的查询覆盖率支持尽可能多的路径查询要素。利用路径索引的支持设计出一种高效率的RDF路径查询处理算法。研究如何利用近似方法放松对查询结果的限制，在不要求查询结果全面性或准确性的前提下，进一步降低路径查询处理的计算复杂度。. (3) 利用RDF路径查询表达语义Web推理. 将RDFS、OWL和OWL2等不同层面的推理功能表达为路径查询。将路径查询的方法应用到基于本体的语义检索、面向公理的本体可视化、知识库一致性检验等方面。. 本项目所取得的研究成果共发表论文15篇，申请专利4项，获得软件著作权1项。通过本项目培养博士生1人、硕士生6人。