作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2021, Vol. 47 ›› Issue (2): 254-260. doi: 10.19678/j.issn.1000-3428.0058851

• 体系结构与软件技术 • 上一篇    下一篇

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

王智铎1, 江波1, 苗瑞2, 赵慧1   

  1. 1. 中国电子科技集团公司第三十二研究所, 上海 201808;
    2. 上海交通大学 船舶海洋与建筑工程学院, 上海 200240
  • 收稿日期:2020-07-06 修回日期:2020-10-10 出版日期:2021-02-15 发布日期:2020-11-13
  • 作者简介:王智铎(1994-),男,硕士研究生,主研方向为Java开发、数据库技术;江波,研究员、博士后、博士生导师;苗瑞,副教授、博士、博士生导师;赵慧,硕士研究生。
  • 基金资助:
    国家自然科学基金(71971139);上海市2019年度科技创新行动计划“一带一路”国际合作项目(19510750200)。

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

WANG Zhiduo1, JIANG Bo1, MIAO Rui2, ZHAO Hui1   

  1. 1. The 32 nd Research Institute of China Electronics Technology Group Corporation, Shanghai 201808, China;
    2. School of Naval Architecture, Ocean & Civil Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
  • Received:2020-07-06 Revised:2020-10-10 Online:2021-02-15 Published:2020-11-13

摘要: 外键作为关系型数据库中的重要约束之一,对约束数据库的操作顺序有着重要意义,但在数据库集群同步情况下用户无法得知操作顺序,会造成外键冲突,为解决该问题,提出一种基于有向图的外键冲突解决算法。将外键关联转化为有向无环图模型,基于SQL语句实现生成有向图的邻接矩阵数据,通过拓扑排序遍历有向无环图,得到满足数据表写入操作的原子性序列。实验结果表明,与传统暴力枚举算法相比,该算法解决外键冲突的执行时间更短,数据库访问频率更低,且CPU占用率和内存消耗性能指标均体现出明显优势。

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

Abstract: 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.

Key words: foreign key, adjacency matrix, directed graph, database, topological sorting

中图分类号: