Codd 1970：关系怎样把大型共享数据库从访问路径里解放出来

破除误解：关系不是表格，独立性也不是换一块更快的磁盘#

第一层误解把「关系」听成电子表格，或听成「排成行列就算关系数据库」。科德取的是数学上的通常含义：给定集合 $S_1,S_2,\ldots,S_n$（不必互异），$R$ 是笛卡尔积的一个子集，每个 $n$ 元组的第 $j$ 个分量取自 $S_j$。用来讲解的阵列有五条性质：每行是一个 $n$ 元组；行序无关；行互异；列序对应域序；列名部分传达该域的意义。阵列不是关系观点的本质部分。用户也不应记住域次序。科德因此区分域有序的关系，与对域置换等价的、域无序的 relationship（关系对应物），并在域重复时用角色名限定，例如零件爆炸里的 sub.part 与 super.part。把 1970 年读成「表等于关系」，会把集合语义收成格子纸，也会把后来 SQL 允许的重复行提前写进这一年。

第二层误解把标题听成 SQL 的出生证明，或听成「科德在这一年发明了数据库」。当时已有可共享的格式化数据系统。论文点名 IMS/360、GIS、TDMS、IDS，以及查尔斯·巴赫曼（Charles W. Bachman）1965 年谈随机访问处理的文章。科德要改的不是「第一次把数据放进机器」，而是用户模型仍被表示性质弄脏——尤其是集合如何被表示。提示服务把内部布局告诉用户，在他看来不是合格答案。终端与大多数应用程序，应在内部表示改变、甚至外部表示的某些方面改变时仍然不受影响。把 1970 年收成查询语言年表的第一章，会把一份数据模型论文误认成语法标准。

第三层误解把数据独立性听成换磁盘，或听成「加一层描述表就够」。描述表已经朝独立性迈了一步，可在不从逻辑上损伤程序的前提下能改的特征仍然很窄。要去掉的是三种依赖。排序依赖：程序假定呈现次序等于按零件序号存放的次序；次序一换就不正确，指针实现的存放次序同样如此。索引依赖：索引在信息上是冗余部件，活动模式会变，索引就应能被建立与撤销。TDMS 无条件为所有属性建索引；当时的 IMS 只在「完全不索引」与「只索引主键」之间选择，应用逻辑并不依赖那些无条件索引。IDS 却让程序按名字引用索引链，链一撤程序就不正确。访问路径依赖：同一份「零件、项目、占用数量」至少可写成五种层次结构。一个不为当前结构做检测的程序 $P$，在其中一种上能跑，就会在其余至少三种上失败。网状模型碰到同类困难。路径是否与存放指针一一对应并不重要：IDS 里对应极简单，TDMS 里正好相反。后果一样：程序依赖这些用户访问路径继续存在。把「路径一旦定义就永不作废」当成政策，科德认为不实际，因为共同体的路径总数会膨胀到无法收拾。

第四层误解把本页收成模式设计手册，或收成注入与越权的操作单。文中的正规形式只做一件事：去掉非简单域（元素本身还是关系，大致对应当时的重复组）。手续是把树顶主键插入直接下属，再删掉父关系里的非简单域，对剩余子树重复。适用条件有两条：非简单域的相互关系图是若干棵树；主键的任何分量都不是非简单域。进一步的正规化运算「本文不予讨论」。二范式以后的名字、System R、优化器都不在这十一页里。本文也不讨论实现。把投影写成拆表步骤，或把谓词条件写成探测语句的拼接法，会离开这份证据对象。

装置：域、元组、键，以及不必知道银行怎样铺开的检索#

数据银行的全体数据被看成一组随时间变化的关系，度数参差；商业与科学银行里度数到 30 并不罕见。每个域在某一瞬间实际出现的值，叫做该瞬间的活跃域。通常，一个域或若干域的组合能唯一标识每个 $n$ 元组，这个组合叫做主键。主键是非冗余的，若它是简单域，或是没有多余分量的组合。可以有多个非冗余主键，此时任意选定一个。外键是关系 $R$ 上不是主键、其元素却是某关系 $S$ 主键值的域或域组合；$S$ 与 $R$ 可以相同。在度数为 4 的 supply 里，供应商—零件—项目是主键，三者各自都是外键。科德据此拒绝把数据银行拆成「实体描述」与「实体之间的关系」两摊：外键可以出现在任何关系里，这道分界在用户模型里站不住。交叉引用的用户手段是键上的值，不是地址。

正规形式要服务的，是表示简单，以及系统之间批量交换时不再携带指针、散列方案与索引。数据项名字可简化为 $R(g).r.d$，常常 $R.d$ 就够。命名集是共同体能用简单名字识别的关系；可表达集是数据语言表达式所能指定的全部关系，通常大得多。存放表示是第三层：系统必须把关系模型上的请求翻译成对当前存放表示的有效动作。科德把这写成困难设计问题，并写明实现不予讨论。翻译层后来长成优化器，那不是 1970 年的封面。

语言这一侧要的是一种通用数据子语言，建立在应用谓词演算之上；已在正规形式中，则一阶就够。子语言声明关系、域与主键；宿主给出可以不那么永久的存放声明。通用性在于描述能力，不在计算能力。每个子集有极多合理描述，因此限定表达式必须具有应用谓词演算合式公式那一档描述力；前束范式已经够用。插入不问机器表示里的次序。对称利用要求：关系一旦存放，就应能把任意一组变元当已知、其余当未知去查询。性能上的对称不可期望。度数 $n$ 若按路径命名，要控制的路径是 $n$ 的阶乘。若强迫写成只含二元关系的嵌套式——论文举 Feldman 的 LEAP——名字从 $n+1$ 个变成 $2n-1$ 个，某些提问会极难写。关系观点把名字贴在关系上，不贴在路径类型上。

第二节的运算专用于从关系派生关系，面向非推断系统。置换对用户的域无序模型本身不相关，却相关于存放表示。投影选定若干列并去掉重复行；$\pi_L$ 一次性给出置换、投影或二者的组合。若 $\pi_2(R)=\pi_1(S)$，二元关系 $R$ 可与 $S$ 连接，此时自然连接 $R*S=\{(a,b,c):R(a,b)\wedge S(b,c)\}$ 总存在。连接域上若有一点在两边都有多个亲属，就出现歧义点，连接可以不止一个；若一方是函数（一对一或多对一、不是一对多），自然连接是唯一连接。复合是连接后再投影。对指针路径的误解在这里有一个名字：连接陷阱。每个供应商描述用指针链到零件，每个零件再链到项目；于是有人下结论：从某供应商经零件走到项目，就得到他供应的全部项目。这个结论一般是错的。它只在目标关系恰好是另外两个关系的自然复合这一极特殊情形下成立，而且还通常必须加上「对所有时间」。限制则是用另一个关系切出子集。

这些运算被用来谈命名集里的冗余与一致性。若运算每次都得到唯一关系——自然连接合格，一般的连接不合格——则 $R$ 对集合 $S$ 是可派生的，当且仅当存在运算序列，对所有时间都从 $S$ 得到 $R$。对命名集，一组够用的运算是投影、自然连接、捆扎与限制。强冗余是某个投影可从该集合中其他投影派生：雇员关系若同时带着经理编号与经理姓名，而活跃域上二者分别总是雇员编号与姓名的子集，则经理姓名不必要。强冗余常因方便而保留，包括留住半过时的命名关系，好让旧程序仍能按名字运行。弱冗余不是等式：某个投影并不能从其他成员派生，却在所有时间都是其他投影之某个连接的投影；复合这一瞬间可以是自然的，下一瞬间可以不是。弱冗余通常来自共同体的逻辑需要，管理员去不掉。无论哪一种，都要配上与时间无关的约束。给定关系汇集 $C$、约束集 $Z$ 与瞬时值 $V$，状态 $(C,Z,V)$ 一致与否，就看 $V$ 是否满足 $Z$。一致性是瞬时状态的性质，与如何到来无关，也不区分漏做还是多做。系统通常无法在不询问环境的情况下裁决「刚才那条插入是漏了配套事实，还是根本插错了」。那不是 并发 里的隔离级别，更不是两阶段提交。

树与网是 数据结构 上合法的访问组织；科德禁止的是把它们当成用户必须命名的路径。属性图 后来把邻居指针重新写进记录，那是另一份存放哲学，用来对照 1970 年要砍掉的访问路径依赖，不是本页变厚。多版本并发 靠版本链让读不阻塞写，不代替域、键与代数。SQL 的 SELECT 是后来的工程方言。本页不填写执行计划。

它证明了什么，没有覆盖什么#

它证明了：可以把大型共享数据银行的用户模型写成 $n$ 元关系的汇集，只用数据的自然结构，不为机器表示再叠加一层结构。三种依赖会让程序在表示或树形改写时逻辑受损；值上的键可以把交叉引用从指针里搬走。正规形式允许用无指针阵列交换批量数据，并允许一阶谓词演算充当检索子语言的尺度。投影、连接、复合与限制足够用来定义可派生性，并把两种冗余写成可检查的约束；一致性是瞬时状态是否满足这些约束。子语言的通用性是描述力。路径名字的阶乘增长说明网状命名会自己把模型撑破。

它没有证明关系代数与关系演算等价。那是 1972 年《Relational Completeness of Data Base Sublanguages》的后文。1970 年只要求限定表达式具有应用谓词演算合式公式的描述力，并指出前束范式已够。它没有给出二范式以后的正规化，没有给出查询优化，没有给出锁表、日志与隔离。共享访问被当作背景：用户越多，有效响应的责任就越从个人转到数据系统。这句话不是 事务 的 ACID 定义。实现不予讨论。巴赫曼 1973 年的图灵奖演讲把程序员写成导航员，是后一年的对立面，不是 1970 年已经印好的反驳稿。Childs 1968 年的集合论数据结构被点名为例外的先驱；当时关系的主应用仍在演绎问答。本页不把优先权写成专利判决。

稳健性来自「用户看见的是值，不是路径」，不来自后来某一种产品。只要交叉引用还能用主键值说出，树形改写就不必改写应用程序；只要索引仍是信息上冗余的表示，索引的来去就不必改写应用逻辑。后来的优化器与日志，是把这篇论文留给系统的翻译题做出来，不是把 1970 年的定义写厚。把连接陷阱读成「所以应当改回指针」，是把诊断收成相反的药方。指针路径可以在某一瞬间碰巧等于自然复合，却不能被当成对所有时间都成立的目标关系。

概念证据到此为止。关系回答的是「大型共享数据银行如何只按自然结构被描述」；代数与子语言回答的是「用户如何在不知道银行铺开方式的前提下指定要哪一个子集」。两句都不是操作单。

跨域连接#

• 科学哲学：科德把关系模型写成一个可冒险的主张：若用户只看见自然结构上的关系，改变内部表示、甚至改变某些外部表示，终端与程序仍应不受影响。这不是对「表格好看」的审美，而是一条一旦树形改写、旧程序仍能跑才会被加强、一旦程序必须随路径改写就会被削弱的预测。巴赫曼后来把程序员写成导航员，是另一套关于「可控的路径才是真实结构」的研究纲领。1970 年的证据是逻辑上的反例程序，不是吞吐曲线。论文自己提供的证伪物，是那五种层次结构上不能共用的程序 $P$。
• 集合论：关系被写成笛卡尔积的子集，行互异、行序无关。这是外延：两个关系是否相同，只看它们含有哪些元组，不看指针串成什么形状。阵列是讲解，不是对象。域重复时必须用角色名，因为单靠域名无法区分同一集合在元组里的两个位置——零件作为组件与作为装配体，是同一个域上的两个角色。SQL 后来允许的包语义，是对这套外延的工程偏离，不是 1970 年已经印好的定义。
• 可计算性：子语言的通用性被明确限制在描述能力，而不是计算能力。科德要的是：有限数据银行上任何一个可检索子集，都能用应用谓词演算的合式公式指定；因为每一瞬间的关系都有限，量词可以改写成对有限集合计数的函数。这不是「任意一阶理论都可判定」，也不是停机问题被数据库取消。检索发生在已经存放的有限关系上。代数与演算是否一样强，要等到 1972 年的完全性论文。把 1970 年听成「查询语言可以计算任何可计算函数」，会把描述力收成通用计算。
• 认识论：连接陷阱是一次关于知识来源的警告。沿指针走完所有路径，得到的是连接，不必是所求的关系。供应商供应哪些项目，是一个关于目标关系的问题；供应商—零件指针加上零件—项目指针，只提供另外两个关系。仅当目标关系在所有时间都是那两个关系的自然复合，路径才能充当证据。键把「我如何知道 $A$ 指向 $B$」从地址换成值的符合。把本地指针结构当成已经共享的事实，会把一次碰巧走通的导航误认为公共知识。
• 数据结构：树、网、链与索引都是合法的组织手段，科德攻击的是它们成为用户模型。IMS 的层次组织、IDS 的索引链、零件在上或项目在上的五种树，都是访问路径这一层的数据结构选择。索引在信息上是冗余表示，可以随活动模式被建立或撤销，而不应进入应用逻辑。存放层仍需要某种结构去满足性能；论文把品种选择留给系统设计，并警告过多会造成描述的反复重解释。B 树、散列与后来的无索引邻接，都是这道存放题的答案，不是 1970 年用户应当命名的路径。

参考文献#

• E. F. Codd, "A Relational Model of Data for Large Shared Data Banks", Communications of the ACM 13(6), June 1970, pp. 377–387. DOI: 10.1145/362384.362685. —— 本文对象。
• D. L. Childs, "Feasibility of a Set-Theoretical Data Structure—A General Structure Based on a Reconstituted Definition of Relation", Proc. IFIP Congress, North-Holland, 1968, pp. 162–172. —— 论文点名的例外先驱。
• Charles W. Bachman, "Software for Random Access Processing", Datamation, April 1965, pp. 36–41. —— 论文所引的网状／随机访问处理文献。
• Alonzo Church, Introduction to Mathematical Logic, Volume I, Princeton University Press, 1956. —— 前束范式足以保存谓词演算描述力。
• E. F. Codd, "Relational Completeness of Data Base Sublanguages", in Randall J. Rustin (ed.), Data Base Systems, Courant Computer Science Symposia Series 6, Prentice-Hall, 1972, pp. 65–98. —— 后来的代数—演算完全性，不是 1970 年的定理。

延伸阅读#

• 与 埃德加·科德 对读：人物页管十二规则与产业化；本页停在 1970 年的模型与代数。
• 与 数据库与事务、Gray 1978 两阶段提交 对读：共享访问在 1970 年是动机，事务的原子结局是后文。
• 与 数据结构、属性图 对读：树与邻居指针可以是存放层；1970 年禁止的是把它们写成用户必须沿途走的名字。
• Charles W. Bachman, "The Programmer as Navigator", Communications of the ACM 16(11), 1973, pp. 653–658. DOI: 10.1145/355611.362534. —— 后一年的导航员纲领，不是封面。
• 与 PostgreSQL 的 MVCC、线性化 对读：版本链与并发对象的顺序历史，各不是关系作为存储模型这一句。