数据技术嘉年华：智能·云原生·一体化——DB与AI协同创新，模型与架构融合发展

图上的高效路径查询 邹磊 北京大学 王选计算机研究所数据管理实验室 大纲 •背景•IFCA：利用动态图上的社区结构加速可达性查询（ICDE’23）•利用物化视图加速图上的正则路径查询（SIGMOD’24）•在图数据库系统的查询执行流程中整合高效路径算法的未来机遇 新型场景：聚焦实体间关系 数据不仅在规模上不断增长，更关键的是相互关联的程度也不断提升。探索、描述、预测和解释现实世界和数字世界的现象，越来越依赖于能刻画实体间关系的数据模型。 --AngelaBonifati,AlexandruIosup,SherifSakr, and Hannes Voigt. Big Graph Processing Systems (DagstuhlSeminar 19491). InDagstuhlReports,Volume 9, Issue 12, pp. 1-27, SchlossDagstuhl- Leibniz-ZentrumfürInformatik(2020) 社交网络聚焦社交关系 金融风控聚焦交易关系 知识图谱聚焦概念关联 互联网聚焦超链接 生物化学聚焦化学反应 •𝐀:节点集合•𝐀:边集合•𝐀:𝐀→𝐀×𝐀,将边与其端点相关联•𝐀:𝐀∪𝐀→𝐀ℒ,给节点和边分配标签•𝐀:𝐀∪𝐀×𝐀→𝐀,给节点和边分配属性键值对 图上的一条路径是边的有限序列𝐀1,𝐀2, …,𝐀𝐀，其中𝐀𝐀=𝐀𝐀,𝐀𝐀∈𝐀，且对于𝐀=1,2, …,𝐀，𝐀𝐀=𝐀𝐀+1（首尾相接）。路径刻画实体间的间接关系。例如，应用于社交网络中的推荐场景：“我间接关注的用户”→“我可能感兴趣的用户”“我关注的人点赞过的帖子”→“我可能感兴趣的帖子” 路径查询的分类 约束 结果形式 判定问题计数问题枚举问题 起始/目标节点路径长度节点/边的标签节点/边的属性过滤条件 •给定起始和目标节点+为判定问题=可达性查询•给定起始节点+限定路径长度为最短+枚举问题=单源最短路径查询•给定以边标签集合为字母表的正则路径+枚举问题=正则路径查询例 图查询语言中的路经查询 示例查询目标：查找在社交网络中David直接或间接认识的所有人 ISO/GQL SPARQL Cypher Neo4j的查询语言 RDF（知识图谱和LinkedData的数据模型）的标准查询语言 正在开发中的ISO标准图查询语言 SELECT?person WHERE{?david .?david“David” .?david+?person .} MATCH(:Person {name:“David”)-[:knows*1..]->(person)RETURNperson MATCH(:Person WHEREname=‘David’)-[:knows*1..]->(person)RETURNperson 路经查询的挑战 当图规模巨大且动态变化、且查询具有复杂的约束条件时，高效地回答路径查询是具有挑战性的。 优化技术： •利用图的结构特征•去除冗余（无用或重复）计算•改进图数据访问的局部性•并行化•… IFCA：利用动态图上的社区结构加速可达性查询 I F C A : I n d e x - F r e e C o m m u n i t y - A w a r e R e a c h a b i l i t yP r o c e s s i n g O v e r L a r g e D y n a m i c G r a p h s Yue Pang, Lei Zou, Yu LiuPeking UniversityICDE 2023 •问题定义:给定有向图𝐀=𝐀,𝐀和一对节点𝐀,𝐀∈𝐀,可达性查询当从𝐀到𝐀存在至少一条有向路径时返回真，否则返回假 •应用： •电子商务图：检测欺诈活动•社交网络：实施访问控制•… •基本思路：在图上的社区结构中搜索时，减少无用的计算 ü利用图的结构特征ü去除冗余（无用或重复）计算 过往工作：静态图上基于索引的可达性算法 动态图给基于索引的可达性算法带来挑战 •索引重建或增量更新可能比查询慢高达5个数量级•因此，不基于索引的可达性算法在动态图上更具优势•本文发表前最新的不基于索引的算法[2]是近似算法，无法保证结果准确性 背景：个性化页面排名（Personalized PageRank, PPR） 定义：假设给定有向图𝐀=𝐀,𝐀，节点数为𝐀、边数为𝐀 •给定一个起始节点𝐀、一个目标节点𝐀、停止概率𝐀从s发起随机游走，每步•以𝐀概率停在当前节点上，•以1−𝐀概率随机跳转到任一出邻居 •从𝐀到𝐀的PPR值： •𝐀𝐀,𝐀=ℙ[从𝐀发起的随机游走停止于𝐀]•表示从𝐀的视角看，节点𝐀的重要程度 背景：个性化页面排名（Personalized PageRank, PPR） 蒙特卡洛模拟[SIAM J.Numer.Anal.07], etc. 基于推送（Push）的技术[KDD17],etc. 幂迭代[SIGMOD21], etc. 𝐀=1−𝐀𝐀𝐀+𝐀∙𝐀p𝐀: PPR向量p𝐀:初始化向量p𝐀:转换矩阵p𝐀:停止概率 每 个 节 点𝐀维 护 一 个残 差 值 （re s i d u e）𝐀𝐀,𝐀和保留值（reserve）𝐀𝐀,𝐀;每轮迭代向邻居推送部分残差值，剩余部分转化为本节点的保留值，最终保留值为PPR估计 从s出发采样若干随机游走𝐀𝐀,𝐀=采样的随机游走停止于𝐀的比例 背景：图上的社区结构 社区是内部密集连接、与外部稀疏连接的子图 传导度（Conductance）是社区质量的一种衡量指标。 Φ𝐀=|𝐀𝐀|min𝐀𨰀𝐀𝐀,2𝐀−𝐀𨰀𝐀𝐀 •传导度越低，社区内部相对于外部连接越密集•给定一个起始节点s，它周围的社区由相对s具有高PPR值的节点构成（可证明由这些节点诱导的子图具有足够低的传导度[4]） [4] R. Andersen, F. Chung, and K. Lang, “Local Graph Partitioning using PageRank Vectors,” in 2006 47thAnnual IEEE Symposium on Foundations of Computer Science (FOCS’06), Berkeley, CA, USA, 2006, pp.475–486. 背景：图上的社区结构 ü提升社区内可达性查询的效率ü将提升推广到跨社区可达性查询 主要工具：个性化页面排名（PPR） 基于PPR的基准算法 给 定 有 向 图𝐀=𝐀,𝐀、 一 对 节 点𝐀,𝐀∈𝐀,以下性质成立： 𝐀→𝐀⇔𝐀𝐀𝐀𝐀𝐀>0,𝐀𝐀𝐀𝐀𝐀(=𝐀𝐀,𝐀)： 节 点𝐀相 对𝐀的PPR值因此，可以通过判断一对节点的PPR值是否大于0来回答可达性查询采用基于推送的技术，因其框架与图遍历相近 基准算法的优势、不足与改进方针 社区内查询（s、t在同一社区中） 基准算法（基于推送的PPR算法）更倾向于首先访问相对起始节点PPR值高的节点，这些节点往往围绕起始节点形成一个社区。 BFS对社区结构无感知，需要覆盖到社区中节点时，会浪费更多边访问。 DTC 2024 基准算法的优势、不足与改进方针 跨社区查询（s、t在不同社区中） 基准算法面临以下问题： •较大的𝐀值（残差阈值，𝐀越大越早终止）：导致提前终止，无法将搜索前沿推进到社区之外，从而产生假阴性•较小的𝐀值：导致残差值在图上的环路中反复传播，造成冗余计算•同样难以处理社区结构不明显的图 基准算法的优势、不足与改进方针 “Let each bird sing its own song” 我们提出一种两阶段的搜索策略 •基于PPR的双向搜索算法ü高效回答社区内查询•社区收缩ü高效回答跨社区查询•基于代价估计的搜索策略选择（何时切换到BFS）ü高效回答社区结构不明显的图上的查询 两阶段搜索策略的挑战 1.如何快速找到起始节点周围的社区？2.如何避免处理跨社区查询时社区内的冗余边访问？3.如何找到合适的切换到BFS的时机？利用子图传导度和PPR之间的关系使用社区收缩技术设计代价模型，估计两种搜索策略未来的开销 我们的方法：IFCA 第一步：给定残差阈值𝐀𝐀𝐀𝐀,进行基于PPR的搜索（以从起始节点s的前向搜索为例，实际为双向） 使用基于PPR的搜索，可快速判定目标节点t是否在包含s的社区中，进而判定可达性 每轮迭代中，通过逐步降低当前的残差阈值ϵcur来“松弛”社区，直至ϵcur<ϵpre 第二步：当𝐀𝐀𝐀𝐀<𝐀𝐀𝐀𝐀时，执行社区收缩（将已访问的节点收缩为一个超节点），并以超节点为新的起点继续基于PPR的搜索 突破社区界限，避免冗余边访问可高效搜索到目标节点t’ 第三步：随着社区收缩多次执行，图变得更加稀疏、社区结构越发不显著，基于PPR的搜索策略逐渐失去优势基于我们设计的代价模型，估计两种搜索策略的未来开销，当BFS开销更低时，切换到BFS可高效搜索到目标节点t′′ 实验：验证选取切换点的策略具有近似最优性 “预言”最优切换点的搜索算法（Oracle）：总是选择导致最短查询时间的切换点，通过枚举所有可能切换点、统计最短查询时间得到 与始终执行基于PPR的搜索+社区收缩的算法（Contract）、BiBFS相比，IFCA与Oracle最接近 ，且差距总在约2倍以内 实验：与当前最先进的可达性算法对比 DTC 2024 PART 03 利用物化视图加速图上的正则路径查询M a t e r i a l i z e d V i e w S e l e c t i o n & V i e w - B a s e d Q u e r y P l a n n i n gf o r R e g u l a r P a t h Q u e r i e s Yue Pang (Peking University), Lei Zou (Peking University), Jeffrey Xu Yu(Chinese University of Hong Kong),LinglinYang (Peking University)SIGMOD 2024 •一个正则路径查询（Regular path query,RPQ）𝐀是以边标签为字母表的正则表达式，形式如下： 在边上带标签的有向图𝐀=𝐀,𝐀,Σ,l上，𝐀的结果是节点对的集合，其中每对节点至少有一条路径的边标签序列满足𝐀[𝐀]= {⟨𝐀,𝐀⟩|∃𝐀∈𝐀,𝐀.𝐀=𝐀∧𝐀.𝐀=𝐀∧𝐀𝐀∈𝐀𝐀𝐀 RPQ的物化视图选择（Materialized view selection, MVS）：背景和动机 •已有的工作主要研究如何加速单个随机RPQ的执行[8] •但是，许多应用场景需要高效地处理一个RPQ构成的负载（即RPQ集合）： •高度专业化的应用对RPQ的需求可能限定于一组在专业语境下有意义的RPQ，例如在蛋白质相互作用网络中进行信号通路检测[9] •具有查询日志、且日志中含有RPQ的应用，如SPARQL查询端点[10]•同时发起多个RPQ的应用，如将图形化的查询表达模糊转译为多个RPQ的可视化查询系统[11] •基本思路：通过将某些子查询选为物化视图、离线计算其结果供在线使用来实现负载中相似RPQ之间的共享计算 ü去除冗余（无用或重复）计算 [8] N.Yakovets, P. Godfrey, and J.Gryz, “Query Planning