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

Design and Implementation of Solution Algorithm for Foreign Key Conflict Based on Directed Graph

作　　者：王智铎 江波 苗瑞 赵慧 WANG Zhiduo;JIANG Bo;MIAO Rui;ZHAO Hui(The 32nd Research Institute of China Electronics Technology Group Corporation,Shanghai 201808,China;School of Naval Architecture,Ocean&Civil Engineering,Shanghai Jiao Tong University,Shanghai 200240,China)

机构地区：[1]中国电子科技集团公司第三十二研究所,上海201808 [2]上海交通大学船舶海洋与建筑工程学院,上海200240

出　　处：《计算机工程》2021年第2期254-260,共7页Computer Engineering

基　　金：国家自然科学基金(71971139);上海市2019年度科技创新行动计划“一带一路”国际合作项目(19510750200)。

摘　　要：外键作为关系型数据库中的重要约束之一,对约束数据库的操作顺序有着重要意义,但在数据库集群同步情况下用户无法得知操作顺序,会造成外键冲突,为解决该问题,提出一种基于有向图的外键冲突解决算法。将外键关联转化为有向无环图模型,基于SQL语句实现生成有向图的邻接矩阵数据,通过拓扑排序遍历有向无环图,得到满足数据表写入操作的原子性序列。实验结果表明,与传统暴力枚举算法相比,该算法解决外键冲突的执行时间更短,数据库访问频率更低,且CPU占用率和内存消耗性能指标均体现出明显优势。As one of the important constraints in relational databases,foreign keys play an important role in constraining the order of operations of the database.However,in some cases,users cannot know the order of operations,causing foreign key conflicts. To solve the problem,this paper proposes a solution algorithm for foreign key conflicts based on directed graphs.The foreign key association is converted into a directed acyclic graph model,and the adjacency matrix data of the directed graph is generated based on SQL statements. Then the directed acyclic graph is traversed through topological sorting to generate an atomic sequence that satisfies the data table write operation. Experimental results show that compared with the traditional violence enumeration algorithm,the proposed algorithm reduces the execution time for solving foreign key conflicts,decreases the database access frequency,and significantly improves the performance indicators of CPU usage and memory consumption.

关 键 词：外键 邻接矩阵 有向图 数据库 拓扑排序 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]