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

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

作　　者：汪林林[1] 

机构地区：[1]重庆邮电学院计算机系

出　　处：《重庆邮电学院学报（自然科学版）》1995年第2期1-9,共9页Journal of Chongqing University of Posts and Telecommunications(Natural Sciences Edition)

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

关 键 词：数据库模式 关系数据库 函数依赖图 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]