数据库原理

数据库概念

数据库：有组织，可共享的大量数据集合，数据之间的联系

数据库管理系统：存储、维护...的软件

应用系统：DBMS，Application，应用界面

数据库系统：硬件HW，数据库DB，软件SW，DBMS，DBA

数据管理技术：人工，文件，数据库

• DBMS的功能

DDL，DML，运行管理，组织存储，建立和维护，通信接口

特点：结构化，共享性，独立性，统一管理和控制（安全性，完整性，并发，恢复）

模式

型Type，值Value

模式Schema，实例Instance

三级模式：模式（逻辑），外模式（子模式，局部逻辑），内模式（存储模式，物理结构唯一）

二级映像：逻辑独立、物理独立

数据模型

数据结构，数据操作，完整性约束

概念模型：ER实体关系模型

逻辑模型：关系模型

ER模型

实体Entity具有多个属性Attribute

码Key：A中能够唯一标志E

域Domain：A的取值范围

简单属性：不可再分

复合属性：可以细分的属性

单值属性：一对一映射

多值属性：一对多映射

派生属性：通过其它属性计算得到

关系Relationship：属性之间，实体集（表）之间

实体集之间的R：

1:1，1:n，m:n

弱实体：双线矩形

关系模型

关系R，元祖T，属性A，主码K

分量：元祖中的一个属性值

• 规范化理论

属性不可再分，元组唯一，元祖次序无关，属性次序无关

笛卡尔积CP：域的乘积（穷举所有可能的组合）

CP的子集：关系R(D1,D2,D3)

• Key

候选码：唯一标识某个元祖

超键：候选码为真子集的集合

主码PK（Primary Key）：候选码的一种取值

关系模型（Relation Schema）：表（属性）即R(U,D,DOM,F)

关系是值：表中的元祖（一行记录作为一个关系）

R(U,D,Dom,F)表示中，R关系名，U属性集，D属性的域，Dom属性到域的映像集合，F依赖关系集合

• 完整性约束

实体（唯一性，PK唯一非空），参照（FK的域取决于PK的域，更新删除的约束），用户定义（check或触发器约束）

关系代数

传统集合运算：并 交 差，笛卡尔积

专门关系运算：选择，投影，连接

• 关系演算语言

元祖、域、结构化查询语言SQL

• 关系运算

t \in R t是R的一个元组（关系集合中的一个关系）

t[A_i] 元祖t的某个分量

笛卡尔积的表示 R \times S = \{t_r t_s | t_r \in R \land t_s \in S\} ，m目关系乘n目关系得到m+n目关系（连接），基数（行数）相乘

• 专门关系运算

选择（元祖） \sigma_F(R) ，F选择条件（逻辑表达式），R关系集合

（在列上的）投影 \pi_A(R) , A属性列，R关系集合

连接， R \mathop{\bowtie}_{A \theta B} S ，\theta 表示任意比较运算符，A、B表示属性（组）

等值连接： R \bowtie S(A=B)

自然连接： R \bowtie S ，等值连接并去掉重复的属性列

除： R \div S = \{ t_r [X] \mid t_r \in R \land \pi_Y (S) \subseteq Y_X \} ，R中的元祖满足S在Y上的投影是Yx的子集，X表示R中比S多出来的域，Y表示R和S共有的域

• 逻辑运算符

\land 与 \lor 或 \neg 取反

• 外连接

全外连接：左右表的悬浮元祖保留，填充NULL

左外连接：保留左表的所有元祖，右表对应的字段填充NULL

右外连接：...

• 重命名

\rho_s(A_1,A_2,..,A_n) (R) 表示关系R重命名为S，属性名为A1...n

广义投影（Generalized Projection） \pi_{表达式1,表达式2}(R)

聚合函数：MAX MIN COUNT SUM AVG

元祖演算

元祖表达式 \{ t \mid P(t) \} 变量t为元祖，P为公式（谓词），满足表达式P的所有元祖t的集合

1. R(t)：t是R中的一个元祖
2. t[i] \theta u[j] ：两个元祖的在分量上满足 \theta 关系
3. t[i] \theta C ：C是常量，t元祖的i分量与常量C满足 \theta 关系

域演算

1. R(t_1...,t_i,...,t_k) ：R中的元祖t由域t_1,t_2,...,t_k 构成
2. t_i \theta u_j ：两个域满足 \theta 关系
3. t_i \theta C ：域等于某个常数

查询优化

查询树中，将选择\sigma 提前到笛卡尔积前面

规范化理论

简化的关系模式R(U,F)，U属性组，F依赖关系集合

函数依赖FD：如果R的两个记录t的A1A2...An分量相等，那么两个t的B分量相等，记作A_1A_2...A_n \rightarrow B

• 函数依赖

X，Y分别是R上的属性集合，假设 X决定Y

平凡函数依赖：Y是X的子集

非平凡FD：Y中至少有一个属性不属于X

完全非平凡FD：Y中所有属性都不属于X

部分函数依赖P：X决定Y，但Y不完全依赖X，且存在X的真子集决定Y

传递函数依赖：X决定Y，Y决定Z，且两个依赖关系非平凡，X（传递）决定Z

• Armstrong公理

关系模式R<U,F>

1. 自反：X包含Y，则X决定Y（Y是X的子集，X到Y存在依赖）
2. 增广：X决定Y，则XZ决定YZ
3. 传递：X决定Y，Y决定Z，则X决定Z

推理规则：

1. 合并：X决定Y，X决定Z，则X决定YZ
2. 伪传递：X决定Y，WY决定Z，则XW决定Z
3. 分解：X决定Y，Z是Y的子集，则X决定Z
4. 属性集闭包

计算闭包：属性集X能够决定的属性加入到X中

函数依赖集合FD中，计算A决定B是否能够从FD推导出来：计算A的闭包cA，如果cA包含B，则能，反之不包含则不能

• 闭包求键

关系R的候选码K满足条件：K决定U（K决定R中的任何属性）K不存在真子集决定U（K为最小属性集合）

那么K的闭包为U

• LR候选码

L：仅出现在F左部的属性，R右部，LR左右都出现，NLR（F中未出现的属性）

候选码K不能包含R属性，必须包含NLR属性

L属性的闭包为U时，该K为唯一候选码

• 最小函数依赖
• 范式

1NF \supset 2NF \supset 3NF \supset BCNF \supset 4NF \supset 5NF

1NF：属性不可再分

2NF：消除非主属性对K的部分函数依赖

3NF：消除...部分和传递

BCNF：每一个决定因素都包含K（避免异常）

4NF：消除非平凡且非函数的多值依赖

• 多值依赖

三个属性集XYZ，存在(x,z)对应一组Y，且Y仅由x决定而与z无关

4NF中每个非平凡多值依赖X中都有K

R分解：1含有X和Y的全部属性和2函数X和U-X-Y的全部属性

• 无损分解

R无损分解为R1，R2

R_1 \cup R_2 \rightarrow R_1-R_2 \in F^+

或R_1 \cup R_2 \rightarrow R_2-R_1 \in F^+

属性共有的子集（交集）能够决定差集，且该依赖在F的闭包内，则是无损分解，保持函数依赖

• Chase法

分解三个及以上的子模式：构造A-R追踪表，如果A in R填充ai，否则填充bij

根据F中的依赖关系将b类值更新为a类值

出现一行全为a，那么是无损分解，否则是有损

关系模式分解到3NF，可以保持函数依赖，存在部分冗余FD（除非分解到BCNF以及4NF完全消除冗余）