1、图上的高效路径查询图上的高效路径查询庞悦庞悦北京大学王选计算机研究所数据管理实验室2024/03/23大纲大纲背景IFCA：利用动态图上的社区结构加速可达性查询（ICDE23）利用物化视图加速图上的正则路径查询（SIGMOD24）在图数据库系统的查询执行流程中整合高效路径算法的未来机遇PART 01背景背景新型场景：聚焦实体间关系新型场景：聚焦实体间关系数据不仅在规模上不断增长，更关键的是相互关联的程度也不断提升。探索、描述、预测和解释现实世界和数字世界的现象，越来越依赖于能刻画实体间关系的数据模型。-Angela Bonifati,Alexandru Iosup,Sherif Sakr,an

2、d Hannes Voigt.Big Graph Processing Systems(Dagstuhl Seminar 19491).In Dagstuhl Reports,Volume 9,Issue 12,pp.1-27,Schloss Dagstuhl-Leibniz-Zentrum fr Informatik(2020)社交网络聚焦社交关系金融风控聚焦交易关系互联网聚焦超链接生物化学聚焦化学反应知识图谱聚焦概念关联and many more图数据模型图数据模型PersonNameAliceAge45GenderFPersonPersonPostfollowsfollowsfollow

3、screateslikesTimestamp2023-12-07T15:30:00Z=,:节点集合:边集合:,将边与其端点相关联:,给节点和边分配标签:,给节点和边分配属性键值对图上路径的含义图上路径的含义PersonNameAliceAge45GenderFPersonPersonPostfollowsfollowsfollowscreateslikesTimestamp2023-12-07T15:30:00Z图上的一条路径是边的有限序列 1,2,，其中=,，且对于 =1,2,，=+1（首尾相接）。路径刻画实体间的间接关系。例如，应用于社交网络中的推荐场景：“我间接关注的用户”“我可能感兴趣

4、的用户”“我关注的人点赞过的帖子”“我可能感兴趣的帖子”路经查询的分类路经查询的分类约束约束结果形式结果形式起始/目标节点路径长度节点/边的标签节点/边的属性过滤条件判定问题计数问题枚举问题给定起始和目标节点+为判定问题=可达性查询给定起始节点+限定路径长度为最短+枚举问题=单源最短路径查询给定以边标签集合为字母表的正则路径+枚举问题=正则路径查询例例图查询语言中的路经查询图查询语言中的路经查询SPARQLRDF（知识图谱和Linked Data的数据模型）的标准查询语言示例查询目标：示例查询目标：查找在社交网络中 David 直接或间接认识的所有人 CypherNeo4j的查询语言ISO/G

5、QL正在开发中的ISO标准图查询语言SELECT?person WHERE?david .?david “David”.?david+?person.MATCH(:Person name:“David”)-:knows*1.-(person)RETURN personMATCH(:Person WHERE name=David)-:knows*1.-(person)RETURN person路经查询的挑战路经查询的挑战当图规模巨大且动态变化、且查询具有复杂的约束条件时，高效地回答路径查询是具有挑战性的。优化技术：优化技术：利用图的结构特征去除冗余（无用或重复）计算改进图数据访问的局部性并行化P

6、ART 02IFCA：利用动态图上的社区结构加速：利用动态图上的社区结构加速可达性查询可达性查询IFCA:Index-Free Community-Aware Reachability Processing Over Large Dynamic GraphsYue Pang,Lei Zou,Yu LiuYue Pang,Lei Zou,Yu LiuPeking UniversityPeking UniversityICDE 2023ICDE 2023问题定义问题定义 问题定义问题定义:给定有向图 =,和一对节点,可达性查询可达性查询当从 到 存在至少一条有向路径时返回真真，否则返回假假 应用应

7、用：电子商务图：检测欺诈活动 社交网络：实施访问控制 基本思路基本思路：在图上的社区结构中搜索时，减少无用的计算利用图的结构特征去除冗余（无用或重复）计算过往工作：静态图上基于索引的可达性算法过往工作：静态图上基于索引的可达性算法静态数据图静态数据图可达性索引可达性索引Label+G部分或全部可达性信息的摘要Label-Onlystst在拥有高达十亿边十亿边的真实静态图上，基于索引的可达性算法的平均查询时间 1 ms动态图给基于索引的可达性算法带来挑战动态图给基于索引的可达性算法带来挑战动态数据图动态数据图可达性索引可达性索引重建索引增量更新索引 索引重建或增量更新可能比查询慢高达比查询慢高达

8、5个数量级个数量级 因此，不基于索引的可达性算法在动态图上更具优势 本文发表前最新的不基于索引的算法2是近似算法，无法保证结果准确性每秒边更新数目高达 20,000 次 1！1 X.Qiu et al.,“Real-time constrained cycle detection in large dynamic graphs,”Proc.VLDB Endow.,vol.11,no.12,pp.18761888,Aug.2018.2 N.Sengupta,A.Bagchi,M.Ramanath,and S.Bedathur,“ARROW:Approximating Reachability U

9、sing Random Walks Over Web-Scale Graphs,”in 2019 IEEE 35th International Conference on Data Engineering(ICDE),Macao,Macao,Apr.2019,pp.470481.例：电子商务图、社交网络背景：个性化页面排名（背景：个性化页面排名（Personalized PageRank,PPR）定义定义：假设给定有向图 =,，节点数为 、边数为 给定一个起始节点 、一个目标节点 、停止概率 从 s 发起随机游走，每步 以 概率停在当前节点上，以 1 概率随机跳转到任一出邻居 从 到 的 P

10、PR 值：,=从发起的随机游走停止于 表示从 的视角看，节点 的重要程度背景：个性化页面排名（背景：个性化页面排名（Personalized PageRank,PPR）,=13123 1 /3 1 /3 1 /3蒙特卡洛模拟蒙特卡洛模拟 SIAM J.Numer.Anal.07,etc.从 s 出发采样若干随机游走,=采样的随机游走停止于 的比例基于推送（基于推送（PushPush）的技术）的技术 KDD17,etc.每个节点 维护一个残差值（residue）,和保留值（reserve）,;每轮迭代向邻居推送部分残差值，剩余部分转化为本节点的保留值，最终保留值为PPR估计幂迭代幂迭代 SIGM

11、OD21,etc.=1 +:PPR向量:初始化向量:转换矩阵:停止概率背景：图上的社区结构背景：图上的社区结构社区社区是内部密集连接、与外部稀疏连接内部密集连接、与外部稀疏连接的子图 传导度（Conductance）是社区质量的一种衡量指标。=|min?,2?传导度越低，社区内部相对于外部连接越密集 给定一个起始节点 s，它周围的社区由相对 s 具有高 PPR 值的节点构成（可证明由这些节点诱导的子图具有足够低的传导度4）4 R.Andersen,F.Chung,and K.Lang,“Local Graph Partitioning using PageRank Vectors,”in 20

12、06 47th Annual IEEE Symposium on Foundations of Computer Science(FOCS06),Berkeley,CA,USA,2006,pp.475486.背景：图上的社区结构背景：图上的社区结构BiBFS:+,是否有必要访问如此多的边？（只需确认是否存在一条一条路径）提升社区内可达性查询的效率将提升推广到跨社区可达性查询主要工具：主要工具：个性化页面排名（个性化页面排名（PPR）社区社区是内部密集连接、与外部稀疏连接内部密集连接、与外部稀疏连接的子图 基于基于PPR的基准算法的基准算法给定有向图 =,、一对节点,以下性质成立：0,(=,)：

13、节点 相对 的PPR值因此，可以通过判断一对节点的 PPR 值是否大于 0 来回答可达性查询采用基于推送的技术，因其框架与图遍历相近基准算法的优势基准算法的优势、不足与改进方针、不足与改进方针社区内查询（社区内查询（s s、t t在同一社区中）在同一社区中）基准算法（基于推送的基准算法（基于推送的PPR算法）算法）更倾向于首先访问相对起始节点PPR值高的节点，这些节点往往围绕起始节点形成一个社区。BFS对社区结构无感知，需要覆盖到社区中节点时，会浪费更多边访问。基准算法的基准算法的优势、优势、不足不足与改进方针与改进方针跨社区查询（跨社区查询（s s、t t在不同社区中）在不同社区中）较大的较

14、大的 值（残差阈值，值（残差阈值，越大越早终止）：越大越早终止）：导致提前终止，无法将搜索前沿推进到社区之外，从而产生假阴性较小的较小的 值：值：导致残差值在图上的环路中反复传播，造成冗余计算同样难以处理社区结构不明显的图基准算法面临以下问题：基准算法的基准算法的优势、不足与优势、不足与改进方针改进方针“Let each bird sing its own songLet each bird sing its own song”BFS基于基于PPR的搜索算法的搜索算法社区内查询慢快跨社区查询快慢我们提出一种两阶段两阶段的搜索策略 基于基于PPR的双向搜索算法的双向搜索算法高效回答社区内查询 社

15、区收缩社区收缩高效回答跨社区查询 基于代价估计的搜索策略选择（何时基于代价估计的搜索策略选择（何时切换切换到到BFS）高效回答社区结构不明显的图上的查询 结果准确 性能优越 在结构满足特定特征的图上复杂度低于BFS两阶段搜索策略的挑战两阶段搜索策略的挑战1.如何快速找到起始节点周围的社区？2.如何避免处理跨社区查询时社区内的冗余边访问？3.如何找到合适的切换到BFS的时机？利用子图传导度和利用子图传导度和PPR之间的关系之间的关系使用社区收缩技术使用社区收缩技术 设计代价模型，估计两种搜索策略未来的开销设计代价模型，估计两种搜索策略未来的开销 我们的方法：我们的方法：IFCA第一步：第一步：给

16、定残差阈值,进行基于基于PPR的搜索的搜索（以从起始节点s的前向搜索为例，实际为双向）使用基于PPR的搜索，可快速判定目标节点快速判定目标节点 t 是否在包含是否在包含 s 的的社区中社区中，进而判定可达性每轮迭代中，通过逐步降低当前的残差阈值逐步降低当前的残差阈值 cur来“松弛松弛”社区社区，直至 cur pre我们的方法：我们的方法：IFCA第二步：第二步：当 时，执行社区收缩社区收缩（将已访问的节点收缩为一个超节点），并以超节点为新的起点继续基于PPR的搜索s突破社区界限，避免冗余边访问可高效搜索到目标节点t我们的方法：我们的方法：IFCA第三步：第三步：随着社区收缩多次执行，图变得更

17、加稀疏、社区结构越发不显著，基于PPR的搜索策略逐渐失去优势基于我们设计的代价模型代价模型，估计两种搜索策略的未来开销，当BFS开销更低时，切换到切换到BFSsBasic operation基于PPR的搜索策略BiBFS#opstime/op()2 11+11?|+?+|+?代价模型：代价模型：两种搜索策略基于相同的基本操作可高效搜索到目标节点t实验：数据集实验：数据集实验：验证选取切换点的策略具有近似最优性实验：验证选取切换点的策略具有近似最优性“预言预言”最优切换点的搜索算法（最优切换点的搜索算法（Oracle）：）：总是选择导致最短查询时间的切换点，通过枚举所有可能切换点、统计最短查询时

18、间得到与始终执行基于 PPR 的搜索+社区收缩的算法（Contract）、BiBFS 相比，IFCA 与与 Oracle 最接近最接近，且差距总在约，且差距总在约 2 倍以内倍以内实验：与当前最先进的可达性算法对比实验：与当前最先进的可达性算法对比综合考虑查询与更新时间时综合考虑查询与更新时间时，IFCA的效率高于其他算法的效率高于其他算法5 A.D.Zhu,W.Lin,S.Wang,and X.Xiao,“Reachability queries on large dynamic graphs:a total order approach,”in Proceedings of the 201

19、4 ACM SIGMOD International Conference on Management of Data,Snowbird Utah USA:ACM,Jun.2014,pp.13231334.6 H.Wei,J.X.Yu,C.Lu,and R.Jin,“Reachability querying:an independent permutation labeling approach,”The VLDB Journal,vol.27,no.1,pp.126,Feb.2018,doi:10.1007/s00778-017-0468-3.N.Yakovets,P.Godfrey,an

20、d J.Gryz,“Query Planning for Evaluating SPARQL Property Paths,”in Proceedings of the 2016 International Conference on Management of Data,San Francisco California USA:ACM,Jun.2016,pp.18751889.7 H.Yildirim,V.Chaoji,and M.J.Zaki,“DAGGER:A Scalable Index for Reachability Queries in Large Dynamic Graphs,

21、”arXiv:1301.0977 cs,Jan.2013,Accessed:Mar.20,2021.Online.PART 03利用物化视图加速图上的正则路径查询利用物化视图加速图上的正则路径查询Materialized View Selection&View-Based Query Planning for Regular Path QueriesYue Pang(Peking University),Lei Zou(Peking University),Jeffrey Yue Pang(Peking University),Lei Zou(Peking University),Jeffre

22、y Xu Yu(Chinese University of Hong Kong),Xu Yu(Chinese University of Hong Kong),LinglinLinglin Yang(Peking Yang(Peking University)University)SIGMOD 2024SIGMOD 2024问题定义问题定义 一个正则路径查询一个正则路径查询（Regular path query,RPQ）是以边标签为字母表的正则表达式，形式如下：|1/2|1|2|?|+在边上带标签的有向图 =,l 上，的结果是节点对的集合，其中每对节点至少有一条路径的边标签序列满足=,|,.=

23、.=?PersonPersonPersonPostfollowsfollowsfollowscreateslikes“我间接关注的人”?+=1,3,1,2,1,1,3,2,3,1,3,3,2,1,2,3,2,2“我关注的人点赞过的帖子”?/?=1,44231RPQ的物化视图选择（的物化视图选择（Materialized view selection,MVS）：背景和动机）：背景和动机 已有的工作主要研究如何加速单个随机RPQ的执行 8 但是，许多应用场景需要高效地处理一个RPQ构成的负载（即RPQ集合）：高度专业化的应用对RPQ的需求可能限定于一组在专业语境下有意义的RPQ，例如在蛋白质相互作

24、用网络中进行信号通路检测 9 具有查询日志、且日志中含有RPQ的应用，如SPARQL查询端点 10 同时发起多个RPQ的应用，如将图形化的查询表达模糊转译为多个RPQ的可视化查询系统 11 基本思路基本思路：通过将某些子查询选为物化视图、离线计算其结果供在线使用来实现负载中相似RPQ之间的共享计算去除冗余（无用或重复）计算8 N.Yakovets,P.Godfrey,and J.Gryz,“Query Planning for Evaluating SPARQL Property Paths,”in Proceedings of the 2016 International Conferenc

25、e on Management of Data,San Francisco California USA:ACM,Jun.2016,pp.18751889.9 Jacob Scott,Trey Ideker,Richard M Karp,and Roded Sharan.2006.Efficient algorithms for detecting signaling pathways in protein interaction networks.Journal of Computational Biology 13,2(2006),133144.10 Angela Bonifati,Wim

26、 Martens,and Thomas Timm.2020.An Analytical Study of Large SPARQL Query Logs.The VLDB Journal 29,2-3(May 2020),655679.11 Zahid Abul-Basher.2017.Multiple-Query Optimization of Regular Path Queries.In 2017 IEEE 33rd International Conference on Data Engineering(ICDE).IEEE,San Diego,CA,USA,14261430.MVS

27、for RPQ:问题定义问题定义 把负载中的每个RPQ都选成物化视图会引致最高的在线处理效率，但可用的内存总量可能不足 因此，引入内存约束，在其基础上最大化在线处理效率（最小化查询时间代价）MVS for RPQ:给定一个边上带标签的有向图 、一个 RPQ 负载 、内存上限，返回满足以下条件的物化视图集合 V：最小化 ,V/*负载的总查询代价*/使得 ,V|其中 ,V 是在 V 中的物化视图基础上执行 的时间代价 MVS for RPQ 是是 NP 难的难的，因为物化视图集合的效用函数（即引起总查询代价减少量的函数）是sub-modular简单启发式简单启发式 MVS 算法的缺陷：冗余视图算法

28、的缺陷：冗余视图 简单启发式简单启发式 MVS 算法：算法：按某种启发式排序，贪心地选择排序最高的候选视图，直到超出内存上限 缺陷缺陷：若不考虑候选视图之间的部分重合关系，可能引致冗余视图 例：对于负载中的RPQ /+/|?，如果/已被物化，视图/将会是冗余的，但/非冗余，不能通过简单的字符串包含关系判定 解决方案：设计多查询计划表示形式 AND-OR DAG with Closure(AODC)，用于表达整个RPQ负载的联合查询计划，包括候选视图之间的关系新型新型 RPQ 查询计划表达形式：查询计划表达形式：AODC(AND-OR DAG with Closure)扩展自多关系查询的查询计划

29、表达形式 AND-OR DAG，在其基础上添加了正则表达式独有的 Kleene 操作符*和+涵盖了一个 RPQ 负载的所有查询计划（搜索顺序）结构：叶子节点叶子节点：单个边标签 内部节点内部节点：AND 节点节点：RPQ 操作符（连接/,合并|,零或一?,Kleene+,Kleene*）OR 节点节点：子查询 AND 节点和 OR 节点是以层为单位交错分布的The AODC of the RPQ workload/+/|/.|*cost=4 card=4cost=2 card=2cost=3 card=3cost=12 card=8cost=9 card=2cost=9 card=2cost=

30、12 card=8cost=21 card=8cost=19 card=8cost=19 card=8stststOR node(RPQs)AND node(operators)OR node as materialized view在在 AODC 上进行计划选择上进行计划选择 目标目标：对于有多个孩子 AND 节点的 OR 节点，选择其“目标孩子”，即为将要执行的计划 算法：算法：自下而上传播代价和基数估计值(BFS)；选择最低代价的孩子节点作为目标孩子 需要一个代价和基数估计模型代价和基数估计模型 基数估计基数估计：估计每个 OR 节点的结果数目 代价估计代价估计：估计每个 AND 节点的

31、执行代价 目前使用的是固定的估计函数，将来考虑扩展到基于机器学习的估计模型The AODC of the RPQ workload/+/|/.|*cost=4 card=4cost=2 card=2cost=3 card=3cost=12 card=8cost=9 card=2cost=9 card=2cost=12 card=8cost=21 card=8cost=19 card=8cost=19 card=8stststOR node(RPQs)AND node(operators)OR node as materialized viewAODC的执行的执行(1/2)算法算法：自下而上传播

32、结果(BFS)操作操作：叶子结点叶子结点：获取带该标签的边 AND 节点节点：连接(/):1/2=11.=2.2 合并(|):1|2|=1 零或一(?):?=,|Kleene 加(+):+=1 Kleene 星(*):=+?OR 节点节点：直接从目标孩子获取结果The AODC of the RPQ workload/+/|/.|*cost=4 card=4cost=2 card=2cost=3 card=3cost=12 card=8cost=9 card=2cost=9 card=2cost=12 card=8cost=21 card=8cost=19 card=8cost=19 card

33、=8stststOR node(RPQs)AND node(operators)OR node as materialized view/+/|/.|*cost=4 card=4cost=2 card=2cost=3 card=3cost=12 card=8cost=9 card=2cost=9 card=2cost=12 card=8cost=21 card=8cost=19 card=8cost=19 card=8stststOR node(RPQs)AND node(operators)OR node as materialized viewAODC的执行的执行(2/2)优化优化：侧向信

34、息传递侧向信息传递(sideways information passing)计划选择过程中，同时选择连接操作节点左右孩子的执行顺序(/)获取了一侧孩子的查询结果后，结果中的起始/目标节点可作为另一侧孩子的目标/起始节点的候选集 选择不同执行顺序能够提升查询效率选择不同执行顺序能够提升查询效率的关键因素的关键因素/?的执行中：?执行结果中的起始节点可作为/的候选目标节点，从而剪枝从 4 出发的冗余搜索The AODC of the RPQ workload/+/|/.|*cost=4 card=4cost=2 card=2cost=3 card=3cost=12 card=8cost=9 ca

35、rd=2cost=9 card=2cost=12 card=8cost=21 card=8cost=19 card=8cost=19 card=8stststOR node(RPQs)AND node(operators)OR node as materialized viewabbcdcdaaad./+/|/.|*cost=4 card=4cost=2 card=2cost=3 card=3cost=12 card=8cost=9 card=2cost=9 card=2cost=12 card=8cost=21 card=8cost=19 card=8cost=19 card=8ststst

36、OR node(RPQs)AND node(operators)OR node as materialized view基于基于 AODC、带有冗余检测的、带有冗余检测的 MVS 算法算法(1/2)冗余检测的基本思路冗余检测的基本思路：一个物化视图是冗余的当且仅当其对应的 AODC 节点不在任何负载 RPQ 的最优执行计划中，即其使用次数使用次数为 0 基于基于 AODC 的的 MVS 算法算法：按在负载中的出现频率（降序）贪心地考虑候选视图 只选择使用次数非使用次数非 0、导致总代价减、导致总代价减少、与当前已选的视图总和不超过内少、与当前已选的视图总和不超过内存上限存上限的视图 每次选定一

37、个视图，需要相应地更新 AODC 中选择的计划，并删除新视图下变得冗余的视图The AODC of the RPQ workload/+/|/.|*cost=4 card=4cost=2 card=2cost=3 card=3cost=12 card=8cost=9 card=2cost=9 card=2cost=12 card=8cost=21 card=8cost=19 card=8cost=19 card=8stststOR node(RPQs)AND node(operators)OR node as materialized view基于基于 AODC、带有冗余检测的、带有冗余检测的

38、 MVS 算法算法(2/2)示例示例 MVS 过程过程：(内存上限 =10)?加入后会超出内存上线，因此不选/在当前已选的物化视图下冗余，因此不选The AODC of the RPQ workload/+/|/.|*cost=4 card=4cost=2 card=2cost=3 card=3cost=12 card=8cost=9 card=2cost=9 card=2cost=12 card=8cost=21 card=8cost=19 card=8cost=19 card=8stststOR node(RPQs)AND node(operators)OR node as materia

39、lized view候选视图候选视图已选的物化已选的物化视图集合视图集合已使用的内已使用的内存存Step 1/2Step 2?/2Step 3/,/10Step 4/,/10基于物化视图的增量计划选择基于物化视图的增量计划选择 新选择的物化视图会造成查询计划新选择的物化视图会造成查询计划变化的原因变化的原因：当选择一个 AODC 节点对应的查询为物化视图时，其代价变更为其结果数目 目标目标：选定该视图前，通过试探性地更新计划来估计其对总代价的减少量 MVS 算法后立即获得对应的最优计划 算法算法：自下而上传播受影响的估计代价The AODC of the RPQ workload/+/|/.|

40、*cost=4 card=4cost=2 card=2cost=3 card=3cost=12 card=8cost=9 card=2cost=9 card=2cost=12 card=8cost=21 card=8cost=19 card=8cost=19 card=8stststOR node(RPQs)AND node(operators)OR node as materialized view实验：数据集实验：数据集&查询负载查询负载数据集数据集：Wikidata(348,945,080 个节点,958,844,164 条边,5,419 种边标签)12查询负载查询负载：从 Wikida

41、ta 查询日志(Wikidata Query Logs)13 的 code-500（超时）段中抽取出的 RPQ，参考 14 中的预处理方式12 Denny Vrandecic and Markus Krotzsch.2014.Wikidata:a free collaborative knowledgebase.Commun.ACM 57,10(2014),7885.13 Stanislav Malyshev,Markus Krotzsch,Larry Gonzalez,Julius Gonsior,and Adrian Bielefeldt.2018.Getting the most out

42、 of Wikidata:semantic technology usage in Wikipedias knowledge graph.In The Semantic WebISWC 2018:17th International Semantic Web Conference,Monterey,CA,USA,October 812,2018,Proceedings,Part II 17.Springer,376394.14 Diego Arroyuelo,AidanHogan,GonzaloNavarro,andJavielRojas-Ledesma.2022.Time-and Space

43、-Efficient Regular Path Queries.In 2022 IEEE 38th International Conference on Data Engineering(ICDE).IEEE,Kuala Lumpur,Malaysia,30913105.实验：验证基于实验：验证基于 AODC 的查询计划的高效性的查询计划的高效性目标目标：不考虑物化视图的前提下，对比基于 AODC 的查询计划和基于极小有穷自动机（DFA）的查询计划的效率结果结果：基于 AODC 的查询计划相对基于 DFA 的查询计划加速比为 2.27实验：基于实验：基于 AODC 的的 MVS for RP

44、Q 必要性必要性目标目标：证明设计考虑子查询间关系以去除冗余的 MVS 算法的必要性（若这样的 MVS 算法与不考虑去除冗余的算法选出的物化视图集合对查询的加速效果相近，则没有考虑必要）结果结果：基于 AODC 的 MVS 算法相对简单的启发式 MVS 算法引致的总查询时间加速比为 2.15实验：基于物化视图的查询效率与不使用物化视图对比实验：基于物化视图的查询效率与不使用物化视图对比结果结果：视图选择和物化总是远快于查询执行 在不同的内存上限下，基于物化视图的查询（即使加上视图选择和物化时间）均显著快于不使用物化视图的查询:不使用物化视图的查询时间:基于物化视图的查询时间:视图选择和物化时间

45、（内存上限以结果数目为单位）实验：与当前最先进的实验：与当前最先进的 RPQ 算法对比算法对比对比算法对比算法：多 RPQ 优化方法：RTC 15,Swarmguide 11 单个随机 RPQ 优化方法：Ring 14,Unit 16结果结果：我们的方法查询时间加速比、加速比与内存实际占用比值均显著高于其他算法15 Inju Na,Yang-Sae Moon,Ilyeop Yi,Kyu-Young Whang,and Soon J.Hyun.2022.Regular Path Query Evaluation Sharing a Reduced Transitive Closure Based

46、 on Graph Reduction.In 2022 IEEE 38th International Conference on Data Engineering(ICDE).IEEE,Kuala Lumpur,Malaysia,16751686.11 Zahid Abul-Basher.2017.Multiple-Query Optimization of Regular Path Queries.In 2017 IEEE 33rd International Conference on Data Engineering(ICDE).IEEE,San Diego,CA,USA,142614

47、30.14 Diego Arroyuelo,Aidan Hogan,Gonzalo Navarro,and Javiel Rojas-Ledesma.2022.Time-and Space-Efficient Regular Path Queries.In 2022 IEEE 38th International Conference on Data Engineering(ICDE).IEEE,Kuala Lumpur,Malaysia,30913105.16 Van-Quyet Nguyen,Quyet-Thang Huynh,and Kyungbaek Kim.2022.Estimati

48、ng Searching Cost of Regular Path Queries on Large Graphs by Exploiting Unit-Subqueries.Journal of Heuristics 28,2(April 2022),149169.PART 04Future Integration Opportunities of Efficient Path Algorithms in Graph Database SystemsTypical workflow of a graph databases optimizer路径算法整合：计划枚举器路径算法整合：计划枚举器计

49、划枚举器计划枚举器枚举查询的等价计划；选择其中估计代价最低的用于执行枚举查询的等价计划；选择其中估计代价最低的用于执行考虑合取 RPQ 的计划选择考虑与其他查询结构（如 UNION 和 OPTIONAL）的联合优化BJWJWJWJ?stu?prof?stu?prof?courseGGP BGP UNION GGP GGP BGP BGP OPTIONAL GGP BGP 17 Yue Pang,Linglin Yang,Lei Zou,and M.Tamer zsu.2023.GFOV:A Full-Stack SPARQL Query Optimizer&Plan Visualizer.In

50、 Proceedings of the 32nd ACM International Conference on Information and Knowledge Management(CIKM 23).Association for Computing Machinery,New York,NY,USA,50815085.含有合取含有合取 RPQ 的的 SPARQL 查询查询关于关于 SPARQL 中中 UNION 和和 OPTIONAL 优化的已有优化的已有工作工作统一的计划表示形式统一的计划表示形式 17局限：局限：尚未考虑含有 RPQ 的三元组模式Combine复杂程度增加与普适图查

51、询语言的整合程度增加路径算法整合：代价与基数估计器路径算法整合：代价与基数估计器代价与基数估计器代价与基数估计器为计划选择提供代价与基数估计值为计划选择提供代价与基数估计值扩展估计器以提供路径查询特需的估计值（如不同边标签间的连接概率）使用基于机器学习的估计技术，以获取更准确的估计值Rule-based estimationPlanCost:Cardinality:经验推导出的估计规则经验推导出的估计规则Learned estimationPlanCost:Cardinality:Machine learning modelTransformPART 05参考文献参考文献References(

52、1/2)1 X.Qiu et al.,“Real-time constrained cycle detection in large dynamic graphs,”Proc.VLDB Endow.,vol.11,no.12,pp.18761888,Aug.2018.2 N.Sengupta,A.Bagchi,M.Ramanath,and S.Bedathur,“ARROW:Approximating Reachability Using Random Walks Over Web-Scale Graphs,”in 2019 IEEE 35th International Conference

53、 on Data Engineering(ICDE),Macao,Macao,Apr.2019,pp.470481.3 M.Mihail,“Conductance and convergence of Markov chains-a combinatorial treatment of expanders,”in 30th Annual Symposium on Foundations of Computer Science,Research Triangle Park,NC,USA,1989,pp.526531.4 R.Andersen,F.Chung,and K.Lang,“Local G

54、raph Partitioning using PageRank Vectors,”in 2006 47th Annual IEEE Symposium on Foundations of Computer Science(FOCS06),Berkeley,CA,USA,2006,pp.475486.5 A.D.Zhu,W.Lin,S.Wang,and X.Xiao,“Reachability queries on large dynamic graphs:a total order approach,”in Proceedings of the 2014 ACM SIGMOD Interna

55、tional Conference on Management of Data,Snowbird Utah USA:ACM,Jun.2014,pp.13231334.6 H.Wei,J.X.Yu,C.Lu,and R.Jin,“Reachability querying:an independent permutation labeling approach,”The VLDB Journal,vol.27,no.1,pp.126,Feb.2018,doi:10.1007/s00778-017-0468-3.7 H.Yildirim,V.Chaoji,and M.J.Zaki,“DAGGER:

56、A Scalable Index for Reachability Queries in Large Dynamic Graphs,”arXiv:1301.0977 cs,Jan.2013,Accessed:Mar.20,2021.Online.8 N.Yakovets,P.Godfrey,and J.Gryz,“Query Planning for Evaluating SPARQL Property Paths,”in Proceedings of the 2016 International Conference on Management of Data,San Francisco C

57、alifornia USA:ACM,Jun.2016,pp.18751889.References(2/2)9 Jacob Scott,Trey Ideker,Richard M Karp,and Roded Sharan.2006.Efficient algorithms for detecting signaling pathways in protein interaction networks.Journal of Computational Biology 13,2(2006),133144.10 Angela Bonifati,Wim Martens,and Thomas Timm

58、.2020.An Analytical Study of Large SPARQL Query Logs.The VLDB Journal 29,2-3(May 2020),655679.11 Zahid Abul-Basher.2017.Multiple-Query Optimization of Regular Path Queries.In 2017 IEEE 33rd International Conference on Data Engineering(ICDE).IEEE,San Diego,CA,USA,14261430.12 Denny Vrandecic and Marku

59、s Krtzsch.2014.Wikidata:a free collaborative knowledgebase.Commun.ACM 57,10(2014),7885.13 Stanislav Malyshev,Markus Krtzsch,Larry Gonzlez,Julius Gonsior,and Adrian Bielefeldt.2018.Getting the most out of Wikidata:semantic technology usage in Wikipedias knowledge graph.In The Semantic WebISWC 2018:17

60、th International Semantic Web Conference,Monterey,CA,USA,October 812,2018,Proceedings,Part II 17.Springer,376394.14 Diego Arroyuelo,Aidan Hogan,Gonzalo Navarro,and Javiel Rojas-Ledesma.2022.Time-and Space-Efficient Regular Path Queries.In 2022 IEEE 38th International Conference on Data Engineering(I

61、CDE).IEEE,Kuala Lumpur,Malaysia,30913105.15 Inju Na,Yang-Sae Moon,Ilyeop Yi,Kyu-Young Whang,and Soon J.Hyun.2022.Regular Path Query Evaluation Sharing a Reduced Transitive Closure Based on Graph Reduction.In 2022 IEEE 38th International Conference on Data Engineering(ICDE).IEEE,Kuala Lumpur,Malaysia

62、,16751686.16 Van-Quyet Nguyen,Quyet-Thang Huynh,and Kyungbaek Kim.2022.Estimating Searching Cost of Regular Path Queries on Large Graphs by Exploiting Unit-Subqueries.Journal of Heuristics 28,2(April 2022),149169.17 Yue Pang,Linglin Yang,Lei Zou,and M.Tamer zsu.2023.GFOV:A Full-Stack SPARQL Query Optimizer&Plan Visualizer.In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management(CIKM 23).Association for Computing Machinery,New York,NY,USA,50815085.谢谢！谢谢！