并发操作带来的数据不一致性

• 丢失修改（Lost Update）
• 不可重复读（Non-repeatable Read）
• 读“脏”数据（Dirty Read）

记号

• R(x):读数据x
• W(x):写数据x

不可重复读包括三种情况， 后两种不可重复读有时也称为幻影 现象（Phantom Row）： ◼ 事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读 该数据时，得到与前一次不同的值 ◼ 事务T1按一定条件从数据库中读取了某些数据记录后，事务T2删 除了其中部分记录，当T1再次按相同条件读取数据时，发现某些 记录神秘地消失了。 ◼ 事务T1按一定条件从数据库中读取某些数据记录后，事务T2插入 了一些记录，当T1再次按相同条件读取数据时，发现多了一些记 录。

数据不一致性及并发控制

数据不一致性：由于并发操作破坏了事务的隔离性

并发控制就是要用正确的方式调度并发操作，使一 个用户事务的执行不受其他事务的干扰，从而避免 造成数据的不一致性

对数据库的应用有时允许某些不一致性，例如有些 统计工作涉及数据量很大，读到一些“脏”数据对统 计精度没什么影响，可以降低对一致性的要求以减 少系统开销

并发控制的主要技术

• 封锁(Locking)
• 时间戳(Timestamp)
• 乐观控制法
• 多版本并发控制(MVCC)

封锁:

排它锁（Exclusive Locks，简记为X锁）

• 共享锁（Share Locks，简记为S锁

排它锁又称为写锁

• 若事务T对数据对象A加 上X锁，则只允许T读取 和修改A，其它任何事 务都不能再对A加任何 类型的锁，直到T释放A 上的锁
• 保证其他事务在T释放A 上的锁之前不能再读取 和修改A

共享锁又称为读锁

• 若事务T对数据对象A加 上S锁，则事务T可以读 A但不能修改A，其它事 务只能再对A加S锁，而 不能加X锁，直到T释放 A上的S锁
• 保证其他事务可以读A， 但在T释放A上的S锁之 前不能对A做任何修改

在运用X锁和S锁对数据对象加锁时，需要约定一些 规则，这些规则为封锁协议（Locking Protocol）。

• 何时申请X锁或S锁
• 持锁时间
• 何时释放

Starvation

避免活锁：采用先来先服务的策略 ◼ 当多个事务请求封锁同一数据对象时 ◼ 按请求封锁的先后次序对这些事务排队 ◼ 该数据对象上的锁一旦释放，首先批准申请队列中第一个事务获得锁

死锁

是两个或多个事务都已封锁了一些数据对象，然后又都请求 对已为其他事务封锁的数据对象加锁，从而出现死等待。

解除死锁 ◼ 选择一个处理死锁代价最小的事务，将其撤消 ◼ 释放此事务持有的所有的锁，使其它事务能继 续运行下去

Transaction Schedule

对于并发程序, 必须要考虑按照什么样的顺序进行调度.

可串行化(Serializable)调度

多个事务的并发执行是正确的，当且仅当其结 果与按某一次序串行地执行这些事务时的结果相同

冲突可串行化 (一个比可串行化更严格的条件)

冲突可串行化调度是可串行化调度的充分不必要条件

两段锁协议

指所有事务必须分两个阶段对数 据项加锁和解锁

遵守两段锁协议的调度一定是一个可串 行化调度。

数据库管理系统普遍采用两段锁协议的方法实 现并发调度的可串行性，从而保证调度的正确 性

两段锁协议，指所有事务必须分两个阶段对数据项加锁和解锁

• 在对任何数据进行读、写操作之前，事务首先要获 得对该数据的封锁
• 在释放一个封锁之后，事务不再申请和获得任何其 他封锁

遵守两段锁协议的事务可能发生死锁

Locking Granularity

多粒度封锁(Multiple Granularity Locking)

• 在一个系统中同时支持多种封锁粒度供不同的事务 选择

选择封锁粒度，同时考虑封锁开销和并发度两 个因素, 适当选择封锁粒度

• 需要处理多个关系的大量元组的用户事务：以数据 库为封锁单位
• 需要处理大量元组的用户事务：以关系为封锁单元
• 只处理少量元组的用户事务：以元组为封锁单位

非常自然的设计

表示上, 可以用树形结构里表示不同粒度的locking

多粒度树

• 以树形结构来表示多级封锁粒度
• 根结点是整个数据库，表示最大的数据粒度
• 叶结点表示最小的数据粒度

在多粒度封锁中一个数据对象可能以两种方式封锁：

• 显式封锁: 直接加到数据对象上的封锁
• 隐式封锁:是该数据对象没有独立加锁，是由于其上级 结点加锁而使该数据对象加上了锁

显式封锁和隐式封锁的效果是一样的

对某个数据对象加锁，系统要检查

• 该数据对象

  • 有无显式封锁与之冲突

• 所有上级结点

  • 检查本事务的显式封锁是否与该数据对象上的隐式封锁 冲突：(由上级结点已加的封锁造成的）

• 所有下级结点

  • 看上面的显式封锁是否与本事务的隐式封锁（将加到下 级结点的封锁）冲突

引入意向锁 (intention lock)

意向共享锁(Intent Share Lock，简称IS锁)

• 如果对一个数据对象加IS锁，表示它的后裔结 点拟（意向）加S锁。
• 例如：事务T1要对R1中某个元组加S锁，则要 首先对关系R1和数据库加IS锁

意向排它锁(Intent Exclusive Lock，简称IX 锁)

• 如果对一个数据对象加IX锁，表示它的后裔结 点拟（意向）加X锁。
• 例如：事务T1要对R1中某个元组加X锁，则要 首先对关系R1和数据库加IX锁

Refererences:

R. Ramakrishnan and J. Gehrke, Database Management Systems, 19.1-19.6

1. Relational Schema

$\textbf{Definition}$ formally, a relation schema $R$ can be defined as $R=(U, D, DOM, F)$, where

• $R:$ 关系名
• $U:$ 组成该关系的属性的集合
• $D:$ $U$ 中属性所来自的域
• $DOM:$ 属性向域的映象集合 (常常直接说明为属性的类型 & 长度)
• $F:$ 属性组 $U$ 上的一组数据依赖

也可以简记为 $R(U)$ 或 $R(A_1, A_2, ..., A_n)$, where $A_1, A_2, ..., A_n$ 为属性名称

由于$D$, $DOM$ 与模式设计关系不大, 因此可以把关系模式看作一个三元组

当且仅当 $U$ 上的一个关系 $r$ 满足 $F$ 时, $r$ 称为关系模式 $R$ 的一个关系.

作为二维表, 关系要符合一个最基本的条件: 每个分量必须是不可分开的数据项. 满足了这个条件的关系模式就属于第一范式 (1NF)

数据依赖: 是一个关系内部属性与属性之间的一种约束关系 (本质上是现实世界属性间相互联系的抽象).
主要类型

• 函数依赖 (Functional Dependency, 简记为$\textsf{FD}$)
• 多值依赖 (Multi-Valued Dependency, 简记为 $\textsf{MVD}$)

2. FD & Key

2.1. Functional Dependency

Definition of Functional Dependency: A functional dependency is a kind of integrity constraint that geralizes the concept of a key.

我们通过 FD 的概念来刻画属性之间的依赖关系.
注意函数依赖的对象是属性集合: 属性集合与属性集合之间产生函数依赖

Definition of Determinant

Suppose $R(U)$ is a relation schema over a set $U$ of attributes, and $X,Y\subset U$ are two sets of attributes. if there is a mapping $f:X\to Y$, then we say "$X$ functionally determines $Y$ " or “$Y$ functionally depends on $X$”, denoted by $X\to Y$. $X$ is then called the Determinant (决定因素) of this functional dependency.

Similarly,

• if $X\to Y$ and $Y\to X$, then we say $X$ and $Y$ are equivalent and denote this by $X\leftarrow \rightarrow Y$.

• if $Y$ is not functionally dependent on $X$, then we denote this by $X\not \to Y$.

• trivial FD: $X\to Y \land Y\subset X$

• non-trivial FD: $X\to Y\land Y\not \subset X$

Definition of Closure of a Set of Attributes

The set of all FDs implied by a given set $F$ of FDs is called the closure of $F$, denoted as $F^+$.

2.2. Armstrong’s Axioms

Definition of Armstrong’s Axioms: The following FD rules can be applied to all FDs:

• Reflexivity: If $Y\subset X$, then $X\to Y$
• Augmentation: If $X\to Y$, then forall $Z$, $XZ\to YZ$
• Transitivity: If $X\to Y$ and $Y\to Z$, then $X\to Z$

It can be proved that Axioms of Armstrong are:

• Sound: in that they generate only FDs in $F^+$ when applied to a set $F$ of FDs, and
• Complete: in that they generate all FDs in $F^+$.

It is convenient to use some additional rules while reasoning about $F^+$:

• Union: If $X\to Y$ and $X\to Z$, then $X\to YZ$.
• Decomposition: If $X\to YZ$, then $X\to Y$ and $X\to Z$.

$\textbf{Definition}$: Complete, Partial and Transitive Functional Dependency

也就是说,
候选键是不含有多余属性的超键
超键是在关系中能唯一标识元组的属性集 (显然, 超键可以很大, 甚至极端一点, 超键可以是上面的 $U$ )

主键是一种设计, 用户可以根据需要从任何一个候选键中选择一个作为主键

3. Normal Forms and Decomposition

3.1. Several Types of Functional Dependencies

在 $R(U)$ 中,

• 如果 $X\to Y$, 并且对于 $X$ 的任何一个真子集 $X^\prime$, 都有 $X^\prime\not \to Y$, 则称 $Y$ 对 $X$ 完全函数依赖. 记作 $X \stackrel F{\to} Y$

• 如果 $X\to Y$, 但是 $Y$ 不完全函数依赖于 $X$, 则称 $Y$ 对 $X$ 部分函数依赖, 记作 $X\stackrel P \to Y$

• 如果 $Y\to Z$, 且 $Y \not \subset X$, 且 $Y \not \to X$, 但是 $X \stackrel F{\to} Y$, 则称 $Y$ 对 $X$ 传递函数依赖, 记作 $X\stackrel T \to Y$

用非形式化的语言解释, 就是说:

• 如果 $X$ 能决定 $Y$ , 并且 $X$ 再少一点属性都不能决定 $Y$ , 那么称 $X \stackrel F{\to} Y$
• 如果 $X$ 能决定 $Y$ , 并且 $X$ 的某一组子属性就可以决定 $Y$ , 那么称 $X \stackrel P{\to} Y$
• 如果 $X$ 能决定 $Y$ , 并且 $Y$ 能决定 $Z$, 但是 $Y$ 不能决定 $X$, 那么称 $X \stackrel T{\to} Y$ (说明传递依赖是比较弱的关系, 如果 $Y$ 和 $X$ 能相互决定的话, $X$ 和 $Y$ 在形式上是等价关系, $Z$ 将直接由 $X$ 决定)

3.2. Normal Forms

Given a relation schema, we need to decide whether it is a good design or we need to decompose it into smaller relations. To provide such guidance, several normal forms have been proposed.

也就是说, 给定一个关系模式, 我们只需要知道它恰好符合哪一种范式, 从而可以知道它是否是一个好的设计, 或者我们需要将其分解为更小的关系.

这篇文章对范式给出了非常好的介绍

根据严苛程度, 可以将范式分为:

• $\text{1NF}:$ 关系中的每个属性都不可再分
• $\text{2NF}:$ 在 $1\text{NF}$的基础之上, 消除了non-primary attributes 对于 candidate keys 的 部分函数依赖 (i.e. 每个非主键列都完全依赖于主键, 而不是依赖于部分主键)
• $\text{3NF}:$ 在 $2\text{NF}$ 的基础之上, 消除了non-primary attributes 对于 candidate keys 的 传递函数依赖 (i.e. 消除传递依赖)
• $\text{BCNF}:$ 在 $3\text{NF}$ 的基础上消除 primary attributes 对于键的 partial and transitive functional dependencies
• $\text{4NF}$
• $\text{5NF}$

where: $5\text{NF} \subset 4\text{NF} \subset \text{BCNF} \subset \text{3NF} \subset \text{2NF} \subset \text{1NF}$

这里要注意.

1. $2\text{NF}$: 既然是数据库, 那么一切 non-primary attributes 都是依赖于每一个 candidate key 的. 我们只是希望数据不冗余, 所以我们要求每个 non-primary attributes 不能 partial dependent 于 candidate key.
2. 一般来说 $1\text{NF}$ 和 $2\text{NF}$ 在数据库设计中都是可以忽略的. 我们主要的工作是确保数据库的设计符合 $3\text{NF}$. 到 $\text{BCNF}$ 和 $4\text{NF}$ 的时候就变成一个 tradeoff 问题了
3. $R$ satisfies $3\text{NF}$ iff every non-trivial FD $X\to Y$ of $R$ saitisfies either “$X$ is a superkey” or “$Y$ is part of a candidate key”.
4. $R$ satisfies $\text{BCNF}$ iff every non-trivial FD $X\to Y$ of $R$ saitisfies “$X$ is a superkey”.

4. Decomposition

某一关系模式$R$ 为第 $n$ 范式, 可简记为 $R\in n\text{NF}$. 一个低一级范式的关系模式, 通过模式分解 (schema decomposition) 可以转换为若干个高一级范式的关系模式的集合, 这种过程就叫规范化 (normalization).

A decomposition should preserve two important properties:

• Lossless Join: 通过连接操作, 可以恢复原来的关系
• Dependency Preservation: 保持原来的函数依赖

4.1. Lossless Join Decomposition

Definition of Lessless-join Decomposition.
A decomposition of $R$ into two schemas with attribute sets $X$ and $Y$ is said to be a lossless-join decomposition with respect to $F$ if, for every instance $r$ of $R$ that satisfies the dependencies in $F$, $\pi_X(r)\Join \pi_Y (r) = r$.

Note that $r\subset\pi_X(r)\Join \pi_Y (r)$ always holds, but the reverse may not be true. The condition $r=\pi_X(r)\Join \pi_Y (r)$ is called lossless join.
All decompositions used to eliminate redundancy must be lossless. The following simple test is very useful

Theorem Let $R$ be a relation and $F$ be a set of FDs that hold over $R$. The decomposition of $R$ into relations with attribute sets $R_1$ and $R_2$ is lossless if and only if $F^+$ contains either the FD $R_1 \cap R_2 \to R_1$ or the FD $R_1 \cap R_2 \to R_2$.

4.2. Dependency Preservation Decomposition

Definition of Dependency Preservation Decomposition.
The decomposition of relation schema $R$ with FDs $F$ into schemas with attribute sets $X$ and $Y$ is dependency-preserving if $(F_X ∪ F_Y )^+ = F^+$.

Decomposition Algorithm

Algorithm of Decomposition into BCNF

1. Start with the original relation $R$ and the set of FDs $F$.
2. Check if $R$ is in BCNF. If so, stop.
3. If not, find a FD $X\to Y$ that violates BCNF.
4. Decompose $R$ into $R_1(XY)$ and $R_2(XZ)$, where $Z=R-Y$.
5. Repeat the process for $R_1$ and $R_2$.

Note that it is always possible to decompose a relation into BCNF and that the decomposition is lossless, but it may not be dependency preserving.

Algorithm of Decomposition into 3NF

// TODO

Note that it is always possible to decompose a relation into BCNF and that the decomposition is lossless and dependency preserving.

Refererences:

R. Ramakrishnan and J. Gehrke, Database Management Systems, 4.2-4.3

1. Relations

1.1. Definitions

Definition of Domain: domain is a set of values with the same data type.

Definition of Cartesian Product: For given domains $D_1, D_2, ..., D_n$, their Cartesian product is defined as

这里的笛卡尔积严格地讲是广义笛卡尔积(Extended Cartesian Product)。在不会出现混淆的情况下广义笛卡尔积也称为笛卡尔积.
更加精确的定义: 两个分别为 $n$ 目和 $m$ 目的关系 $R$ 和 $S$ 的广义笛卡尔积是一个 $(n+m)$ 列的元组的集合。元组的前 $n$ 列是关系 $R$ 的一个元组, 后 $m$ 列是关系 $S$ 的一个元组。若 $R$ 有 $k_1$ 个元组, $S$ 有 $k_2$ 个元组, 则关系 $R$ 和关系 $S$ 的广义笛卡尔积有 $k_1×k_2$ 个元组。记作：

Definition of Tuple: Every element of a cartesian product $(d_1, d_2, …, d_n)$ is called a $n$-tuple or just a tuple.

Definition of Component (分量): every (column) value of a $n$-tuple $(d_1, d_2,\dots, d_n)$ i.e. $d_i$ is called a component of the tuple.

Definition of Cardinal number (基数): If every $D_i\ (i＝1, 2,\ldots, n)$ is a finite set, then the cardinal number of $D_1\times D_2\times\ldots\times D_n$ is recursively defined as

Definition of Relation: Every element of the set $D_1\times D_2\times\ldots\times D_n$ is called a relation on the domains $D_1, D_2, ..., D_n$, denoted by $R(D_1, D_2, ..., D_n)$, where:

• $R: $ is the name of the relation
• $n:$ is called the degree (目/度) of the relation

Definition of Attribute: Note that every column can correspond to the same domain, so to distinguish them, each column must be given a name, called an attribute. A relation of $n$ degrees must have $n$ attributes.

Definition of Key

• Candidate Key: A set of attributes that just uniquely identifies a tuple (by just I mean the smallest set of attributes that can uniquely identify a tuple)
• Super Key: A set of attributes that uniquely identifies a tuple.
• Primary Key: Any one of the candidate keys can be a primary key.
• Prime Attribute: All attributes in a candidate key are called prime attributes
• Non-Prime/Non-key Attribute: All attributes that are not in the candidate key are called non-prime attributes

All attributes in a relation are either prime or non-prime.

1.2. Relations

在数据库中, 关系可以分成如下几类

• 基本关系 (基本表或基表): 实际存在的表, 是实际存储数据的逻辑表示.
• 查询表: 查询结果对应的表.
• 视图表: 由基本表或其他视图表导出的表, 是虚表, 不对应实际存储的数据.

我们在这里主要研究基本关系, 基本关系具有如下的性质.

• 列是同质的 (Homogeneous): 每一列中的分量是同一类型的数据, 来自同一个域
• 不同的列可出自同一个域: 其中的每一列称为一个属性, 不同的属性要给予不同的属性名
• 列的顺序无所谓: 列的次序可以任意交换
• 任意两个元组的候选键不能相同
• 行的顺序无所谓: 行的次序可以任意交换
• 分量必须取原子值

1.3. Relational Schema

Definition: formally, $\text{relational schema}$ can be defined as $R(U, D, DOM, F)$, where

• $R:$ 关系名
• $U:$ 组成该关系的属性的集合
• $D:$ $U$ 中属性所来自的域
• $DOM:$ 属性向域的映象集合 (常常直接说明为属性的类型 & 长度)
• $F:$ 属性间数据的依赖关系的集合

也可以简记为 $R(U)$ 或 $R(A_1, A_2, ..., A_n)$, where $A_1, A_2, ..., A_n$ 为属性名称

Normally, we can consider relation as an instance of a given relational schema. But intuitionally I don’t see any differences

1.4. Relational Database

在一个给定的应用领域中, 所有关系的集合构成一个关系数据库

Definition of Type and Value of a relational schema

• Type: 关系数据库模式, 是对关系数据库的描述
• Value: 关系模式在某一时刻对应的关系的集合, 通常称为关系数据库

2. Relational Integrity

2.1. Constraints

• Entity Integrity Constraint: 关系数据库中, 主键/主属性不能为NULL (基本表通常对应现实世界的一个实体集, 而现实世界中的实体是可区分的, 即它们具有某种唯一性标识. )
• Referential Integrity Constraint: 关系数据库中, 确保在一个表中引用另一个表时, 引用有效的行. i.e. 外键值必须在关联表中存在. (在关系模型中实体及实体间的联系都是用关系来描述的, 自然存在着关系与关系间的引用)
• User-Defined Integrity Constraint: 由用户定义的一组规则, 用于限制对表的访问和维护, 例如 CHECK 约束、触发器等.

其中, 前两者由关系系统自动支持, 后者应用时需要遵循的语义规则, 体现了具体领域中的语义约束

Definition of Foreign Key

说白了就是在当前表中不是主键但是在别的表中是主键的键

设 $F$ 是基本关系 $R$ 的一个或一组属性, 但不是关系 $R$ 的键 (key). 如果 $F$ 与基本关系 $S$ 的主键 $K_s$ 相对应, 则称 $F$ 是 $R$ 的外键. where

• $R:$ 参照 / 引用关系 (Referencing Relation)
• $S:$ 被参照 / 被引用关系 (Referenced Relation) / 目标关系 (Target Relation)

Definition of Referential Integrity Constraint

若属性 (或属性组) $F$ 是基本关系 $R$ 的外键它与基本关系 $S$ 的主键 $K_s$ 相对应 (基本关系 $R$ 和 $S$ 不 一定是不同的关系), 则对于 $R$ 中每个元组在 $F$ 上的值必须为下列两种情况之一

• 空值 ($F$ 的每个属性值均为空值)
• $S$ 中某个元组的主键值

3. Relational Algebra

关系代数是一种抽象的查询语言, 它用对关系的运算来表达查询.

Observe that queries in algebra are composed using a collection of operators. A fundamental property is that every operator in the algebra accepts (one or two) relation instances as arguments and returns a relation instance as the result.

Codd (the C of BCNF) 是关系代数(数据库)的创始人, 他提出了六种原始运算 (还有其他的运算可以由原始运算导出)

选择, 投影, Descartes积, 并集, 差集, 重命名. 其中, 并集, 差集和Descartes积是集合论中的基本运算

除此之外, 关系代数(数据库)中还有一些别的运算, 包括连接和类似连接的计算, 还有除法

3.1. Set Operations

Definition of Union

If two relations $R$ and $S$ have the same schema (so their each attribute should come from the same domain respectively).
Then the union of these two relations is

Definition of Difference

If two relations $R$ and $S$ have the same schema. Then the difference between $R$ and $S$ is

也就是在数据库中, 具有相同性质和数量列的两个表, 行可以相减 (集合意义上的减)

Definition of Intersection

If two relations $R$ and $S$ have the same schema. Then the intersection of these two relations is

The reason we use such a definition instead of the native one is because this operation is not raw in the relational algebra, i.e. we can derive it from the difference operation.

Extended Cartesian Product ( $\times$ ): 见上文

3.2. Related Symbols

$R:$ 关系模式 (对应于关系数据库中的一张表)

$t\in R:$ $t$ 是 $R$ 的一个元组 (这里可见, 我们认为表的基本元素是行而不是列)

$t[A_i]:$ 元组 $t$ 中相应于属性 $A_i$ 的一个分量

$A = \{A_{i_1}, A_{i_2}, ..., A_{i_k}\}:$ $A$ 称为属性列或属性组.

$t[A]:$ 元组 $t$ 中相应于属性组 $A$ 中所有属性的分量集合

$\bar A:$ $\{A_{1}, A_{2}, ..., A_{n}\} - A$

3.3. Relational Operations

1. Selection

Given a relation (table) $R$ and a condition $\varphi$, return some tuples of this relation

Definition of Selection: 广义选择 是写为 $\sigma _{\varphi }(R)$ 的一元运算, 这里的 $\varphi$ 是由正常选择中所允许的原子和逻辑算子 $\land , \lor, \lnot$ 构成的命题公式。这种选择选出 $R$ 中使 $\varphi$ 成立的所有元组。可以表示为:

where $\varphi:$ 选择条件, 是一个逻辑表达式, 取值为“真”或“假”

2. Projection

Given a relation (table) $R$ and a set of Attributes $A_1, A_2, \ldots, A_n$

Definition of Projection: 投影是写为 $\Pi_{A_1,\ldots,A_n}(R)$ 的一元运算, 这里的 $A_{1},...,A_{n}$ 是属性名字的集合。这种投影的结果定义为当所有在 $R$ 中的元组被限制为集合 $\{A_{1},...,A_{n}\}$ 的时候所获得的集合. 可以表示为:

其中, $A$ 为 $R$ 中的一些属性列的集合

3. Cartesian Product

Given two relations $R(A_1, A_2, \ldots, A_n)$ and $S(B_1,B_2,\ldots,B_m)$ with no common attributes (even if they have, we still treat these two attributes as different), return a new relation with $m+n$ attributes

where $t_r \textsf{ concat } t_s$ is the concatenation of two tuples $t_r$ and $t_s$.

4. Rename

Given a relation $R(A_1, A_2, \ldots, A_n)$, rename the attributes to $B_1, B_2, \ldots, B_n$

where $B_1, B_2, \ldots, B_n$ are the new names of the attributes.

5. Join ( $\theta$-连接 )

Given two relations $R$ and $S$ and a condition $\theta$, return a new relation with the same schema as the Cartesian product of these two relations, but only the tuples that satisfy the condition are kept.

连接运算就是从两个关系的笛卡尔积中选取属性之间满足一定条件的元组进行连接, i.e.

or

where

• $A$ 和 $B:$ 分别为 $R$ 和 $S$ 上度数相等且可比的属性组
• $\theta:$ 比较运算符

比较特殊地, Join 包括但不限于有 Equijoin (where $\theta$ is $\text{equivalent}$) 的情况. 更加特殊地, Equijoin 包括但不限于有 Natural join (where lines / tuples are $\text{unique}$) 这一情况.

一般来说, $\Join$ 符号就表示自然连接.

4. Outer Join

悬浮元组 (Dangling tuple): 两个关系 $R$ 和 $S$ 在做自然连接时, 关系 $R$ 中某些元组有可能在 $S$ 中不存在公共属性上值相等的元组, 从而造成 $R$ 中这些元组在操作时被舍弃了. 这些被舍弃的元组称为悬浮元组.

如果把悬浮元组也保存在结果关系中, 而在其他属性上填空值 (Null), 就叫做外连接

• 左外连接(LEFT OUTER JOIN或LEFT JOIN): 只保留左边关系R中的悬浮元组
• 右外连接(RIGHT OUTER JOIN或RIGHT JOIN): 只保留右边关系S中的悬浮元组

5. Division ( $÷$ )

给定关系 $R (X, Y)$ 和 $S(Y, Z)$, 其中 $X, Y, Z$为属性组.

$R$ 中的 $Y$ 与 $S$ 中的 $Y$ 可以有不同的属性名, 但必须出自相同的域集. $R$ 与 $S$ 的除运算得到一个新的关系 $P(X)$, $P$ 是 $R$ 中满足下列条件的元组在 $X$ 属性列上的投影:

元组在 $X$ 上分量值 $x$ 的象集 $Y_x$ 包含 $S$ 在 $Y$ 上投影的集合, 记作:

where

• $Y_x:$ $x$ 在 $R$ 中的象集 ( $R$ 中属性组 $X$ 上值为 $x$ 的诸元素在 $Y$ 分量上的集合)
• $x = t_r [X]$

值得注意的是, 在以上的所有关系代数运算中, 最基本的5种运算为 $\cup$, $-$, $\Pi$, $\sigma$ 和 $\times$: 也就是说剩下的运算均可以由这五种运算推导得到.

证明也是相当的 trivial, 只需要把这些定义中的运算全部以集合的形式展开, 进行一些代数恒等变形即可.

1. Database Safety

1.1. Intro

数据共享是数据库的一大特点. 由共享产生的安全性问题于是值得考量. 数据库的安全性是指保护数据库以防止不合法使用所造成的数据泄露、更改或破坏 .

系统安全保护措施是否有效是数据库系统主要的性能指标之一.

数据库的不安全因素:

• 非授权用户对数据库的恶意存取和破坏: 使用用户身份鉴别、存取控制和视图等技术
• 数据库中重要或敏感的数据被泄露: 强制存取控制、数据加密存储和加密传输等.
• 安全环境的脆弱性: 建立一套可信计算机系统的概念和标准 (因为数据库的安全性与计算机系统的安全性紧密联系)

1.2. TCSEC/TDI

Trusted Computer System Evaluation Criteria / Trusted Database Management System Interpretation

TCSEC/TDI安全级别划分按系统可靠或可信程度逐渐增高, 且各安全级别之间具有一种偏序向下兼容的关系

1.3. CC

Common Criteria

CC是一种国际标准，由国际标准化组织（ISO）和国际电工委员会（IEC）共同制定。它是一种针对信息技术产品和系统的评估标准，旨在为用户提供全球范围内适用的评估方法和标准。

CC将安全功能和保护需求定义为一系列称为保护配置（Protection Profile，PP）的文档，PP描述了特定类型的产品或系统所需满足的安全功能要求和安全保证要求。同时，CC还规定了一系列可操作的评估步骤和具体实施方式，以便进行评估并生成评估报告。CC包含七个不同的保护等级，从最低的EAL1到最高的EAL7，每个等级都有明确的技术需求和验证要求。

与TCSEC/TDI相比，CC更加灵活和通用，能够适应不同的业务需求和技术发展。在实践中，CC已经成为国际上公认的信息技术产品和系统评估标准之一，并被广泛应用于各种领域，如政府、军事、金融、制造业等。

2. Access Control

2.1. Intro

存取控制/访问控制 (Access Control) 是 DBMS 的一套子系统, 其功能有如下两条:

• 定义用户权限: DBMS提供适当的语言来定义用户对某一数据对象的操作权力, 存放在数据字典中, 称做安全规则或授权规则
• 检查合法权限: 用户发出存取数据库操作请求时, DBMS查找数据字典, 进行合法权限检查

2.2. DAC

自主存取控制 (Discretionary Access Control), C2级

• 用户对不同的数据对象有不同的存取权限
• 不同的用户对同一对象也有不同的权限
• 用户还可将其拥有的存取权限转授给其他用户

具体来说, DAC可以通过 SQL 的 GRANT 语句和 REVOKE 语句实现.

在设计上, 用户权限 = 数据库对象 + 操作类型

关系数据库系统中有如下图所示的存取控制对象

SQL中的授权机制

DBA

• 拥有所有对象的所有权限
• 根据实际情况不同的权限授予不同的用户

用户:

• 拥有自己建立的对象的全部的操作权限
• 可以使用GRANT，把权限授予其他用户

被授权 (Granted) 的用户:

• 如果具有“继续授权”的许可，可以把获得的权限再授予其他用户

所有授予出去的权力在必要时又都可用 REVOKE 语句收回

GRANT 语句的使用

REVOKE 语句的使用

创建数据库模式的权限

数据库角色: 一组操作权限的集合

DAC 缺点

可能存在数据的“无意泄露”. 因为这种机制仅仅通过对数据的存取权限来进行安全控制, 而数据本身并无安全性标记

• 解决：对系统控制下的所有主客体实施强制存取控制策略

2.3. MAC

强制访问控制 (Mandatory Access Control), B1级

• 每一个数据对象被标以一定的密级

• 每一个用户也被授予某一个级别的许可证

• 对于任意一个对象, 只有具有合法许可证的用户才可以存取

• 用户不能直接感知或进行控制

3. Machanisms

1. 文件系统

1.1. 文件

1.2. 文件系统

操作系统中负责存取和管理信息的模块

观察文件, 需要观察它的两个部分

• 逻辑结构 (逻辑文件)
• 存储结构 (物理文件)

文件系统的功能

由于文件是一种抽象的概念, 因此文件系统的功能也要分层次考虑

面向用户的功能

• 文件的按名存取 (这也是文件系统的主要目的)
• 文件的共享和保护
• 文件的操作和使用

为了构建可靠的文件系统, OS必须考虑的事情是

• 文件目录的建立和维护
• 存储空间的分配和回收
• 数据的保密和保护
• 监督用户存取和修改文件的权限
• 实现在不同存储介质上信息的表示方 式、编址方法、存储次序，以及信息 检索等问题

2. 文件的组织

2.1. 文件的存储

文件存储介质有磁带、光盘和磁盘

两个概念: 卷和块

卷 (Volume): 一个卷可以视为一个文件系统. 从设计的角度来讲, 一个Volume可以认为是一个虚拟存储设备(磁盘/光盘/磁带). 在Windows上, 一个物理磁盘实际上可以分为多个Volume, 每个Volume可以使用不同的文件系统(NTFS, FAT, etc.)

块 (Block): Block是存储器进行数据交换的最小单位. 早期的Block大小一半是512字节, 但是现代Block的大小在4kb~64kb之间

块为什么设计成这么大: 考虑多方面的统计学因素. 实际上, 块的大小很灵活. 同一存储介质的块大小一般相同, 也可以不同(这话说了就像没说)

块是连续存储的吗: 是也不是. 实际上, 块之间留有空隙. 考虑到如下的2点因素

• 设备读写时往往会进行机械操作, 为了确保安全并避免数据损坏，相邻的数据块之间需要留有足够的距离，以免机械部件运动产生干扰或碰撞。
• 某些外围设备可能需要识别不同块之间的分界点，以便正确地读取或写入数据。为了满足这种需求，相邻的数据块之间也会留有一定的间隙，以确保设备能够准确识别块的边界位置。

顺序存取存储设备的信息安排

磁带 & 光盘是典型的顺序存取存储设备

严格依赖信息的物理位置次 序进行定位和读写的存储设备

直接存取存储设备的信息安排

磁盘

它的每个物理记录有确定的位置和唯 一的地址，存取任何一个物理块所需 的时间几乎不依赖于此信息的位置

2.2. 文件的逻辑结构

逻辑文件

i.e.文件的逻辑结构. 也就是完全不管其物理结构的, 用户能够直观感受到的文件

分成两种形式

• 流式文件 (Stream File)
• 记录式文件 (Record File)

GPT: “判断一种文件是流式文件还是记录式文件，需要根据该文件所采用的文件格式和数据组织方式来进行分析。

通常情况下，流式文件是一种顺序型文件，其中数据按照固定的字节流顺序排列。在读写流式文件时，应用程序可以读取或写入任意长度的数据，但必须按照顺序进行，不能跳过或插入数据。

而记录式文件则通常将数据组织成若干个逻辑上的记录，每个记录由多个字段组成。在处理记录式文件时，应用程序通常需要对每个记录进行读取或写入操作，并且每个记录通常具有相同的长度或可变长度，由特定的记录分隔符进行分隔。

例如，在文本文件中，每个字符都被视为一个字节，它们按照顺序排列组成了一整个文件。因此，文本文件是一种典型的流式文件。而在数据库系统中，每个记录代表一个实体，例如一个人、一辆车或一张订单等等，每个记录由若干个字段组成，因此数据库中的数据通常是一种记录式文件。

总之，要判断一个文件是流式文件还是记录式文件，需要分析该文件所采用的文件格式和数据组织方式。”

直观的感受: 有结构的文件就是记录式文件, 无结构的文件就是流式文件

文件系统和数据库系统的区别

DBMS可以支持基于联系的查询 (因为数据库中的记录可以通过数据冗余形成某种联系). 但是文件系统不能支持基于联系的查询

2.3. 记录的成组与分解

这里的记录就是上文 记录式文件 的记录

给出非常愚蠢的定义: 若干个逻辑记录合并成一组，写入一个块叫记录的成组，每块中的逻辑记录数称为块因子

如何实现记录成组: 使用计算机科学中的经典想法——添加一个中间层(buffer)

• 记录的成组操作在输出缓冲区内进行， 凑满一块后才将缓冲区内的信息写到存储介质上

类似的, 先从存储介质上取出一个block, 再取出其中的一个记录, 这样的行为叫做记录的分解

记录成组和分解的优点

• trivially 节省了存储空间 (考虑到存储设备一次性只能传一个block过来, 如果记录不成组的话, 一个block中便只能有一条记录, 是非常浪费的)
• trivially 减少IO次数

当然也带来一些不足一提的副作用:

• 提前读: 读取一个逻辑记录时, 会将和它在一个block的一堆逻辑记录都带出来
• 推迟写: 写完一个逻辑记录后, 需要将它后续的一堆逻辑记录都写完并构成一个完整的block才能写入存储设备

2.4. 文件的物理结构

文件的物理结构 $\iff$ 物理文件

从设计的角度来讲, 文件的物理结构影响文件系统的性能

顺序文件

$O(n)$

将逻辑上连续的文件存放到存储介质中相邻的block中, 以这样存储方式进行存储的文件叫做顺序文件(连续文件). 一些典型的例子就是系统文件和批处理文件(bat, sh)

trivially, 顺序文件的存储是很快的, 但是任何修改都会显得很麻烦(可能会影响相邻的文件), 同时在存储之前必须先知道文件的大小. 因此从设计的角度来讲, 多读少写的文件更加适合以这样的方式存储. 系统文件就是很典型的例子.

从设计的角度来讲, 顺序文件的存储很像C语言里的数组.

连接文件

$O(n)$, 或者叫串联文件

愚蠢的又平凡定义: 用一个叫连接块的东西, 来指向下一个物理块 (因为物理块是最小单位). 同时如果连接块的value为0, 它就是结尾

我真不理解为什么要设置这么多混淆的, 矛盾的, 愚蠢的, 不可复用的定义.

从设计的角度来讲, 顺序文件的存储很像C语言里的链表. 它的存储, 修改, 删除都非常方便, 但是不方便的是一切涉及到读的操作. 并且由于其物理结构的性质, 只能顺序存取

直接文件

$O(1)$, 或者叫散列文件

通过计算记录的关键字建立与其物理存储地址之间的对应关系, 常常使用Hash散列. 那么很明显, 这样的文件应该具有Hash散列数据的性质.

为了解决Hash函数中不可避免的冲突, 这里引入几个无比trivial又中二的称呼:

• 拉链法
• 循环探查法
• 二次散列法
• 溢出区法

索引文件

$O(1)$, 基本思想: 建立一个中间层

索引文件在文件存储器上分两个区

• 索引区
• 数据区

访问索引文件需两步操作

• 第一步查找索引表
• 第二步获得记录物理地址

为每个文件建立了一张索引表，其中，每个表目包含一个记录的键(或逻辑记录号)及其存储地址. 这样的设计是我很欣赏的.

在Unix下, 可以用stat <PATH> 来查看文件的索引结构

3. 文件目录

3.1. 目录结构

文件目录是实现文件的 按名存取 的关键数据结构. 为了解决不同用户文件的 命名冲突 问题，通常在文件系统中采用多级目录.

具体来说, Unix系统中, 通过 目录项 这一数据结构实现文件系统的按名存取功能.

比较重要的一点是, 文件目录需要永久保存，因此也组织成文件存放在磁盘上，称目录文件

• 一级目录结构: 想象一下所有文件存储在一个目录下
• 二级目录结构: 底层目录用于存储不同的用户信息, 高级目录用户存储每个用户的文件 (很有点RBAC的感觉)
• 树形目录结构

值得注意的是, 在树形目录结构中, 一个文件的全名包括从根目录开始到文件为止, 通路上遇到的所有子目录路径, 又称为路径名

也就是说路径名不是路径的名字, 是这个文件的名字

值得区分的是, 目录和路径是不一样的概念:

• 目录（Directory）是指在文件系统中用于组织和管理文件和子目录的一种数据结构。每个目录都可以包含若干个文件和子目录，并且可以通过目录索引来访问其中的内容。在Unix和Linux等操作系统中，目录通常用一个特殊的文件来表示，其中存储了目录下的所有文件和子目录信息。
• 路径（Path）是指用于标识文件或目录在文件系统中位置的字符串。通常以根目录（如“/”）为起点，逐级列出该文件或目录所在的目录名，直到最后一级为止。例如，“/usr/local/bin/test.sh”就是一个典型的文件路径，表示test.sh文件位于/usr/local/bin目录下。

文件系统用**目录来组织文件**

3.2. 文件目录的管理

这里前面一部分主要讲一些指令, trivial

树形文件系统存在的一个问题是：当一个文件经过许多目录节点时, 使用很不方便; 系统在沿路径查找目录时, 往往要多次访问文件存储器，使访问速度大大减慢.

从设计的角度来讲, 一种有效办法是把常用和正在使用的那些文件目录复制进主存, 这样, 既不增加太多的主存开销. 又可明显减少目录查找时间.

为了实现如上的设计, 设计一种新的中间层, 叫做活动文件表, 抽象出文件的两种平凡的操作:

• 打开: 系统可以为每个用户进程建立一张活动文件表，当用户使用一个文件之前，先通过 打开 操作，把该文件有关目录信息复制到指定主存区域, 有关信息填入活动文件表, 以建立用户进程和该文件索引的联系. (这也就是大文件打开时间会比较长, 特别大的文件打开时可能会死机)
• 关闭: 当不再使用该文件时，使用 关闭, 切断用户进程和这个文件的联系. 同时, 若该目录已被修改过，则应更新辅存中对应的文件目录

4. 文件共享, 保护和保密

从信息安全 (CIA) 的角度, 文件的设计需要考虑如下几点

• 文件共享: 是指不同用户共同使用某些文件 (Accessibility)
• 文件保护: 是指防止文件被破坏 (Integrity)
• 文件保密: 则是指防止文件及其内容被其他用户窃取 (Confidentiality)

4.1. 共享

很自然地, 操作系统必须为文件共享提供并发控制. 这一点我们会在并发部分仔细谈论.

4.2. 保护

常用的文件保护办法

文件副本

• 动态多副本技术: 是在多个介质上维持同一内容的文件，并且在更新内容时同时进行
• 转储, 备份与恢复: 定时把文件复制转储到其它介质上，当某介质上出现故障时，复原转储文件

文件存取矩阵与文件存取表

也就是信息安全课上讲的那个

实际上限制了用户能访问文件的部分权限, 是一种RBAC

设计文件属性

rwx, user等信息便是非常典型的文件属性. 使用chmod, chgrp, chown等指令便可以修改对应的文件属性.

5. 文件的使用

5.1. 存取方法

文件存取方法是操作系统为用户程序提供的使用文件的技术和手段, 在某种程度上依赖于文件的物理结构.

顺序存取

$O(n)$

指的是像磁带这种存储设备上, 想要读或者写某一个文件, 必须从头扫描找到它.

直接存取

$O(1)$, 也叫做随机存取

指的是按地址索引. 可以直接访问存储空间内任何一处的数据. 典型的例子就是磁盘上的文件, 既可以随机存取, 又可以顺序存取

索引存取

$O(1)$, idk, or maybe $O(\log n)$

要查表. 一般按照二分查找等方法索引.

5.2. 文件的使用

用户通过两类接口来与文件系统相联系.

• 文件操作命令: cp, mv, find, mkdir, etc.
• 文件类系统调用: 建立, 打开, 读/写, 定位, 关闭, 撤销

建立文件: 在相应设备上建立一个文件目录项, 为文件分配第一个物理块, 在活动文件表中申请一个项, 登记有关目录信息, 并返回一个文件句柄

撤销文件: 若文件没有关闭, 先关闭文件; 若为共享文件, 进行联访处理; 在目录文件中删去相应目录项; 释放文件占用的文件存储空间

打开文件: 将活动文件表中该文件的“当前 使用用户数”减1；若此值为0，则收回此活 动文件表；完成“推迟写” ；若活动文件表 目内容已被改过，则应先将表目内容写回文 件存储器上相应表目中，以使文件目录保持 最新状态

而open的返回值是一个整数类型的文件描述符 (File Descriptor)

读/写文件: 按文件句柄从活动文件表中找到该文件的目录项信息; 根据目录项指出的该文件的逻辑和物理组织方式, 把相关逻辑记录转换成物理块

定位文件

6. 文件系统实现

6.1. 辅存空间管理

主要是碎片管理: 由于被多用户共享, 文件碎片经常出现.

解决方法: 定期地对文件重新组织，让其存放在连续存储区中. (trivial but necessary)

辅存空间的分配方式

• 连续分配：存放在辅存空间连续存储区中 (连续的物理块号) 优点是顺序访问时速度快，管理较为简单， 但为了获得足够大的连续存储区，需定时进行‘碎片’整理
• 非连续分配：动态分配给若干扇区或簇（几 个连续扇区），不要求连续优点是辅存空间管理效率高，便于文件动态增长和收缩

空闲块的管理

• 位示图法: FAT12文件系统
• 空闲块成组连接法: 使用如下图的方式将空闲块组织起来

6.2. 文件系统的实现层次

哲学家就餐问题

mutex: mutual exclusion

只有可能互斥的对象之间才需要有mutex

1. 并发进程

1.1. 顺序程序设计

1.2. 进程的并发性

并发进程分类：

• 无关的
• 交互的

$\text{Bernstein}$ 条件: 并发进程的无关性是进程的执行与时间无关的一个充分条件

程序 $p_i$ 在执行期间改变的变量集 为 $W(p_i) = \{b_1, b_2, ...b_m\}$

两个进程的程序 $p_i$ 和 $p_j$ 满足$\text{Bernstein}$ 条件 $\iff$

• $R(p_i) \cap W(p_j) = \phi$
• $R(p_j) \cap W(p_i) = \phi$
• $W(p_i) \cap W(p_j) = \phi$

在这样的条件下, 并发进程的执行与时间无关

两个问题

• 机票问题
• 主存管理问题

1.3. 进程的交互：竞争和协作

竞争与协作是进程之间的两种基本的关系

竞争关系带来两种问题:

• 死锁
• 饥饿

这里参考了这篇文章

为了解决进程间竞争关系（间接制约关系）而引入进程互斥；

为了解决进程间松散的协作关系( 直接制约关系)而引入进程同步；

为了解决进程间紧密的协作关系而引入进程通信。

2. 临界区管理

2.1. 互斥与临界区

并发进程中涉及到共享变量的程序段叫 “临界区” (critical section), 共享变量代表的资源叫“临界资源”.

2.2. 临界区管理的尝试

直接尝试: 有bug

临界区管理的软件方法: Peterson算法 (设计比较巧妙, 能够实现良好的临界区管理)

临界区管理的硬件方法:

• 关中断
• 测试并建立指令
• 对换指令

硬件这一部分跳过了, 不知道重不重要

2.3. 实现临界区管理的硬件设施

3. 信号量与PV操作

“忙式等待”方法解决临界区调度问题的缺点

上面的Peterson算法属于忙式等待的方法: 也就是一种轮询, 要一直查看是否互斥对象忙. 显然对象很多时, Peterson算法需要for嵌套while, 时间复杂度很高, 而且一直占用CPU, 设计不是很合理. 同时从软件工程的角度来讲, 将测试能否进入临界区的职责 (responsibility) 推给各个竞争的进程会削弱系统的可靠性, 加重用户编程负担

我们在这里提出阻塞式等待的方法: 也就是所谓的PV操作, 我们这里不需要进程来查看共享资源是否被占用, 相反地, 当资源的占有情况发生改变的时候, 我们会主动通知进程

哲学家就餐问题的一些解决方案

• 至多允许四个哲学家同时取叉子(C. A. R. Hoare方案)
• 奇数号先取左手边的叉子，偶数号先取右手边的叉子
• 每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取 (第五版教材, Page 188, AND型信号量)

4. 管程

4.1. 管程和条件变量

管程的定义: 管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块

管程的概念是由Brinch Hansen提出的, 但是由Hoare改进

4.2. 管程的实现

4.3. 管程求解进程的同步与互斥问题

5. 进程通信

直观上感觉挺 trivial, 但是仔细一想感觉蛮神奇.

但是第五节并不考, 所以没空看了

5.1. 进程通信

5.2. 高级进程通信机制

6. 死锁

6.1. 发生

6.2. 防止

6.3. 避免

6.4. 检测和解除

1. Intro to SQL

1.1. SQL的特点

SQL (Structured Query Language) a general purpose, highly functional, declarative language specifically designed to work with relational databases, is the standard language for relational database management systems. It has the following characteristics:

• 综合统一 (DDL + DML + DCL, 并且可以独立完成数据库生命周期中的全部活动)
• 高度非过程化
• Set-oriented 的操作方式 (而非关系数据模型采用面向记录的操作方式, 操作对象是一条记录)
• 以同一种语法结构提供两种使用方法 (既是独立的语言, 又可以嵌入到高级语言如C++, Java中)
• 语言简洁, 易学易用 (it’s core function only requires 9 verbs)
  • 数据定义: CREATE, DROP, ALTER
  • 数据查询: SELECT
  • 数据操作: INSERT, UPDATE, DELETE
  • 数据控制: GRANT, REVOKE

There are three major components of SQL:

• DDL: data definition language (create, alter, drop)
• DML: data manipulation language (insert, update, delete)
• DCL: data control language

1.2. SQL与数据库三级模式

SQL（Structured Query Language）是一种关系型数据库的标准查询语言, 是管理和操作关系型数据库的重要工具之一. 与此同时, 数据库通常被描述为三级模式的组合, 包括外模式, 模式和内模式.

1. 外模式（External Schema）: 也称用户模式, 是数据库系统中最高层次的抽象, 它定义了用户可以访问和操作的数据视图. 外模式是基于用户需求和角色设计的, 不同的用户可能有不同的外模式. 例如, 一个销售人员只需要访问客户订单信息, 而不需要了解订单的生产过程；而一个生产经理则需要访问订单的详细信息以及生产过程的相关数据.
2. 模式（Conceptual Schema）: 也称全局模式或逻辑模式, 是数据库系统的中间层, 它定义了整个数据库的逻辑结构和关系. 模式是由数据库管理员设计和维护的, 它表示了所有数据的集合和它们之间的关系, 但并不涉及具体的存储方式和物理结构.
3. 内模式（Internal Schema）: 也称存储模式或物理模式, 是数据库系统的最底层, 它定义了数据在物理媒介上的存储形式和访问路径. 内模式包括数据项的实际存储方式, 索引结构, 文件存储方式等, 它是由数据库管理系统（DBMS）根据模式和外模式转换而来的.

总体来说, 外模式, 模式和内模式构成了数据库系统的三级模式, 这种分层结构提供了一种灵活和高效的方式来设计和管理数据库. 通过将数据和应用程序之间的逻辑隔离开来, 可以简化不同用户之间的访问过程, 并且增强了数据库的可维护性和安全性. 同时, SQL 作为一种标准查询语言, 可以方便地操作和管理不同级别的数据.

基本表

• 本身独立存在的表
• 一个关系对应一个基本表
• 一个（或多个）基本表对应一个存储文件
• 一个表可以带若干索引

存储文件

• 逻辑结构组成了关系数据库的内模式
• 物理结构对用户是隐蔽的

视图

• 从一个或几个基本表导出的表
• 数据库中只存放视图的定义而不存放视图对应的数据
• 视图是一个虚表
• 用户可以在视图上再定义视图

2. DDL

可以根据菜鸟教程来速成学习基本的SQL语句, 效果还不错

2.1. Creating Table

Consider such a E-R diagram

Student(snum:int, sname:String, major:String, level:String, age:int)
Class(cname:String, meets_at:String,room:String, fid:int)
Enroll(snum:int, cname:String)

The the SQL code for creating the tables is

CREATE TABLE Student (
  snum BIGINT,
  sname VARCHAR(50),
  major VARCHAR(50),
  level CHAR(2),
  age INT,
  PRIMARY KEY (snum)
);
CREATE TABLE Class (
  cname VARCHAR(50),
  meets_at VARCHAR(50),
  room VARCHAR(50),
  fid BIGINT,
  PRIMARY KEY (cname)
);
CREATE TABLE Enroll (
  snum BIGINT,
  cname VARCHAR(50),
  PRIMARY KEY (snum, cname), -- 复合主键
  FOREIGN KEY (snum) REFERENCES Student(snum), -- 确保外键的完整性
  FOREIGN KEY (cname) REFERENCES Class(cname) -- 确保外键的完整性
);

However if I forgot to add the two foreign keys, there are two ways to add them

1. drop the table and recreate it

   DROP TABLE Enroll;
   -- continue to create the table
   

2. use ALTER TABLE to add the foreign key

   ALTER TABLE Enroll 
   add FOREIGN KEY(snum) REFERENCES student(snum) 
   ON UPDATE CASCADE; 
   -- Add a foreign key constraint to table enroll
   

2.2. Inserting Data

INSERT INTO Student (snum, sname, major, level, age)
VALUES (123456789, 'Smith', 'CS', 'SR', 18);

Note that you don’t have to list all the columns, but you have to list the columns in the same order as the values
if no column is specified, then the values must be in the same order as the columns in the table

INSERT INTO table_name (column1,column2,column3,...)
VALUES (value1,value2,value3,...);

2.3. Deleting Tuple

DELETE FROM Student WHERE age < 18; -- 删除年龄小于18的学生
DELETE FROM Student; -- 删除所有学生

2.4. Updating Tuple

UPDATE Student SET major = 'International Study' 
WHERE snum = 123456789;

2.5. Select-From-Where Statements

The principal form of a query is

SELECT A1, A2, ..., An -- desired attributes
FROM   R1, R2, ..., Rm -- one or more tables, i.e. relation list
WHERE  P;              -- selection condition
-- ORDER BY A1, A2, ..., An; -- optional

Intuitively, semantics of an SQL query is defined in terms of the following conceptual evaluation strategy:
– Compute the cross-product of relation-list.
– Apply selection (using qualifications) to discard resulting tuples if they fail qualifications.
– Apply projection to delete attributes that are not in target-list.

But this is just too SLOW!!

There are numerous ways to optimize the query, such as

• Indexing: to speed up the search
• Query Optimization: to find the best way to execute the query
• Materialized Views: to store the result of the query

Set VS. Bag Semantics

• Set: a collection of distinct elements
• Bag: a collection of elements that may contain duplicates (default in SQL)

By adding DISTINCT to the SELECT statement, we can eliminate duplicates

SELECT DISTINCT age
FROM Student;

Arithmetic Expressions

In SELECT clause

SELECT sname, age, age + 5
FROM Student;

In WHERE clause

SELECT sname, age
FROM Student
WHERE age + 5 > 20;

Like Predicate

Similar to regular expression

SELECT sname
FROM Student
WHERE sname LIKE 'A%'; -- find all students whose name starts with 'A'

• ‘%’: any string of zero or more characters, similar to * in regular expression
• ‘_’: any single character, similar to . in regular expression

Order By

SELECT sname, age
FROM Student
ORDER BY age DESC; -- sort the result by age in descending order
-- by defualt, it's ascending order

Where clause

Attribute names of the relations appearing in FROM clause

• Comparison operators: =, <>, <, >, <=, >=
• Arithmetic operations: +, -, /, *
• AND, OR and NOT to combine/negate conditions
• Operations on strings: concatenation, etc.
• Pattern matching: s LIKE p
• Special functions for comparing dates and times

Aliases

SELECT s.sname 
FROM Student s, Enroll e 
WHERE s.snum = e.snum AND e.cname LIKE 'Database Systems'

A general form is

SELECT a1, a2, ..., ak
FROM R1 AS x1, R2 AS x2, ..., Rn AS xn -- AS is an optional keyword
WHERE <conditions>;

A psudocode is like the following

answer := {}
for x1 in R1:
  for x2 in R2:
    ...
      for xn in Rn:
        if <conditions>:
          answer := answer  {(a1,…,ak)}
return answer

2.1. 层次化的数据库对象命名机制

• 一个关系数据库管理系统的实例（Instance）中可以建立多个数据库
• 一个数据库中可以建立多个模式
• 一个模式下通常包括多个表, 视图和索引等数据库对象

2.2. 数据定义

• 模式定义
• 表定义
• 视图和索引定义

模式(schema) 实际上是一个namespace

模式的创建, 删除 以及相关细节

基本表的创建

基本表中的数据类型

基本表的修改

基本表的删除, 以及相关细节 (RESTRICT / CASCADE )

索引(indexing): 用来加快查询速度

索引是用户不可见的, 由DBA或者表的构建者创建, 由数据库 (自动) 维护

索引的创建

索引的修改, 删除

11. SQL中的空值

关于空值有几个平凡的注意点

• 有NOT NULL约束条件的不能取空值

• 加了UNIQUE限制的属性不能取空值

• 码属性不能取空值

• 空值与另一个值（包括另一个空值）的算 术运算的结果为空值

• 空值与另一个值（包括另一个空值）的比 较运算的结果为UNKNOWN.

• 有UNKNOWN后, 传统二值（TRUE, FALSE）逻辑就扩展成了三值逻辑

12. 视图

视图是一种设计, 这篇博客介绍了为什么要设计视图

1. Database Design

////时间不够了, 因此先记一个大纲, 有时间补上

结构和行为分离的设计

设计方法

• 新奥尔良（New Orleans）方法
• 基于E-R模型的数据库设计方法
• 3NF（第三范式）的设计方法
• 面向对象的数据库设计方法
• 统一建模语言（UML）方法

数据库设计中最重要的是基础数据本身, 而我们将数据抽象成数据模型: 数据结构 + 数据操作 + 数据约束.

数据模型又被抽象成这样的三个部分:

• 概念数据模型: 直观上主要研究E-R图的设计
• 结构数据模型: 直观上主要研究关系模型的设计
• 物理数据模型: 直观上并不需要数据库使用者来操心

2. Demanding Analysis

3. Conceptual Model & Entity-Relationship Model

将需求分析得到的用户需求抽象为信息结构（即概念模型）的过程就是概念结构设计

E-R模型是描述概念结构的工具

两个实体型之间的联系

• 一对一 (1 : 1)
• 一对多 (1 : n)
• 多对多 (m : n)

两个以上的实体型之间的联系

• 一对一 (1 : 1)
• 一对多 (1 : n)
• 多对多 (m : n)

单个实体型内的联系

• 实体型是相对的, 一个实体型可以由多个子实体型构成

联系的度：参与联系的实体型的数目

• 2个实体型之间的联系度为2，也称为二元联系

• N个实体型之间的联系度为N，也称为N元联系

E-R图提供了表示实体型、属性和联系的方法：

• 实体型：用矩形表示，矩形框内写明实体名。
• 属性：用椭圆形表示，并用无向边将其与相应的实体型 连接起来。
• 联系：用菱形表示，菱形框内写明联系名，并用无 向边分别与有关实体型连接起来，同时在无向边旁 标上联系的类型（1∶1，1∶n或m∶n）。
• 联系可以具有属性

实体性之间联系的类型:

1. ISA联系:

有的实体型是某个实体型的子类型，这种父类-子类 联系称为ISA联系，表示“is a”语义。用△表示。

ISA联系的性质: 子类继承了父类的所有属性，子类 也可以有自己的属性。

分类属性是父实体型的一个属性 (分类属性的值把父实体型中的实体分派到 子实体型中)

ISA联系中, 子类之间的约束关系可以有几种

• 基数约束: 说明实体型中的任何一个实体可以在联系中出现的最少 次数和最多次数

  • 实际上是对实体之间一对一、 一对多、多对多联系的细化
  • 约束用一个数对 min…max表示，0≤min ≤ Smax。例如， 0…1， 1…3， 1…*，, 其中*代表无穷大。
  • 强制参与约束: min = 1
  • 非强制参与约束: min = 0

• 完备性约束: 描述父类中的一个实体是否必须是某一个子类中的实体 (一个学生要么是研究生要么是本科生. etc)

  • 如果是，则叫做完全特化( total specialization ) : 完全特化用父类到子类的双线连接来表示
  • 否则叫做部分特化( partial specialization) : 部分特化用父类到子类的单线连接来表示

• 不相交约束: 一个父类中的实体最多属于一个子类实体集 (用ISA联系符号三角形的-一个叉号“X"来表示。)

• 可重叠约束: 父类中的一个实体能同时属于多个子类中的实体集。 子类符号中没有叉号表示是可重叠的。

2. Part-of 联系

描述某个实体型是另外一个 实体型的一部分。可以分成两种情况

• 非独占的 Part-of 联系，简称 非独占联系 (整体实体如果被破坏，另一部分实体仍然可以独立存在)
• 独占的 Part-of 联系， 简称独占联系 (整体实体如果被破坏，部分实体不能存在)

如果一个实体型的存在依赖于其它实体型的存在， 则这个实体型叫做弱实体型,否则叫做强实体型

用弱实体类型和识别联系来表示独占联系双矩形表 示弱实体型，用双菱型表示识别联系

3. 识别联系 (Identifying Relationship)

4. Conceptual Structure Design

设计方法:

• 自顶向下, 逐步求精
• 自底向上
• 逐步扩张

首先定义全局概念结构的框架，然后逐步细化

5. Conceptual Structure Design (plus)

E-R图合并时可能的冲突：

• 属性冲突：属性域冲突，即属性值的类型、取值范围或取值集合不同
• 命名冲突：同名异义，异名同义
• 结构冲突：同一对象具有不同的抽象，同一实体包含属性不同，实体间的联系类型不同

6. Logical Structure Design

逻辑结构设计要做这样的事: 把概念结构设计阶段设计好的基本E-R图转换 为与选用数据库管理系统产品所支持的数据模 型相符合的逻辑结构

一个实体型转换为一个关系模式

• 关系的属性：实体的属性
• 关系的码：实体的码

在转换的过程中, 可能会遇到不同的联系类型, 可以进行相应的转换 / 合并

转换好了之后, 由于数据库逻辑设计的结果不是唯一的, 还应该适当地修改、 调整数据模型的结构，以进一步提高数据 库应用系统的性能，这就是数据模型的优 化。

如何优化: 关系数据模型的优化通常以规范化理论为 指导。

6.2. Decomposing

对关系模式进行必要分解，提高数据操作 效率和存储空间的利用率。

常用分解方法

• 水平分解: 把(基本)关系的元组分为若干子集合，定义每 个子集合为一个子关系，以提高系统的效率。
• 垂直分解: 把关系模式R的属性分解为若干子集合，形成若干 子关系模式。

7. Physics Structure Design

8. Database Implementation and Maintenance

Transaction

• 事务(Transaction)是用户定义的一个数据库操 作序列，这些操作要么全做，要么全不做，是 一个不可分割的工作单位。

• 事务和程序是两个概念

  • 在关系数据库中，一个事务可以是一条SQL语句， 一组SQL语句或整个程序
  • 一个程序通常包含多个事务

• 事务是恢复和并发控制的基本单位

事物的定义

显示地定义

BEGIN TRANSACTION
  <SQL STATEMENT 1>
  <SQL STATEMENT 2>
  ...
COMMIT  

BEGIN TRANSACTION
  <SQL STATEMENT 1>
  <SQL STATEMENT 2>
  ...
ROLLBACK

这里 COMMIT 和 ROLLBACK 是显示地终止一个事物的两条指令

当用户没有显式地定义事务时, 数据库管理系统按缺省规定自动划分事务

• 事务正常结束

• 提交事务的所有操作（读+更新）

• 事务中所有对数据库的更新写回到磁盘上的物理数据库中

• 事务异常终止

• 事务运行的过程中发生了故障，不能继续执行

• 系统将事务中对数据库的所有已完成的操作全部撤销

• 事务滚回到开始时的状态

• ACID特性

  • Atomicity: 事务是数据库的逻辑工作单位 —— 事务中包括的诸操作要么都做, 要么都不做
  • Consistency: 数据库中只包含成功事务提交的结果 (也就是说失败的事物必须rollback)
  • Isolation: 一个事务的执行不能被其他事务干扰, 并发执行的各个事务之间不能互相干扰
  • Durability: 一个事务一旦提交，它对数据库中数据的改变就应该是永久性的. 接下来的其他操作或故障不应该对其执行结果有任何影响

• 事务的控制语句：事务的提交(commit)与回滚(rollback)

Fault and Database Recovery

故障 (Fault) 的种类

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

各类故障，对数据库的影响有两种可能性

• 数据库本身被破坏
• 数据库没有被破坏, 但数据可能不正确, 这是由于事务的运行被非正常终止造成的.

事务内部更多的故障是非预期的, 是不能由应用程序处理的.

• 运算溢出
• 并发事务发生死锁而被选中撤销该事务
• 违反了某些完整性限制而被终止等

事务故障仅指这类非预期的故障

事务故障的恢复：事务撤消（UNDO）

• 强行回滚（ROLLBACK）该事务
• 撤销该事务已经作出的任何对数据库的修改，使得该事务像根本没有启动一样

系统故障, 称为软故障, 是指造成系统停止运转的任何事件 (特定类型的硬件错误（如CPU故障）、 操作系统故障、数据库管理系统代码错误、系统断 电），使得系统要重新启动。

• 整个系统的正常运行突然被破坏

• 所有正在运行的事务都非正常终止

• 不破坏数据库

• 内存中数据库缓冲区的信息全部丢失

• 发生系统故障时，一些尚未完成的事务的结果可能已送 入物理数据库，造成数据库可能处于不正确状态。

  • 恢复策略：系统重新启动时，恢复程序让所有非正常终止的 事务回滚，强行撤消（UNDO）所有未完成事务

• 发生系统故障时，有些已完成的事务可能有一部分甚至 全部留在缓冲区，尚未写回到磁盘上的物理数据库中， 系统故障使得这些事务对数据库的修改部分或全部丢失

  • 恢复策略：系统重新启动时，恢复程序需要重做（REDO） 所有已提交的事务

介质故障，称为硬故障，指外存故障

• 磁盘损坏
• 磁头碰撞
• 瞬时强磁场干扰

介质故障破坏数据库或部分数据库，并影响正 在存取这部分数据的所有事务

介质故障比前两类故障的可能性小得多，但破 坏性大得多

病毒是数据库的主要威胁

恢复操作的基本原理：冗余: 利用存储在系统别处的冗余数据来重建数据库中已被破 坏或不正确的那部分数据

恢复的实现技术：复杂: 一个大型数据库产品，恢复子系统的代码要占全部代码 的10%以上

恢复机制涉及的关键问题:

• 如何建立冗余数据（数据转储，登记日志文件）
• 如何利用这些冗余数据实施数据库恢复

Data Dumping & Logs

数据转储

转储 (dumping) 是指数据库管理员定期地将整个数据库复制到 磁带、磁盘或其他存储介质上保存起来的过程

转储方法:

• 静态: 在系统中无运行事务时进行的转储操作
• 动态: 转储操作与用户事务并发进行

海量转储: 每次转储全部数据库

增量转储: 只转储上次转储后更新过的数据

日志

日志文件的格式

• 以记录为单位的日志文件
• 以数据块为单位的日志文件

用途

• 进行事务故障恢复
• 进行系统故障恢复
• 协助后备副本进行介质故障恢复

Schedule

• 串行调度(serial schedule)

• 可串行化调度(Serializability Schedule)

• 冲突 与 冲突可串行化调度

• 串行调度/可串行化调度/冲突可串行化调度 三者之间的关系

Two-Phase Locking

• 封锁

  • 排它锁的作用与申请规则

  • 共享锁的作用与申请规则

• 两阶段封锁协议

• 死锁的定义

Logs

• UNDO日志的内容，记载规则和作用

• REDO日志的内容，记载规则和作用

• UNDO/REDO日志的内容，记载规则和作用

恢复策略

• 事务故障：UNDO
• 系统故障：UNDO and REDO
• 介质故障：重装数据库，UNDO and REDO

1. 存储管理

1.1. 主要模式

逻辑地址 逻辑地址：又称相对地址，即用户编 程所使用的地址空间 逻辑地址从0开始编号，有两种形式： 一维逻辑地址（地址） 二维逻辑地址（段号:段内地址）

用户可以自己应用段覆盖技术扩充内 存空间使用量 这一技术是程序设计技术，不是OS 存储管理的功能

物理地址：又称绝对地址，即程序执 行所使用的地址空间 处理器执行指令时按照物理地址进行

主存储器的复用 多道程序设计需要复用主存

按照分区复用： 主存划分为多个固定/可变尺寸的分区 一个程序/程序段占用一个分区

按照页架复用： 主存划分成多个固定大小的页架 一个程序/程序段占用多个页架

存储管理的基本模式

单连续存储管理：一维逻辑地址空间的 程序占用一个主存固定分区或可变分区

段式存储管理：段式二维逻辑地址空间 的程序占用多个主存可变分区

页式存储管理：一维逻辑地址空间的程 序占用多个主存页架区

段页式存储管理：段式二维逻辑地址空 间的程序占用多个主存页架区

1.2. 功能

1.3. 虚拟存储器

1.4. 硬件支持

2. 单连续存储管理

2.1. 单连续存储管理

2.2. 可变分区存储管理

3. 页式存储管理

3.1. 基本原理

3.2. 地址转换

3.3. 页式虚拟存储管理

3.4. 页面调度

3.5. 反置页表

4. 段式存储管理

4.1. 基本原理

4.2. 段式虚拟存储管理

4.3. 段页式存储管理