第1章 基本知识 1
1．1关系模型和关系模式 1
1．1．1函数依赖及相关理论概念 1
1．1．2多值依赖及相关理论概念 3
1．2候选关键字 3
1．2．1候选关键字约束 3
1．2．2求关系模式的一个候选关键字 4
1．2．3求全部候选关键字——替换法 5
1．3逻辑蕴涵和覆盖 10
1．3．1逻辑蕴涵 10
1．3．2覆盖与等价 11
1．4范式与规范化 14
1．5联接依赖的性质和判定问题 17
1．5．1联接依赖的概念 17
1．5．2全生成元组器 18
1．5．3联接依赖的种类和联接表 20
1．5．4联接依赖性质的判定 22
1．6符号表和追踪算法 26
1．6．1符号表 27
1．6．2追踪算法 29
1．7小结 33
第2章 数据库模式环的种类与特性 34
2．1无环数据库的良好的特性 34
2．2超图和线图 38
2．2．1超图及与超图相关概念 38
2．2．2无环的超图和线图的概念 40
2．2．3无α环的判定——Graham算法 42
2．2．4化简一致超图的性质 43
2．2．5联接树顺序表达式 44
2．2．6 FD超图 45
2．3超图中各种环的定义及关系 47
2．3．1超图中各种环的定义 47
2．3．2超图中各种环的关系 48
2．4超图有α环的特性 50
2．5超图有β环的特性 65
2．6超图有γ环的特性 67
2．7小结 68
第3章 函数依赖集F有内部冲突的判定 69
3．1 FD集F的归并依赖集的相关概念 69
3．2 FD集F的归并依赖集的求解算法 71
3．3 FD集F的最小归并依赖集的求解算法 72
3．4二元组集合闭包B＋求解算法 75
3．5函数依赖集F有内部冲突的判定 77
3．6归并FD超图表示及构造 79
3．6．1归并准路与准环 79
3．6．2超图构造算法 84
3．7归并FD超图存在内部冲突的条件和算法 85
3．7．1归并FD超图存在内部冲突的条件 85
3．7．2归并FD超图存在内部冲突的检测算法 87
3．8小结 88
第4章 无内部冲突环境下的无α环分解 90
4．1归并依赖集存在弱左、右部冲突判定 90
4．2最小归并依赖集的关联度 94
4．3无内部冲突满足P3的无α环分解条件 97
4．4无内部冲突满足P3的无α环分解算法 100
4．5冗余属性的确定 105
4．6无内部冲突满足PEK的无α环分解 108
4．6．1初等关键字范式的相关概念 108
4．6．2满足初等关键字范式的分解 111
4．6．3满足PEK的无α环分解 113
4．7无内部冲突满足Ps的无α环分解 117
4．7．1简单范式及相关概念 117
4．7．2满足简单范式的分解 119
4．7．3满足Ps的无α环分解 124
4．8小结 131
第5章 有内部冲突的广义左、右部冲突的性质和判定 132
5．1归并依赖集的对称左部属性集 132
5．2有内部冲突的广义左、右部冲突的性质 134
5．2．1有内部冲突的广义左部冲突的性质 134
5．2．2有内部冲突的广义右部冲突的性质 136
5．3有内部冲突的广义左、右部冲突判定算法 138
5．4小结 140
第6章 F有内部冲突满足无α环分解 141
6．1有内部冲突满足P3的无α环分解条件 141
6．2 F有内部冲突满足P3的无α环分解算法 148
6．3小结 155
第7章 多值依赖环境下的无α环分解 156
7．1满足无损联接和4NF的分解 156
7．1．1保证无损联接和4NF分解的有关定理 156
7．1．2产生4NF分解的思想和算法 158
7．2 MVD集M无冲突的判定 162
7．2．1无α环联接依赖与无冲突多值依赖集的等价性 162
7．2．2 MVD集M冲突判定算法 165
7．3混合依赖集环境下的数据库模式无α环分解问题 171
7．3．1混合依赖集D的生成多值依赖集 171
7．3．2混合依赖集环境下的数据库模式无α环分解 175
7．4关系数据库模式环境的判定和泛分解问题的讨论 178
7．4．1数据依赖环境的判定 178
7．4．2关系数据库模式的泛分解算法 179
7．5小结 180
第8章 归并依赖集左部集分析 181
8．1归并依赖集左部属性集分析及求解算法 181
8．1．1一个归并依赖的扩展左部集求法 181
8．1．2归并依赖集的左部联合集的求解算法 182
8．1．3蕴涵左部集的求解 184
8．2 FD集F的归并依赖集集间联系与冲突 186
8．2．1归并依赖集集间冲突 186
8．2．2归并依赖集集内冲突 187
8．2．3归并依赖集强左部冲突和几个冲突的区别 188
8．3小结 190
第9章 无内部冲突环境下的无β环分解 191
9．1基于线图的无β环判定 191
9．1．1线图是三角化的相关问题 191
9．1．2线图是β环判定算法 194
9．2无内部冲突满足P3的无β环分解条件 195
9．2．1无弱左部冲突、弱右部冲突D中任意两个归并依赖间的关系 195
9．2．2无内部冲突满足P3的无β环分解条件 201
9．3 F无内部冲突满足P3的无β环分解算法 205
9．3．1主归并依赖冲突判定算法 205
9．3．2无内部冲突满足P3的无β环分解算法 208
9．4无内部冲突满足P- BC的无β环分解问题 213
9．5有内部冲突满足P3的无β环分解 215
9．5．1环冲突及弱广义、归并广义左部冲突的判定算法 216
9．5．2有内部冲突的满足P3无β环分解存在条件 218
9．5．3有内部冲突的满足P3无β环分解算法 221
9．6小结 224
第10章 MVD无内部冲突环境下的无β环分解 225
10．1 MVD无冲突满足无β环数据库模式分解 225
10．1．1无β环且满足P4-的分解条件 225
10．1．2 MVD集的化简与等价 229
10．1．3严格无冲突的算法 234
10．2混合依赖环境下满足P4-无β环数据库模式研究 237
10．2．1混合依赖集的表示及化简 237
10．2．2混合依赖环境下满足P4-且无β环分解的条件 239
10．2．3混合依赖环境下的分解算法 242
10．3小结 246
第11章 无γ环无损联接的4NF数据库模式R分解 247
11．1 MVD环境下γ环数据库模式的存在性 247
11．2基于强无冲突MVD集的数据库模式的特性 248
11．2．1基于Nα-Decomposition强无冲突MVD集分解特性 248
11．2．2强无冲突MVD集数据库模式分解线图的特性 250
11．3无γ环的数据库模式的特性 252
11．3．1无γ环的数据库模式的线图特性 252
11．3．2无γ环的数据库模式的联接树的特性 254
11．4 MVD环境下产生无γ环数据库模式的条件 255
11．5强无冲突的覆盖存在性 257
11．5．1化简全依赖集的逻辑等价性 257
11．5．2强无冲突的覆盖存在的条件 258
11．6无γ环无损联接的4NF数据库模式R分解 260
11．6．1无γ环模式判定 260
11．6．2化简全依赖集无冲突判定 262
11．6．3强无冲突覆盖的判定和满足无γ环P4-分解算法 264
11．7小结 266
第12章 最小广义特征集与无γ环分解的相关性 267
12．1最小广义特征集 267
12．1．1最小广义特征集和广义特征集的区别 267
12．1．2无冲突MVD集M和FD集F蕴涵关系 268
12．2最小广义特征集和MVD相交性理论 272
12．2．1最小广义特征集和分割的关系 272
12．2．2最小广义特征集和MVD相交性关系 276
12．3无冲突的最小广义特征集 279
12．3．1无冲突的最小广义特征集特性 279
12．3．2无γ环的满足BCNF的数据库模式分解 282
12．4最小覆盖和最小广义特征集 285
12．4．1最小覆盖和相容性的关系 285
12．4．2最小覆盖和最小广义特征集的关系 287
12．5满足无γ环的BCNF数据库模式的分解算法 289
12．5．1归并依赖集的可不分裂集生成算法 289
12．5．2归并依赖集D的相容集的相关算法 292
12．5．3满足无γ环的BCNF数据库模式的相关算法 295
12．6小结 297
参考文献 298