关系

关系可以看作一张“哪些配对成立”的清单。课程与学生之间的选课关系中，一个学生可以选多门课，一门课也可以有多个学生；没有选课的学生仍可能属于声明的学生集合。关系既不自动保证有配对，也不自动保证配对唯一。

当声明的载体 $A,B$ 都是有限集时，关系可以表示成矩形的零一表：行对应 $A$，列对应 $B$，位置 $(a,b)$ 上的 $1$ 表示 $aRb$。反向查询把行列互换，关系复合则检查是否存在中间列与中间行能够接通。

若矩阵分别为 $M_R,M_S$，复合的 $(a,c)$ 项为 $\underset{b\in B}{\bigvee }(M_R(a,b)\wedge M_S(b,c))$：乘法换成“且”，求和换成“或”。普通整数矩阵乘法会累计路线条数，布尔运算只保留有没有路线。这种表示统一了成员判定与连接操作，但表格本身不决定配对在具体领域中代表什么。

用一次复合完成两步查询 ​

设学生集合为 $A=\{\text{甲},\text{乙}\}$，课程集合为 $B=\{\text{算法},\text{数据库}\}$，教师集合为 $C=\{\text{林},\text{周}\}$。选课关系与授课关系分别是

先从甲出发：沿算法可到林，沿数据库可到林和周，因此得到 $(\text{甲},\text{林})$、$(\text{甲},\text{周})$。乙只选数据库，但也能到林和周。四种学生—教师配对都成立，所以 $S\circ R=A\times C$。

按上述学生、课程、教师的列举顺序，两张关系表为

普通矩阵乘积是 $\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$，左上角的 $2$ 数出了甲到林的两条路线；把非零项改为 $1$，才得到复合关系的零一表。结果集合只包含一次 $(\text{甲},\text{林})$，因为它判断有没有路线，而不是记录路线有几条。

逆关系也不是普通函数的逆函数。上例的 $R^{-1}$ 把数据库课程关联到两位学生，仍是一对多；交换箭头总能定义逆关系，得到逆函数则需要原函数是双射。

同一张关系图，不同的类型 ​

图 $R=\{(1,1)\}$ 可声明为从 $\{1\}$ 到 $\{1\}$ 的关系，也可声明为从 $\{1\}$ 到 $\{1,2\}$ 的关系。两者都覆盖源集，但第二个没有覆盖目标中的 $2$。因此只扩大目标集改变的是目标覆盖性，不改变源集的全域性。

若改为从 $\{1,2\}$ 到 $\{1\}$，同一张图则遗漏源元素 $2$，不再全域。这说明不能只从实际投影恢复原先声明的类型；函数的定义域与陪域，也需要作为数据明确保留。

齐次关系的公理各管什么 ​

当源与目标都是 $A$ 时，称为 $A$ 上的关系。常见性质是：

条件均对 $A$ 中相关变量全称量化。反对称不是“对称不成立”：相等关系同时对称、反对称。正整数上的整除关系自反、反对称、传递，但 $2,3$ 互不整除；它给出偏序理路偏序Partial order · Partially ordered set满足自反、反对称和传递性的关系。，而不是全序。

从关系得到不同结构 ​

要求每个 $a\in A$ 恰好关联一个 $b\in B$，得到带陪域的函数理路函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。。只要求至多一个输出，得到部分函数。要求自反、对称、传递，得到等价关系理路等价关系Equivalence relation满足自反、对称和传递性的关系。；将对称改为反对称，则得到偏序。这些约束有不同目的，不能默认一般关系同时满足它们。

关系复合满足结合律，因为两种括号都要求存在相同的两个中间见证：

恒等关系 ${\mathrm{\Delta }}_A=\{(a,a):a\in A\}$ 是相应类型上的单位。逆关系会反转复合顺序：$(S\circ R{)}^{-1}=R^{-1}\circ S^{-1}$。复合一般不交换，有时反向复合连类型都不匹配。

一步转移与任意步可达 ​

对 $A$ 上的关系 $R$，令 $R^0={\mathrm{\Delta }}_A$，$R^{n+1}=R\circ R^n$。那么

分别是传递闭包与自反传递闭包。“闭包”指包含原关系且满足指定性质的最小关系：有限路线首尾相接仍是有限路线，所以 $R^{+}$ 传递；任何包含 $R$ 的传递关系又必须包含每条有限路线的首尾对。若 $R$ 是图的邻接关系，$R^{+}$ 允许至少一步，$R^{\ast }$ 还允许停在原地。图中只有一条边 $a\to b$ 时，$R^{+}$ 只有 $(a,b)$，而 $R^{\ast }$ 另含 $(a,a),(b,b)$；“可达”一词必须说明采用哪一种约定。

数据库连接、程序执行和图搜索都使用上述存在中间见证的机制。标号转移系统理路标号转移系统Labeled transition system · Labelled transition system · LTS在状态转移上标记动作，明确路径、可达性、使能动作以及终止与死锁的行为模型。再给转移附上动作，模拟关系理路模拟关系Simulation relation · Forward simulation用方向性的状态关系要求一个系统的每步行为能够由另一个系统匹配。则用一套状态之间的关系比较两套系统的行为；它们复用关系运算，但各自还需独立的语义条件。