作者：whisper

链接：http://proprogrammar.com:443/article/580

声明：请尊重原作者的劳动，如需转载请注明出处

    1. Armstrong公理系统
    2. 导出规则
    3. 函数依赖闭包F +
    4. 求属性集X（X ⊆ U）关于F的闭包XF+
    5. Armstrong公理系统的有效性与完备性
    6. 函数依赖集等价的概念
    7. 最小依赖集或最小覆盖

    数据依赖的公理系统是模式分解算法的理论基础。
    函数依赖的一个有效而完备的公理系统——Armstrong公理系统，一套推理规则，是模式分解算法的理论基础。

    已知： R<U, F>, U={X,C,W,Y, Z, }， F={X→YZ, Z→CW}
    问： X→CWYZ是否为F逻辑蕴含

    用途

• 从一组函数依赖求得蕴含的函数依赖。 例如问X →Y是否被F所蕴含。
• 求给定关系模式的码。

    逻辑蕴含
    定义6.11 对于满足一组函数依赖F的关系模式R <U， F>，其任何一个关系r，若函数依赖X→Y都成立（即r中任意两元组t， s，若t [X]=s [X]，则 t [Y ] = s[Y]），则称F逻辑蕴含X →Y。

    1. Armstrong公理系统

    Armstrong公理系统
    设U为属性集总体， F是U上的一组函数依赖， 于是有关系模式R <U， F >。对R <U， F> 来说有以下的推理规则：

• Al. 自反律(Reflexivity)：若Y ⊆ X ⊆ U，则X →Y为F所蕴含。
• A2. 增广律(Augmentation)：若X→Y为F所蕴含，且Z ⊆ U，则XZ→YZ为F所蕴含。
• A3. 传递律(Transitivity)：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。

    定理6.l Armstrong推理规则是正确的（证明参见《数据库系统概论P.190~P.191》 ）

    2. 导出规则

    1.根据A1， A2， A3这三条推理规则可以得到下面三条推理规则：

• 合并规则：由X→Y， X→Z，有X→YZ。

    （A2， A3） X→Y X ， XY →ZY

• 伪传递规则：由X→Y， WY→Z，有XW→Z。

    （A2， A3） XW→YW

• 分解规则：由X→Y及Z⊆Y，有X→Z。

    （A1， A3） Z⊆Y， Y→Z

    2.根据合并规则和分解规则，可得引理6.1
    引理6.l X→A1 A2…Ak成立的充分必要条件是 X→Ai 成立（i =l， 2， …， k）。

    3.函数依赖闭包

    4. 求属性集X 关于F的闭包

    求闭包的例子

    5.Armstrong公理系统的有效性与完备性

    有效性与完备性的含义

• 有效性：由F 出发根据Armstrong公理推导出来的每一个函数依赖一定在F +中
• 完备性： F +中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来

    定理6.2 Armstrong公理系统是有效的、 完备的。（证明参见《数据库系统概论P.192~P.193》 ）

    6. 函数依赖集等价的概念

    7. 最小依赖集

    例题

    R<U, F>， U=ABCD,
    函数依赖集 F = {A→BD， AB→C， C→D}。
    求： F最小函数依赖集
    解法步骤：

• 1.将F中的所有函数依赖的右边化为单一属性
• 2.去掉F中的所有函数依赖左边的冗余属性
• 3.去掉F中所有冗余的函数依赖

    例题图解（1）

    （1）将F中的所有函数依赖右边化为单一属性

    F={ , , , }

    2.去掉F中的所有函数依赖左边的冗余属性

    3.去掉F中所有冗余的函数依赖关系

    7. 最小依赖集

    思考题

亲爱的读者：有时间可以点赞评论一下