2022年翻译大型共享数据库的数据关系模型 .pdf

《2022年翻译大型共享数据库的数据关系模型 .pdf》由会员分享，可在线阅读，更多相关《2022年翻译大型共享数据库的数据关系模型 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大型共享数据库的数据关系模型E.F.Cod d IBM Research Laboratory,SanJose,California 未来的数据库使用者一定是和数据在机器中的存储（即数据库的内部模式）相隔离的。而通过提示服务来提供信息是一个不太令人满意的解决方法。当数据的内部模式表示发生改变，甚至数据内部表示的多个方面发生改变时，终端用户和大多数应用程序的活动都不会受到影响。 因此， 查询、 更新和报告存储信息类型的自然增长和变动都需要在数据表示中表现出来。现存的不可推断的、格式化的数据系统给用户提供了树结构的文件或者更一般的网格模式的数据。本文在第一部分讨论这些模式的不足之处。并且会介绍一种

2、基于n 元组关系的模式，一种数据库关系的正式形式和通用数据子句的概念。第二部分将讨论一些关系的操作（不是逻辑层面的） ，并且把这些操作应用于用户模式上解决冗余和一致性问题。1关系模式和一般模式1.1 简介这篇文章是关于系统的基本关系原理的应用，这个原理提供了共享大型格式化数据库的方法。除了Childs1 的文章有介绍外，用于数据库系统的关系的主要应用还表现在演绎推理型的问-答系统中。 Levein 和 Maron2 提供了大量关于这个领域的参考资料。相比之下，这里要解决的问题是一些数据独立性的问题应用程序和终端活动之于数据类型增长和数据表示变动的独立性，而数据一致性问题即使在非演绎推理型系统中

3、也是很棘手的。在目前流行的非推论性系统中，第一部分要介绍的数据的关系视图（或叫做模式）在一些方面似乎优于图模式和网格模式3,4 。这种模式提供了一种根据数据的自然结构来描述描述数据的方式 也就是说，不用为了数据的机器表示而添加其他的将结构。因此，这种模式为高水准的数据语言提供了基础，而这种数据语言机制一方面可以达到最大化程序之间的独立性，另一方面也可以最大化数据的机器表示和组织之间的独立性。关系模式更高一级的优势在于它构成了关系处理可导性、冗余性和一致性的坚固基础 这些将在第二部分讨论。另一方面，网络模型产生了一些混淆，尤其是把连接的源误作为关系的源（见第二部分“ 连接陷阱 ” ）最后，关系视

4、图允许对目前格式化数据系统的范围和逻辑限制的更清晰的估算，并且有在单独的系统内竞争数据表示方式的优点（从逻辑的观点） 。更清楚的这个观点的示例会在本文中的不同部分中被阐释。但是支持关系模式的系统实现不会讨论。1.2 目前系统的数据相关性最近发展的信息系统中数据描述表的提供是向数据独立性目标5,6,7 靠近的重要提高。这些表可以使改变数据库中数据表示的某些特征变得更容易些。但是，许多数据表示特征可以在不逻辑地削弱一些应用程序的情况下被改变的功能仍受到相当的限制。更进一步，与用户交互的数据模式仍然有一些散乱的代表性特征，特别名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

5、- - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 是关于数据收集的描述（如个人名目） 。三个仍然需要提高的数据独立性的主要类型是：排序依赖，索引依赖和存取路径的依赖。在一些系统中这些依赖之间并不是明确分隔的。1.2.1 顺序依赖。数据库中的数据元素可以有很多种存储方式，一些是不考虑顺序的，一些是允许一个元素只参与一个排序，而另外一些允许每个元素参与多个排序。现在让我们来看看要求或允许数据元素存储在至少一个总排序的现存系统，而这种总体排序是与硬件决定的排序地址密切相关的。这种系统通常允许应用程序自己假定

6、文件记录的表示顺序与其在磁盘上的存储顺序是相同的（或者说是存储排序的子目）。这些运用文件存储顺序有利条件的应用程序，如果由于某些原因而变得需要用一个新排序替换这种顺序时，很可能不能正确运行。以指针方式实现的存储排序也有相似的问题。我们没有必要挑选出任何一个系统作为例子，因为现在上市的所有著名的信息系统在清楚区别表示顺序和存储顺序两方面都是失败的。重要的实现问题必须得到解决来提供这种独立性。1.2.2 索引依赖。 格式化数据的上下文联系中，索引通常被看成数据表示的一个纯粹的效能导向组件。它倾向于提高对查询和更新的响应，同时减慢了对插入和删除的响应。从信息的观点来看，索引是数据表示的冗余构成成分。

7、如果一个系统王全用索引， 并且如果它在变化活动形式的数据库环境中能够表现的很好，那么不时地产生和销毁索引的能力可能是必须的。那么问题产生了：应用程序和终端活动在索引项来去的时候仍然能够不受影响吗？目前格式化数据系统采用很不相同的方法来进行索引。TDMS7 无条件地提供了所有属性上的索引。IMS5 目前发布的版本为用户提供了为每一文件选择的权利：是完全没有索引（层次序列的组织）和只有主键索引（层次化索引序列组织） 之间的选择。 没有一种会使用户的应用逻辑依赖于无条件提供的索引的存在。但是，IDS8 允许文件设计者选择用于索引的属性和指定用于与索引通过外加链的方式组合成文件结构的属性。运用索引链性

8、能的优势的应用程序必须通过名字来引用这些链。如果这些链后来被删除，那么这些程序就无法正确运行。1.2.3 存取路径依赖。 许多现存格式化数据系统为用户提供了树结构的文件或者更一般的数据网络模式。为和这类系统共同工作而发展的应用程序，在树或网格的结构改变时，往往会在逻辑层受到削弱。一个简单的例子如下。设想数据库包含关于部件和工程的信息。对于每一个部件，其部件号码、部件名字、部件描述、在手的数量和订单上的数量的信息都被记录。对于每一个工程，其工程编号、工程名字和工程描述信息被记录。无论什么时候，一个工程要用特定部件时，用于这个工程的那种部件的数量也会被记录。假如系统要求用户或者文件创作者根据树结构

9、声明或者定义数据。那么，任一层次结构都可以用到如上提到的信息上（见结构1 5） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - 现在考虑打印用于名为“alpha “的工程每个部件的编号、部件名和数目。 不考虑可

10、用于面向树的信息系统可以用于解决这个问题，我们可以得到以下的发现。如果程序P 是开发用于解决这个问题（假设结构是上面五种结构中的一种） ，也就是说P 不会检测哪一种结构对他来说有效，然而这样的结果是P至少在其中三个结构上是失败的。更具体地， 如果 P 对结构 5 行之有效， 那么在其他结构上就会失败；如果 P 对结构 3 或 4 行之有效， 那么它至少会在结构 1,2,5 上是失败的；如果P 对结构 1 或 2 行之有效，那么它至少会在结构 3,4,5 上是是小的。对于每一种情况的原因都很简单。在没有经过检测来决定哪种结构是有效的情况下，P 会失败是因为它试图引用一个不存在的文件（现可用的系统

11、把这种情况视为error ）或者是它没有引用包含它必需信息的文件。有疑问的读者应该找一些样例程序来理解这个简单的问题。由于在一般情况下， 开发可以检测系统允许的所有树结构的应用程序是不实际的，而且这种程序在结构需要改变时也会失败。为用户提供网格数据模式的系统也会遇到相似的问题。在树和网格两种情形下，用户（或者是用户的程序）都被要求采用用户数据存取路径的集合。这些路径是否与存储表示的指针定义的路径有较近通信是没有影响的，而在IDS 中这种通信时极其简单的，但在TDMS 中就正好相反了。不考虑存储表示来看这种问题，结果就是， 终端活动和程序变得依赖于用户存取路径的连续存在性。对于这个问题的一个解决

12、方案就是采用如下策略：一旦用户存取路径被定义了，那么除非所有应用这个路径的所有程序都废弃了（finish 了） ，否则这个路径就不会过时。 由于在团体总体模式的数据库用户的存取路径的数量最终可能变得过大，因此这种策略是不实际的。1.3 数据的关系视图关系这个词在这里使用的是其被广泛认可的数学意义。给定集合S1,S2,Sn（这些集合没有必要一定是不同的），如果R 是一个满足如下条件的n 元组集合：其每个元素的第一个元素来自S1，第二个元素来自集合S2，以此类推，那么R 就是这n个集合（ S1,S2,Sn）上的一个关系。我们用Sj 来表示 R 的第 j 个域。正如上面所定义， R 被称作是 n 级

13、的。 1 级的关系通常叫做一元关系，2 级的被叫做二元关系，3 级的被叫做三元关系，而n 级的叫 n 元关系。（更简单地说，R 是 S1,S2, ,Sn这n 个集合的笛卡尔乘积的一个子集）说明一下，我们将频繁地使用关系的数组表示，但是必须清楚的是这个特定表示并不是用于解释关系视图必须的部分。用于表示n 元关 R 的数组有如下特征：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - （1）每一行代表R 的一个 n 元组（2）行的排列

14、顺序是无关紧要的（3）所有行都是不相同的（4）列的顺序是有意义的 列应该符合R 定义时的域的顺序S1,s2, ,Sn（但是注意，排序的域和无序的域下标之间的关系）（5）每个列的意义部分是由命名相应域来传达的图 1 中的例子展示了一个叫做supply 4 级的关系， 这个关系显示的是特定工程的特定供应者的特定数量的零件发货过程。图 1 有人可能会问： 如果列由相应域的名字来标识，那么为什么列的顺序会有影响呢？正如图2 中例子显示的一样，两列可以有相同的头（表示同样的域），但是对于这个关系他们有不同的含义。这里描述的关系叫做component 。它是一个三元关系，其中前两个域叫做part 而第三个

15、域叫做quantity 。Component （x，y，z）的意思就是部件x 部件 y 的直接构成成分（或者子部件），而需要 z 个的 x 部件来组成一个的y 部件。这个关系在零件扩大问题中有重要作用。图 2 一个引人注目事实是，一些现存的信息系统（主要是基于树结构文件组织）不能够为有两个或两个以上的相同域的关系提供有效地数据表示。IMS/3605的目前版本就是这种系统的一个实例。一个数据库中的总体数据可以看做一个随着时间变化的关系的集合。这些种类的关系有各种各样的级（或度）。随着时间的前进，每个n 元关系都可能经历插入另外的 n 元组，删除现存的n 元组和改变现存任意n 元组的组成部分的操作

16、。但是，在很多商业、政府和科学数据库中，一些关系的度（或作级别）是相当高的（30 级的关系也是很常见的）。 用户通常不能记住任何关系的所有域的顺序（例如，关系 supply 中定序的提供者、零件、工程和数量）。因此，我们提出用户不必处理域排序的关系，而处理与其非排序域的有同样效果的关系的方法。为了达到这个目的， 关系中的域必须是在不采用位置时唯一可确认的，至少在某个给定的关系中是这样的。 因此， 在有两个或更多相同域的地方，我们要求对每一种情况下域名都是合格的不同的角色名（role name） ，这些角色名用于识别给定的关系中的域所扮演的角色。例如，在图2 的 component 关系中，第一

17、个域part 可以用合格角色名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - 名 sub 指示，而第二个用super ，以便用户能够处理component关系和它的域sub.partsuper.part,quantity 而不用考虑这些域之间的任何排序。总之， 提出多数用户应该与由随时间变化的联系集合（而不是关系） 组成的数据的关系模式交互。 每个用户不必知道除了关系的名字和其相应的域的名字外的其它更多信息（只要有需要就可以采用

18、角色资格）。甚至信息可以是系统（具有安全和隐私约束）根据用户的请求以菜单形式提供的。数据库关系模型的建立通常还有其他很多可供选择的方法。为了讨论更好的方式（或标准形式） ，我们必须引入另外几个概念（活动域、主码、外码、非单一域）并建立一些与目前在信息系统编程中使用的术语的链接。在本文后面的部分，我们将不再烦恼地去区别关系（relation ）和联系（ relationship ） ，而在需要显示他们不同之处的地方我们会显示地指出。下面考虑这样一个数据库实例，该数据库包含关于部件，工程和供应者的一系列关系。一个叫part 的关系被定义在以下的域上：（1）部件编号（ part number）（2）

19、部件名称（ part name ）（3）部件颜色（ part col or）（4）部件重量（ part weight ）（5）在手的数量（ quantity on hand ）（6）预订的数量（ quantity on ord er）可能还有其他的域。事实上， 每个这样的域都是一池数值，这些数值中的一些或全部可以在任一瞬时在数据库中表示出来。可以想象， 在某些瞬间， 所有部件颜色都被显示出来， 但是难以做到的是把所有可能存在的部件的重量、部件名字和部件编号都显示出来。 我们称在某个时刻表现出来的值的集合为在那个时刻的活动域（active domain ） 。通常， 一个给定关系的一个域（或者域

20、的组合）有一组唯一识别该关系的每一元素（ n 元组）的值。这样的一个域（或组合）被叫做主码（primary key） 。在上面的例子中， 部件号可能是一个主码，而部件颜色可能就不是了。主码是非冗余的，如果他满足它是一个简单域（非组合的） 或者一个组合， 而对于组合的情况，在唯一识别每一元素时参与到这个组合中的简单域没有一个是多余的（也就是组合中的所有的简单域共同构成一个唯一识别关系元素的码）。一个关系可以有多个非冗余的主码。如果上面所说的部件的名字都互不相同，那么就成了这种情况的一个实例。无论什么时候， 只要一个关系有两个或者更多非冗的主码，它们中的任意一个都可以选作这个关系的主码。一个普遍的

21、要求就是， 关系当中的元素交叉引用同一关系的其他元素或者引用一个不同关系的元素。码提供了一种用于表示这种交叉引用的面向用户的方式（但不是唯一的方式） 。如果一个域（或者域组合）不是关系R 的主码，但是它的元素是某个关系S 的主码值（排除S和 R 是同一关系的可能） ，那么我们就把关系R 的这个域（或者域组合）叫做外码。在图1supply关系中， supplier 、part 、project是主码，而这三个域中每一个都被单独看作是一个外码。在前面的工作中已经显现出一个很强的趋势，即把一个数据库中的数据看成由两个部分组成，一个部分由实体描述组成（如supplier的描述），而另一个部分由不同实体

22、间或者实体类型间的关系组成（如 supply 关系）。当一个关系有任何其他关系的外码时， 要维持这种区别是困难的。在用户的关系模式中，做出这样的区别似乎是没有益处的（但是， 当把关系概念用于用户联系集的机器表示时，这种区分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 可能有些益处） 。到目前为止， 我们已经讨论了一系列定义在简单域上的关系的例子，而那些简单域的元素是原子的（非组合的）值。非原子值会在关系框架中讨论。因此，一些

23、域可以把关系当做元素。相应地， 这些关系可以被定义在非简单域等等。例如， 关系 empl oyee 定义的其中一个域可以是salary history （薪水历史） 。Salary history域中的一个元素是一个定义在date 域和 salary 域上的二元关系。Salary history 域就是这种二元关系的一个集合。在数据库中任意瞬间都会有与empl oyee（员工）数量相同的salary history关系实例。相比之下，employee 关系就只有一个实例。在表示数据库的术语中属性和重复组分别在简单域和非简单域中是大致相似的。现在术语中的多混淆之处是由于没能把类型和实例（如在“r

24、ecord ”中）区别开和把数据的用户模式的组成和它们相应的机器表示区别开（再次以“record ”为例）。1.4 标准形式一种所有域都是简单域的关系能够用如上讨论过的二维的齐次列数组来表示其存储形式。一些更为复杂的数据结构对一个有一个或多个非简单域的关系是必要的。由于这个原因（其他的将在下面举例），消除非简单域的潜力似乎值得投资。事实上，有一种简单的消除过程，而我们把这个过程叫做标准化。例如， 考虑图 3（a）显示的关系集合。Job history 和 children 是 empl oyee 关系的非简单域。 Salary history是 job history的一个非简单域。图 3（a

25、）中的树展示了各个非简单域之间相互关系。图 3（ a）图 3（b）标准化按如下程序进行。从关系的树顶端开始，记住它的主码，并且通过插入主码域或者域组合来扩展每个直属的下层关系。每个扩展关系的主码由从父关系（即上一层的关系）拷贝下来主码在进行扩大前的主码构成。现在，从父关系中化掉所有非简单域，删除树的顶节点，并且在留下的子树上重复同样的操作程序。图 3（a）中标准化关系集合的结果就是图3（b）中的集合。每个关系的主码都用斜体表示以显示这些码值是如何通过标准化来扩展的。如果要使得如上所述的标准化是可用的，那么关系集合的非标准化必须满足如下条名师资料总结 - - -精品资料欢迎下载 - - - -

26、- - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - 件：（1）非简单域之间的相互关系图是一个树集合。（2）没有主码是由非简单域构成的作者不知道哪个应用是不严格满足以上这些条件的。那这类标准化的更进一步的操作就可进行了。这些在本文中不会讨论。当所有关系都以标准形式出现时，变得可行的数组表示的简单性不仅有利于存储的目的，而且有利于广泛采用不同数据表示的系统之间的大量数据的通信。这种通信形式是数组表示的一个相称的压缩版本，并且有如下有利条件：（1）没有指针（值地址或值替换）（2）避免了所有对哈

27、希选址方式的依赖性（3）不包含索引和有序列表如果用户的关系模式以标准形式建立，那么数据库中数据项的名字可以是一种更简单的形式，反之亦然。一个通用的名字有如下形式：R (g).r.d 其中 R 是关系名字；g 是同辈标识符（可选的）；r 是角色名（可选的）；d 是域名。由于 g只有在当一个给定的关系中多个同辈存在时才需要，而且 r 只有在当关系R 有两个或更多名为d 的域时才需要，所以简单形式R.d 通常是恰当的。1.5 一些语言方面如上所述，数据关系模式的采用使基于实用谓词演算的通用数据子语言的发展成为可能。如果关系结合是标准形式的，那么一阶谓词演算就足够了。这种语言为所有其它提议的数据语言提

28、供了语言影响力的一个衡量标准，并且它自己也是嵌入（有适当的句法修改）在许多其它主流语言（编程，面向命令的或面向问题的）中的一种强势的候选者。虽然详细地描述这样一种语言不是本文的目的，但是它显著的特征有如下几点。我们用 R 标记数据子语言，用H 标记主语言。 R 允许关系及他们的域的声明。每一个关系的声明都为这个关系确定了它的主键。声明过的关系被添加到系统资料库，从而被任何拥有合适权限的使用者群体的一员使用。H 允许支持声明，这些声明可能没那么永久性的表明了这些关系在存储时时如何表示的。R 允许定义数据库中的任何数据子集的检索。这样的一个检索请求之后能发生的动作受制于安全限制条件。数据子语言的普

29、适性是由它的描述能力决定的（而非它的计算能力） ，在一个大型数据库中，每一个数据子集都拥有大量的可能的（而且合理的）描述。即使我们假设（正如我们所做的）系统有权使用的、确定搜索数据合格性的功能子程序的有限集合只有一个。因此，能够应用于集规范资格表达式的集合的必须拥有对应用谓词演算的格式规范的公式集合的描述能力。众多周知，为了维护这种描述能力，不必要表示（无论选择的是什么语法）选中的谓词演算的所有公式。比如，那些以前束规范格式的就够了。在搜索体验行业的合格性或其他方面可能要用到算术函数。这些函数用H 语言定义，用R 语言调用。这样指定的一个集合可能仅用于查询，或者用于可能发生的变化。插入采用向已

30、声明的关系中加入新的元素的形式实现，同时不考虑在机器中表示的顺序。删除对公共组都有效（而不是个人用户或子组），删除以从已声明的关系中移除元素的形式实现。如果指定关系之间的删除和更新依赖性已经用R 语言声明，那么一些删除和更新可能会由其他的删除和更新引发产生。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - 用这种视图看数据，对查询数据的语言有一个重大的影响，这个影响就是数据元素和集合的命名。这其中的一些方面已经在上一节讨论过。使

31、用通常的网络视图，用户常常为创造和使用更多的而不是完全有必要的关系名称所累。因为名称适合路径（或路径类型）有关，而不是和关系有关。一旦用户意识到存储了某个特定的关系，他会希望使用他的已知参数和未知参数的任意组合来利用这个关系，因为信息（如珠穆朗玛峰）是存在的。这是一个系统特征，我们叫做（逻辑上）关系的对称利用。当然，性能上的对称性是不可能的。为了支持一个二元关系的对称性利用，需要两条直接路径。对于一个n 元的关系，被命名和控制的路径数量是n 的阶乘。同样，如果采取这样的关系视图：每一个n元关系必须被用户以只包含2 元关系的一张网状表达式表示出来（比如，参见Feldman s LEAP 系统），

32、那么必须创造2n-1 个名称而不仅仅是1.2 节描述的n+1个拥有直接n 元标记的名称。例如，图片1 这的 4 元关系 supply ，它以 n 元标记初始化了 5 个名称，用如下形式表示P (supplier, & (part, R (project, quantity) 以网状二元标记，包含7 个名称。这种表示方式的进一步的缺点是它的不对称性。尽管这种不对称性不会禁止对称性利用，它肯定会使用户的一些询问操作很不方便表示（比如，对于跟给定的使用 Q 和 R 写的项目相关的那些部分和数量的查询）。1.6 可表达的、已命名的而且已存储的关系有两个关系集合跟资料库有关：命名集和可表达集。命名集市用

33、户群能够通过一个简单名字（或标识）识别的所有关系的集合。当恰当授权的用户声明R 时，关系 R 拥有了命名集的成员资格。当恰当授权的用户取消R 的声明时，它失去了成员资格。可表达集是能够用数据语言中的表达式表示的所有关系的集合。这些表达式是由名字集中关系的简单名字组建起来的。阶段的名称、角色和域、逻辑连接词、谓词演算的量词以及某些常量关系符号，如= ， 。名字集是可表达集的一个子集 通常是一个很小的子集。由于名称集合中的某些关系可能是集合中其它关系的时间无关的组合，将名称集和定义这些时间无关的限制条件的语句的集合联系起来考虑很有用。我们将推迟讨论这个，直到我们介绍了对关系的几种操作（参看第二节）

34、。为用户设计一个支持关系模型的数据系统时，设计者所面临的主要问题之一是确定支持存储表示所用的集合。理想情况下，允许的数据表现形式的多样性应该正好足够覆盖性能安装总集合要求的范围。太大的范围导致不必要的存储开销和连续的对当先结构描述的重新解释。对于任意选定的存储表示集合，数据系统必须提供把用关系模型的数据语言表达的用户需求转换成相应且有效的当前存储表示的方法。对于高层数据语言，这好似一个具有挑战性的设计问题。不过，随着更多的用户拥有了对大型资料库的访问权限，这就变成了一个必须解决的问题。同时，也能为从个人用户到数据系统提供有效的响应和吞吐量。2冗余和兼容2.1 对关系的操作由于关系是集合，所有普

35、通的集合操作也都适用于关系。不过，结果可能不是一个关系，比如，一个二元关系和三元关系的连接不是一个关系。下面讨论的操作是专门针对关系的。介绍这些关系是因为它们在从其他关系中派生出关系上扮演重要角名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - 色。它们主要应用在非推理的信息系统中，这种系统不提供逻辑推理服务，尽管当类似的服务被添加后不一定会损害它们的适用性。大多数用户不会直接关心这些操作。然而，信息系统设计人员和与资料库控制相关

36、的人员应该彻底熟悉它们。2.1.1 置换。一个二元关系有一个具有两列的数组表示。将这两个列换位得到逆关系。更一般的， 如果一个置换被应用于一个n 元关系的列， 由此产生的列被称作给定序列的排列。例如， 图 1 中有关系supply 的 4！=24 种排列， 如果我们包括不改变列顺序的恒等排列。2.1.2投影。假设我们从一个关系中选出特定的某些列（剔除其它的列），然后从结果中删除数组中的任何行重复。最终的数组表示了一个叫做给定关系的投影的关系。选择算子 被用来获取任何所需的排列、投影或两个操作的组合。因此， 如果 L 是 K 个标记的列表L = i1, i2, , ik，R 是一个 n 元关系（

37、n=k ）,那么 L（R）一个 k 元关系，这个关系的第j 列是 R 的第 ij 列（ j=1, 2, ,k），同时结果的行中的冗余也将移除。考虑图1 中的关系supply ，图 4 展示了这个关系的置换投影。注意，在这个特殊的情况下，投影比产生该投影的关系的n 元组要少。2.1.3 连接。 假设给定两个二元关系，它们有一部门共同域。在什么情况下我们可以结合这两个关系，以形成一个三元关系，其中保留了所给关系的所有信息？图5中的例子显示了两个可以进行无信息损失连接的两个关系R,S ，图 6显示了R和S的连接。如果存在一个三元关系U， 满足12（U ) = R 且23 (U) = S.，则二元关系

38、 R和S 则是可连接的。任意这样的三元关系都叫做R和S的连接。如果R,S是二元关系且2（R）=1（S），则 R和S是可连接的。 自然连接是肯定存在的一个连接，定义为R*S = (a, b, c):R(a, b) A S(b, c) 其中，如果（ a,b）是R的一个成员且和S(b,c)相似，则 R(a,b) 的值是真。即12 (R*S) = R 且23 (R*S) = S. 注意，图 6中显示的连接是图5中的 R和 S的自然连接，图7显示了；另一个连接。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

39、- - - 第 10 页，共 17 页 - - - - - - - - - 检查这些关系展示了域part（连接操作发生的域）中的一个元素（元素 1） ，该元素有性质：它拥有在R 和 S 中不止一个关系。正是这个元素引起了连接的多元化。在连接域里这样的元素叫做有关R 和 S 连接的歧义点。如果21（R ）或 R 是一个函数， 在 R 和 S的连接中不会出现歧义点。在这种情况下， R 和 S的自然连接就是R 和 S的连接。注意反复的限定“R和 S”是必需的，应为S 可能和 S 可连接（ R 和 S 同样），而且这个连接应该完全分开考虑。在图5 中，关系 R，21（R ）， S，21（S ）都不是一

40、个函数。R 和 S连接中的歧义点有时可以用其它关系消除。假设我们被给定，或者可以从 R,S中产生一个关系T，关系在域project 和 supplier 上拥有以下性质：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - 这样我们可能形成R,S,T 的三路连接，也就是一个三从关系，如下：这样的一个连接被叫做循环三路连接以和线性三路连接区别开来，后者将会是一个四元关系V，如下：尽管可能存在不止一个循环三路连接（参看图8，9），这种

41、情况可能发生的环境比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 有这个属性。3 个 2 元关系 R,S,T的自然线性三路连接如下：其中，因为是2 元自然连接 ,等号左边不用圆括号。为了获取循环副本，我们引入操作符号r,它可以通过将一个n 元关系的首位相连产生一个n-1 元的关系。因此

42、，如果R 是一个 n 元关系（ n=2 ）， R 产生的环由下面的公示定义：我们现在可以用下面的表达式表示R,S,T的自然循环三路连接：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - 线性概念，循环S-连接和 n 元关系的连接的自然副本的扩展很明显。然而，考虑到一些进行连接的关系不一定是二元的，所以可能需要一些额外的描述。考虑关系R（r 元），S （ s 元）的情况，在它们的p 个域上连接两个关系。简单的说， 假设这 p 个

43、域是 R 的 r 个域中的最后p 个域和 S的 s 个域中的前p个域。如果不是这样，我们可以总是采用适当的排列使它这样。现在，取得R的前 r-p 个域的笛卡尔乘积，并且叫这个新的域为A。取得 R 的后 p 个域的笛卡尔乘积，并称之为B。取得 S的后 s-p 个域的笛卡尔乘积，并称之为C。我们可以把R 看作是在域A.B 上的二元函数。类似的，我们可以把S 看作是域B,C 上的二元关系。线性和循环S-连接的概念现在成为可以直接接受的了。可以对线性的和各种元的n 个关系的循环n 元连接也采用这种方法。2.1.4组成。读者很可能对应用在函数上的组成概念非常熟悉。我们将会讨论这个概念的概括而且首先把它应

44、用到二元关系上。我们对组成和可组合型的定义是直接基于以上给出的联合和可联合性的定义上的。假设我们被给予两个关系R,S。T 是 R 和 S 的组合，如果存在一个R 和 S的连接且满足。因此，当且仅当两个关系是可连接的时，它们是可组合的。 然而，存在多于一个的R 和 S的连接并不意味着存在多余一个的 R 和 S的组合。与 R 与 S 的自然连接相应的是S伴随 R 的自然组成，定义为：R?S = 13（R*S）将关系 R 和 S从表 5 中提取出来看， 他们的天然组成由表10 展示，而另一个组成由表11 展示（与表 7 展示的连接相区别）表 10. S 伴随 R 的天然组成（由表5 所得）表 11.

45、 S 伴随 R 的另一个组成（由表5 所得）当存在 2 个或更多的连接时，不同的组成数量可能少至1 个也可能多至与不同连接数目相同。表12 展示了一个有许多连接关系但是只有一个组成的2 个关系的例子。注意到在由S 组成 R 时，点 c 的不确定性丢失了，因为通过点 a,b,d,e 造成了确定性的关联。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - 表 12. 多个连接，只有一个组成多对非必须二元 （可能是多维的） 的关系的组

46、成的扩展与这种关系成对连接的情况如出一辙。对于关系组合了解的缺乏导致许多系统设计员陷入了一种我们称为连接陷阱的困境。 这种陷阱可能被依照以下举例描述。假设每个供应商的描述与供应商供应的每一部分的描述相关联，并且每一部分的描述近似地与使用这些部分的工程描述相关联。通常， 现在就可以得出一个错误的结论：换句话说， 如果所有可能的通道通过供应商在工程中供应的部分来遵循供应商，就可以得到一个该供应商供应的所有工程的有效集。这样一个结论只有在非常特殊的情况下才是正确的， 即是目标的工程和供应商关系实际上是另两个关系的自然组成 而我们通常必须加上一个词“ 对于所有时间 ” ，因为这通常是在跟踪控制技术的要

47、求中暗示到的。*别的作者倾向于忽略组成而不是自然组成，于是把这一特别的组成看做“ 那个组成” 看，举个例子， Kelley 的”General Topology ”.2.1.5 限制。一个关系的子集还是一个关系。关系S 可能对关系R 操作从而形成一个 R 的子集的一种途径是通过S对 R 进行限制操作。这个操作是函数对子集的域的限制的一般化，它的定义如下。设 L,M 为等长目录列表， L=i1,i2, , ik， M=j1, j2, jk其中 kR的维数且kS的维数。则L,M 对由 S对 R 的限制 RL|MS表示 R 的最小子集R ，L（R ）= M(S)。这个操作只有当相等可以对于h=1,2

48、, ,k ，应用到ih(R)的成员和jh(R)之间才被定义。表 13 中 R,S,R这 3 个关系满足等式R = R(2,3)|(1,2)S。表 13. 限制举例我们现在立足于考虑这些操作在关系上的应用。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - 2.2 冗余一个指定关系集的冗余必须可以与存储陈述集的冗余相区别。在这里我们主要关心的是前者。首先，我们需要一个关于关系的可导出性的精确概念。假设 是关系上的一个操作集合，而且

49、每个操作都有对每个操作数产生一个唯一关系的性质（因此自然连接是合理的，但是连接是不合理的）。如果一个关系R 在所有情况下存在一个集合的操作序列， 使 R 从 S 的一个成员中产生， 则 R 对一个关系集合S -可导。 “ 在所有情况下 ” 这一描述是现在时的，因为我们正在处理随时间变化的关系，而且我们的兴趣在于保持一段关键时期的可导性。对于非推理性系统上的指定关系，似乎一个恰当的集合1包含了一下操作：投影，自然连接，束缚和限制。排列是不相干的且自然成分需要被包含，因为在进行连接然后投影的情况下是可行的。对于表示的存储集来说，一个恰当的对2集合的操作会包含排列和更多的关于子集合和合并关系的操作，

50、并且排列和关联它们的元素。2.2.1 强冗余。如果一个关系集包含了最少一个关系，这个关系控制了一个不同于其他关系集投影的投影，我们就称这个关系集是强冗余的。以下两个例子是为了解释为什么强冗余性是这样定义的，和证明它的实际作用。在第一个关系系列的例子中包含了下面这个关系：Employee( serial #, name, manager#, managername) 其中 serial# 是主键而 manager# 是外键。让我们用 来指定有效域，并假设对于所有时间t 满足：t（manager# ）? t（serial# ）且 t（ managername ）? t（name ）这种情况下的冗余