20240322GraphPathQueries-中文.pdf

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问题定义问题定义 问题定义问题定义:给定有向图 =,和一对节点,可达性查询可达性查询当从 到 存在至少一条有向路径时返回真真，否则返回假假 应用应