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

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

IBMResearchLaboratory,Sanjose,California

将来的数据库运用者确定是和数据在机器中的存储（即数据库的

内部模式）相隔离的。而通过提示效劳来供应信息是一个不太令人满

足的解决方法。当数据的内部模式表示发生变更，甚至数据内部表示

的多个方面发生变更时，终端用户和大多数应用程序的活动都不会受

到影响。因此，查询、更新和报告存储信息类型的自然增长和变动都

须要在数据表示中表现出来。

现存的不行推断的、格式化的数据系统给用户供应了树构造的文

件或者更一般的网格模式的数据。本文在第一局部探讨这些模式的缺

乏之处。并且会介绍一种基于n元组关系的模式，一种数据库关系的

正式形式和通用数据子句的概念。其次局部将探讨一些关系的操作

（不是逻辑层面的），并且把这些操作应用于用户模式上解决冗余和

一样性问题。

1关系模式和一般模式

1.1简介

这篇文章是关于系统的根本关系原理的应用，这个原理供

应了共享大型格式化数据库的方法。除了Childs[l]的文章有

介绍外，用于数据库系统的关系的主要应用还表现在演绎推理

型的问-答系统中。Levein和Maron[2]供应了大量关于这个领

域的参考资料。

相比之下，这里要解决的问题是一些数据独立性的问题

——应用程序和终端活动之于数据类型增长和数据表示变动的

独立性，而数据一样性问题即使在非演绎推理型系统中也是很

麻烦的。

在目前流行的非推论性系统中，第一局部要介绍的数据的

关系视图〔或叫做模式）在一些方面好像优于图模式和网格模

式[3,4]o这种模式供应了一种依据数据的自然构造来描述描述

数据的方式一一也就是说，不用为了数据的机器表示而添加其

他的将构造。因此，这种模式为高水准的数据语言供应了根底,

而这种数据语言机制一方面可以到达最大化程序之间的独立

性，另一方面也可以最大化数据的机器表示和组织之间的独立

性。

关系模式更高一级的优势在于它构成了关系处理可导性、

冗余性和一样性的巩固根底一一这些将在其次局部探讨。另一

方面，网络模型产生了一些混淆，尤其是把连接的源误作为关

系的源（见其次局部“连接陷阱"）

最终，关系视图允许对目前格式化数据系统的范围和逻辑

限制的更清晰的估算，并且有在单独的系统内竞争数据表示方

式的优点（从逻辑的观点）。更清晰的这个观点的例如会在本文

中的不同局部中被阐释。但是支持关系模式的系统实现不会探

讨。

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会失败是因为它试图引用一个不存在的文件

（现可用的系统把这种状况视为error）或者是它没有引

用包含它必需信息的文件。有疑问的读者应当找一些样例

程序来理解这个简洁的问题。

由于在一般状况下，开发可以检测系统允许的全部树构造

的应用程序是不实际的，而且这种程序在构造须要变更时

也会失败。

为用户供应网格数据模式的系统也会遇到相像的问题。在

树和网格两种情形下，用户（或者是用户的程序）都被要

求采纳用户数据存取路径的集合O这些路径是否与存储表

示的指针定义的路径有较近通信是没有影响的，而在IDS

中这种通信时极其简洁的，但在TDMS中就正好相反了。

不考虑存储表示来看这种问题，结果就是，终端活动和程

序变得依靠于用户存取路径的连续存在性。

对于这个问题的一个解决方案就是采纳如下策略:一旦用

户存取路径被定义了，那么除非全部应用这个路径的全部

程序都废弃了［finish了），否那么这个路径就不会过时。

由于在团体总体模式的数据库用户的存取路径的数量最

终可能变得过大，因此这种策略是不实际的。

1.3数据的关系视图

关系这个词在这里运用的是其被广泛认可的数学意义。给定集

合SLS2,……,Sn［这些集合没有必要确定是不同的），假如R

是一个满足如下条件的n元组集合：其每个元素的第一个元素

来自S1,其次个元素来自集合S2,以此类推，那么R就是这n

个集合（S1,S2,……,Sn）上的一个关系。我们用Sj来表示R

的第j个域。正如上面所定义，R被称作是n级的。1级的关系

通常叫做一元关系，2级的被叫做二元关系，3级的被叫做三元

关系，而n级的叫n元关系。（更简洁地说，R是SI,S2,,Sn

这n个集合的笛卡尔乘积的一个子集）

说明一下，我们将频繁地运用关系的数组表示，但是必需清晰

的是这个特定表示并不是用于说明关系视图必需的局部。用于

表示n元关R的数组有如下特征：

（1）每一行代表R的一个n元组

（2）行的排列依次是无关紧要的

（3）全部行都是不一样的

（4）列的依次是有意义的一一列应当符合R定义时的域的依

次SLs2,……,Sn］但是留意，排序的域和无序的域下标

之间的关系）

（5）每个列的意义局部是由命名相应域来传达的

图1中的例子展示了一个叫做supply4级的关系，这个关系显

示的是特定工程的特定供应者的特定数量的零件发货过程。

supply(supplierpartprojectquantity)

12517

13023

2379

27514

41112

FIG.1.Arelationofdegree4

图1

有人可能会问：假如列由相应域的名字来标识，那么为什

么列的依次会有影响呢？正如图2中例子显示的一样，两列可

以有一样的头（表示同样的域），但是对于这个关系他们有不

同的含义。这里描述的关系叫做component。它是一个三元关

系，其中前两个域叫做part而第三个域叫做quantityo

Component（x,y,z）的意思就是部件x部件y的干脆构成成

分（或者子部件），而须要z个的x部件来组成一个的y部件。

这个关系在零件扩大问题中有重要作用。

component(paripartquantity)

159

257

352

2612

363

471

671

FIG.2.Arelationwithtwoidenticaldomains图？

一个引人注目事实是，一些现存的信息系统（主要是基于

树构造文件组织）不能够为有两个或两个以上的一样域的关系

供应有效地数据表示。IMS/360[5]的目前版本就是这种系统的

一个实例。

一个数据库中的总体数据可以看做一个随着时间变更的关

系的集合。这些种类的关系有各种各样的级（或度）。随着时

间的前进，每个n元关系都可能经验插入另外的n元组，删除

现存的n元组和变更现存随意n元组的组成局部的操作。

但是，在很多商业、政府和科学数据库中，一些关系的度

（或作级别）是相当高的（30级的关系也是很常见的）。用户

通常不能记住任何关系的全部域的依次（例如，关系supply

中定序的供应者、零件、工程和数量）。因此，我们提出用户

不必处理域排序的关系，而处理与其非排序域的有同样效果的

关系的方法。为了到达这个目的，关系中的域必需是在不采纳

位置时唯一可确认的，至少在某个给定的关系中是这样的。因

此，在有两个或更多一样域的地方，我们要求对每一种状况下

域名都是合格的不同的角色名〔rolename）,这些角色名用于

识别给定的关系中的域所扮演的角色。例如，在图2的

component关系中，第一个域part可以用合格角色名sub指

示，而其次个用super,以便用户能够处理component关系和

它的域----sub.partsuper.part,quantity----而不用考虑这

些域之间的任何排序。

总之，提出多数用户应当与由随时间变更的联系集合（而

不是关系）组成的数据的关系模式交互。每个用户不必知道除

了关系的名字和其相应的域的名字外的其它更多信息（只要有

须要就可以采纳角色资格）。甚至信息可以是系统〔具有平安

和隐私约束）依据用户的恳求以菜单形式供应的。

数据库关系模型的建立通常还有其他很多可供选择的方

法。为了探讨更好的方式（或标准形式），我们必需引入另外

几个概念（活动域、主码、外码、非单一域〕并建立一些与目

前在信息系统编程中运用的术语的链接。在本文后面的局部，

我们将不再苦恼地去区分关系frelation）和联系

（relationship）,而在须要显示他们不同之处的地方我们会

显示地指出。

下面考虑这样一个数据库实例，该数据库包含关于部件,

工程和供应者的一系列关系。一个叫part的关系被定义在以

下的域上：

(1)部件编号(partnumber)

(2)部件名称(partname)

(3)部件颜色(partcolor)

(4)部件重量(partweight)

(5)在手的数量(quantityonhand)

(6)预订的数量(quantityonorder}

可能还有其他的域。事实上，每个这样的域都是一池数值,

这些数值中的一些或全部可以在任一瞬时在数据库中表示出

来。可以想象，在某些瞬间，全部部件颜色都被显示出来，但

是难以做到的是把全部可能存在的部件的重量、部件名字和部

件编号都显示出来。我们称在某个时刻表现出来的值的集合为

在那个时刻的活动域(activedomain)□

通常，一个给定关系的一个域(或者域的组合)有一组唯

一识别该关系的每一元素(n元组)的值。这样的一个域(或

组合)被叫做主码(primarykey)。在上面的例子中，部件号

可能是一个主码，而部件颜色可能就不是了。主码是非冗余的，

假如他满足它是一个简洁域(非组合的)或者一个组合，而对

于组合的状况，在唯一识别每一元素时参与到这个组合中的简

洁域没有一个是多余的（也就是组合中的全部的简洁域共同构

成一个唯一识别关系元素的码）。一个关系可以有多个非冗余

的主码。假如上面所说的部件的名字都互不一样，那么就成了

这种状况的一个实例。无论什么时候，只要一个关系有两个或

者更多非冗的主码，它们中的随意一个都可以选作这个关系的

主码。

一个普遍的要求就是，关系当中的元素穿插引用同一关系

的其他元素或者引用一个不同关系的元素。码供应了一种用于

表示这种穿插引用的面对用户的方式（但不是唯一的方式）。

假如一个域（或者域组合）不是关系R的主码，但是它的元素

是某个关系S的主码值（解除S和R是同一关系的可能），那

么我们就把关系R的这个域1或者域组合）叫做外码。在图

Isupply关系中，supplier、part、project是主码，而这三

个域中每一个都被单独看作是一个外码。

在前面的工作中已经显现出一个很强的趋势，即把一个数

据库中的数据看成由两个局部组成，一个局部由实体描述组成

［如supplier的描述），而另一个局部由不同实体间或者实体

类型间的关系组成（如supply关系）。当一个关系有任何其他

关系的外码时，要维持这种区分是困难的。在用户的关系模式

中，做出这样的区分好像是没有好处的〔但是，当把关系概念

用于用户联系集的机器表示时，这种区分可能有些好处）。

到目前为止，我们已经探讨了一系列定义在简洁域上的关

系的例子，而那些简洁域的元素是原子的（非组合的）值。非

原子值会在关系框架中探讨。因此，一些域可以把关系当做元

素。相应地，这些关系可以被定义在非简洁域等等。例如，关

系employee定义的其中一个域可以是salaryhistory［薪水

历史）。Salaryhistory域中的一个元素是一个定义在date

域和salary域上的二元关系。Salaryhistory域就是这种二

元关系的一个集合。在数据库中随意瞬间都会有与employee

（员工）数量一样的salaryhistory关系实例。相比之下，

employee关系就只有一个实例。

在表示数据库的术语中属性和重复组分别在简洁域和非简洁域

中是大致相像的。现在术语中的多混淆之处是由于没能把类型

和实例（如在“record"中）区分开和把数据的用户模式的组

成和它们相应的机器表示区分开（再次以“record”为例）。

1.4标准形式

一种全部域都是简洁域的关系能够用如上探讨过的二维的齐次

列数组来表示其存储形式。一些更为困难的数据构造对一个有

一个或多个非简洁域的关系是必要的。由于这个缘由〔其他的

将在下面举例），消退非简洁域的潜力好像值得投资。事实上，

有一种简洁的消退过程，而我们把这个过程叫做标准化。

例如，考虑图3（a）显示的关系集合。Jobhistory和children

是employee关系的非简洁域。Salaryhistory是jobhistory

的一个非简洁域。图3（a）中的树展示了各个非简洁域之间相

互关系。

,______emp1lo_yee____1

II

jobhistorychildren

I

salaryhistory

employee(tzianf,name,birthdate,jobhistory,children)

johhiatcry(johdaUjtit1*salaryhistory)

salaryhistorySalarydale,salary)

children(childname,birthyear)

FIG.3(a).Unnormalisedset图3(a)

employee*(manf9name,birthdate)

jobhistory'(num#,?而dal%title)

salaryhistory'(man#,jobdatetsalarydate,salary)

children1(man#,childnamc,birthyear)

FIG.3(b).Normalizedset图3

标准化按如下程序进展。从关系的树顶端开场，记住它的主码,

并且通过插入主码域或者域组合来扩展每个直属的下层关系。

每个扩展关系的主码由从父关系(即上一层的关系)拷贝下来

主码在进展扩大前的主码构成。现在，从父关系中化掉全部非

简洁域，删除树的顶节点，并且在留下的子树上重复同样的操

作程序。

图3(a)中标准化关系集合的结果就是图3(b)中的集合。每

个关系的主码都用斜体表示以显示这些码值是如何通过标准化

来扩展的。

假如要使得如上所述的标准化是可用的，那么关系集合的非标

准化必需满足如下条件：

(1)非简洁域之间的相互关系图是一个树集合。

（2）没有主码是由非简洁域构成的

作者不知道哪个应用是不严格满足以上这些条件的。那这类标

准化的更进一步的操作就可进展了。这些在本文中不会探讨。

当全部关系都以标准形式出现时，变得可行的数组表示的简洁

性不仅有利于存储的目的，而且有利于广泛采纳不同数据表示

的系统之间的大量数据的通信。这种通信形式是数组表示的一

个相称的压缩版本，并且有如下有利条件：

（1）没有指针（值地址或值替换）

（2）防止了全部对哈希选址方式的依靠性

（3）不包含索引和有序列表

假如用户的关系模式以标准形式建立，那么数据库中数据项的

名字可以是一种更简洁的形式，反之亦然。一个通用的名字有

如下形式：

其中R是关系名字；g是同辈标识符（可选的）；r是角色名（可

选的）；d是域名。由于g只有在当一个给定的关系中多个同

辈存在时才须要，而且r只有在当关系R有两个或更多名为d

的域时才须要，所以简洁形式R.d通常是恰当的。

1.5一些语言方面

如上所述，数据关系模式的采纳使基于好用谓词演算的通用数

据子语言的开展成为可能。假如关系结合是标准形式的，那么

一阶谓词演算就足够了。这种语言为全部其它提议的数据语言

供应了语言影响力的一个衡量标准，并且它自己也是嵌入（有

适当的句法修改）在很多其它主流语言（编程，面对吩咐的或

面对问题的）中的一种强势的候选者。虽然具体地描述这样一

种语言不是本文的目的，但是它显著的特征有如下几点。

我们用R标记数据子语言，用H标记主语言。R允许关系及

他们的域的声明。每一个关系的声明都为这个关系确定了它的

主键。声明过的关系被添加到系统资料库，从而被任何拥有相

宜权限的运用者群体的一员运用。H允许支持声明，这些声明

可能没那么永久性的说明白这些关系在存储时时如何表示的。R

允许定义数据库中的任何数据子集的检索。这样的一个检索恳

求之后能发生的动作受制于平安限制条件。

数据子语言的普适性是由它的描述实力确定的（而非它的计

算实力），在一个大型数据库中，每一个数据子集都拥有大量的

可能的（而且合理的）描述。即使我们假设〔正如我们所做的）

系统有权运用的、确定搜寻数据合格性的功能子程序的有限集

合只有一个。因此，能够应用于集标准资格表达式的集合的必

需拥有对应用谓词演算的格式标准的公式集合的描述实力。众

多周知，为了维护这种描述实力，不必要表示（无论选择的是

什么语法）选中的谓词演算的全部公式。比方，那些以前束标

准格式的就够了。

在搜寻体验行业的合格性或其他方面可能要用到算术函数。

这些函数用H语言定义，用R语言调用。

这样指定的一个集合可能仅用于查询，或者用于可能发生的

变更。插入采纳向已声明的关系中参与新的元素的形式实现，

同时不考虑在机器中表示的依次。删除对公共组都有效〔而不

是个人用户或子组），删除以从已声明的关系中移除元素的形

式实现。假如指定关系之间的删除和更新依靠性已经用R语言

声明，那么一些删除和更新可能会由其他的删除和更新引发产

生。

用这种视图看数据，对查询数据的语言有一个重大的影响，

这个影响就是数据元素和集合的命名。这其中的一些方面已经

在上一节探讨过。运用通常的网络视图，用户经常为创建和运

用更多的而不是完全有必要的关系名称所累。因为名称适合路

径（或路径类型）有关，而不是和关系有关。

一旦用户意识到存储了某个特定的关系，他会希望运用他的

参数和未知参数的随意组合来利用这个关系，因为信息（如珠

穆朗玛峰）是存在的。这是一个系统特征，我们叫做（逻辑上）

关系的对称利用。当然，性能上的对称性是不行能的。为了支

持一个二元关系的对称性利用，须要两条干脆路径。对于一个

n元的关系，被命名和限制的路径数量是n的阶乘。同样，假

如实行这样的关系视图：每一个n元关系必需被用户以只包含

2元关系的一张网状表达式表示出来（比方，参见Feldman's

LEAP系统），那么必需创建2n-l个名称而不仅仅是1.2节描

述的n+1个拥有干脆n元标记的名称。例如，图片1这的4元

关系supply,它以n元标记初始化了5个名称，用如下形式表

示

P(supplier,&(part,R(project,quantity)))

以网状二元标记，包含7个名称。

这种表示方式的进一步的缺点是它的不对称性。尽管这种不

对称性不会制止对称性利用，它确定会运用户的一些询问操作

很不便利表示〔比方，对于跟给定的运用Q和R写的工程相关

的那些局部和数量的查询)。

1.6可表达的、已命名的而且已存储的关系

有两个关系集合跟资料库有关：命名集和可表达集。命名

集市用户群能够通过一个简洁名字(或标识)识别的全部关系

的集合。当恰当授权的用户声明R时，关系R拥有了命名集的

成员资格。当恰当授权的用户取消R的声明时，它失去了成员

资格。

可表达集是能够用数据语言中的表达式表示的全部关系的

集合。这些表达式是由名字集中关系的简洁名字组建起来的。

阶段的名称、角色和域、逻辑连接词、谓词演算的量词以及某

些常量关系符号，如=,>o名字集是可表达集的一个子集

——通常是一个很小的子集。

由于名称集合中的某些关系可能是集合中其它关系的时间

无关的组合，将名称集和定义这些时间无关的限制条件的语句

的集合联系起来考虑很有用。我们将推迟探讨这个，直到我们

介绍了对关系的几种操作〔参看其次节)。

为用户设计一个支持关系模型的数据系统时，设计者所面

临的主要问题之一是确定支持存储表示所用的集合。志向状况

下，允许的数据表现形式的多样性应当正好足够覆盖性能安装

总集合要求的范围。太大的范围导致不必要的存储开销和连续

的对领先构造描述的重新说明。

对于随意选定的存储表示集合，数据系统必需供应把用关

系模型的数据语言表达的用户需求转换成相应且有效的当前存

储表示的方法。对于高层数据语言，这好像一个具有挑战性的

设计问题。不过，随着更多的用户拥有了对大型资料库的访问

权限，这就变成了一个必需解决的问题。同时，也能为从个人

用户到数据系统供应有效的响应和吞吐量。

2冗余和兼容

2.1对关系的操作

由于关系是集合，全部一般的集合操作也都适用于关系。不过,

结果可能不是一个关系，比方，一个二元关系和三元关系的连

接不是一个关系。下面探讨的操作是特地针对关系的。介绍这

些关系是因为它们在从其他关系中派生出关系上扮演重要角

色。它们主要应用在非推理的信息系统中，这种系统不供应逻

辑推理效劳，尽管当类似的效劳被添加后不确定会损害它们的

适用性。大多数用户不会干脆关切这些操作。然而，信息系统

设计人员和与资料库限制相关的人员应当彻底熟识它们。

2.1.1置换。一个二元关系有一个具有两列的数组表示。将这两

个列换位得到逆关系。更一般的，假如一个置换被应用于

一个n元关系的列，由此产生的列被称作给定序列的排

列。例如,图1中有关系supply的4!=24种排列,假如

我们包括不变更列依次的恒等排列。

2.1.2投影。假设我们从一个关系中选出特定的某些列［剔除其

它的列)，然后从结果中删除数组中的任何行重复。最终

的数组表示了一个叫做给定关系的投影的关系。

选择算子JI被用来获得任何所需的排列、投影或两个操

作的组合。因此，假如L是K个标记的列表L=il,i2,…，

ik,R是一个n元关系(n>=k),那么L(R)一个k元

关系，这个关系的第j列是R的第ij列(j=l,2,…,k),

同时结果的行中的冗余也将移除。考虑图1中的关系

supply,图4展示了这个关系的置换投影。留意，在这个

特殊的状况下，投影比产生该投影的关系的n元组要少。

2.1.3连接。假设给定两个二元关系，它们有一部门共同域。在

什么状况下我们可以结合这两个关系，以形成一个三元关

系，其中保存了所给关系的全部信息、？图5中的例子显示

了两个可以进展无信息损失连接的两个关系R,S,图6显示

了R和S的连接。假如存在一个三元关系U,满足弘12⑴)

=R且Ji23(U)=S.,那么二元关系R和S那么是可连接

的。随意这样的三元关系都叫做R和S的连接。假如R,S是

二元关系且弘2(R)=冗1(S),那么R和S是可连接的。

自然连接是确定存在的一个连接，定义为

R*S={(a,b,c):R(a,b)AS(b,c))

其中，假如(a,b)是R的一个成员且和S(b,的相像,那么

R(a,b)的值是真。即

Ji12(R*S)=R且Ji23(R*S)=S.

留意，图6中显示的连接是图5中的R和S的自然连接，图7

显示了；另一个连接。

检查这些关系展示了域part〔连接操作发生的域)中

的一个元素(元素1),该元素有性质：它拥有在R和S

中不止一个关系。正是这个元素引起了连接的多元化。在

连接域里这样的元素叫做有关R和S连接的歧义点。

假如冗21(R)或R是一个函数，在R和S的连接中

不会出现歧义点。在这种状况下，R和S的自然连接就是R

和S的连接。留意反复的限定“R和S〃是必需的，应为S

可能和S可连接(R和S同样)，而且这个连接应当完全

分开考虑。在图5中，关系R,n21(R),S,冗21(S)

都不是一个函数。

R和S连接中的歧义点有时可以用其它关系消退。假设

我们被给定，或者可以从R,S中产生一个关系T,关系在

域project和supplier上拥有以下性质：

这样我们可能形成R,S,T的三路连接，也就是一个三从

关系，如下:

这样的一个连接被叫做循环三路连接以和线性三路连

接区分开来，后者将会是一个四元关系V,如下：

尽管可能存在不止一个循环三路连接（参看图8,9）,

这种状况可能发生的环境比2元关系的多元性要发生该状

况的环境要有更严格的限制.

具体来说，关系R,S,T必需处理关于R和S连接（假设

是点x）,S和T的连接1假设是y）和T和R的连接（假

设是z）的歧义点。而且，更进一步，y必需是x在S下的

一个关系，z是y在T下的一个关系，x是z在R下的一个

关系。留意在图8中，点x=a;y=d;z=2有这个属性。

3个2元关系R,S,T的自然线性三路连接如下：

其中，因为是2元自然连接，等号左边不用圆括号。为

了获得循环副本，我们引入操作符号r,它可以通过将一个

n元关系的首位相连产生一个nT元的关系。因此，假如R

是一个n元关系（n>=2）,R产生的环由下面的公示定义:

我们现在可以用下面的表达式表示R,S,T的自然循环

三路连接：

线性概念，循环S-连接和n元关系的连接的自然副本

的扩展很明显。然而，考虑到一些进展连接的关系不确定

是二元的，所以可能须要一些额外的描述。考虑关系R（r

元），S（s元）的状况，在它们的p个域上连接两个关系。

简洁的说，假设这P个域是R的r个域中的最终p个域和

S的s个域中的前P个域。假如不是这样，我们可以总是

采纳适当的排列使它这样。现在，取得R的前r-p个域的

笛卡尔乘积，并且叫这个新的域为Ao取得R的后p个域

的笛卡尔乘积，并称之为Bo取得S的后s-p个域的笛卡

尔乘积，并称之为Co我们可以把R看作是在域A.B上的

二元函数。类似的，我们可以把S看作是域B,C上的二元

关系。线性和循环S-连接的概念现在成为可以干脆承受的

了。可以对线性的和各种元的n个关系的循环n元连接也

采纳这种方法。

2.1.4组成。读者很可能对应用在函数上的组成概念特别熟识。

我们将会探讨这个概念的概括而且首先把它应用到二元

关系上。我们对组成和可组合型的定义是干脆基于以上给

出的联合和可联合性的定义上的。

假设我们被赐予两个关系R,s。T是R和S的组合，假如

存在一个R和S的连接且满足7=m(U)。因此，当且

仅当两个关系是可连接的时，它们是可组合的。然而，

存在多于一个的R和S的连接并不意味着存在多余一个

的R和S的组合。

与R与S的自然连接相应的是S伴随R的自然组成，

定义为：

R*S=Ji13(R*S)

将关系R和S从表5中提取出来看，他们的自然组成由

表10展示，而另一个组成由表11展示（与表7展示的

连接相区分）

表10.S伴随R的自然组成（由表5所得〕

表11.S伴随R的另一个组成（由表5所得）

当存在2个或更多的连接时，不同的组成数量可能少至

1个也可能多至与不同连接数目一样。表12展示了一个有

很多连接关系但是只有一个组成的2个关系的例子。留意

到在由S组成R时，点c的不确定性丢失了，因为通过点

a,b,d,e造成了确定性的关联。

表12.多个连接，只有一个组成

多对非必需二元（可能是多维的）的关系的组成的扩展

与这种关系成对连接的状况如出一辙。

对于关系组合了解的缺乏导致很多系统设计员陷入了

一种我们称为连接陷阱的逆境。这种陷阱可能被依照以下

举例描述。假设每个供应商的描述与供应商供应的每一局

部的描述相关联，并且每一局部的描述近似地与运用这些

局部的工程描述相关联。通常，现在就可以得出一个错误

的结论：换句话说，假如全部可能的通道通过供应商在工

程中供应的局部来遵循供应商，就可以得到一个该供应商

供应的全部工程的有效集。这样一个结论只有在特别特殊

的状况下才是正确的，即是目标的工程和供应商关系事实

上是另两个关系的自然组成一一而我们通常必需加上一个

词“对于全部时间〃，因为这通常是在跟踪限制技术的要

求中示意到的。

*别的作者倾向于忽视组成而不是自然组成，于是把这

一特殊的组成看做“那个组成”一一看，举个例子，Kelley

的"GeneralTopology".

2.1.5限制。一个关系的子集还是一个关系。关系S可能对

关系R操作从而形成一个R的子集的一种途径是通过S

对R进展限制操作。这个操作是函数对子集的域的限制

的一般化，它的定义如下。

设L,M为等长书目列表，L4,i2,……,ik,M=j„

j2,……jk其中kWR的维数且kWS的维数。那么L,M对由

S对R的限制RL|«S表示R的最小子集R',一(R')=

nM(S)o

这个操作只有当相等可以对于h=l,2,…,k,应用到

〜h(R)的成员和gh(R)之间才被定义。

表13中R,S,R'这3个关系满足等式R'=R(2,3)|(i12)So

表13.限制举例

我们现在立足于考虑这些操作在关系上的应用。

2.2冗余

一个指定关系集的冗余必需可以与存储陈述集的冗余相区分。

在这里我们主要关切的是前者。首先，我们须要一个关于关系的

可导出性的精确概念。

假设9是关系上的一个操作集合，而且每个操作都有对每个

操作数产生一个唯一关系的性质(因此自然连接是合理的，但是

连接是不合理的)。假如一个关系R在全部状况下存在一个集合9

的操作序列，使R从S的一个成员中产生，那么R对一个关系集

合S。-可导。“在全部状况下"这一描述是现在时的，因为我

们正在处理随时间变更的关系，而且我们的爱好在于保持一段关

键时期的可导性。对于非推理性系统上的指定关系，好像一个恰

当的集合匕包含了一下操作：投影，自然连接，束缚和限制。排

列是不相干的且自然成分须要被包含，因为在进展连接然后投影

的状况下是可行的。对于表示的存储集来说，一个恰当的对92

集合的操作会包含排列和更多的关于子集合和合并关系的操作，

并且排列和关联它们的元素。

2.2.1强冗余。假如一个关系集包含了最少一个关系，这个

关系限制了一个不同于其他关系集投影的投影，我们就

称这个关系集是强冗余的。以下两个例子是为了说明为

什么强冗余性是这样定义的，和证明它的实际作用。在

第一个关系系列的例子中包含了下面这个关系：

Employee(serial#,name,manager#,managername)

其中serial#是主键而manager#是外键。让我们用△来

指定有效域，并假设对于全部时间t满足：

△tfmanager#}uAt(serial#)且Atfmanagername)

u△,(name)

这种状况下的冗余就很明显了：域managername就是不

必要的。要证明这个是我们在之前定义的强冗余，我们发

觉

冗34temployee)=冗12(employee)1113(employee)。

在其次个关系系列的例子中包含了一个描述供应商的

关系S,S的主键为s#,一个关系描述部门的关系D,D的

主键为d#,一个描述工程的关系J,J的主键为j#,以及

一下关系：

P(s#,d#,…)，Q(spj#,…)，R(d#,j#,…)

其中…表示除了s#,d#,j#的其他域。让我们假设接

下来一个状况C,C保持时间的图理性：供应商s当且仅当

他供应的工程J［关系Q)是部门d可以被安排到的工程时

(关系R),s才将这个部门d［关系P)供应出来。然后，

我们就可以写出这个等式并因此展示出一个强冗余：

弘12(P)=n12(Q)•^2i(R)

强冗余存在于指定关系系列的一个重要缘由是用户便

利性。对此一个特殊的状况是指定关系集特征关系的保持,

从而从名字上涉及到它们的旧程序可以接着正确运行。关

于指定集强冗余存在性的学问使一个系统或者数据库管理

员得以在选择展示形式上有更多自由行，从而在处理当前

流量时更高效。假如一个指定集的强冗余干脆被存储集的

强冗余影响〔或者假如其他强冗余被引入这一存储集)，那

么一般来说，将会在一些查询的时间和装载中心处理器时

间突然变更的同时，消耗更多存储空间和更新时间。

2.2.2弱冗余。其次种类型的冗余可能存在。与强冗余相反,

它不是用一个等式来描述的。假如一个关系系列包含

了一个关系，这个关系包含一个无法区分于其他成员的

工程，但是这个关系对于任何时候都是一个该集合关系

中其他投影连接的投影，那么这一关系系列就是弱冗余

的。

我们可以用其次个强冗余的例子〔前面提到的)来展示

一个弱冗余，并且假设现在状态C并不能在全部时间下保

持稳定。关系〜2IP),(Q),〜2(R〕是困难关系，

在潜在的任两个关系连接的同时观点模糊的可能性时时常

产生。在这种状况下，没有一个关系可以区分于另外两个。

但是，在他们之间的确存在约束，因为每一个关系都是这

3个关系循环链接的投影。其中一个弱冗余可以用这个陈

述来表现：对于全部时间，/2(P)是一个—2(Q)和S2

(R)的组合。问题的组成可能是自然的那个发生在某个瞬

时而不自然的那个发生在另一个瞬时。

通常来说，弱冗余是随着用户沟通的逻辑须要而固有出

现的。他们无法被系统或数据库管理员移动。假如它们彻

底出现了，那必定在指定集和存储集的表现形式中同时出

现了。

2.3一样性