关系代数

关系代数把"关系"本身当作运算对象：两个集合的元素之间是否存在联系，可以通过并、交、逆、复合等操作组合出新的联系，像数的加减乘除一样可以演算。它是映射理论的自然延伸——映射是关系的特例，关系代数则把关系当作可计算的对象，也是关系数据库查询语言的理论基础。

需先掌握二元关系（关系的定义与自反、对称、传递性质）、映射（关系的特例）与集合（笛卡尔积）。

定义

设 $R\subseteq A\times B$ 是从 $A$ 到 $B$ 的二元关系，$S\subseteq B\times C$ 是从 $B$ 到 $C$ 的关系。关系代数研究以下基本运算：

• 并：$R\cup S=\{(a,b)\mid (a,b)\in R\lor (a,b)\in S\}$
• 交：$R\cap S=\{(a,b)\mid (a,b)\in R\land (a,b)\in S\}$
• 逆关系（converse）：$R^{-1}=\{(b,a)\mid (a,b)\in R\}\subseteq B\times A$，把对应方向倒转
• 复合（先 $R$ 后 $S$）：$S\circ R=\{(a,c)\mid \exists\,b\in B,\ (a,b)\in R\land(b,c)\in S\}\subseteq A\times C$
• 恒等关系：$\mathrm{id}_A=\{(a,a)\mid a\in A\}$，复合运算的单位元
• 有全集结构时还可定义差 $R\setminus S$ 与补 $\overline R=(A\times B)\setminus R$

以这些运算为基本操作的代数系统称为关系代数（relation algebra）。

性质

• 结合律：对 $R:A\to B,\ S:B\to C,\ T:C\to D$，有 $(T\circ S)\circ R=T\circ(S\circ R)$
• 复合的逆：$(S\circ R)^{-1}=R^{-1}\circ S^{-1}$（顺序反转，与逆映射的 $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ 一致）
• 逆的逆：$(R^{-1})^{-1}=R$
• 对偶律：$(R\cup S)^{-1}=R^{-1}\cup S^{-1}$，$(R\cap S)^{-1}=R^{-1}\cap S^{-1}$
• 复合对并的分配：$S\circ(R_1\cup R_2)=(S\circ R_1)\cup(S\circ R_2)$
• 恒等关系为复合单位元：$R\circ\mathrm{id}_A=\mathrm{id}_B\circ R=R$
• 性质的关系刻画：$R$ 自反 $\iff \mathrm{id}_A\subseteq R$；$R$ 对称 $\iff R=R^{-1}$；$R$ 传递 $\iff R\circ R\subseteq R$

示例

• 设 $A=\{1,2,3\}$，$R=\{(1,2),(2,3)\}$。则 $R^{-1}=\{(2,1),(3,2)\}$，$R\circ R=\{(1,3)\}$。因 $(1,3)\notin R$，故 $R\circ R\nsubseteq R$，$R$ 不传递
• 实数上的 $\le$ 满足 $\le\circ\le\ =\ \le$（传递性取等的情形），其逆关系为 $\ge$
• 函数 $f:A\to B$ 是"单值"关系 $f=\{(a,f(a))\mid a\in A\}$：每个 $a$ 恰好对应一个 $b$；$f$ 可逆当且仅当该关系是双射（见逆映射）

应用

• 数据库理论：关系代数（选择、投影、连接等运算）是关系数据库查询语言（SQL）的理论基础，即映射"应用"节所述数据库背景的严格化
• 等价关系与划分：用关系运算刻画二元关系中的等价类划分与偏序结构
• 图论与网络：有向图可视为顶点集上的关系，复合 $R\circ R$ 记录长度为 2 的路径，幂 $R^n$ 给出长度为 $n$ 的路径
• 数理逻辑与程序语义：Tarski 关系代数是一类经典代数结构，用于关系逻辑与程序指称语义