数据依赖的公理系统
定理2 Armstrong公理系统是有效的、完备的。
Armstrong公理系统的有效性可由定理1得到证明。这里给出完备性的证明。
证明完备性的逆否命题，即若函数依赖X→Y不能由F从Armstrong公理导出，那么它必然不为F所蕴涵，它的证明分三步。
(1)若V→W成立，且V⊆X⁺F，则W⊆X⁺F。
证 因为V⊆X⁺F，所以有X→V成立；于是X→W成立(因为X→V，V→W)，所以W⊆X⁺F。
(2)构造一张二维表r，它由下列两个元组构成，可以证明r必是R(U,F)的一个关系，即F中的全部函数依赖在r上成立。
若r不是R<U,F>的关系，则必由于F中有某一个函数依赖V→W在r上不成立所致。由r的构成可知，V必定是X⁺F的子集，而W不是X⁺F的子集，可是由第(1)步，W⁺X⁺F，矛盾。所以r必是R<U,F>的一个关系。
(3)若X→Y不能由F从Armstrong公理导出，则Y不是X⁺F的子集，因此必有Y的子集Y'满足Y'⊆U-X⁺F，则X→Y在r中不成立，即X→Y必不为R<U,F>蕴涵。
Armstrong公理的完备性及有效性说明了“导出”与“蕴涵”是两个完全等价的概念。于是F⁺也可以说成是由F出发借助Armstrong公理导出的函数依赖的集合。
从蕴涵(或导出)的概念出发，又引出了两个函数依赖集等价和最小依赖集的概念。
定义14 如果G⁺=F⁺，就说函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖)，或F与G等价。
引理3 F⁺=G⁺的充分必要条件是F⁺⊆G⁺和G⁺⊆F⁺。
证 必要性显然，只证充分性。
(1)若F⊆G⁺，则X⁺F⊆X⁺G⁺
(2)任取X→Y∈F⁺，则有Y⊆X⁺F⊆X⁺G⁺
所以X→Y∈(G⁺)⁺=G⁺。即F⁺⊆G⁺
(3)同理可证G⁺⊆F⁺，所以F⁺=G⁺。
而要判定F⊆G⁺，只需逐一对F中的函数依赖X→Y考察Y是否属于X⁺G⁺。即可。因此引理3给出了判断两个函数依赖集等价的可行算法。
定义15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖(minimal cover)。
F中任一函数依赖的右部仅含有一个属性。
F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。
F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}U{Z→A}与F等价。
定义15(3)的含义是对于F中的每个函数依赖，它的左部要尽可能简。
【例1】考察关系模式S<U,F>，其中：
U={Sno, Sdept, Mname, Cno, Grade},
F={Sno→Sdept, Sdept→Mname, (Sno,Cno)→Grade}
设 F'={Sno→Sdept, Sno→Mname, Sdept→Mname, (Sno,Cno)→Grade, (Sno,Sdept)→Sdept}
根据定义15可以验证F是最小覆盖，而F'不是。因为F'-{Sno→Mname}与F'等价，F'-{(Sno,Sdept)→Sdept}与F'等价。
定理3 每一个函数依赖集F均等价于一个极小函数依赖集Fm。此F称为F的最小依赖集。
证 这是一个构造性的证明，分三步对F进行“极小化处理”，找出F的一个最小依赖集来。
(1)逐一检查F中各函数依赖FDi：X→Y，若Y=A1A2…Ak，k≥2，则用{X→Aj | j=1,2,…,k}来取代X→Y。
(2)逐一检查F中各函数依赖FDi：X→A，令G=F-{X→A}，若A∈X⁺G，则从F中去掉此函数依赖(因为F与G等价的充要条件是A∈X⁺G)。
(3)逐一取出F中各函数依赖FDi：X→A，设X=B1B2…Bm，m≥2，逐一考查Bi(i=1,2,…,m)，若A∈(X-Bi)⁺F，则以X-Bi取代X(因为F与F-{X→A}U{Z→A}等价的充要条件是A∈Z⁺F，其中Z=X-Bi)。
最后剩下的F就一定是极小依赖集，并且与原来的F等价。因为对F的每一次“改造”都保证了改造前后的两个函数依赖集等价。这些证明很显然，请读者自行补上。
应当指出，F的最小依赖集Fm不一定是唯一的，它与对各函数依赖FDi及X→A中X各属性的处置顺序有关。
【例2】F={A→B, B→A, B→C, A→C, C→A}
Fm1={A→B, B→C, C→A}
Fm2={A→B, B→A, A→C, C→A}
这里给出了F的两个最小依赖集Fm1、Fm2。
若改造后的F与原来的F相同，说明F本身就是一个最小依赖集，因此定理3的证明给出的极小化过程也可以看成是检验F是否为极小依赖集的一个算法。
两个关系模式R1<U,F>、R2<U,G>，如果F与G等价，那么R1的关系一定是R2的关系；反过来，R2的关系也一定是R1的关系。所以在R<U,F>中用与F等价的依赖集G来取代F是允许的。
小 结
本章在函数依赖、多值依赖的范畴内讨论了关系模式的规范化，其基本思想可用下图表示。
在整个讨论过程中，只采用了两种关系运算——投影和自然连接，并且总是从一个关系模式出发，而不是从一组关系模式出发实行分解。“等价”的定义也是一组关系模式与一个关系模式的“等价”，这就是说，在开始讨论问题时事实上已经假设了存在着一个单一的关系模式，这就是泛关系(universal relation)假设。
本章一开始就指出这是研究模式设计的一种特殊情况：“假设已知一个模式Sφ，它仅由单个关系模式组成，问题是要设计一个模式SD，它与Sφ等价，但在某些方面更好一些”。
泛关系假设是运用规范化理论时的障碍，因为承认了泛关系假设就等于承认了现实世界各实体间只能有一种联系，而这常常是办不到的。比如工人与机器之间就可以存在“使用”、“维护”等多种联系。对此人们提出了一些办法，希望解决这个矛盾。例如建立一个不受泛关系假设限制的理论，或者采用某些手段使现实世界向信息世界转换时适合于泛关系的要求。
最后应当强调的是，规范化理论为数据库设计提供了理论的指南和工具，但仅仅是指南和工具。并不是规范化程度越高模式就越好，必须结合应用环境和现实世界的具体情况
