数据库设计与应用

关系数据理论

如何设计好的关系模式使得数据库的使用效率更高

问题提出

怎样判断数据库好坏：用范式衡量

关系模式由五部分构成：R(U, D, DOM, F)

• R：关系名
• U：属性名集合
• D：属性的域
• DOM：属性向域的映象集合
• F：属性间数据的函数依赖
• 其中D,DOM和关系模式设计关系不大，于是我们也视作三元组R(U, F)

数据依赖：完整性约束的表现

• 函数依赖（FD）
• 多值依赖（MVD）

试想这样一个数据库：一个学校的教务管理系统，只有一个表，Student(sno, sdept, mname, cno, grade)，分别为学号、系、系主任、课程号、成绩

这个关系模式存在的问题：

• 数据冗余太大：系主任一个系只有一个，系中每条数据都加这个人的名字
• 更新异常（Update Anomalies）：更换系主任后，系中每条数据都要改
• 插入异常（Insertion Anomalies）：一个系刚成立没有学生，无法插入系主任的数据
• 删除异常（Deletion Anomalies）：学生全毕业了，系主任的数据会随之丢失

将这个表分成三个表

• S(sno, sdept), sno -> sdept
• SC(sno, cno, grade), sno,cno -> grade
• Dept(sdept, mname), sdept -> mname

解决了上述四个问题且数据完整没有任何丢失

规范化

规范化理论用于指导改造关系模式，通过分解关系模式来消除不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题

函数依赖

设有关系模式R，U为其属性集，X,Y∈U，X的取值唯一（在表中只出现一次），且只对应一个Y，那么我们说X函数确定Y，或Y函数依赖于X，记作X->Y

• 不同的X可以对应相同的Y
• X,Y可以是多个属性，也可以是单个属性

平凡依赖：若X->Y, Y∈X，称其为平凡依赖

非平凡依赖：即X->Y, Y!∈X

完全依赖：若X->Y，且Y不依赖于X的任一子集，则成为完全依赖

部分依赖：与完全依赖相反，即X->Y，X的某一子集也可以决定Y

传递函数依赖：X->Y, Y!∈X, Y->Z, Z!∈Y，则称Z传递依赖于X，记作X->Z(传递)

码

码：key

候选码：可以决定关系中全部属性的一组码（可单可多）

主码：选定候选码中某个码为主码

主属性：候选码中的属性

非主属性：非候选码中的属性

全码：码为整个属性组，称为全码

外码：不为当前关系的候选码，但是是其他关系的码

范式

• 第一范式
• 第二范式
• 第三范式
• BC范式
• 第四范式
• 第五范式

低级范式的关系模式可以转化为若干个高一级的关系模式，这个过程就叫做规范化

1NF：第一范式，关系模式R中每个属性都是不可再分的基本数据项，如不能连续存语数英三门成绩（9165110）

• 不满足1NF不能称为关系数据库

2NF

消除部分依赖

2NF：若R满足1NF，且每个非主属性都完全依赖于候选码，则R∈2NF

• 这意味着非主属性必须完全依赖于码，不可以部分依赖

  如果说某个非主属性依赖于主码但不依赖于某个主属性（候选码多于一个），那么这个关系模式不符合2NF

• 注意非主属性可以依赖于非主属性

  如系教学楼可以依赖于系，但系是非主属性，依赖于学号

举个栗子：S-L-C(Sno, Sdept, Sloc, Cno, Grade)

其中，Sno学号, Cno课程号和为码，可以决定Sdept系, Sloc系教学楼, grade成绩，很明显，学号可以直接决定系、系教学楼，不需要课程号参与

• 即系、系教学楼部分依赖于码

这样会造成如下问题：

• 插入异常

  如果插入一个新学生，但该生未选课，即该生无Cno，由于插入元组时，必须给定码值，因此插入失败

• 删除异常

  如果S4只选了一门课C3，现在他不再选这门课，则删除C3后，整个元组的其他信息也被删除了

• 数据冗余度大 （k门课，Sdept Sloc重复存储k次）

• 修改复杂

  如果一个学生选了多门课，则Sdept，Sloc被存储了多次。如果该生转系，则需要修改所有相关的Sdept和Sloc，造成修改的复杂化

解决方法：将S-C-L拆分为两张表

• SC(Sno,Cno,Grade)
• S-L(Sno,Sdept,Sloc)

3NF

消除非主属性对主属性的传递依赖

3NF：在2NF的基础山，非主属性不依赖于任一非主属性，那么该关系模式满足3NF

• 可以从传递依赖的方面来理解，如学号->系，系->系教学楼，其中系是一个非主属性，在码学号和非主属性系教学楼之间存在非主属性系连接的传递依赖，那么我们就说这个关系模式不满足3NF

举个例子S-L(Sno,Sdept,Sloc)

解决方法：将S-L拆分为两张表

• S-D(Sno, Sdept)
• S-L(Sdept, Sloc)

BCNF

Boyce-Codd巴斯科德范式，通常被认为是修正的第三范式

• 所有非主属性都完全依赖于每个候选码(2NF)
• 没有任何属性完全依赖于非码的任何一组属性(3NF)
• 所有主属性都完全依赖于每个不包含它的候选码(BCNF)

进一步规范了主属性的依赖

注意：满足BC范式一定满足第三范式，反之不然

多值依赖

将关系模式的属性集U分为三个部分X,Y,Z，其中Z=U-X-Y

若一对(x,y)值对应一组Z值，但z实际上只取决于x，而无关y，这时我们称Z多值依赖于X

学科X	教师Y	参考书Z
数学	邓军	数分
数学	邓军	高代
数学	邓军	微分

• 如上述关系中，候选码为全码，满足3NF，一组X,Y决定一个Z，但实际上Z只取决于X

可将上表分为

学科X	教师Y
数学	邓军

学科X	参考书
数学	数分
数学	高代
数学	微分

• 两个表的候选码依旧为全码，分别均满足3NF，未拆分前存在多值依赖

平凡多值依赖：若X-->Z且Y为空集，则称Z平凡多值依赖于X

非平凡多值依赖：即Y不为空集

多值依赖的性质：

• 对称性：若x-->Z，则必有X-->Y
• 函数依赖是多值依赖的特殊情况
  • 函数依赖X->Y：X具有唯一性，一个X只对应一个Y
  • 多值依赖X-->Z：(X,Y)不具有唯一性，对应多个Z
• 若X-->Y，X-->Z，则X-->Y∪Z, X-->Y∩Z, X-->Y-Z, X-->Z-Y
• 传递性：若X-->Y, Y-->Z， 则X-->Z–Y

4NF

要求关系模式中所有的非平凡多值依赖均满足：X中均含有码

翻译成人话就是

• 限制了关系模式中的多值依赖，不允许出现非平凡且非函数依赖的多值依赖
• 即要求关系模式中只准有函数依赖，不准有多值依赖
• 平凡多值依赖就是TM的函数依赖

数据依赖的公理系统

Armstrong公理系统

模式分解算法的理论基础：Armstrong公理系统

• 尽可能少的函数依赖描述出实际需求

逻辑蕴含：若F是关系模式R的函数依赖，若在R中，Y函数依赖于X，即X->Y，则称F逻辑蕴含X->Y

Armstrong公理：

• 自反律：若Y包含于X包含于U，则X->Y为F所蕴含
• 增广律：X->Y被F蕴含，则XZ->YZ同样被F蕴含
• 传递律：若X->Y,Y->Z被F蕴含，则X->Z被F蕴含

根据上述公理可以导出规则：

• 合并规则：若X->Y,X->Z，则X->YZ
• 伪传递规则：若X->Y,WY->Z，则XW->Z
• 分解规则：若X->Y,Z包含于Y，则X->Z

函数依赖闭包：

X关于函数依赖集F的闭包X+：

• XF+ ={A|X→A能由F根据Armstrong公理导出}

在F中，若X->Y能根据公理推出，那么Y一定被包含于XF+

• 于是判断X->Y是否能导出变成判定Y是否是XF+子集的问题

Armstrong公理是有效且完备的

函数依赖集等价：当G+=F+，则称函数依赖集F于G等价

最小依赖集：

• F中任一函数依赖的右部仅含有一个属性
• F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价 (没有多余的函数依赖)
• F中不存在这样的函数依赖X→A， X有真子集Z使得F-{X→A}∪{Z→A}与F等价 (决定因素里没有多余的属性)
• 目的：用最少的描述反应实际中事物间的关系从而便于分解

极小化过程：即把依赖集F化为其等价的最小依赖集Fm

模式分解

模式分解

矩阵法

• 极小化处理
• 去重取并

分解法

关系一定有码

任何一个二元关系都是3NF、BCNF、4NF

最小函数依赖集算法

• 右部单属性

  H->IK，分解为H->I, H->K

• 无多余依赖

  H->J, J->K, K->I, H->I，那么H->I就是多余的

• 左部无多属性

  IJK->L, I->K，那么可以简化为IJ->L, I->K

候选码求解算法

• L类属性：只出现在函数依赖左部的属性

• R类属性：只出现在函数依赖右部的属性

• LR类属性：同时出现在函数依赖左右部的属性

• N类属性：不在F中的函数依赖中出现的属性

有以下结论

• L类属性和N类属性必包含于任一候选码中
• R类属性必不包含于任何候选码中
• LR类属性不能确定是否在码中

算法：对码分类

数据库设计方法和步骤

各阶段目标及注意事项

概述

为用户和各种应用系统提供一个信息基础设施和高效率的运行环境(存取效率、存储空间利用率运行管理效率)

特点：

• 基本规律：三分技术，七分管理，十二分基础数据
• 结构（数据）设计和行为（处理）设计相结合

设计方法：

• 手工试凑方法
• 规范设计法
  • 新奥尔良方法
  • 基于E-R模型的数据库设计方法
  • 3NF的设计方法
  • 面向对象的数据库设计方法
  • 统一建模语言(UML)方法

数据库设计准备工作：确立系统分析人员、数据库设计人员；用户和数据库管理员；应用开发人员

数据库设计的六个过程：

• 需求分析
• 概念结构设计
• 逻辑结构设计
• 物理结构设计
• 数据库实施
• 数据库运行和维护

需求分析

任务：

• 调查显示世界要处理的对象
• 了解原系统
• 明确用户各种需求
• 确定新系统功能
• 充分考虑今后可能的扩充和改变

需求分析方法：

• 调查并分析实际需求
  • 常用调查方法：
    • 跟班作业
    • 开调查会
    • 请专人介绍
    • 询问
    • 用调查表进行用户调研
    • 查阅记录
  • 结构化分析方法：
    • 从最上层的系统组织机构入手
    • 自顶向下、逐层分解分析系统
• 与用户达成共识
• 分析和表达这些需求

数据字典：关于数据库中数据的描述，即元数据，是数据分析所获得的主要结果

数据字典的内容：

• 数据项
• 数据结构
• 数据流
• 数据存储
• 处理过程

概念结构设计

什么是概念结构设计？

• 将需求分析得到的用户需求抽象为信息结构即概念模型的过程就是概念结构设计
• 概念结构是各种数据模型的共同基础，它比数据逻辑模型和物理模型更独立于机器、更抽象，从而更加稳定
• 概念结构设计是整个数据库设计的关键

概念模型：从现实世界抽象出的模型

• 能真实、充分地反映现实世界
• 易于理解
• 易于更改
• 易于向关系、网状、层次等各种数据模型转换

逻辑结构设计

E-R模型：描述概念模型的工具

• 消除冲突
  • 属性冲突
  • 命名冲突
  • 结构冲突
• 消除不必要的冗余**，**设计生成基本E-R图
  • 分析方法
  • 规范化理论

数据模型的优化

• 极小化数据依赖
• 确定关系模式范式，进行范式的合并或分解
• 对关系模式进行分解，提高数据操作效率和存储空间
  • 水平分解：从行上分解，如stu分成stu1,stu2两张表存，base分成base1,base2两个库存
  • 垂直分解：从列上分解，保持连接无损性

数据库的物理设计

数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于选定的数据库管理系统

数据库管理系统常用存取方法：

• B+树索引存取方法
• Hash索引存取方法
• 聚簇存取方法

聚簇的作用：

• 大大提高按聚簇码进行查询的效率

  如果将同一系的学生元组集中存放，则每读一个物理块可得到多个满足查询条件的元组

• 节省存储空间

  聚簇以后，聚簇码相同的元组集中在一起了

聚簇的局限性：

• 聚簇只能提高某些特定应用的性能
• 建立与维护聚簇的开销相当大

确定数据存放位置和存储结构的因素

• 存取时间
• 存储空间利用率
• 维护代价

确定数据存放位置和存储结构的基本原则

• 易变部分与稳定部分分开存放
• 经常存取部分与存取频率较低部分分开存放

数据库编程

如何在应用程序中去访问和管理数据库

编程技术的概念、方法：嵌入SQL、PL/SQL、ODBC

略，参考jdbc

关系查询处理和查询优化

关系数据库系统的查询处理

RDBMS查询处理步骤：

• 查询分析：对SQL查询语句进行扫描，进行词法分析和语法分析
• 查询检查
  • 合法权检查
  • 视图转换
  • 安全性检查
  • 完整性初步检查
• 查询优化：选择一个高效执行的查询处理策略
• 查询执行：两种执行方法
  • 自顶向下
  • 自底向上

常见查询算法：

• 全表扫描算法
• 索引扫描算法

连接算法：

• 嵌套循环算法(nested loop join)
• 排序-合并算法(sort-merge join或merge join)
• 索引连接(index join)算法
• Hash Join算法

关系数据库系统的查询优化

• 是关系数据库管理系统实现的关键技术又是关系系统的优点所在
• 减轻了用户选择存取路径的负担

数据库执行代价考虑：

• 集中式数据库：执行开销主要包括
  • 磁盘存取块数(I/O代价)
  • 处理机时间(CPU代价)
  • 查询的内存开销
  • I/O代价是最主要的
• 分布式数据库
  • 总代价 = I/O代价 + CPU代价 + 内存代价＋通信代价

代数优化

关系代数表达式等价变换规则：运用离散数学的知识简化关系代数表达式

查询树的启发式优化：

• 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条
• 把投影运算和选择运算同时进行
• 把投影同其前或其后的双目运算结合起来
• 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算
• 找出公共子表达式

物理优化

物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划

物理优化方法：

• 基于规则的启发式优化

  • 启发式规则是指那些在大多数情况下都适用，但不是在每种情况下都是适用的规则

• 基于代价估算的优化

  • 优化器估算不同执行策略的代价，并选出具有最小代价的执行计划

• 两者结合的优化方法：

  • 常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量

    然后分别计算这些候选方案的执行代价，较快地选出最终的优化方案

数据库恢复技术

略

并发控制

略

数据库管理系统

略