论文部分内容阅读
随着计算机和网络技术的发展,大规模数据库在各种信息系统中的应用日益广泛,数据库的设计与查询成为信息系统设计中的关键技术。无环数据库具有许多优良的特性,不存在许多在有环数据库模式下出现的数据异常,无环数据库理论的研究不仅具有理论价值,而且能指导数据库设计实践,是数据库理论与应用研究中一个重要分支。对于数据库模式中的无环性,存在不同的级别,无α环数据库消除了许多有α环数据库出现的不良现象,而无β环除具有无α环所具有的优良特性外,还具有子图的无环形,因此无β环数据库有效地消除了子模式的数据异常。本文主要研究函数依赖集无内部冲突条件下数据库分解为满足无β环,无损链接,保持函数依赖和3NF的条件和分解算法,并且对算法进行了证明和分析。这些结论能够在不同的条件下指导数据库的设计,避免各种问题的出现导致设计失败。主要内容如下1.关于FD环境下数据库模式分解满足PEK且无α环问题的研究。通过分析在FD集F的最小归并依赖集的性质和特征,提出了初等归并依赖集和初等最小归并依赖集的概念,并定义了初等最小规并依赖集的弱左部冲突和弱右部冲突,PEK(保持FD,无损连接且满足EKNF)等概念。讨论了数据库模式分解为EKNF的无α环判定问题,给出了在初等最小D有弱左部或弱有部冲突时满足PEK的分解是有α环的结论,在此基础上给出了分解算法、正确性证明和分析。2.关于FD环境下数据库模式分解满足PS且无α环问题的研究。通过分析在FD集F的最小归并依赖集D存在弱左部或弱右部冲突时所具有的性质和特征,提出了PS(保持FD,无损连接且满足SNF)、条件T等概念。在此基础上讨论了数据库模式分解为SNF的无α环问题,给出了满足PS(保持FD,无损连接且满足SNF)且无α环分解的充要条件和算法,对算法的正确性、可终止性进行了证明,并对算法的时间复杂度给出了分析。3.归并依赖集全部扩展左部属性的求解。在FD环境下无环数据库模式的研究过程中,各种冲突的讨论需要涉及归并依赖集的扩展左部集。提出一种多项式时间算法求解所有归并依赖的扩展左部集中的属性,给出了算法的正确性、可终止性证明,并对算法的时间复杂度给出了分析。4. FD集无内部冲突条件下满足P3及无β环数据库模式分解问题的研究。通过分析在FD集F的最小归并依赖集D无弱左部冲突、弱右部冲突、时相邻归并依赖所具有的性质和特征,提出了左部集冲突、蕴含集间冲突和主归并依赖冲突等概念,在此基础上证明了在FD集F无内部冲突,且最小归并依赖集D中存在弱左,右部冲突、左部集冲突、蕴含集间冲突和主归并依赖冲突时模式分解为满足P3为有β环的结论,并给出了左部集冲突、蕴含集间冲突和主归并依赖冲突的判定算法及分析。