数据库原理笔记

此份笔记是本人学习过程中自己总结记录的，其内容受到课堂教学内容、采用教材、个人认知水平的影响。虽然笔者力图保证内容准确以及易于理解（起码自己能看懂），但难免存在谬误或者渲染问题。非常欢迎您通过邮件等方式联系我修改，让我们一起让这份笔记变得更好！

第一章绪论

数据库管理系统（DBMS）由一个互相关联的数据的集合和一组用以访问这些数据的程序组成。这个数据集合通常称之为数据库。DBMS 的主要目标是提供方便、高效地提取数据库信息的途径。

数据库管理系统面向：

相对庞大的数据集合。所以需要考虑如何合理地设计存储结构以及实现操作机制，还有减少冗余信息的存在等。
具有很高价值的数据集合。所以需要保证信息的安全，提供权限管理以及系统崩溃时的保障。
常常同时被多个用户或应用系统访问的数据集合。所以要考虑同步和可能存在的数据不一致问题。

传统的文件处理系统（文件系统+程序）存储机构信息的过程中，出现许多弊端：

数据冗余和不一致性：同一个数据可能出现在多个地方。要更改这个数据也要更改多个地方，否则会导致数据不一致
数据访问困难：对于特殊的要求（如找出满足某个条件的学生）只能编写特定的程序处理，缺乏通用的方式。
数据孤立：数据可能分散在多个不同的文件中，难以同时读取。
完整性问题：数据可能要满足某种一致性约束。当这种约束涉及不同文件的多个数据项时，很难实现。
原子性问题：一些操作需要是原子的（比如转账时，付款和收款一起必须是原子的，要不都完成，要不都不发生），但是难以实现。
并发访问异常：多用户访问/修改，可能造成的数据不一致或破坏约束
安全性问题：难以实现权限的细粒度管理

这些各种各样的问题促成了数据库系统的初始发展和基于文件的应用向基于数据库的应用的变迁。

数据库结构的基础是数据模型。数据模型描述了数据的结构、数据语义、一致性约束等。

数据模型有四类：

关系模型。用二维表的集合来表示数据与数据之间的关系。每个二维表有多个列，每列有唯一的列名。一行就称为一个记录。
实体——联系模型（E-R 模型）。主要用于数据库设计阶段。E-R 数据模型使用称为实体的基本对象的集合以及这些对象之间的联系。
半结构化数据模型。这个数据模型允许数据项有不同的结构和属性。JSON 和 XML 常用来表示这种半结构化的数据。
基于对象的数据模型。可以看成对关系模型的扩展，引入了封装、方法和对象标识等概念。

为了实现高效检索数据，数据库中常常使用复杂的数据结构来表示数据。我们通过以下几个层次的数据抽象来隐藏数据的复杂性，使得用户可以方便地访问和操作数据：

物理层：最低层次的抽象，描述数据在磁盘上的存储结构、索引、文件组织等。
逻辑层：比物理层高一层的抽象，描述数据的逻辑结构和关系。
视图层：最高层次的抽象，描述用户能够看到的数据视图。不同的用户可以有不同的视图。视图层提供了数据的定制化表示，隐藏了底层的复杂性。

alt text

特定时刻存储在数据库中信息的集合称为数据库的一个实例，而数据库的总体设计称作数据库模式（schema）。

按照上面提到的层次，物理模式在物理层描述了数据库的设计，逻辑模式在逻辑层描述数据库的设计。数据库在视图层的模型有时也称为子模式，可以有多种，描述了数据库的不同视图。

一般程序员关注的是逻辑模式。物理模式隐藏在逻辑模式之下，并且通常可以在应用程序丝毫不受影响的情况下被轻易更改。如果应用程序不依赖与物理模式，即便物理模式改变了它们也无需重写，它们就被称为具有物理数据独立性。

数据库系统提供数据定义语言（DDL）来定义数据库模式，并提供数据操纵语言（DML）来表达数据库的查询与更新。这两者构成了数据库语言（例如 SQL 语言）的不同部分。

可以通过一系列特定的 DDL 语句来说明数据库系统所采用的存储结构和访问方式。

存储在数据库中的数据值还必须满足一些一致性约束，DDL 语言也提供了指明这些约束的工具。这里的约束包括：

域约束：每个属性对应一个所有可能取值构成的域。
引用完整性：例如一个 course 关系中某个记录上的 dept_name 值，必须要出现在 department 关系的某个记录的 dept_name 值中，这就叫做引用完整性。
授权：不同用户拥有不同权限，读/写/插入/删除等。

执行 DDL 语句后会产生一些输出，这些输出放在数据字典中，它是一个数据库中的特殊表或一组表，用于存储关于数据库结构的信息。它包含了数据库中所有对象的定义和描述，例如表、视图、索引、约束、存储过程等。

数据字典中存储着元数据，元数据是数据（数据库中实际存储的数据）的数据，提供了数据描述和上下文信息，使数据更容易理解和使用（可以理解为数据字典就像配置文件）。

数据操纵语言使得用户可以访问或操纵按照某种数据模型组织起来，基本的动作——增删查改。

数据操纵语言包括过程化的 DML和声明式的 DML。前者要求用户指定需要什么数据以及如何获得这些数据，后者只需要指定需要什么数据。

对于声明式 DML，由于用户不指明如何获得数据，所以必须由数据库系统找出一种访问数据的高效途径。

数据库系统的结构如图所示：

database-structure

最底层是物理磁盘存储。

存储管理器负责与文件管理器进行交互。原始数据通过操作系统提供的文件系统存储在磁盘上。存储管理器将各种 DML 语句翻译为底层文件系统命令。

查询处理器中的 DML 编译器除了将 DML 语句翻译为一系列查询执行引擎能理解的低级指令的执行方案。DML 编译器还进行查询优化，也即从几个候选执行计划中选出代价最小的那个。

事务是数据库应用中完成单一逻辑功能的操作集合。每一个事务是一个既具有原子性又具有一致性的单元。

第二章关系数据库

1、关系数据库的结构

关系数据库是表的集合，每个表都有唯一的名字。一个表就代表着一种关系（relation）。

每一张表都有若干列，每一列有唯一的列名，一列就代表着一种属性（attribute），所以列名就是属性名。每个属性都存在一个允许取值的集合，称为该属性的域。如果一个域中的元素，都是不可再分的单元，就称该域是原子的。

每一张表也有若干行，表中的一行代表一组值之间的某种联系。这一组值就构成了一个元组（tuple）。空值是一个特殊的值，表示值未知或者并不存在。

table

2、关系模式

之前已经提到，数据库模式指数据库的逻辑设计，数据库实例指给数据库的一个快照。

对于关系数据库而言，如果关系相当于程序设计语言中的变量，关系模式就相当于程序设计语言中的类型定义。一个关系模式由一个属性列表及各属性对应的域构成。

例如上表是 instructor 关系，其关系模式是instructor(ID, name, dept_name, salary)。上面的表就是一个实例。

3、码

关系是一个元组的集合，一个关系中没有两个元组在所有属性上的取值完全相同。

超码（superkey）是一个或者多个属性的集合，这个集合内的属性组合在一起可以在一个关系中唯一地标识出一个元组。显然，一个关系至少有一个超码，也即所有属性的集合。

令 $R$ 为关系 $r$ 的属性集合。如果 $R$ 的子集 $K$ 是 $r$ 的一个超码，则任意 $K$ 的超集也是 $r$ 的一个超码。

如果 $K$ 的任意真子集都不是超码，也即 $K$ 是最小的超码，就称 $K$ 为候选码（candidate key）。候选码可以有多个。

从候选码中选出一个，作为数据库中区分不同元组的主要方式，这个候选码就称之为主码（primary key）。主码只有一个，候选码可以有多个。选出主码之后，数据库中的元组就要满足一种约束——不能有两个元组在主码上的取值相同，所以主码也称为主码约束。

关系模式的表示中，习惯将主码属性放在前面，且用下划线标识，例如： $\text{classroom}(\underline{\text{building}},\underline{\text{room\_number}}, \text{capacity})$

另一种约束是外码约束。举一个例子：教师信息列表中，某个教师所属的部门必须是真实存在的部门，也即该部门必须存在于部门信息列表中。

一般地，从 $r_1$ 关系的 $A$ 属性集到 $r_2$ 关系的主码 $B$ 的外码约束（foreign-key constraint）表明：在任何数据库实例中， $r_1$ 中每个元组对 $A$ 的取值也必须是 $r_2$ 中某个元组对 $B$ 的取值。

$A$ 属性集被称为从 $r_1$ 引用 $r_2$ 的外码（foreign key）， $r_1$ 关系称为此外码约束的引用关系， $r_2$ 称为被引用关系。被引用属性集 $B$ 必须是被引用关系的主码。

更泛化的情况是引用完整性约束，仅要求引用关系中的任意元组在指定属性上出现的取值，出现在被引用关系中至少一个元组的指定属性上，不一定要是主码。

可以用模式图来表示带有主码和外码约束的数据库模式：

schema-graph

主码属性，用下划线标注
外码约束，用从引用关系的外码属性指向被引用关系的主码属性的箭头标注
引用完整性约束，用双头箭头来表示

4、关系代数

查询语言是用户用来从数据库请求获取信息的语言。查询语言可以分为命令式的、函数式的以及声明式的。

关系代数就是一种函数式查询语言。关系代数构成了 SQL 查询语言的理论基础。

关系代数由一组运算构成，这些运算接受一个或者两个关系作为输入，并生成一个新的关系作为结果：

选择运算：选出关系中满足给定谓词的元组。运算符用 $\sigma$ 表示，谓词写在下标中，关系写在括号里作为参数。

$\sigma_{\text{dept\_name="Physics"}}(\text{instructor})$

谓词里还可以用与或非，不等号等构造更复杂的谓词
投影运算：只保留某些属性。运算符用 $\prod$ 表示，想要保留的属性写在下标中，关系写在括号里作为参数。

$\prod_{\text{ID, name, salary}}(\text{instructor})$
笛卡尔积：结合两个关系的信息。运算符用 $\times$ 表示。如果关系 $r_1$ 有 $n_1$ 个元组，关系 $r_2$ 有 $n_2$ 个元组，则 $r_1\times r_2$ 有 $n_1n_2$ 个元组。通过改名来避免两个关系中同名属性的冲突。
连接运算：笛卡尔积和选择运算的结合。运算符考虑关系 $r(R), s(S)$ ，令 $\theta$ 为 $R\cup S$ 模式的属性上的一个谓词。

$r\Join_{\theta} s=\sigma_\theta(r\times s )$
集合运算：包括交 $\cap$ 、并 $\cup$ 、集差 $-$ 。
赋值运算：将某个关系代数运算的结果赋给一个临时的关系变量，运算符用 $\leftarrow$ 表示。

$\text{course\_fall\_2017}\leftarrow \prod_{\text{course.id}}(\sigma_{\text{semester="Fall"}\wedge \text{year}=2017}(\text{section}))$
更名运算：给一个关系代数表达式的结果命名。运算符用小写字母 $\rho$ 表示，想要的名字作为下标，关系代数表达式作为参数放在括号里。

$\rho_x(E)$

第三章初级 SQL

SQL 语言有几个部分：

DLL：定义以及修改关系模式、删除关系的命令
DML：查询信息，在数据库增删改元组
完整性：定义完整性约束的命令
视图定义：定义视图的命令
事务控制：定义事务的开始点和结束点的命令
嵌入式 SQL 和动态 SQL：定义 SQL 语句如何嵌入 C/C++等通用编程语言
授权：定义对关系和视图访问权限的命令

注：SQL 语言是大小写不敏感的，为了有更好的观感，本笔记中规定命令的关键字都用大写，属性名等用小写

3.1、基本类型

SQL 标准支持多种固有类型：

char(n)/character(n)：长度固定为 $n$ 的字符串
varchar(n)/character varying(n)：最大长度为 $n$ 的可变长字符串
int/integer：整数
smallint：小整数
numeric(p, d)：共 $p$ 位数字，其中小数部分为 $d$ 位的小数
real：浮点数
double precision：双精度浮点数
float(n)：精度至少为 $n$ 位数字的浮点数

3.2、基本模式定义

用CREATE TABLE命令来定义 SQL 关系，其一般形式为：

CREATE TABLE r(
  A1 D1 constraint1，
  A2 D2 constraint2,
  ...,
  An Dn constraintn,
  <完整性约束1> ,
  <完整性约束k>);

其中 $r$ 是关系名， $A_i$ 是关系 $r$ 的模式中的一个属性名， $D_i$ 是 $A_i$ 的域

完整性约束有：

PRIMART KEY(Aj, Ak, ...)：指定主码。主码属性必须是非空且唯一的
FOREIGN KEY(Al, Am, ...) REFRENCES s：指定外码。
NOT NULL：在某个属性上，约束该属性上不允许存在空值

一个实例：

CREATE TABLE department(
  dept_name VARCHAR (20),
  building VARCHAR (15),
  budget NUMERIC (12,2),
  PRIMARY KEY (dept_name));

向关系中插入、删除、更新元组，分别是INSERT, DELETE, UPDATE

DROP TABLE r是丢弃掉整张表；DELETE FROM r是删掉元组，但是仍然保留模式

ALTER TABLE r ADD A D，向已有关系中增加属性；ALTER TABLE r DROP A，删除属性

3.3、SQL 查询

SQL 查询的基本结构如下：

1
2
3

SELECT name
FROM instructor
WHERE depy_name='Comp.Sci.';

从FROM后列出的关系中，查询SELECT后跟的属性中，满足WHERE后跟的谓词的数据

默认查询结果是不去除重复的，也可以用ALL关键字显示指明：SELECT ALL dept_name

加上关键词DISTINCT，可以去除结果中的重复项：SELECT DISTICT dept_name

前面的例子是单关系查询，更一般的多关系查询：

1
2
3

SELECT name, course_id
FROM instructor, teaches
WHERE depy_name='Comp.Sci.' AND instructor.ID=teaches.ID;

可以理解为：

为FROM子句中列出的关系产生笛卡尔积
在步骤 1 的结果上应用WHERE子句中指定的谓词
对于步骤 2 的结果中的每个元组，输出SELECT子句中指定的属性

可以在FROM子句或者SELECT子句里面使用AS来进行更名：

1
2
3

SELECT T.name, S.course_id
FROM instructor AS T, teaches AS S
WHERE T.ID=S.ID;

谓词中还可以利用LIKE关键字来做字符串匹配：

1
2
3

SELECT dept_name
FROM department
WHERE building LIKE '%Waston_'

其中%匹配任意子串，_ 匹配任意字符

还可以用ESCAPE关键字来定义转移字符LIKE 'ab\%cd%' ESCAPE '\'，这匹配的是以ab%cd的所有字符串

可以用ORDER BY关键字，来让查询结果按顺序显示。DESC和ASC关键词分别指定升序和降序

1
2
3

SELECT *
FROM instructor
ORDER BY salary DESC, name ASC

两个 SQL 查询语句之间，还可以用集合运算。并、交、差分别是UNION, INTERSECT, EXCEPT

(
    SELECT course_id
    FROM section
    WHERE semester='Fall' AND year=2018
)
EXCEPT ALL
(
    SELECT course_id
    FROM section
    WHERE semester='Spring' AND year=2018
)

其中EXCEPT会执行集差运算之前自动去除输入中的重复项。如果想保留重复项，要用EXCEPT ALL

3.4、空值

空值给算术运算、比较运算和集合运算带来的特殊问题。需要扩展这三种运算以能处理空值。

对于算术运算，算术表达式的任意一个输入为空值，则整个表达式的结果也是空值。

对于比较运算，与空值进行比较式没有意义的，因为并不知道空值代表着什么。所以，新定义了一个unknown值。涉及空值的任何比较运算的结果被视为unknown，这是除了true, false之外的第三种逻辑值

由于WHERE子句中的谓词通常会对比较结果用布尔运算，引入unknown后，同样要对布尔运算进行拓展：

AND：true AND unknown=unknown, false AND unknown=false, unknown and unknown=unknown
OR：true OR unknown=true, false OR unknown=unknown, unknown OR unknown=unknown
NOT：NOT unknown=unknown

如果一个元组，用WHERE子句谓词计算出是unknown或者false，则这个元组不能被加入结果中

可以在谓词中用is unknown, is not unknown来测试比较结果是否为unknown

一个查询可以用SELECT DISTINCT子句，来去除结果中的重复元组。两个元组重复，指这两个元组对应的属性值都非空且相等，或者都为空。在集合的交、并运算中同理，只要元组在所有属性上取值相等，就被当成相同的元组，即使某些值为空。

这里对空值的处理与之前提到的不同。在谓词中，null=null会返回unknown。

3.5、聚集函数

聚集函数是以值集为输入，并返回单个值的函数。SQL 标准中五个固有的聚集函数是：AVG, MIN, MAX, SUM, COUNT

1
2
3

SELECT AVG (salary) AS avg_salary
FROM instructor
WHERE dept_name='Comp.Sci.'

有时做聚集之前先去重，就在属性名前加一个DISTINCT

1
2
3

SELECT COUNT (DISTINCT ID)
FROM teaches
WHERE semester='Spring' AND year=2018

还可以进行分组聚集，通过添加GROUP BY子句，按照后面跟的属性先分组，再对每一个分组进行聚集：

1
2
3

SELECT dept_name, AVG (salary) AS avg_salary
FROM instructor
GROUP BY dept_name;

分组聚集要确保，出现在SELECT子句中但没有被聚集的属性，只能是出现在GROUP BY子句中的属性。其他属性都被“聚集”掉了，或者分组时被合并掉了，不能再被选出了。

有时，我们还希望只筛选出满足条件的分组，此时可以再附加上HAVING子句：

SELECT dept_name, AVG (salary) AS avg_salary
FROM instructor
GROUP BY dept_name
HAVING AVG(salary)>42000;

这样，包括聚集、HAVING、GROUP BY的一个查询语句可以这样理解：

首先根据FROM子句计算出一个关系
如果有WHERE子句，将WHERE子句的谓词应用在刚才计算出来的关系上
如果有GROUP BY子句，按照该子句指定的属性进行分组
如果有HAVING子句，将其应用在每个分组上；不满足条件的分组会被去掉
最后根据SELECT子句产生查询结果，如果有聚集函数的就应用，得到单个结果元组。

聚集运算也需要考虑到空值和布尔值的问题。

除了COUNT以外的聚集运算，都会忽略掉空值。

对于空集，COUNT运算值为 0；其他的聚集运算会返回一个空值。

对于布尔值，有SOME和EVERY聚集运算可以运用于布尔值的集合（布尔值包括UNKNOWN），分别是计算析取和合取。

3.6、嵌套子查询

可以在WHERE子句中嵌套子查询：

SELECT DISTINCT course_id
FROM section
WHERE semester='Fall' AND year=2017 AND
  course_id IN (SELECT course_id
                FROM section
                WHERE semester='Spring' AND year=2018);

相对的，也可以用NOT IN运算符。IN和NOT IN不仅能用于关系，也可以用于枚举集合：

1 2	... WHERE name NOT IN ('Mozart', 'Einstein')

还可以利用SOME关键字，写关于比较的嵌套子查询：

SELECT name
FROM instructor
WHERE salary > SOME (SELECT salary
                     FROM instructor
                     WHERE dept_name='Biology');

-- 这个语句的意思是，查找薪资至少比某一个生物系老师高的老师的名字

另外也有<SOME、>=SOME等用法，=SOME等价于IN。

<>SOME并不等价与NOT IN，这个运算符的意思是，只要与子查询结果集中的某一个元素（非空）不同，就能返回真。NOT IN，是要与子查询结果集中全部都不一样才返回真。

同理ALL也有类似的运算符。=ALL不等价于IN，<>ALL等价于NOT IN。

可以用EXISTS、NOT EXISTS来判断子查询结果是否为空：

SELECT course_id
FROM section AS S
WHERE semester='Fall' AND year=2017 AND
  EXISTS (SELECT *
      FROM section AS T
      WHERE semester='Spring' AND year=2018 AND
              S.course_id=T.course_id);

--这个语句列出既在 2017 年秋季学期开设，又在 2018 年春季学期开设的课程

可见，来自外层查询的相关名称S 可以用到子查询中。使用了来自外层查询的相关名称的子查询被称作相关子查询。

用NOT EXISTS可以表达包含关系。例如关系 A 包含关系 B 可以表达为NOT EXISTS (B EXCEPT A)

UNIQUE关键字可以检测子查询结果是否存在重复元组，子查询结果中没有重复元组时返回TRUE。

子查询也可以放在FROM语句中，因为一个查询子句的结果总是一个关系。在FROM子句的子查询中新得到的属性（例如使用了聚合函数），可以在外层使用：

SELECT dept_name, avg_salary
FROM (SELECT dept_name, AVG(salary)
      FROM instructor
      GROUP BY dept_name)
      AS dept_avg(dept_name, avg_salary)
WHERE avg_salary>42000;

-- 这个语句列出平均薪水大于 42000 的那些系

WITH子句可以定义一个临时关系。这个临时定义的关系只对包含该WITH子句的查询语句能用：

WITH max_budget(value) AS
  (SELECT MAX(budget)
      FROM department)
SELECT budget
FROM department, max_budget
WHERE department.budget=max_budget.value;

-- 这个语句列出预算拥有最多预算的那些系。

SQL 允许子查询出现在返回单个值的表达式能出现的任何地方，如果这个子查询只返回一个包含单个属性的元组，这样的子查询称之为标量子查询：

SELECT dept_name,
  (SELECT COUNT(*)
    FROM instructor
    WHERE departmen.dept_name=instructor.dept_name)
    AS num_instructors
FROM department;

-- 这个语句可以列出所有的系以及每个系对应的教师数。

这里的特殊情况是，有时候我们的运算不需要依赖任何关系，也就不需要SELECT子句。为了不违反语法，可以用关键词DUAL，代表一个特殊的虚拟关系：

SELECT (SELECT COUNT(*) FROM teaches)/(SELECT COUNT(*) FROM instructor)
FROM DUAL;

-- 这个语句计算每位教师平均教授的课程段数

3.7、数据库的修改

删除请求的基本模式如下：

1 2	DELETE FROM r WHERE p;

删除语句只能作用于一个关系上。同样的，WHERE子句也可以像查询语句中一样复杂（嵌套子查询，使用复杂的谓词等）

插入请求的一个例子如下：

1 2	INSERT INTO course(course_id, title, dept_name, credits) VALUES ('CS-437', 'Database Systems', 'Comp. Sci', 4);

属性顺序不一定要按一开始定义好的来。没有被指定的属性将会被赋予空值。

也可以将某个查询语句的结果插入到关系中：

INSERT INTO instructor
  SELECT ID, name, dept_name, 18000
  FROM student
  WHERE dept_name='Music' AND tot_cred>144;

系统会先执行查询语句，再执行插入动作。

更新请求的一个例子如下：

1
2
3

UPDATE instructor
SET salary=salary*1.05
WHERE salary<17000

这里的WHERE子句也可以使用任何能在查询语句中合法的结构。

还可以使用CASE结构：

UPDATE ...
SET ...=
  CASE
    WHEN pred1 THEN result1
    WHEN pred2 THEN result2
    ...
    WHEN predn THEN resultn
    ELSE result0
  END

第四章中级 SQL

1、自然连接

考虑下面的查询语句：

1
2
3

SELECT name, course_id
FROM student, takes
WHERE student.ID=takes.ID;

是将两张表，按照 ID 对应起来，合成为一张表。这样的操作是很常见的，为了简化操作，SQL 中提供了一种叫做自然连接的操作。

自然连接运算作用于两个关系，并产生一个关系作为结果。自然连接只考虑在两个关系的模式中都出现的那些属性上取值相同的元组对（而笛卡尔积会将第一个关系的每个元组和第二个关系的每个元组进行串接）：

1	student NATURAL JOIN takes

结果先列出公共属性，再是只出现在第一个关系中的属性，然后是只出现在第二个关系中的属性。

也可以指定自然连接使用的公共属性：

1 2	SELECT name, title FROM (student NATURAL JOIN takes) JOIN course USING (course_id);

这样，即使有其他的公共属性且不相等，也不会影响元组的连接。

更一般的，可以用连接条件来表达：

1 2	SELECT * FROM student JOIN takes ON student.ID=takes.ID;

如果来自两个关系的元组满足ON后面的谓词，就说明它们是匹配的，可以连接起来。

2、外连接

假设有 student 和 takes 两个关系，其公共属性为 ID。但是某个学生没有选课，所以只出现在第一个关系上。加入我们要查看所有学生及其选课情况，如果使用自然连接，这个学生就不会出现在最后的结果中。

为了解决这个问题，我们利用外连接运算，它会在结果中创建包含空值的元组来保留那些在连接中会丢失的元组。相对的，之前提到的连接都是内连接。

一共有三种形式的外连接：

左外连接：只保留出现在连接运算左边的关系中的元组
右外连接：只保留出现在连接运算右边的关系中的元组
全外连接：保留出现在两个关系中的元组

以左外连接为例。首先，像之前一样计算出内连接的结果。然后，对于内连接的左侧关系中任意一个与右侧关系中任何元组都不匹配的元组 t，向连接结果或中加入一个元组 r。元组 r 的构造如下：

元组 r 从左侧关系得到的属性被赋值为元组 t 的值
元组 r 从右侧关系获得的属性全部被赋予空值

右外连接、全外连接可以直接类比。全外连接可以理解为左外连接和右外连接的并运算。

... NATURAL FULL OUTER JOIN ...
... NATURAL RIGHT OUTER JOIN ...
... NATURAL LEFT OUTER JOIN ...
... LEFT OUTER JOIN ... ON ...

ON和WHERE对于外连接的表现是不一样的。

ON条件是属于外连接声明的一部分，而WHERE不是。外连接是否补全缺少的元组，是根据ON决定的。

如果将ON后面的条件外移到WHERE中，而原来的ON变成永真，就不会补全缺少的元组了。

没有加OUTER关键字时，默认是内连接。也可以显式使用INNER关键字来指定内连接。

3、视图

让所有用户都能看到完整的数据库并不总是合适的。一个常见的需求是，要求某一个部门的成员只能看到一部分数据，可以创建视图来满足这一个需求：

1
2
3

CREATE VIEW faculty AS
  SELECT ID, name, dept_name
  FROM instructor

上面这个语句创建了一个名为 faculty 的视图关系。视图关系在概念上包含查询结果中的元组，但是并不进行与计算和存储，只有当这个视图关系被访问的时候，才会把其中的元组计算出来。

也可以显示指定视图关系的属性名。

与WITH的不同之处在于，视图一旦创建，再被显式删除之前就一直是可用的，由WITH定义的临时关系只在那个查询语句中可用。定义了视图关系可以在其他 SQL 查询/视图定义中直接使用。

3.1、物化视图

一些数据库也允许实际存储视图关系，这样的视图称为物化视图。如果实际关系发生了改变，视图也会跟着修改以保持最新。

保持物化视图一直在最新状态的过程称之为物化视图维护。维护的策略有：

构成视图定义的任何关系更新后，马上进行维护
视图被查询时，再进行维护
定期维护

对于频繁使用视图的应用，物化视图可以更快响应查询请求。

3.2、视图更新

由于视图名可以出现在关系名能出现的任何地方，自然会出现对视图进行更新的情况。

可以想见，对视图进行更新，本质上是要对构成视图定义的关系进行更新。但是对视图更新时，提供的新元组一般只包含视图关系的属性，而可能不包含所有构成视图定义的关系的属性。这个新元组，是无法插入到原关系中的。此时可以：

拒绝插入
用空值填充，插入到原关系中

更复杂的情况是，即便用空值填充，并插入到原关系中。但是由于谓词的存在，视图关系并不会包含这个新元组，相当于没有达到更新视图的目的，更新是无效的。

于是，除了有限的情况外，一般来说，视图是不允许更新的。

如果定义视图的查询满足以下条件，则称这个视图是可更新的：

FROM子句只包含一个关系
SELECT子句只包含这个关系的属性名，不包含任何表达式、聚集和DISTINCT声明
没有出现在SELECT子句中的任何属性，可以取空值
查询中没有出现GROUP BY和HAVING子句

这种情况下，可以在视图上进行更新、插入和删除操作。

即便如此，还是会出现原本的关系更新了，视图没变的情况。可以在是视图的定义中加入WITH CHECK OPTION子句，这样不满足查询语句的谓词的元组的插入操作会被拒绝，也就保证了能插入的元组一定会出现在视图中。

4、事务

一个事务（transaction）由查询和更新语句的序列组成。每一条 SQL 语句被执行时，就隐式地开始了一个事务。下面两条特殊的 SQL 语句可以结束一个事务：

COMMIT WORK：将事务的结果永久保存到数据库中。WORK是可选的。
ROLLBACK WORK：撤销事务中的所有更新操作，也即回滚操作。WORK是可选的。

一个事务能且只能由上面两个命令中的一个结束。数据库系统保证，当一个事务没执行完毕，但出现了各种故障时，如果还没有执行COMMIT，那么系统会自动执行ROLLBACK。执行了COMMIT之后，系统就不能再执行ROLLBACK。

所以，一个事务或者在完成其所有步骤后提交其操作，或者在不能成功完成其所有动作的情况下回滚其所有动作。通过这种方式，数据库提供了事务的原子性。

很多数据库系统的实现中，缺省状态下，每条 SQL 语句都自成一个事务，如果成功执行，会自动提交；如果出现错误，会自动回滚。无需显式地使用COMMIT和ROLLBACK。当然，也支持关闭这种“自动提交”模式。

也可以显示地开始一个事务，其中一个可能的语法是：

1
2
3

BEGIN ATOMIC
  ...
END

之间的语句就构成了一个事务。

也有一些数据库缺省状态下是不自动提交的，需要显式地使用COMMIT来提交事务。

5、完整性约束

完整性约束（integrity constraint）保证授权用户对数据库所做的修改不会导致数据一致性的丢失。与安全性约束相区别，安全性约束是保证只有授权用户才能访问数据库。

一般而言，完整性约束可以是关于数据库的任意谓词。大多数数据库系统，只允许用户组指定一些只需要极小开销就可以检测的完整性约束。

完整性约束可以作为创建关系命令CREATE TABLE中的一部分被声明。还也可以用ALTER TABLE table_name ADD CONSTRAINT constraint_name constraint命令来添加，系统首先检查当前关系是否满足这个约束，如果满足，就添加这个约束；否则，拒绝添加。

5.1、非空约束

空值在缺省情况下，是每个属性的合法值。但是有时候，我们希望某个属性不允许为空。这时，可以在属性定义的后面，加上非空约束NOT NULL。

1	name VARCHAR(20) NOT NULL

非空约束是域约束（限制属性值的取值范围）的一种，可能导致向一个被声明为非空的属性插入空值的操作都会被拒绝。

5.2、唯一性约束

唯一性约束形如：

1	UNIQUE (A1, A2, ..., An)

这个约束指明，(A1, A2, ..., An)构成一个超码，也就是说关系中没没有任何两个元组在列出的属性上完全相同。

声明了唯一性的属性允许为空值（除非显示指明为非空），因为空值不等于其他任何值（包括空值），这与前面对UNIQUE子句中对空值的处理是一样的。

5.3、CHECK 子句

在关系声明中，还可以加入形如CHECK(P)的子句。这个子句指明，关系中的每个元组都必须满足谓词 P。

只要CHECK子句不为假，其约束就是满足的，也就是说P为未知时，约束也是满足的。

CHECK子句可以加在属性定义后面，也可以加在关系定义的最后。

5.4、引用完整性

我们常常希望保证，一个关系（引用关系）中给定属性集合的值在另一个关系（被引用关系）中是存在的。这种约束称为引用完整性。外码是引用完整性约束的一种形式，其中被引用的属性构成被引用关系的主码。

外码子句FOREIGN KEY attr REFERENCES relation也可以作为创建表语句的一部分。缺省情况下，外码引用的是被引用关系的主码。也可以显示指定要引用的属性列表FOREIGN KEY (attr1, attr2, ..., attrn) REFERENCES relation(attr1, attr2, ..., attrn)，这种情况下，被指定的属性必须构成被引用关系的超码。

外码必须引用一组兼容的属性，也即，属性数量必须相同，对应属性的数据类型必须兼容。

考虑被引用关系中的某个元组被删除，此时引用完整性被违反（引用关系中的某个属性取值，在被引用关系中不存在）。这种情况下，可以有以下几种处理方式：

级联删除：同时删除引用关系中的相应，在外码子句后加上ON DELETE CASCADE子句来实现。如果有进一步引用，只要指定了级联删除，就会一直删除下去。
设空：在外码子句后加上ON DELETE SET NULL子句，将引用关系中的相应属性设为空值。
恢复默认值：在外码子句后加上ON DELETE SET DEFAULT子句，将引用关系中的相应属性设为缺省值。

更新的情况同理。

在一些特殊情况下，一个级联更新/删除所带来的对约束的违反，不能通过进一步的级联更新/删除来解决，这时，系统会终止这个事务并回滚。

5.5、事务中对完整性约束的违反

一个事务包括若干语句，在某一步之后可能会暂时违反完整性约束，但是最后是不会违反的。

例如有这样一个表：

CREATE TABLE person(
  name PRIMARY KEY,
  spouse REFERENCES person
)

如果我们先插入丈夫的元组，元组中妻子的名字还不在name中，此时违反了外码约束。但是等到插入妻子的元组后，就不会违反了。

缺省情况下，约束会被立即检查。我们可以将INITIALLY DEFERRED子句加在约束后，这样系统会等到事务结束时再检查完整性约束。对于被声明为可延迟的约束，SET CONSTRAINTS deferrable_list DEFERRED会隐式地成为事务的一部分，导致对这些约束的检查被推迟到事务结束时。

5.6、复杂 CHECK 子句与断言

CHECK子句中的谓词可以是包含子查询的任意谓词，例如：

CHECK (
  time_slot_id IN (
    SELECT time_slot_id
    FROM time_slot
  )
)

CHECK子句一般在属性定义后面或者关系定义的最后，是表级别的约束。

断言则更一般些，是数据库级别的约束，可以跨表定义。可以通过CREATE ASSERTION assertion_name CHECK P来定义断言。

要注意使用CHECK子句和断言的开销，涉及到的任何一个关系发生更新，都会触发检查。

6、SQL 的数据类型与模式

SQL 还支持的一些数据类型是：

1
2
3

DATE '2024-12-24'
TIME '12:00:00'
TIMESTAMP '2024-12-24 11:45:14.00'

CAST：系统可以进行一些数据类型之间的转换，对于不支持的转换，需要显示地使用CAST(type_a_value AS type_b)来将某个表达式转换为指定类型。
COALESCE函数：可以用来选择查询结果中输出空值的方式。例如COALESCE(salary, 0)，如果salary为空值，就输出 0。
DEFAULT deault_value：用在属性定义后，可以指定这个属性的缺省值。

用户可以创建自己的数据类型CREATE TYPE type_name AS ...。相应的，可以用ALTER TYPE和DROP TYPE来修改和删除数据类型。

对于标识符，我们一把需要它在数据库中是唯一的。可以在属性定义后加上GENERATED ALWAYS AS IDENTITY，告知系统这个属性是标识符，总是为其生成一个唯一的码值。如果用GENERATED BY DEFAULT AS IDENTITY，则用户指定了，就用指定值，否则就用系统生成的值。

可以用CREATE TABLE copy LIKE original来创建一个与原表有相同模式的新表。

可以用CREATE TABLE new_table AS (SELECT ...)，来将查询结果直接创建为一个新表。加上WITH DATA，显式地指定要将查询结果插入到新表中。

7、索引

实际应用中，我们的查询通常只涉及整个表中的一小部分记录，例如在员工表中查找所有男员工（gender属性值为male的记录）。一般，系统会读取所有的记录，然后查找出满足条件的记录，这样的效率是比较低的。

关系属性上的索引（Index）是一种数据结构，它允许数据库系统高效地找到在关系中具有该属性指定值的那些元组，而不扫描关系的所有元组。

索引不是必要的，这是一种冗余的数据结构，属于数据库物理模式的一部分，而不是逻辑模式的一部分。引入索引，对于事务的高效处理有很大的帮助。

创建索引的语句如下：

1 2	CREATE INDEX index_name ON relation_name (attr1, attr2, ..., attrn)

这里的属性列表，构成了索引的搜索码（search key）。

可以在索引定义后加上UNIQUE，以声明这个搜索码就是一个候选码CREATE UNIQUE INDEX ...。如果指定的属性列表并不构成候选码，系统返回错误，索引创建失败。

利用DROP INDEX可以删除索引。

8、授权

SQL 标准定义了数据库某些部分上的四种权限，也即增删改查（SELECT, INSERT, UPDATE, DELETE）。当用户尝试执行一个 SQL 语句时，系统会检查用户是否有权限执行这个操作。

除此之外还有数据库模式上的权限，例如创建、修改和删除表。还可以控制，拥有某些权限的用户，是否可以将这些权限传递给其他用户。

8.1、权限的授予与收回

授权的语法如下：

1
2
3

GRANT privilege_list
ON object_name
TO user_list

一条授权语句可以授予多个权限，也可以授予多个用户。其中privilege_list可以是SELECT, INSERT, UPDATE, DELETE, ALL等。object_name是视图或者关系的名字。user_list如果是PUBLIC，表示授权所有用户/角色（包括目前系统内已经存在的，以及未来加入的）。

缺省情况下，被授权的用户 /角色无权把此权限传递给其他用户 /角色。

收回权限的语句如下：

1
2
3

REVOKE privilege_list
ON object_name
FROM user_list

8.2、角色

假设新学期到了，创建了很多学生用户，如果要手动为每个用户授权是非常麻烦的。一种更好的方法是给“学生”这个角色（Role）授权，然后给学生用户授予这个角色。

创建角色的语法如下：

1	CREATE ROLE role_name

然后，就可以像对用户一样，用GRANT和REVOKE来授予和收回角色的权限。授予用户角色的语法如下：

1 2	GRANT role_name TO user_list

角色也可以授予其他角色，可以存在角色链。

最终，一个用户/角色拥有的权限包括：

直接授予该用户/角色的所有权限
该用户/角色所拥有的所有角色的所有权限

8.3、视图的授权

考虑某个用户拥有对某个视图的查询权限，他尝试查询这个视图时。当查询处理器处理此查询时，会用视图的定义替换掉视图名，这就转化为了对原关系的查询。所以系统应该在替换之前，就检查用户是否有对视图的查询权限。

视图的创建者应该有对原关系的查询权限，否则就不能创建视图。创建者是否有对视图的更新权限，取决于是否有对原关系的更新权限，其余权限同理。

视图的使用者使用这个视图时，只需要拥有对视图相应权限即可，不必拥有对原关系的权限。换句话说，过了一开始对视图的权限检查之后，就像是视图的创建者在执行查询一样。最终能不能执行成功，还是要看视图的创建者是否有对原关系的相应权限。

函数/过程的授权也与视图类似。函数/过程的创建者，需要有函数/过程中用到的表的相应权限。函数/过程的使用者，只要有EXECUTE权限就能执行这个函数/过程。函数/过程运行起来之后，就像是创建者在执行一样、最终能不能执行成功，还是要看创建者是否有相应权限。

8.4、模式的授权

只有模式的拥有者，才能执行对模式的任何修改，例如创建/删除表、增加/删除某个表的属性，增加/删除索引等。

一种特殊的模式级别的权限是引用权限REFERENCES。当用户拥有表 A 的引用权限时，可以在创建新关系 B 时声明外键引用表 A 的某个属性。

外键约束存在时，对表 B 的更新删除对 A 也会有影响。如果没有引用权限这一概念，用户就可以在不拥有表 A 的权限的情况下，通过创建表 B 和关于表 A 的外键约束，间接地对表 A 进行更新删除。

8.5、权限的转移

缺省情况下，被授予权限的用户/角色，无法将自身拥有的权限再授予其他用户/角色。

通过给授权语句加上WITH GRANT OPTION，允许这条授权语句中涉及的权限被传递给其他用户/角色。可以理解为，权限本身有一个“传递权限”。

将用户/角色视为一个节点，将授权关系视为一条边，就得到了一个授权图，这是一个有向图。如果某个用户/角色有某个权限，授权图上一定存在到根节点（数据库管理员，拥有一切权限）的一条路径。

grant-graph

8.6、权限的收回

由于权限可以传递，所以收回某个用户的权限，还可能影响到其他用户。

缺省情况下，数据库系统一般采用级联授权的方式。也即收回某个用户的权限时，会从该用户开始，沿着授权图的边，将所有的权限都收回。

收回权限的语法如下：

1
2
3

REVOKE privilege_list
ON object_name
FROM user_list

给收权语句加上CASCADE，显式指定级联收权；加上RESTRICT，显式指定不级联收权。

一些数据库系统还支持收回传递权限的权限：

1
2
3

REVOKE GRANT OPTION FOR privilege_list
ON object_name
FROM user_list

SQL 中存在当前角色的概念。缺省情况下，某个会话关联的当前角色是空的。可以通过SET ROLE role_name来设置当前角色。如果当前角色已设置，且当前操作用户拥有这个角色，就可以给授权语句加上GRANTED BY CURRENT_ROLE，表示授权是由当前角色授予的，而不是当前用户。

由角色来授予权限，可以避免某个具体用户权限被撤回时，对其他用户的影响。例如某个教务员 A 以用户的身份授予了某个老师 B 教师角色以及相关权限。如果 A 离职了，其权限被收回，B 也会失去权限，即便 B 还在工作，这是不希望看到的。如果一开始教务员 A 是以教务员角色的身份授予的，那么 B 就不会失去权限。

第五章高级 SQL

1、动态 SQL

SQL 只能完成数据库的相关操作，如果要对查询出来的数据进行复杂的处理或者做可视化展示，还是要借助 C、Python 等通用编程语言。

动态 SQL 是指，普通程序在运行时可以动态的构建 SQL 语句，然后通过某些接口连接到数据库、发送 SQL 语句、接收返回结果等。

预备语句是一种动态 SQL 的实现方式。预备语句是一种 SQL 语句的模板，其中的某些部分留空（以?代替），之后再填入具体的值，变成一个完整的 SQL 语句后再发给数据库。

例如INSER INTO student VALUES (?, ?, ?, ?)就是一个预备语句，之后可以用具体的值填充这个模板，例如最终变成INSER INTO student VALUES ('12345', 'Tom', 'CS', 100)。

这种也称为参数化查询，相比用字符串拼接的方式构造 SQL 语句，可以有效防止SQL 注入攻击。

2、函数和过程

2.1、函数和过程的创建与调用

除了执行单个的 SQL 语句之外，SQL 标准也允许创建和执行类似于函数的“语句块”。

一个用 SQL 定义函数的例子如下：

CREATE FUNCTION dept_count(dept_name VARCHAR(20))
  RETURN INTEGER
  BEGIN
    DECLARE count INTEGER;
    SELECT COUNT(*) INTO count
    FROM instructor
    WHERE dept_count.dept_name=instructor.dept_name;
    RETURN count;
  END

与我们用 C 语言之类的编写函数类似，也要写明函数参数，返回值类型，且有返回语句（RETURN）、和赋值语句（INTO）。

如果是编写自己的函数，可以用CREATE OR REPLACE来替换CREATE，这样如果函数已经存在，就会被替换。这样方便频繁修改和调试。

上面这个例子的返回值是一个标量，也可以返回一个表。这种函数称为表函数：

CREATE FUNCTION instructor_of(dept_name VARCHAR(20))
  RETURN TABLE (
    ID CHAR(5),
    name VARCHAR(20),
    dept_name VARCHAR(20),
    salary NUMERIC(8, 2)
  )
  BEGIN
    RETURN TABLE(
      SELECT ID, name, dept_name, salary
      FROM instructor
      WHERE instructor_of.dept_name=instructor.dept_name
    )
  END

注意引用函数的参数要用带上函数名。

这个表函数可以通过下面的方式调用：

1 2	SELECT * FROM TABLE(instructor_of('Music'))

也可以写成过程的形式：

CREATE PROCEDURE dept_count_proc(IN dept_name VARCHAR(20), OUT count INTEGER)
  BEGIN
    SELECT COUNT(*) INTO count
    FROM instructor
    WHERE dept_count_proc.dept_name=instructor.dept_name;
  END

IN表示输入参数，OUT表示输出。

过程利用CALL来调用：

1 2	DECLARE count INTEGER; CALL dept_count_proc('Music', count);

函数/过程是以函数名/过程名+参数标识的，所以不同的函数/过程可以有相同的名字，只要参数不同即可。

2.2、用于函数和过程的语言结构

SQL 中可以利用DECLARE var_name type的方式来声明变量，然后用SET var_name=value来赋值。

之前已经出现过的BEGIN ... END中间可以包含多条 SQL 语句，也可以在其中声明局部变量。利用BEGIN ATOMIC ... END将其中所有的语句作为一个事务执行。

SQL 中还有条件控制和循环结构。

条件控制：

IF condition THEN
  ...
ELSEIF condition THEN
  ...
ELSE
  ...
END IF

WHILE 循环：

1
2
3

WHILE condition DO
  ...
END WHILE

FOR 循环：

DECLARE sum INTEGER DEFAULT 0;
FOR r AS (
    SELECT budget
    FROM department
    WHERE dept_name='Music'
  )
DO
  SET sum=sum+r.budget;
END FOR

REPEAT 循环（C 语言中的 do-while）：

REPEAT
  ...
UNTIL condition
END REPEAT

C 语言中的break和continue在 SQL 中分别对应LEAVE和ITERATE。

SQL 中还有异常处理机制，可以像下面这样声明一个异常处理句柄：

DECLARE handle_type HANDLER FOR condition
  BEGIN
    ...
  END

其中handle_type可以是CONTINUE、EXIT等，表示句柄的行为。condition是句柄触发的条件，可以是预定义的一些状态，例如SQLEXCEPTION、SQLWARNING、NOT FOUND等，也可以是用户自定义的条件。后面的BEGIN ... END之间是捕获到异常后的处理。

3、触发器

触发器（Trigger）是作为对数据库修改的连带效果，而由系统自动执行的一组语句。与函数/过程不同，触发器是被动的，不是由用户显式调用的。触发器可以用于实现 SQL 约束机制无法实现的特殊的完整性约束。

一个触发器的要素包括其要检测的事件，触发执行要满足的条件，以及触发后要执行的动作。

一个触发器的例子如下：

CREATE TRIGGER timeslot_check
AFTER INSERT ON section

REFERENCING NEW ROW AS new_row
FOR EACH ROW
WHEN new_row.time_slot_id NOT IN (
  SELECT time_slot_id
  FROM time_slot
)
BEGIN
  ROLLBACK;
END

这个触发器的监测的事件是对section表的插入操作，条件是插入的time_slot_id在time_slot表中不存在，执行的操作是回滚这个操作。

同样，可以使用BEGIN ATOMIC ... END来指定一组语句作为事务。还可以进一步监测某个属性上的更新：AFTER UPDATE OF attr ON relation。

REFERENCING NEW ROW AS new_row为新插入的元组指定一个别名，方便后续的操作。

FOR EACH ROW是比那里每一个受影响的行，可以换用FOR EACH STATEMENT，然后用REFERENCING NEW TABLE AS new_table来指代包含所有受影响行一个临时的表，也称为过渡表。

触发器在创建之后是默认启用的，可以用ALTER TRIGGER trigger_name DISABLE来禁用触发器，也可以用DROP TRIGGER来删除触发器。

4、递归查询

考虑有表prereq，其中存储了课程的先修课程关系。表中有两个属性，course_id和prereq_id，分别表示课程 ID 和其先修课程的 ID。我们希望能够找出某个课程的所有先修课程。

如果将课程之间的依赖关系画成一个有向图，实际上就是找出从某个点出发的所有路径，可以利用迭代的方法完成（BFS）。在BEGIN ... END块中，可以用CREATE TEMPORARY TABLE来创建一个临时表，用来存储中间结果，然后借助循环来完成遍历。

另一种做法是利用递归查询：

WITH RECURSIVE rec_prereq(course_id, prereq_id) AS (
    SELECT course_id, prereq_id
    FROM prereq
  UNION
    SELECT rec_prereq.course_id, prereq.prereq_id
    FROM rec_prereq, prereq
    WHERE rec_prereq.prereq_id=prereq.course_id
)
SELECT *
FROM rec_prereq

WITH定义了一个临时视图，加上RECURSIVE关键字，表示这个视图是递归的。

任何递归视图都必须定义为两个子查询的并。我们的例子中，前面一个子查询称为基查询，后面的子查询使用了递归视图，称之为递归查询。

整个递归查询的过程可以理解为：

计算基查询，将结果加入到递归视图中
利用当前视图，计算递归查询，将结果加入到递归视图中
重复以上两个步骤，直到没有新的关系被加入到递归视图中

递归查询结束后得到的视图，就是我们想要的结果，称之为递归视图的不动点（不会进一步扩展）。

递归视图上的递归查询还要满足单调性，也就是说，递归视图中的元组要随着递归查询的进行，不断增加，不会减少。

所以递归查询上，不能使用聚集、NOT EXISTS、EXCEPT等结构，因为这些结构可能会导致递归视图的元组减少。

5、高级聚集特性

5.1、排名

已经介绍过用ORDER BY进行排序，我们也经常希望得到某个元组在排序后的位置，也就是排名。SQL 中提供了RANK()来方便的得到排名。

一个展示其最基本用法的例子如下：

1 2	SELECT ID, RANK() OVER (ORDER BY GPA DESC) AS rank FROM grades

这个查询给grades表添加了一个属性，表示 GPA 从高到低的排名。

RANK()会给在ORDER BY指定的属性上相等的两个元组相同的排名。DENSE_RANK()给每个人都不同的排名。

ORDER BY指定的属性值如果为空，默认会被视为最高值。也可以通过ORDER BY attr NULLS LAST将空值指定为最小值。

考虑一张表中存储了整个学校的学生名单，我们希望得到每个学生在其院系内部的排名，这可以通过PARTITION BY指定分区排名做到：

SELECT ID, dept_name,
  RANK() OVER (PARTITION BY dept_name ORDER BY GPA DESC) as dept_rank
FROM grades
ORDER BY dept_name, dept_rank

当排名语句和GROUP BY同时出现时，会先应用GOURP BY，再按照GROUP BY的结果进行分区和排名。

PERCENT_RANK()以比例的形式给出该元组的排名，例如 0.2，表示排名前 20%。

CUME_DIST()，名字来源于累计分布，对于某元组，给出排序值小于或等于该元组的元组占所有元组的比例。

NTILE(n)，排序后将所有元组分为 $n$ 个元组个数相同的集合，可以用于分等级。

5.2、分窗

有时候我们需要对表的指定部分进行一些操作，这个指定的部分（区间）就称之为窗口（Window）。

上面提到的排名函数，属于分窗的一种。不带分区的排名函数，窗口就是整个表；带分区的排名函数，每个分区就是一个窗口。

分窗的一半形式如下：

function_name (expression) OVER (
  [PARTITION BY partition_expression]
  [ORDER BY sort_expression]
  [frame_clause]
)

function_name是某种分窗函数，表示对窗口中的元组进行的操作。OVER后括号内的部分，定义了窗口的形式。

frame_clause是分窗框架，指定了窗口的范围。借一个具体的例子来说明：

SELECT year,
  AVG(num_credits) OVER (
    ORDER BY year
    ROWS ROWS 3 PRECEDING
  ) AS avg_credits
FROM tot_credits

这个 SQL 语句的含义是，先按照year属性排序，然后对于每一行，计算从本身开始往前数共三行（包括自己）的num_credits的平均值。

frame_clause写成完整形式应该是：

1	ROWS BETWEEN start_row AND end_row

在没有使用ORDER BY的情况下，窗口默认是整个表。在使用了ORDER BY的情况下，起始行是第一行，结束行是当前行CURRENT ROW。

将这个例子的分窗框架写完整，应该是：

1	ROWS BETWEEN 3 PRECEDING AND CURRENT ROW

所以对每 $n$ 行，指定的窗口为第 $[n-2, n]$ 行。

UNBOUNDED PRECEDING指定起始行是第一行，UNBOUNDED FOLLOWING指定结束行是最后一行。

n PRECEDING和n FOLLOWING分别指从当前行开始数的前 $n$ 行和后 $n$ 行。

通过以上关键字设定起始行和结束行，配合ORDER BY，可以实现很多复杂的窗口操作。

5.3、旋转

一般同一个属性下若干个取值是以列的形式呈现的，将属性的值作为新的属性，就好像把一列旋转成为行，故得名。旋转后得到的新表称为数据透视表（Pivot Table）或者交叉表。

例如，原表格如下：

year	product	amount
2020	A	100
2020	B	150
2021	A	200
2021	B	250
2022	A	300
2022	B	350

将其中的product列旋转，得到新表格如下：

year	A	B
2020	100	150
2021	200	250
2022	300	350

交叉表是从一个关系 R 中派生出来的表。选择 R 中的某个属性 A（称之为轴向属性）的取值作为新表的属性。

上面的例子对应的语句如下：

SELECT *
FROM sales
PIVOT (
  SUM(amount)
  FOR product IN ('A', 'B')
)

5.4、ROLLUP 和 CUBE

ROLLUP和CUBE是两种用于生成汇总数据的操作，可以理解为多个GROUP BY的一种简化写法。

1
2
3

SELECT a, b, SUM(c)
FROM r
GROUP BY ROLLUP(a, b)

等价于

(
  SELECT a, b, SUM(c)
  FROM r
  GROUP BY a, b
)
UNION
(
  SELECT a, NULL AS b, SUM(c)
  FROM r
  GROUP BY a
)
UNION
(
  SELECT NULL AS a, NULL AS b, SUM(c)
  FROM r
)

对每个前缀做一次GROUP BY，包括空前缀

CUBE是ROLLUP的一般化，对于每个可能的组合都做一次GROUP BY。

第六章 E-R 模型

1、数据库设计

数据库设计过程可以简单概括如下：

需求分析：完整明确地描述数据库用户的需求，包括数据、功能、性能等方面。
概念设计：根据需求分析，设计出数据库的概念模型，通常采用实体-联系模型。此过程中，通常还会绘制实体联系图。在功能需求规格说明中，用户会描述需要再数据上执行的各类操作。设计者此阶段还需要检查模式是否能满足这些功能需求。
逻辑设计：将高层的概念模式映射到具体实现使用的数据模型上，通常是关系模型。
物理设计：根据逻辑设计，选择合适的存储结构、索引、物理存储等。

数据库设计过程中，一个主要任务是决定如何在设计中表示各种类型的“事物”，例如学生、课程、教师等。我们用实体这个术语指代任何可以明确识别的个体。

在数据库模式的设计中，必须避免两个主要的缺陷：

冗余：同一信息在数据库中存储多个地方，容易导致数据不一致。
不完整：设计缺陷导致不能完整地表示用户需求。

2、实体-联系模型

实体-联系数据模型，简称为 E-R 模型，是一种用于数据库设计的概念模型。E-R 模型的三个基本要素是：实体集、联系集、属性。

2.1、实体集

一个实体（Entity）是现实世界中可区别于其他所有对象的一个“事物”或者“对象”。

每个实体有一组性质，且某些性质集合的值能够唯一标识一个实体。这里的性质我们一般称之为属性（Attribute），每个实体在它的每个属性上都有一个值（Value）。

实体集（Entity Set）是具有相同属性的一组实体的集合。实体集的外延用于指代实际的实体集合（类似于模板和实例的关系）。

数据库包含一组实体集，每个实体集包含任意数量的相同类型的实体。实体集在 E-R 图中用矩形表示。矩形中列出实体集的名字以及包含的所有属性的名字，作为主码的属性用下划线标出。

2.2、联系集

联系（Relationship）是两个或多个实体之间的关联，例如学生和老师之间有“教导”这一联系。联系集（Relationship Set）是相同类型联系的集合。

联系集在 E-R 图中用菱形表示，菱形通过线条连接到多个不同的实体集：

relationship-set

若记 $E_1, E_2, \cdots, E_n$ 为实体集，则联系集 $R$ 是：

$\{(e_1, e_2, \cdots, e_n) | e_1 \in E_1, e_2 \in E_2, \cdots, e_n \in E_n\}$

其中 $(e_1, e_2, \cdots, e_n)$ 就是一个联系实例，称 $E_1, E_2, \cdots, E_n$ 参与了联系集 $R$ 。

参与到联系集的实体集的数目称之为联系集的度（Degree）。例如上面这个式子是一个 $n$ 元联系集，度为 $n$ 。

实体在联系中扮演的功能称之为实体的角色（Role）。例如在联系集advisor中，实体集Instructor和Course分别扮演了教师和课程的角色。

通常参与到同一个联系集中是互异的实体集，用名字就可以轻松区分。有时候，同一个实体集可能在同一个联系集中扮演不同的角色，这时候需要用角色名来区分，例如“先修”联系集中，同一个实体集Course在分别扮演了“先修课程”和“后修课程”的角色。

联系本身也可以具有属性，称之为描述性属性（Descriptive Attribute）。例如在联系集advisor中，可能还有属性since，表示教师担任课程顾问的时间。

联系集的属性在 E-R 图中用不带联系集名的矩形表示，然后用虚线连接到联系集。

decriptive-attr

2.3、复杂属性

每个属性都有一个可能取值的集合，称之为该属性的域（Domain）或者值集（Value Set）。

E-R 模型中使用的属性包括：

简单属性和复合属性：简单属性是指不能再分解的属性，例如学生的学号；复合属性是划分为多个子部分属性，例如学生的姓名，可以分解为姓和名。复合属性代替多个简单属性，可以使模型更清晰。
单值属性和多值属性：单值属性是指每个实体只有一个值，例如学生的学号；多值属性是指每个实体可以有多个值，例如一个人可以有多个电话号码。
派生属性：派生属性是指可以从其他属性派生出来的属性，例如学生的年龄可以从出生日期计算出来。

在 E-R 图中，复合属性用层次结构列出其包含的简单属性，多值属性用中括号包裹，派生属性在其后加一个括号标识：

complex-attr

2.4、映射基数

映射基数（Mapping Cardinality）描述了一个实体能过通过一个联系集关联到另一个实体集中实体的数量。

对于二元联系集来说，映射基数是以下四种情况之一：

一对一：一个实体只能关联到另一个实体
一对多：一个实体能关联到多个实体
多对一：多个实体能关联到一个实体
多对多：多个实体能关联到多个实体

在 E-R 图中，从表示联系集的菱形指向实体集为有向箭头，表示只能映射到该实体集的一个实体；从菱形指向实体集为无向线段，表示能映射该实体集的多个实体。

mapping-cardinality

如果实体集 $E$ 中的每个实体都必须参与到联系集的至少一个联系中，则称 $E$ 在 $R$ 的参与是全部的，否则称参与是部分的。

用双线段表示全部的参与，单线段表示部分的参与。

E-R 图中，一种用于表示更复杂的映射基数的方法是，在无向线段上加上标记：

complex-mapping-cardinality

这里的0..*表示可以一个老师可以有任意个学生（零个到无限个），1..1表示一个学生只能有一个老师（一个到一个）。

注意不要理解反了！线段上的标识表示，一个实体能够参与到多少个联系中。

2.5、主码

之前介绍的主码、候选码、外码等概念，可以直接沿用到实体集中。

联系集中所有实体集的主码以及描述性属性的并集，可以通过这个并集上属性取值的集合来唯一标识一个联系实例（如果实体集主码名字相同，改名以区分；如果一个实体集多次参与到一个联系集中，可以用角色名来区分）。

所有实体集的主码的集合 $S$ 构成了联系集的一个超码。二元联系集主码的选择取决于映射基数：

多对多关系： $S$ 就是最小的超码，可被选作主码。
一对多或多对一关系：“多”的一方的主码是最小的超码，可被选作主码。
一对一关系：任意一方的主码都是最小的超码，可被选作主码。

对于非二元联系集，如果没有映射基数约束， $S$ 就是唯一的候选码。

2.6、弱实体集

弱实体集（Weak Entity Set）是依赖于另一个标识性实体集（Identifying Entity）存在。弱实体集自身的属性，称之为分辨符属性（Discriminator Attribute），无法唯一标识一个实体，必须再结合标识性实体集的主码才能唯一标识。非弱实体集的实体集称之为强实体集（Strong Entity Set）。

弱实体集存在依赖（Existence Dependent）于标识性实体集，标识性实体集拥有（Owns）弱实体集。将弱实体集与标识性实体集相关联的联系被称为标识性联系（Identifying Relationship）。

标识性联系是从弱实体集到标识性实体集的多对一联系，且弱实体集的参与是全部的。标识性联系集没有也不需要有描述性属性，有可以直接放到弱实体集中。

弱实体集的主码由弱实体集的分辨符属性和标识性实体集的主码组成。

E-R 图中，双边框矩形描述弱实体集，分辨符属性用下划虚线标出。标识性联系集用双边框菱形表示。

weak-entity

2.7、冗余的删除

一个好的实体-联系设计应当不包含冗余的属性。

考虑以下两个实体集：

Instructor：包含属性ID、name、dept_name、salary
Department：包含属性dept_name、building、budget

dept_name在两个实体集中都出现了。dept_name是Department的主码，不能被去除，但是在Instructor中，dept_name是一个冗余属性，可以被去除。它们之间的联系，改用联系集来表示。

3、将 E-R 模型转换为关系模式

E-R 模型和关系模型采用类似的设计原则，两者之间可以相互转换。在数据库设计中，对于每个实体集和联系集，都有唯一的关系模式与之对应。

3.1、强实体集的表示

设 $E$ 是只有简单属性 $a_1, a_2, \cdots, a_n$ 的强实体集，其可以表示为关系模式(a_1, a_2, ..., a_n)。可见转换是非常直接的，强实体集的属性直接映射到关系模式中的属性，原强实体集的主码就是关系模式的主码。

对于带有复合属性的强实体集，我们为复合属性中每个最终的简单属性创建一个属性，而不为复合属性本身创建属性。例如，强实体集中address是复合属性，包含street，city，zip，则关系模式为(..., street, city, zip, ...)。

对于带有多值属性的强实体集，多值属性抽离出来单独创建一个关系模式，然后建立外码约束引用原关系。这个单独创建的关系模式的主码由所有属性构成。

例如强实体集 $E$ 的属性为 $a, b, c$ ，其中 $c$ 是多值属性，那么一共有两个关系模式(a, b)和(a, c)。

派生属性可以表示为函数、过程等。

3.2、弱实体集的表示

设弱实体集 $A$ 有属性 $a_1, a_2, \cdots, a_n$ ，标识性实体集 $B$ 的主码为 $b_1, b_2, \cdots, b_m$ ，则弱实体集 $A$ 的关系模式为(a_1, a_2, ..., a_n, b_1, b_2, ..., b_m)。

这个关系模式的主码为全体属性，也即标识性实体集的主码加上弱实体集的分辨符属性。还需要创建外码约束，指明 $b_1, b_2, \cdots, b_m$ 是引用关系 $B$ 的主码。

3.3、联系集的表示

设联系集 $R$ ，每个参与 $R$ 的实体集的主码的并集构成的属性集合为 $a_1, a_2, \cdots, a_n$ ，联系集 $R$ 的描述性属性为 $b_1, b_2, \cdots, b_m$ ，则联系集 $R$ 的关系模式为(a_1, a_2, ..., a_n, b_1, b_2, ..., b_m)。

在其上也要建立外码约束，指明 $a_1, a_2, \cdots, a_n$ 是引用自各个实体集的主码。

一般而言，连接弱实体集与其对应的标识性实体集的联系集的模式是冗余的，可以不必给出。

3.4、模式的合并

考虑实体集 $A$ 到实体集 $B$ 是多对一的，相应的联系集为 $AB$ ，则按照前面所述，我们可以相应可以转换得到三个模式。进一步假定 $A$ 的参与是全部的，这种情况下 $AB$ 和 $A$ 模式可以合并为一个模式，这个模式的属性由 $A$ 和 $AB$ 的属性并集构成，主码为 $A$ 的主码。

例如有模式Student(ID, name, tot_cred)以及Department(dept_name, building, budget)，联系集转换出的模式为Student_Dept(ID, dept_name)。则Student和Student_Dept可以合并为一个模式Student(ID, dept_name, name, tot_cred)，其中主码为Student的主码ID。

如果是一对一的联系，则联系集的关系模式可以和参与联系的任何一个实体集的模式合并。即便是部分参与，也可以通过引入空值来合并。

4、特化和概化

一个实体集可以进一步划分出若干个自己，这个过程称之为特化（Specialization）。子集的属性包括原实体集的所有属性以及可能的附加属性。

speciliaze

E-R 图中用空心箭头来表示特化关系。实体如果至多属于一个特化实体集，也即不相交特化，则用分离的箭头表示（如图中的employee和student）；否则是重叠特化，用重叠的箭头表示（如图中的insturctor和secretary）。

概化则是相反的过程，若两个实体集（子类）之间存在共性，可以概化为一个一般的实体集（超类）。

第七章关系数据库

考虑两个模式instructor(ID, name, dept_name, salary)和department(dept_name, building, budget)。

如果单个模式in_dep(dept_name, ID, name, salary, building, budget)来代替上面的两个模式，会出现以下问题：

同一个部门的building和budget会被重复存储多次
in_dep中某一行的building和budget修改了，其他相关的行也要修改，否则会导致数据不一致
无法单纯的表示一个部门，除非这个部门至少存在一个老师，或者允许building和budget为空。

可见关系模式也有好坏之分，我们需要一种精确的方法来评价关系模式的设计。

1、分解

1.1、引入

避免上面的信息重复的唯一方法是将其分解为两个模式（也即将in_dep分解为instructor和department）。

但是并非所有的分解都是有益的。考虑下面的例子，将employee(ID, name, street, city, salary)分解为employee1(ID, name)和employee2(name, street, city, salary)。

考虑下表中的过程：

bad-decomp

当有同名的两个职员出现时，如果进行自然连接，我们会得到的元组变多了，可是却难以区分出原本的两个职员了。换句话说，这样的分解导致信息丢失了（不确定性变大了）。

我们称有信息损失的分解为有损分解（Lossy Decomposition），没有信息损失的分解为无损分解（Lossless Decomposition）。我们希望所有的分解都应该是无损分解。

1.2、无损分解

令 $R$ 为某个关系模式，其一个分解是 $R_1$ 和 $R_2$ 。也即如果将它们都视为属性集，满足 $R=R_1 \cup R_2$ 。如果 $R$ 的一个实例 $r$ 满足：

$\prod_{R_1}(r) \bowtie \prod_{R_2}(r) = r$

就称这个分解是无损分解。

换句话说， $r$ 与下面这个语句的结果是相同的：

SELECT *
FROM (
  SELECT R_1
  FROM r
  )
  NATURAL JOIN (
  SELECT R_2
  FROM r
  )

相反，如果计算投影结果的自然连接时得到了原始关系的一个真超集，也即：

$r \subset \left( \prod_{R_1}(r) \bowtie \prod_{R_2}(r)\right)$

就说明分解是有损的。

1.3、规范化

规范化（Normalization）的目标是生成一组关系模式，能够存储信息并且避免不必要的冗余。其过程如下：

确定一个给定的关系模式是否为良构的（也即没有信息重复问题）。
如果不是“良构的”，将其分解为许多较小的关系模式，使每个关系都满足某种范式。分解必须是无损的。

2、函数依赖

2.1、定义

函数依赖是用于确定一个关系模式是否符合满足一种理想范式的方法。

超码的形式化定义：给定 $r(R)$ ， $R$ 的一个子集 $K$ 如果满足，对于 $r(R)$ 的任意合法实例中的任意两个元组 $t_1, t_2$ ，当 $t_1\neq t_2$ 时，总有 $t_1[K]\neq t_2[K]$ ，则称 $K$ 是 $R$ 的一个超码（Superkey）。

下面定义函数依赖。考虑关系模式 $r(R)$ ，且两个属性集的子集 $\alpha \subseteq R$ 和 $\beta \subseteq R$ 。如果对于 $r(R)$ 的某个合法实例中的任意两个元组 $t_1, t_2$ ，当 $t_1[\alpha]=t_2[\alpha]$ 时，总有 $t_1[\beta]=t_2[\beta]$ ，则称该实例满足函数依赖 $\alpha \rightarrow \beta$ 。

如果 $r(R)$ 的每个合法实例都满足函数依赖 $\alpha \rightarrow \beta$ ，则称该函数依赖在 $r(R)$ 上成立（Hold）。

所以如果 $K\rightarrow R$ 在 $r(R)$ 上成立， $K$ 就是 $r(R)$ 的一个超码。

函数依赖可以有以下两种用法：

测试关系的实例，看其是否满足某个给定的函数依赖集 $F$
声明合法关系上的约束。对数据库进行更改后，必须仍然保证 $F$ 在 $r(R)$ 上成立。

一些函数依赖是平凡的，总是被所有关系满足。一般地，如果 $\beta \subseteq \alpha$ ，则 $\alpha \rightarrow \beta$ 是平凡的。

函数依赖之间存在“传递性”，也即如果 $\alpha \rightarrow \beta$ ， $\beta \rightarrow \gamma$ 在 $r(R)$ 上成立，那么 $\alpha \rightarrow \gamma$ 也在 $r(R)$ 上成立。所以如果某个函数依赖集 $F$ 在 $r(R)$ 上成立，那么 $F$ 的传递闭包 $F^+$ 也在 $r(R)$ 上成立， $F^+$ 是 $r$ 满足的所有函数依赖的集合。

2.2、函数依赖与无损分解

利用函数依赖可以说明什么时候一个分解是无损的。

假定函数依赖集 $F$ 在 $R$ 上成立， $R_1, R_2$ 是 $R$ 的一个无损分解的条件是，下列函数依赖至少有一个在 $F^+$ 中：

$R_1 \cap R_2 \rightarrow R_1$
$R_1 \cap R_2 \rightarrow R_2$

换句话说，如果 $R_1 \cap R_2$ 要么构成 $R_1$ 的超码，要么构成 $R_2$ 的超码，那么 $R_1, R_2$ 是 $R$ 的一个无损分解。

如果将关系模式 $r(R)$ 分解为 $r_1(R_1), r_2(R_2)$ ，不妨设 $R_1 \cap R_2 \rightarrow R_1$ ，则还需要施加以下约束以确保它们的内容与原始模式一致：

$R_1 \cap R_2 \rightarrow R_1$ 是 $r_1$ 的主码
$R_1 \cap R_2$ 是 $r_2$ 的外码，引用自 $r_1$

3、范式

之前已经提到了范式这个词，范式是一种关于关系模式“好坏”的评价标准。

3.1、BCNF

全称为Boyce-Codd 范式（Byoce-Codd Normal Form，BCNF），是一种关于函数依赖的范式，它可以消除基于函数依赖能够发现的所有冗余。

对于满足函数依赖集 $F$ 的关系模式 $R$ ，其满足 BCNF 的条件是，对于 $F^+$ 中所有形如 $\alpha \rightarrow \beta$ 的函数依赖，下面至少一项成立：

$\alpha \rightarrow \beta$ 是平凡的
$\alpha$ 是 $R$ 的超码

对于不满足 BCNF 的模式有一套进行分解的通用规则。

假定 $R$ 是不满足 BCNF 的一个模式，则至少存在一个非平凡的函数依赖 $\alpha \rightarrow \beta$ ，使得 $\alpha$ 不是 $R$ 的超码。我们可以将 $R$ 分解为两个模式 $\alpha \cup \beta$ 和 $R-(\beta-\alpha)$ 。

如果分解出的模式仍有不满足 BCNF 的，可以继续分解，直到所有的模式都满足 BCNF。

考虑以下联系集：

dept_advisor

该联系集指明的约束是，一名学生可以有不止一位导师，但是在一个给定的系中只能有一个导师。对应函数依赖 $\text{s\_id, dept\_name} \rightarrow \text{i\_id}$ ）
我们还假定，一个导师只能属于一个系。对应函数依赖 $\text{i\_id} \rightarrow \text{dept\_name}$

将该联系集转化为关系模式，得到(s_id, i_id, dept_name)。由于该模式满足 $\text{i\_id} \rightarrow \text{dept\_name}$ ，但是 $\text{i\_id}$ 不是超码，所以不满足 BCNF。

按照上面的方法，进行分解，得到(s_id, i_id)和(i_id, dept_name)两个模式，这两个模式都满足 BCNF。但是在分离后的两个关系上，没办法直接检查提到的第一个函数依赖。也就是说，BCNF 是非保持依赖（Dependency-Preserving）的。

3.2、第三范式

第三范式（Third Normal Form，3NF）是另一种关于函数依赖的范式，其相对于 BCNF 更加宽松。

对于满足函数依赖集 $F$ 的关系模式 $R$ ，其满足 3NF 的条件是，对于 $F^+$ 中所有形如 $\alpha \rightarrow \beta$ 的函数依赖，下面至少一项成立：

$\alpha \rightarrow \beta$ 是平凡的
$\alpha$ 是 $R$ 的超码
$\beta-\alpha$ 中的每个属性都被包含在 $R$ 的一个候选码中。注意，不是说 $\beta-\alpha$ 被包含于某个候选码中， $\beta-\alpha$ 中的属性可以在不同的候选码中。

由定义，显然任何满足 BCNF 的模式也满足 3NF。

在讲解 BCNF 时给出的例子中，提到 $\text{i\_id} \rightarrow \text{dept\_name}$ 这个依赖导致原关系不满足 BCNF。

考虑 $\beta-\alpha=\text{dept\_name}$ 。由于该关系满足 $\text{s\_id, dept\_name} \rightarrow \text{i\_id}$ ，所以(s_id, dept_name)是一个候选码，所以 $\beta-\alpha$ 中的属性都被包含在某个候选码中，所以该关系满足 3NF。

3.3、BCNF 与 3NF 的比较

3NF 总可以在不牺牲无损性或者依赖保持性的前提下得到，但是有时候不得不用空值来表示数据项之间的某些可能有意义的联系，兵器存在信息重复的问题。

我们应用函数依赖进行数据库设计的目标是：

满足 BCNF
无损分解
依赖保持

有时候 BCNF 并不能满足上述所有目标，这时候就不得不在 BCNF 与 3NF 之间做出权衡。

4、函数依赖理论

之前，只是简单的给出了函数依赖的定义。下面将进一步讨论，如何对函数依赖进行系统的推理。

4.1、函数依赖集的闭包

给定一个关系模式 $r(R)$ ，如果关系 $r(R)$ 的每一个满足 $F$ 的实例，也满足另一个函数依赖 $f$ ，则称 $f$ 被 $F$ 逻辑蕴含（Logically Imply）。被 $F$ 所逻辑蕴含的所有函数依赖的集合称之为 $F$ 的闭包（Closure），记作 $F^+$ 。

阿姆斯特朗公理（Armstrong’s Axioms）：

自反律：若 $\alpha$ 为一个属性集，且 $\beta \subseteq \alpha$ ，则 $\alpha \rightarrow \beta$ 成立
增补律：若 $\alpha \rightarrow \beta$ 成立，且 $\gamma$ 为一个属性集，则 $\alpha \gamma \rightarrow \beta \gamma$ 成立
传递律：若 $\alpha \rightarrow \beta$ 成立，且 $\beta \rightarrow \gamma$ 成立，则 $\alpha \rightarrow \gamma$ 成立

阿姆斯特朗公理是有效的（不会产生任何不正确的函数依赖），且是完备的（对于给定的 $F$ ， $F^+$ 中的所有函数依赖都可以由阿姆斯特朗公理推导出来）。

进一步，有以下附加规则：

合并律：若 $\alpha \rightarrow \beta$ 和 $\alpha \rightarrow \gamma$ 成立，则 $\alpha \rightarrow \beta \gamma$ 成立
分解律：若 $\alpha \rightarrow \beta \gamma$ 成立，则 $\alpha \rightarrow \beta$ 和 $\alpha \rightarrow \gamma$ 成立
伪传递律：若 $\alpha \rightarrow \beta$ 和 $\gamma\beta \rightarrow \delta$ 成立，则 $\alpha \gamma \rightarrow \delta$ 成立

由阿姆斯特朗公理，可以证明这些附加规则是有效的。

一个由 $F$ 计算 $F^+$ 的算法伪代码如下：

cal-F-plus

4.2、属性集的闭包

对于属性集 $\alpha$ 和某个属性 $B$ ，如果 $\alpha\rightarrow B$ ，则称 $B$ 被 $\alpha$ 函数决定（Functionally Determine）。

所以要确认某个属性集 $\alpha$ 是否为超码，就是要找出 $\alpha$ 函数决定的所有属性。一种方式是计算出 $F^+$ ，然后找出所有左侧是 $\alpha$ 的函数依赖，然后求这些函数依赖右侧的并集。显然，这种方法的代价是高昂的。

令 $\alpha$ 为一个属性集， $F$ 下被 $\alpha$ 决定的所有属性的集合称之为 $F$ 下 $\alpha$ 的闭包，记作 $\alpha^+$ 。

下图中是计算 $\alpha^+$ 的算法伪代码：

cal-alpha-plus

计算出属性集闭包有许多用途：

检查某个属性集 $\alpha$ 是否为超码，只需要看 $\alpha^+$ 是否包含了所有属性
检查 $\alpha\rightarrow \beta$ 是否成立，只需要看 $\alpha^+$ 是否包含了 $\beta$
计算 $F^+$ ，只需对于任意的 $\gamma \subseteq R$ ，计算 $\gamma^+$ ，然后对于任意的 $S\subseteq \gamma^+$ ，将 $\gamma \rightarrow S$ 加入 $F^+$

4.3、正则覆盖

如果某个关系模式上由函数依赖集 $F$ ，则每当用户在该关系上进行更新时，数据库都需要保证此更新不会破坏任何函数依赖。每次更新都需要检查所有的函数依赖，代价是十分高昂的。

我们可以转而去测试一个与 $F$ 有相同闭包的一个简化集，来减小开销。

如果可以删除函数依赖的某个属性，而不改变该函数依赖集的闭包，就称这个属性在该函数依赖中是无关的（Extraneous）。

从某个函数依赖的左侧移除一个属性，可以使其成为更强的约束；从右侧移除一个属性，可以使其成为更弱的约束。

考虑一个函数依赖集 $F$ 和其中的某个函数依赖 $\alpha\rightarrow \beta$ ，无关属性（Extraneous Attribute）可以形式化的定义为：

从左侧移除：如果 $A\in \alpha$ ，且 $F$ 逻辑蕴含 $(F-\{\alpha\rightarrow \beta\}) \cup \{(\alpha-A)\rightarrow \beta\}$ ，则属性 $A$ 是无关的
从右侧移除：如果 $A\in \beta$ ，且 $F$ 逻辑蕴含 $(F-\{\alpha\rightarrow \beta\}) \cup \{\alpha\rightarrow (\beta-A)\}$ ，则属性 $A$ 是无关的

简而言之，去掉那个属性之后，是否还能推出原来的函数依赖。

为了判断 $\alpha\rightarrow \beta$ 中的某个属性 $A$ 是否是无关的：

如果 $A\in \beta$ ，只需考虑 $F'=(F-\{\alpha\rightarrow \beta\}) \cup \{\alpha\rightarrow (\beta-A)\}$ 能否推出 $\alpha\rightarrow A$ 。这可以通过检查 $F'$ 下的 $\alpha^+$ 是否包含 $A$ 来完成。（实际上在检查去掉 $\alpha\rightarrow \beta$ 后，还能否重新推出 $\alpha\rightarrow \beta$ ）
如果 $A\in \alpha$ ，令 $\gamma=\alpha-\{A\}$ ，检查 $F$ 是否可以推出 $\gamma\rightarrow \beta$ 。这可以通过检查 $F$ 下的 $\gamma^+$ 是否包含 $\beta$ 来完成。（实际上在检查去掉 $A$ 后，还能否推出 $\alpha\rightarrow \beta$ ）

$F$ 的正则覆盖（Canonical Cover） $F_c$ 是这样的一个依赖集： $F$ 逻辑蕴含 $F_c$ 中的所有依赖， $F_c$ 逻辑蕴含 $F$ 中的所有依赖。且 $F_c$ 满足：

$F_c$ 中的任意函数依赖都不包含无关属性
$F_c$ 中的每个函数依赖的左侧都是唯一的

计算正则覆盖的算法伪代码如下：

cal-canonical-cover

4.4、保持依赖

令 $F$ 为模式 $R$ 上的一个函数依赖集，且 $R_1, R_2, \cdots, R_n$ 为 $R$ 的一个分解。 $F$ 对 $R_i$ 的限定是 $F^+$ 中所有形如 $\alpha \rightarrow \beta$ 的函数依赖的集合 $F_i$ ，其中 $\alpha, \beta \subseteq R_i$ 。显然，限定相对于 $F$ 是一个能够被高效检查的集合。

令 $F'=F_1 \cup F_2 \cup \cdots \cup F_n$ ，如果 $F'^+=F^+$ ，则 $F$ 中的每个依赖都被 $F'$ 逻辑蕴含。这种情况下，如果我们证明了 $F'$ 是被满足的，则 $F$ 也是被满足的。我们称满足 $F'^+=F^+$ 的分解是保持依赖（Dependency-Preserving）的。

分解得到的模式上，由于不包含所有的属性，所以 $F$ 中的某些函数依赖不能被检查，只能检查对应的限定。如果分解得到的模式上都满足各自的限定，就能保证原模式上的函数依赖也被满足，就说明原来的函数依赖在分解后被保持了。这正是上面的定义。

直接的检验分解是否是保持依赖的算法伪代码如下：

cal-dependency

上面这种检查保持依赖的方法开销很高。

一种可替代方式是：如果 $F$ 中的每一个函数依赖都可以在分解后的某一个关系上验证，这个分解就是保持依赖的。但是，可能存在某个函数依赖，在分解后的任何一个关系上都不能验证，但该分解本身是保持依赖的。所以这种方法只是一个充分条件。

另一种替代方案是，对 $F$ 中的每个依赖 $\alpha\rightarrow \beta$ 应用以下过程：

second-method

这里的属性集闭包是在 $F$ 下计算的。如果最终 $\text{result}$ 包含了 $\beta$ ，则函数依赖 $\alpha\rightarrow \beta$ 在分解后的模式上是被保持的。当且仅当，按照上面过程检查发现 $F$ 中的每个函数依赖都被保持，这个分解就是保持依赖的。

其本质是检查每个函数依赖是否在 $F'$ 下被保持，为此，计算 $F'$ 下 $\alpha$ 的闭包，看起是否包含 $\beta$ 。如果是，说明该依赖保持。

同时，用修改后的属性闭包算法来计算 $F'$ 下的闭包，不必计算出 $F'$ 。算法中在 $F$ 下计算 $(\text{result} \cap R_i)^+$ ，然后与 $R_i$ 求交集，等价于求 $F_i$ 下的闭包。最后并起来，就得到了 $F'$ 下的闭包。

5、使用函数依赖的分解算法

5.1、BCNF 检测

之前已经给出了 BCNF 的定义，可以按照定义来直接检测。但是这样需要计算 $F^+$ ，开销很大。

事实上，可以做以下简化：

对于一个非平凡的依赖 $\alpha\rightarrow \beta$ ，我们要确定 $\alpha$ 是否是超码。这可以通过计算 $F$ 下的 $\alpha^+$ 是否包含 $R$ 中的所有属性来完成。
只需要检查 $F$ 中的所有依赖是否满足 BCNF 的定义，不必计算 $F^+$ 。可以证明，如果 $F$ 中没有依赖违反 BCNF，那么 $F^+$ 中也没有。（这一简化对分解后的模式不一定成立）

要检查 $R$ 分解后的一个关系模式 $R_i$ 是否满足 BCNF，可以：对于 $R_i$ 中属性的每个子集 $\alpha$ ，检查其 $F$ 下的 $\alpha$ ，如果其要么不包含 $R_i-\alpha$ 的任何属性，要么包含 $R_i$ 的所有属性，则 $R_i$ 满足 BCNF。

如果 $R_i$ 中有某个属性集 $\alpha$ 违反了该条件，则其一定不满足 $F^+$ 中的函数依赖 $\alpha\rightarrow (\alpha^+ -\alpha)\cap R_i$ ，说明 $R_i$ 违反了 BCNF。

5.2、BCNF 分解

下面给出一个通用方法来分解一个关系模式 $R$ ，使得每个分解后的模式都满足 BCNF，且分解是无损的：

BCNF-comp

基本思路是，找到一个不满足 BCNF 的模式 $R_i$ ，以及使其不满足 BCNF 的非平凡依赖 $\alpha\rightarrow \beta$ （说明 $\alpha$ 不是超码）。然后将 $R_i$ 分解为 $\alpha\cup\beta$ 和 $R_i-\beta$ 这两个模式。

BCNF 分解算法的时间复杂度是指数级的。

5.3、3NF 分解

下图给出了一个通用的 3NF 分解算法，其得到的分解是保持依赖且无损的：

3NF-comp

其基本思路是，对于正则覆盖中的任意一个函数依赖 $\alpha\rightarrow \beta$ ，构造一个属性集 $\alpha \cup \beta$ 。如果没有任何一个属性集包含候选码，则再添加一个包含任意候选码的属性集。最后去除冗余的属性集。

6、使用多值依赖的分解

考虑大学instructor模式(ID, dept_name, name, street, city)。假定一位老师可以和多个系关联，且一个老师可以有多个地址，但是一个老师只能有一个名字。

所以，模式满足依赖 $\text{ID}\rightarrow \text{name}$ 。由于ID不是超码，原模式不满足 BCNF。根据 BCNF 分解，可以得到(ID, name)和(ID, dept_name, street, city)两个模式。

由于一个老师可以有多个地址，所以分解得到的第二个关系还是存在冗余。需要进一步分解为(ID, dept_name)和(ID, street, city)。并不存在任何约束引导我们进行这种分解，我们需要一种新的依赖——多值依赖。

6.1、多值依赖

设关系模式 $R$ ，且 $\alpha\subseteq R$ ， $\beta\subseteq R$ 。如果对于 $R$ 的任意两个满足 $t_1[\alpha]=t_2[\alpha]$ 的元组 $t_1, t_2$ ，都存在 $R$ 中的元组 $t_3, t_4$ 使得：

$t_1[\alpha]=t_2[\alpha]=t_3[\alpha]=t_4[\alpha]$
$t_1[\beta]=t_3[\beta], t_2[\beta]=t_4[\beta]$
$t_1[R-\beta]=t_4[R-\beta], t_2[R-\beta]=t_3[R-\beta]$

则称多值依赖（Multivalued Dependency） $\alpha\rightarrow\!\!\rightarrow \beta$ 在 $R$ 上成立。

直观理解就是， $\alpha$ 和 $\beta$ 之间的联系，独立于 $\alpha$ 和 $R-\beta$ 之间的联系。在之前的例子中，ID 与dept_name之间的联系，独立于 ID 与street, city之间的联系，所以没必要把dept_name和street, city放在一起。

如果某个关系 $r$ 不满足给定的多值依赖，可以通过添加元组的方式来构造出一个满足多字依赖的关系 $r'$ 。

多值依赖是一种元组产生依赖，其要求某些元组存在于关系中。而函数依赖是相等产生依赖，其要求某些元组在属性上的取值相等。

常用 $D$ 表示一个函数依赖和多值依赖的集合。 $D$ 的闭包 $D^+$ 是 $D$ 逻辑蕴含的所有函数依赖和多值依赖的集合。

关于多值依赖，有以下规则：

若 $\alpha\rightarrow \beta$ ，则 $\alpha\rightarrow\!\!\rightarrow \beta$
若 $\alpha\rightarrow\!\!\rightarrow \beta$ ，则 $\alpha \rightarrow \!\! R-\alpha-\beta$

6.2、第四范式

一个关系模式 $R$ 满足第四范式（Fourth Normal Form，4NF）的条件是，对于 $D^+$ 中所有形如 $\alpha\rightarrow\!\!\rightarrow \beta$ 的多值依赖，下面至少一项成立：

$\alpha\rightarrow\!\!\rightarrow \beta$ 是平凡的多值依赖
$\alpha$ 是 $R$ 的超码

第四范式比 BCNF 的要求更为严格。每个满足 4NF 的模式，一定是满足 BCNF 的。反之则不然。

6.3、4NF 分解

下面为 4NF 分解的算法伪代码，与 BCNF 分解的思路类似，只是函数依赖换为多值依赖， $F^+$ 换为 $D^+$ ：

4NF-comp

这样产生的也是无损的分解。