通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

数据库系统概论高级 6-7 关系数据理论 函数依赖的公理系统

269人浏览 / 0人评论 / | 作者:因情语写  | 分类: 数据库系统概论  | 标签: 数据库系统概论

作者:因情语写

链接:https://www.qingyu.blue/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. 最小依赖集

    思考题


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

点赞(0) 打赏

全部评论

还没有评论!