Codd 1970 年论文,逐段注解

#TL;DR

Edgar Codd 1970 年发表在 Communications of the ACM 上的论文,重新定义了计算机如何存储数据。它也是一篇极其紧凑的写作——12 页的文档,在相当于一次展会咖啡休息的时间里,悄悄地扔下了关系、外键、范式和完整查询语言的数学定义。这篇文章走一遍这篇论文实际上说了什么、那些精确的定义意味着什么、哪些活到了 SQL、哪些没有,以及为什么 Codd 在论文发表后还要再多斗十年才能看到自己的想法按照他本来的意图被实现。

#背景

1970 年,Edgar Codd 是一位英国出身的数学家,就职于 IBM 圣何塞研究实验室。他在 IBM 已经待了将近二十年——足够长以致亲眼见过第一代层次数据库(IMS)和网状数据库(CODASYL)投入生产。他认为两者的设计都是错的。不是有 bug——是概念上错了。

他在 1970 年 6 月发表的论文,“A Relational Model of Data for Large Shared Data Banks,” 是另一种路径的论证。12 页,紧凑,数学上精确,而且明显是写给计算机科学家而不是 DBA 看的。IBM 自己的数据库小组在多年里基本无视它。

#“关系”是什么意思

论文开头有一个很容易被一扫而过的定义:

给定集合 S₁, S₂, …, Sₙ(不必互不相同),如果 R 是 n-元组的一个集合,其中每个元组的第一个元素来自 S₁、第二个元素来自 S₂、依此类推,那么 R 是这 n 个集合上的一个关系。

翻译过来:一个关系是一组元组,每个元组有相同的结构。每个”集合” Sᵢ 被称为一个域 (domain)——该位置所能取的所有可能值的集合。示例:

Customers 是 { CustomerID, Name, City } 上的一个关系:

(101, "Ada Lovelace", "London")
(102, "Alan Turing",  "London")
(103, "Grace Hopper", "New York")

每个元组是 CustomerID × Name × City 的一个元素——三个集合的笛卡尔积。关系是那个笛卡尔积的子集。并不是所有可能的组合都在这个关系里;只有真正代表合法数据的那些。

论文很小心地把关系(数学对象——一组元组)和关系模式(结构的描述——列的名称和类型)分开。在 SQL 里,表大致相当于一个关系的存储表示,但有一些重要差异。

#Codd 在意的区别:重复和顺序

论文里两个细节非常关键,但没完全活到 SQL 里:

关系是集合。 不允许重复元组。两行完全相同的行会合并成一行。
关系是无序的。 没有”第一行”。依赖物理顺序的查询就是在作弊——你想排序就必须明确说怎么排。

SQL 把这两点都放松了。SQL 表在技术上是袋 (bag)(多重集),不是集合——重复是允许的。SQL 有 SELECT DISTINCT 来恢复集合性质,这意味着默认是非关系的。Codd 在他余生的职业生涯都在反对这件事。他后来的 “规则 1”(来自 1980 年代发布的 Codd 12 条规则)明确要求表必须是关系,不是袋。

顺序问题更微妙。SQL 没有 ORDER BY 时不保证行序,但实践中实现常常按插入顺序或存储顺序返回行,于是应用代码就长期依赖这一点。Codd 的论文讲得很明白:如果你的查询需要排序输出,那查询本身应该指明排序。依赖实现是一种范畴错误。

#数据独立性:这篇论文的目标

论文的动机——也是它最具后果的论点——出现得很早:

当今格式化数据银行盛行的模型是树(或层次)模型……这样的技术迫使程序去知道存储表示的特定顺序。

Codd 的论断是:层次数据库和网状数据库有一个设计缺陷——应用代码必须知道数据物理上是怎么存储的。存储一变,代码就坏。改一个索引、给表分区、换一套硬件——这些任何一件事都可能需要重写几百个程序。

他提出的解决办法是数据独立性:干净地分离数据的意义和数据的存储方式。查询描述想要的结果;数据库引擎负责找出物理访问路径。应用代码永远不需要知道索引、存储布局或访问方法。

在 1970 年这是激进的主张。它要求两样当时任何生产数据库都没有的东西:

一个声明式查询语言,只按逻辑结构描述数据。
一个查询优化器,能把逻辑查询高效地翻译成物理访问计划。

Codd 的论文勾画了第一样。第二样成了 System R(IBM 1974-79 的研究项目)以及之后每一个数据库的核心工程挑战。

#关系代数

论文引入了一组关系上的运算,合在一起构成关系代数。这些是查询语言最终会对外暴露的原语。Codd 的原始列表:

σ(选择) — 选出满足某条件的元组。σ city='London' (Customers) 返回伦敦客户。
π(投影) — 选出特定列。π name, city (Customers) 返回只有 (name, city) 对的关系。
×(笛卡尔积) — 把一个关系中的每个元组与另一个关系中的每个元组配对。
⋈(连接) — Codd 的论文叫”自然连接”:把两个关系中共享属性值的元组合并。
∪, ∩, −(并、交、差) — 标准集合运算。
÷(除法) — 用于”所有满足 X,使得对每个 Y 都……”的查询。这个很少能在不做体操的情况下活到 SQL。

论文证明了仅凭这些原语,就能表达数据上任何一阶逻辑查询。这是我们今天所谓**“关系完备”** 的数学基础——一门查询语言表达的内容等同于关系代数所能表达的。

SQL 在面世时被设计成关系完备。它的语法与 Codd 的记号不同——是 SELECT name FROM customers WHERE city = 'London' 而不是 π name (σ city='London' (Customers))——但表达能力本应是等价的。

本应。实践中,SQL 与纯关系代数的偏离(袋语义、NULL、隐式类型转换)让某些查询只能在一边表达、不能在另一边表达。Codd 抱怨过这件事,大多数从业者并不在意。

#外键与参照完整性

论文引入了外键的概念——一个关系中的属性,其取值必须匹配另一个关系中主键的取值。这就是实体间关系不通过物理指针也能被表达的机制。

关键性质是参照完整性:如果 orders 中有一条元组 customer_id = 101,那么 customers 里必须确实有一条 id = 101。删客户时要么级联(把订单一起删),要么被阻止(删除失败)。

层次数据库按结构就有参照完整性——子记录根本不能脱离父记录而存在。关系数据库则必须显式强制。Codd 1970 年的论文引入了概念但基本上没谈如何强制。要到 1989 年 SQL-89 标准引入 FOREIGN KEY 约束时,这部分工作才进 SQL。

#范式(隐含)

1970 年的论文没有使用”范式”这个术语——那是 Codd 1971-72 年的后续论文才出现的。但 1970 年的论文已经提出了范式要解决的问题。它定义了键(能唯一标识元组的属性)和函数依赖(如果知道 A 就能知道 B,则属性 A 决定属性 B)。它指出属性被冗余存储时会出现”异常”。

到 1972 年,Codd 形式化了第一、第二和第三范式,到 1974 年他和 Boyce 定义了 Boyce-Codd 范式来处理 3NF 漏掉的情况。范式那篇文章详细走过这些。1970 年的论文是种子埋下的地方。

#论文里没有的东西

今天感觉跟关系数据库密不可分的一些东西,在 1970 年的论文里并不存在:

SQL。 论文通篇使用关系代数记号。SQL——当时叫 SEQUEL——是 IBM 的 Chamberlin 和 Boyce 从 1974 年开始设计的,目的就是让 Codd 的数学对程序员可用。
索引。 论文不描述索引结构或物理存储。这正是重点——论文主张这些细节应该对用户不可见。真正的索引工作(B 树、哈希索引)是另外做的。
事务与 ACID。 并发和故障恢复是后续工作,尤其是 Härder 和 Reuter 1983 年对 ACID 的形式化。
SQL 的 NULL。 Codd 对 NULL 有名的摇摆。他主张三值逻辑(真、假、未知),但也觉得 NULL 在实践中被滥用了。后来他提出多种 NULL(值未知 vs. 值不适用),SQL 实现没有采纳,他自己也没完全放弃。

#没活下来的部分

论文里一些部分被丢下了:

默认用”自然连接”。 Codd 的论文主要把连接当成自然连接——自动按同名属性连接。SQL 把这个做成了选择项(通过 NATURAL JOIN),大多数从业者宁可用显式的 JOIN ... ON,因为跨表依赖命名约定太脆弱。
除法。 ÷(关系除法)运算符强但别扭。SQL 没有直接对应的东西;要表达”找出供应所有零件的供应商”需要嵌套的 NOT EXISTS 子查询或类似绕路。
纯集合语义。 如上所述,SQL 用的是袋语义。
Codd 自己那套 NULL 方案。 他关于多种 NULL 的提案从未进入 SQL。
论文提出的”更新”操作。 论文里关于在外键存在时如何处理删除的讨论相当笨拙,后来被完全重做。

#Codd 自己的挫败

关系模型那篇文章提到 IBM “压着”关系模型好些年。Codd 本人在 1970 年代和 1980 年代一直挫败于 IBM 交付了他认为关系得不完整的产品(SQL/DS,后来的 DB2)。

1985 年,他发表了 “Codd 12 条规则”(实际是 13 条,从 0 编到 12),作为一份显式的清单,规定一个关系数据库应该做什么。规则故意很严格——没有任何一款商业数据库完全满足所有条款。IBM 的 DB2、Oracle 以及所有其他厂商在各种条目上都失分。

Codd 12 条规则部分也是一种营销动作,针对那些宣称”关系”但实际把关系查询栓在根本不关系的内部之上的厂商。他在 1980 年代末大部分时间都在到处演讲,用他的规则给商业产品打分。厂商恨死这事了。

规则本身是有用的纯度测试。但它也暴露了理论优雅与工程实际之间的落差——严格满足 Codd 规则的数据库未必是最好的数据库,只是数学上最一致的。业界基本上落脚在”类关系”系统上,做了 Codd 不会赞同的实用权衡。

#为什么这篇论文经得住时间

1970 年代的计算机科学论文多数只剩历史价值。Codd 的这一篇仍然是承重的基础设施。你写过的每一条 SQL 查询都会经过一个查询优化器,而它在应用这篇论文里的概念。外键、连接、数据独立性——全部都直接追溯到那 12 页。

它经得住时间的原因:

它不特定于实现。 Codd 描述的是一种数学模型,不是一种数据结构。这意味着这些想法跨越了硬件、存储和软件架构的代际变化仍然存活。
它做出了对的关注点分离。 逻辑 vs. 物理,声明式 vs. 过程式。后面每一个数据库系统都采用了那种分离,因为另一条路就是重复 CODASYL 曾犯的耦合错误。
它可证明是完备的。 关系代数被已知恰好表达结构化数据上的一阶逻辑。这意味着查询语言不会以某种出乎意料的方式耗尽表达力——而早期的层次查询语言有时会。

关系模型那篇文章把这篇论文总结为”看似简单”。“看似”这两个字承担了太多重量。表面之下是集合论、一阶逻辑、函数依赖理论,以及关于数据库是什么的一份精确论证——论证足够细致,所以过去五十六年的工程实践基本都是在填充细节,而不是回过头重订蓝图。