A Relational Model of Data for Large Shared Data Banks

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 数据的关系视图

本文中使用的术语关系（relation）取其公认的数学含义。给定集合 S₁, S₂, …, S_n（不必互异），若 R 是一个 n 元组集合，其中每个元组的第一个元素取自 S₁，第二个元素取自 S₂，依此类推，则 R 是这 n 个集合上的一个关系。^[1] 我们将 S_j 称为 R 的第 j 个域（domain）。按上述定义，R 的度为 n。度为 1 的关系通常称为一元关系，度为 2 的称为二元关系，度为 3 的称为三元关系，度为 n 的称为 n 元关系。

为便于说明，我们将经常使用关系的数组表示，但必须记住，这种特定表示并非所述关系视图的本质部分。表示 n 元关系 R 的数组具有以下性质：

1. 每行代表 R 的一个 n 元组。
2. 行的顺序无关紧要。
3. 所有行互不相同。
4. 列的顺序是有意义的——它对应于定义 R 的域的顺序 S₁, S₂, …, S_n（但请参见下文关于域有序与域无序关系的讨论）。
5. 每列的含义部分通过用相应域的名称标记该列来传达。

图 1 中的示例展示了一个度为 4 的关系，名为 supply，它反映了指定供应商向指定项目供应指定零件的在途发货量。

有人可能会问：如果列用相应域的名称标记，列的顺序为何重要？如图 2 中的例子所示，两列可能有相同的标题（表示相同的域），但对于该关系具有不同的含义。图中所示的关系名为 component，它是一个三元关系，其前两个域都称为 part，第三个域称为 quantity。component(x, y, z) 的含义是：零件 x 是零件 y 的直接组件（或子装配件），组装一单位零件 y 需要 z 单位的零件 x。这是一个在零件分解问题中起关键作用的关系。

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

数据银行中的全部数据可视为时变关系的集合。这些关系具有不同的度。随着时间的推移，每个 n 元关系可能会经历额外 n 元组的插入、现有 n 元组的删除以及任何现有 n 元组分量的修改。

然而，在许多商业、政府和科学数据银行中，某些关系的度相当高（度为 30 并不罕见）。用户通常不应被迫记住任何关系的域排序（例如，supply 关系中的供应商→零件→项目→数量的顺序）。因此，我们建议用户处理的是域无序关系（relationship），而非域有序关系（relation）。^[2] 为实现这一点，域必须至少在给定关系内能够唯一标识，而不依赖于位置。因此，当存在两个或更多相同域时，我们要求在每个情况下用具有区分性的角色名（role name）来限定域名，以标识该域在给定关系中所扮演的角色。例如，在图 2 的 component 关系中，第一个域 part 可以用角色名 sub 来限定，第二个用 super，这样用户就可以处理 component 关系及其域——sub.part、super.part、quantity——而无需关心这些域之间的任何顺序。

综上所述，建议大多数用户与一个关系的数据模型进行交互，该模型由时变关系（relationship）的集合组成。每个用户对任何关系只需了解其名称及其域名（必要时加上角色限定）。^[3] 即便是这些信息，系统也可以根据用户请求以菜单形式提供（受安全和隐私约束的制约）。

为一个数据银行建立关系模型通常有多种可选的方法。为了讨论一种优选的方法（或范式），我们必须首先引入一些额外概念（活动域、主键、外键、非简单域），并与当前信息系统编程中使用的术语建立联系。在本文的其余部分，除非明确区分有意义，否则我们不再区分 relation 和 relationship。

考虑一个包含零件、项目和供应商相关关系的数据银行示例。一个名为 part 的关系定义在以下域上：

1. 零件编号（part number）
2. 零件名称（part name）
3. 零件颜色（part color）
4. 零件重量（part weight）
5. 在手数量（quantity on hand）
6. 订购数量（quantity on order）

可能还有其他域。每个域实际上是一个值池，在任何时刻某些值或全部值可能被表示在数据银行中。虽然在某个时刻所有零件颜色都可能存在，但所有可能的零件重量、零件名称和零件编号未必都存在。我们将某个时刻所表示的值集合称为该时刻的活动域（active domain）。

通常，给定关系的某个域（或域的组合）上的值能够唯一标识该关系中的每个元素（n 元组）。这样的域（或组合）称为主键（primary key）。在上例中，零件编号是主键，而零件颜色则不是。如果主键要么是一个简单域（而非组合域），要么是一个其中没有参与简单域是多余的组合，则该主键是非冗余的。一个关系可以拥有多个非冗余主键。如果不同的零件总是被赋予不同的名称，那么在上例中就会出现这种情况。当一个关系拥有两个或更多非冗余主键时，任意选择其中一个称为该关系的主键。

一个常见需求是关系中的元素交叉引用同一关系中的其他元素或不同关系中的元素。键提供了一种面向用户（但并非唯一）的表达此类交叉引用的手段。如果关系 R 的某个域（或域的组合）不是 R 的主键，而是某个关系 S 的主键（S 和 R 相同的可能性不排除），则称该域（或组合）为外键（foreign key）。在图 1 的 supply 关系中，供应商、零件、项目的组合是主键，而这三个域各自单独看都是外键。

在以往的工作中，存在一种强烈的倾向，即把数据银行中的数据视为由两部分组成：一部分包含实体描述（例如供应商的描述），另一部分包含各实体或实体类型之间的关系（例如供应关系）。当任何关系中都可能存在外键时，这种区分很难维护。在用户的关系模型中，做出这种区分似乎没有优势（然而，当将关系概念应用于用户关系集合的机器表示时，可能存在一些优势）。

到目前为止，我们讨论了定义在简单域（simple domain）上的关系的例子——简单域的元素是原子（不可分解）值。非原子值也可以在关系框架内讨论。因此，某些域可能以关系作为其元素。这些关系又可能定义在非简单域上，依此类推。例如，定义 employee 关系的域之一可能是 salary history。该域的一个元素是定义在 date 域和 salary 域上的二元关系。在任何时刻，数据银行中 salary history 关系的实例数量与员工数量相同。与此相反，employee 关系只有一个实例。

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

1.4 范式（Normal Form）

一个所有域都是简单域的关系可以用上述二维列同质数组在存储中表示。对于具有一个或多个非简单域的关系，则需要更复杂的数据结构。出于这个原因（以及下文将提到的其他原因），消除非简单域的可能性值得研究。^[4] 事实上，存在一种非常简单的消除过程，我们称之为规范化（normalization）。

考虑图 3(a) 中展示的关系集合。在 employee 关系中，jobhistory 和 children 是非简单域。在 jobhistory 关系中，salaryhistory 是非简单域。图 3(a) 中的树仅展示了这些非简单域的相互关系。

employee (man#, name, birthdate, jobhistory, children)
  |
  +---- jobhistory (jobdate, title, salaryhistory)
  |        |
  |        +---- salaryhistory (salarydate, salary)
  |
  +---- children (childname, birthyear)
  

规范化的过程如下：从树的顶端关系开始，取其主键，然后扩展每个直接下级关系，将主键域或域组合插入其中。每个扩展后的关系的主键由扩展前的主键加上从父关系复制下来的主键组成。然后，从父关系中删除所有非简单域，移除树的顶部节点，并在每个剩余子树上重复相同的操作序列。

将图 3(a) 中的关系集合规范化后，得到图 3(b) 中的集合。每个关系的主键以斜体显示，以展示规范化的过程中键的扩展方式。

employee' (man#, name, birthdate)
jobhistory' (man#, jobdate, title)
salaryhistory' (man#, jobdate, salarydate, salary)
children' (man#, childname, birthyear)
  

要使上述规范化可应用，未规范化的关系集合必须满足以下条件：

1. 非简单域之间相互关系的图是一组树（tree）。
2. 没有主键的组成域是非简单的。

据作者所知，没有应用场景需要放宽这些条件。还有其他规范化类型的操作是可能的，但本文不予讨论。

当所有关系都被转化为范式时，数组表示的简洁性不仅对存储目的而言是一种优势，也对使用截然不同数据表示的系统之间传输批量数据而言是一种优势。通信形式将是数组表示的适当压缩版本，并具有以下优势：

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

如果用户的关系模型按范式建立，数据银行中的数据项名称可以比否则更简单。通用名称的形式如下：

其中 R 是关系名；g 是代标识符（可选）；r 是角色名（可选）；d 是域名。由于 g 仅在给定关系有多个代存在或预期存在时才需要，而 r 仅在关系 R 有两个或更多名为 d 的域时才需要，因此简单形式 R.d 通常就足够了。

1.5 若干语言学方面

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

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

数据子语言的通用性在于其描述能力（而非计算能力）。在大型数据银行中，每组数据都有大量可能（且合理）的描述，即使我们假设（正如我们所假设的那样）系统只能访问有限的功能子程序集用于限定要检索的数据。因此，可以用于集合规范的限定表达式的类别必须具有应用谓词演算中合式公式（well-formed formula）类的描述能力。众所周知，要保留这种描述能力，并不需要（以所选择的任何语法）表达所选谓词演算的每一个公式。例如，仅表达前束范式（prenex normal form）中的公式就足够了[9]。

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

如此指定的集合可以仅出于查询目的被取出，也可以被保留以备可能的更改。插入操作以向声明的关系中添加新元素的形式进行，而不考虑其机器表示中可能存在的任何顺序。删除操作（对整个社区而非单个用户或子社区有效）以从声明的关系中移除元素的形式进行。如果在 R 中声明了指定关系之间的删除和更新依赖，则某些删除和更新可能由其他操作触发。

采用的数据视图对检索所用语言的一个重要影响体现在数据元素和集合的命名上。这方面的一些内容已在上一节中讨论过。在通常的网络视图中，用户往往被迫创制和使用比绝对必要的更多的关系名，因为名称与路径（或路径类型）关联，而非与关系关联。

一旦用户意识到某个关系已存储，他将期望能够以对称方式利用它——将它的任意参数组合作为"已知"，其余参数作为"未知"——因为信息（像珠穆朗玛峰一样）就在那里。这是一个系统特性（许多当前信息系统中缺失的特性），我们将其称为（逻辑上）对称地利用关系（symmetric exploitation of relations）。当然，性能上的对称是不期望的。

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

此外，如果采用一种关系视图，其中每个 n 元关系（n > 2）都必须由用户表达为仅涉及二元关系的嵌套表达式（例如 Feldman 的 LEAP 系统[10]），那么需要创制 2n − 1 个名称，而非使用如第 1.2 节所述的直接 n 元记法只需 n + 1 个名称。例如，图 1 中的四元关系 supply 在 n 元记法中需要 5 个名称，而在嵌套二元记法中将被表示为：

并因此使用了 7 个名称。

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

1.6 可表达关系、命名关系与存储关系

与数据银行相关的有两类关系集合：命名集（named set）和可表达集（expressible set）。命名集是用户社区可以通过简单名称（或标识符）识别的所有那些关系的集合。当一个适当授权的用户声明 R 时，关系 R 就获得了命名集的成员资格；当一个适当授权的用户取消 R 的声明时，它就失去了该成员资格。

可表达集是可以通过数据语言中的表达式指定的关系的总集合。此类表达式由以下元素构造而成：命名集中关系的简单名称；代名、角色名和域名；逻辑连接词；谓词演算的量词；^[6] 以及某些常量关系符号，如 =、>。命名集是可表达集的子集——通常是非常小的子集。

由于命名集中的某些关系可能是该集合中其他关系的与时间无关的组合，因此将一组定义这些与时间无关约束的语句与该命名集关联是很有用的。在介绍关系的若干操作之后（见第 2 节），我们再进一步讨论这一点。

设计支持用户关系模型的数据系统所面临的主要问题之一，是确定要支持的存储表示类别。理想情况下，允许的数据表示种类应恰好足以覆盖所有安装的总体性能需求范围。种类过多会导致不必要的存储开销和持续的结构描述重新解释。种类过少则会导致常见事务的性能不佳。

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

2. 冗余与一致性

2.1 关系上的操作

由于关系是集合，所有通常的集合操作都适用于它们。然而，结果可能不是一个关系；例如，二元关系与三元关系的并集不是一个关系。

下面讨论的操作是专门针对关系的。引入这些操作是因为它们在从其他关系推导关系方面起着关键作用。它们的主要应用是在非推理型信息系统——即不提供逻辑推理服务的系统——尽管当添加此类服务时，它们的适用性并不一定被破坏。

大多数用户不会直接关注这些操作。然而，信息系统设计者和关注数据银行管控的人员应当彻底熟悉它们。

2.1.1 置换（Permutation）

二元关系的数组表示有两列。交换这两列得到逆关系。更一般地，如果将排列应用于 n 元关系的列，所得关系称为给定关系的一个置换（permutation）。例如，图 1 中 supply 关系有 4! = 24 种置换，包括保持列顺序不变的单位置换。

由于用户的关系模型由一组 relationship（域无序关系）组成，置换与孤立考虑的这种模型无关。然而，它与考虑该模型的存储表示有关。在提供关系对称利用的系统中，存储关系可回答的查询集合与该关系的任何置换可回答的集合完全相同。虽然从逻辑上讲同时存储一个关系及其某种置换是不必要的，但出于性能考虑可能使其可取。

2.1.2 投影（Projection）

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

选择操作符 π 用于获取任何所需的置换、投影或两者的组合。因此，如果 L 是一个包含 k 个索引的列表 L = i₁, i₂, …, i_k，R 是一个 n 元关系（n ≥ k），^[7] 则 π_L(R) 是一个 k 元关系，其第 j 列为 R 的第 i_j 列（j = 1, 2, …, k），但结果行中的重复被去除。考虑图 1 中的 supply 关系。该关系的置换投影如图 4 所示。注意，在这种特定情况下，投影的 n 元组比其导出关系的少。

2.1.3 连接（Join）

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

图 5 中的例子显示了两个关系 R 和 S，它们可以无信息损失地连接，而图 6 展示了 R 与 S 的连接。二元关系 R 与二元关系 S 是可连接的，如果存在一个三元关系 U 使得 π₁₂(U) = R 且 π₂₃(U) = S。任何这样的三元关系称为 R 与 S 的连接（join）。如果 R、S 是二元关系且 π₂(R) = π₁(S)，则 R 与 S 可连接。在这种情况下始终存在的一个连接是 R 与 S 的自然连接（natural join），定义为：

其中 R(a, b) 为真当且仅当 (a, b) 是 R 的成员，S(b, c) 类似。立即可以得到：

注意，图 6 中展示的连接是图 5 中 R 与 S 的自然连接。图 7 展示了另一种连接。

检查这些关系可以发现，域 part（被连接域）中有一个元素（元素 1），它在 R 和 S 下都具有多于一个关联项。正是这个元素导致了连接的多样性。连接域中的这种元素称为关于 R 与 S 连接的歧义点（point of ambiguity）。

如果 π₂₁(R) 或 S 是函数，^[8] 则在 R 与 S 的连接中不可能出现歧义点。在这种情况下，R 与 S 的自然连接是 R 与 S 的唯一连接。注意，反复的限定"R 与 S"是必要的，因为 S 可能与 R 可连接（正如 R 与 S 可连接），而这个连接将是完全独立的考虑。在图 5 中，关系 R、π₂₁(R)、S、π₂₁(S) 都不是函数。

R 与 S 连接中的歧义有时可以通过其他关系来消除。假设我们拥有（或可以从独立于 R 和 S 的来源导出）一个在域 project 和 supplier 上的关系 T，具有以下性质：

1. π₁(T) = π₂(S)
2. π₂(T) = π₁(R)
3. T(j, s) → ∃p(R(s, p) ∧ S(p, j))
4. R(s, p) → ∃j(S(p, j) ∧ T(j, s))
5. S(p, j) → ∃s(T(j, s) ∧ R(s, p))

则我们可以构造 R、S、T 的三路连接，即一个三元关系 U 使得：

这种连接称为循环 3-连接（cyclic 3-join），以区别于线性 3-连接（linear 3-join），后者将是一个四元关系 V，使得：

虽然可能存在多个循环 3-连接（参见图 8、9 的例子），但可能发生这种情况的环境所涉及的限制比多个 2-连接的情况要严格得多。具体而言，关系 R、S、T 必须具有关于连接 R 与 S（设为点 x）、S 与 T（设为点 y）和 T 与 R（设为点 z）的歧义点，此外，y 必须是 x 在 S 下的关联项，z 是 y 在 T 下的关联项，x 是 z 在 R 下的关联项。注意，在图 8 中，点 x = a, y = d, z = 2 具有此性质。

三个二元关系 R、S、T 的自然线性 3-连接由下式给出：

其中左边不需要括号，因为自然 2-连接（∗）是结合的。要获得循环版本，我们引入操作符 γ，它通过将首尾绑在一起，从度为 n 的关系产生一个度为 n − 1 的关系。因此，如果 R 是一个 n 元关系（n ≥ 2），R 的绑定（tie）由以下等式定义：

现在我们可将 R、S、T 的自然循环 3-连接表示为：

将线性/循环 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 组合（Composition）

读者可能熟悉应用于函数的组合概念。我们将讨论该概念的一种推广，并首先将其应用于二元关系。我们对组合和可组合性的定义直接基于上文给出的连接和可连接性的定义。

假设我们有两个关系 R 和 S。T 是 R 与 S 的组合（composition），如果存在 R 与 S 的连接 U，使得 T = π₁₃(U)。因此，两个关系可组合且仅当它们可连接。然而，R 与 S 存在多于一个连接，并不意味着 R 与 S 存在多于一个组合。

对应于 R 与 S 的自然连接的是自然组合（natural composition），^[9] 定义为：

取图 5 中的关系 R、S，它们的自然组合如图 10 所示，另一种组合如图 11 所示（从图 7 所示的连接导出）。

当存在两个或更多连接时，不同组合的数量可能少至一个，也可能多至不同连接的数量。图 12 展示了一个例子：两个关系有多个连接但只有一种组合。注意，点 c 的歧义性在组合 R 与 S 中丢失了，因为通过点 a、b、d、e 建立了无歧义的关联。

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

对关系组合缺乏理解导致若干系统设计者陷入了所谓的连接陷阱（connection trap）。这个陷阱可以用以下例子描述。假设每个供应商的描述通过指针链接到该供应商供应的每个零件的描述，并且每个零件的描述类似地链接到使用该零件的每个项目的描述。现在得出了一个通常不正确的结论：即如果从给定供应商出发，沿着他供应的零件追踪到使用这些零件的项目，就能得到该供应商供应的所有项目的有效集合。只有当项目和供应商之间的目标关系恰好是其他两个关系的自然组合时，这个结论才是正确的——而且我们通常必须加上"在任何时候"这个限定语，因为这在路径追踪技术的宣称中通常是隐含的。

2.1.5 限制（Restriction）

关系的子集是一个关系。关系 S 作用于关系 R 以生成 R 子集的一种方式是通过限制（restriction）操作。此操作是函数限制到其定义域子集的推广，定义如下。

设 L、M 为等长的索引列表，其中 L = i₁, i₂, …, i_k，M = j₁, j₂, …, j_k，且 k ≤ R 的度且 k ≤ S 的度。则 R 按 L, M 对 S 的限制——记作 R_L|MS——是 R 的最大子集 R' 使得：

此操作仅在等式对所有的 h = 1, 2, …, k 在 π_ih(R) 的元素与 π_jh(S) 的元素之间可适用时才被定义。图 13 中的三个关系 R、S、R' 满足方程 R' = R_(2,3)|(1,2)S。

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

2.2 冗余

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

假设 θ 是一组关系操作，每个操作都具有从其操作数产生一个唯一关系的性质（因此自然连接符合条件，但连接不符合条件）。如果存在来自 θ 的操作序列，它能始终从 S 的成员中产生 R，则关系 R 是从关系集合 S θ-可推导的。短语"始终"的存在是因为我们处理的是时变关系，而我们关注的是在相当长时期内保持的可推导性。

对于非推理型系统中关系的命名集，一个适当的集合 θ₁ 似乎包含以下操作：投影、自然连接、绑定和限制。置换是无关的，自然组合不需要包含在内，因为它可以通过先自然连接后投影来获得。对于存储表示集合，适当的操作集合 θ₂ 将包括置换以及与子集化、合并关系以及对其元素排序和连接相关的额外操作。

2.2.1 强冗余

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

在第一个例子中，关系集合仅包含以下关系：

其中 serial# 为主键，manager# 为外键。记活动域为 Δ_t，并假设在任何时间 t 都满足：

以及：

在这种情况下，冗余是显然的：域 managername 是不必要的。为了说明它是如上定义的强冗余，我们观察到：

在第二个例子中，关系集合包含一个描述供应商的关系 S（主键 s#）、一个描述部门的关系 D（主键 d#）、一个描述项目的关系 J（主键 j#），以及以下关系：

其中 "…" 表示除 s#、d#、j# 外的其他域。假设已知以下条件 C 不随时间变化：供应商 s 供应部门 d（关系 P）当且仅当供应商 s 供应某个项目 j（关系 Q），且部门 d 被分配到该项目（关系 R）。于是，我们可以写出方程：

从而展示出强冗余。

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

2.2.2 弱冗余

可能存在第二种类型的冗余。与强冗余相反，它不由等式刻画。如果一组关系包含一个关系，其某个投影不能从其他成员导出，但在任何时候它都是该集合中其他关系的某些投影的某个连接的投影，则该关系集合是弱冗余的。

我们可以通过取上述强冗余的第二个例子来展示弱冗余，但假设条件 C 不始终成立。

关系 π₁₂(P)、π₁₂(Q)、π₁₂(R) 是复合关系（complex relations），^[10] 在其中任意两个的潜在连接中，可能不时出现歧义点。在这些情况下，它们之中没有一个能量从另外两个导出。然而，它们之间确实存在约束，因为每个都是它们三者中某个循环连接的投影。其中一种弱冗余可以用以下陈述来刻画：在任何时候，π₁₂(P) 是 π₁₂(Q) 与 π₂₁(R) 的某个组合。该组合在某个时刻可能是自然组合，而在另一时刻可能是非自然组合。

一般来说，弱冗余内在于用户社区的逻辑需求中。它们不能被系统或数据库管理员移除。如果它们出现，它们会同时出现在命名集和存储表示集中。

2.3 一致性

无论何时命名关系集合在任何意义上是冗余的，我们都将把一组定义所有不随时间变化的冗余的语句与该集合关联起来。如果信息系统缺乏（而且它很可能缺乏）关于每个命名关系的详细语义信息，它就不能推导出适用于该命名集的冗余。它可能在一段时间内尝试归纳出冗余，但这样的尝试不会万无一失。

给定一个时变关系集合 C，一个关联的约束语句集合 Z，以及 C 的一个瞬时值 V，我们将根据 V 是否满足 Z 来称状态 (C, Z, V) 为一致或不一致。

例如，给定存储的关系 R、S、T 以及约束语句 "π₁₂(T) 是 π₁₂(R) 与 π₁₂(S) 的组合"，我们可以不时检查 R、S、T 的存储值是否满足此约束。执行此检查的算法将检查 R、S、T 各自的前两列（以系统表示的任何方式），并确定：

1. π₁(T) = π₁(R)，
2. π₂(T) = π₂(S)，
3. 对于关系 π₁₂(T) 中的每一对元素 (a, c)，存在某个元素 b，使得 (a, b) 在 π₁₂(R) 中且 (b, c) 在 π₁₂(S) 中。

在获取一个关系集合的瞬时快照方面存在实际问题（本文不予讨论），其中某些关系可能非常大且多变。

重要的是要注意，如上定义的一致性是一个数据银行瞬时状态的属性，并且与该状态是如何产生的无关。因此，特别地，不区分用户是由于遗漏行为还是执行行为而产生的不一致性。考察一个简单例子将说明这种方法（可能不同寻常）对一致性的合理性。

假设命名集 C 包含第 2.2 节例子中的关系 S、J、D、P、Q、R，且 P、Q、R 具有其中描述的强或弱冗余（在当前考虑的情况下，哪种类型的冗余发生并不重要）。进一步假设，在某个时间 t，数据银行状态是一致的，且不存在这样一个项目 j：供应商 2 供应项目 j 且 j 被分配到部门 5。因此，在 π₁₂(P) 中没有元素 (2, 5)。现在，用户通过向 P 插入某个合适的元素，将元素 (2, 5) 引入 π₁₂(P)。数据银行状态现在不一致了。

如果不一致性可能来自遗漏行为——如果输入 (2, 5) 是正确的，并且确实存在项目 j 使得供应商 2 供应 j 且 j 被分配到部门 5，在这种情况下，用户很可能打算在不久的将来向 Q 和 R 中插入元素，其效果将是将 (2, j) 引入 π₁₂(Q) 和 (5, j) 引入 π₁₂(R)。另一方面，输入 (2, 5) 可能是有错误的。可能是用户打算向 P 插入其他元素——其插入将把一致状态转变为一致状态的元素。关键是，系统通常无法在不对其环境（也许是创建了不一致性的用户）进行询问的情况下解决这个问题。

当然，系统可以采用若干种可能的方式来检测不一致性并对其做出响应。一种方法是，每当发生插入、删除或键更新时，系统检查可能的不一致性。自然，这种检查会减慢这些操作。如果产生了不一致性，细节被记录在内部日志中，如果在合理的时间间隔内没有修复，则通知用户或负责数据安全性和完整性的人。另一种方法是每天一次或更低频率地以批处理方式进行一致性检查。在检查时间仍留在数据银行状态中的引起不一致性的输入，可以通过系统维护所有改变状态的事务日志来追踪。如果很少发生非暂时性的不一致性，这后一种方法当然会更优越。

2.4 小结

在第 1 节中，提出了数据的关系模型，作为保护格式化数据系统的用户免受数据表示中潜在破坏性变化（由数据银行的增长和流量变化引起）的基础。引入了时变关系集合的范式。

在第 2 节中，定义了关系上的操作和两种类型的冗余，并将其应用于维护数据一致性问题。随着越来越多不同类型的数据被整合到公共数据银行中，一致性问题必将成为一个严重的实际问题。

许多问题被提出但未得到解答。例如，第 1.4 节中数据子语言的许多更重要性质仅被提及。本文既没有讨论这种语言的纯语言学细节，也没有讨论实现问题。然而，所呈现的材料应当足够让有经验的系统程序员勾勒出若干种方法。同时也希望本文能够促进格式化数据系统工作中的更高精确性。

致谢：IBM Poughkeepsie 的 C. T. Davies 说服了作者认识到未来信息系统中数据独立性的必要性。作者还要感谢他以及 IBM San Jose 研究实验室的 F. P. Palermo、C. P. Wang、E. B. Altman 和 M. E. Senko 的有益讨论。