数据库第四章2.pptVIP

4.4 函数依赖的公理系统 4.4.1 函数依赖的逻辑蕴涵 4.4.2 Armstrong公理系统 4.4.3 函数依赖集的等价和覆盖 4.4.4 函数依赖集的最小集 4.4.1 函数依赖的逻辑蕴涵 一、逻辑蕴涵的定义 研究的问题：对于给定的一组函数依赖，要判断另外的一些函数依赖是否成立？ 例如：对关系模式R(A，B，C)。已知A→B，B→C，判断A→C是否成立？ 这就是函数依赖的逻辑蕴涵所要研究的内容。 定义4.1：设F是关系模式R的一个函数依赖集，X，Y是R的属性子集。如果从F中的函数依赖能够推导出X→Y，则称F逻辑蕴涵X→Y，或X→Y是F的逻辑蕴涵。 4.4.1 函数依赖的逻辑蕴涵 二、F的闭包F+ 定义4.2：所有被F逻辑蕴含的函数依赖的集合称为F的闭包（Closure），记为F+。 即：F+是所有能从F中推导出来的函数依赖的集合。 通常，F?F+，若F=F+，则称F是函数依赖的完备集。 说明：F+的计算相当麻烦。即使F不大，但F+可能很大。 4.4.1 函数依赖的逻辑蕴涵 例：若有关系模式R(X，Y)，它的函数依赖集F={X→Y}，则F的闭包为： F+ = { X→?， Y→?， XY→?， X→X， Y→Y，XY→X，  X→Y， XY→Y，  X→XY， XY→XY } 上述函数依赖中，很多是意义不大的，如X→?，X→X等，但借此可以了解F+的全貌。 4.4.1 函数依赖的逻辑蕴涵 三、关系的码 定义4.3：设有关系模式 R(A1,A2,…,An)，F是它的函数依赖集，X是{A1,A2,…,An}的一个子集。如果 (1)X→A1A2…An∈F+，且  (2)不存在X的真子集Y，使得Y→A1A2…An成立，且Y→A1A2…An∈F+。 则称X是R的一个候选码。 上述条件(1)表示X能唯一决定一个元组，条件(2)表示X是能满足(1)而又无多余的属性集。 4.4.2 Armstrong公理系统 为了确定码和函数依赖的逻辑蕴涵，需要从F中的函数依赖出发，推出F+中的所有函数依赖，或者对于给定的F和X，Y，判断X→Y是否在F+中，为此，要求有一套正确和完备的推理规则。 1974年，W.W.Armstrong总结了各种推理规则，将其中最主要、最基本的作为公理，形成了最著名的Armstrong公理系统──简称阿氏公理。 公理系统是模式分解算法的理论基础。 4.4.2 Armstrong公理系统 一、Armstrong公理 设有关系模式R(U，F)，U={A1, A2, …, An}为属性全集，F是R的函数依赖集，X，Y，Z ? U。则有： 自反律(Reflexivity)：若Y ? X，则X→Y。 增广律(Augmentation)：若X→Y，Z ? U，则XZ→YZ。 传递律(Transitivity)：若X→Y，Y→Z，则X→Z。 4.4.2 Armstrong公理系统 4.4.2 Armstrong公理系统 (2) 增广律：若X→Y，Z ? U，则XZ→YZ。 证明：设r是R的任意一个关系，s，t是r的任意两个元组。已知：X→Y，Z ? U又设s[XZ]=t[XZ]则有s[X]=t[X]，且s[Z]=t[Z] ∵ X→Y，根据函数依赖定义，有s[Y]=t[Y] ∴ s[Y]s[Z]=t[Y]t[Z]，即s[YZ]=t[YZ] 故在s[XZ]=t[XZ]的条件下，推出了s[YZ]=t[YZ]由函数依赖的定义，有XZ→YZ。 4.4.2 Armstrong公理系统 (3) 传递律：X→Y，Y→Z，则X→Z。 证明：设r是R的任意一个关系，s，t是r的任意两个元组。 若s[X]=t[X]，由X→Y，有s[Y]=t[Y] 再由Y→Z，有s[Z]=t[Z] ∴ 由s[X]=t[X]能导出s[Z]=t[Z] 根据函数依赖的定义有：X→Z。 4.4.2 Armstrong公理系统 三、Armstrong公理的推论 合成规则：若X→Y，X→Z，则X→YZ。 分解规则：若X→YZ，则X→Y，X→Z。 伪传递规则：若X→Y，YW→Z，则XW→Z。 4.4.2 Armstrong公理系统 四、Armstrong公理的推论正确性 定理4.2：Armstrong公理的三个推论是正确的。 证明： (1) 合成规则（若X→Y，X→Z，则X→YZ） ∵X→Y 由增广律得：XX→XY，即X→XY ∵X→Z