热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

数据库——关系数据理论

目录一、问题提出数据依赖与冗余二、函数依赖2.1定义2.2函数依赖类型2.2.1函数依赖2.2.2平凡函数依赖与非平凡函数依赖2.2.3完全函数依赖与部分函数依赖

目录

一、问题提出

数据依赖与冗余

二、函数依赖

2.1定义

2.2函数依赖类型

2.2.1函数依赖

2.2.2平凡函数依赖与非平凡函数依赖

2.2.3完全函数依赖与部分函数依赖

2.2.4传递函数依赖

2.3函数依赖的推导

2.3.1 Armstrong公理

2.3.2属性集的闭包

2.3.3函数依赖集的极小覆盖

三、范式

3.1码

3.2范式种类

3.2.1 1NF

3.2.2 2NF

3.2.3 3NF与 BCNF

四、关系模式分解

4.1无损连接分解

4.2保持函数依赖的分解

五、关系模式分解成高级范式

5.1具有无损连接性的 BCNF分解

5.2具有无损连接性和保持函数依赖的 3NF分解



  • 关系名R是符号化的元组语义
  • U为一组属性
  • D为属性组U中的属性所来自的域
  • DOM为属性到域的映射
  • F为属性组U上的一组数据依赖(关系内部属性与属性之间的一种约束关,主要分函数依赖和多值依赖)

由于D、DOM与模式设计关系不大,本博客中把关系模式看作一个三元组:R

一、问题提出

数据库设计的不好可能导致多个问题:冗余,修改异常,插入异常,删除异常

数据依赖与冗余

数据依赖是关于诸属性值之间内在相关性的陈述,它规定了关系模式的合法关系实例所必须满足的条件,可分为函数依赖多值依赖

依赖和冗余是密不可分的:承认某种数据依赖,就能发现关系中的某些冗余;而不承认数据之间的依赖关系,也没理由认为某些信息是多余的

冗余的产生原因和处理总是联系在一起

 

 

二、函数依赖

2.1定义

字母表开头的大写字母 A,B,…,H表示单个属性

字母表尾部的大写字母 U,V,…,Z一般表示属性集,也可能是由单个属性构成的集合。U常用于表示关系的全部属性组成的集合

串接表示并。A1A2…An表示集合 {A1,A2,…,An},XY是 X \cup

  • 某一关系模式R为第n范式,可简记为R∈nNF

一个低一级范式的关系模式,通过模式分解可以转换为若干个高一级范式的关系模式的集合,这种过程就叫规范化

3.2.1 1NF

条件:每个分量必须是不可分开的数据项

解释:在一列中不能插入两个及以上不同属性的值

3.2.2 2NF

定义:对于任意的非平凡函数依赖 X->A \in F+,必须满足下列两个条件之一:A是主属性,或 X不是 R的任何码的真子集

解释:第二范式(2NF)要求数据库表中的每个实例或记录必须可以被唯一地区分。选取一个能区分每个实体的属性或属性组,作为实体的唯一标识,即要有主码

举例:如果在成绩表SG中添加一列姓名变成下面这样,SG表的主码是学号加CID(课程号),但是(学号)->姓名,所以姓名部分函数依赖于(学号,CID(课程号)),不符合2NF

成绩表SG

学号CID(课程号)成绩
1180

成绩表SG 2.0

学号CID(课程号)成绩姓名
1180张三

3.2.3 3NF与 BCNF

1、3NF

定义:对于任意的非平凡函数依赖 X->A \in F+,必须满足下列两个条件之一:A是主属性,或 X是 R的码(在2NF基础上消除传递依赖)

解释:第三范式(3NF)要求一个关系中不包含已在其它关系已包含的非主属性信息

举例:如果在课程表SC中添加一列老师姓名,变成如下,存在CID(课程号)->TID(授课老师ID),TID(授课老师ID)->教师姓名,TID(授课老师ID) !->CID(课程号),所以教师姓名传递函数依赖于CID(课程号),不满足3NF,但是满足2NF,主码是CID

课程表SC

CID (课程号)课程名称TID(授课老师ID)学分
1数学12

课程表SC 2.0

CID (课程号)课程名称TID(授课老师ID)学分教师姓名
1数学12李四

2、BCNF

对于任意的非平凡函数依赖 X->A \in F+,X是 R的码


范式总结

  • 1NF:关系模式的任何一个属性都是原子属性
  • 2NF:任一个非主属性都不能依赖于码的一部分
  • 3NF:任一个非主属性都不能传递依赖与码
  • BCNF:非主属性和主属性都不能依赖于码的一部分或传递依赖于码

 

 

四、关系模式分解

4.1无损连接分解

检测无损分解的连接性

输入:关系模式 R(A1,A2,...,An),R的函数依赖集 F和分解 \rho ={R1,R2,...Rk}

输出:\rho 是否是关于 F的无损连接分解的判定

方法

  1. 建立一张 n列 k行的表,每一列对应一个属性,每一行对应一个关系模式。若属性Aj \in Ri,则表的第 i 行第 j 列上为 aj,否则为 bij
  2. 重复如下过程,直到表不再变化:在每一轮,考察每个 X->Y \in F。如果表中存在两行或多行在 X的属性上对应相同,则按如下方法使得这些行在 Y上的符号相同:对于每个 Aj \in Y,如果这些行存在 aj,则将这些行的第 j 列都改为 aj,否则将它们都改为 bij,其中 i 是这些行的最小行号
  3. 如果存在一行是a1...an,则 \rho 是无损连接分解,否则不是

例:关系模式 R(A,B,C,D,E)的分解是 \rho ={R1(A,B,C), R2(C.D), R3(D,E)},其中 R的函数依赖集 F={AB->C,C->D,D->E}

解:

构造初始表

A

B

C

D

E

a1

a2

a3

b14

b15

b21

b22

a3

a4

a5

b31

b32

b33

a4

a5

得出最终表

A

B

C

D

E

a1

a2

a3

a4

a5

b21

b22

a3

a4

a5

b31

b32

b33

a4

a5

第一行是a1a2a3a4a5,所以 \rho 是无损连接分解

如果 R被分解成两个关系模式 R1和 R2,可用如下简单方法进行判定

设 \rho ={R1,R2}是关系模式 R的一个分解,F是 R上的函数依赖集。\rho 关于 F是无损连接分解当且仅当:

(R1 \cap R2) -> (R2 - R1) 或 (R1 \cap R2) -> (R2 - R1)

 

4.2保持函数依赖的分解

输入:关系模式 R的函数依赖集 F和分解 \rho ={R1,R2,...,Rk}

输出:\rho 是否保持函数依赖的判定

方法

for (每个 X->Y包含于 F) do
beginif (不存在 i使得 XY包含于 Ri) then
--检验 X->Y是否被分解 p所保持beginZ=X;repeatfor i=1 to k doZ=Z 并 ((Z 交 Ri)+ 交 Ri);until (Z不发生变化);if (Y不是 Z的子集) then -- X->Y不被分解 p所保持return p不是保持函数依赖的分解;end;
end;


无损连接是对关系模式分解的基本要求。不具有无损链接性的分解是有害的,因为分解前后的关系模式可能不能反应相同的现实世界

保持函数依赖的分解是对关系模式分解的进一步要求。实践中应当在确保无损连接性的前提下尽可能地追求保持函数依赖。如果两者不可兼得,优先考虑无损连接分解

 

 

五、关系模式分解成高级范式

任意关系模式都可以无损连接地分解成 BCNF

如果要求分解保持函数依赖,或者保持函数依赖并且具有无损连接性,则只能保证分解到 3NF

5.1具有无损连接性的 BCNF分解

只包含两个属性的关系模式一定是 BCNF

输入:关系模式 R及 R的函数依赖集 F

输出:R的 BCNF分解,它关于 F具有无损连接性

方法

result={R}
while (存在 Ri属于 result,但 Ri不是 BCNF)
begin找出 Ri中满足如下条件的非平凡函数依赖:X->Y属于F+,且 X不是 Ri的超码;result={Ri1(XY),Ri2(Ri-Y)};   --之后分别对新产生的模式进行该操作
end
return result;

例、关系模式R,其中:U={A,B,C,D,E},F={A→C,C→D,B→C,DE→C,CE→A},将其分解成BCNF并保持无损连接

解:

L: ACBDE   R: CDA N:      LR: ACD

①令ρ={R(U,F)}

②ρ中不是所有的模式都是BCNF,转入下一步

③分解R:R上的候选关键字为BE(因为所有函数依赖的右边没有BE)

   考虑A→C函数依赖不满足BCNF条件(因A不包含候选键BE),将其分解成R1(AC)、R2(ABDE)

   计算R1和R2的最小函数依赖集分别为:F1={A→C},F2={B→D,DE→D,BE→A}

   其中B→D是由于R2中没有属性C且B→C,C→D;DE→D是由于R2中没有属性C且DE→C,C→D;BE→A是由于R2中没有属性C且B→C,CE→A。又由于DE→D是蕴含关系,可以去掉,故F2={B→D, BE→A}

 

5.2具有无损连接性和保持函数依赖的 3NF分解

对于给定的关系模式 R,先计算 F的极小覆盖(转顶部链接内容:2.3.3函数依赖集的极小覆盖)

对于极小覆盖中的每个函数依赖,只要依赖的左侧相同,则合并这些函数依赖的所有属性构成一个单独的模式

如果关系模式 R中存在没有出现在函数依赖集中的元素,这些元素合并构成一个单独的模式

如果上面两步得出的结果中不包含候选码,则候选码单独构成一个模式(尽管候选码被拆散到多个模式中也不算)

例、关系模式R,其中U={C,T,H,R,S,G},F={CS→G,C→T,TH→R,HR→C,HS→R},将其分解成3NF并保持函数依赖

解:

(一)计算F的最小函数依赖集

①利用分解规则,将所有的函数依赖变成右边都是单个属性的函数依赖。由于F的所有函数依赖的右边都是单个属性,故不用分解

②去掉F中多余的函数依赖 F={CS→G,C→T,TH→R,HR→C,HS→R}

   去掉F中各函数依赖左边多余的属性(只检查左部不是单个属性的函数依赖),没有发现左边有多余属性的函数依赖

   故最小函数依赖集为:F={CS→G,C→T,TH→R,HR→C,HS→R}

(二)由于R中的所有属性均在F中都出现,所以转下一步

(三)对F按具有相同左部的原则分为:

F={CS→G,C→T,TH→R,HR→C,HS→R}

R1=CSG,R2=CT,R3=THR,R4=HRC,R5=HSR

所以 ρ={ R1(CSG), R2(CT), R3(THR), R4(HRC), R5(HSR) }


推荐阅读
  • 本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率,使用经典的EK(Edmonds-Karp)和Dinic算法进行求解。 ... [详细]
  • 本文介绍如何使用阿里云的fastjson库解析包含时间戳、IP地址和参数等信息的JSON格式文本,并进行数据处理和保存。 ... [详细]
  • 探讨如何真正掌握Java EE,包括所需技能、工具和实践经验。资深软件教学总监李刚分享了对毕业生简历中常见问题的看法,并提供了详尽的标准。 ... [详细]
  • 优化局域网SSH连接延迟问题的解决方案
    本文介绍了解决局域网内SSH连接到服务器时出现长时间等待问题的方法。通过调整配置和优化网络设置,可以显著缩短SSH连接的时间。 ... [详细]
  • 本文详细介绍了网络存储技术的基本概念、分类及应用场景。通过分析直连式存储(DAS)、网络附加存储(NAS)和存储区域网络(SAN)的特点,帮助读者理解不同存储方式的优势与局限性。 ... [详细]
  • 解析SQL查询结果的排序问题及其解决方案
    本文探讨了为什么某些SQL查询返回的数据集未能按预期顺序排列,并提供了详细的解决方案,帮助开发者理解并解决这一常见问题。 ... [详细]
  • 本文详细介绍了如何通过RPM包在Linux系统(如CentOS)上安装MySQL 5.6。涵盖了检查现有安装、下载和安装RPM包、配置MySQL以及设置远程访问和开机自启动等步骤。 ... [详细]
  • 反向投影技术主要用于在大型输入图像中定位特定的小型模板图像。通过直方图对比,它能够识别出最匹配的区域或点,从而确定模板图像在输入图像中的位置。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 深入理解 SQL 视图、存储过程与事务
    本文详细介绍了SQL中的视图、存储过程和事务的概念及应用。视图为用户提供了一种灵活的数据查询方式,存储过程则封装了复杂的SQL逻辑,而事务确保了数据库操作的完整性和一致性。 ... [详细]
  • MySQL 数据库迁移指南:从本地到远程及磁盘间迁移
    本文详细介绍了如何在不同场景下进行 MySQL 数据库的迁移,包括从一个硬盘迁移到另一个硬盘、从一台计算机迁移到另一台计算机,以及解决迁移过程中可能遇到的问题。 ... [详细]
  • 基于KVM的SRIOV直通配置及性能测试
    SRIOV介绍、VF直通配置,以及包转发率性能测试小慢哥的原创文章,欢迎转载目录?1.SRIOV介绍?2.环境说明?3.开启SRIOV?4.生成VF?5.VF ... [详细]
  • 解决JAX-WS动态客户端工厂弃用问题并迁移到XFire
    在处理Java项目中的JAR包冲突时,我们遇到了JaxWsDynamicClientFactory被弃用的问题,并成功将其迁移到org.codehaus.xfire.client。本文详细介绍了这一过程及解决方案。 ... [详细]
  • 本文提供南昌大学《嵌入式系统》课程期末考试的真题及详细解答,涵盖填空题、指令测试题等内容,帮助学生更好地理解和掌握相关知识点。 ... [详细]
  • 本文详细介绍了C语言的起源、发展及其标准化过程,涵盖了从早期的BCPL和B语言到现代C语言的演变,并探讨了其在操作系统和跨平台编程中的重要地位。 ... [详细]
author-avatar
我就是在刷粪_944
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有