中文摘要：

社交网络、生物信息、交通网络等领域技术的发展产生了大规模图数据。图路径查询是多种图数据应用以及图其他复杂操作的基础。大规模应用环境中的图数据规模、查询的灵活性、图基本操作的复杂性使得有效实现图路径查询面临巨大挑战，迫切需要提出新的查询理论和方法来加以支持。本课题从不同层面研究了图路径查询的关键技术。在逻辑层面，本课题研究基于图数据模式的路径查询逻辑优化算法、基于图结构自动机的图路径查询重写算法、基于结果有效性的图路径查询结果排序算法、结合图统计特性的图路径查询近似算法。在物理层面，本课题研究面向图路径查询的物理操作集合和运算规则、基于代价的图路径查询物理执行计划优化策略、基于K-Distance 的图结点Dewey 编码索引、基于图模式的关系数据库图数据优化存储。本课题最终提出实现图路径查询的一系列关键技术，有效支持图数据应用环境中的数据查询和分析。