第三节 数据依赖的公理系统           （1） （2） （3）
    逻辑蕴含定义：对于满足一组函数依赖 F 的关系模式R <U，F>，其任何一个关系r，若函数依赖X→Y都
成立, 则称F 逻辑蕴含 X →Y。Armstrong公理系统，一套推理规则，是模式分解算法的理论基础，用途：
求给定关系模式的码；从一组函数依赖求得蕴含的函数依赖。
    1. Armstrong公理系统，对于关系模式 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 所蕴含。
    由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。
    自反律: 若Y∈X∈U, 则 X →Y 为 F 所蕴含。
    证: 对R <U,F> 的任一关系 r 中的任意两个元组 t,s：若 t[X]=s[X]，由于Y→X，有t[y]=s[y]，因此，X→Y成立。
    增广律: 若 X→Y 为 F 所蕴含, 且Z∈U, 则 XZ→YZ 为 F 所蕴含。
    证：设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 所蕴含。
    传递律：若X→Y及Y→Z为F所蕴含，则 X→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 所蕴含。
    2. 导出规则，根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：
    合并规则：由X→Y，X→Z，有X→YZ。（A2， A3）；
    伪传递规则：由X→Y，WY→Z，有XW→Z。（A2， A3）；
    分解规则：由X→Y 及 Z∈Y，有X→Z。（A1， A3）。
    根据合并规则和分解规则，可得引理5.1。引理5.l X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l，
2，…，k）。
    3. 函数依赖闭包定义，在关系模式R<U,F>中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。
    定义：设F为属性集U上的一组函数依赖，X∈U, XF+ = { A | X→A能由 F 根据Armstrong公理导出}，
XF+称为属性集X关于函数依赖集F 的闭包。
    例：R(X, Y), F = {X?Y}
        F+ = { X→Φ, X→X, X→Y, X→XY, Y→Φ, Y→Y, XY→Φ, XY→X, XY→Y, XY→XY }
    F+计算是NP完全问题。关于闭包的引理：
    引理 设F为属性集U上的一组函数依赖，X,Y∈U，X→Y 能由F 根据Armstrong公理导出的充分必要条件
是Y∈XF+。用途：将判定X→Y是否能由F根据Armstrong公理导出的问题，转化为求XF+ ，判定Y是否为XF+子
集的问题。