背景与问题定义
实体间关系数据规模和关联程度不断增长，关系数据模型在现实和数字世界现象的探索、描述、预测和解释中发挥越来越重要的作用。图数据模型通过节点集合、边集合、边与端点关联函数、节点和边标签函数以及节点和边属性键值对函数来刻画实体间关系。图上路径刻画实体间的间接关系，例如社交网络中的推荐场景。路径查询分类包括判定问题、计数问题和枚举问题，其中判定问题即为可达性查询。图查询语言如SPARQL、RDF和Cypher等都支持路径查询。然而，当图规模巨大且动态变化、查询具有复杂约束条件时，高效地回答路径查询具有挑战性。
IFCA：利用动态图上的社区结构加速可达性查询
IFCA（Index-Free Community-Aware Reachability Processing Over Large Dynamic Graphs）算法利用动态图上的社区结构加速可达性查询。给定有向图和一对节点，IFCA通过判断一对节点的个性化页面排名（PPR）值是否大于0来回答可达性查询。动态图给基于索引的可达性算法带来挑战，因为索引重建或增量更新可能比查询慢很多。IFCA算法采用两阶段搜索策略：基于PPR的双向搜索算法和社区收缩，以及基于代价估计的搜索策略选择。实验结果表明，IFCA在动态图上具有高效性和准确性，优于其他可达性算法。
利用物化视图加速图上的正则路径查询
Materialized View Selection & View-Based Query Planning for Regular Path Queries算法通过物化视图加速图上的正则路径查询（RPQ）。RPQ是以边标签为字母表的正则表达式，物化视图选择（MVS）通过将某些子查询选为物化视图、离线计算其结果供在线使用来实现负载中相似RPQ之间的共享计算。MVS for RPQ问题定义是在给定有向图、RPQ负载和内存上限的情况下，返回满足条件的物化视图集合，最小化在线处理效率（最小化查询时间代价）。算法使用AND-OR DAG with Closure (AODC)表达RPQ负载的联合查询计划，并设计基于AODC的MVS算法和基于物化视图的增量计划选择。实验结果表明，基于AODC的MVS算法和基于物化视图的查询效率均显著高于不使用物化视图的查询，并且优于其他RPQ算法。
未来整合机遇
未来可以将高效的路径算法整合到图数据库系统中，包括计划枚举器和代价与基数估计器。计划枚举器枚举查询的等价计划并选择其中估计代价最低的用于执行，代价与基数估计器为计划选择提供代价与基数估计值。整合这些算法可以提升图数据库系统的查询效率和性能。
