5.1 二元关系：性质、复合与闭包

用户关注用户、任务依赖任务、服务调用服务，都可以表示成对象之间的有序配对。关系论提供的不是新的数据格式，而是一组判断结构性质的语言：是否有环、是否可逆、是否能沿多步传播。

关系是笛卡尔积的子集

从集合 A 到集合 B 的二元关系 R：

R ⊆ A×B

若 (a,b)∈R，写作：

a R b

例：

Users={alice,bob}
Projects={atlas,compiler}

Owns={
  (alice,atlas),
  (bob,compiler)
}

Owns 只是所有可能用户与项目的有序对中的一部分。

关系的定义域与像集：

dom(R)={a∈A | ∃b∈B, aRb}
ran(R)={b∈B | ∃a∈A, aRb}

它们未必等于声明的 A、B。可能有用户不拥有任何项目，也可能有项目尚无负责人。

逆关系

交换每个有序对的位置：

R⁻¹={(b,a) | aRb}

若 Owns(user,project)，逆关系可以读作 OwnedBy(project,user)。逆关系不表示操作可撤销，只表示配对方向交换。

(R⁻¹)⁻¹=R

关系复合

设：

R⊆A×B
S⊆B×C

复合关系 S∘R⊆A×C：

a (S∘R) c ⇔ ∃b∈B (aRb ∧ bSc)

例：用户属于团队，团队拥有仓库：

MemberOf ⊆ User×Team
Owns     ⊆ Team×Repo

Owns∘MemberOf ⊆ User×Repo

中间对象 Team 被存在量词连接。复合顺序像函数复合：先走 R，再走 S，符号写作 S∘R。不同教材和数据库记号可能采用其他约定，使用前应声明。

关系复合满足结合律：

T∘(S∘R)=(T∘S)∘R

但一般不满足交换律。

集合上的关系性质

以下假设 R⊆A×A。

自反与反自反

自反：  ∀a∈A, aRa
反自反：∀a∈A, ¬aRa

≤ 自反，< 反自反。某关系也可能既不自反也不反自反。

性质依赖底集：空底集上的空关系既自反又反自反，因为两个全称命题都真；非空底集上则不能同时成立。

对称、反对称与非对称

对称：  aRb → bRa
反对称：(aRb ∧ bRa) → a=b
非对称：aRb → ¬bRa

反对称不是“不对称”。相等关系既对称又反对称；空关系也可以同时满足二者。非对称则蕴含反自反。

“同版本”是对称关系；集合包含 ⊆ 是反对称关系；严格小于 < 是非对称关系。

传递

(aRb ∧ bRc) → aRc

≤ 和“是祖先”传递；“直接依赖”通常不传递，因为 A 直接依赖 B、B 直接依赖 C，不代表 A 直接依赖 C。其传递闭包才表示“直接或间接依赖”。

图和矩阵表示

有限集合上的关系可以画成有向图：元素是顶点，aRb 是边 a→b。

也可用 0-1 邻接矩阵：

M[i,j]=1 ⇔ a_i R a_j

于是：

• 自反对应对角线全为 1；
• 对称对应 M=Mᵀ；
• 关系复合对应布尔矩阵乘法；
• 路径可达性对应传递闭包。

布尔矩阵乘法用 ∧ 代替乘法、∨ 代替加法：

(M⨀N)[i,k]=∨_j (M[i,j] ∧ N[j,k])

它表达“是否存在一个中间节点 j”。

若矩阵的行是起点、列是终点，则 M_R⨀M_S 表示先走 R 再走 S，对应 S∘R。函数复合符号从右往左读，路径矩阵乘积在这一约定下从左往右走，别把两个顺序混写。普通整数矩阵乘法则计数中间路径，结果未必仍是 0 或 1。

闭包：补上最少的配对

下面这些闭包都是包含 R、满足指定性质的最小关系，这里的“最小”按集合包含比较。并非任意性质都存在这样的补边操作：若 R 已有 aRb,bRa 且 a≠b，继续加边无法让它反对称。

• 自反闭包：加入所有 (a,a)；
• 对称闭包：加入每条边的反向边，即 R∪R⁻¹；
• 传递闭包：加入所有长度至少为 1 的可达配对，常记 R⁺；
• 自反传递闭包：还包含长度为 0 的路径，常记 R*。

若依赖图为：

A→B, B→C

传递闭包还包含 A→C。它没有凭空增加“直接依赖”，而是构造了一种新的“可达”关系。

有限图可用 Floyd–Warshall、重复搜索或位集优化计算闭包。选择算法取决于图的稠密度、查询次数和是否动态更新。

下面用 Python 3 实现 Warshall 布尔更新。顶点应唯一，边的端点应属于顶点集。处理完中间点 k 后，矩阵已包含所有只使用已处理顶点作内部点的路径；有限次处理后得到 R⁺：

def transitive_closure(vertices, edges):
    vertices = tuple(vertices)
    reach = {(u, v): (u, v) in edges for u in vertices for v in vertices}
    for k in vertices:
        for i in vertices:
            for j in vertices:
                reach[i, j] = reach[i, j] or (reach[i, k] and reach[k, j])
    return {pair for pair, present in reach.items() if present}

vertices = ("A", "B", "C", "D")
edges = {("A", "B"), ("B", "C")}
plus = transitive_closure(vertices, edges)
star = plus | {(v, v) for v in vertices}
print(sorted(plus - edges))       # [('A', 'C')]
print(("D", "D") in plus, ("D", "D") in star)  # False True
cycle = transitive_closure(("A", "B"), {("A", "B"), ("B", "A")})
print(("A", "A") in cycle)      # True

R⁺ 不会自动排除自环：有正长度环就会出现 (a,a)。R* 还为孤立顶点补上零长度路径。本例使用 Θ(|V|³) 次布尔更新和 Θ(|V|²) 存储，只用于小型静态图。

数据库中的关系不要只靠名字类比

关系模型中的一张关系可视为满足属性类型约束的元组集合；一般二元关系只是二元组集合。SQL 表还涉及重复、NULL、键和物理存储。因此：

• 数学关系有助于理解连接与投影；
• SQL 的实际语义必须参考 Bag 和三值逻辑；
• 外键表达的是参照约束，不自动让任意业务关系满足传递或对称性。

完成检查

在底集 A={1,2,3} 上给定关系：

R={(1,1),(1,2),(2,3),(3,3)}

1. 求 dom(R)、ran(R) 和 R⁻¹；
2. 判断自反、反自反、对称、反对称、传递；
3. 写出对称闭包；
4. 写出传递闭包新增的配对；
5. 把服务调用图表示成邻接矩阵，并解释矩阵平方中的一个非零项。

参考资料

• MIT Mathematics for Computer Science