数据依赖的公理系统
数据依赖的公理系统是模式分解算法的理论基础。下面首先讨论函数依赖的一个有效而完备的公理系统——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|次循环就会终止。
