关系模型与关系代数

概念

关系模型把数据看成一堆二维表。用集合论的词说：一个关系就是若干域（domain）的笛卡尔积的一个子集。

D1 = {S1, S2, S3}          域：所有学号
D2 = {张三, 李四, 王五}      域：所有姓名
D1 × D2 一共 9 个有序对，其中真正存在的 3 个构成一个关系

一句话：关系 = 元组的集合。这个"集合"两个字带来了三条铁律：

性质	含义	现实对应
行无序	集合里的元素没有先后	没有"第一行""最后一行"，要顺序得自己 ORDER BY
行不重复	集合不存重复元素	同一个元组只出现一次
属性原子	每个分量不可再分	没有"表里套表"，这叫第一范式

关系模型的三要素：结构（就是这张表长什么样）、操作（本章的关系代数）、完整性约束（数据必须满足的规则）。

原理

一、几个名字

说法	也叫	例
关系	表	S
元组	行	(S1, 张三, 北京)
属性	列	SNO
目 / 度	元数、列的个数	S 是 3 目
候选码	候选键	SNO
分量	属性值	S1

关系模式要写清楚"哪些属性、哪些来自哪个域、哪个是主码"，通常写成 S(SNO, SNAME, CITY)。关系模式是"型"，关系是"值"——前者相当于 C 里的结构体定义，后者相当于一个具体的结构体变量。

二、键的四个层次（最容易考混）

名字	定义
超键	能唯一标识一个元组的属性集合（可能含多余属性）
候选键	极小的超键（再去掉任何一个属性就不能唯一标识）
主键	从候选键里挑一个，用来做"官方标识"
外键	本关系的属性，是另一个关系的主键

判据一句话：超键看"能不能唯一"，候选键再看"能不能再瘦"。{SNO}、{SNO, SNAME} 都是超键，但只有 {SNO} 是候选键。

三、五个基本运算

关系代数是以关系为输入、以关系为输出的运算，正因为输出还是关系，才能层层嵌套。

运算	符号	中文	直观理解
选择	${\sigma }_{\mathrm{条}\mathrm{件}}(R)$	选择	横着切：挑符合条件的行
投影	${\pi }_{\mathrm{属}\mathrm{性}\mathrm{表}}(R)$	投影	竖着切：挑列，并自动去重
并	$R\cup S$	并	两个关系的元组合起来（要求同目、对应属性同域）
差	$R-S$	差	在 R 里但不在 S 里
笛卡尔积	$R\times S$	积	行数相乘，把两边的属性拼起来

还有改名 $\rho$：给关系或属性换个名字（常被算作第六个基本运算）。改名看着没用，其实必不可少——做笛卡尔积再选择时，两张表的同名属性必须先改名才能区分。

四、派生运算

派生运算不是新能力，只是基本运算的组合写起来更好看：

运算	含义	等价写法
交 $R\cap S$	两边都有的	$R-(R-S)$
$\theta$ 连接	先积、再按条件选	${\sigma }_{\theta }(R\times S)$
等值连接	$\theta$ 里只有等号	特殊情形
自然连接 $R\bowtie S$	对所有同名属性取等值连接，并去掉重复的那一组属性	等值连接 + 投影
除 $R÷S$	见下	用投影、差、积组合

除法的定义：$R÷S=\{t\mid \text{对 }S\text{ 里的每一个元组 }s，t\cdot s\in R\}$。

翻译成话："R 里那些'和 S 中每一个都配过对'的元组"。它的典型用途就是"选修了全部课程的学生"这类问句。写起来等价于：

$${\pi }_A(R)-{\pi }_A(({\pi }_A(R)\times S)-R)$$

读法："能配上的" 减掉 "本该配上却没配上一些的"。

五、关系代数 ↔ SQL

关系代数	SQL	备注
${\sigma }_{\mathrm{条}\mathrm{件}}$	WHERE	选行
${\pi }_{\mathrm{属}\mathrm{性}}$	SELECT DISTINCT	投影会去重，所以 SELECT 要加 DISTINCT 才等价
$\cup$ / $-$ / $\cap$	UNION / EXCEPT / INTERSECT	都要求并兼容
$\times$	CROSS JOIN	慎用，行数会爆
$\bowtie$	NATURAL JOIN	按同名属性配
$\rho$	AS	改名

最容易踩的一条：关系代数的投影天生去重，而 SQL 的 SELECT 默认不去重。所以写"等价改写"的题，DISTINCT 不能丢。

六、完整性约束与三值逻辑

约束	管什么
实体完整性	主键不能为空（也不能重复）
参照完整性	外键要么为空，要么必须指向存在的那个元组
用户定义完整性	业务自己的规则（成绩 0~100）

NULL 带来的三值逻辑：任何与 NULL 的比较都得到 UNKNOWN——不是 TRUE，也不是 FALSE。WHERE 只留下结果为 TRUE 的行，所以 GRADE > 80 遇到 GRADE 是 NULL 的行会既不选中也不报错。WHERE 里 NULL = NULL 也是 UNKNOWN，判断空值只能用 IS NULL。

示例

例 1：关系代数用循环实现（C）

#include <stdio.h>
#include <string.h>

/* S(SNO, SNAME, CITY) —— 为了 printf 对齐，这里用 ASCII 数据 */
static const char *SNO[3]   = {"S1", "S2", "S3"};
static const char *SNAME[3] = {"Zhang", "Li", "Wang"};
static const char *CITY[3]  = {"BJ", "SH", "BJ"};

/* SC(SNO, CNO, GRADE) */
static const char *SC_SNO[4] = {"S1", "S1", "S2", "S3"};
static const char *SC_CNO[4] = {"C1", "C2", "C1", "C2"};
static int         SC_G[4]   = {90, 85, 70, 95};

int main(void) {
    printf("=== (1) sigma_CITY=BJ(S) ===\n");
    for (int i = 0; i < 3; i++)
        if (strcmp(CITY[i], "BJ") == 0)
            printf("  %-4s %-8s %s\n", SNO[i], SNAME[i], CITY[i]);

    printf("=== (2) pi_SNAME(S) ===\n");
    for (int i = 0; i < 3; i++) printf("  %s\n", SNAME[i]);

    printf("=== (3) S join SC（按 SNO 自然连接） ===\n");
    printf("  %-4s %-8s %-4s %-4s %s\n", "SNO", "SNAME", "CITY", "CNO", "GRADE");
    int rows = 0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 4; j++)
            if (strcmp(SNO[i], SC_SNO[j]) == 0) {
                printf("  %-4s %-8s %-4s %-4s %d\n",
                       SNO[i], SNAME[i], CITY[i], SC_CNO[j], SC_G[j]);
                rows++;
            }
    printf("  共 %d 行\n", rows);

    printf("=== (4) pi_SNAME(sigma_CNO=C1(S join SC)) ===\n");
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 4; j++)
            if (strcmp(SNO[i], SC_SNO[j]) == 0 && strcmp(SC_CNO[j], "C1") == 0)
                printf("  %s\n", SNAME[i]);

    printf("=== (5) 除法：选修了全部课程的学生 ===\n");
    for (int i = 0; i < 3; i++) {
        int cnt = 0;
        for (int j = 0; j < 4; j++)
            if (strcmp(SNO[i], SC_SNO[j]) == 0) cnt++;
        if (cnt == 2) printf("  %-4s %s\n", SNO[i], SNAME[i]);
    }
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

=== (1) sigma_CITY=BJ(S) ===
  S1   Zhang    BJ
  S3   Wang     BJ
=== (2) pi_SNAME(S) ===
  Zhang
  Li
  Wang
=== (3) S join SC（按 SNO 自然连接） ===
  SNO  SNAME    CITY CNO  GRADE
  S1   Zhang    BJ   C1   90
  S1   Zhang    BJ   C2   85
  S2   Li       SH   C1   70
  S3   Wang     BJ   C2   95
  共 4 行
=== (4) pi_SNAME(sigma_CNO=C1(S join SC)) ===
  Zhang
  Li
=== (5) 除法：选修了全部课程的学生 ===
  S1   Zhang

例 2：用集合实现关系代数（Python 对照）

def dw(s):
    """显示宽度：中文算 2 列"""
    return sum(2 if ord(c) > 0x2000 else 1 for c in s)


def pad(s, w):
    return s + " " * max(0, w - dw(s))


def show(title, rel, cols):
    rows = sorted(rel)
    widths = []
    for i, c in enumerate(cols):
        w = dw(c)
        for r in rows:
            w = max(w, dw(str(r[i])))
        widths.append(w + 2)
    print("  " + title)
    print("    " + " | ".join(pad(c, widths[i]) for i, c in enumerate(cols)))
    for r in rows:
        print("    " + " | ".join(pad(str(r[i]), widths[i]) for i in range(len(cols))))
    print("    " + pad("共 %d 行" % len(rows), 12))


# 关系就是“元组的集合”：重复行自动消掉，行序无意义
S = {("S1", "张三", "北京"),
     ("S2", "李四", "上海"),
     ("S3", "王五", "北京")}
SC = {("S1", "C1", 90),
      ("S1", "C2", 85),
      ("S2", "C1", 70),
      ("S3", "C2", 95)}
C = {("C1", "数据库"), ("C2", "操作系统")}

print("=== 三个关系（都是元组的集合） ===")
show("S(SNO, SNAME, CITY)", S, ["SNO", "SNAME", "CITY"])
show("SC(SNO, CNO, GRADE)", SC, ["SNO", "CNO", "GRADE"])
show("C(CNO, CNAME)", C, ["CNO", "CNAME"])

print()
print("=== sigma 选择（按行筛）: CITY = 北京 的学生 ===")
show("sigma_CITY=北京(S)", {r for r in S if r[2] == "北京"}, ["SNO", "SNAME", "CITY"])

print()
print("=== pi 投影（按列留，自动去重）: 所有出现过的城市 ===")
show("pi_CITY(S)", {(r[2],) for r in S}, ["CITY"])
print("  注意：投影之后行数从 3 变成 2 —— 集合会消掉重复")

print()
print("=== 笛卡尔积 S x C 的规模 ===")
prod = {(s[0], s[1], c[0], c[1]) for s in S for c in C}
print("  |S| = %d，|C| = %d  ->  |S x C| = %d" % (len(S), len(C), len(prod)))
show("S x C（只列前 3 行）", set(sorted(prod)[:3]), ["SNO", "SNAME", "CNO", "CNAME"])

print()
print("=== 自然连接 S join SC（按同名属性 SNO 配对） ===")
join = {(s[0], s[1], s[2], c[1], c[2]) for s in S for c in SC if s[0] == c[0]}
show("S join SC", join, ["SNO", "SNAME", "CITY", "CNO", "GRADE"])


def divide(r, cols_r, s, cols_s):
    """r ÷ s：cols_s 必须是 cols_r 的真子集"""
    head = [c for c in cols_r if c not in cols_s]
    hi = [cols_r.index(c) for c in head]
    si = [cols_r.index(c) for c in cols_s]
    out = set()
    for v in {tuple(row[i] for i in hi) for row in r}:
        cover = {tuple(row[i] for i in si) for row in r
                 if tuple(row[i] for i in hi) == v}
        if cover >= s:
            out.add(v)
    return out


print()
print("=== 除法：选修了全部课程的学生 ===")
R = sorted({(a, b) for (a, b, g) in SC})        # pi_{SNO,CNO}(SC)
D = {c[0] for c in C}                           # pi_CNO(C)
print("  " + pad("pi_{SNO,CNO}(SC)", 20) + str(R))
print("  " + pad("pi_CNO(C)", 20) + str(sorted(D)))
res = divide(R, ["SNO", "CNO"], {("C1",), ("C2",)}, ["CNO"])
name = {s[0]: s[1] for s in S}
print("  " + pad("商 =", 20) + str(sorted(res)))
for sno in sorted(res):
    print("    " + sno[0] + "  " + name[sno[0]] + "  两门课都选了")

print()
print("=== 三值逻辑：GRADE 里有 NULL 时 ===")
SCN = {("S1", "C1", 90), ("S2", "C2", None), ("S3", "C1", 70)}
print("  " + pad("元组", 22) + "GRADE > 80 的结果")
for t in sorted(SCN, key=lambda x: x[0]):
    if t[2] is None:
        verdict = "UNKNOWN（不是 TRUE，不会被选中）"
    else:
        verdict = "TRUE" if t[2] > 80 else "FALSE"
    print("  " + pad(str(t), 22) + verdict)
kept = {t for t in SCN if t[2] is not None and t[2] > 80}
print("  sigma_{GRADE>80} 实际留下 %d 行；NULL 那一行既不算满足也不算不满足" % len(kept))

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

=== 三个关系（都是元组的集合） ===
  S(SNO, SNAME, CITY)
    SNO   | SNAME   | CITY  
    S1    | 张三    | 北京  
    S2    | 李四    | 上海  
    S3    | 王五    | 北京  
    共 3 行     
  SC(SNO, CNO, GRADE)
    SNO   | CNO   | GRADE  
    S1    | C1    | 90     
    S1    | C2    | 85     
    S2    | C1    | 70     
    S3    | C2    | 95     
    共 4 行     
  C(CNO, CNAME)
    CNO   | CNAME     
    C1    | 数据库    
    C2    | 操作系统  
    共 2 行     

=== sigma 选择（按行筛）: CITY = 北京 的学生 ===
  sigma_CITY=北京(S)
    SNO   | SNAME   | CITY  
    S1    | 张三    | 北京  
    S3    | 王五    | 北京  
    共 2 行     

=== pi 投影（按列留，自动去重）: 所有出现过的城市 ===
  pi_CITY(S)
    CITY  
    上海  
    北京  
    共 2 行     
  注意：投影之后行数从 3 变成 2 —— 集合会消掉重复

=== 笛卡尔积 S x C 的规模 ===
  |S| = 3，|C| = 2  ->  |S x C| = 6
  S x C（只列前 3 行）
    SNO   | SNAME   | CNO   | CNAME     
    S1    | 张三    | C1    | 数据库    
    S1    | 张三    | C2    | 操作系统  
    S2    | 李四    | C1    | 数据库    
    共 3 行     

=== 自然连接 S join SC（按同名属性 SNO 配对） ===
  S join SC
    SNO   | SNAME   | CITY   | CNO   | GRADE  
    S1    | 张三    | 北京   | C1    | 90     
    S1    | 张三    | 北京   | C2    | 85     
    S2    | 李四    | 上海   | C1    | 70     
    S3    | 王五    | 北京   | C2    | 95     
    共 4 行     

=== 除法：选修了全部课程的学生 ===
  pi_{SNO,CNO}(SC)    [('S1', 'C1'), ('S1', 'C2'), ('S2', 'C1'), ('S3', 'C2')]
  pi_CNO(C)           ['C1', 'C2']
  商 =                [('S1',)]
    S1  张三  两门课都选了

=== 三值逻辑：GRADE 里有 NULL 时 ===
  元组                  GRADE > 80 的结果
  ('S1', 'C1', 90)      TRUE
  ('S2', 'C2', None)    UNKNOWN（不是 TRUE，不会被选中）
  ('S3', 'C1', 70)      FALSE
  sigma_{GRADE>80} 实际留下 1 行；NULL 那一行既不算满足也不算不满足

三条结论：

1. C 与 Python 两段给出同一组答案：(1) 两行、(3) 4 行、(4) 两行、(5) 只有 S1。C 用数组下标循环，Python 用集合运算——同一套关系代数，两种实现。
2. 投影把 3 行变成 2 行：S 里有 3 个学生，但城市只有两个不同值。这是"关系是集合"的直接后果，也是 SELECT 必须配 DISTINCT 才能与投影等价的原因。
3. 除法的答案是 S1：只有 S1 两门课都选了（S2 只选 C1、S3 只选 C2）。除法就是"对全部"这三个字的代数化。

考点

考点

1. 键的四层判据

• 超键：能唯一标识元组的属性集合（可以含多余属性）。
• 候选键：极小的超键。
• 主键：从候选键里选一个。
• 外键：本关系的属性，是另一个关系的主键（也可以是同一个关系的主键，如"上级"）。

2. 关系的两个"数"

• 目（度） = 属性的个数。
• 基数 = 元组的个数。
• 笛卡尔积：结果目 = 两边目之和、基数 = 两边基数之积。

3. 五个基本运算（能默写）

选择 $\sigma$、投影 $\pi$、并 $\cup$、差 $-$、笛卡尔积 $\times$（外加改名 $\rho$）。

4. 三种连接分得清

连接	条件	结果属性
$\theta$ 连接	任意条件	两边属性都保留
等值连接	条件只有 =	两边属性都保留（含重复的那列）
自然连接	对所有同名属性取 =	同名属性只留一份

"自然连接 = 等值连接 + 去掉重复列" 是最省事的记法。若两个关系没有同名属性，自然连接退化成笛卡尔积。

5. 外连接

类型	保留什么
左外连接 ⟕	保留左表所有行，右表配不上的填 NULL
右外连接 ⟖	保留右表所有行
全外连接 ⟗	两边都保留

6. 高频陷阱

• 投影去重，SELECT 不去重——等价改写时 DISTINCT 不能省。
• 并、差、交要求"并兼容"：目相同，且对应属性的域相同。名字不同没关系，看的是域。
• R - S 与 S - R 不是一个东西；∪ 才可交换。
• NULL 参与比较得到 UNKNOWN，WHERE 只留 TRUE；NULL = NULL 是 UNKNOWN，判空要用 IS NULL。
• 实体完整性管主键非空，参照完整性管外键有效，两者不要搞反。
• %-8s 排中文会错位：C 的 printf 按字节补齐，一个汉字占 3 字节、显示只占 2 列。所以上面的 C 例用 ASCII 数据，含中文的表交给 Python 的 pad() 按显示宽度补齐。

小结

• 关系 = 元组的集合：行无序、行不重复、属性原子，这三条决定了后面所有结论。
• 超键能唯一、候选键还要极小；主键负责标识，外键负责联系。
• 关系代数只有五个基本运算，连接与除法都是拼出来的；自然连接 = 等值连接 + 去重列。
• 与 SQL 的对应要盯住一处：投影天生去重，所以 SELECT 要配 DISTINCT。

回到主线：soft 这一层是"主线走完之后的向上延伸"。上一章（代码生成）把程序落成了机器码，这五章合起来把 lang/20-steps.md 里那句"编译器把 C 变成汇编"拆成了五个能各自讲清的阶段。本章换了个话题——从"怎么让机器算"转到"怎么把数据组织好"。关系模型是数据库的地基，下一章要做的，就是给它配一套能实际敲的语言：SQL。

下一篇：SQL 基础