精华内容
下载资源
问答
  • 数据库函数闭包练习题
    2022-01-15 18:41:06

    1.已知关系模式R<U,F>,U={ A,B,C,D,E } ,F={AB→C,B→D, C→E,EC→B,AC→B },求(AB)+F

    解:
    设X(0)=AB
    计算X(1),因为AB→C,B→D,所以X(1)=ABUCD=ABCD,因为X(1)≠X(0)
    计算X(2),因为C→E,AC→B,所以X(2)=ABCDUBE=ABCDE,因为X(2)=U
    所以,(AB)+F= ABCDE

    2.已知关系模式R<U,F>,U={ A,B,C,D } ,F={ A→C,C→A, B→AC,D→AC }求(AD)+F

    解:
    设X(0)=AD
    计算X(1),因为A→C,D→AC,所以X(1)=ADUC=ACD,因为X(1)≠X(0)
    计算X(2),因为C→A,所以X(2)=ACDUA=ACD,因为X(2)=X(1)
    所以,(AD)+F= ACD

    步骤: 例如:已知关系模式R<U,F>,求(AB)+F

    • step1. 设X(0)=AB
    • step2. 计算X(1),比较X(1)与X(0)是否相等,X(1)与U是否相等,如果不相等,求X(2)
    • step3. 计算X(2),比较X(2)与X(1)是否相等,X(2)与U是否相等,如果不相等,求X(3)
    • ……
    • step4. 当X(n)=X(n-1)或者X(n)=U时,求得(AB)+F=X(n)
    更多相关内容
  • 数据库函数依赖闭包的求法

    万次阅读 多人点赞 2014-04-03 20:25:19
    函数依赖闭包 定义:若F为关系模式R(U)的函数依赖集,我们把F以及所有被F逻辑蕴涵的函数依赖的集合称为F的闭包,记为F+。 即:F+={X→Y|X→Y∈F∨“应用Armstong公理从F中导出的任何X→Y”} △ F包含于F+...

    函数依赖的闭包


    定义:若F为关系模式R(U)的函数依赖集,我们把F以及所有被F逻辑蕴涵的函数依赖的集合称为F的闭包,记为F+。
    即:F+={X→Y|X→Y∈F∨“应用Armstong公理从F中导出的任何X→Y”}

    △ F包含于F+,如果F=F+,则F为函数依赖的一个完备集。
    △ 规定:若X为U的子集,X→Φ 属于F+。

    关系模式R<U,F>若有n个属性,则在模式R上可能成立的函数依赖有4n个,其中n个属性中组合成X有2n个,组合成Y有2n个。

    例:已知关系模式R(ABC),F={A→C,B→C},求F+

    解:∵U={A,B,C},左部不同的属性集组合有23=8种:

    Φ、A、B、C、AB、BC、AC、ABC。

    (1)∴Φ→Φ

    (2)∵(A)F+=AC

    ∴A→Φ、A→A、A→C、A→AC。

    (3)∵(B)F+=BC

    ∴B→Φ、B→B、B→C、B→BC。

    (4)∵(C)F+=C

    ∴C→Φ、C→C。

    (5)∵(AB)F+=ABC

    ∴AB→Φ、AB→AB 、AB→A、AB→B 、AB→C、AB→BC 、AB→AC、AB→ABC 。

    (6)∵(BC)F+=BC

    ∴BC→Φ、BC→BC、BC→B、BC→C。

    (7)∵(AC)F+=BC

    ∴AC→Φ、AC→BC、AC→B、AC→C。

    (8)∵(ABC)F+=ABC

    ∴ABC→Φ、ABC→ABC 、ABC→A、ABC→B 、ABC→C、ABC→BC 、ABC→AB、ABC→AC。

    所以F+共有35个具体如下:

    ∴Φ→Φ、A→∅、A→A、A→C、A→AC

    B→Φ、B→B、B→C、B→BC

    C→Φ、C→C、 AB→∅、AB→AB 、AB→A、AB→B 、AB→C、AB→BC 、AB→AC、AB→ABC 、

    BC→Φ、BC→BC、BC→B、BC→C、

    AC→Φ、AC→BC、AC→B、AC→C、

    ABC→Φ、ABC→ABC 、ABC→A、ABC→B 、ABC→C、ABC→BC 、ABC→AB、ABC→AC

    展开全文
  • 数据库函数依赖、属性集的闭包、覆盖、模式分解、范式、3NF的分解、BCNF的分解

    Functional Dependency 函数依赖

    1. K 是关系模式R 的超码 当且仅当 K ->R
    2. K 是关系模式R 的候选码 当且仅当
      K -> R, 并且
      不存在 a属于 K, a-> R
    • 函数依赖集:若干个函数依赖组成的集合
    • 如果一个关系 r 没有违反函数依赖集 F, 那么称
      关系 r 满足函数依赖集 F ( r satisfies F )
    • 如果关系模式 R 的所有关系都满足函数依赖集 F, 那么称
      函数依赖集F 在关系模式 R 上成立 ( F holds on R )

    Closure of Attribute Sets 属性集的闭包

    根据一个给定的函数依赖集 F,由属性集 a 可推出的所有属性组成的集合,称为 a 的闭包,记为 a+

    计算属性集的闭包

    属性集闭包的用途:

    • 判断一个属性集是否超码

      要判断 a 是不是 R 的超码,只要看 a+ 是不是包含 R

    • 判断一个函数依赖是否成立

      要判断 a->b 是不是成立,只要看b属于a+ 是不是成立

    Canonical Cover 最小覆盖/规范覆盖

    把函数依赖集 F 中多余的函数依赖和多余的属性删除,得到“最小的”函数依赖集合,称为 F 的最小覆盖或规范覆盖

    1. 函数依赖集中的某些函数依赖是多余的

      例如. {A ->B, B -> C, A ->C} 可以简化为等价的函数依赖集合

      {A ->B, B -> C}

    2. 函数依赖中的某些属性是多余的

      例如. {A ->B, B ->C, A ->CD} 可以简化为等价的函数依赖集合

      {A ->B, B ->C, A -> D}

      例如. {A ->B, B ->C, AC ->D} 可以简化为等价的函数依赖集合

      {A -> B, B ->C, A -> D}

    Decomposition(模式分解)

    Lossless Decomposition 无损分解

    Closure of a Set of Functional Dependencies函数依赖集的闭包

    由函数依赖集 F 可推断出的所有函数依赖所组成的集合,叫做 F 的闭包,记为 F+

    F+ 是 F 的超集

    Dependency Preservation(保持函数依赖)

    1. 分解关系模式 R 后, 得到关系模式 R1, R2,…,Rn

    2. 把 F+ 中只包含 R1 属性的函数依赖子集合记为 F1

    3. 把 F+ 中只包含 R2 属性的函数依赖子集合记为 F2

      如此类推

    4. 把 F+ 中只包含 Rn 属性的函数依赖子集合记为 Fn

    保持函数依赖. 如果
    F1 并 F2 并 … 并 Fn 和 F 是等价的
    那么称这个分解是保持函数依赖的(dependency preserving)

    Normal Forms(范式)

    范式是关系的集合

    1NF (First Normal Form,第1范式)

    如果一个关系模式R的所有属性域都是原子域,那么R属于第一范式

    以下哪些域是原子域?
    食品 = { 可乐,薯条,鸡翅,面条,饺子,汤,…… }
    套餐 = { (可乐,薯条,鸡翅),(面条,饺子,汤),……}
    车票 = { D7727次02车20A号,D7712次08车04A号,…… }
    车次 = { D7727次,D7712次,…… }
    车厢 = { 02车,08车,…… }
    座位 = { 20A号,04A号,…… }
    答案
    食品,车次,车厢,座位

    3NF (Third Normal Form)

    BCNF (Boyce-Codd Normal Form)

    BCNF定义. 如果 F+ 里面的所有非平凡函数依赖 a->b的 a 都是 R 的超码,那么 R 属于 BCNF
    实际上,只需要检查 F 的函数依赖,不需要检查 F+ 的全部函数依赖
    Example. 以下关系模式不属于 BCNF:
    instr_dept (ID, name, salary, dept_name, building, budget )
    因为存在非平凡函数依赖 dept_name-> building, budget
    但是 dept_name 不是超码

    3NF vs BCNF

    1. Redundancy 冗余

      BCNF 能消除用函数依赖发现的冗余

      3NF 还有一些冗余

    2. Dependency-preserving decomposition 保持函数依赖分解

      所有关系模式都有保持函数依赖的 3NF 分解

      有一些关系模式,它们的 BCNF 分解不能保持函数依赖

    Decomposition Algorithms(分解算法)

    3NF 分解算法

    以下 3NF 分解算法是保持函数依赖的:

    1. 先求出 F 的最小覆盖 Fc

    2. 为 Fc 的每个函数依赖 a->b 生成一个新的关系模式 a U b

    3. 如果生成的每一个关系模式都不包含 R 的候选码,

      ​ 就选择 R 的任意一个候选码 A,生成一个新的关系模式 A

    4. 检查生成的关系模式,如果有 R1 属于 R2,就把 R1 删掉

    分解以下关系模式:
    cust_banker_branch = (customer_id, employee_id, branch_name, type )
    函数依赖集:
    customer_id, employee_id -> branch_name, type
    employee_id -> branch_name
    customer_id, branch_name -> employee_id
    首先计算最小覆盖 Fc

    1. 第一个函数依赖中的 branch_name 是多余的

    FC = { customer_id, employee_id -> type

    ​ employee_id -> branch_name

    ​ customer_id, branch_name -> employee_id }

    为每个函数依赖生成一个关系模式:
    (customer_id, employee_id, type )
    (employee_id, branch_name)
    (customer_id, branch_name, employee_id)
    (customer_id, employee_id, type ) 已经包含了原关系模式的候选码, 所以不用为候选码生成新的关系模式
    第二个关系模式是第三个关系模式的子集,可以删掉
    最终得到的分解:
    (customer_id, employee_id, type)
    (customer_id, branch_name, employee_id)

    BCNF 分解算法

    假设关系模式 R 有一个非平凡函数依赖 a->b (且a并b = 空 ),a不是超码
    我们可以把 R 分解为以下两个关系模式
    a U b 和 R – b
    如果分解后的两个关系模式还不是BCNF, 就继续分解下去
    注意:要判断分解后得到的关系模式 Ri 是否属于 BCNF时, 要用函数依赖集Fi ,而不是用函数依赖集 F

    例如:
    R = (A, B, C, D, E)
    F = { A-> B, BC-> D}
    考虑 A -> B,A 不是超码,所以把 R 分解为
    R1 = (A,B)
    R2 = (A,C,D,E)
    F 的函数依赖,都不是仅包含 (A,C,D,E)
    所以不能根据 F 来判断 R2 是否属于BCNF
    实际上, F+ 中的 AC-> D 使得 R2 不属于 BCNF
    所以还要继续对 R2 进行分解

    展开全文
  • 4) 计算函数依赖闭包。此步骤不作要求,但要会方法。个人总结:将所有属性元素组成一个集合(域)记为R;求R的所有子集(要用到第二步中的全排列~~~),设其中一个为Ri;对每一个子集求其闭包,记为Ri+;然后求Ri...
  • 函数依赖(Function Dependency,FD): 数学形式的定义就不说了,有一个等价的定义可以仔细体会一下: (FD的等价定义) 对X中的任一值x, 的值仅有一个元组,则有X→Y。 注意基本单位是关系中的属性,即列与列...
  • 1. 由用户输入函数依赖,当用户输入End时,表示所有依赖都输入完毕。(即函数依赖是由用户自己定的,程序中不能假定某个具体的依赖)。 2. 函数依赖的形式是ABC, ABE这样的形式,为了简单起见,我们假定所有的属性...
  • 前提概念须知 候选码(或候选键)∶属性或属性组合,其值能够唯一地标识一个元组。 主码(或主键):在一个关系中可能有多个候选码,从中选择一个作为主码。 主属性:包含在任何候选码中的属性称为主属性,不...函数依赖
  • 1、最小函数依赖集 2、闭包 3、候选键 一、求最小函数依赖集 步骤: 1、先将右边都变成单属性 2、依赖集中不能出现冗余的函数依赖(重复的函数依赖) 3、左边没有多余的属性 举个例子: 1.首先将右边都变成单属性,...
  • 一、函数依赖 定义:设R(U)R(U)R(U)是属性集合U={A1,A2,...,An}U = \{A_1, A_2, ..., A_n\}U={A1​,A2​,...,An​}上的一个关系模式,X,YX, YX,Y是UUU上的两个子集,若对R(U)R(U)R(U)的任意一个可能得关系rrr,rrr...
  • 函数依赖: 字母表示:FD(Functional Dependency,FD) 定义:R(U),X、Y为属性集,t1、t2为元组,若t1[X]=t2[X],则t1[Y]=t2[Y],称X函数决定Y函数或Y依赖于X,记作X→Y。 例3-22 对实例3-21“学生选课”关系...
  • 数据库函数依赖判断

    千次阅读 2020-11-11 13:02:27
    数据库函数依赖判断例题 1.前言 因为在复习国科大数据库新技术课程,找遍全网也没有找到对函数依赖判定的实例化讲解。于是决定自己写一个给大家参考。第一篇csdn博客,写的不好,敬请见谅。 2.例题 问:已知R<U,F...
  • 函数依赖闭包生成

    2018-12-08 00:09:32
    实现: 查询每次都是扫面前面的所有函数依赖,直到一次循环下来闭包不再更新。 使用细节:二进制枚举子集,for(int i = s; i; i = (i-1)&amp;amp;s) #include &amp;lt;cstdio&amp;gt; #include &...
  • 数据库 函数依赖

    2020-05-03 18:21:45
    用处:指导关系模型的设计,规范...函数依赖(FD) 单值映射 码是一种特殊的FD: 比如超码:可以唯一标识一个元组(SK -> R) 候选码(最小超码):CK -> R 且 不存在CK的子集可以 -> R FD的作用:可以检测...
  • 1.求闭包 推理规则推导 2. 求最小依赖集 具体步骤 1.右边单一化 2.除去自身求闭包 3.左部最小化 练习1: ...3.无损分解及保持函数依赖 无损分解两个方法: 1.表格法 2.适用于分解为2个ρ ...
  • 数据库中的闭包到底是什么?

    千次阅读 2020-05-12 15:29:07
    书上说的闭包到底是什么东西呢? 原来就是F中能所有的函数依赖以及能推导出来的所有的函数依赖在一起的集合就是F的闭包
  • 一、函数依赖1. 函数依赖定义:设 R(U) 是属性集合 U={ A1, A2, ... , An } 上的一个关系模式,X, Y 是 U 上的两个子集,若对 R(U) 的任意一个可能的关系 r ,r 中不可能有两个元组满足在 X 中的属性值相等而在 Y 中...
  • 数据库关系模式中函数依赖的理论涉及不少算法,此次根据课程需要将求属性闭包(closure)和函数最小依赖集(basis)用代码实现。 思路 两个算法已有理论支撑,因此第一步是设计合适的数据结构,存储算法过程需要的...
  • 一、函数依赖:在关系R中,若属性或者属性集 A 中 两个元祖的值相等,如果这两个元祖中对应的属性或者属性集B中的值也相同,则记作A——>B。 A函数决定B; 或者 B函数依赖于A。例1:...
  • 一、函数依赖:在关系R中,若属性或者属性集 A 中 两个元祖的值相等,如果这两个元祖中对应的属性或者属性集B中的值也相同,则记作A——&gt;B。 A函数决定B; 或者 B函数依赖于A。例1:下表就是问题领域, 则存在...
  • 一文搞懂数据库函数依赖及其Armstrong公理和引理

    千次阅读 多人点赞 2021-01-11 14:20:32
    闭包二、函数依赖的 Armstrong 公理及其引理1. 函数依赖的 Armstrong 公理(1). 自反律(2). 增广律(3). 传递律2. 函数依赖的 Armstrong 的引理2.1 引理1(1). 合并律(2). 伪传递律(3). 分解律2.2 引理22.3 属性(集)...
  • 数据库】—闭包

    万次阅读 多人点赞 2016-09-22 17:46:11
    由于函数依赖是用命题形式定义的,因此函数依赖黄子健存在着逻辑蕴涵的关系。比如A决定 B(也可以用由A指向B的箭头表示)和B决定C在关系模式R中成立,那么A决定C在R中是否成立?这个问题就是FD之间的逻辑蕴涵问题,...
  • 数据库闭包(例子)

    2021-12-25 14:17:32
    数据库闭包求法(例子)
  • 数据库老师布置的作业题目,求属性集闭包函数依赖闭包的算法实现 我用比较简单的方法算了一下 欢迎交流 import java.util.*; public class QiuBiBao_DBtext { public static void main(String[] ...
  • 数据库(笔记)——函数依赖

    千次阅读 多人点赞 2020-08-15 10:01:01
    函数依赖函数依赖的定义函数依赖的逻辑蕴涵逻辑蕴涵闭包函数依赖的推导规则完全函数依赖与部分函数依赖完全函数依赖部分函数依赖传递函数依赖候选键在函数依赖中的定义总结 函数依赖的定义 定义 函数依赖是关系模式...
  • 前言 一个设计良好的数据库模式(database schema),应该要具备以下特点: 完整性(Completeness) 减少冗余(Redundancy freeness) 一致的含义(Consistent understanding) ...为什么需要函数依赖...
  • 数据库闭包,最小函数依赖

    万次阅读 多人点赞 2018-07-08 19:56:16
     例(1): 设有关系模式R(U,F),其中U={A,B,C,D,E,I},F={A→D,AB→E,BI→E,CD→I,E→C},计算(AE)+ 解: (1) 令X={AE},X(0)=AE (2)在F中寻找尚未使用过的左边是AE的子集的函数依赖,结果是: A→D, ...
  • 不含多与依赖,即去掉某一函数依赖后形成的集合B和原来的集合A是等价的,在说白点,B可以退出去掉的函数依赖 不含部分依赖,像F{AB—>C,A—>C}就不是最小函数依赖集 已知关系模式R(U,F),其中U={A,B,C},F...
  • eg:考虑属性A,B,C,D,E,F的关系,假设此关系有函数依赖:AB -> C, BC -> AD, D -> E, CF -> B, 那么{A, B}的闭包{A, B}+为? 步骤:BC -> AD 分解为 BC -> A 和 BC -> D,从X = {A, B}出发,AB -> C,把C加入X...
  • 函数依赖:核心,是模式分解和设计的基础 范式:模式分解的标准 模式设计 二、不合理的关系模式存在的异常问题 异常种类 数据冗余 插入异常 删除异常 更新异常 根本原因:属性间存在着数据依赖的关系。 解决方法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,305
精华内容 4,522
关键字:

数据库函数依赖的闭包