基于函数依赖图的设计关系数据库模式的综合算法

A Synthesis Algorithm of Designing Relational Database Scheme Based on Functional Dependence Graphs

本文详细讨论了函数依赖图的原理及基于函数依赖图求解ＥＫＮＦ（基本关键字范式）的数据库模式的综合算法。它对于给定的一关系数据库的一组函数依赖产生相应的ＦＤ图；基于此ＦＤ图，删除该ＦＤ图中的冗余复合节点、多余复合节点和冗余完全弧；从而得到一个ＬＲ最小ＦＤ图覆盖；并由此得出一个属于ＥＫＮＦ的较好的关系数据库模式。本文所述综合算法的时间复杂度为多项式的，因而在实践中有重要的实用价值。

In this paper we discuss a sythesis algorithm of designing relational database scheme inEKNF(Elementary Key Normal Form)based on the theory of FD-graphs(Functional De-pendence-graphs).From a given set of FD’s(Ftinctional Dependencies)and its FD-graphthe algorithm can find a better relational dotabase scheme in EKNF based on deleting redu-dant compound nodes of the FD-graph. superfluous compourid nodes and redtidant fullarcs. The time complexity of the algorithm is polynomial.In the case,we are certain the al-gorithm is very useful in practice.