逻辑蕴含
定义5.11 对于满足一组函数依赖 F 的关系模式R <U，F>，其任何一个关系r，若函数依
赖X→Y都成立, 则称F逻辑蕴含X →Y。
一、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。
定理 5.l Armstrong推理规则是正确的
证明：
(1)自反律:若Y∈X∈U，则X →Y为F所蕴含
证: 设Y∈X∈U 对R <U，F>的任一关系r中的任意两个元组t，s：
若t[X]=s[X]，由于Y≤X，有t[y]=s[y]，
所以X→Y成立，自反律得证
(2)增广律: 若X→Y为F所蕴含，且Z∈U，则XZ→YZ 为F所蕴含。
证：设X→Y为F所蕴含，且Z∈U。设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所蕴含，增广律得证。
(3) 传递律：若X→Y及Y→Z为F所蕴含，则X→Z为 F所蕴含。
证：设X→Y及Y→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所蕴含，传递律得证。
二、导出规则
1.根据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）
2.根据合并规则和分解规则，可得引理5.1
引理5.l X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）。
三、函数依赖闭包
定义5.l2 在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包,记为F+。
定义5.13 设F为属性集U上的一组函数依赖，X≤U， XF+ ={ A|X→A能由F 根据
Armstrong公理导出}，XF+称为属性集X关于函数依赖集F 的闭包。
引理5.2 设F为属性集U上的一组函数依赖，X，Y≤U，X→Y能由F 根据Armstrong公理导
出的充分必要条件是Y≤XF+。
用途：将判定X→Y是否能由F根据Armstrong公理导出的问题， 就转化为求出XF+ ，判定
Y是否为XF+的子集的问题。
算法5.l 求属性集X（X≤U）关于U上的函数依赖集F 的闭包XF+
输入：X，F
输出：XF+
步骤：
（1）令X（0）=X，i=0
(2）求B，这里B = { A |(ヨV)(ヨW)(V→W∈F∧V≤X（i）∧A∈W)}；
（3）X（i+1）=B∪X（i）
（4）判断X（i+1）= X （i）吗?
（5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。
（6）若否，则 i=i+l，返回第（2）步。
对于算法5.l， 令ai =|X（i）|，{ai }形成一个步长大于1的严格增的序列，序列的上
界是 | U |，因此该算法最多|U| - |X| 次循环就会终止。
[例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；
(1)计算X（1）: 逐一的扫描F集合中各个函数依赖，找左部为A，B或AB的函数依赖。
得到两个：AB→C，B→D，于是X（1）=AB∪CD=ABCD。
(2)因为X（0）≠ X（1） ，所以再找出左部为ABCD子集的那些函数依赖，又得到
AB→C，B→D， C→E，AC→B，于是X（2）=X（1）∪BCDE=ABCDE。
(3)因为X（2）=U，算法终止，所以（AB）F+ =ABCDE。
四、Armstrong公理系统的有效性与完备性
有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中
/* Armstrong正确
完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来
/* Armstrong公理够用，完全
完备性：所有不能用Armstrong公理推导出来f, 都不为真。
若 f 不能用Armstrong公理推导出来， f∈ F+
有效性与完备性的证明（略）
Armstrong公理的完备性及有效性说明:
“蕴含” == “导出” 等价的概念；
F+ ==由F出发借助Armstrong公理导出的函数依赖的集合五、函数依赖集等价
定义5.14 如果G+=F+，就说函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖)或F与G等价。
引理5.3 F+ = G+ 的充分必要条件是F≤G+ ，和G≤F+
证: 必要性显然，只证充分性。
（1）若F≤G+ ，则XF+≤XG++ 。
（2）任取X→Y∈F+ 则有 Y≤XF+≤XG++ 。
所以X→Y∈(G+）+= G+。即F+≤G+。
（3）同理可证G+≤F+ ，所以F+ = G+。
六、最小依赖集
定义5.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依
赖集或最小覆盖。
(1) F中任一函数依赖的右部仅含有一个属性。
(2) F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。
(3) F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z→A}与F等价。
[例2] 对于5.l节中的关系模式S<U，F>，其中：U={ SNO，SDEPT，MN，CNAME，G }，
F={ SNO→SDEPT，SDEPT→MN，（SNO，CNAME）→G }
设F’={SNO→SDEPT，SNO→MN，SDEPT→MN，(SNO，CNAME)→G，(SNO，
SDEPT)→SDEPT}F是最小覆盖，而F ’不是。
因为：F ’-{SNO→MN}与F ’等价 F ’-{(SNO，SDEPT)→SDEPT}也与F ’等价
F ’-{(SNO，SDEPT)→SDEPT}∪{SNO→SDEPT}也与F ’等价
七、极小化过程
定理5.3 每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集
证:构造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集。
(1)逐一检查F中各函数依赖FDi：X→Y，
若Y=A1A2 …Ak，k >2，则用 { X→Aj |j=1，2，…， k} 来取代X→Y。
引理5.1保证了F变换前后的等价性。
(2)逐一检查F中各函数依赖FDi：X→A，
令G=F-{X→A}，若A≤XG+， 则从F中去掉此函数依赖。
由于F与G =F-{X→A}等价的充要条件是A≤XG+ 。因此F变换前后是等价的。
(3)逐一取出F中各函数依赖FDi：X→A，
设X=B1B2…Bm，逐一考查Bi （i=l，2，…，m），若A∈（X-Bi ）F+ ，则以X-Bi 取
代X。由于F与F-{X→A}∪{Z→A}等价的充要条件是A≤ZF+ ，其中Z=X-Bi。因此F变换
前后是等价的。
由定义，最后剩下的F就一定是极小依赖集。因为对F的每一次“改造”都保证了改造
前后的两个函数依赖集等价，因此剩下的F与原来的F等价。 证毕
定理5.3的证明过程 也是求F极小依赖集的过程
[例3] F = {A→B，B→A，B→C，A→C，C→A}
Fm1、Fm2都是F的最小依赖集：
Fm1= {A→B，B→C，C→A}
Fm2= {A→B，B→A，A→C，C→A}
F的最小依赖集Fm不一定是唯一的。
它与对各函数依赖FDi 及X→A中X各属性的处置顺序有关。
极小化过程( 定理5.3的证明 )也是检验F是否为极小依赖集的一个算法。若改造后的
F与原来的F相同，说明F本身就是一个最小依赖集。
在R<U，F>中可以用与F等价的依赖集G来取代F
原因：两个关系模式R1 <U，F>，R2<U，G>，如果F与G等价，那么R1的关系一定是R2的
关系。反过来，R2的关系也一定是R1的关系。
关系模式的分解
1．模式分解的等价标准
规范化过程中将一个关系模式分解为若干个关系模式，应该保证分解后产生的模式和原来的模式等价。常用的等价标准有要求：
● 分解是具有无损连接性的；
● 分解是保持函数依赖的；
● 分解既要具有无损连接又要保持函数依赖两种。
将一个关系模式R(U,F)分解为若干个关系模式R1(U1,F1),R2(U2,F2)…Rn(Un,Fn)（其中U＝U1 U2 … Un，R1为F在U1上的投影），这意味着相应的将存储在一个二维表r中的数据分散到若干个二维表r1,r2,…,rn中（其中r1是r在属性组U1上的投影）。我们当然希望这样的分解不丢失信息，也就是说，希望能够通过对关系r1,r2…rn的自然连接运算重新得到关系r中的所有信息。
事实上，将关系r投影为r1,r2,…,rn时并不会丢失信息，关键是对r1,r2,…,rn作自然连接可能会产生一些原来r中没有的元组，从而无法区别那些元组是r中原来有的，即数据库中应该存在的数据，在这个意义上丢失了信息。
例如：设关系模式S(SNO,CLASSNO,DEPTNO)在某一时刻的关系r如下表5-14
表5-14
SNO CLASSNO DEPTNO
S1 C1 D1
S2 C2 D2
S3 C2 D2
S4 C3 D1
若按分解方案一将关系模式S分解为：
S11(SNO,DEPTNO)和
S12(CLASSNO,DEPTNO)，
则将r投影到S11和S12的属性上，得到关系r11如表5-15，r12如表5-16。
表5-15
SNO DEPTNO
S1 D1
S2 D2
S3 D2
S4 D1
表5-16
CLASSNO DEPTNO
C1 D1
C2 D2
C3 D1
对分解后的两个关系作自然连接r11*r12，得到r'如表5-17如下：
表5-17
SNO CLASSNO DEPTNO
S1 C1 D1
S1 C3 D1
S2 C2 D2
S3 C2 D2
S4 C1 D1
S4 C3 D1
r'中的元组S1C3D1和S4C1D1都不是原来r中的元组。就是说，我们无法知道原来r中到底有哪些元组，这是我们不希望的。
定义1：设关系模式R(U,F)分解为关系模式R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)，若对于R的任何一个可能的关系r，都有r=r1*r2…*rn，即r在R1,R2,…,Rn上的投影的自然连接等于r，则称关系模式R的这个分解是具有无损连接性的。
分解1不具有无损连接性，这是一个不好的分解方案。
在将一个关系模式分解为三个或者更多个关系模式的情况下，要判别分解是否具有无损连接性需要比较复杂的算法。然而若将一个关系模式分解为两个关系模式，则很容易判别分解是否具有无损连接性。
关系模式R(U,F)分解为关系模式R1(U1,F1),R2(U2,F2)是具有无损连接性的分解的充分必要条件是（U1∩U2→U1-U2）∈F+，或者（U2∩U1→U2-U1）∈F+。
让我们再考察第二种分解方案，将关系模式S分解为：
S21(SNO,CLASSNO)，
S22(SNO,DEPTNO)
由于U1∩U2＝SNO，U1-U2=CLASSNO，显然U1 U2→U1-U2，所以分解2具有无损连接性。然而分解2也不是一个很好的分解方案，将前面例子的关系r投影到S21,S22的属性上，得到关系r21如表5-18和r22如表5-19：
表5-18
SNO CLASSNO
S1 C1
S2 C2
S3 C2
S4 C3
表5-19
SNO DEPTNO
S1 D1
S2 D2
S3 D2
S4 D1
在这种分解中，假设学生S3从C2班转到C3班，于是我们需要在r21中将元组S3C2修改为S3C3，同时在r22中将元组S3D2修改为S3D1。如果这两个修改没有同时完成，数据库中就会存在不一致信息。这是因为分解得到的两个关系模式不是互相独立造成的。F中的函数依赖CLASSNO→DEPTNO既没有投影到关系模式R22中，而是跨在两个关系模式上。函数依赖是数据库中的完整性约束条件。在r中，若两个元组的X值相等，则Y值也必须相等。现在r的一个元组中的X值和Y值跨在两个不同的关系中，为维护数据库的一致性，在一个关系中修改X值时就需要相应的在另外一个关系中修改Y值，这当然是很麻烦而且是容易出错的，于是我们要求模式分解保持函数依赖这条等价标准。
定义2：设关系模式R(U,F)分解为关系模式R1(U1,F1)，R2(U2,F2)，…，Rn(Un,Fn)，若F=(F1F2…Fn) ，即F所逻辑蕴含的函数依赖一定也由分解得到的各个关系式中的函数依赖所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的。
分解方案二不是保持函数依赖的，因为分解得到的关系模式中只有函数依赖SNO→CLASSNO，丢失了函数依赖CLASSNO→DEPTNO。不是一个好的分解。
分解方案三是保持函数依赖的。
《数据库原理及应用》
第1章 绪论
1.1 数据管理技术的发展
1.1.1 人工管理阶段
1.1.2 文件系统阶段
1.1.3 数据库管理阶段
1.2 数据库系统结构
1.2.1 三级模式结构
1.2.2 数据库系统的二级独立性
1.2.3 数据库系统的二级映像
1.3 数据库、数据库管理系统和数据库系统
1.3.1 数据库
1.3.2 数据库管理系统
1.3.3 数据库系统
1.4 数据库技术的发展
小结
习题
第2章 数据模型
2.1 数据模型的概念
2.1.1 数据的三个范畴
.2.1.2 数据模型的组成要素及分类
2.2 e-r模型
2.2.1 基本概念
2.2.2 e-r图设计
2.3 面向对象模型
2.3.1 对象建模的基本知识
2.3.2 类图
小结
习题
第3章 关系数据库
3.1 关系数据模型
3.1.1 关系数据模型概述
3.1.2 基本术语
3.1.3 关系的性质
3.2 关系的完整性
3.3 关系代数
3.3.1 传统的集合运算
3.3.2 专门的关系运算
3.3.3 关系代数运算的应用实例
3.3.4 关系代数的扩充 *** 作
小结
习题
第4章 结构化查询语言sql
4.1 sql概述
4.1.1 sql语言的发展
4.1.2 sql语言的特点
4.1.3 sql语言的基本概念
4.2 数据定义语句
4.2.1 基本表的定义
4.2.2 基本表的修改与删除
4.2.3 基本表的删除
4.3 查询
4.3.1 单表查询
4.3.2 连接查询
4.3.3 嵌套查询
4.3.4 集合查询
4.4 数据 *** 纵
4.4.1 插入数据
4.4.2 修改数据
4.4.3 删除数据
4.5 视图
4.5.1 视图的定义与删除
4.5.2 查询视图
4.5.3 更新视图
4.5.4 视图的作用
小结
习题
第5章 存储过程、触发器和数据完整性
5.1 sql server编程结构
5.1.1 变量
5.1.2 显示信息
5.1.3 注释语句
5.1.4 批处理
5.1.5 流程控制语句
5.2 存储过程
5.2.1 存储过程的基本概念
5.2.2 创建存储过程
5.2.3 使用sql server管理控制台执行存储过程
5.2.4 修改和删除存储过程
5.3 触发器
5.3.1 触发器的基本概念
5.3.2 创建触发器
5.3.3 修改和删除触发器
5.4数据库完整性
5.4.1 约束
5.4.2 默认值
5.4.3 规则
5.4.4 用户定义的数据完整性
小结
习题
第6章 关系数据库设计理论
6.1 问题的提出
6.2 基本概念
6.2.1 函数依赖
6.2.2 码
6.3 规范化
6.3.1 第一范式
6.3.2第二范式
6.3.3 第三范式
6.3.4 bc范式
6.3.5 多值依赖与第四范式
6.3.6 关系模式规范化
6.4 函数依赖的公理系统
6.4.1 armstrong公理系统
6.4.2 闭包
6.4.3 函数依赖集的等到价和最小化
6.5 模式分解
6.5.1 模式分解的准则
6.5.2 分解的函数依赖保持性和无损连接性
6.5.3 模式分解的算法
小结
习题
第7章 索引
7.1 索引的概念
7.1.1 聚集索引
7.1.2 非聚集索引
7.1.3 唯一索引
7.1.4 何时应该创建索引
7.1.5 系统如何访问表中的数据
7.2 sql server 2005中的索引
7.2.1 索引的结构
7.2.2 管理索引
小结
习题
第8章 数据库设计
8.1 数据库设计概述
8.2 数据库设计的过程
8.2.1 数据库设计的步骤
8.2.2 需求分析阶段
8.2.3 概念设计阶段
8.2.4 逻辑设计阶段
8.2.5 物理设计阶段
8.2.6 数据库实现阶段
8.2.7 数据库的运行与维护阶段
8.3 数据库设计实例：电网设备抢修物资管理数据库设计
8.3.1 需求分析
8.3.2 概念模型
8.3.3 逻辑模型
小结
习题
第9章 数据库安全
9.1 安全性概述
9.1.1 用户标识与鉴别
9.1.2 存取控制
9.1.3 自主存取控制方法
9.1.4 强制存取控制方法
9.1.5 视图机制
9.1.6 审计
9.1.7 数据加密
9.2 sql server的安全性
9.2.1 sql server 2005的身份验证模式
9.2.2 sql server 2005的安全机制
9.3 用户管理和角色管理
9.3.1 登录用户和数据库用户
9.3.2 用户管理
9.3.3 角色管理
9.3.4 sql server的固定角色
9.4 权限管理
9.4.1 授予权限
9.4.2 收回权限
9.4.3 禁止权限
9.5 架构
小结
习题
第10章 数据库保护
10.1 事务
10.1.1 事务的定义
10.1.2 事务的acid性质
10.1.3 事务的状态
10.2 并发控制
10.2.1 并发 *** 作与数据的不一致性
10.2.2 封锁
10.2.3 并发 *** 作的调度
10.3 数据库的恢复
10.3.1 存储器的结构
10.3.2 恢复的原则和实现方法
10.3.3 故障类型和恢复方法
10.4 sql server数据库备份与恢复
10.4.1 数据库备份方法
10.4.2 数据库恢复
小结
习题
第11章数据库技术新进展
11.1 数据仓库
11.1.1 数据仓库的概念、特点与组成
11.1.2 数据的技术
11.1.3 数据仓库的几个重要概念
11.1.4 数据仓库的结构
11.1.5 数据仓库的多维数据模型
11.1.6 数据仓库系统设计
11.1.7 数据仓库的未来
11.2 数据挖掘
11.2.1 支持数据挖掘的基础
11.2.2 数据挖掘的分析方法
11.2.3 数据挖掘常用的基本技术
11.2.4数据挖掘技术实施的步骤
11.2.5数据挖掘技术发展
11.3 数据库技术的研究及发展
11.3.1 数据库技术的研究热点
11.3.2 数据库技术的发展方向
11.4 结语
小结
习题
附录a sql server 2005的安装及使用
a.1 sql server简介
a.2 sql server 2005的安装
a.3 sql server配置管理器
a.4 启动sql server服务
a.5 使用sql server management studio管理数据库
附录b 实验
实验一 通过sql server management studio创建及管理数据库
实验二 通过sql语句创建与管理数据表
实验三 单表查询
实验四 复杂查询
实验五 视图的创建与使用
实验六 存储过程
实验七 触发器
实验八 实现数据完整性
实验九 索引及数据库安全
参考文献
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）