非经典关系数据库理论

　　本书系统介绍了非经典关系数据库理论的国际前沿成果及作者本人的研究成果，内容包括约束关系模型、时态关系模型、空值关系模型、偏序关系模型、概率关系模型、对象关系模型、粗糙关系模型、关系中的说明性更新、关系中的相容与蕴含及关系中的说明性扩充等。本书是数据库领域的学术专著，可作为高等院校计算机专业研究生或本科高年级学生的教材，也可作为相关专业科技工作者的参考书，对一般数据库的研究及教学有很大的参考价值。本书前言序1998年3月我曾为马垣的著作《关系数据库理论》作序，那是我在学习和思考后，对关系数据库和其他数据库技术的发展形成的一些认识。时隔6年，作者又有了新的著作《非经典关系数据库理论》，这是作者在数据库理论研究领域辛勤耕耘的又一成果。关系数据库从1970年诞生到现在已有30多年了。30多年来，它的应用领域越来越广，影响的范围越来越大。2003年全世界关系数据库年销售额已达70亿美元，根据IDC市场研究公司预测，2008年全世界关系数据库年销售额将达到200多亿美元。关系数据库之所以能如此快速的发展，究其原因就是它从诞生就得到了严格的理论指导与支持。1970年6月，IBM公司的高级研究员EdgarFrankCodd发表的论文“Arelationalmodelforlargeshareddatabanks”开创了关系数据库的新时代。该论文于1983年被ACM列为1958年以来具有里程碑意义的25篇论文之一。1981年Codd获图灵奖。关系数据库和许多事物一样也在与时俱进。20世纪90年代以来，关系数据库的研究领域及应用领域（例如从数据库发现知识领域）更加扩大，提出了很多新思想，引出了很多新方向，取得了很多新成果。这些新思想、新方向、新成果全都远远超出了原来的经典研究范围，它们形成了前景非常广阔的“非经典关系数据库”。目前，国内外集中而系统地论述非经典关系数据库理论的书还非常少，《非经典关系数据库理论》一书是我国的第一部，是作者在其1999年的著作《关系数据库理论》的基础上撰写的新的、全面反映非经典关系数据库理论的学术专著，其中也包括作者本人的成果。书中的内容是目前非经典关系数据库理论的世界前沿，绝大多数内容都是目前国内外相关的书籍中没有介绍过的。例如，该书研讨的“单依赖”集合就是人们在研究不完全关系中函数依赖的可加性时提出的一种全新概念，是在20世纪90年代前国际上未曾研究过的。它的提出彻底解决了函数依赖的可加性问题。而更有意义的是，它还使经典关系数据库中的一些遗留问题有了答案。再如该书介绍的一种“二元关系约束”也是经典关系数据库中函数依赖、多值依赖、连接依赖、等值产生依赖、元组产生依赖等诸多约束都未能包括的全新约束。这种约束在实际应用中的意义不亚于经典关系数据库中的约束。近些年来国内外对具有复杂对象的时态关系进行了很多的研究，各种成果也都超出了经典关系理论的范畴，该书中均做了详细的论述。粗糙关系、偏序关系、概率关系、对象关系等新的关系模型更是层出不穷，该书全面研究了这些关系模型，并对研究成果一一进行了论述。该书内容翔实，视野开阔。显然，它的出版将会与国内外学者的研究成果相辅相成，成为国内同行研究工作中非常有用的武器，书中的最新成果对大家的工作都有很好的参考价值，并具有很好的启发和帮助作用。不论在理论上，还是在实践上，该书的出版都对我国关系数据库的研究向更广、更深的方向发展起到非常重要的作用。本书作者于20世纪70年代初开始从事编制计算机程序的工作，80年代初开始了对数据库理论的研究，1989年出版了《VAX11网状数据库》一书，1999年出版了《关系数据库理论》一书。作者原先在冶金部门工作，是在繁忙的工作之余从事数据库理论研究的。这期间他不仅在工作上获得了许多国家级及省部级奖项，而且在《计算机学报》、《计算机工程》等刊物上发表了许多关系数据库理论的论文。作为业余研究人员，他于1995年获得了国家自然科学基金资助。作者现于鞍山科技大学计算机科学与工程学院担任研究生导师。他从一个业余研究人员成为本领域卓有成就的执著的专业研究人员，这在国内是少见的，他那种锲而不舍、刻苦钻研的精神值得我们敬佩与学习。我祝贺这本书的出版，并高兴地把这本书推荐给广大读者。祝我国的数据库理论研究人才辈出，祝我国的数据库实际应用欣欣向荣。

暂缺《非经典关系数据库理论》作者简介

第1章约束关系模型1
1.1二元约束关系1
1.1.1形式化定义3
1.1.2约束关系运算4
1.1.3约束矩阵4
1.1.4约束矩阵的运算5
1.1.5路径相容与对称7
1.2广义关系代数7
1.2.1布尔代数7
1.2.2广义关系代数的定义8
1.2.3K定理.表征.简单关系代数8
1.2.4原子11
1.2.5等价元素及“z广义关系代数”11
1.3广义关系代数的实例12
1.3.1点代数12
1.3.2区间代数13
1.3.3包含代数17
1.3.4硬代数18
1.4广义关系代数上的矩阵18
1.4.1原子RA矩阵及原始可解性21
1.4.2解答21
1.4.3原始可解性与解之间的关系21
1.4.4最小示踪22
1.5约束关系模型在查询优化中的应用25
1.5.1关系数据库的查询25
1.5.2不等式合取查询与点代数27
1.5.3二元约束矩阵的变换29
1.5.4不等式合取查询极小化31
1.5.5二元约束矩阵的全部原始解34
1.6在其他领域的应用36
1.6.1计算机视觉36
1.6.2图着色39
第2章时态关系模型42
2.1具有复杂对象的时态关系42
2.2实例46
2.3时间模型48
2.3.1时间关系48
2.3.2时间关系的WIJSEN基48
2.3.3时态类型50
2.3.4时态类型的细偏序格51
2.4数据模型51
2.4.1模式与时态实例51
2.4.2模式依赖图（SDG）53
2.4.3有效时间与事务时间54
2.5时态函数依赖54
2.5.1时态函数依赖实例54
2.5.2时态函数依赖的形式化定义55
2.5.3时态函数依赖的公理系统55
2.6无回路模式56
2.6.1公理及蕴含56
2.6.2闭包59
2.7约束线性时间序列62
2.7.1整体细化与TFDX公理62
2.7.2约束实例64
2.8回路模式65
2.8.1Twin关系65
2.8.2有限与无限约束65
2.8.3无约束蕴含的完备性66
第3章空值关系模型70
3.1不完全关系及函数依赖的可加性70
3.2形式化定义73
3.3可满足性74
3.4Lien-Atzeni公理系统及“单依赖”集合75
3.5“单依赖”集合与可加性的重要联系86
3.6最小函数依赖集合与最优函数依赖集合93
3.6.1“分特性”与“交特性”109
3.6.2周年特征集合与复合函数依赖116
3.6.3“单依赖”集合的构造理论126
3.7“单依赖”的K基数关键字127
3.7.1分特性时关键字多项式算法130
3.7.2分特性与交特性时主属性多项式算法134
3.8交特性时2NF=3NF=BCNF139
3.9“单依赖”时无损连接的分解一定无损依赖141
第4章偏序关系模型153
4.1偏序数据域上的关系153
4.2形式化定义156
4.2.1点态序及字典序156
4.2.2序关系模式与序关系157
4.3序关系运算157
4.3.16种基本运算158
4.3.2数据库保序自同构160
4.3.3查询.可计算性.序域.序代数的层次170
4.3.4关系的内部层次及OSQL语言176
4.3.5OSQL在树结构.时态.不完全信息中的应用183
4.3.6OSQL的完整语法185
4.4序函数依赖187
4.4.1点态序函数依赖及字典序函数依赖187
4.4.2点态序函数依赖有效完备公理系统189
4.4.3字典序函数依赖的追赶算法192
4.4.4“模型关系”及字典序函数依赖推导规则197
4.4.5点态序字典序联合函数依赖200
第5章概率关系模型203
5.1概率关系的基本思想203
5.1.1联合分布与边缘分布204
5.1.2概率选择.概率投影和概率连接205
5.1.3信念修改与并.差运算208
5.2概率关系及其运算的形式化210
5.2.1PLUS合并.MAX合并及概率关系210
5.2.2内部完整性约束与参考完整性约束212
5.2.3包含“条件运算”及“α截取”的关系代数213
5.2.4概率关系代数的封闭性及兼容性217
5.2.5概率关系查询220
5.3包含空值的概率关系221
5.3.1空缺概率223
5.3.2N次值矩与空值Ω224
第6章对象关系模型227
6.1经典关系理论与面向对象思想227
6.1.1经典关系数据库设计方法227
6.1.2经典关系理论对面向对象的不适应228
6.2用于规范化的面向对象数据模型230
6.2.1数据模型230
6.2.2依赖与聚集.联合.继承233
6.2.3垂直路径.水平路径及组合路径234
6.2.4投影代数235
6.3面向对象数据模型中的“依赖”238
6.3.1路径依赖238
6.3.2局部依赖239
6.3.3整体依赖241
6.3.4路径关键字242
6.4对象模型“依赖”的公理系统243
6.5对象模型规范化244
6.5.1实例244
6.5.2对象模型247
6.5.3对象范式250
6.5.4规范化的规则252
6.5.5规则的完备性255
6.6对象范式的设计方法256
6.6.1修改模式法256
6.6.2生成对象结构法257
6.6.3分解与合成算法258
第7章粗糙关系模型279
7.1粗糙集的基本概念279
7.2粗糙关系数据库281
7.3粗糙关系查询284
7.4粗糙关系运算287
7.4.1粗糙差287
7.4.2粗糙并289
7.4.3粗糙交290
7.4.4粗糙选择291
7.4.5粗糙投影292
7.4.6粗糙连接293
7.5粗糙运算符的性质296
7.6粗糙关系中的信息熵297
7.6.1精确度与粗糙度297
7.6.2粗糙模式熵297
7.6.3粗糙关系熵298
第8章关系中的说明性更新301
8.1更新运算301
8.1.1包含动态原子的谓词公式302
8.1.2外展.紧致等价与紧致模型303
8.2数据库NDBPTIME变换及相应的图灵机307
8.3动态关系及更新代数312
8.3.1动态关系312
8.3.2动态关系上的运算314
8.3.3更新代数317
8.4更新的解318
8.4.1动态查询的解318
8.4.2动态查询的某些特殊情况320
8.4.3从动态表达式到动态查询322
第9章关系中的相容与蕴含324
9.1问题的提出324
9.2从Rosenkrantz到Ullman再到Gou等人的复杂度研究326
9.3相容问题328
9.3.1OP┐≠相容问题328
9.3.2OPall相容问题334
9.4蕴含问题335
9.4.1OP┐≠蕴含问题335
9.4.2Klug-Ullman公理系统与OPall蕴含问题338
第10章关系中的说明性扩充347
10.1模型框架347
10.2“序”.“前辍”.“扩充”与“抽取”349
10.3特定的几何扩充351
10.4几何关系代数实例352
10.5说明性可扩充代数353
10.5.1语法格式说明353
10.5.2描述性代数及可执行代数354
10.5.3包括索引结构的可执行代数355
10.6可扩充系统的构成359
10.6.1查询计算的层次结构359
10.6.2可扩充的数据类型361
10.6.3可执行运算符的扩充362
10.6.4规则的扩充与存入363
参考文献367