数据库数据组织无环性理论

出版时间：2009-3  出版社：科学出版社  作者：郝忠孝  页数：299  

前言

数据库技术是在20世纪60年代末作为数据管理的最新技术登上数据处理舞台的。随着计算机应用的不断扩大，计算机硬件快速发展，数据库技术也得到了迅速的发展。数据库技术和计算机网络技术已成为当今世界计算机应用中两个最重要的基础领域。经过四十多年的发展，以数据模型的进展、变化为主线，出现了以层次模型和网状模型为代表的层次数据库和网状数据库的第一代数据库。20世纪70年代末出现了以关系数据模型为代表的第二代数据库——关系数据库。关系数据库应用数学方法来处理数据库中的数据，这也正是关系模型能够长盛不衰，成为许多其他类型数据库发展的基础，能够成为第二代数据库典型代表的主要原因。最早提出关系模式雏形的是美国IBM公司Codd，1970年在美国计算机学会会刊CommunicationoftheACM上发表的题为“A Relational Model of Data for Shared Data Banks”的论文中提出了关系模型的思想。此后，他又发表了一系列有价值的论文，确立了关系数据库理论的框架，正是由于他的贡献，1980年获得了图灵奖。人们在关系数据库理论方面做了大量的研究工作，随着关系数据库理论的不断完善以及计算机技术的不断发展，关系数据库的技术也日趋成熟。关系数据库之所以重要，主要是它具有以关系代数与逻辑为手段的严格的理论基础，同时还具有单一的数据结构，数据独立性强与操作简单等优点。关系数据库之后，又出现了面向对象数据库系统、分布式数据库系统、并行数据库系统等。但目前运行的数据库系统大部分仍是关系型的，这说明关系数据库具有强大的生命力，关系数据库规范化和设计理论的研究仍具有理论和实际意义。自20世纪70年代Codd及其他一些著名学者发表一系列论文开始，开创了关系数据库及关系数据库的理论研究的一个时代，这一理论直到80年代初才算基本完成，其标志是Ullman1980年发表了他的专著Principles of Database Sys-terns。这之后，Datc和Maier相继发表了相关专著，促进了关系数据库理论的发展。关系数据库理论中最重要的组成部分是数据依赖及其相关性质和关系规范化理论。迄今为止，这些问题的研究已经取得了很多重要成果。数据依赖作为对数据固有语义的一种描述形式被引入。一些重要的数据依赖类型，如FD、WVD、JD等被深入地研究过，若干描述数据依赖之间的逻辑蕴涵关系的形式公理系统被提出。

内容概要

本书是在作者三十余年来对关系数据库数据组织理论研究的基础上撰写的。书中系统论述和分析了数据库数据组织理论以及作者提出的若干新的概念、方法、算法。    本书共分12章。主要内容包括：基于超图、线图的无α环、无β环、无γ环的特性。特别提出了作为本书讨论的核心概念——归并依赖集。在深入研究这个概念的基础上给出了归并依赖集的最小归并依赖集、蕴涵左部集、扩展左部集、全部对称左部集等相关概念，对归并依赖集的性质进行系统的研究。关联度、关联集是另一类重要概念。在深入讨论中还给出了有、无内部冲突，左、右部冲突，弱左、右部冲突，广义左、右部冲突，集间冲突，集内冲突，强左部冲突，强无冲突MVD集，最小广义特征集等概念。在此基础上分别讨论了在有、无内部冲突环境下的无α环、无β环、无γ环的数据库模式分解。    本书可作为计算机科学与技术学科、数据库相关专业的高年级本科生教材或硕士生选修课教材，也可供从事上述领域研究的博士生、科研人员及工程技术人员参考。

书籍目录

前言第1章  基本知识  1.1  关系模型和关系模式    1.1.1  函数依赖及相关理论概念    1.1.2  多值依赖及相关理论概念  1.2  候选关键字    1.2.1  候选关键字约束    1.2.2  求关系模式的一个候选关键字    1.2.3  求全部候选关键字一一替换法  1.3  逻辑蕴涵和覆盖    1.3.1  逻辑蕴涵    1.3.2  覆盖与等价  1.4  范式与规范化  1.5  联接依赖的性质和判定问题    1.5.1  联接依赖的概念    1.5.2  全生成元组器    1.5.3  联接依赖的种类和联接表    1.5.4  联接依赖性质的判定  1.6  符号表和追踪算法    1.6.1  符号表    1.6.2  追踪算法  1.7  小结第2章  数据库模式环的种类与特性  2.1  无环数据库的良好的特性  2.2  超图和线图    2.2.1  超图及与超图相关概念    2.2.2  无环的超图和线图的概念    2.2.3  无α环的判定——Graham算法    2.2.4  化简一致超图的性质    2.2.5  联接树顺序表达式    2.2.6  FD超图  2.3  超图中各种环的定义及关系    2.3.1  超图中各种环的定义    2.3.2  超图中各种环的关系  2.4  超图有α环的特性  2.5  超图有β环的特性  2.6  超图有γ环的特性  2.7  小结第3章  函数依赖集F有内部冲突的判定  3.1  FD集F的归并依赖集的相关概念  3.2  FD集F的归并依赖集的求解算法  3.3  FD集F的最小归并依赖集的求解算法  3.4  二元组集合闭包B+求解算法  3.5  函数依赖集F有内部冲突的判定  3.6  归并FD超图表示及构造    3.6.1  归并准路与准环    3.6.2  超图构造算法  3.7  归并FD超图存在内部冲突的条件和算法    3.7.1  归并FD超图存在内部冲突的条件    3.7.2  归并FD超图存在内部冲突的检测算法  3.8  小结第4章  无内部冲突环境下的无α环分解  4.1  归并依赖集存在弱左、右部冲突判定  4.2  最小归并依赖集的关联度  4.3  无内部冲突满足P3的无α环分解条件  4.4  无内部冲突满足P3的无α环分解算法  4.5  冗余属性的确定  4.6  无内部冲突满足PEK无α环分解    4.6.1  初等关键字范式的相关概念    4.6.2  满足初等关键字范式的分解    4.6.3  满足PEK无α环分解  4.7  无内部冲突满足Ps的无α环分解    4.7.1  简单范式及相关概念    4.7.2  满足简单范式的分解    4.7.3  满足P3的无α环分解  4.8  小结第5章  有内部冲突的广义左、右部冲突的性质和判定  5.1  归并依赖集的对称左部属性集  5.2  有内部冲突的广义左、右部冲突的性质    5.2.1  有内部冲突的广义左部冲突的性质    5.2.2  有内部冲突的广义右部冲突的性质  5.3  有内部冲突的广义左、右部冲突判定算法  5.4  小结第6章  F有内部冲突满足无α环分解  6.1  有内部冲突满足P3的无α环分解条件  6.2  F有内部冲突满足P3的无α环分解算法  6.3  小结第7章  多值依赖环境下的无α环分解  7.1  满足无损联接和4NF的分解    7.1.1  保证无损联接和4NF分解的有关定理    7.1.2  产生4NF分解的思想和算法  7.2  MVD集M无冲突的判定    7.2.1  无α环联接依赖与无冲突多值依赖集的等价性    7.2.2  MVD集M冲突判定算法  7.3  混合依赖集环境下的数据库模式无α环分解问题    7.3.1  混合依赖集D的生成多值依赖集    7.3.2  混合依赖集环境下的数据库模式无α环分解  7.4  关系数据库模式环境的判定和泛分解问题的讨论    7.4.1  数据依赖环境的判定    7.4.2  关系数据库模式的泛分解算法  7.5  小结第8章  归并依赖集左部集分析  8.1  归并依赖集左部属性集分析及求解算法    8.1.1  一个归并依赖的扩展左部集求法    8.1.2  归并依赖集的左部联合集的求解算法    8.1.3  蕴涵左部集的求解  8.2  FD集F的归并依赖集集间联系与冲突    8.2.1  归并依赖集集间冲突    8.2.2  归并依赖集集内冲突    8.2.3  归并依赖集强左部冲突和几个冲突的区别  8.3  小结第9章  无内部冲突环境下的无β环分解  9.l  基于线图的无β环判定    9.1.1  线图是三角化的相关问题    9.1.2  线图是β环判定算法  9.2  无内部冲突满足P3的无犀环分解条件    9.2.1  无弱左部冲突、弱右部冲突D中任意两个归并依赖间的关系    9.2.2  无内部冲突满足P3的无β环分解条件  9.3  F无内部冲突满足P3的无β环分解算法    9.3.1  主归并依赖冲突判定算法    9.3.2  无内部冲突满足P3的无β环分解算法  9.4  无内部冲突满足PBC-的无β环分解问题  9.5  有内部冲突满足P3的无β环分解    9.5.1  环冲突及弱广义、归并广义左部冲突的判定算法    9.5.2  有内部冲突的满足P3无β环分解存在条件    9.5.3  有内部冲突的满足P3无β环分解算法  9.6  小结第10章  MVD无内部冲突环境下的无β环分解  10.1  MVD无冲突满足无β环数据库模式分解    10.1.1  无廖环且满足P4-的分解条件    10.1.2  MVD集的化简与等价    10.1.3  严格无冲突的算法  10.2  混合依赖环境下满足P4-无β环数据库模式研究    10.2.1  混合依赖集的表示及化简    10.2.2  混合依赖环境下满足P4-且无β环分解的条件    10.2.3  混合依赖环境下的分解算法  10.3  小结第11章  无丫环无损联接的4NF数据库模式R分解  11.1  MVD环境下7环数据库模式的存在性  11.2  基于强无冲突MVD集的数据库模式的特性    11.2.1  基于Nα-Decomposition强无冲突MVD集分解特性    11.2.2  强无冲突MVD集数据库模式分解线图的特性  11.3  无γ环的数据库模式的特性    11.3.1  无γ环的数据库模式的线图特性    11.3.2  无γ环的数据库模式的联接树的特性  11.4  MVD环境下产生无γ环数据库模式的条件  11.5  强无冲突的覆盖存在性    11.5.1  化简全依赖集的逻辑等价性    11.5.2  强无冲突的覆盖存在的条件  11.6  无γ环无损联接的4NF数据库模式尺分解    11.6.1  无γ环模式判定    11.6.2  化简全依赖集无冲突判定    11.6.3  强无冲突覆盖的判定和满足无γ环P4-分解算法  11.7  小结第12章  最小广义特征集与无γ环分解的相关性  12.1  最小广义特征集    12.1.1  最小广义特征集和广义特征集的区别    12.1.2  无冲突MVD集M和FD集F蕴涵关系  12.2  最小广义特征集和MVD相交性理论    12.2.1  最小广义特征集和分割的关系    12.2.2  最小广义特征集和MVD相交性关系  12.3  无冲突的最小广义特征集    12.3.1  无冲突的最小广义特征集特性    12.3.2  无γ环的满足BCNF的数据库模式分解  12.4  最小覆盖和最小广义特征集    12.4.1  最小覆盖和相容性的关系    12.4.2  最小覆盖和最小广义特征集的关系  12.5  满足无γ环的BCNF数据库模式的分解算法    12.5.1  归并依赖集的可不分裂集生成算法    12.5.2  归并依赖集D的相容集的相关算法    12.5.3  满足无γ环的BCNF数据库模式的相关算法  12.6  小结参考文献

章节摘录

插图：第2章 数据库模式环的种类与特性从关系数据库问世以来，数据库中模式分解的问题一直是关系数据库研究人员的重点问题，即在相应的条件下，得到品质优良的模式分解。多年来，许多研究者的研究成果表明：对于纯FD环境下的数据库模式分解都可以得到同时满足无损联接性、保持函数依赖性、3NF或BCNF这三个特性的数据库模式分解。2.1 无环数据库的良好的特性自从Beeri，Fagin等提出的无α环数据库模式以来，许多研究人员的成果表明无α环数据库模式是一个重要的级别，它可以从许多不同的角度来定义和表示，而每一种表示方式都对应了一些良好的特性。许多在有。环数据库模式中出现的不良的异常现象，在无。环数据库模式中是不存在的。而且许多在有α环模式中要解决的问题是不存在多项式时间的解决算法的，是NP完全的问题。在无α环模式中却存在着多项式时间的解决算法，比如说总体一致性问题。另外，对于无。环数据库模式，在查询时无论对于时间性还是空间性都存在一个较佳的查询路径，这尤其表现在当需要几个关系模式的联接来完成一个查询时。上述几点充分说明了无α环数据模式的设计具有重要意义。经研究表明，无环数据库模式能够充分体现客观现实世界。因而，人们把模式分解的无α环特性作为数据库模式分解的一种优良特性。

编辑推荐

《数据库数据组织无环性理论》可作为计算机科学与技术学科、数据库相关专业的高年级本科生教材或硕士生选修课教材，也可供从事上述领域研究的博士生、科研人员及工程技术人员参考。