摘要： 外键作为关系型数据库中的重要约束之一，对约束数据库的操作顺序有着重要意义，但在数据库集群同步情况下用户无法得知操作顺序，会造成外键冲突，为解决该问题，提出一种基于有向图的外键冲突解决算法。将外键关联转化为有向无环图模型，基于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

中图分类号: 

• TP391