本文最后更新于：2024年11月4日下午

大型共享数据库的关系数据模型

A Relational Model of Data Large Shared Data Banks
E.F. CODD IBM Research Laboratory, San Jose, California

必须保护大型数据库的未来用户，使他们不必知道数据在机器中的组织方式（内部表示）。提供此类信息的提示服务并不是令人满意的解决方案。当数据的内部表示发生变化，甚至外部表示的某些方面发生变化时，终端和大多数应用程序上的用户活动应不受影响。由于查询、更新和报告流量的变化以及存储信息类型的自然增长，通常需要更改数据表示。

现有的非推理格式化数据系统为用户提供树形文件或稍微更通用的数据网络模型。在第 1 节中，讨论了这些模型的不足之处。介绍了基于 n 元关系的模型、数据库关系的范式以及通用数据子语言的概念。在第 2 节中，讨论了某些关系操作（逻辑推理除外），并将其应用于用户模型中的冗余和一致性问题。

关键词和短语：数据库、数据库、数据结构、数据组织、数据层次结构、数据网络、关系、可导出性、冗余度、一致性、组合、连接、检索语言、谓词演算、安全性、数据完整性 CR 类别：3.70、3.73、3.75、4.20、4.22、4.29

1.关系模型与范式

1.1引言

本文关注的是基本关系理论在提供对大型格式化数据共享访问的系统中的应用。除了 Childs [1] 的一篇论文外，关系在数据系统中的主要应用是演绎问答系统。
Levein 和 Maron [2] 提供了大量有关该领域工作的参考资料。
与此相反，本文讨论的问题是数据独立性问题（应用程序和终端活动不受数据类型增长和数据表示变化的影响），以及某些类型的数据不一致性问题，这些问题即使在非演绎系统中也会变得麻烦.

第 1 节中描述的数据关系视图（或模型）似乎在多个方面优于目前在非推理系统中流行的图形或网络模型 [3, 4]。它提供了一种仅使用其自然结构描述数据的方法——也就是说，无需为机器表示目的而添加任何附加结构。因此，它为高级数据语言提供了基础，这种语言将在程序与机器表示和数据组织之间实现最大程度的独立性。

关系视图的另一个优点是它为处理关系的可导出性、冗余性和一致性奠定了坚实的基础——这些将在第 2 节中讨论。另一方面，网络模型引发了许多混淆，其中最严重的混淆是将连接的导出误认为是关系的导出（请参阅第 2 节中关于“连接陷阱”的注释）。

最后，关系视图允许更清楚地评估当前格式化数据系统的范围和逻辑限制，以及单个系统内竞争数据表示的相对优点（从逻辑角度来看）。本文各部分都引用了这种更清晰观点的例子。不讨论支持关系模型的系统的实现。

1.2. 现有系统中的数据依赖性

在最近开发的信息系统中，数据描述表的提供代表着朝着数据独立性目标迈出了一大步 [5, 6, 7]。这样的表有助于更改数据库中存储的数据表示的某些特征。然而，在不从逻辑上损害某些应用程序的情况下可以更改的数据表示特征种类仍然非常有限。此外，用户与之交互的数据模型仍然充斥着表示属性，特别是在数据集合（而不是单个项目）的表示方面。仍然需要消除的三种主要数据依赖关系是：排序依赖关系、索引依赖关系和访问路径依赖关系。在某些系统中，这些依赖关系彼此之间不能明显区分

1.2.1. 排序依赖性

数据库中的数据元素可以以多种方式存储，有些方式与排序无关，有些方式允许每个元素仅参与一种排序，而另一些方式允许每个元素参与多种排序。让我们考虑那些现有系统，它们要求或允许数据元素以至少一种全排序方式存储，该全排序与硬件确定的地址排序密切相关。例如，文件中有关零件的记录可能按零件序列号的升序存储。此类系统通常允许应用程序假设此类文件中记录的呈现顺序与存储的排序相同（或为其子排序）。如果出于某种原因需要用另一种排序方式替换该排序，那么利用文件存储排序的应用程序可能无法正常运行。对于通过指针实现的存储排序，也有类似的评论。

没有必要单独挑出任何系统作为例子，因为当今市场上所有知名的信息系统都没有明确区分显示顺序和存储顺序。要提供这种独立性，必须解决重大的实施问题。

1.2.2. 索引依赖性。

在格式化数据的上下文中，索引通常被认为是数据表示中纯粹面向性能的组件。它倾向于提高对查询和更新的响应，同时减慢对插入和删除的响应。从信息的角度来看，索引是数据表示的冗余组件。如果系统使用索引，并且要在数据库活动模式不断变化的环境中表现良好，那么可能需要能够不时创建和销毁索引。然后出现了一个问题：应用程序和终端活动能否在索引来来去去时保持不变？目前的格式化数据系统采用截然不同的索引方法。 TDMS [7] 无条件地为所有属性提供索引。当前发布的 IMS [5] 版本为每个文件提供了选择：完全不索引（分层顺序组织）或仅对主键进行索引（分层索引顺序组织）。在这两种情况下，用户的应用程序逻辑都不依赖于无条件提供的索引的存在。但是，IDS [8] 允许文件设计者选择要索引的属性，并通过附加链将索引合并到文件结构中。利用这些索引链的性能优势的应用程序必须通过名称引用这些链。如果这些链后来被删除，此类程序将无法正常运行。

1.2.3. 访问路径依赖性。

许多现有的格式化数据系统为用户提供了树结构文件或稍微更通用的数据网络模型。

如果树或网络的结构发生变化，为与这些系统协同工作而开发的应用程序往往会在逻辑上受到损害。下面是一个简单的例子。
假设数据库包含有关零件和项目的信息。对于每个零件，记录零件编号、零件名称、零件说明、现有数量和订单数量。对于每个项目，记录项目编号、项目名称和项目说明。每当项目使用某个零件时，还会记录该零件投入到给定项目的数量。假设系统要求用户或文件设计者以树形结构声明或定义数据。那么，可以采用上述信息中的任何一种层次结构（参见结构 1-5）。

现在，考虑打印出项目名称为“alpha”的项目中所使用的每个部件的部件编号、部件名称和承诺数量的问题。无论选择哪种可用的树形信息系统来解决此问题，都可以进行以下观察。如果针对此问题开发了一个程序 P，假设上述五种结构之一——即 P 不进行测试以确定哪种结构有效——那么 P 将在剩余结构中的至少三种上失败。更具体地说，如果 P 在结构 5 上成功，它将在所有其他结构上失败；如果 P 在结构 3 或 4 上成功，它将至少在 1、2 和 5 上失败；如果 P 在 1 或 2 上成功，它将至少在 3、4 和 5 上失败。每种情况下的原因都很简单。在没有测试来确定哪种结构有效的情况下，P 会失败，因为尝试执行对不存在的文件的引用（可用系统将此视为错误）或没有尝试执行对包含所需信息的文件的引用。
不相信的读者应该为这个简单的问题开发示例程序。

由于通常开发测试系统允许的所有树结构的应用程序是不切实际的，因此当需要更改结构时，这些程序就会失败。

为用户提供数据网络模型的系统也会遇到类似的困难。在树和网络情况下，用户（或其程序）都需要利用一组用户访问数据路径。这些路径是否与存储表示中的指针定义路径紧密对应并不重要——在 IDS 中，对应关系非常简单，在 TDMS 中则恰恰相反。无论存储的表示如何，其结果是终端活动和程序都依赖于用户访问路径的持续存在。

解决此问题的一个方法是采用以下策略：一旦定义了用户访问路径，它将不会过时，直到使用该路径的所有应用程序都过时为止。这种策略并不切实际，因为数据库用户社区的总体模型中的访问路径数量最终会变得非常大。

1.3. 数据的关系视图

这里使用术语“关系”的数学意义。给定集合 $S_1、S_2、… 、S_n$（不一定不同），如果 R 是一组 n 元组，每个 n 元组的第一个元素来自 $S_1$，第二个元素来自 $S_2$，依此类推，则 R 是这 n 个集合上的关系。我们将 $S_j$ 称为 R 的第 j 个域。如上所述，R 被称为度为 n。度为 1 的关系通常称为一元关系，度为 2 的关系称为二元关系，度为 3 的关系称为三元关系，度为 n 的关系称为 n 元关系。

出于解释的原因，我们将经常使用关系的数组表示，但必须记住，这种特定的表示并不是所阐述的关系观点的必要部分。表示 n 元关系 R 的数组具有以下属性：
(1) 每行代表 R 的 n 元组。
(2) 行的顺序无关紧要。
(3) 所有行都是不同的。
(4) 列的顺序很重要 - 它对应于定义 R 的域的顺序 $S_1、S_2、…、S_n$（但请参见下面关于域有序和域无序关系的注释）。
(5) 每列的重要性部分地通过用相应域的名称标记它来传达

图 1 中的示例说明了 4 度关系，称为供应，它反映了从指定供应商到指定项目的指定数量的在制品零件的发货情况。

有人可能会问：如果列是用相应域的名称标记的，那么列的顺序为什么重要呢？如图 2 中的示例所示，两列可能具有相同的标题（表示相同的域），但就关系而言具有不同的含义。所描绘的关系称为组件。它是一个三元关系，其前两个域称为零件，第三个域称为数量。组件 (x, y, z) 的含义是零件 x 是零件 y 的直接组件（或子组件），并且需要零件 x 的 z 个单元来组装零件 y 的一个单元。它是在零件爆炸问题中起着关键作用的关系

值得注意的是，现有的几个信息系统（主要是基于树形文件的信息系统）无法为具有两个或更多相同域的关系提供数据表示。当前版本的 IMS/360 [5] 就是此类系统的一个例子。

数据库中的全部数据可以看作是随时间变化的关系的集合。这些关系有各种程度。随着时间的推移，每个 n 元关系可能会插入额外的 n 元组、删除现有的 n 元组以及更改其现有 n 元组中的任意一个的组件

然而，在许多商业、政府和科学数据库中，一些关系的度数相当高（30 度并不罕见）。用户通常不必记住任何关系的域顺序（例如，关系供应中的订购供应商，然后是零件，然后是项目，然后是数量）。

因此，我们建议用户不要处理按域排序的关系，而是处理其无序域对应关系。2 为实现这一点，域必须至少在任何给定关系中唯一可识别，而无需使用位置。因此，当有两个或多个相同的域时，我们在每种情况下都要求域名由独特的角色名称限定，该角色名称用于标识该域在给定关系中扮演的角色。例如，在图 2 的关系组件中，第一个域部分可能由角色名称 sub 限定，第二个域部分可能由 super 限定，这样用户就可以处理关系组件及其域（sub.part super.part，数量），而无需考虑这些域之间的任何顺序。

总之，建议大多数用户应该与由随时间变化的关系（而不是关系）集合组成的数据关系模型进行交互。每个用户只需知道关系的名称及其域的名称（必要时角色限定）即可。3 甚至这些信息也可能由系统以菜单形式提供（受安全和隐私约束），以应用户请求。

通常，为数据库建立关系模型有很多种替代方法。为了讨论首选方法（或范式），我们必须首先介绍一些额外的概念（活动域、主键、外键、非简单域），并与信息系统编程中当前使用的术语建立一些联系。在本文的其余部分，我们不会费心区分关系和关系，除非明确说明会更有利。

考虑一个数据库的例子，其中包括与零件、项目和供应商有关的关系。一个称为零件的关系在以下域上定义：

(1)零件编号

(2)零件名称

(3)零件颜色

(4)零件重量

(5)现有数量

(6)订单数量

可能还有其他域。实际上，这些域中的每一个都是一个值池，其中的部分或全部可能在任何时刻都表示在数据库中。虽然可以想象，在某个时刻，所有零件颜色都存在，但所有可能的零件重量、零件名称和零件编号都存在的可能性不大。我们将在某个时刻表示的值集称为该时刻的活动域

通常，给定关系的一个域（或域的组合）具有唯一标识该关系的每个元素（n 元组）的值。这样的域（或组合）称为主键。在上面的例子中，零件编号是主键，而零件颜色不是。如果主键是简单域（不是组合）或组合，使得参与的简单域中没有一个在唯一标识每个元素方面是多余的，则主键是非冗余的。关系可能拥有多个非冗余主键。如果不同的零件始终被赋予不同的名称，则在示例中就是这种情况。每当关系具有两个或多个非冗余主键时，就会任意选择其中一个并称为该关系的主键。

一个常见的要求是关系的元素交叉引用同一关系的其他元素或不同关系的元素。键提供了一种面向用户的方法（但不是唯一的方法）来表达这种交叉引用。如果关系 R 的域（或域组合）不是 R 的主键，但其元素是某个关系 S 的主键的值（不排除 S 和 R 相同的可能性），则我们称其为外键。在图 1 的关系供应中，供应商、零件、项目的组合是主键，而这三个域单独来看都是外键。

在以前的工作中，人们倾向于将数据库中的数据视为由两部分组成，一部分由实体描述（例如，供应商描述）组成，另一部分由各种实体或实体类型之间的关系组成（例如，供应关系）。当任何关系中都可能有外键时，这种区别很难保持。在用户的关系模型中，做出这样的区分似乎没有任何好处（但是，当将关系概念应用于用户关系集的机器表示时，可能会有一些好处）。

到目前为止，我们讨论了在简单域上定义的关系的例子——这些域的元素是原子（不可分解）值。非原子值可以在关系框架内讨论。因此，一些域可能将关系作为元素。这些关系又可以在非简单域上定义，等等。

例如，定义关系雇员的域之一可能是薪资历史。薪资历史域的一个元素是在域日期和域薪资上定义的二元关系。薪资历史域是所有此类二元关系的集合。在任何时刻，数据库中薪资历史关系的实例数与雇员数一样多。相比之下，雇员关系只有一个实例

当前数据库术语中的术语属性和重复组分别大致类似于简单域和非简单域。当前术语中的许多混淆是由于未能区分类型和实例（如“记录”）以及数据的用户模型组件与机器表示对应物（再次引用“记录”作为示例）。

1.4 范式

域都是简单的关系可以在存储中用上面讨论的二维列同质数组表示。对于具有一个或多个非简单域的关系，需要一些更复杂的数据结构。由于这个原因（以及下面要引用的其他原因），消除非简单域的可能性似乎值得研究。4 事实上，有一个非常简单的消除过程，我们称之为规范化。

例如，考虑图 3 (a) 中展示的关系集合。工作经历和子女是关系雇员的非简单域。工资历史是关系工作历史的非简单域。图 3 (a) 中的树显示了非简单域的这些相互关系

规范化过程如下。从树顶部的关系开始，取其主键，并通过插入此主键域或域组合来扩展每个直接下属关系。

每个扩展关系的主键由扩展前的主键加上从父关系向下复制的主键组成。现在，从父关系中删除所有非简单域，删除树的顶部节点，并对每个剩余子树重复相同的操作序列。

规范化图 3 (a) 中的关系集合的结果是图 3 (b) 中的集合。每个关系的主键都以斜体显示，以显示这些键如何通过规范化进行扩展。

如果要应用上述规范化，则非规范化的关系集合必须满足以下条件：

（1）非简单域的相互关系图是树的集合。
（2）没有主键具有非简单的组成域。

作者不知道任何需要放宽这些条件的应用程序。规范化类型的进一步操作是可能的。本文不讨论这些。

当所有关系都以规范形式转换时，数组表示的简单性变得可行，这不仅有利于存储目的，而且有利于在使用不同数据表示的系统之间进行批量数据通信。通信形式将是数组表示的适当压缩版本，并具有以下优点：

（1）它将没有指针（地址值或位移值）。
（2）它将避免对哈希寻址方案的所有依赖。
（3）它不包含索引或排序列表

如果用户的关系模型是按照标准形式建立的，那么数据库中数据项的名称可以采用比其他情况更简单的形式。通用名称可以采用诸如 $R (g).r.d$ 的形式，其中 R 是关系名称；g 是代标识符（可选）；r 是角色名称（可选）；d 是域名。
由于只有当给定关系的几代存在或预计存在时才需要 g，而只有当关系 R 有两个或多个名为 d 的域时才需要 r，因此简单形式 R.d 通常是足够的

1.5. 一些语言方面

如上所述，采用关系数据模型允许开发基于应用谓词演算的通用数据子语言。如果关系集合是范式，则一阶谓词演算就足够了。这种语言将为所有其他提议的数据语言提供语言能力的标准，并且本身将成为嵌入（经过适当的语法修改）各种宿主语言（编程、命令或面向问题）的有力候选者。虽然本文的目的不是详细描述这种语言，但它的显著特征如下。

让我们用 R 表示数据子语言，用 H 表示宿主语言。R 允许声明关系及其域。每个关系声明都标识该关系的主键。已声明的关系被添加到系统目录中，供具有适当授权的用户社区的任何成员使用。H 允许支持声明，这些声明可能不是永久的，表明这些关系在存储中是如何表示的。 R 允许从数据库中检索任何数据子集。对此类检索请求的操作受到安全约束。

数据子语言的通用性在于其描述能力（而非计算能力）。在大型数据库中，每个数据子集都具有大量可能的（且合理的）描述，即使我们假设（正如我们所假设的）系统只能访问一组有限的函数子例程来限定要检索的数据。因此，可用于集合规范的限定表达式类必须具有应用谓词演算的合式公式类的描述能力。众所周知，为了保持这种描述能力，没有必要（无论选择哪种语法）表达所选谓词演算的每个公式。例如，只要前缀范式中的公式就足够了 [9]。

检索语句的限定或其他部分可能需要算术函数。此类函数可以在 H 中定义并在 R 中调用。

如此指定的集合可能仅用于查询目的，也可能被保留以备可能发生的更改。插入采取向声明的关系添加新元素的形式，而不考虑其机器表示中可能存在的任何顺序。对社区（而不是单个用户或子社区）有效的删除采取从声明的关系中删除元素的形式。如果在 R 中声明了指定关系之间的删除和更新依赖关系，则某些删除和更新可能会由其他删除和更新触发。对数据采取的观点对用于检索数据的语言的一个重要影响是数据元素和集合的命名。上一节讨论了这方面的一些方面。使用通常的网络视图，用户通常会被创造和使用比绝对必要的更多的关系名称所困扰，因为名称与路径（或路径类型）相关联，而不是与关系相关联。一旦用户知道存储了某个关系，他将期望能够使用其参数作为“已知”和其余参数作为“未知”的任意组合来利用它，因为信息（如 Everest）就在那里。这是一个系统特性（许多当前信息系统都缺少这个特性），我们将其称为（逻辑上）对称关系利用。当然，性能上的对称性是不可预期的。

为了支持对称利用单个二元关系，需要两条有向路径。对于 n 度关系，要命名和控制的路径数是 n 阶乘。

同样，如果采用关系视图，其中每个 n 元关系（n > 2）都必须由用户表示为仅涉及二元关系的嵌套表达式（例如，参见 Feldman 的 LEAP 系统 [10]），则必须创造 $2n -1$ 个名称，而不是仅使用 1.2 节中所述的直接 n 元表示法创造 $n + 1$ 个名称。例如，图 1 中的 4-ary 关系 supply 在 n 元表示法中需要 5 个名称，在嵌套二元表示法中将以 $P（供应商，Q（零件，R（项目，数量）））$的形式表示，因此使用 7 个名称。

这种表达方式的另一个缺点是它的不对称性。虽然这种不对称性并不妨碍对称利用，但它肯定会使用户表达某些查询基础非常困难（例如，考虑通过 Q 和 R 查询与某些给定项目相关的零件和数量）。

1.6. 可表达、命名和存储关系

与数据库相关联的是两个关系集合：命名集和可表达集。命名集是用户社区可以通过简单名称（或标识符）识别的所有关系的集合。

当适当授权的用户声明 R 时，关系 R 获得命名集合的成员资格；当适当授权的用户取消 R 的声明时，它失去成员资格。

可表达集是可以通过数据语言中的表达式指定的关系的总集合。这些表达式由命名集中关系的简单名称、世代、角色和域的名称、逻辑连接词构成；谓词演算的量词；6 和某些常量关系符号，如 =、>。

命名集是可表达集的子集——通常是一个非常小的子集。

由于命名集中的一些关系可能是该集合中其他关系的时间无关组合，因此考虑将定义这些时间无关约束的语句集合与命名集相关联是很有用的。

我们将推迟对此的进一步讨论，直到我们介绍了几个关系操作（参见第 2 节）。
数据系统的设计人员面临的一个主要问题是确定要支持的存储表示类别，该系统要为其用户提供关系模型。理想情况下，允许的数据表示的多样性应该刚好足以覆盖整个安装集合的性能要求范围。种类太多会导致不必要的存储开销和对当前有效结构的描述的不断重新解释。

对于任何选定的存储表示类型，数据系统必须提供一种手段，将以关系模型的数据语言表达的用户请求转换为当前存储表示上的相应且高效的操作。对于高级数据语言来说，这是一个具有挑战性的设计问题。然而，这是一个必须解决的问题——随着越来越多的用户同时访问大型数据库，提供高效响应和吞吐量的责任从单个用户转移到数据系统。

2. 冗余和一致性

2.1. 关系上的操作

由于关系是集合，因此所有常见的集合操作都适用于它们。但是，结果可能不是关系；例如，二元关系和三元关系的并集不是关系。

下面讨论的操作专门用于关系。引入这些操作是因为它们在从其他关系派生关系方面起着关键作用。它们的主要应用是在非推理信息系统（不提供逻辑推理服务的系统）中，尽管添加此类服务并不一定会破坏它们的适用性。

大多数用户不会直接关注这些操作。但是，信息系统设计人员和关注数据库控制的人员应该非常熟悉它们。

2.1.1. 排列。

二元关系具有包含两列的数组表示。交换这些列可得出逆关系。更一般地，如果对 n 元关系的列应用排列，则结果关系被称为给定关系的排列。例如，如果我们包括保持列顺序不变的身份排列，则图 1 中的关系供应有 4！–24 种排列。
由于用户的关系模型由关系集合（域无序关系）组成，因此排列与单独考虑的这种模型无关。

但是，它与模型的存储表示的考虑有关。在提供关系对称利用的系统中，存储关系可回答的查询集与该关系的任何排列可回答的查询集相同。虽然从逻辑上讲，没有必要同时存储关系及其某些排列，但出于性能考虑，建议这样做

2.1.2. 投影。

假设现在我们选择一个关系的某些列（删除其他列），然后从结果数组中删除行中的任何重复项。最终数组表示一个关系，该关系被称为给定关系的投影。

选择运算符 $\pi$ 用于获得任何所需的排列、投影或两个操作的组合。因此，如果 L 是 k 索引列表 $ L = i_1,i_2, • • • , i_k $并且 R 是 n 元关系 (n > k)，则 ${\pi}_L (R)$ 是 k 元关系，其第 j 列是 $R (j = 1, 2, … , k)$ 的列 $i_j$，只是结果行中的重复项被删除。考虑图 1 的关系供应。图 4 展示了此关系的排列投影。请注意，在这种特殊情况下，投影的 n 元组少于它所衍生的关系

2.1.3. 连接

假设我们给定两个二元关系，它们有一些共同的定义域。在什么情况下我们可以将这些关系组合起来形成三元关系，以保留给定关系中的所有信息？

图 5 中的示例显示了两个关系 R、S，它们可以连接且不会丢失信息，而图 6 显示了 R 与 S 的连接。如果存在三元关系 U 使得 $\pi_{12}(U) = R$ 且 $\pi_{23}(U) = S$，则二元关系 R 可以与二元关系 S 连接。任何这样的三元关系称为 R 与 S 的连接。如果 R、S 是二元关系，使得 $π_2(R) = π_1(S)$，则 R 可以与 S 连接。

在这种情况下始终存在的一个连接是 R 与 S 的自然连接，其定义为$ RS = {(a,b,c):R(a,b) \and S(b,c)}$，其中如果 (a, b) 是 R 的成员，则 R (a, b) 的值为 true，对于 S (b, c) 也是如此。立即得出 $\pi_{12} (RS) = R$ 且 $\pi_{23} (R*S) = S$。

请注意，图 6 中所示的连接是图 5 中 R 与 S 的自然连接。图 7 中显示了另一个连接。

检查这些关系会发现域部分（要进行连接的域）的一个元素（元素 1），其属性是它在 R 和 S 下都拥有多个关系。正是这个元素产生了多个连接。连接域中的这种元素被称为 R 与 S 连接的歧义点。

如果 $\pi_{21} (R)$ 或 S 是函数，则在连接 R 和 S 时不会出现歧义。在这种情况下，R 和 S 的自然连接是 R 和 S 的唯一连接。请注意，重申“R 和 S”的限定是必要的，因为 S 可能可以与 R 连接（以及 R 和 S 连接），并且这种连接将是一个完全独立的考虑。在图 5 中，关系$ R、\pi_{21} (R)、S、\pi_{21} (S)$ 都不是函数。

R 和 S 连接中的歧义有时可以通过其他关系来解决。假设我们得到或可以从独立于 R 和 S 的来源推导出域 project 和 supplier 上的关系 T，具有以下属性：
$$
\left( 1 \right) \ \pi _1\left( T \right) =\pi _2\left( S \right) ,
$$
$$
\left( 2 \right) ,,\pi _2\left( T \right) =\pi _1\left( R \right) ,
$$
$$
\left( 3 \right) \ T\left( j,s \right) \rightarrow \exists p\left( R\left( S,p \right) \land S\left( p,j \right) \right) ,
$$
$$
\left( 4 \right) ,,R\left( s,p \right) \rightarrow \exists j\left( S\left( p,j \right) \land T\left( j,s \right) \right) ,
$$
$$
\left( 5 \right) ,,S\left( p,j \right) \rightarrow \exists s\left( T\left( j,s \right) \land R\left( s,p \right) \right) ,
$$

那么我们可以形成 R、S、T 的三向连接；也就是说，三元关系如下：
$$
\pi _{12}\left( U \right) =R,\ \pi _{23}\left( U \right) =S,\ \pi _{31}\left( U \right) =T
$$
这种连接将被称为循环 3 连接，以区别于线性 3 连接，后者是四元关系 V
$$
\pi _{12}\left( V \right) =R,\ \pi _{23}\left( V \right) =S,\ \pi _{34}\left( V \right) =T
$$
虽然可能存在多个循环 3 连接（参见图 8、9 的示例），但发生这种情况的情况需要更严格的约束

比多个 2-连接更复杂。具体来说，关系 R、S、T 必须具有关于连接 R 与 S（例如点 x）、S 与 T（例如y ）以及 T 与 R（例如 z）的歧义点，而且，y 必须是 S 下 x 的亲属，z 必须是 T 下 y 的亲属，x 必须是 R 下 z 的亲属。请注意，在图 8 中，点 $x = a; y = d; z = 2 $具有此属性

三个二元关系 R、S、T 的自然线性 3 连接由以下公式给出
$$
\pi _{12}\left( U \right) =R,\ \pi _{23}\left( U \right) =S,\ \pi _{31}\left( U \right) =T
$$
其中左侧不需要括号，因为自然的 2 连接 (*) 是结合的。为了获得循环对应项，我们引入运算符 .y，它通过将 n 度关系的两端连接在一起，从 n 度关系生成 n-ary关系。因此，如果 R 是 n 元关系 (n > 2)，则 R 的连接由以下等式定义
$$
\pi _{12}\left( U \right) =R,\ \pi _{23}\left( U \right) =S,\ \pi _{31}\left( U \right) =T
$$
将线性和循环 3 连接及其自然对应概念扩展到 n 个二元关系（其中 n > 3）的连接是显而易见的。不过，关于不一定是二元的关系的连接，可能还需要说几句话。考虑两个关系 R（度 r）、S（度 s）的情况，它们要在它们的域 p 上连接（p < r，p < s）。为简单起见，假设这 p 个域是 R 的 r 个域中的最后一个 p，以及 S 的 s 个域中的第一个 p。如果不是这样，我们总是可以应用适当的排列来实现这一点。现在，取 R 的前 r-p 个域的笛卡尔积，并将这个新域称为 A。取 R 的最后 p 个域的笛卡尔积，并将其称为 B。取 S 的最后 s-p 个域的笛卡尔积，并将其称为 C。

我们可以将 R 视为域 A、B 上的二元关系。同样，我们可以将 S 视为域 B、C 上的二元关系。线性和循环 3 连接的概念现在可直接应用。可以对不同程度的 n 个关系的线性和循环 n 连接采取类似的方法

2.1.4. 组合

读者可能熟悉组合概念在函数中的应用。我们将讨论该概念的泛化，并首先将其应用于二元关系。我们对组合和可组合性的定义非常直接地基于上面给出的连接和可连接性的定义。

假设我们给定两个关系 R、S。如果存在 R 与 S 的连接 U 使得 $T = \pi_{13} (U)$，则 T 是 R 与 S 的组合。因此，当且仅当两个关系可连接时，它们才是可组合的。但是，R 与 S 存在多个连接并不意味着 R 与 S 存在多个组合

与 R 与 S 的自然连接相对应的是 R 与 S 的自然组合，其定义如下
$$
R \cdot S = \pi_{13}(R*S)
$$
以图 5 中的关系 R、S 为例，它们的自然组合如图 10 所示，而另一种组合如图 11 所示（源自图 7 所示的连接）。

当存在两个或多个连接时，不同组合的数量可能少至一个，也可能多至与不同连接的数量一样多。图 12 显示了两个关系的示例，它们具有多个连接但只有一个组合。
请注意，由于通过点 a、b、d、e 建立了明确的关联，因此在将 R 与 S 组合时，点 c 的歧义性会消失。

将组合扩展到不一定是二元的（并且可能具有不同程度）关系对，其模式与将成对连接扩展到此类关系的模式相同。

由于缺乏对关系组合的理解，一些系统设计人员陷入了所谓的连接陷阱。可以用以下示例来描述此陷阱。假设每个供应商描述都通过指向该供应商提供的每个零件的描述的指针链接，并且每个零件描述同样链接到使用该零件的每个项目的描述。现在得出一个结论，该结论通常是错误的：即，如果从给定供应商通过他提供的零件到使用这些零件的项目遵循所有可能的路径，则将获得该供应商提供的所有项目的有效集合。这样的结论仅在非常特殊的情况下才是正确的，即项目和供应商之间的目标关系实际上是其他两个关系的自然组合——我们通常必须添加短语“永远”，因为这通常隐含在有关路径跟踪技术的权利要求中。

2.1.5. 限制。

关系的子集是关系。关系 S 作用于关系 R 以生成 R 的子集的一种方式是通过对 R 进行 S 操作限制。此操作是将函数限制为其域的子集的推广，定义如下。

假设 L, M 为等长索引列表，且$ L = i_1,i_2, … i_k, M = j_1,j_2,…,j_k，$其中 k 小于等于 R 的度数，k 小于等于 S 的度数。则 L, M 对 R 的限制（记为 $R_{L|M}S$）为 R 的最大子集 R’，且
$$
\pi_{L}(R’)=\pi_M(S)
$$
仅当对于所有 $h = 1, 2, • • •, k$，$ \pi_{i_h}(R)$ 中的元素与 $\pi_{j_h} (S)$ 中的元素之间相等时，该运算才有定义。

图 13 中的三个关系 R、S、R’ 满足方程 $R’=R_{(2,3)|(1.2)}S$。

我们现在可以考虑这些操作在关系上的各种应用。

2.2. 冗余

命名关系集中的冗余必须与存储表示集中的冗余区分开来。我们主要关注前者。
首先，我们需要一个精确的关系可导性概念。

假设 $\theta$是关系操作的集合，每个操作都具有从其操作数产生唯一关系的属性（因此自然连接是合格的，但连接不是）。如果存在来自集合 0 的操作序列，该序列在所有时间内从 S 的成员产生 R，则关系 R 可以从关系集 S 中 $\theta-derivable$ 导出。
之所以使用“所有时间”一词，是因为我们正在处理随时间变化的关系，我们感兴趣的是可导性，该可导性在相当长的一段时间内成立。对于非推理系统中的命名关系集，似乎适当的集合 $\theta_1$ 包含以下操作：投影、自然连接、绑定和限制。
置换无关紧要，自然组合也无需包括在内，因为它可以通过自然连接然后投影获得。对于存储的表示集，足够的操作集合 ~ 将包括置换和与子集和合并关系以及排序和连接其元素有关的附加操作。

2.2.1. 强冗余

如果一组关系至少包含一个关系，该关系具有可从该集合中其他关系投影导出的投影，则该组关系为强冗余。以下两个示例旨在解释为什么以这种方式定义强冗余，并展示其实际用途。在第一个示例中，关系集合仅由以下关系组成：

以 serial# 作为主键，manager# 作为外键。我们用 ,~ 表示活动域，并假设

对于所有时间 t。在这种情况下，冗余是显而易见的：域管理器名称是不必要的。为了看出它是如上定义的强冗余，我们观察到
$$
\pi_{34}(employee)=\pi_{12}(employee)_{1|1}\pi_3(employee)
$$
在第二个示例中，关系集合包括关系 S（使用主键 s# 描述供应商）、关系 D（使用主键 d# 描述部门）、关系 J（使用主键 j# 描述项目）以及以下关系：

其中，在每种情况下，表示除 s#、d#、j# 之外的域。假设已知以下条件 C 与时间无关：供应商 s 供应部门 d（关系 P），当且仅当供应商 s 供应某个项目 j（关系 Q），而 d 被分配到该项目 j（关系 R）。然后，我们可以写出方程
$$
\pi_{12}(P)=\pi_{12}(Q) \cdot \pi_{21}(R)
$$
从而表现出很强的冗余度。

命名关系集中存在强冗余的一个重要原因是用户的便利性。一个特殊的例子是保留命名集中的半过时关系，以便通过名称引用它们的旧程序可以继续正确运行。了解命名集中存在强冗余使系统或数据库管理员在选择存储表示时有更大的自由度，以更有效地应对当前流量。如果命名集中的强冗余直接反映在存储集中的强冗余中（或者如果将其他强冗余引入存储集中），那么一般来说，会消耗额外的存储空间和更新时间，从而可能减少某些查询的查询时间和中央处理单元的负载。

2.2.2. 弱冗余

可能存在第二种类型的冗余。与强冗余相反，它不以方程式为特征。如果关系集合包含一个关系，该关系具有一个投影，该投影不能从其他成员中导出，但始终是集合中其他关系投影的某个连接的投影，则该关系集合是弱冗余的。

我们可以通过采用第二个强冗余示例（上面引用）来展示弱冗余，现在假设条件 C 并不总是成立。关系 $\pi_{12} (P)、\pi_{12} (Q)、\pi_{12} (R)$ 是复杂的 l° 关系，在任意两个关系的潜在连接中，可能会不时出现歧义点。在这种情况下，它们都不能从其他两个关系中推导出来。然而，它们之间确实存在约束，因为每个约束都是它们三个的某个循环连接的投影。弱冗余之一可以用以下语句来描述：对于所有时间，$\pi_{12} (P)$ 都是$\pi_{12} (Q)$ 与 $\pi_{21} (R)$ 的某种组合。所讨论的组合在某个时刻可能是自然的，而在另一个时刻可能是非自然的。

一般而言，弱冗余是用户群体逻辑需求所固有的。系统或数据库管理员无法移除它们。如果它们出现，它们会同时出现在命名集和存储的表示集中。

2.3. 一致性

每当命名关系集在任何意义上是冗余的，我们将与该集合关联一组语句，这些语句定义了成员关系之间独立于时间的所有冗余。如果信息系统缺乏（而且很可能缺乏）关于每个命名关系的详细语义信息，它就无法推断出适用于命名集的冗余。它可能会在一段时间内尝试引入冗余，但这种尝试可能会出错

给定一个随时间变化的关系集合 C、一个相关的约束语句集 Z 和一个 C 的瞬时值 V，我们将根据 V 是否满足 Z 来称状态 (C, Z, V) 是一致的还是不一致的。
例如，给定存储的关系 R、S、T 和约束语句$\pi_{12}(T)$ 是 $\pi_{12}(R)$ 与 $\pi_{12} (S)$ 的组合”，我们可以不时地检查存储的 R、S、T 的值是否满足此约束。进行此检查的算法将检查 R、S、T 的前两列（无论它们在系统中以何种方式表示），并确定是否

在对一系列关系进行即时快照时，存在一些实际问题（我们在此不讨论），其中一些关系可能非常大且高度可变

值得注意的是，如上定义的一致性是数据库瞬时状态的属性，与该状态如何产生无关。因此，具体而言，不会根据用户是否因疏忽或故意而产生不一致做出区分。通过一个简单的例子，我们将展示这种（可能非常规的）一致性方法的合理性。

假设命名集合 C 包括第 2.2 节示例中的关系 $S、J、D、P、Q、R$，并且 $P、Q、R$ 具有其中描述的强冗余或弱冗余（在现在考虑的特定情况下，发生哪种冗余并不重要）。此外，假设在某个时间 t，数据库状态一致且不包含项目 j，因此供应商 2 供应项目 j，并且 j 被分配给部门 5。因此，$\pi_{12}(P)$中没有元素 (2, 5)。现在，用户通过将某个适当的元素插入 P 中，将元素 (2, 5) 引入 $\pi_{12}(P)$。数据库状态现在不一致。
如果输入 (2, 5) 正确，并且确实存在项目 j，供应商 2 供应 j，并且 j 被分配给部门 5，则不一致可能是由于疏忽造成的。在这种情况下，用户很可能打算在不久的将来将元素插入 Q 和 R，这将导致将 (2, j) 引入 $\pi_{12}(Q)$ 和将 (5, j) 引入 $\pi_{12}(Q)$。另一方面，输入 (2, 5) 可能有误。用户可能打算将其他元素插入 P——插入该元素会将一致状态转变为一致状态。关键在于，系统通常无法在不询问其环境（可能是造成不一致的用户）的情况下解决这个问题

当然，系统可以通过多种方式检测不一致并做出响应。在一种方法中，系统会在插入、删除或密钥更新时检查可能的不一致。当然，这种检查会减慢这些操作的速度。如果产生了不一致，则会在内部记录详细信息，如果在合理的时间间隔内未纠正，则会通知用户或负责数据安全性和完整性的人员。另一种方法是每天一次或更少地以批处理操作的形式进行一致性检查。如果系统维护所有状态变化交易的日志，则可以追踪检查时数据库中仍存在不一致的输入。如果发生的非暂时性不一致很少，后一种方法肯定会更好。