信息学院博士生2篇论文被国际顶级会议VLDB、CIDR接收

近日，信息学院博士生金国栋为第一作者的论文《Making RDBMSs Efficient on Graph Workloads Through Predefined Joins》被VLDB 2022会议接收；《GRainDB: A Relational-core Graph-Relational DBMS》被CIDR 2022会议接收。VLDB（International Conference on Very Large Data Bases）会议是数据管理与数据库领域的三大国际顶尖学术会议之一，被中国计算机学会（CCF）推荐为A类国际会议，被我校推荐为A+类国际会议。VLDB 2022会议将于9月5日在澳大利亚悉尼召开。

研究背景

在企业数据库应用中，关系表和图是两种很常见的数据结构，这两种数据结构分别对应了关系数据库和图数据库的核心数据模型。图数据库（如Neo4j、TigerGraph、DGraph和GraphflowDB等）主要采用属性图模型，在很多包含复杂多对多连接的查询上性能比关系数据库更好，这类查询负载被称之为“图查询”。例如，在社交网络应用中，查找两个用户之间基于多对多的Follows关系的多跳长路径；在金融欺诈检测应用中，寻找账户之间环状的多对多转账模式。尽管已有专门的图数据库系统，但关系数据库在图数据的查询和管理中仍然发挥着重要角色——在企业应用中，数据普遍先存储在关系数据库中，再提取、复制和同步到专门的图数据库中进行分析。这种关系数据库和图数据库混合的架构增加了数据迁移和同步的代价，并且在传统OLAP分析上，关系数据库已有很多成熟的技术和架构，例如列存储、并发执行、查询优化器等，都可以应用到图查询上。因此，我们在这个研究项目中探索如何扩展关系数据库以更好地支持图查询，并将扩展后的新的数据库称之为“图-关系数据库”。

研究内容概述

在基于列存储的关系数据库中，我们利用元组的RID作为其逻辑指针，并将基于值的等值连接转换为基于ID的等值连接。在此基础上，我们提出了关系表中外键列F到主键列P的物化RID列，以及基于RID列的类邻接链表索引结构。在查询执行时，我们结合旁路信息传递技术（Sideways Information Passing, SIP），扩展关系数据库中的哈希连接算子为SIPJoin。SIPJoin在构建哈希表后，基于构建侧的连接键值，访问物化RID列和RID索引，生成bitmask用于过滤探测侧不匹配的元组，减少探测侧的扫描和连接等操作的开销，提高查询性能。基于开源列存数据库系统DuckDB，我们实现了图-关系数据库原型系统GRainDB。在LDBC SNB基准上，GRainDB大幅提高了DuckDB的查询性能，同时，GRainDB的性能同当前state-of-art的图数据库GraphflowDB的性能接近。

图 1  GRainDB在LDBC SNB上同DuckDB和GraphflowDB的对比

系统实现

1.数据建模。图2展示了一个将数据库中的部分关系表建模为图的示例。图中下半部分的矩形框为数据库中的五张关系表，包括Contact、Person、Visit、Place和Zipcode等，框之间的箭头表示表之间的主外键关联。图中上半部分的圆形框表示图模型中的顶点，三角形框表示图中的边。Person表和Place表中的元组被建模为图中的顶点vPerson和vPlace，而Visit和Contact则分别被建模为图中vPerson和vPlace之间的边eVisit，以及vPerson之间的边eContact。

图 2 混合关系和图建模示例

2.查询语言GRQL。我们在GRainDB中设计和实现了GRQL，在标准的SQL语法中集成了图查询语言的路径模式，路径模式可以出现在FROM子句中，同关系表的语义级别相同。例如，查找Mahinda通过1到4的变长路径接触过的在海淀地区的人的姓名。

3.查询可视化。用户可以通过Web界面向GRainDB提出查询，并将结果可视化为表格或者图。具体地，当SELECT子句中的投影中包含用来描述路径模式的节点和边的变量，可视化前端就可以将这些变量的值以交互式的顶点链接图的形式输出。用户可以点击图中的节点，以扩展到图中的邻居节点。

作者简介：金国栋，中国人民大学信息学院2017级博士，计算机应用技术专业，主要研究方向是数据库系统。

指导老师简介：陈跃国，教授，博士生导师，数据工程与知识工程教育部重点实验室副主任，中国人民大学大型科学仪器共享平台副主任，中国计算机学会数据库专家委员会秘书长。拥有清华大学学士学位和硕士学位新加坡国立大学博士学位，微软亚洲研究院铸星计划访问学者，UIUC高级研究学者。从事大数据可视化分析、制造大数据评分析、金融量化分析等方面研究工作。在高水平学术期刊和会议上发表论文40余篇。承担国家级重点研发计划课题和自然科学基金重点项目。曾获教育部科技进步一等奖。