(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210515138.X (22)申请日 2022.05.11 (71)申请人 上海交通大 学 地址 200240 上海市闵行区东川路80 0号 (72)发明人 陈榕　沈斯杰　夏虞斌　陈海波　 臧斌宇　 (74)专利代理 机构 上海汉声知识产权代理有限 公司 3123 6 专利代理师 胡晶 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/2455(2019.01) G06F 16/28(2019.01) G06F 16/2457(2019.01) (54)发明名称 基于图结构索引的关系型数据连接方法及 系统 (57)摘要 本发明提供了一种基于图结构索引的关系 型数据连接方法及系统， 该方法采用一种能够保 存关系型数据之间关系的图结构索引， 通过这种 图结构索引进行匹配数据的筛选以及数据的定 位， 完成连接操作。 与现有 技术相比， 本发明可以 减少连接操作筛选过程中的复杂操作和数据读 取， 提升连接操作性能， 同时图结构索引的使用 开销和构建开销相比现有连接方法中的索引有 所减少。 本发明基于图结构索引的连接方法， 相 比原来的索引结构， 更能表达数据之间的关系， 提高连接过程中筛选效率， 减少无用数据的读 取， 达到服务高效的目的； 在图结构索引使用过 程中， 相比树状索引和哈希索引避免复杂的计算 操作， 只需要对图结构索引进行读取， 额外的时 间成本小。 权利要求书2页 说明书7页 附图2页 CN 114860729 A 2022.08.05 CN 114860729 A 1.一种基于图结构索引的关系型 数据连接方法， 其特 征在于， 所述方法包括如下步骤： 步骤S1： 根据用户定义构建图结构索引； 步骤S2： 客户端发送请求至服务端， 服务端判断请求类型； 若能够使用图结构索引进行 连接操作， 执 行步骤S3； 否则使用其 他连接方式， 流 程结束； 步骤S3： 服务端解析连接操作请求， 根据图结构索引确定该连接操作的外层表和内层 表； 步骤S4： 外层表是否迭代完成， 若是， 则执 行步骤S9； 若否， 则执 行步骤S5； 步骤S5： 对外层表中的数据进行遍历， 对每一个外层表的数据， 定位该数据在图结构索 引中对应的节点； 步骤S6： 定位到节点后， 通过图结构中的边遍历该节点的邻居节点， 并通过这些邻居节 点定位它 们所代表的内层表数据； 步骤S7： 将外层表数据与内层表数据进行进一步的条件匹配与筛选， 将符合条件的数 据合并成结果 放入结果 集中； 步骤S8： 判断外层表的数据是否遍历完成， 若未完成， 返回步骤S4； 若已完成， 执行步骤 S9； 步骤S9： 将结果 集返回给客户端， 流 程结束。 2.根据权利要求1所述的基于图结构索引的关系型数据连接方法， 其特征在于， 所述步 骤S1中构建图结构索引需要根据用户指定， 图结构索引中的点表征不同类型的关系型数据 库表， 每个点保存对应数据的位置信息， 边保存的是不同数据库表的连接关系， 两个顶点、 方向和类型确定一条边， 用户需要指定两个数据库表的匹配条件； 其构建过程通过轻量的 连接方式完成。 3.根据权利要求1所述的基于图结构索引的关系型数据连接方法， 其特征在于， 所述步 骤S2中根据请求中涉及到的关系型 数据库表是否具有图结构索引判断。 4.根据权利要求1所述的基于图结构索引的关系型数据连接方法， 其特征在于， 所述步 骤S3中的外层表和内层表根据图结构索引的拓扑结构确定； 若图结构索引中的边存的是单 向边， 以出边为例， 则出边代表出边起点的数据库表为外层表， 代表终点的数据库 表为内层 表； 若图结构索引是双向边， 按照行 数少的为外层表进行确定， 并且初始化结果 集为空。 5.根据权利要求1所述的基于图结构索引的关系型数据连接方法， 其特征在于， 所述步 骤S5中的定位是通过数据的位置信息， 找到图结构索引中对应节点， 节点和数据之间一一 对应。 6.根据权利要求1所述的基于图结构索引的关系型数据连接方法， 其特征在于， 所述步 骤S6中通过节点找对应数据， 是通过邻居节点中保存的数据位置信息找对应数据。 7.根据权利要求1所述的基于图结构索引的关系型数据连接方法， 其特征在于， 所述步 骤S7中需要根据查询中除了图结构索引中匹配条件中的其他条件进 行进一步筛选， 并且根 据输出格式将数据进行投影和合并， 形成结果。 8.根据权利要求1所述的基于图结构索引的关系型数据连接方法， 其特征在于， 所述关 系型数据包括使用关系型模型系统中的数据。 9.一种基于图结构索引的关系型 数据连接系统， 其特 征在于， 所述系统包括如下模块： 模块M1： 根据用户定义构建图结构索引；权　利　要　求　书 1/2 页 2 CN 114860729 A 2模块M2： 客户端发送请求至服务端， 服务端判断请求类型； 若能够使用图结构索引进行 连接操作， 执 行模块M3； 否则使用其 他连接方式， 流 程结束； 模块M3： 服务端解析连接操作请求， 根据图结构索引确定该连接操作的外层表和内层 表； 模块M4： 外层表是否迭代完成， 若是， 则执 行模块M9； 若否， 则执 行模块M5； 模块M5： 对外层表中的数据进行遍历， 对每一个外层表的数据， 定位该数据在图结构索 引中对应的节点； 模块M6： 定位到节点后， 通过图结构中的边遍历该节点的邻居节点， 并通过这些邻居节 点定位它 们所代表的内层表数据； 模块M7： 将外层表数据与内层表数据进行进一步的条件匹配与筛选， 将符合条件的数 据合并成结果 放入结果 集中； 模块M8： 判断外层表的数据是否遍历完成， 若未完成， 返回模块M4； 若已完成， 执行模块 M9； 模块M9： 将结果 集返回给客户端， 流 程结束。 10.根据权利要求9所述的基于图结构索引的关系型数据连接系统， 其特征在于， 所述 模块M1中构建图结构索引需要根据用户指 定， 图结构索引中的点表征不同类型的关系型数 据库表， 每个点保存对应数据 的位置信息， 边保存的是不同数据库表的连接关系， 两个顶 点、 方向和类型确定一条边， 用户需要指定两个数据库表的匹配条件； 其构建过程通过轻量 的连接方式完成； 所述模块M2中根据请求中涉及到的关系型 数据库表是否具有图结构索引判断； 所述模块M3 中的外层表和内层表根据图结构索引的拓扑结构确定； 若图结构索引中的 边存的是单向边， 以出边为例， 则出边代表出边起点的数据库表为外层表， 代表终点的数据 库表为内层表； 若图结构索引是双向边， 按照行数少的为外层表进 行确定， 并且初始化结果 集为空； 所述模块M5中的定位是通过数据的位置信息， 找到图结构索引中对应节点， 节点和数 据之间一 一对应； 所述模块M6 中通过节点找对应数据， 是通过邻居节点中保存的数据位置信息找对应数 据； 所述模块M7中需要根据查询中除了 图结构索引中匹配条件中的其他条件进行进一步 筛选， 并且根据输出格式将数据进行投影和合并， 形成结果； 所述关系型 数据包括使用关系型模型系统中的数据。权　利　要　求　书 2/2 页 3 CN 114860729 A 3