https://www.modb.pro/db/170662
数据依赖的公理系统
数据依赖的公理系统是模式分解算法的理论基础。下面首先讨论函数依赖的一个有效而完备的公理系统——Armstrong公理系统。
定义11 对于满足一组函数依赖F的关系模式R<U，F>，其任何一个关系r，若函数依赖X→Y都成立(即r中任意两元组t、s，若t[X]=s[X]，则t[Y]=s[Y])，则称F逻辑蕴涵X→Y。
为了求得给定关系模式的码，为了从一组函数依赖求得蕴涵的函数依赖，例如已知函数依赖集F，要问X→Y是否为F所蕴涵，就需要一套推理规则，这组推理规则是1974年首先由Armstrong提出来的。
Armstrong公理系统(Armstrong's axiom) 设U为属性集总体，F是U上的一组函数依赖，于是有关系模式R<U,F>，对R<U,F>来说有以下的推理规则：
自反律(reflexivity rule)：若Y⊆X⊆U，则X→Y为F所蕴涵。
增广律(augmentation rule)：若X→Y为F所蕴涵，且Z⊆U，则XZ→YZ为F所蕴涵。
传递律(transitivity rule)：若X→Y及Y→Z为F所蕴涵，则X→Z为F所蕴涵。
注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。
定理1 Armstrong推理规则是正确的。
下面从定义出发证明推理规则的正确性。
证
(1)设Y⊆X⊆U.
对R<U,F>的任一关系r中的任意两个元组t、s：
若t[X]=s[X]，由于Y⊆X，有t[Y]=s[Y]，
所以X→Y成立，自反律得证。
(2)设X→Y为F所蕴涵，且Z⊆U。
设R<U,F>的任一关系r中任意的两个元组t、s：
若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z];
由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，XZ→YZ为F所蕴涵，增广律得证。
(3)设X→Y及Y→Z为F所蕴涵。
对R<U,F>的任一关系r中的任意两个元组t、s：
若t[X]=s[X]由于X→Y，有t[Y]=s[Y]；
再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴涵，传递律得证。
根据上面这三条推理规则可以得到下面三条很有用的推理规则。
合并规则(union rule)：由X→Y，X→Z，有X→YZ。
伪传递规则(pseudo transitivity rule)：由 X→Y，WY→Z，有XW→Z。
分解规则(decomposition rule)：由X→Y及Z⊆Y，有X→Z。
根据合并规则和分解规则，很容易得到这样一个重要事实：
引理1 X→A1A2…Ak成立的充分必要条件是X→Ai成立(i=1,2,…,k)。
定义12 在关系模式R<U,F>中为F所逻辑蕴涵的函数依赖的全体叫作F的闭包(closure)，记为F⁺。
人们把自反律、传递律和增广律称为Armstrong公理系统。Armstrong公理系统是有效的、完备的。Armstrong公理的有效性指的是：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F中：完备性指的是F中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。
要证明完备性，就首先要解决如何判定一个函数依赖是否属于由F根据Armstrong公理推导出来的函数依赖的集合。当然，如果能求出这个集合，问题就解决了。但不幸的是，这是一个NP完全问题。例如，从F={X→A1，…，X→An}出发，至少可以推导出2ⁿ个不同的函数依赖。为此引入了下面的概念：
定义13 设F为属性集U上的一组函数依赖，X、Y⊆U，X⁺F={A|X→A能由F根据Armstrong公理导出}，X⁺F称为属性集X关于函数依赖集F的闭包。
由引理1容易得出引理2。
引理2 设F为属性集U上的一组函数依赖，X、Y⊆U，X→Y能由F根据Armstrong公理导出的充分必要条件是Y⊆X⁺F。
于是，判定X→Y是否能由F根据Armstrong公理导出的问题就转化为求出X⁺F，判定Y是否为X⁺F的子集的问题。这个问题由算法1解决了。
算法1 求属性集X(X⊆U)关于U上的函数依赖集F的闭包X⁺F。
输入：X、F
输出：X⁺F
步骤：
①令X⁽ᶿ⁾=X，i=0。
②求B，这里B={A|(∃V) (∃W) (V→W∈F ^ V⊆X⁽ⁱ⁾ ^ A∈W)}。
③X⁽ⁱ⁺¹⁾=BUX⁽ⁱ⁾。
④判断X⁽ⁱ⁺¹⁾=X⁽ⁱ⁾。
⑤若X⁽ⁱ⁺¹⁾与X⁽ⁱ⁾相等或X⁽ⁱ⁾=U，则X⁽ⁱ⁾就是X⁺F，算法终止。
⑥若否，则i=i+l，返回第②步。
【例1】已知关系模式R<U,F>，其中U={A, B, C, D, E}, F={AB→C, B→D, C→E, EC→B, AC→B}。求(AB)⁺F。
解 由算法1，设X⁽⁰⁾=AB。
计算X⁽¹⁾：逐一扫描F集合中各个函数依赖，找左部为A、B或AB的函数依赖。得到两个：AB→C，B→D。于是X⁽¹⁾=ABUCD=ABCD。
因为X⁽⁰⁾≠X⁽¹⁾，所以再找出左部为ABCD子集的那些函数依赖，又得到C→E，AC→B，于是X⁽²⁾=X⁽¹⁾UBE=ABCDE。
因为X⁽²⁾已等于全部属性集合，所以(AB)⁺F=ABCDE。
对于算法1，令ai=|X⁽ⁱ⁾|，{ai}形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多|U|-|X|次循环就会终止。
数据依赖的公理系统
定理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φ等价，但在某些方面更好一些”。
泛关系假设是运用规范化理论时的障碍，因为承认了泛关系假设就等于承认了现实世界各实体间只能有一种联系，而这常常是办不到的。比如工人与机器之间就可以存在“使用”、“维护”等多种联系。对此人们提出了一些办法，希望解决这个矛盾。例如建立一个不受泛关系假设限制的理论，或者采用某些手段使现实世界向信息世界转换时适合于泛关系的要求。
最后应当强调的是，规范化理论为数据库设计提供了理论的指南和工具，但仅仅是指南和工具。并不是规范化程度越高模式就越好，必须结合应用环境和现实世界的具体情况
联系客服
