关系数据库数据组织中无α环的分解问题的研究

摘要

计算机技术的快速发展使数据存储的问题得到一定程度的解决，数据库出现了海量数据的大型和超大型数据库，它们广泛的应用于CIMS、GIS等领域；数据库的数据类型也出现如流媒体、空间、时态等多种复杂的数据形式，产生了网络、并行、移动、分布式等数据库的多种组织形式。因此近些年来在数据库的设计与应用中的查询异常问题逐渐成为数据库研究的热，点。无环数据库模式的设计理论研究，已成为了当前数据库研究的一个新的重要分支。 数据库理论与图论的结合产生了无环数据库模式设计理论。数据库模式分解是使数据库模式设计更加规范化，可以减少冗余，减少存储异常和查询异常。通过图论中图的方式比较直观的表达数据库的数据模式，这种方法与数据规范化理论和函数依赖对数据库的数据多样性语义描述相结合，产生了一个针对复杂数据库的设计研究的新方法。由于无环数据库模式本身具有很多优良的特性，这些特性解决了数据库研究中以往一些难以解决的问题，因此数据库的无环性已经成为判断数据库模式优劣的一个重要特性。 本文是基于无环数据库模式，对数据库数据组织中数据模式无α环分解问题展开研究。通过关系数据库的函数依赖集的归并依赖集对数据库模式是否存在函数依赖冲突进行讨论，研究数据库的数据模式中是否存在环，数据库模式是否满足无α环分解，以及如何在各种数据库模式的规范化的范式级别上判断环的存在和进行无α环分解的问题。 1、基于数据库超图的无α环的特性。分析了求解归并依赖集和最小归并依赖集的算法，提出了归并依赖集的二元组集合闭包的求解算法。并对归并依赖集的左部集及子集的求解算法进行了系统的整理。 2、结合数据库超图、FD 超图从微观讨论函数依赖蕴涵关系的特点，分析了归并 FD 超图对应的关系模式中存在的各种内部冲突。在此基础上，对FD集 F 存在内部冲突的特征和条件进行讨论，提出了判定定理和判定算法；同时在广义左部冲突和右部冲突概念的基础上，提出了数据库模式 R〈W，F〉分解为满足 P<,3>(保持函数依赖、无损连接、第三范式)分解时 F是否存在的广义左部冲突和右部冲突的判定定理和算法。 3、在对有内部冲突的归并依赖集中的函数依赖关系进行分析的基础上，提出满足BCNF的分解条件和满足P<,2>且无α环分解的充要条件并进行了证明。给出了条件的判定算法和数据库模式的分解算法。 4、提出初等归并依赖集和初等最小归并依赖集的概念，定义初等最小规并依赖集的弱左部冲突和弱右部冲突，讨论了初等最小归并依赖集下的冲突问题，给出了在FD集F其初等最小归并依赖集D中存在弱左，右部冲突时模式分解为满足 P<,EK> 为有α环的结论，并给出了初等最小归并依赖集的求解方法，冲突的判定算法。最后给出了数据库模式分解满足P<,EK>和无α环分解算法。 5、在研究简单范式 (SNF) 的数据库模式无α环分解时，基于最小归并依赖集关联度的基础上，提出了简单范式的数据库模式无α环的分解条件。证明了在FD集 F 的最小归并依赖集D中存在弱左、右部冲突以及D不满足条件时模式分解为满足P<,S>为有α环的这一充分必要的结论。给出了数据库模式满足无环的条件判定定理及算法和数据库模式满足P<,S>和无α环分解的算法。

目录

文摘

英文文摘

声明

第1章绪论

1.1本文研究的背景及目的和意义

1.2国内外无环数据库模式研究的现状

1.2.1数据库数据规范化设计理论的研究现状

1.2.2连接超图的有关理论

1.2.3无环数据库

1.2.4关系数据库数据组织的无环性问题的研究现状

1.3学位论文的主要研究内容与结构

第2章函数依赖集的归并依赖集的研究

2.1引言

2.2 FD集F的归并依赖集的相关概念

2.2.1 FD集F的归并依赖集

2.2.2 FD集F的归并依赖集嵌入

2.3归并FD超图的研究

2.3.1超边、准路和准环

2.3.2归并FD超图构造算法

2.4最小归并依赖集的求解算法

2.4.1 FD集F的一个归并依赖集D的求解

2.4.2归并依赖集D的最小归并依赖集求解

2.5归并依赖集的二元组集合闭包的求解算法

2.5.1归并依赖集D的完全函数决定属性集的求解

2.5.2归并依赖集D二元组集合B求解

2.6归并依赖集的各种左部集

2.6.1归并依赖的扩展左部集的求解算法

2.6.2归并依赖的蕴涵左部集D的求解算法

2.6.3归并依赖集D的所有对称左部集的求解算法

2.7本章小结

第3章数据库函数依赖集内部冲突的研究

3.1引言

3.1.1存在冲突的函数归并超图

3.1.2函数依赖集中存在的各种冲突的的定义

3.2满足P3分解的R〈W，F〉的F内部冲突的判定

3.2.1 F存在内部冲突的特征和条件

3.2.2内部冲突的判定算法分析

3.3满足P3分解的R〈W，F〉的F广义左、右部冲突

3.3.1F存在广义左、右部冲突的特征和条件

3.3.2广义左、右部冲突判定算法

3.4各种冲突检测算法

3.5 F有内部冲突保持FD、BCNF无α环模式分解

3.5.1P2且无α环的模式分解的相关概念

3.5.2满足P2且无α环模式分解理论

3.5.3 F有内部冲突满足P2且无α环的分解算法

3.6本章小结

第4章FD无内部冲突时满足PEK且无α环模式分解问题研究

4.1引言

4.2初等关键字范式(EKNF)相关理论

4.3满足PEK且无α环分解的理论

4.4满足EKNF的无环分解算法

4.5本章小结

第5章FD环境下满足PS及无α环模式分解问题研究

5.1引言

5.2简单范式(SNF)相关理论

5.2.1简单范式SNF的基本概念

5.2.2满足SNF且保持FD的分解算法

5.3满足Ps和无α环的分解的相关理论

5.3.1简单范式(SNF)满足Ps和无α环的分解相关概念

5.3.2满足Ps和无α环的分解条件

5.4满足Ps和无α环的判定与分解算法

5.5本章小结

结论

参考文献

攻读学位期间发表的学术论文

致谢