DB 论文阅读：A Relational Model of Data for Large Shared Data Banks
关系模型是现代数据库的理论基础。1969 和 1970 年，Codd 的两篇论文 《Derivability, Redundancy and Consistency of Relations Stored in Large Data Banks》和《A Relational Model of Data for Large Shared Data Banks》提出了关系模型理论，为后续几十年数据库领域的发展提供了基础。
由于 1969 年的论文实际上就是《A Relational Model of Data for Large Shared Data Banks》的非正式版本，二者内容基本一致，所以本文仅介绍 1970 年发表在 Communications of the ACM 上的正式论文《A Relational Model of Data for Large Shared Data Banks》。
1. 背景介绍
要想理解关系模型为什么被提出，首先需要了解论文发表时的时代背景。
当时的数据库系统大多采用树形或网状结构，应用程序与数据库的物理存储结构紧密耦合，应用程序的开发者必须知道数据库中数据的物理存储结构，并在应用程序中实现相关逻辑进行数据访问。一旦数据库的物理存储结构发生变化，那么应用程序的相关代码也必须进行相应的改变。
这种应用和数据库紧密耦合的问题在论文中被统称为 “Data Dependencies”，具体地，有以下 3 种迫切需要移除的数据依赖：
Ordering Dependence
排序依赖指在某些系统中，数据元素的存储方式与硬件确定的地址顺序紧密相关。例如，一个存储零件记录的文件可能按照零件序列号升序存储。这些系统允许应用程序员假设记录的展示顺序与物理存储顺序一致。应用程序可能依赖于这一假设实现，这导致当需要更换物理存储顺序时，依赖于存储顺序的应用程序可能无法正确运行。
Indexing Dependence
索引通常被视为数据表示的性能导向组件，它通常能提高对查询和更新的响应，同时可能会减慢插入和删除操作的响应。从信息角度来看，索引是数据表示的冗余部分。索引依赖指应用程序和终端活动能否在索引的创建和销毁过程中保持不变，也即索引存在与否不影响应用的正常运行。
Access Path Dependence
访问路径依赖指许多现有的格式化数据系统为用户提供了树状文件或更一般的网络模型的数据。为这些系统开发的应用程序在树或网络结构发生变化时，逻辑上可能会受损。
2. 关系模型
为了解决已有系统的问题，Codd 提出了关系模型，将数据的表示和数据的存储解耦。关系模型仅描述数据的逻辑结构，而不限制数据的物理存储结构。
2.1 概念
在原论文中，关系是使用集合和笛卡尔积严格定义的：
给定集合 \(S_1, S_2, …, S_n\) ，\(R\) 是 \(n\) 个集合上的关系，如果 \(R\) 是 \(n\) 元元组的集合，且元组的第一个元素来自集合 \(S_1\) ，元组的第二个元素来自 \(S_2\) ，……，以此类推。用更简洁的形式表述，也就是 \(R\) 是 \(S_1 \times S_2 \times … \times S_n\) 的子集。
据此，可以引出我们已经非常熟悉的概念，如：元组、表、列等等，在此不再介绍。
关系型模型的优点在于提供了一种描述数据的自然结构的方式，即只描述数据本身，而不涉及机器表示的额外结构。这为高级数据语言提供了基础，并有助于清晰评估当前格式化数据系统的逻辑限制。
2.2 正规形式
2.1 小节定义的关系允许含有非简单域，也就是允许某个列也是关系。当关系中含有非简单域时，需要更复杂的数据结构来存储。为了降低存储复杂度，可以将关系进行规范化。
Codd 提出了一种称为规范化（Normalization）的过程，该过程从树状结构的顶部关系开始，通过插入父关系的主键来扩展每个直接下级关系。然后从父关系中删除所有非简单域，移除树的顶部节点，并在剩余的子树上重复这个过程。为了使规范化过程适用，非规范化的关系集合必须满足两个条件：非简单域之间的相互关系图必须是一系列树，且没有任何主键包含非简单域的组成部分。
原论文的例子可以帮助理解：
2.3 关系的操作
此小节实际上就是关系代数的内容，讨论了如何使用运算符及运算符的组合对关系进行运算。
对关系代数的介绍可参考： 从关系代数到 SQL ，本文不再介绍。
2.4 冗余性
本小节讨论了数据库中数据冗余的概念，以及如何通过关系型数据模型来管理和减少冗余。
首先需要引入定义 \(θ\)-derivable ：
给定关系的操作集合 \(\theta\) ，如果存在来自 \(\theta\) 的操作序列，能够从关系集合 \(S\) 中经过这些操作产生关系 \(R\) ，则称 \(R\) 是可从 \(S\) 中 \(θ\)-derivable 的。
在此基础上引出强冗余性和弱冗余性的定义。
强冗余性
当关系集中至少有一个关系可以通过其他关系的投影推导出来时，就存在强冗余。这意味着关系集中存在不必要的重复数据，一般需要重新设计关系模式以消除冗余。
弱冗余性
当关系集中存在一个关系，其投影不是从其他关系推导出来的，但始终是其他关系投影的某个连接的投影时，就存在弱冗余。这种冗余是固有的，通常与用户社区的逻辑需求相关，一般不需要消除。
2.5 一致性
在本小节中，Codd 定义了数据一致性的概念，即在给定的一组关系（\(C\)）、一组约束声明（\(Z\)）和关系集的即时值（\(V\)）的情况下，如果 \(V\) 满足 \(Z\) ，则称状态 （\(C, Z, V\)） 是一致的，否则是不一致的。
为了保持系统的一致性，可在插入、删除或更新操作时检查可能的不一致性，以及定期进行一致性检查。
3. 总结
以上就是对论文 《A Relational Model of Data for Large Shared Data Banks》主要内容的总结。本文章节与原论文章节并非一一对应，而是重新进行了组织，同时删除了个人认为不影响理解论文核心内容的章节，如原论文 1.5 和 1.6 小节等，具体请参阅原论文。
参考：