数据库设计
目标：数据库设计的整体流程，E-R画法，给定E-R图转成关系模式
数据库设计的基本步骤⭐️
- 需求分析：准确了解与分析用户需求
- 概念结构设计：通过对用户需求进行综合、归纳与抽象，形成一个独立于具体DBMS的概念模型
- 逻辑结构设计：将概念结构转换为某个DBMS所支持的数据模型，对其进行优化
- 物理结构设计：为逻辑数据模型选取一个最适合应用环境的物理结构（包括存储结构和存取方法）
- 数据库实施：运用DBMS提供的数据语言、工具及宿主语言，根据逻辑设计和物理设计的结果：建立数据库、编制与调试应用程序、组织数据入库、并进行试运行
- 数据库运行和维护：数据库应用系统经过试运行后即可投入正式运行。在数据库系统运行过程中必须不断地对其进行评价、调整与修改
需求分析
需求分析的方法过程⭐️
- 调查组织机构总体情况
- 熟悉业务活动
- 明确用户需求
- 确定系统边界
数据字典⭐️
数据字典的内容
- 数据项
- 数据结构
- 数据流
- 数据存储
- 处理过程
数据项是数据的最小组成单位
若干个数据项可以组成一个数据结构
数据字典通过对数据项和数据结构的定义来描述数据流、数据存储的逻辑内容
数据项
数据项是不可再分的数据单位
数据项描述＝{数据项名，数据项含义说明，别名，数据类型，长度，取值范围，取值含义，与其他数据项的逻辑关系｝
- 取值范围、与其他数据项的逻辑关系定义了数据的完整性约束条件
数据结构
数据结构反映了数据之间的组合关系
一个数据结构可以由若干个数据项组成，也可以由若干个数据结构组成，或由若干个数据项和数据结构混合组成
数据结构描述＝｛数据结构名，含义说明，组成:｛数据项或数据结构}｝
数据流
数据流是数据结构在系统内传输的路径
数据流描述＝｛数据流名，说明，数据流来源，数据流去向，组成:｛数据结构｝，平均流量，高峰期流量｝
- 平均流量是指在单位时间（每天、每周、每月等） 里的传输次数
- 高峰期流量则是指在高峰时期的数据流量
数据存储
数据存储是数据结构停留或保存的地方，也是数据 流的来源和去向之一
数据存储描述＝｛数据存储名，说明，编号，流入的数据流 ，流出的数据流 ，组成:｛数据结构｝，数据量，存取方式｝
- 数据量：每次存取多少数据，每天（或每小时、每周等） 存取几次等信息
- 存取方法：批处理 / 联机处理；检索 / 更新；顺序检索 / 随即检索
处理过程
处理过程的具体处理逻辑一般用判定表或判定树来描述。数据字典中只需要描述处理过程的说明性信息
处理过程描述＝｛处理过程名，说明，输入:｛数据流｝，输出:｛数据流｝，处理:｛简要说明}}
- 简要说明：主要说明该处理过程的功能及处理要求
- 功能：该处理过程用来做什么
- 处理要求：处理频度要求（如单位时间里处理多少事务，多少数据量）；响应时间要求等
- 处理要求是后面物理设计的输入及性能评价的标准
概念结构设计⭐️
要会画E-R图
E-R图画法⭐️
E-R图提供了表示实体型、属性和联系的方法：
- 实体型：用矩形表示，矩形框内写明实体名
- 属性：用椭圆形表示，并用无向边将其与相应的实体型连接起来
- 联系：用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体型连接起来，同时在无向边旁标上联系的类型（1∶1，1∶n或m∶n）
- 联系可以具有属性
- 联系的度：参与联系的实体型的数目
- 2个实体型之间的联系度为2，也称为二元联系；
- 3个实体型之间的联系度为3，称为三元联系；
- N个实体型之间的联系度为N，也称为N元联系
实体和属性的区别
实体与属性是相对而言的。同一事物，在一种应用环境中作为“属性”，在另一种应用环境中就必须作为“实体” 。
属性不能再具有需要描述的性质。即属性必须是不可分的数据项，不能再由另一些属性组成。
属性不能与其他实体具有联系。联系只发生在实体之间。
E-R图的集成
集成方式
- 一次集成
- 一次集成多个分E-R图
- 通常用于局部E-R图比较简单时
- 逐步累积式
- 首先集成两个局部E-R图（通常是比较关键的两个局部E-R图）
- 以后每次将一个新的局部E-R图集成进来
冲突⭐️
属性冲突
两类属性冲突
- 属性域冲突：属性值的类型、取值范围或取值集合不同
例1， 由于学号是数字，因此某些部门（即局 部应用）将学号定义为整数形式，而由于学号 不用参与运算，因此另一些部门（即局部应用） 将学号定义为字符型形式。
例2， 某些部门（即局部应用）以出生日期形 式表示学生的年龄，而另一些部门（即局部应用）用整数形式表示学生的年龄。 - 属性取值单位冲突
例：学生的身高，有的以米为单位，有的以厘 米为单位，有的以尺为单位
属性冲突的解决方法：讨论、协商解决
命名冲突
两类命名冲突
- 同名异义：不同意义的对象在不同的局部应用中具有相同的名字
例，局部应用A中将教室称为房间 局部应用B中将学生宿舍称为房间 - 异名同义（一义多名）：同一意义的对象在 不同的局部应用中具有不同的名字
例，有的部门把教科书称为课本 有的部门则把教科书称为教材
属性冲突的解决方法：讨论、协商解决
结构冲突
三类结构冲突
- 同一对象在不同应用中具有不同的抽象
例，“课程”在某一局部应用中被当作实体 在另一局部应用中则被当作属性
解决方法：通常是把属性变换为实体或把实体变换为属性，使同一对象具有相同的抽象。变换时要遵循两个准则 - 同一实体在不同局部视图中所包含的属性不完全相同，或者属性的排列次序不完全相同。
解决方法：使该实体的属性取各分E-R图中属性的并集，再适当设计属性的次序 - 实体之间的联系在不同局部视图中呈现不同的类型
例1， 实体E1与E2在局部应用A中是多对多联系， 而在局部应用B中是一对多联系
例2， 在局部应用X中E1与E2发生联系，而在局部应用Y中E1、E2、E3三者之间有联系。
解决方法：根据应用语义对实体联系的类型进行综合或调整。
小结
什么是概念结构设计
概念结构设计的步骤
- 抽象数据并设计局部视图
- 集成局部视图，得到全局概念结构
- 验证整体概念结构
设计局部视图
- 选择局部应用
- 逐一设计分E-R图
- 标定局部应用中的实体、属性、码，实体间的联系
- 用E-R图描述出来
集成局部视图
- 合并分E-R图，生成初步E-R图
- 消除冲突
- 属性冲突
- 命名冲突
- 结构冲突
- 修改与重构
- 消除不必要的冗余，设计生成基本E-R图
- 分析方法
- 规范化理论
逻辑结构设计⭐️
要会把E-R图转换为关系模式
转换规则⭐️⭐️⭐️⭐️⭐️
1.一个实体型转换为一个关系模式。
- 关系的属性：实体型的属性
- 关系的码：实体型的码
例，学生实体可以转换为如下关系模式： 学生（学号，姓名，出生日期，所在系， 年级，平均成绩）
2.一个m:n联系转换为一个关系模式。
- 关系的属性：与该联系相连的各实体的码以 及联系本身的属性
- 关系的码：各实体码的组合
例，“选修”联系是一个m:n联系，可以将它转换为如下关系模式，其中学号与课程号为关系的组合码： 选修（学号，课程号，成绩）
3.一个1:n联系可以转换为一个独立的关系模式，也可以与n端对应的关系模式合并。
- 转换为一个独立的关系模式
- 关系的属性：与该联系相连的各实体的码以及联系本身的属性
- 关系的码：n端实体的码
- 与n端对应的关系模式合并
- 合并后关系的属性：在n端关系中加入1端关系的码和联系本身的属性
- 合并后关系的码：不变
例，“班级组成”联系为1:n联系。 将其转换为关系模式的两种方法： 1)使其成为一个独立的关系模式： 组成（学号，班级号） 2)将其学生关系模式合并： 学生（学号，姓名，出生日期，所在系， 年级，班 级 号 \color{red}{班级号}班级号，平均成绩）
4.一个1:1联系可以转换为一个独立的关系模式， 也可以与任意一端对应的关系模式合并
- 转换为一个独立的关系模式
- 关系的属性：与该联系相连的各实体的码以及联系本身的属性
- 关系的候选码：每个实体的码均是该关系的候选码
- 与某一端对应的关系模式合并
- 合并后关系的属性：加入对应关系的码和联系本身的属性
- 合并后关系的码：不变
5.三个或三个以上实体间的一个多 元 联 系 \color{red}{多元联系}多元联系转换为一个关系模式
- 关系的属性：与该多元联系相连的各实体的码以及联系本身的属性
- 关系的码：各实体码的组合
例，“讲授”联系是一个三元联系，可以将它 转换为如下关系模式，其中课程号、职工号和 书号为关系的组合码： 讲授（课程号，职工号，书号）
6.同一实体集的实体间的联系，即自 联 系 \color{red}{自联系}自联系，也可按上述1:1、1:n和m:n三种情况分别处理。
例，如果教师实体集内部存在领导与被领导的 1:n自联系，我们可以将该联系与教师实体合 并，这时主码职工号将多次出现，但作用不同， 可用不同的属性名加以区分： 教师：｛职工号，姓名，性别，职称，系 主 任 号 \color{red}{系主任号}系主任号｝
7.具有相同码的关系模式可合并。
数据模型的优化
关系数据模型的优化通常以规范化理论为指导。
优化数据模型的方法
- 确定数据依赖
- 对于各个关系模式之间的数据依赖进行极小化处理，消除冗余的联系
- 按照数据依赖的理论对关系模式逐一进行分析，考查是否存在部分函数依赖、传递函数依赖、多值依赖等，确定各关系模式分别属于第几范式
- 按照需求分析阶段得到的各种应用对数据处理的要求，分析对于这样的应用环境这些模式是否合适，确定是否要对它们进行合并或分解。
- 按照需求分析阶段得到的各种应用对数据处理的要求，对关系模式进行必要的分解或合并，以提高数据操作的效率和存储空间的利用率
小结
任务
- 将概念结构转化为具体的数据模型
逻辑结构设计的步骤
- 将概念结构转化为一般的关系、网状、层次模型
- 将转化来的关系、网状、层次模型向特定DBMS支 持下的数据模型转换
- 对数据模型进行优化
- 设计用户子模式
数据库的物理设计
数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于给定的计算机系统。
为一个给定的逻辑数据模型选取一个最适合应用环境的物理结构的过程，就是数据库的物理设计。
存取方法
DBMS常用存取方法
- 索引方法，目前主要是B+树索引方法，其他还有hash、Rtree、Bitmap等
- 聚簇（Cluster）方法
什么是聚簇
为了提高某个属性（或属性组）的查询速度，把这个或这些属性（称为聚簇码）上具有相同值的元组集中存放在连续的物理块称为聚簇
例： CREATE CLUSTER INDEX Stusname ON Student(Sname)；
在Student表的Sname（姓名）列上建立一个聚簇索引，而且Student表中的记录将按照Sname值的升序存放
- 在一个基本表上最多只能建立一个聚簇索引
- 聚簇索引的用途：对于某些类型的查询，可以提高查询效率
- 聚簇索引的适用范围
- 很少对基表进行增删操作
- 很少对其中的变长列进行修改操作
Hash
当一个关系满足下列两个条件时，可以选择HASH存取方法
- 该关系的属性主要出现在等值连接条件中或主要出现在相等比较选择条件中
- 该关系的大小可预知，而且不变； 或该关系的大小动态改变，但所选用的DBMS提供了动态HASH存取方法。
数据库维护
在数据库运行阶段，对数据库经常性的维护工作主要是由DBA（Database Administrator）完成的，包括：
- 数据库的转储和恢复
- 数据库的安全性、完整性控制
- 数据库性能的监督、分析和改进
- 数据库的重组织和重构造
数据库编程
目标：基本概念的理解
嵌入式SQL⭐️
将SQL嵌入到高级语言，通过预编译将sql语言转换为高级语言或者一些库函数进行调用
嵌入式SQL的处理过程⭐️
为了区分SQL语句与主语言语句，需要前缀：EXEC SQL
嵌入式SQL语句与主（高级）语言之间的通信⭐️
- 主变量（宿主变量，host variable）：就是在嵌入式SQL语句中引用主语言说明的程序变量
- SQL通信区 （SQLCA）：向主语言传递SQL语句的执行状态信息；主语言能够据此控制程序流程
- 建立和关闭数据库：合法用户连接，按需分配，用完释放资源
- 游标：数据缓冲区，将查询的结果存放在缓冲区中
- 解决集合性操作语言与过程性操作语言的不匹配
- 将SQL语句查询数据库的结果交主语言进一步处理
ODBC
ODBC（Open Database Connectivity） 建立了一组规范，并提供一组访问数据库的标准API
- 规范应用开发
- 规范DBMS应用接口
PL/SQL
PL/SQL是编写数据库存储过程的一种过程语言，叫做过程化SQL语言（Procedural Language/SQL）。
它结合SQL的数据操作能力和过程化语言的流程控制（判断、循坏）能力，是SQL的过程化扩展。
PL/SQL程序的基本结构是块，所有的PL/SQL程序都是由块组成的，这些块之间可以相互嵌套，每个块完成一个逻辑操作。
存储过程
由PL/SQL书写的过程，经过编译后存储在数据库服务器中，使用时直接调用即可。
优点
- 由于存储过程不像解释执行的SQL语句那样在提出操作请 求时才进行语法分析和优化工作，因而运行效率高。
- 存储过程降低了客户机和服务器之间的通信量。
- 方便实施企业规则。
关系查询的处理和优化
目标：理解查询处理的步骤阶段，会用关系代数写出查询表达式，并对其进行优化
查询处理
查询处理的步骤⭐️
查询操作
常见的查询操作：选择，投影，连接
选择操作⭐️
- 简单的全表扫描方法：对查询的基本表顺序扫描，逐一检查每个元组是否满足条件，把满足条件的元组作为结果输出，小表有效，大表顺序扫描效率低。
- 索引扫描方法：若选择条件中的属性上有索引（B+索引或Hash索引） ，可以用索引扫描方法。 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。
连接操作⭐️
例 ： SELECT * FROM Student ,SC WHERE Student.Sno=SC.Sno;
- 嵌套循环方法（nested loop）：对外层循环（Student）的每一个元组（s）,检索内层循环（SC）中的每一个元组（sc），并检查这两个元组在连接属性 （sno）上是否相等。满足条件则串接后输出，否则直到外层循环表中的元组处理完为止。
- 排序-合并连接法（sort-merge join）：
- 若连接的表没有排好序，首先对Student表和SC表按连接属性Sno排序；
- 取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组；把它 们连接起来；
- 当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个 元组，再扫描SC表中具有相同Sno的元组，把它们连接起来；
- 重复上述步骤直到Student表扫描完。
- 索引连接（index join）方法：
- 在SC表上建立属性Sno的索引，如果原来没有的话；
- 对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组；
- 把这些SC元组和Student元组连接起来。
- 循环执行2)3),直到Student表中的元组处理完为止。
查询优化
代数优化⭐️
关系代数等价变换规则
关系代数表达式等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。上面的优化策略大部分都涉及到代数表达式的变换。
常用的等价变换规则
设E1、E2等是关系代数表达式，F是条件表达式
- 连接、笛卡尔积交换律
E 1 × E 2 ≡ E 2 × E 1 E1\times{E2}\equiv{E2\times{E1}}E1×E2≡E2×E1
E 1 ⋈ E 2 ≡ E 2 ⋈ E 1 E1\mathop{\bowtie}E2\equiv{E2\mathop{\bowtie}E1}E1⋈E2≡E2⋈E1
E 1 ⋈ F E 2 ≡ E 2 ⋈ F E 1 E1\mathop{\bowtie}\limits_{F}E2\equiv{E2\mathop{\bowtie}\limits_{F}E1}E1F⋈E2≡E2F⋈E1 - 连接、笛卡尔积的结合律
( E 1 × E 2 ) × E 3 ≡ E 1 × ( E 2 × E 3 ) (E1\times{E2})\times{E3}\equiv{E1\times({E2}\times{E3})}(E1×E2)×E3≡E1×(E2×E3)
( E 1 ⋈ E 2 ) ⋈ E 3 ≡ E 1 ⋈ ( E 2 ⋈ E 3 ) (E1\mathop{\bowtie}E2)\mathop{\bowtie}E3\equiv{E1\mathop{\bowtie}(E2\mathop{\bowtie}E3)}(E1⋈E2)⋈E3≡E1⋈(E2⋈E3)
( E 1 ⋈ F E 2 ) ⋈ F E 3 ≡ E 1 ⋈ F ( E 2 ⋈ F E 3 ) (E1\mathop{\bowtie}\limits_{F}E2)\mathop{\bowtie}\limits_{F}E3\equiv{E1\mathop{\bowtie}\limits_{F}(E2\mathop{\bowtie}\limits_{F}E3)}(E1F⋈E2)F⋈E3≡E1F⋈(E2F⋈E3) - 投影的串接定律
- 选择的串接定律
σ F 1 ( σ F 2 ( E ) ) ≡ σ F 1 ∧ F 2 ( E ) \sigma_{F1}(\sigma_{F2}(E))\equiv\sigma_{F1\wedge{F2}}(E)σF1(σF2(E))≡σF1∧F2(E)
选择的串接律说明选择条件可以合并，这样一次就可检查全部条件。 - 选择与投影的交换律
- 假设: 选择条件F只涉及属性A1,…,An
- 假设: F中有不属于A1, …,An的属性B1,…,Bm
- 选择与笛卡尔积的交换律
- 假设：F中涉及的属性都是E1中的属性
- 假设：F=F1∧F2，并且F1只涉及E1中的属性， F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出：
- 假设： F=F1∧F2， F1只涉及E1中的属性， F2涉及E1和E2两者的属性，它使部分选择在笛卡尔积前先做
- 选择与并的分配律
假设：E=E1∪E2，E1，E2有相同的属性名 
- 选择与差运算的分配律
假设：E1与E2有相同的属性名 
- 选择对自然连接的分配律
F 只涉及E1 与E2的公共属性 
- 投影与笛卡尔积的分配律
假设：E1和E2是两个关系表达式， A1，…，An是E1的属性， B1，…，Bm是E2的属性 
小结
1-2: 连接、笛卡尔积的交换律、结合律
3： 合并或分解投影运算
4： 合并或分解选择运算
5-8： 选择运算与其他运算交换
5，9，10： 投影运算与其他运算交换
查询树的启发式优化⭐️
1.选择运算应尽可能先做。 ⭐️
2.把投影运算和选择运算同时进行
3.把投影同其前或其后的双目运算结合起来
4.把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 ⭐️
5.找出公共子表达式
结合变换准则所得表达式的优化算法⭐️
（1）分解选择运算：利用规则4分解选择运算
（2）通过交换选择运算，将其尽可能移到叶端：对每一个选择，利用规则4～8尽可能把它移到树的叶端。
（3）通过交换投影运算，将其尽可能移到叶端：对每一个投影利用规则3，5，9，l0中的一般形式尽可能把它移向树的叶端。
（4）合并串接的选择和投影，以便能同时执行或在一次扫描中完成：利用规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成。
（5）对内结点分组：把上述得到的语法树的内节点分组。每一双目运算(×，⋈ \mathop{\bowtie}⋈ ，∪，-)和它所有的直 接祖先为一组(这些直接祖先是б，π运算)。如果其后代直到叶子全是单目运算，则也将 它们并入该组，但当双目运算是笛卡尔积 (×)，而且其后的选择不能与它结合为等值 连接时除外。把这些单目运算单独分为一组。
（6）生成程序：生成一个程序，每组结点的计算是程序中的 一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。
物理优化
存取路径和底层操作算法的选择
