【梳理】数据库系统概论 第6章 关系数据理论 6.3 数据依赖的公理系统

教材：王珊 萨师煊 编著 数据库系统概论（第5版） 高等教育出版社
注：文档高清截图在后

6.3 数据依赖的公理系统

1、有满足一组函数依赖F的关系模式R<U, F>。如果函数依赖X→Y对R的全部关系r成立（对r中的任意两个元组s、t，若s[X] = t[X]则s[Y] = t[Y]），就说F逻辑蕴涵X→Y。也就是说，F能够推出不直接存在于F中的依赖X→Y。

2、Armstrong公理系统（axiom） 设属性集总体U，F是U上的一组函数依赖，对关系模式R<U, F>有以下推理规则：
【1】自反律（reflexivity rule）：若 ，则X→Y为F所蕴涵。
【2】增广律（augmentation rule）：若X→Y为F所蕴涵，且 ，则X∪Z→Y∪Z为F所蕴涵。
【3】传递律（transitivity rule）：若X→Y及Y→Z为F所蕴涵，则X→Z为F所蕴涵。
证明 【1】设R<U, F>中任一关系r中的任意元组s、t，若s[X] = t[X]，由于 ，所以s[Y] = t[Y]。所以X→Y。
【2】设R<U, F>中任一关系r中的任意元组s、t，若s[X∪Z] = t[X∪Z]，则s[X] = t[X]、s[Z] = t[Z]。而X→Y，所以s[Y] = t[Y]，所以由s[Y] = t[Y]，s[Z] = t[Z]得s[Y∪Z] = t[Y∪Z]。又s[X∪Z] = t[X∪Z]，所以X∪Z→Y∪Z为F所蕴涵。
【3】设R<U, F>中任一关系r中的任意元组s、t，若s[X] = t[X]，且X→Y，所以s[Y] = t[Y]。又Y→Z，所以s[Z] = t[Z]。又s[X] = t[X]，所以X→Z为F所蕴涵。

3、（1）合并规则（union rule）：由X→Y，X→Z，有X→Y∪Z。
（2）伪传递规则（pseudo transitivity rule）：由X→Y，W∪Y→Z，（有X∪W→W∪Y）有X∪W→Z。
（3）分解规则（decomposition rule）：由X→Y及 ，有X→Z。

4、X→A1∪A2∪……∪Ak的充要条件是：X→Ai成立（i = 1，2，……，k）。

5、R<U, F>中为F逻辑蕴涵的函数依赖的全体叫做F的闭包（closure）F+。

6、Armstrong公理系统是有效的、完备的。这里的有效性指的是：根据该公理由F出发推导出来的每个函数依赖一定都在F+中；完备性指的是：F+中的每一个函数依赖，必定可以由F通过该公理推导出来。

7、NP完全问题（NPC问题）是世界七大数学难题之一。首先明确几个定义：
（1）P问题。这类问题具有多项式的时间复杂度的确定的算法。即对于一切合法的输入，都能在多项式的时间内给出结果。对于一个尚未验证正确性的解，要验证其是否正确，时间复杂度自然也是多项式的。
（2）NP问题。这类问题目前尚未找到具有多项式的时间复杂度的确定的算法，但对于每个可能的解，都可以在多项式时间内对正确性完成验证。
（3）NPC问题。如果全部的NP问题都能转化成一个很复杂的问题去求得多项式时间的“通法”，以至于只要解决了这个最复杂的问题，那么其余的NP问题都可以在多项式的时间复杂度内完成求解。也就是说，NP问题实际上都是P问题，即NP = P。NP完全问题的核心内容就是“NP = P？”，即：是否所有能在多项式的时间内验证一个解的问题，都具有一个确定的时间复杂度为多项式的算法？
比如我们已知解一元、二元、三元、四元的线性方程组的算法。我们把这个问题不断推广，推广到n元线性方程组，如果对n元线性方程组能找到多项式的时间复杂度的算法，那么这个算法就可以套用去解一、二、三、四、……元的线性方程组。NP问题转化到NPC问题的思想也是类似的。

8、要证明Armstrong公理的完备性，首先要解决如何判定一个函数依赖是否属于由F根据Armstrong公理推得的函数依赖集。但很不幸，要求出这个集合，就是在求解一个NP完全问题：例如已知F = {X→A1，X→A2，……，X→An}，只通过合并规则就可以枚举出2n个不同的函数依赖（乘法原理或二项式定理也可以算出枚举数量是2n）。也就是说已知算法的复杂度都是指数级的，无论是人类还是计算机都难以接受。为此，引入下面的概念：

9、设F为属性集U上的一组函数依赖， ，XF+ = {A | X→A可由F通过Armstrong公理导出}。则XF+为属性集X关于函数依赖集F的闭包。显然X∈XF+，因为X→X，不过这是平凡的函数依赖。

10、由上一条易得：设F为属性集U上的一组函数依赖， ，一个函数依赖X→Y能由F根据Armstrong公理导出的充分必要条件是： 。下面也有证明。
11、求属性集X（ ）关于U上的函数依赖及F的闭包XF+的算法。
输入：X、F
输出：XF+
（1）X0 = X，i = 0。
（2）求B，其中 。
（3）Xi+1 = Xi∪B。
（4）判断：若Xi+1 = Xi或Xi = U，则X就是XF+，算法终止。若否，i = i + 1，重新从（2）开始执行。

12、Armstrong公理是有效的、完备的。
证明 有效性是指Armstrong公理的三条推理规则（自反律、增广律、传递律）成立，即Armstrong公理的推理规则是正确的。这里只给出完备性的证明。
前面已经即证逆否命题“设关系模式R<U, F>。若函数依赖X→Y不能由F通过Armstrong公理导出，那么X→Y不为F所蕴涵”。证明分三步：
（1）先证：若V→W，且 ，那么 。
因为 ，所以X→V。而X→V，V→W，所以X→W，所以 。
（2）在（1）的条件下，再证：构造二维表r，由下面两个元组构成（属性列的顺序不影响关系，所以把整个XF+画在一起）：

若r不是R<U, F>的关系，则F中至少有某个函数依赖V→W在r上不成立。但 ，所以只能有 不成立，与（1）矛盾。所以r只能是R<U, F>下的一个关系。
（3）在（2）的条件下，若X→Y不能由F通过Armstrong公理导出，则Y不是XF+的子集（回忆一下能导出的充要条件，且在（1）中已证明）。因此必有Y的子集Y’满足 （Y的一部分跑到闭包外面去了），但关系r上要求F能推导出的全部函数依赖都成立，所以X→Y在R<U, F>下的一个关系r上不成立，而r∈R<U, F>，所以X→Y不为R<U, F>所蕴涵。

13、如果G+ = F+，就说函数依赖集F覆盖G或G覆盖F（F是G的覆盖、G是F的覆盖）或F与G等价。可见，两个函数依赖集F和G的闭包等价，意味着已知F能推出的依赖，已知G也能推出，反之亦然。

14、F+ = G+的充分必要条件是： 。
证明 只证充分性，必要性显然。
（1）若 则 。
（2）任取X→Y∈F+，则 。所以X→Y∈(G+)+ = G+（G+推出来的依赖肯定也能从G开始一步一步推出来）。所以 。
（3）同理 。

15、如果函数依赖集F满足下列条件，就称F为一个极小函数依赖集，又称最小依赖集或最小覆盖（minimal cover）：
（1）F中任一函数依赖的→后只有一个属性。
（2）F中不存在函数依赖X→A，使F与F－{X→A}等价。也就是说，去掉已知条件X→A，还是跟没去掉一样能推出那么多依赖来。
（3）F中不存在函数依赖X→A，X有真子集Z使得(F－{X→A})∪{Z→A}与F等价。也就是说，在（2）的基础上只保留Z→A，还是跟不删减一样能推出那么多依赖来。

16、每一个函数依赖集F均有一个等价的极小函数依赖集Fm，此Fm称为F的最小依赖集。
证明 根据定义，可以直接得出：通过以下三步能构造出要求的Fm。
（1）检查F中的全部依赖Di：X→Y，若Y = A1∪A2∪……∪Ak，k≥2，那么用X→Aj，j = 1，2，……，k来取代X→Y。
（2）检查F中的全部依赖Di：X→A，设G = F－{X→A}，若A∈XG+，则去掉X→A。
（3）检查F中的全部依赖Di：X→A，设X = B1∪B2∪……∪Bm，m≥2，逐一考察Bi，i = 1，2，……，m，若A∈(X－Bi)F+，就用X－Bi代替X。
最后剩下的F就是极小依赖集，而且与原来的F等价。F的最小依赖集不是唯一的，与对各个函数依赖以及X→A中X包含的各个属性的处理顺序有关。