【数据库系统】课程笔记 - part 1

· · 算法·理论

写在前面：

成绩 93/100，绩点 4.8。

由于 db 的笔记有点太多了（12 个 md 文档加在一起有 122K），因此将其按顺序均分为 3 个部分，每个部分包含 4 个 Lecture。

注：Lecture 1 为导论课，Lecture 7 为期中考试复习课，因此没有记录笔记。

另注：我已经尽可能写的详细了，但仍不保证知识点覆盖完全。

【数据库系统】课程笔记 - part 1：https://www.luogu.com.cn/article/47sozboa

【数据库系统】课程笔记 - part 2：https://www.luogu.com.cn/article/xcqqbg8c

【数据库系统】课程笔记 - part 3：https://www.luogu.com.cn/article/fk3j2hgg

Lecture 2 - Relational Model

relation 和 relationship 的区别

Structure of Relational Databases

笛卡尔积

给出 n 个域 (domain) D_{1\cdots n}，那么这 n 个域的笛卡尔积 (Cartesian product) D_1\times D_2\times \cdots \times D_n 为一个集合，每个集合中的元素都为一个 n 元组 (tuple) (a_1,a_2,\cdots,a_n),a_i\in D_i。

而一个关系 (relation) 就是笛卡尔积的一个反映了特定意义的子集。

属性类型

之前提到了，一个关系是若干个域的笛卡尔积的子集，其中每个域都有一个名字，即为属性 (attribute)，而域就是这个属性能取的所有值的集合。

由于关系理论第一范式 (1st NF)，一般来说属性都要是原子的 (atomic)，不可分割的 (indivisible)，例如：

注意，空值 (null) 是每个域的元素，但它的引入可能会导致一些麻烦，这里暂不讨论。

关系的一些概念

一些性质：

关系模式 (relation schema)

用规范的语言来描述，则是：

关系实例 (relation instance)

每个关系实例中的一行都是一个元组，例如下图就是一个表：

数据库 (database)

一个数据库由若干个关系组成，通常来说我们会将一个复杂的关系拆分成若干个小的关系，具体如何判断是否需要拆分以及如何拆分会在之后的章节讨论，如果直接存储一个复杂的关系，那么可能会导致：

码/键 (key)

码为一个属性集合的子集，即 K\subseteq R，有如下几种码：

将所有的参照关系指向被参照关系，就可以得到表示关系模式的图，例如下面：

Fundamental Relational-Algebra Operations

六种基本运算，这六种运算都是以一个或两个关系为输入，并以一个关系为输出：

选择运算

形式为 \sigma_{p}(r)，其中 r 为一个关系，p 为选择谓词 (selection predicate)，例如：

\sigma_{\rm branch-name='Perryridge'}(\rm account)

投影运算

形式为 \prod_{A_1,A_2,\cdots,A_k}(r)，其中 r 为一个关系，A_i 为选择的属性，这个运算会删除所有没有选择的属性，并将剩余的所有元组去重，例如：

\prod_{\rm account-number,balance}(\rm account)

并运算

形式为 r\cup s，其中 r,s 为两个关系，且它们的属性集合必须相同，这个操作会将两个关系的所有元组去重并组成一个新的关系，例如：

\rm \prod_{customer-name}(depositor)\cup \prod_{customer-name}(borrower)

差运算

形式为 r-s，其中 r,s 为两个关系，且它们的属性集合必须相同，这个操作会将所有属于 r 但不属于 s 的元组组成一个新的关系，例如：

\rm \prod_{customer-name}(depositor)-\prod_{customer-name}(borrower)

笛卡尔积

形式为 r\times s，其中 r,s 为两个关系，其它们的属性集合必须不交（如果有交则必须进行重命名），这个操作会将两个关系的属性集合并，并得到 |r|\times |s| 个合并之后的元组，例如：

重命名

形式为 \rho_{X(A_1,A_2,\cdots,A_n)}(E)，表示将关系 E 重命名为 X，并将它的 n 个 attribute 依次命名为 A_{1\cdots n}。

Additional Relational-Algebra Operations

有四种运算：

交运算

形式为 r\cap s，表示选出所有 r,s 共有的组，注意到 r\cap s=r-(r-s)，因此可以用差运算得到

自然连接

形式为 r\bowtie s（这个符号没有对应的 latex 语法），表示：

（哎不对是有语法的\bowtie）

有点难以描述，可以看下图：

除运算

形式为 r\div s，其中要求：

也有点难以描述，看下图：

赋值运算

形式为 r\leftarrow s，表示将关系 r 赋值为关系 s，在一些复杂的运算中会用到

Extended Relational-Algebra Operations

有两种运算：

广义投影

在一般的投影运算中，只能指定原关系的一些属性，在广义投影中，可以指定这些属性之间的运算关系，例如：

\rm \prod_{customer\_name,limit-credit\_balance}(credit\_info)

聚合函数

一个聚合函数 (aggregate function) 以多个数为输入，并返回一个结果，典型的聚合函数有：

聚合函数的结构为 {}_{G_1,G_2,\cdots,G_n}g_{F_1(A_1),F_2(A_2),\cdots,F_m(A_m)}(E)，其含义为：

注意：聚合函数计算出的结果是没有名称的，需要命名，例如：

\rm {}_{branch-name}g_{sum(balance)\ as\ sum-balance}(account)

下面是一个例子：

Modification of the Database

有三种应用场景：

Lecture 3 - SQL

SQL (Structured Query Language，结构化查询语言)，其包含三个部分：

Data Definition Language

DDL 的主要功能包含以下几种：

域的类型

表的定义

一个标准的 SQL 语句为：

create table r(
    A1 D1,
    A2 D2,
    ...
    An Dn,
    (integrity constraint 1),
    ...
    (integrity constraint k),
);

其中 r 为这个表的名称，每个 A_i 为一个属性的名称，D_i 为域的类型。

然后是一些 integrity constraints 的类型：

比如下面是一个例子：

create table branch(
    branch_name varchar(30) not null,
    branch_city varchar(30),
    assets int,
    primary key(branch_name),
    check(assets>=0)
);

表的删除与修改

表的删除 (drop) 较为简单：

drop table r;

这样的语句即可删除名为 r 的表格（会删除所有信息，因此谨慎使用）

表的修改 (alter) 有以下几种类型：

alter table r [执行的操作];

索引的建立和删除

索引 (index) 是一种用于加速查询，但减缓更新速度的手段（因为要同步更新索引）

索引的建立：

create (unique) index 索引名 on r(A1,A2,...);

其中 unique 可写可不写，如果加上就表示唯一索引

索引的删除：

drop index 索引名;

Basic Structure

select clause

一个标准的 select 语句的结构为：

select A1,A2,...
from r1,r2,...
where P;

其中 A_i 为指定的各个属性，r_i 为各个表，P 为一个谓词（判断标准），P 这一项可以省略。

上面的这个语句等价于：

\prod_{A_1,A_2,\cdots}(\sigma_P(r_1\times r_2\times \cdots )) 
select distinct age
from student
where age>=18;

与之对应的，如果不需要去重，也可以将 distinct 替换为 all（虽然默认就是允许重复的）。

select * from student where age>=18;
select price*1.2 from products;
select
  product_name,
  price,
  discount,
  price*(1-discount) as final_price
from products;
select
  product_name,
  price,
  discount,
  price*(1-discount) as final_price
from products P;

这个重命名通常会在多个关系做笛卡尔积的时候用到。

where clause

where 语句之后跟的判断条件为筛选依据，可以使用 and,or,not 等逻辑运算符进行不同条件的连接。

from clause

from 语句指定了筛选的范围，如果填写多个关系，则在这些关系的笛卡尔积中进行筛选。

请注意，如果两个进行笛卡尔积的关系中有相同的属性，则需要添加前缀来区分，例如：

select
  a.id as 表A的id,
  a.name as 表A的名称,
  b.id as 表B的id,
  b.name as 表B的名称
from 表A a, 表B b;

同时，from 语句中的一个表格可以重命名为不同的名称，使用两次，例如：

select distinct A.score
from student A, student B
where A.score>B.score and A.class=101 and B.class=102;

这样就选出了 101 班中比 102 班中某些学生成绩高的成绩了（某些和所有的区别会在之后写到）

order 语句

如果想要对筛选出的结果进行排序，那么可以在 where 之后添加一条 order by 指令，默认是升序的 (体现为 ASC)，如果要改成降序则需要添加 DESC，例如：

select score from student order by score DESC;

这样就以降序排列了所有学生的分数。

另外，order by 语句中可以添加多项，此时的功能为多关键字排序。

select * from student
order by class ASC, score DESC;

这样就以班级编号为第一关键字升序排序，在班级相同时以分数为第二关键字降序排序了。

Set Operations

SQL 中集合操作一共有三种：交，并，差

Aggregate Functions

常见的聚合函数有：avg,min,max,sum,count，它们都作用于一列数据，并得到一个返回值。

例如一个最简单的情况：

select avg(balance) as avg_bal
from account
where branch_name='Perryridge';

那么如果想对每种 branch_name 都做平均值，就需要 group by 来指定分组方式了：

select avg(balance) as avg_bal
from accout
group by branch_name;

having clause

如果想对分组之后的各个组进行筛选，则需要加上 having 语句，其格式为：

select class, sum(score) as total_score
from scores
where score>=60 -- 分组前的筛选方法
group by class
having sum(score)>150; -- 分组后的筛选方法

注意 having 之后必须用聚合函数

Null Values

空值 (null) 是 SQL 中的一种特殊值，它代表着 “数据缺失” 或者 “数据不合法”，因此，与 null 相关的任何算术运算，逻辑运算得到的结果都是 null/unknown。同时，where 语句的结果如果是 unknown，那么它会被当做 false 处理。

所以，如果想判断某个内容是否为空，是不可以用 where A=null 的，而应当采用 where A is null/is not null。

同时，聚合函数（除了 count）在应用时都会忽略 null 值以免对结果产生影响。

Nested Subqueries

大致就是询问的嵌套，核心是 select 语句中涉及到的关系可以是子询问的结果。

select branch_name
from branch
where assets > all(
    select assets
    from branch
    where branch_city='Brooklyn'
);

select branch_name
from branch
where assets > (
    select max(assets)
    from branch
    where branch_city='Brooklyn'
);

上面的这两句话是等价的。

exists r     -- r 非空
not exists r -- r 为空
unique r      -- r 中无重复
not unique r  -- r 中有重复

Views

视图 (view) 建立的初衷就是限制一些列不向一些用户显示，建立视图的语句结构为：

create view 视图名称 as
select A1,A2,...
from r
where P

其本质为一张虚拟表，或者预保存的 select 语句。在创建完视图之后，可以把它当做正常的表格来使用。

Derived Relations

有些复杂的 SQL 语句可能需要保存某些查询得到的表进行重复使用，此时就可以使用 with 语句：

with 临时表名 as (
    select 列 from 表 where 条件
)
select * from 临时表名;

也可以一次性创建多个临时表，中间用逗号分开，例如：

with
t1 as (select * from student where gender='男'),
t2 as (select * from scores where score>80)
select t1.name,t2.score
from t1 join t2 on t1.id=t2.stu_id;

Modification of the Database

Deletion

删除行，其结构为：

delete from 表
where 条件;

Insertion

添加新的行，其结构为：

insert into 表(A1,A2,...)
values (D1,D2,...),(...),...

Update

对原有的列进行修改，其结构为：

update 表
set [A1=a1,A2=a2,...] where 条件;

其中 where 这部分可以省略，例如：

update salary_record
set salary=salary*1.05
where dept_name='sale';

Case

这个语句是用来进行一个简单的 if 操作的：

case A1
    when value1 then result1
    when value2 then result2
    else default_result
end -- 这个是针对一个具体的字段进行 if 判断

case
    when condition1 then result1
    when condition2 then result2
    else default_result
end -- 这个是具体的条件判断

它会返回一个值，例如对薪资超过 10000 的员工上涨 5\%，没超过的下调 5\%，那么就是：

update salary_record
set salary=case
             when salary>10000 then salary*1.05
             else salary*0.95
           end
where dept_name='sale';

Joined Relations

分以下几种：

select *
from A
inner join B
on A.id=B.id
select *
from A
left join B
on A.id=B.id
select *
from A
right join B
on A.id=B.id
select *
from A
full join B
on A.id=B.id

其中 left/right/full join 与第一种相反，称为 outer join，同时 join 默认是 inner join，因此 inner 可以省略。

Lecture 4 - Advanced SQL

这个部分介绍一些更加进阶的 SQL 语法以及它们能实现的功能。

SQL Data Types and Schemas

类似 C/C++ 中的 typedef，SQL 也有类似的用户自定义类型，有 create type 和 create domain 两种：

create type gender as enum('male','female','other'); -- create type 可以用于创建全新的数据类型
create domain positive_int as int check(value>0);    -- create domain 是在原有类型的基础上添加限制

简而言之：

Integrity Constraints

这里主要介绍四个内容：Domain Constraints, Referential Integrity, Assertions, Triggers。

完整性约束的作用就是在数据发生意外改变的时候维持数据内容的一致性，其包含实体完整性、参照完整性和用户定义的完整性约束。

最简单的完整性约束就是单个关系中的约束，例如关键字 not null/primary key/unique/check(P) 等等。

Domain Constraints

这个略去不提，就是上面 create domain 中添加的约束。

Referential Integrity

参照完整性 (Referential Integrity) 这部分就是之前提到的外键，回顾之前对外键的限制：参照关系中外键的值必须在被参照关系中实际存在，或为 null。

举一个最简单的例子来进行说明：

学生(学号(PK),姓名,专业号)
专业(专业号(PK)，专业名称)

那么可以发现学生表中的 "专业号" 这一项参照了专业表中的 "专业号" 这一项，于是学生表中的 "专业号" 必须在专业表中出现过，否则会破坏参照完整性。

接下来用严谨的方式来进行定义：

于是在对 r_1,r_2 进行插入/删除的时候就需要处理参照完整性（更新是同理的），依旧以上面两张表为例：

在 SQL 中，可以通过添加关键字来手动指定主键、外键等：

例如：

foreign key (account-number) references account -- 自动参照 account 表中的 account-number
foreign key (account-number) references account(account-number) -- 手动指定也可以

Cascading Actions in SQL

之前提到了，删除被参照关系中的元组时，是否需要删除所有参照关系中参照它的内容，这部分就是级联行为 (cascading action)，注意，级联行为是可以传递多次的。

指定级联行为的 SQL 语句为：

foreign key (branch-name)
    references branch(branch-name)
    [on delete cascade]
    [on update cascade]

（可见 lab3 的实验报告，里面有这部分的实验结果）

注意，null 值外键往往在级联操作时会引起很复杂的问题，因此请尽量避免这种情况。

Assertions

与 C/C++ 类似，断言 (assertion) 起到了一个保证条件成立的功能：

create assertion 断言名 check(P);

这样，系统会在每一次可能导致断言不成立的修改之后检查（因此引入断言可能会导致系统整体效率显著下降）。

另外，SQL 不支持 for all X, P(X) 这样的检查方式，因此只能用它的逆否命题

not exists X, such that not P(X)

Triggers

触发器 (trigger) 会在数据发生一些变化时自动进行一些行为，因此如果需要建立触发器，就必须指定：

触发器的具体语法比较复杂，大概有这么几个部分：

这是豆包给出的一个例子：

CREATE TABLE user_log(
    id INT PRIMARY KEY AUTO_INCREMENT,
    uid INT,
    old_name VARCHAR(20),
    new_name VARCHAR(20),
    update_time DATETIME DEFAULT NOW()
);

DELIMITER $$
CREATE TRIGGER trg_user_update_log
AFTER UPDATE ON user
FOR EACH ROW
BEGIN
    INSERT INTO user_log(uid,old_name,new_name)
    VALUES(OLD.id, OLD.name, NEW.name);
END$$
DELIMITER ;

Authorization

这一部分主要是关于 SQL 安全性，其实主要是两类语句：

grant <privilege list> on <table|view> to <user-list> -- 将特性的权限授予给某个用户
revoke <privilege list> on <table|view> from <user-list> [restrict|cascade]
  -- 将特定的权限从某个用户处收回，加了 cascade 是因为可能有递归授予权限，此时 revoke 会全部收回

这里能授予和回收的权限有：insert/update/delete/references/select/all 等等。

Embedded SQL

Dynamic SQL

TBD（就是不会考，看不懂也懒得写，后面 to be done 的原因大致也是如此）

Lecture 5 - Entity-Relationship Model

Entity Sets

核心思想为：现实世界可以被抽象为若干实体 (entity) 以及实体之间的联系 (relationship)。

实体拥有多种属性（例如 "学生" 实体就包含姓名，性别，年龄等等），同时可以是具体的，也可以是抽象的。

一个实体集 (entity set) 是一系列同一类的，具有同种特性的实体的集合。

Attributes

之前对属性 (attribute) 已经有过介绍了，这里添加一些描述：

Relationship Sets

联系 (relationship) 是两个或两个以上不同实体之间的关联。

联系集 (relationship set) 包含多个同类的联系，表示两个或两个以上实体集之间的关联。

上面的图就是一个例子，students 和 courses 是两个实体集，而 enrolled 就是这两个实体集之间的联系集。

（单条的 student 和 course 为单个实体，enroll 同理）

与实体类似，联系也可以拥有属性，来描述这个联系的特性。

Mapping Cardinality

指的是在一个联系集中，一个实体可以与另一类实体相联系的实体数目，这里数目可以是最多一个也可以是允许多个。

根据最多一个和允许多个可以分成这几类：

（允许有一些实体不参与到联系中）

Keys

Keys for Entity Sets

超码：能够唯一确定每个实体的一个或多个属性

候选码：大小最小的超码

主码：被用户选中的一个候选码

（这三种在之前都已经介绍过了）

Keys for Relationship Sets

一个联系集的超码为：参与联系的各个实体集的主码的并集（注意这里说的是超码）

因此考虑联系集的候选码时必须要关注这个联系集的 Mapping Cardinality，确定是多少对多少的。

存在多个候选码时，选择主码的时候需要考虑这个联系本身的语义。

E-R Diagram

使用图的方式对实体和联系进行表示：

Cardinality Constraints

E-R 图中的直线可以带上箭头，表示参与联系的实体数目，其中：

一个例子

Participation of an Entity Set in a Relationship Set

区分实体集中的所有实体是否都会参与到联系集中：

Converting Non-Binary Relationships to Binary Form

有些时候一些复杂的联系可能会涉及到两个以上的实体集，这种情况较为复杂，因此可以考虑通过人为添加实体集的方法将所有联系集都变成二元的，例如下图所示：

Weak Entity Sets

弱实体集 (weak entity set) 与强实体集相区分，它们没有自己的主键，无法靠自己唯一标识实体，必须依赖另一个强实体集才能存在。

部分键/区分符 (partial key/discriminator) 是弱实体集的一组属性，用于在同一个强实体集下，区分不同的弱实体，因此需要强实体的主键，加上区分符，合起来才是弱实体的完整主键。

较为抽象，这里举一个例子：员工和员工家属

体现在 E-R 图中：

Extended E-R Features

TBD