基于有向图的外键冲突解决算法设计与实现

王智铎，江 波，苗 瑞，赵 慧

（1.中国电子科技集团公司第三十二研究所，上海 201808；2.上海交通大学船舶海洋与建筑工程学院，上海 200240）

0 概述

数据库作为存储数据的介质，其包含数量庞大的数据表和复杂的数据关联。为确保数据库中数据的一致性，需要在数据表间定义一些约束关系，并引入外键（foreign key）概念，用于建立和加强两个表数据之间的链接关系，即通过将表中某一字段或多个字段映射到另一个表中，创建两个表之间的约束关联。目前，采用外键设计的数据库已在传统行业中广泛使用，其优点主要是从数据库底层实现了数据的完整性和一致性，软件底层数据库开发与软件应用层开发相对透明，上层应用开发人员无需完全了解数据库设计规约。随着大数据时代的到来，互联网的数据容量呈现指数级增长，传统行业的应用软件逐渐转向互联网应用模式。由于外键字段执行写入操作时，需实现外键约束逻辑，对涉及外键校验的数据表加同步锁。如果写入操作不按照某种顺序执行，则造成外键校验不通过。因此，互联网行业应用不推荐使用外键。例如，数据表A关联数据表B，在用户执行写入操作时，新增表A数据的操作应在新增表B数据的操作之后，删除表A数据的操作应在删除表B的操作之前。

为满足大数据时代用户新需求，需要将通过客户端访问的模式转向通过浏览器访问的模式。数据表的数据量逐渐扩增且存在极为复杂的多表多字段外键依赖关系。在搭建数据库集群实现数据同步过程中，极易出现因外键冲突导致同步业务困难问题。如果重新设计底层数据库结构，消除已有外键依赖的数据表必然大幅增加开发成本。传统的解决方法是通过递归暴力查找外键冲突，此方法需反复访问数据库来查找外键依赖，造成IO操作频繁，影响了整体业务的性能。

外键识别是解决外键冲突的开始，通过外键字段的数据类型是否为所述外键关系中标识可定义外键关系［1-3］。文献［4］提出一种自动检测外键约束关系的算法，将外键定义为唯一列的组合和包含依赖项集合的子集。然而，此方法只适用于数据表的单列的外键检测，并不适用于存在多列的外键关联的业务场景。文献［5］提出一种识别多列外键的算法，通过评估外键的相关性、列名以及数据的最大值最小值来查找外键关系。

随着人工智能技术的兴起，研究人员使用机器学习算法检测传统数据库的外键关系［6-8］。文献［9］介绍一种采用机器学习检测关系型数据库外键依赖的方法，包括数据表字段名的相似度和字段数据的平均长度等，被数据库厂商广泛应用于数据库外键关系检测。同时，多列外键依赖关系机器学习检测算法受到人们重视。文献［10］提出一种机器学习算法确定关系型数据库的数据表中主键与外键关系的方法，但该方法仅适用于外键与主键的关系检测，并未考虑外键冲突的情况，以及解决外键冲突的方法。文献［11］提出一种基于外键冲突消除的外键检测算法，该方法定义了外键依赖关系的图结构模型，以图的层级顺序消除外键冲突，但该方法只适用于网络表格，其外键关系的定义与传统的关系型数据库相比存在明显区别。然而，现有的外键冲突解决算法仅提出了理论依据，或仅能解决某些应用场景的实现，而未提出一种通用的算法，来满足传统应用软件兼容互联网应用模式且不改变数据库表结构设计等需求。

此外，研究人员对于异构数据库的数据迁移［12］与数据同步［13-14］问题也展开了广泛的研究。由于其数据迁移过程涉及大批量读写操作，外键冲突问题会造成写入数据操作困难，因此解决数据库外键冲突是实现异构数据库同步的重要技术之一。文献［15］介绍了一种异构数据库的同步解决方案，提出存在外键关联表的模式转换同步方案，但该方案仅考虑到外键依赖主键字段。文献［16］提出一种异构数据库多种数据同步技术方案，但该方案中提到的触发器同步、快照同步、时间戳同步均需要变更数据表结构。文献［17］介绍一种利用有向图模型解决分布式控制系统中局部信息一致性问题的方法，该方法将多智能体系统数据建模为有向图模型，从而得出完全分布式的一致性算法。此外，一些关于外键依赖的异常检测方法也可以应用于解决外键冲突问题［18-20］。

本文提出一种外键关联有向图模型算法，将数据表之间的外键关系以有向图的形式展现，方便分析造成外键冲突的原因。根据数据库提供的SQL语句实现有向图生成算法，并将有向图转化为邻接矩阵，为解决外键冲突提供元数据。在此基础上，提出以邻接矩阵作为输入数据、以拓扑排序算法作为数据处理方法的原子性序列生成算法，解决外键冲突问题。

1 数据表与外键的有向无环图表征法

1.1 有向无环图模型生成

外键关系检测是解决外键冲突的必要条件，因此在介绍外键冲突解决算法前，本节首先将数据表之间的外键依赖关系通过有向图直观展现。表1所示为本文中的符号描述。

表1 符号描述Table 1 Symbol description

假定ta为要解决外键冲突的表，ta依赖于tb、tc、td、te。图1给出了该外键依赖关系的有向无环图示例，在后续的论述中，均以此为例。

图1 外键有向图模型Fig.1 Directed graph model of foreign key

数据表外键依赖关系转化为有向无环图方法的步骤如下：

步骤1获取数据库的数据表集合T=｛ta，tb，tc，td，te｝，令T=V。

步骤2获取ti.fk与tj.rfk，得到Referenc（eti.fk，tj.rfk）。

步骤3令ei=Reference（ti.fk，tj.rfk），即一条从ti指向tj的有向边，构建G（V，E）。

步骤4由数据库的外键约定可知，外键不存在循环依赖，即不存在环，G=DAG。

1.2 邻接矩阵生成算法

根据1.1节给出的将数据表之间的外键关联转换为有向图模型方法，DAG可以直观地展现外键依赖关系，但是DAG不能直接作为应用程序的输入数据交给计算机处理。因此，通常会将DAG转化为邻接矩阵，以方便数据存储和外键冲突解决处理。本节的主要研究工作集中在如何通过程序执行SQL语句获取T和Reference数据，以及设计并实现将外键依赖关系转化为邻接矩阵的方法。以oracle数据库为例，将DAG转化为邻接矩阵的SQL代码如下：

本文的研究重点在于如何通过SQL语句生成邻接矩阵，该SQL语句的详细功能如下：

1）从user_constraints查询parent和child数据，user_constraints是主键、外键等约束记录。查询结果如表2所示。

表2 笛卡尔积映射表Table 2 Cartesian product mapping table

2）对user_constraints做笛卡尔积自链接inner join生成以数据库所有表作为节点集合T的无向图，如图2所示，图中任意两节点间均一步可达，tn代表不存在外键的冗余节点。

图2 节点集合T 的无向图Fig.2 Undirected graph of node set T

3）以constraint_name列等于r_constraint_name列作为自连接映射关联的过滤条件，筛选满足该条件的边；使用where关键字作为过滤条件，过滤掉不包含fk、rfk的数据表，即移除图2中无关的节点和边，过滤后的结果如图3所示。

图3 过滤后的结果Fig.3 Filtered result

4）确定存在外键依赖的表，将无向图转为有向图。其中，connect by表示将每一行的数据按链式的层次关系检索，prior关键字表示指针的指向，放置在连接关系两列中的某一列，prior所在的一侧表示入度，另一侧表示出度。

5）用start with关键字来标识查找图型结构的起始节点，需要执行写入操作的起始节点，即程序的输入。

经过上述流程，图2所示的无向图最终转化为图1所示的有向图。完整的SQL语句的执行结果如表3所示，其中parent和child集合为T。以T=｛ta，tb，tc，td，te｝为行和列建立邻接矩阵表。首先将邻接矩阵表的数据均初始化为0，然后在表3查找Reference，如果存在Reference=｛ti，t｝j，则将邻接矩阵的第i行、第j列的元素更新为1。图1的邻接矩阵如表4所示。

表3 约束记录Table 3 Reference record

表4 邻接矩阵Table 4 Adjacency matrix

2 外键冲突解决算法

根据外键有向图模型，分析写入操作的执行顺序可得出以下结论：执行插入操作需满足插入节点的出度为0；执行删除操作需满足删除节点的入度为0；更新操作可视为插入新数据，且删除旧数据。更新前的数据为删除的旧数据，更新后的数据为插入新数据。

数据之间的外键约束关系可模型化为递归遍历的层次关系。在递归遍历的执行过程中，还需要判断当前访问节点的入度和出度。为实现上述功能，本文提出一种基于拓扑排序［21-22］的邻接矩阵遍历算法，具体步骤如下：

步骤1指定用户需要执行写入操作数据表为起始节点。

步骤2从当前节点开始，访问该节点，并标记该节点为已访问过的节点，防止递归回溯出现重复访问。

步骤3判断该节点是否存在未被访问的子节点，若无，则执行步骤4，若有，则判断未被访问的节点入度是否为0。若入度为0，则访问该子节点，跳转到步骤2，否则执行步骤5。

步骤4如果该节点为根节点，则访问完毕，否则执行步骤3。

步骤5标记该节点的入度为1，跳转到步骤3。

综上所述，扫描整个图的过程就是有向无环图（DAG）的拓扑排序过程［23］，其满足每个节点出现且仅出现一次。若存在一条从节点A到节点B的路径，那么在序列中顶点A出现在顶点B之前。如果用户执行插入操作，则需要满足入度为0，插入操作的顺序即为拓扑排序的正序；如果执行删除操作，则需要满足出度为0，删除操作的顺序即为拓扑排序的倒序。

以图1为例，如果对ta执行插入操作，首先判断该有向图中出度为0的点，扫描到td的出度为0，则先将td存入输出结果队列，从图中移除td节点。然后重复该操作，递归移除出度为0的节点，直到遍历完图中的全部节点为止。如果对ta执行删除操作，只需要扫描入度为0的节点，其余步骤一致，或逆序遍历执行插入操作的输出结果均可。执行插入操作的输出结果集合INSERT=｛td，tc，te，tb，ta｝，执行删除操作的输出结果集合DELETE=｛ta，tb，tc，td，te｝。

3 实验结果与分析

3.1 实验环境

实验硬件环境采用Intel®CoreTMi5-9400 CPU @2.9 GHz、16 GB DDR5内存和2 TB机械硬盘；软件环境采用Microsoft Windows 10操作系统oracle数据库、Java Development kit 8开发工具包、NaviCat数据库可视化工具、jprofiler性能测试工具和IntelliJ IDEA开发工具等。

3.2 评估指标

实验将CPU利用率和内存消耗作为性能评估依据。CPU利用率是反映系统忙闲程度的指标。CPU利用率稳步上升，且数值不会过高，表明程序运行状态良好。当CPU利用率在某一时刻开始下降时，表明IO线程开始执行访问数据库，占用了CPU线程的工作；内存消耗是反映系统资源占用情况的指标。内存占用越高，表明程序运行过程中资源占用越多。当内存在某一时刻开始减少，表明jvm的垃圾回收线程开始工作，清理程序运行中不需要使用的资源。垃圾回收线程工作需要暂停CPU线程的正常运行。若CPU利用率和内存消耗出现频繁的抖动现象，则表明CPU线程处于阻塞状态，应用程序会出现明显的卡顿，影响用户体验。

3.3 结果对比与分析

为验证算法的准确性与泛化性，本文实验在不同的数据库应用场景下，对本文算法和传统算法进行性能比较。实验1为某学校的OA系统，实验采集了该管理系统的20张表，表中的数据主要为文本格式，有5张存在外键冲突的数据集；实验2为某公司的业务数据管理系统集群，实验采集了该数据库的20张表，表中的数据主要为文本和图片格式，有100张存在外键冲突的数据集；实验3为某公司的分布式多媒体文件存储系统，实验采集了该数据库的500张表，表中的数据主要为音频和视频格式，有200张存在外键冲突的数据集。

从图4可以看出：本文外键冲突解决算法的运行时间约为1 s，CPU占用率在运行期间内逐渐增长，最高值不超过40%，内存占用不超过50 MB，运行期间无垃圾回收，该结果说明应用程序访问数据库的开销可忽略不计；传统暴力枚举算法的运行时间约为9 s，CPU占用率的峰值接近50%，内存占用约为70 MB，运行期间触发一次轻量级垃圾回收，该结果说明暴力枚举算法访问数据库的I/O操作影响了CPU线程的正常工作，出现平缓的抖动。

图4 OA系统数据集Fig.4 OA system dataset

从图5可以看出：本文外键冲突解决算法的运行时间约为2 s，CPU占用率在运行期间逐渐增长后趋于平稳，最高值不超过40%，内存占用不超过50 MB，程序运行期间无垃圾回收，该结果说明访问数据库的I/O操作略影响CPU工作线程；传统暴力枚举算法的运行时间约为20 s，CPU占用率出现频繁的波动，最高值超过50%，内存占用约为125 MB，运行期间多次触发垃圾回收。该结果说明暴力枚举算法的CPU工作线程被多次阻塞，出现较为频繁的抖动，应用程序出现卡顿。

图5 数据管理系统数据集Fig.5 Database management system dataset

从图6可以看出：本文外键冲突解决算法的运行时间约为8 s，CPU占用率在运行期间出现略微抖动，最高值不超过40%，内存占用不超过100 MB，程序运行期间触发一次垃圾回收，该结果说明外键冲突解决算法访问数据库的I/O操作略微阻塞了CPU工作线程；传统暴力枚举算法的运行时间约40 s，CPU占用率在运行期间出现极为频繁的抖动，最高值超过50%，内存占用超过150 MB，运行期间多次触发垃圾回收，该结果说明暴力枚举算法的CPU线程频繁处于阻塞状态，应用程序出现明显的卡顿，影响用户体验。

图6 分布式多媒体数据库数据集Fig.6 Distribute multimedia database dataset

综上所述，本文提出的基于有向图的外键冲突解决算法在运行时间、CPU占用率和内存消耗上均明显优于暴力枚举算法。

4 结束语

本文提出一种解决外键约束的有向图模型生成算法，其中有向图模型以某一数据表为起点，通过拓扑排序遍历与该表有外键关联的数据表，从而得出用户数据表写入操作执行的顺序，保证存在外键关联数据表的写入操作的原子性。实验结果证明了基于有向图的外键冲突解决算法比暴力枚举算法在性能上有着明显优势。下一步将对数据库集群化分布式数据同步模块的外键冲突解决方案进行研究，以优化时间复杂度，提升算法的鲁棒性。