数据库系统的关系代数
关系代数的全部对象与运算，本质上都可以理解为：对元组集合做集合运算。因此理解关系代数前需要先理解集合论。
集合论
集合的概念和描述
集合set是一些对象的汇集，可以表示如下：
某个元素是否属于集合，用 \in或 \notin( in / notin)表示:
集合有两个核心特征，无序性和不重复性。
这两点非常关键：在经典关系模型里，一张关系表就是一个集合，因此它的行不因顺序不同而不同，也不允许重复行.
描述集合的方法通常有枚举法， A=\{1,2,3\}，即列出所有元素。还有一类是描述法，用性质定义集合，比如 A=\{x∣x 是 1 到 10 的偶数\}。描述法会被频繁使用，因为关系代数中很多结果关系都用满足某种谓词的元组集合来定义。
子集
子集的定义
直白的描述就是，如果A的元素都可以在B中找到，那么A就是B的一个子集。
真子集的定义
和子集不同，真子集不包含A和B元素相同的情况。
集合相等
这是后面证明关系代数等价变换的主要方法：要证明两个表达式等价，往往就是证明它们互为子集。
空集及全集
空集和全集是边界条件的来源。空集定义如下:
\varnothing\subseteq A 对任意集合 A 都成立，即使A是空集，这个定理也是成立的。很多对所有的命题，在空集上会表现出重要的边界语义，后面讲关系除法会用到。
全集不是固定的，它依赖讨论范围:
引入全集后可以定义补集。
集合运算四件套
集合论中的并、交、差、补四件套是关系代数里并/交/差以及很多推导变换的数学基础。
并集（Union）
即两个集合的合并，元素要么在A集合，要么在B集合。
交集（Intersection）
集合A和和集合B两者共有的部分。
差集（Difference）
从 集合A 中删掉 集合B 的元素。注意，差集是有方向和先后顺序的，一般情况下 A-B \neq B-A
补集（Complement）
给定全集 (U),则
不在 集合A 里，但是在全集U内的元素。
关系、性质与等价性
关系代数中的关系有两层含义：
集合论的关系：集合 A 上的一个二元关系，是 A\times A 的子集。
数据库的关系：是若干域的笛卡尔积上的子集，是更一般的 n 元关系。
我们本节论述的是第一个含义，它们对后续理解等价变换、分组归并等非常关键。
二元关系的严格定义
给定集合 A,B，一个从 A到 B的二元关系 R 是笛卡尔积的子集：
若 A=B，则称 R 是 集合 A 上的二元关系
可记号约定为
读作a 与 b 满足关系 R
关系的三大基本性质
假设 R\subseteq A\times A
自反性（Reflexive）
R_\text{ 自反 } \iff \forall a\in A,\ (a,a)\in R每个元素都与它自己相关。自反性强调关系指向自身，是描述事物恒等、自我包含或自我反思的属性。
比如，把R取为家人
family-of，人是其中的元素。则任何人都是自己的家人。传递性（Transitive）
R_\text{ 传递 } \iff \forall a,b,c\in A,\ (a,b)\in R \land (b,c)\in R \Rightarrow (a,c)\in R如果 a 通过 b 能到 c，那么 a 也能直接到 c。传递性是一种普遍的逻辑模式，它描述了关系连接的链式效应，从集合关系到语言用法，都强调了这种
前推后导的特性。同样例子，你和爸爸是家人，你和妈妈是家人，则依据传递性，爸爸和妈妈是家人。
对称性（Symmetric）
R_\text{ 对称 } \iff \forall a,b\in A,\ (a,b)\in R \Rightarrow (b,a)\in R对称性是双向奔赴的。就好比你对于妻子是家人，妻子对于你也是家人。很明显 a \neq b。
R_{对称} \iff R^{-1} = R其中 R^{-1} 和 R是逆关系
反对称性（Antisymmetric）
除了上述三大性质，还有一类非常重要的性质，就是反对称性。
R_\text{ 反对称 } \iff \forall a,b\in A,\ (a,b)\in R \land (b,a)\in R \Rightarrow a=b如果 a 和 b 彼此都相关,即双向都成立，那它俩就不能是两个不同的元素；只能是同一个元素。不允许出现两个不同元素之间的双向关系。
把元素取为集合，关系取为包含于，则
A \subseteq B \ and \ B \subseteq A \\ \therefore A = B举例就是把R取为家谱
ancestor-of,其中的元素是目录item,就是每一代的目录。若目录A是B的祖先，且B又是A的祖先，那么A和B只能是同一目录。层级关系中不允许相互在上层。需要注意的是，
对称性和反对称性在逻辑上并不是对立的，是可以同时出现的。\forall{a,b} \in A,aRb \Rightarrow bRa(对称性，symmetric) \\ \forall{a,b} \in A,(aRb \land bRa) \Rightarrow a= b(反对称，antisymmetric)对称性关注有一条边，就必须有反向的边。反对称性强调如果出现双向边则只能是同一个点。
比如A的学号和A相同，反过来A的学号也和A相同，这是对称性的体现，关系是学生和学号的关系。如果A的学号和B的学号相同，且B的学号和A的也相同，那么A,B必然是一个人，这体现了反对称性。同时存在反对称和对称的前提就是关系中只能有一个元素。
反对称 vs 非对称（asymmetric）
非常容易混肴的概念
非对称（asymmetric）定义是更强的：
\forall a,b,\ aRb \Rightarrow \neg(bRa)它直接禁止任何双向（包括 a=b 的情况），因此非对称关系必然反自反（不可能有 aRa）。
关系强弱包含关系是：
\text{非对称} \Rightarrow \text{反对称}但反过来不成立：反对称允许 aRa，而非对称不允许。
等价关系
集合 A 上的关系 \sim 若同时满足：
自反性
对称性
传递性
则称 \sim 为 等价关系（equivalence relation）。
给定等价关系 \sim，元素 a\in A 的等价类定义为：
等价类的三个核心定理
定理1： (a\in [a])
因为自反 a\sim a
定理2: 若 a\sim b，则 [a]=[b]
用传递性与对称性证明互为子集
定理 3：任意两个等价类要么相等，要么不相交
[a]\cap [b]\neq \varnothing \Rightarrow [a]=[b]因此等价类把集合 A 划分成互不相交的块。
所有等价类的集合称为商集：
并且 {[a]} 构成对 A的一个划分：并起来等于整个集合，两两不相交，每个块非空。
这部分和数据库中按某个键分组的直觉非常接近：等价关系把对象归并成类。
偏序
给定集合 A，关系 \preceq 是 偏序（partial order） 当且仅当它满足：
自反性（Reflexive）
\forall a\in A,\ a\preceq a反对称性（Antisymmetric）
\forall a,b\in A,\ (a\preceq b \land b\preceq a)\Rightarrow a=b传递性（Transitive）
\forall a,b,c\in A,\ (a\preceq b \land b\preceq c)\Rightarrow a\preceq c
满足这三条的 A,\preceq 称为偏序集（poset）。
对 a,b\in A，若 a\preceq b或 b\preceq a，称 a,b 可比。否则称 不可比（incomparable）。
全序是在偏序条件的基础上再增加一条可比性：
也就是任意两元素都可比，偏序不要求这一点，所以更宽松，因此叫偏。
非严格偏序如上定义，允许 a\preceq a。
严格偏序定义则如下:
严格偏序满足:
反自反， \forall a,\ \neg(a\prec a)
传递性， (a\prec b \land b\prec c)\Rightarrow a\prec c
偏序与等价的关系
等价关系：自反 + 对称 + 传递
等价关注归类和同一性，侧重对象分组。
偏序关系：自反 + 反对称 + 传递
关注层级和先后，侧重把对象排序。
两者关键区别在于
等价关系允许不同元素互相相关（对称），表示同类
偏序禁止不同元素互相都在关系中（反对称），以避免排序意义下的循环/混淆
偏序下的四类极值
设 A,\preceq 是偏序集， S\subseteq A。
最小元 （minimum / least element）
m\in S 是 最小元，若：
\forall x\in S,\ m\preceq x它比 S 里所有元素都小。若存在，则唯一。
最大元（maximum / greatest element）
M\in S 是 最大元，若：
\forall x\in S,\ x\preceq M若存在，也唯一。
极小元（minimal element）
m\in S 是 极小元，若：
\neg \exists x\in S,\ x\prec m也就是 S 中找不到比它更小的元素。因为不可比会造成并列最小，极小元可能有多个。
极大元（maximal element）
M\in S 是 极大元，若：
\neg \exists x\in S,\ M\prec x同理，可能有多个。
“最小/最大”是全局比较（对所有）
“极小/极大”是局部不可再改进（不存在更小/更大）
关系代数
关系代数就是将一些本质为元组集合的关系 relation用一套算子变为另外一套关系。全程满足封闭性，输入是关系，输出也是关系。
关系的相关概念
每个属性 A_i 取值来自某个域 D_i。
一个 n 元关系 R 的模式 schema 可写作`:
一个元组 t 是对属性的赋值， t=(a_1,\dots,a_n)，其中 a_i\in D_i。其中关系（relation）就是元组的集合:
关系 = 笛卡尔积上的子集
经典关系代数用的是集合语义，包括元组不重复，没有顺序，投影天然去重。
SQL 的重复/NULL/外连接等，属于工程扩展，不在此文讨论。
关系代数的算子
为了方便介绍关系代数的各个算子，以学生和选课为统一举例。
设学生集合 S=\{s_1,s_2,s_3\}，课程集合 C=\{c_1,c_2\}。
选课关系（二维关系）：
必修课集合（一元关系）：
选择 \sigma
选择算子就是按谓词筛元组，即筛选行。其定义为对关系 R，谓词 p（关于元组属性的条件）:
例如对选课关系进行选择:
常用代数律,比如合并选择:
投影 \pi
投影算子就是丢掉属性，即筛列。对属性集合 X\subseteq {A_1,\dots,A_n}：
其中 t|_X 表示把元组 t 限制到属性集合 X 上。
选课关系投影到学生:
投影除了筛选列外，为了集合语义，还需要去重。 s_1 在 E 中出现两次，但投影后只保留一次。
常用代数律是幂等（收缩）：
并 / 交 / 差：集合运算
并兼容 Union-compatibility
\cup,\cap,- 要求两个关系属性个数相同,且对应属性域相同，或者说是可比。
运算定义如下:
交集可由差算子导出，是常用的派生算子：
笛卡尔积 \times
若 R\subseteq D_1\times\cdots\times D_m，S\subseteq E_1\times\cdots\times E_n，则：
结果是一个 m+n 元关系。
若 |R|=m, |S|=n，则 |R\times S|=mn。这是为什么“连接”不能简单靠 × 硬算：会爆炸。
连接 \Join
连接是最核心的派生算子，是受约束的组合。其本质是，连接 = 先做 \times 生成候选，再用 \sigma 过滤匹配。
\theta-连接
给定连接条件 \theta：
自然连接（Natural Join）
当 R 与 S 有同名属性（比如都含 B），自然连接要求这些同名属性相等，并把重复列合并。可形式化写作：
左连接/右连接/全连接属于扩展关系代数（带空值/外连接语义），经典纯关系代数里通常不把它们当基本算子。这里不讨论。
除法 \div
除法回答的不是有没有，而是是不是对所有都成立。
给 E(S,C) 与 R(C)，定义：
选出了把 R 里每门课都选了的学生。
只有 s_1 同时匹配 c_1,c_2，因此：
用基本算子展开除法
设 X={S}，Y={C}，则有经典等价式：
拆解如下:
候选学生： \pi_X(E)
左表里出现过的 X 值，才有资格被考虑（比如出现过的学生）。
候选学生 × 必修课得到所有应当出现的配对\pi_X(E)\times R
把每个候选 x 与右边每个 y 配对，得到理论上必须存在的配对集合。
缺失配对
(\pi_X(E)\times R)-E
把实际存在的配对 E 减掉，剩下的就是缺的那几门。
不合格的 X（至少缺一门）
\pi_X\bigl((\pi_X(E)\times R)-E\bigr)
只要某个 x 出现在缺失配对里，就说明它缺课，不合格。
候选减去缺课学生，即为
全修完的学生\pi_X(E)-(\text{不合格X})
除法的逻辑等价如下:
x 合格，当且仅当 不存在 一门必修课 ( y) 使得 ( x,y) 不在选课关系里。
这就是 \forall for all被改写成 \neg\exists\neg\neg\exists\neg 的经典套路：
关系代数中的笛卡尔积 \times 和 除法 \div 并不是互逆的。
在代数中，我们定义运算 f(x) 和 g(x) 互逆，通常意味着:
在合适的定义域和值域上成立 \\ g(f(x)) = x \\ f(g(y)) = y
而在关系代数中：
\times 的输入是两个关系，输出是更宽、更大的关系；
\div 的输入是两个关系，但它的输出丢掉了右侧属性，是更窄的关系；
\times会引入大量信息（所有组合）， \div 的定义是基于对所有的约束抽取，过程里发生了信息不可逆的压缩。
因此一般不可能要求:
(R\times S)\div S = R\quad\text{且}\quad (R\div S)\times S = R
对所有关系都适用，例外如下
若 E恰好只包含 Y\in R 的配对，并且对所有 x\in(E\div R) 都是完整的 x\times R，则可能得到：
(E\div R)\times R = E
非常少见的情况，不是普遍的真理。
反方向则更不可能 (E\times R)\div R = E。
E\times R 的属性会变得更宽（多出一份 Y 或其它属性），结构与 E 不同；
即便你设计得让属性可对齐， \times 生成的是所有组合，这会人为制造很多对所有都成立的候选，从而改变除法结果。
因此先乘再除回去等价于原关系，通常是不成立的。
总结
\sigma：在集合里挑满足条件的元组
\pi：在元组上抹掉不关心的属性（并去重）
\cup,\cap,-：对同构关系做集合运算
\times：把两个关系做全组合（一般太大，常作为中间步骤）
\Join：\sigma(R\times S) 的工程化表达
\div：把“对所有”变成可计算的集合差与投影,是在表达一个都不能少
各算子的优先级
括号 (...) 永远最高优先级，先算括号里的子表达式。如果没有括号，就按约定的优先级从高到低绑定。
按照这个规则，我们在书写关系代数的时候，宁可多用括号来梳理计算的优先级别，也不要让读者去猜。
除括号外，各算子的优先级从高到低如下：
一元算子优先级最高。因为它们只修饰一个关系
选择： \sigma_p(\cdot)
投影： \pi_X(\cdot)
重命名： \rho(\cdot)
它们会优先绑定到右边最近的关系符号上。比如:
\sigma_pR \Join S \quad\text{默认读作}\quad (\sigma_p(R)) \Join S而不是 \sigma_p(R\Join S)（除非你写括号）。
连接与笛卡尔积是次高
以下这些运算位于同一运算优先级:
笛卡尔积： \times
\theta-连接： \Join_\theta
自然连接： \Join
除法 \div是二元构造型算子，且语义上通常先把
结构性组合做完再做集合并差。所以也在这一层。比如
R \Join S \times T \quad\text{默认按从左到右结合：}\quad (R \Join S)\times T交运算
Intersection是更低一层的算子。类似算术里
乘除高于加减，交 \cap运算更紧实，所以优先级高于并和差。R \cup S \cap T \quad\text{默认读作}\quad R \cup (S\cap T)并运算和差运算
Union / Difference优先级最低的算子。\cup,\quad - 并与差通常放在同一最低层级，并按从左到右结合。
R - S - T \quad\text{默认读作}\quad (R-S)-T
当你连续写同优先级的二元算子时，常见约定是左结合 left-associative：
R \Join S \Join T := (R \Join S)\Join T
R \times S \times T := (R \times S)\times T
R \cup S \cup T := (R \cup S)\cup T
R - S - T := (R - S)-T
注意：结合性是怎么加括号的约定；并不意味着所有算子都满足严格的结合律。
例如差集就不满足交换律，结合后语义也会变
关系演算
关系代数像过程语言，你告诉系统怎么做，先筛、再连、再投影之类。关系演算则更像声明语言，你告诉系统你要什么，满足哪些逻辑条件的元组/值。前者是优化基础，算子闭包 + 等价变换;后者是语义基础，算子闭包 + 等价变换。两者是数据库理论的两条主线。
关系元组演算 TRC
Tuple Relational Calculus
设关系模式为 R(A_1,\dots,A_n)。变量表示整行元组（tuple），通常以以下形式呈现
即所有满足谓词 P(t) 的元组 t。 t是一个元组变量（可以访问 t.A_i）。 P(t) 是一阶逻辑公式（可包含 \land,\lor,\neg,\exists,\forall 等）
原子公式 building blocks
TRC 的谓词里常用的原子形式包括：
关系成员： R(t)，表示元组 t 属于关系 R。更常见写法是对 t 的属性与关系模式匹配，例如： R(t.A_1,\dots,t.A_n)。
属性比较： t.A_i \theta u.B_j，或 t.A_i \theta c，其中 \theta\in\{=,\neq,<,\le,>,\ge\}， c 是常量。
逻辑连接与量词： \land,\lor,\neg,\exists,\forall
想要一个结果关系的元组 t，可以写：
关系域演算 DRC
Domain Relational Calculus
变量表示属性值（domain value），不是整行。
通常写成：
所有满足公式 Q 的 k-元组值组合。 x_i 是值变量（对应某个域）， Q 中通过关系谓词把这些值落在关系里，例如 R(x,y,z)。
DRC 的原子公式常见形式：
R(x_1,\dots,x_n)：表示 (x_1,\dots,x_n)\in R
值比较： x_i\theta x_j 或 x_i\theta c
同样支持 \land,\lor,\neg,\exists,\forall
DRC例子:
域独立
上面说的域不是所谓的表里出现过的值，而是数学上的取值域，比如整数域 Z,字符串集合，所有可能的日期，上述这些都是无限的，变量不受限制，范围则可能是无限大的，这也是关系域中要特别强调的，安全和域独立。
假设 R(x) 是一元关系，表示数据库里记录的某些整数。比如：
我们现在进行域演算
所有不在 R 里的 x
如果 x 的取值范围是整个整数域 \mathbb{Z}，那答案就是：
这是无限集合。数据库没法把它输出成一个有限关系。
比如你查“没选课的学生”，你期待结果只会是某些学生 ID，而不会出现一个数据库里根本不存在的随机 ID。
活跃域（active domain）
如果数据库里只出现过 \{1,2,3\}，那
那么真正像要的结果是
这样结果必然是有限的（因为 \text{adom}(D) 有限）。
保证域安全和域独立是数据库系统理论的基础，离开这个基础，将无法返回结果。
Codd 定理：关系代数与安全的关系演算（TRC/DRC）在表达能力上等价。换句话说：你用代数能表达的查询，用安全演算也能表达，反之亦然。
这个结论解释了为什么数据库可以让用户写“声明式”的 SQL，接近演算，而内部可以用代数树去优化与执行。
数学模型与工程实现
前面讲了那么多数学概念，实际上都是为了后面的工程实现做铺垫。总而言之就是关系代数是集合语义的数学模型，SQL 是工程语言。工程中，我们往往直接从业务需求到编写SQL语句，而不会去考虑所谓的选择，映射，连接之类的算子。关系代数之所以重要并不是在工程实现上，而是在系统层面解决了SQL语言无法定义的事情：语义，等价，优化，以及可分析性。工程实现上的jion只是表层，数据库内部的所有优化与执行，都是在关系代数及其变体的框架内发生。
另外，在项目设计阶段，关系代数通常不会以 \sigma，\pi ，\Join这样的形式出现，但是对应的那套抽象在一些关键设计工作中有所体现。例如:
输入哪些关系（
实体/事实/维表）做出哪些筛选（谓词）
如何关联（连接键与基数）
输出哪些属性(投影)
是否去重(语义袋/集合)
这些都是关系代数的工程化抽象。
大型项目的痛处往往不是写SQL，而是指标口径的一致性。当多个团队，多个系统上产出指标时，为了口径一致，必须回答这个指标在那一步进行的过滤，不同节点上的过滤条件是否可以交换；这个去重是连接后还是连接前，结果是否等价；这个排除条件是差集还是反链接，边界条件是什么，这些都是需要用数学模型去约束的。最终目的是口径可复现，口径可审计，口径可对齐。
从模型到工程还是有些出入的，主要表现在以下几点:
本文前半部分默认集合语义；进入 SQL 后，若不加
DISTINCT，许多等价变换只在袋语义下部分成立或需要额外条件。凡涉及 NULL 的比较，都要考虑 Unknown；因此 SQL 的筛选条件与连接条件在 NULL 上会偏离经典代数（关系代数的谓词是二值逻辑）。
左/右/全连接依赖补空值的语义，本质是扩展代数。而关系代数篇讲的是内连接为核心的闭包体系。关系代数保证语义等价；SQL 性能是否等价取决于优化器与物理执行。
SQL 没有除法算子，但可以用两类范式表达同一语义：反证式（NOT EXISTS）与计数式（GROUP BY/HAVING）。
了解完数学模型和工程实现的联系与区别后，我们可以开始下面的数据库开发部分了。