参考资料：

ISO/IEC 9075-1:1999标准的电子整理版可以参见：https://sql-99.readthedocs.io/en/latest/

数据库管理系统事实上的标准：Microsoft Open Database Connectivity https://learn.microsoft.com/sql/odbc/microsoft-open-database-connectivity-odbc

零、绪论

数据库、数据库管理系统及数据库系统

基本概念

数据：描述事物的符号记录。

数据库：长期/永久储存在计算机内、有组织的、可共享的大量数据的集合。数据库中的数据按一定的数据模型组织、描述和储存，具有较小的冗余度（redundancy）、较高的数据独立性（data independency）和易扩展性（scalability），并可为各种用户共享。

数据库管理系统：位于用户与操作系统之间的一层数据管理软件。其功能有：

  • 数据库的建立与维护；
  • 数据定义功能：提供DDL（Data Definition Language，数据定义语言），定义数据库中数据的组成和结构；
  • 数据组织、存储和管理：确定数据库中数据的物理组织方式；
  • 数据操纵功能：提供DML（Data Manipulation Language，数据操纵语言），通过其操纵数据库；
  • 数据库的事务管理和运行管理：保证数据库及内部数据在多用户并发环境下的完整性、安全性及数据恢复。
  • 其他功能：如通信功能、数据转换功能、互访互操作等。

数据库系统：由数据库、数据库管理系统（及其应用开发工具）、应用程序、数据库管理员和其他用户（系统分析员、程序员、最终用户）组成存储、管理、处理、维护数据的系统。在不混淆的情况下，可以将数据库系统称为数据库。其特点为：

  1. 数据结构化：数据库存储的数据（组）具有自组织的特点。整体上来看，去除了（在文件系统上）文件间无关系的问题，实现了整体的结构化。
  2. 数据的共享性高、冗余度低且易扩充：数据库系统从整体角度看待和描述数据，数据不再面向某个应用而是面向整个系统。数据共享可以大大减少数据冗余，节约存储空间。数据共享还能够避免数据之间的不相容性与不一致性。而且数据库容易增加新的应用，这就使得数据库系统弹性大，易于扩充，可以适应各种用户的要求。
  3. 数据独立性高：数据独立性是借助数据库管理数据的一个显著优点，包括数据的物理独立性和逻辑独立性。数据与程序的独立把数据的定义从程序中分离出去，加上存取数据的方法又由数据库管理系统负责提供，从而简化了应用程序的编制，大大减少了应用程序的维护和修改。
    • 物理独立性是指用户的应用程序与数据库中数据的物理存储是相互独立的。
    • 逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的。
  4. 数据由数据库管理系统统一管理和控制：数据库的共享将会带来数据库的安全隐患，而数据库的共享是并发的共享。另外，数据库中数据的正确与一致也必须得到保障。为此，数据库管理系统提供以下几方面的数据控制功能。
    • 数据的安全性保护：保护数据以防止不合法使用造成的数据泄密和破坏。每个用户只能按规定对某些数据以某些方式进行使用和处理。
    • 数据的完整性检查：将数据控制在有效的范围内，并保证数据之间满足一定的关系，保证数据的正确性、有效性和相容性。
    • 并发控制：对多用户的并发操作加以控制和协调。
    • 数据库恢复：将数据库从错误状态恢复到某一已知的正确状态。

使用数据库系统的好处为：

  • 大大提高应用开发的效率
  • 当数据的逻辑结构需要改变时，开发人员不必修改应用程序，或者只需要修改很少的应用程序，从而既简化了应用程序的编制，又大大减少了应用程序的维护和修改。
  • 减轻数据库管理员维护系统的负担。

数据管理形态的演化

  1. 人工管理阶段：20世纪50年代中期以前，由于计算机仅用于科学计算等用途，不存在数据存储的需要。
  2. 文件系统阶段：至20世纪60年代，硬件存储出现，伴随着数据可以长期存储与硬件中。此时人们将数据直接存储于文件中，通过相应的文件系统访问数据。但此时由于软件的相互独立性，数据仅服务于特定的软件，数据间也基本不存在共享，冗余度较大。
  3. 数据库管理系统计算：20世纪70年代的开始，数据日益丰富，同时硬件发展，使得数据库管理系统即成为可能也有必要。
  人工管理阶段 文件系统阶段 数据库系统阶段
应用背景 科学计算 科学计算、数据管理 大规模数据管理
硬件背景 无直接存取存储设备 磁盘、磁鼓 大容量磁盘、磁盘阵列
软件背景 没有操作系统 有文件系统 有数据库管理系统
处理方式 批处理 联机实时处理、批处理 联机实时处理、分布处理、批处理
数据的管理者 用户（程序员） 文件系统 数据库管理系统
数据面向的对象 某一应用程序 某一应用 现实世界（一个部门、企业、跨国组织等）
数据的共享程度 无共享，冗余度极大 共享性差，冗余度大 共享性高，冗余度小
数据的独立性 不独立，完全依赖于程序 独立性差 具有高度的物理独立性和一定的逻辑独立性
数据的结构化 无结构 记录内有结构、整体无结构 整体结构化，用数据模型描述
数据控制能力 应用程序自己控制 应用程序自己控制 由数据库管理系统提供数据安全性、完整性、并发控制和恢复能力

数据库系统的出现使信息系统从以加工数据的程序为中心转向围绕共享的数据库为中心的新阶段。

数据模型

基本定义

是数据库中用来对现实世界进行抽象的工具，是数据库中用于提供信息表示和操作手段的形式构架。由数据结构、数据操作和完整性约束三部分组成。

概念模型

也称信息模型，它是按用户的观点来对数据和信息建模，主要用于数据库设计。概念模型应该具有较强的语义表达能力，能够方便、直接地表达应用中的各种语义知识，另一方面它还应该简单、清晰、易于用户理解。

组成部分有

  • 实体：客观存在并可相互区别的事物。
  • 属性：实体的某一特性。应当不可分。
  • 码/键：唯一标识实体的属性集。
  • 实体型：实体名及其属性名集合，用于抽象和刻画同类实体。
  • 实体集：同一类型实体的集合称为实体集。
  • 联系：实体之间的联系通常是指不同实体集之间的联系，有一对一、一对多和多对多等多种类型。

逻辑模型

逻辑模型是概念模型的细化，旨在明确数据实体的属性、关系和约束。明确实体名称、属性的数据类型和精度，定义主键、唯一索引以及实体之间的关系。

常见的逻辑模型有：

  1. 层次模型：实体间构成树。
    • 优点：结构简单清晰、查询效率高、完整性支持良好。
    • 缺点：无法描述现实中的实体间的复杂关系。
  2. 网状模型：实体间构成DAG。和层次模型统称为结构化模型。
    • 优点：更直接的描述现实中的联系、性能良好存取效率高。
    • 缺点：结构复杂、DDL、DML操作复杂。
  3. 关系模型：实体间构成线性表。这是大多数数据库所采取的逻辑模型。
    • 特点：有严格的数学基础、概念单一、存取路径透明（数据独立性、安全保密性、简化工作）
    • 缺点：查询效率较低
  4. 面向对象模型：实体作为对象。
  5. 对象关系模型：综合关系模型和面向对象模型。
  6. 半结构化数据模型：以xml或类xml形式组织实体。

物理模型

系统内部的表示方式和存取方法。

数据库系统的结构和组成

模式

通常将数据库系统的逻辑结构和特征统称为模式，数据的集体称为实例。

  • 逻辑模式：也称模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。描述了数据的全局逻辑结构。一个数据库只有一个模式。义模式时不仅要定义数据的逻辑结构，而且要定义数据之间的联系，定义数据的完整性约束条件。数据库管理系统提供模式数据定义语言（模式 DDL）来严格地定义模式。
  • 外模式：也称子模式或用户模式，它是数据库用户可见局部数据的逻辑结构和特征的描述，是数据库用户的数据视图。外模式所表示的内容通常是模式所表示的内容的子集。一个数据库可以有多个外模式。外模式通常是模式的子集。数据库管理系统提供外模式数据定义语言（外模式DDL）来严格地定义外模式。
  • 内模式：也称存储模式，是数据物理结构和存储方式的描述，是数据在数据库内部的组织方式。一个数据库只有一个内模式。

数据库的二级映像功能与数据独立性

为了能够在系统内部实现这三级模式的联系和转换，数据库管理系统在这三级模式之间提供了两层映像：外模式/模式映像和模式/内模式映像。正是这两层映像保证了数据库系统中的数据能够具有较高的逻辑独立性和物理独立性。

  • 外模式/模式映像：当模式改变时，由数据库管理员对各个外模式/模式的映像作相应改变，可以使外模式保持不变。应用程序是依据数据的外模式编写的，从而应用程序不必修改，保证了数据与程序的逻辑独立性，简称数据的逻辑独立性。
  • 模式/内模式映像：当数据库的存储结构改变时，由数据库管理员对模式/内模式映像作相应改变，可以使模式保持不变，从而应用程序也不必改变。保证了数据与程序的物理独立性。

一、关系数据库

关系数据库理论

关系模型

基本概念

关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。

  定义 类比二维表
关系（relation） 若干域$D_i$的笛卡尔积的子集 一张二维表
属性（attribute） 关系在某一域上包含元素的集合 二维表的某一列
域（domain） 一组具有相同数据类型的值的集合 某一量的可选范围
元组（tuple） 关系的某一元素 二维表的某一行
码（key）   能够唯一确定元组的属性组
分量 元组在某一属性的值 某一行的某一列值
超码/超键（super key） 包含候选码的超集  
候选码/候选键（candidate key） 完全函数确定关系的某属性组 能够唯一标识元组的、但是其子集不能的属性组
主码/主键（primary key） 其中一个候选码  
主属性（primary attribute） 候选码包含的属性  
外码（foreign key） 与某一关系的主码对应  

关系的三种类型：

  • 基本表/基本关系
  • 查询表
  • 视图表

基本关系的六（七）个性质：

  • 列是同质；
  • 不同列有不同属性名，以取消属性的有序性；
  • 列之间无序；
  • 元组的候选码两两不同；
  • 行之间无序；
  • 分量原子值/不可分。
  • 关系应为有限的。

关系模式

对关系的形式化描述，可以表示为$R(U，D，DOM，F)$。其中R为关系名，U为组成该关系的属性名集合，D为U中属性所来自的域，DOM为属性向域的映像集合，F为属性间数据的依赖关系集合。

关系数据库

一个应用中的所有关系的集合。

关系数据库的型也称为关系关系数据库模式。值就是关系数据库自身。

关系数据库的操作

操作种类

  • 插入（增）
  • 删除（删）
  • 查询（查）
    • 基本操作
      • 选择
      • 投影
      • 并
      • 差
      • 笛卡尔积
    • 连接
    • 除
    • 交
  • 更新（改）

操作的对象都是集合。

操作的描述：关系数据语言

  • 代数方法：关系代数语言
  • 逻辑方式：关系演算语言
    • 元组关系演算
    • 域关系演算
  • 具有关系代数和关系演算双重特点的语言：结构化查询语言SQL

一个关系数据语言能够表示关系代数可以表示的查询，称为完备的。上述的都是完备的。

关系完整性

基本定义

数据库的完整性是指数据的正确性和相容性。

分类

实体完整性：基本关系的主属性不能取空值。 参照完整性：基本关系的外码要么取空值，要么等于相应主码的值。 用户定义的完整性：具体关系数据库的用户定义的约束条件，反映语义要求。

应当实现的功能

  • 定义功能：提供定义完整性约束条件的机制。
  • 检查功能：检查用户发出的操作请求是否违背了完整性约束条件。
  • 违约处理：如果发现用户的操作请求使数据违背了完整性约束条件，则采取一定的动作来保证数据的完整性。
    • 拒绝：实体完整性、用户定义完整性。
    • 级联操作：参照完整性
    • 设置为空值：参照完整性

关系代数

集合运算

略，同集合论

关系运算

设$R_1(A_1，A_2，\ldots，A_n)$和$R_2(B_1，B_2，\ldots，B_m)$为关系，属性全集$U = \{A_1，A_2，\ldots，A_n，B_1，B_2，\ldots，B_m\}$

记：

  • $t[A_i]$为元组t分量
  • $t[A] = (t[A_1]，t[A_2]，\ldots，t[A_n])$
  • $\overparen{t_rt_s} = (t_r[A_1]，t_r[A_2]，\ldots，t_r[A_n]，t_s[B_1]，t_s[B_2]，\ldots，t_s[B_n])$

  • 象集$Z_x = \{t[Z]\mid \forall t\in R，t[X] = x\}$，X为一属性组

  • 选择：$\sigma_F(R) = \{t\mid t\in R，F(t)\}$
  • 投影：$\Pi_A(R) = \{t[A]\mid t\in R\}$
  • 连接：$R_1 \underset{F}{\Join} R_2 = \{\overparen{t_rt_s}\mid t_r\in R_1，t_s\in R_2，F(t_r，t_s)\}$
    • 等值连接：$F(t_r，t_s) \equiv t_r[A] = t_s[B]$
    • 自然连接：特殊的等值连接，连接后去重$R_1\Join R_2 = \{\overparen{t_r t_s}[U]\mid t_r\in R_1，t_s\in R_2，t_r = t_s\}$
    • 左外连接：$R_1 ⟕ R_2 = R_1\Join R_2 \cup ((R - \Pi_{R_1}(R_1\Join R_2)) \times null^m)$
    • 右外连接：$R_1 ⟖ R_2 = R_1\Join R_2 \cup (null^n \times (R - \Pi_{R_2}(R_1\Join R_2)))$
    • （全）外连接：$R_1 ⟗ R_2 = R_1 ⟕ R_2 \cup R_1 ⟖ R_2$
  • 除：$R_1 \div R_2 = \{t[U_{R_1} - Y]\mid t\in R_1，\Pi_Y(R_2)\subseteq Y_{t[U_{R_1} - Y]}\}$，其中Y为选定的属性组，$Y \subseteq U_{R_1} \cap U_{R_2}$

数据库安全性

数据库的不安全因素

为保护数据库以防止不合法使用所造成的数据泄露、更改或破坏，要考虑：

  • 非授权用户对数据库的恶意存取和破坏
  • 数据库中重要或敏感的数据被泄露
  • 安全环境的脆弱性

安全标准

常见安全标准

  • 1985年美国：TCESC（桔皮书）
  • 1991年欧洲：ITSEC
  • 1993年加拿大：CTCPEC
  • 1993年美国：FC
  • 1993年起：CC通用准则

数据库安全标准：

  • TCSEC/TDI 紫皮书：D——C1（自主安全保护、DAC）——C2（受控的存取保护）-B1（标记安全保护、MAC）-B2（结构化保护）-B3（安全域）-A（验证设计）
  • CC：EAL1~EAL7：功能测试——结构测试——系统地测试和检查——系统地设计、测试和复查——半形式化设计和测试——半形式化验证的设计和测试——形式化的设计和测试

安全控制

  • 用户身份鉴别：系统核对用户身份。分为静态口令、动态口令、生物特征鉴别、智能卡鉴别等。
  • 存取控制：定义用户权限并登记到数据字典、合法用户检查
    • 用户权限=数据库对象+操作类型
    • DAC：自主存取控制：用户拥有权限，授予、收回权限
    • MAC：对象拥有密级（TS、S、C、P），用户拥有许可证，读需要许可证≥密级，写需要许可证≤密级。
  • 视图机制：不同用户不同视图，为无权用户隐藏保密信息。
  • 审计：自动记录操作的审计日志。
  • 数据加密：存储加密、传输加密

SQL

基本概念

$\overset{Data Definition Language}{数据定义语言}$：定义和管理数据库中的数据结构和对象。

视图——基本表——存储文件三级结构。

特点

  • 综合统一：集模式数据定义语言、外模式数据定义语言、数据存储有关的描述语言、数据操纵语言为一体的统一语言
  • 高度非过程化/结构化
  • 面向集合的操作模式
  • 以同一种语法结构提供多种使用方式
  • 语言简洁，易学易用

语法

注：下方标记？的为非标准功能

特殊单词

级联操作

  • RESTRICT：存在依赖时取消/拒绝执行
  • CASCADE：同时对依赖执行

数据类型<Data type> |数据类型|定义| |-|-| |CHAR(n)，CHARACTER(n)|定长n字符串| |VARCHAR(n)，CHARACTERVARYING(n)|最长n字符串| |CLOB|长字符串| |BLOB|二进制数据| |INT/INTEGER|4B整数| |SMALLINT|2B整数| |BIGINT|8B整数| |NUMERIC(p，d)/DECIMAL(p，d)/DEC(p，d)|p位整数和d位小数| |REAL|单精度浮点数| |DOUBLE PRECISION|双精度浮点数| |FLOAT(n)|至少n精度的浮点数| |BOOLEAN|布尔值| |DATE|日期| |TIME|时间| |TIMESTAMP|时间戳| |INTERVAL|时间间隔|

次序

  • ASC：升序，默认
  • DESC：降序

重复

  • DISTINCT：去重
  • ALL：不去重，默认

检查合法性

  • WITH CHECK OPTION：在操作时检查数据的合法性
  • WITH GRANT OPTION：在授权时检查数据的合法性

通配符

  • %：匹配0个或多个字符
  • _：匹配一个字符

运算符

运算符 定义
+ 加法
- 减法
* 乘法
/ 除法
% 取余
|| 字符串连接
& 位与
| 位或
^ 位异或
~ 位取反
<< 左移
>> 右移
= 等于
!= 不等于
< 小于
> 大于
<= 小于等于
>= 大于等于
AND 逻辑与
OR 逻辑或
NOT 逻辑非

谓词

谓词 定义
IS NULL 空值
IS NOT NULL 非空值
IN 在集合中
LIKE 模糊匹配
BETWEEN 在区间内
EXISTS 存在
ALL 满足所有谓词
SOME 满足任意谓词
ANY 满足任意谓词

ALL SOME ANY 必须与比较预算符连用。

聚集函数

聚集函数 定义
COUNT 计数
MAX 最大值
MIN 最小值
SUM 求和
AVG 平均值

特殊的：COUNT(*)表示计算行数。

模式

定义：<Schema create> ::= CREATE TABLE [<Schema name>] AUTHORIZATION <AuthorizationID> [<Table create> | <View create> | <Grant>]

  • <Schema name>默认为<AuthorizationID>

删除：DROP SCHEMA <Schema name> {RESTRICT | CASCADE}

基本表

定义：CREATE TABLE [<Schema name>.]<Table name> "("<Column name> <Data type> [<Column Constraint>] [， <Column name> <Data type> [<Column Constraint>]]... [，<Table constraint>]]")"

修改：ALTER TABLE <Table name> [ADD [COLUMN] <Column name> <Data type> [<Column Constraint>]] [ADD <Table constraint>] [DROP [COLUMN] <Column name> {RESTRICT | CASCADE}] [DROP CONSTRAINT <Table constraint name> {RESTRICT | CASCADE}] [ALTER COLUMN <Column name> <Data type>]

删除：DROP TABLE <Table name> {RESTRICT | CASCADE}

插入元组：INSERT INTO <Table name> "("<Column name> [， <Column name>]...")" {VALUES "("<Value> [， <Value>]...)")" | <select>}

修改元组：UPDATE <Table name> SET "("<Column name> = <Value> [， <Column name> = <Value>]...")" [WHERE <Where condition>]

删除元组：DELETE FROM <Table name> [WHERE <Where condition>]

索引

定义：CREATE [UNIQUE] [CLUSTER] INDEX <Index name> ON <Table name> "("<Index attribute> [ASC | DESC] [， <Index attribute> [ASC | DESC]]...")"

修改：ALTER INDEX <Index name> RENAME TO <Index name>

删除：DROP INDEX <Index name>

查询

SELECT [ALL | DISTINCT] {({<Column expression> [AS <name>]} [， {<Column expression> [AS <name>]}]...) | *}

FROM {({<Table name> | <View name>} [AS <name>] [， {<Table name> | <View name>} [AS <name>]]...) | ( (<select>) [AS] <name>)}

[WHERE <Where condition>]

[GROUP BY <Column name> [HAVING <Group condition>]]

[ORDER BY <Column name> [ASC | DESC] [， <Column name> [ASC | DESC]]...]

其中的<select>称为子查询，分为：

  • 相关子查询：子查询的WHERE子句中引用了外部查询的表，执行依赖于外部查询。
  • 不相关子查询：

视图

定义：CREATE VIEW <View name> [<Column name> [， <Column name>]...] AS <select> [WITH CHECK OPTION]

删除：DROP VIEW <View name> [CASCADE]

对视图的修改等操作等同于对表的修改等操作。

完整性约束

实体完整性约束：PRIMARY KEY，PRIMARY KEY"("<Column name> [， <Column name>]...")" 参照完整性约束：FOREIGN KEY "("<Column name>")" REFERENCES <Table name>"("<Column name>")" 用户定义的完整性：NOT NULL，UNIQUE，CHECK <check contidion> 完整性约束子句定义：CONSTRAINT <Constraint name> <Constraint type> "("<Column name> [， <Column name>]...")" 完整性约束子句删除：ALTER TABLE <Table name> DROP CONSTRAINT <Constraint name>

授权

授予：GRANT <Privilege> [， <Privilege>]... ON <type> <name> [， [<type> <name]]... TO <AuthorizationID> [， <AuthorizationID>]... [WITH GRANT OPTION]

收回：REVOKE <Privilege> [， <Privilege>]... ON <type> <name> [， [<type> <name]]... FROM <AuthorizationID> [， <AuthorizationID>]... [CASCADE | RESTRICT]

创建角色：CREATE ROLE <Role name>

授权角色：GRANT <Privilege> [， <Privilege>]... ON <type> <name> [， [<type> <name]]... TO <Role name> [， <Role name>]...

角色授予用户：GRANT <Role name> [， <Role name>]... TO <AuthorizationID> [， <AuthorizationID>]... [WITH ADMIN OPTION]

收回角色授权：REVOKE <Privilege> [， <Privilege>]... ON <type> <name> [， [<type> <name]]... FROM <Role name> [， <Role name>]...

？创建用户：CREATE USER <AuthorizationID> [WITH] {DBA | RESOURCE | CONNECT}

审计

？启用审计：ADULT <Privilege> [， <Privilege>]... ON <name>>

？禁用审计：NOADULT <Privilege> [， <Privilege>]... ON <name>

嵌入式SQL

编译流程：

  • 预编译：DBMS预处理程序将嵌入式SQL语句转换为宿主语言
  • 编译：宿主语言编译

C语言嵌入式语句：EXEC SQL <SQL statement>;

JAVA嵌入式语句：# SQL {<SQL statement>};

通信区定义：INCLUDE SQLCA

  • SQLCA.SQLCODE用于指示操作是否成功

主变量定义：BEGIN DECLARE SECTION END DECLARE SECTION

  • 主变量使用时前面加:
  • 使用时主变量后可附加使用一个指示变量

游标：DECLARE <Cursor name> CURSOR FOR <SQL statement>

打开游标：OPEN <Cursor name>

关闭游标：CLOSE <Cursor name>

遍历游标：FETCH <Cursor name> INTO <Variable name> [， <Variable name>]...

建立数据库连接：SET CONNECTION TO {<Connection name> | DEFAULT}

关闭数据库连接：DISCONNECTION {<Connection name> | DEFAULT}

提交更新：COMMIT WORK

执行动态SQL语句：EXECUTE IMMEDIATE <Variable name>

准备动态SQL语句：PREPARE <Statement name> FROM <Variable name>

  • 在被准备的语句<Variable name>中用?代替参数

执行准备好的动态SQL语句：EXECUTE <Statement name> [INTO <Variable name>] USING <Variable name>

事务

开始事务：BEGIN TRANSACTION

提交事务：COMMIT

回滚事务：ROLLBACK

二、数据库应用

关系数据理论

数据库常见问题

  • 数据冗余
  • 更新异常
  • 插入异常
  • 删除异常

关系数据理论引入了对关系数据库的规范化理论。

数据依赖

关系的内部属性之间的约束关系。是语义上考虑的。

函数依赖：对属性组X和Y，该关系模式的任一关系中不存在两个元组t1和t2，使得$t1[X] = t2[X]$且$t1[Y] \neq t2[Y]$，即属性组X和Y构成函数关系$F:X \rightarrow Y$，记作$X \rightarrow Y$。此时X为决定因素。否则记为$X \not \rightarrow Y$

平凡函数依赖：$X \rightarrow Y$且$Y \subseteq X$，否则为非平凡的。

若$X \rightarrow Y$且$Y \rightarrow X$，则记为$X \leftarrow \rightarrow Y$。

完全函数依赖：$X \rightarrow Y$ 且$\forall X^\prime \subsetneqq X，X^\prime \not \rightarrow F$，记作$X \overset{F}{\rightarrow Y}$。否则为部分函数依赖，记为$X \overset{P}{\rightarrow Y}$。

传递（函数）依赖：若$X \rightarrow Y \wedge Y \not \subseteq X, Y \rightarrow Z \wedge Z \not \subseteq Y$，则Z传递依赖于X，记作$X \overset{传递}{\rightarrow} Z$

多值依赖：当属性组A的值确定时，属性组B的值与剩下的属性组无关，称为$A \rightarrow \rightarrow B$。

  • 传递性
  • 对称性
  • 函数依赖是特殊情况

平凡的多值依赖：$U = A \cup B$

码

候选码：关系模式的属性组全体完全函数依赖于的属性（组）。

超码：关系模式的属性组全体部分函数依赖于的属性（组）。

主码：一个候选码。

主属性：任意候选码的元素。

范式

关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。

范式名 要求 意义
1NF 属性/分量不可分 -
2NF 非主属性完全函数依赖于任意一个候选码 解决插入、修改、删除异常
3NF 不存在码X、属性组Y、非主属性组Z使得Y函数依赖于X且Z非平凡函数依赖于Y 不存在传递依赖。解决插入、修改、删除异常
BCNF 每个非平凡函数依赖的决定因素都包含码 尽可能消除函数依赖
4NF 被非平凡多值依赖的属性组都有码 不存在非平凡非函数依赖的多值依赖
5NF - 消除连接依赖

投影分解法

通过投影运算将原关系拆分为若干关系，以解决常见问题。

投影分解法依1NF->2NF->3NF->BCNF->4NF的顺序，依次针对每种范式的要求进行。

Armstrong公理系统

若满足一组函数依赖F的关系模式中存在函数依赖$X \rightarrow Y$，那么F逻辑蕴含$X \rightarrow Y$。

自反律：F逻辑蕴含每个平凡函数依赖。

增广律：F逻辑蕴含$X\rightarrow Y$，对属性组Z，有F逻辑蕴含$X\cup Z \rightarrow Y\cup Z$。

传递律：F逻辑蕴含的函数依赖的传递函数依赖被F逻辑蕴含。

由此关于函数依赖形成命题逻辑推理系统。

合并规则：$X \rightarrow Y \wedge Y \rightarrow Z \Rightarrow X \rightarrow Z$

伪传递规则：$X\rightarrow Y \wedge W\cup Y\rightarrow Z \Rightarrow X\cup W \rightarrow Z$

分解规则：$X\rightarrow Y \wedge Z \subseteq Y \Rightarrow X \rightarrow Z$

闭包：F所逻辑蕴含的函数依赖的全体。记作$F^+$。所有逻辑蕴含的、决定因素为X的函数依赖的右侧Y的全体。记作$F_X^+$。

如果函数依赖集F、G满足$F^+ = G^+$，那么F与G等价。

Armstrong公理系统是有效的（Armstrong推理规则正确）、完备的。

极小/最小覆盖：某一函数依赖G满足：

  • G的所有函数依赖右侧仅含有一个属性。
  • G的子集不与G等价
  • 令 G中的任意（一个）部分函数依赖 被 该函数依赖的决定因素的真子集替换的函数依赖 替换得到的集合不与G等价。

模式分解

无损连接性：关系模式的任一关系都等于该分解下所有子投影的自然连接。保证达到4NF

保持函数依赖：关系模式的函数依赖的闭包的该分解下所有子函数依赖的闭包的并。保证达到3NF

数据库设计

相关概念

涉及到的人员：设计人员、操作员、程序员、用户

实体联系图ER图：描述实体型-属性-联系的一种方法。

  • 矩形表示实体型，内写实体名。
  • 椭圆表示属性，内写属性名，用无向边与实体型连接。
  • 菱形表示联系，内写联系名，用无向边与实体型连接，并标注联系的类型：一对一1:1、一对多1:n和多对多m:n。

设计方法和步骤

需求分析

了解与分析用户需求，形成数据字典。

数据字典：数据项、数据结构、数据流、数据存储和处理过程，是关于数据库中数据的描述。是数据的最小组成单位。

概念结构设计

通过数据抽象形成概念结构（尤其是E-R图）。主要有自顶向下、自底向上、逐步扩张、混合策略四种设计策略。

E-R图的集成步骤：

  • 合并
    • 解决冲突：属性冲突、命名冲突、结构冲突
    • 去除冗余：分析法、规范化理论法
  • 修改和重构

概念结构：信息世界的结构，即概念模型。

属性：不可分；不能与实体型具有联系。

逻辑结构设计

把概念结构设计阶段设计好的基本E-R图转换为与选用的DBMS产品所支持的数据模型相符合的逻辑结构。

步骤为：

  • 将概念结构转换为关系模型。
    • 1:1型转换为一个关系模式，或与任意一端的关系模式合并;
    • 1:n型转换为一个多对一的关系模式，或与n端的关系模式合并;
    • m:n型转换为一个多对多的关系模式；
    • 3个及以上实体型间的联系转换为一个关系模式；
    • 相同码的实体型合并为一个关系模式。
  • 优化数据模型。
    • 极小化数据依赖；
    • 模式分解；
    • 规范化。

同时要考虑设计用户子模式

物理结构设计

物理结构：数据库在物理设备上的存储结构和存取方法，依赖特定DBMS。

要为一个给定的逻辑数据模型选取一个最适合应用要求的物理结构。步骤：

  • 确定数据库的物理结构。
  • 对物理结构进行评价，评价的重点是时间和空间效率。

存取方法由有：B+Tree索引、hash索引、聚簇方法

确定存储结构：指确定数据的存放位置和存储结构，综合考虑存取时间、存储空间利用率和维护代价3个方面。

数据库实施

考虑：

  • 数据载入；
  • 应用程序的编码和调试；
  • 试运行。

数据库运行和维护

考虑：

  • 数据库转储和恢复；
  • 数据库安全性、完整性控制；
  • 数据库性能监督、分析与改造；
  • 数据库的再组织、重构造。
    • 再组织：重新安排存储位置、回收垃圾、减少指针链等，提高系统性能。
    • 重构造：部分修改数据库的模式和内模式,即修改原设计的逻辑和物理结构。

三、数据库实现原理

查询处理与优化

  • 查询分析：扫描-词法分析-语法分析
  • 查询检查：语义检查、安全性检查、完整性初步检查，形成查询树
  • 查询优化：物理优化、代数优化
  • 查询执行：代码生成、执行

查询优化概述

  • 把查询转换成某种内部表示，通常用的内部表示是语法树。
  • 把语法树转换成标准（优化）形式，即利用优化算法把原始的语法树转换成优化的形式。
  • 选择低层的存取路径。
  • 生成查询计划，选择所需代价最小的计划加以执行。

代数优化

表达式等价变换

略

查询树的启发式

  • 选择先做
  • 投影选择同时做
  • 投影同相邻双目运算结合
  • 选择与笛卡尔积结合形成连接
  • 找公共子表达式

物理优化

基于启发式规则

小关系：全表扫描 大关系：

  • 主属性等于：索引扫描
  • 非主属性=或属性上的其他查询：数目少索引扫描，否则全表扫描
  • AND连接：组合索引、一般索引、全表扫描
  • OR连接：全表扫描

选取合适的连接操作：

  • 排序合并
  • 索引连接
  • hash join
  • 嵌套循环

基于代价

计算代价

基于语义

略

事务处理

事务的概念

事务是一组操作的集合，要么全部执行/提交，要么全部取消/回滚，是一个不可分割的工作单位。 特点：

  • Atomicity原子性：事务中的操作要么全部执行，要么全部取消
  • Consistency一致性：一致性状态之间变化
  • Isolation隔离性：事务之间互不干扰
  • Durability持续性：事务完成则永久改变数据库

故障：数据库本身破坏/数据出错

  • 事务内部故障
  • 系统故障
  • 介质故障
  • 计算机病毒

事务是并发控制的基本单位。

数据库恢复技术

冗余数据建立

  • 数据转储：利用后备副本。分为静态转储、动态转储；增量转储、海量转储
  • 日志文件：记录事务引起的更新。先登记日志再更新数据。登记时按时间顺序。
    • 以记录为单位：开始标记-结束标记-更新，都是日志记录（事务标识-操作类型-操作对象-旧值-新值）。
    • 以数据块为单位：事务标识-数据块

恢复策略

  • 事务故障：反向扫描、执行逆操作，直至事务开始标记
  • 系统故障：正向扫描，建立已提交（重做）-尚未完成（撤销）两个事务队列。撤销未完成事务。重做已完成事务。
  • 介质故障：装入最新的后备副本（恢复到最近一致性状态）和日志文件副本，重做已完成事务。

检查点记录

一种新的日志记录。内容：

  • 正在执行事务
  • 事务的最近日志记录的地址。

周期性的建立检查点：

  • 写入日志
  • 写入检查点
  • 数据记录写入数据库
  • 写入重新开始文件

恢复时（最近检查点起）：正向扫描、建立已提交（重做）-尚未完成（撤销）两个事务队列，然后处理：

  • 检查点之前提交：无视
  • 检查点之后提交、之前开始：重做
  • 检查点之后提交：撤销

优势：

  • 从检查点开始扫描日志即可，缩短扫描时间。
  • 减少了恢复时重做的事务个数。

数据库镜像

根据DBA的要求，自动把整个数据库或者其中的部分关键数据复制到另一个磁盘上。每当主数据库更新时，DBMS自动把更新后的数据复制过去，即DBMS自动保证镜像数据与主数据的一致性。

用途：

  • 用于数据库恢复。
  • 提高数据库的可用性。

数据库并发控制

并发问题

为了保证事务的一致性和隔离性，处理事务并发存取时的同时读写/写写统一数据问题。表现为：

  • 修改丢失
  • 不可重复读
  • 读脏数据

（封）锁

事务T在对某个数据对象操作之前，对其加锁，便有一定的控制（其他的事务不能更新或读取此数据对象）。

基本锁类型

  • 排他锁/写锁/X锁：事务T读取和修改，不能加锁
  • 共享锁/读锁/S锁：事务T只读，能加S锁

封锁协议：

  • 一级：修改加X锁，直至事务结束。防止修改丢失、事务可恢复。
  • 二级：一级+读加S锁，直至读完。防止读脏数据。
  • 三级：一级+读加S锁，直至事务结束。防止不可重复读、读脏数据。

活锁：事务可能因为锁而等待时间太长/永远等待。采用先来先服务解决。

死锁：事务间因为锁而互相等待。 解决：

  • 预防：
    • 一次封锁法：全部申请
    • 顺序封锁法：按预先规定的数据对象申请顺序申请
  • 诊断与解决：
    • 超时法：事务等待时间过长
    • 等待图法：画等待图，环=死锁
  • 撤销：撤销代价最小的事务

并发调度的正确性

调度的可串行化：与某种串行执行结果相同。即正确的调度。

调度的可串行性：可串行化的并发执行。

冲突操作：不同事务同时对同一个数据读写/写写。

冲突可串行化：交换不冲突操作的顺序可串行化。冲突可串行化必然可串行化。

两段锁协议

先全部申请，再全部释放。

任何对遵循两段锁协议的事务的并发调度都是可串行化的。

锁粒度

不同级别的数据库对象形成多粒度树。对一个节点加锁（显式加锁）则所有子节点加锁（隐式加锁）。

意向锁：用来提高封锁子系统的效率。表示下层节点将会加锁。加锁必须为所有上层节点加相应意向锁。

  • 意向共享锁/IS锁：子节点将加S锁。
  • 意向排他锁/IX锁：子节点将加X锁。
  • 共享意向排他锁/SIX锁：加S锁，加IX锁。

锁的相容矩阵

先加列上的锁，是否可以再加行上的锁？

  S X IS IX SIX
S Y N Y N N
X N N N N N
IS Y N Y Y Y
IX N N Y Y N
SIX N N Y N N