关系数据库

  关系数据库应用数学方法来处理数据库中的数据。最早将这类方法用于数据处理的是1962年CODASYL发表的“信息代数”，之后有1968年David Child在IBM7090机上实现的集合论数据结构，但系统、严格地提出关系模型的是美国IBM公司的E.F.Codd。
  1970年，E.F.Codd在美国计算机学会会刊《Communications of the ACM》上发表了题为“A Relational Model of Data for Shared Data Banks”的论文，开创了数据库系统的新纪元。ACM1983年把这篇论文列为从1958年以来的四分之一世纪中具有里程碑意义的25篇研究论文之一。此后，E.F.Codd连续发表了多篇论文，奠定了关系数据库的理论基础。
  20世纪70年代末，关系方法的理论研究和软件系统的研制均取得了丰硕的成果，IBM公司的San Jose实验室在IBM 370系列机上研制的关系数据库实验系统System R历时6年获得成功。1981年，IBM公司又宣布了具有System R全部特征的新的数据库软件产品SQL/DS问世。
  与System R同期，美国加州大学伯克利分校也研制了INGRES关系数据库实验系统，并由INGRES公司发展成为INGRES数据库产品。
  40多年来，关系数据库系统的研究和开发取得了辉煌的成就。关系数据库系统从实验室走向了社会，成为最重要、应用最广泛的数据库系统，大大促进了数据库应用领域的扩大和深入。因此，关系数据模型的原理、技术和应用十分重要。

关系数据结构及形式化定义

关系

  关系模型的数据结构非常简单，只包含单一的数据结构——关系。在用户看来，关系模型中数据的逻辑结构是一张扁平的二维表。
  关系模型的数据结构虽然简单却能够表达丰富的语义，描述出现实世界的实体以及实体间的各种联系。也就是说，在关系模型中，现实世界的实体以及实体间的各种联系均用单一的结构类型，即关系来表示。
  前面已经非形式化地介绍了关系模型及有关的基本概念。关系模型是建立在集合代数的基础上的，这里从集合论角度给出关系数据结构的形式化定义。

域(domain)

  定义1（域）：域是一组具有相同数据类型的值的集合。例如，自然数、整数、实数、长度小于25字节的字符串集合、 {0,1} 、 {男,女} 、大于等于0且小于等于100的正整数等，都可以是域。

Cartesian乘积(cartesian product)

  定义2（Cartesian乘积）：给定一组域 \(D_1,D_2,\cdots,D_n\) ，允许其中某些域是相同的， \(D_1,D_2,\cdots,D_n\)的Cartesian乘积为

  其中，每一个元素 \((d_1,d_2,\cdots,d_n)\) 叫作一个n元组(tuple)，或简称元组(tuple)。元素中的每一个值 \(d_i\) 叫做一个分量(component)。
  一个域允许的不同取值个数称为这个域的基数(cardinal number)。若 \(D_i(i=1,2,\cdots,n)\) 为有限集，其计数为 \(m_i(i=1,2,\cdots,n)\) ，则 \((D_1,D_2,\cdots,D_n)\) 的基数 \(M\) 为

  Cartesian乘积可表示为一张二维表，表中的每行对应一个元组，表中的每一列来自一个域，例如给出三个域

  则 \(D_1,D_2,D_3\) 的Cartesian乘积为

  其中，(张清玫,计算机专业,李勇)、(张清玫,计算机专业,刘晨)等都是元组。张清玫、计算机专业、李勇、刘晨等都是分量。该Cartesian乘积的基数为 \(2\times 2\times 3=12\) ，也就是说， \(D_1\times D_2\times D_3\) 一共有 \(2\times 2 \times 3 = 12\) 个元组。这12个元组可列成一张二维表，如表1所示

表1 \(D_1,D_2,D_3\) 的Cartesian乘积

关系

  定义3（关系）： \(D_1\times D_2 \times \cdots\times D_n\) 的子集叫做在域 \(D_1,D_2,\times,D_n\) 以上的关系，表示为

  这里 \(R\) 表示关系的名字， \(n\) 是关系的目或度(degree)。

  关系中的每个元素是关系中的元组，通常用 \(t\) 表示。

  当 \(n=1\) 时，称该关系为单元关系(unary relation)，或一元关系。
  当 \(n=2\) 时，称该关系为二元关系(binary relation)。

  关系是Cartesian乘积的有限子集，所以关系也是一张二维表，表的每行对应一个元组，表的每列对应一个域。由于域可以相同，为了加以区分，必须对每列起一个名字，称为属性(attribute)。n目关系必有n个属性。

  若关系中的某一属性组的值能唯一地标识一个元组，而其子集不能，则称该属性组为候选码(candidate key)。若一个关系有多个候选码，则选定其中一个为主码(primary key)。

  候选码的属性称为主属性(prime attribute)。不包含在任何候选码中的属性称为非主属性（non-prime attribute）‌或‌非码属性（non-key attribute）。

  在最简单的情况下，候选码只包含一个属性。在最极端的情况下，关系模式的所有属性是这个关系模式的候选码，称为全码（all-key）。

  一般来说， \(D_1,D_2,\cdots,D_n\) 的Cartesian乘积是没有实际语义的，只有它的某个真子集才有实际含义。例如，可以发现表1的Cartesian乘积中许多元组是没有意义的。因为在学校中一个专业方向有多个导师，而一个导师只在一个专业方向带研究生；一个导师可以带多名研究生，而一名研究生只有一个导师，学习某一个专业。因此，表1中的一个子集才是有意义的，才可以表示导师与研究生的关系，把该关系取名为 \(\text{SAP}\) ，如表2所示。李勇和刘晨是计算机专业张清玫老师的研究生；王敏是信息专业刘逸老师的研究生。

表2 SAP关系

  把关系 \(\text{SAP}\) 的属性名取为域名，即 \(\text{SUPERVISOR}\) , \(\text{SPECIALITY}\) , \(\text{POSTGRADUATE}\) 则这个关系可以表示为

  假设研究生不会重名（这在实际生活中是不合适的，这里只是为了举例方便），则 \(\text{POSTGRADUATE}\) 属性的每一个值都唯一地标识了一个元组，因此可以作为SAP关系的主码。
  关系可以有三种类型：基本关系（通常又称为基本表或基表）、查询表和视图表。其中，基本表是实际存在的表，它是实际存储数据的逻辑表示：查询表是查询结果对应的表；视图表是由基本表或其他视图表导出的表，是虚表，不对应实际存储的数据。
  按照定义2，关系可以是一个无限集合。由于组成Cartesian乘积的域不满足交换律，所以按照数学定义， \((d_1,d_2,\cdots,d_n)\ne(d_2,d_1,\cdots,d_n)\) 。当关系作为关系数据模型的数据结构时，需要给予如下的限定和扩充。

  (1) 无限关系在数据库系统中是无意义的。因此，限定关系数据模型中的关系必须是有限集合。
  (2) 通过为关系的每个列附加一个属性名的方法取消关系属性的有序性，即 \((d_1,d_2,\cdots,d_i,d_j,\cdots,d_n)=(d_1,d_2,\cdots,d_j,d_i,\cdots,d_n)\quad(i,j=1,2,\cdots,n)\)

  因此，基本关系具有以下6条性质。

  (1) 列是同质的(homogeneous),即每一列中的分量是同一类型的数据，来自同一个域。
  (2) 不同的列可出自同一个域，称其中的每一列为一个属性，不同的属性要给予不同的属性名。例如，在上面的例子中，也可以只给出两个域： \[ \begin{aligned} &\text{人(PERSON)}=\set{张清玫，刘逸，李勇，刘晨，王敏}\\[5pt] &\text{专业(SPECIALITY)}=\set{计算机专业，信息专业} \end{aligned} \tag{7} \]    \(\text{SAP}\) 关系的导师属性和研究生属性都从 \(\text{PERSON}\) 域中取值。为了避免混淆，必须给这两个属性取不同的属性名，而不能直接使用域名。例如，定义导师属性名为 \(\text{SUPERVISOR-PERSON}\) （或 \(\text{SUPERVISOR}\) ）研究生属性名为 \(\text{POSTGRADUATE-PERSON}\) （或 \(\text{POSTGRADUATE}\) ）
  (3) 列的顺序无所谓，即列的次序可以任意交换。由于列顺序是无关紧要的，因此在许多实际关系数据库产品中增加新属性时，永远是插至最后一列。
  (4) 任意两个元组的候选码不能取相同的值。
  (5) 行的顺序无所谓，即行的次序可以任意交换。
  (6) 分量必须取原子值，即每一个分量都必须是不可分的数据项。

  关系模型要求关系必须是规范化(normalization)‌的，即要求关系必须满足一定的规范条件。这些规范条件中最基本的一条就是，关系的每一个分量必须是一个不可分的数据项。规范化的关系简称为范式（Normal Form，NF）。范式的概念将在第6篇关系数据理论中做进一步讲解。 例如，表3虽然很好地表达了导师与研究生之间的一对多关系，但由于属性 \(\text{POSTGRADUATE}\) 中分量取了两个值，不符合规范化的要求，因此这样的关系在数据库中是不允许的。通俗地讲，关系表中不允许还有表，简言之不允许“表中有表”。直观地描述，表3中还有一个小表。

表3 非规范关系

关系模式

  在数据库中要区分型和值。关系数据库中，关系模式是型，关系是值。关系模式是对关系的描述，那么一个关系需要描述哪些方面呢？
  关系是元组的集合，因此关系模式必须指出这个元组集合的结构，即它由哪些属性构成，这些属性来自哪些域，以及属性与域之间的映像关系。
  现实世界随着时间在不断地变化，因而在不同的时刻关系模式的关系也会有所变化。但是，现实世界的许多己有事实和规则限定了关系模式所有可能的关系必须满足一定的完整性约束条件。这些约束或者通过对属性取值范围的限定，例如职工年龄小于60岁（60岁以后退休），或者通过属性值间的相互关联反映出来。例如，如果2个元组的主码相等，那么元组的其他值也一定相等，因为主码唯一标识一个元组，主码相等就表示这是同一个元组。关系模式应当刻划出这些完整性约束条件。

  定义4（关系模式）：关系的描述称为关系模式(relation schema)。它可以形式化地表示为

  其中 \(R\) 为关系名， \(U\) 为组成该关系的属性名集合， \(D\) 为 \(U\) 中属性所来自的域， \(\text{DOM}\) 为属性向域的映像集合， \(F\) 为属性间数据的依赖关系集合。
  属性间的数据依赖将在后篇讨论，本章中关系模式仅涉及关系名、各属性名、域名、属性向域的映像四部分，即 \(R(U,D,\text{DOM})\) 。

  例如，在上面例子中，由于导师和研究生出自同一个域——人，所以要取不同的属性名，并在模式中定义属性向域的映像，即说明它们分别出自哪个域，如：

  关系模式通常可以简记为

  或

  其中 \(R\) 为关系名， \(A_1,A_2,\cdots,A_n\) 为属性名。而域名及属性向域的映像常常直接说明为属性的类型、长度。
  关系是关系模式在某一时刻的状态或内容。关系模式是静态的、稳定的，而关系是动态的、随时间不断变化的，因为关系操作在不断地更新着数据库中的数据。例如，学生关系模式在不同的学年，学生关系是不同的。在实际工作中，人们常常把关系模式和关系都笼统地称为关系，这不难从上下文中加以区别，希望读者注意。

关系数据库

  在关系模型中，实体以及实体间的联系都是用关系来表示的。例如导师实体、研究生实体、导师与研究生之间的一对多联系都可以分别用一个关系来表示。在一个给定的应用领域中，所有关系的集合构成一个关系数据库。
  关系数据库也有型和值之分。关系数据库的型也称为关系数据库模式，是对关系数据库的描述。关系数据库模式包括若干域的定义，以及在这些域上定义的若干关系模式。关系数据库的值是这些关系模式在某一时刻对应的关系的集合，通常就称为关系数据库。

关系模型的存储结构

  我们已经知道，在关系数据模型中实体及实体间的联系都用表来表示，但表是关系数据的逻辑模型.在关系数据库的物理组织中，有的关系数据库管理系统中一个表对应一个操作系统文件，将物理数据组织交给操作系统完成；有的关系数据库管理系统从操作系统那里申请若干个大的文件，自己划分文件空间，组织表、索引等存储结构，并进行存储管理。

关系操作

  关系模型给出了关系操作的能力的说明，但不对关系数据库管理系统语言给出具体的语法要求，也就是说不同的关系数据库管理系统可以定义和开发不同的语言来实现这些操作。

基本的关系操作

  关系模型中常用的关系操作包括查询(query)操作和插入(insert)、删除(delete)、修改(update)操作两大部分。关系的查询表达能力很强，是关系操作中最主要的部分。查询操作又可以分为选择(select)、投影(project)、连接(join)、除(divide)、并(union)、差(except)、交(intersection)、Cartesian乘积等。其中选择、投影、并、差、Cartesian乘积是5种基本操作，其他操作可以用基本操作来定义和导出，就像乘法可以用加法来定义和导出一样。

关系数据语言的分类

  早期的关系操作能力通常用代数方式或逻辑方式来表示，分别称为关系代数(relational algebra)‌和关系演算(relational calculus)‌关系代数用对关系的运算来表达查询要求，关系演算则用谓词来表达查询要求。关系演算又可按谓词变元的基本对象是元组变量还是域变量分为元组关系演算和域关系演算。一个关系数据语言能够表示关系代数可以表示的查询，称为具有完备的表达能力，简称关系完备性。已经证明关系代数、元组关系演算和域关系演算三种语言在表达能力上是等价的，都具有完备的表达能力。
  关系代数、元组关系演算和域关系演算均是抽象的查询语言，这些抽象的语言与具体的关系数据库管理系统中实现的实际语言并不完全一样。但它们能用作评估实际系统中查询语言能力的标准或基础。实际的查询语言除了提供关系代数或关系演算的功能外，还提供了许多附加功能，例如聚集函数(aggregation function)。关系赋值、算术运算等，使得目前实际查询语言的功能十分强大。
  另外，还有一种介于关系代数和关系演算之间的结构化查询语言(Structured Query Language,SQL)。SQL不仅具有丰富的查询功能，而且具有数据定义和数据控制功能，是集查询、数据定义语言、数据操纵语言和数据控制语言(Data Control Language,DCL)于一体的关系数据语言。它充分体现了关系数据语言的特点和优点，是关系数据库的标准语言。因此，关系数据语言可以分为三类：

图1 关系数据语言

  特别地，SQL语言是一种高度非过程化的语言，用户不必请求数据库管理员为其建立特殊的存取路径，存取路径的选择由关系数据库管理系统的优化机制来完成。例如，在一个存储有几百万条记录的关系中查找符合条件的某一个或某一些记录，从原理上讲可以有多种查找方法。例如，可以顺序扫描这个关系，也可以通过某一种索引来查找。不同的查找路径（或者称为存取路径）的效率是不同的，有的完成某一个查询可能很快，有的可能极慢。关系数据库管理系统中研究和开发了查询优化方法，系统可以自动选择较优的存取路径，提高查询效率。

关系的完整性

  关系模型的完整性规则是对关系的某种约束条件。也就是说关系的值随着时间变化时应该满足一些约束条件。这些约束条件实际上是现实世界的要求。任何关系在任何时刻都要满足这些语义约束。
  关系模型中有三类完整性约束：实体完整性(entity integrity)、参照完整性(referential integrity)和用户定义的完整性（user-defined integrity）。其中实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称作是关系的两个不变性，应该由关系系统自动支持。用户定义的完整性是应用领域需要遵循的约束条件，体现了具体领域中的语义约束。

实体完整性

  关系数据库中每个元组应该是可区分的，是唯一的。这样的约束条件用实体完整性来保证。

  实体完整性规则：若属性（指一个或一组属性） \(A\) 是基本关系 \(R\) 的主属性,则 \(A\) 不能取空值(null value)。所谓空值就是“不知道”或"不存在”或“无意义”的值。
  按照实体完整性规则的规定，如果主码由若干属性组成，则所有这些主属性都不能取空值。例如选修（学号，课程号,成绩）关系中，“学号、课程号”为主码，则“学号”和“课程号”两个属性都不能取空值。

  对于实体完整性规则说明如下：
  (1) 实体完整性规则是针对基本关系而言的。一个基本表通常对应现实世界的一个实体集。例如学生关系对应于学生的集合。
  (2) 现实世界中的实体是可区分的，即它们具有某种唯一性标识。例如每个学生都是独立的个体，是不一样的。
  (3) 相应地，关系模型中以主码作为唯一性标识。
  (4) 主码中的属性即主属性不能取空值。如果主属性取空值，就说明存在某个不可标识的实体，即存在不可区分的实体，这与(2)相矛盾，因此这个规则称为实体完整性。

参照完整性

  现实世界中的实体之间往往存在某种联系，在关系模型中实体及实体间的联系都是用关系来描述的，这样就自然存在着关系与关系间的引用。先来看三个例子。

  例1：学生实体和专业实体可以用下面的关系来表示，其中主码用下划线标识。

  这两个关系之间存在着属性的引用，即学生关系引用了专业关系的主码“专业号”显然，学生关系中的“专业号”值必须是确实存在的专业的专业号，即专业关系中有该专业的记录。也就是说，学生关系中的某个属性的取值需要参照专业关系的属性取值。

  例2：学生、课程、学生与课程之间的多对多联系可以如下三个关系表示：

  这三个关系之间也存在着属性的引用，即选修关系引用了学生关系的主码“学号”和课程关系的主码“课程号”。同样，选修关系中的“学号”值必须是确实存在的学生的学号,即学生关系中有该学生的记录；选修关系中的“课程号”值也必须是确实存在的课程的课程号，即课程关系中有该课程的记录。换句话说，选修关系中某些属性的取值需要参照其他关系的属性取值。

  不仅两个或两个以上的关系间可以存在引用关系，同一关系内部属性间也可能存在引用关系。

  例3：在 \(学生（\underline{学号}，姓名，性别，专业号，年龄，班长）\) 关系中，“学号”属性是主码，“班长”属性表示该学生所在班级的班长的学号，它引用了本关系“学号”属性, 即“班长”必须是确实存在的学生的学号。

  这三个例子说明关系与关系之间存在着相互引用、相互约束的情况。下面先引入外码 的概念，然后给出表达关系之间相互引用约束的参照完整性的定义。

  定义5（参照关系）：设 \(F\) 是基本关系 \(R\) 的一个或一组属性，但不是关系 \(R\) 的码， \(K_s\) 是基本关系 \(S\) 的主码。如果 \(F\) 与 \(K_s\) 相对应，则称 \(F\) 是 \(R\) 的外码(foreign key)，并称基本关系 \(R\) 为参照关系(referencing relation)，基本关系 \(S\) 为被参照关系(referenced relation)‌或目标关系(target relation)，关系 \(R\) 和 \(S\) 不一定是不同的关系。

图2 参照关系与被参照关系

  显然，目标关系 \(S\) 的主码 \(K_s\) 和参照关系 \(S\) 的外码 \(F\) 必须定义在同一个（或同一组） 域上。

  在例1中，学生关系的“专业号”属性与专业关系的主码“专业号”相对应，因此“专业号”属性是学生关系的外码。这里专业关系是被参照关系，学生关系为参照关系。如图3(a)所示。
  在例2中，选修关系的“学号”属性与学生关系的主码“学号”相对应：选修关系的“课程号”属性与课程关系的主码“课程号”相对应，因此“学号”和“课程号”属性 是选修关系的外码。这里学生关系和课程关系均为被参照关系，选修关系为参照关系。如图3(b)所示。
  在例3中，“班长”属性与本身的主码“学号”属性相对应，因此“班长”是外码。这里，学生关系既是参照关系也是被参照关系。如图3(c)所示。

图3 关系的参照图

  需要指出的是，外码并不一定要与相应的主码同名，如例2.3中学生关系的主码为学号，外码为班长。不过，在实际应用中为了便于识别，当外码与相应的主码属于不同关系时，往往给它们取相同的名字。

  参照完整性规则就是定义外码与主码之间的引用规则。

  参照完整性规则：若属性（或属性组） \(F\) 是基本关系 \(R\) 的外码，它与基本关系 \(S\) 的主码 \(K_s\) 相对应（基本关系 \(R\) 和 \(S\) 不一定是不同的关系），则对于 \(R\) 中每个元组在 \(F\) 上的值必须：
  ◦或者取空值（ \(F\) 的每个属性值均为空值）。
  ◦或者等于 \(S\) 中某个元组的主码值。

  例如，对于例1，学生关系中每个元组的“专业号”属性只能取下面两类值：
  ◦空值，表示尚未给该学生分配专业。
  ◦非空值，这时该值必须是专业关系中某个元组的“专业号”值，表示该学生不可能分配到一个不存在的专业中。即被参照关系“专业”中一定存在一个元组，它的主码值等于该参照关系"学生"中的外码值。

  对于例2，按照参照完整性规则，“学号”和“课程号”属性也可以取两类值：空值或目标关系中已经存在的值。但由于“学号"和"课程号”是选修关系中的主属性，按照实体完整性规则，它们均不能取空值，所以选修关系中的"学号”和“课程号”属性实际上只能取相应被参照关系中已经存在的主码值。
  参照完整性规则中， \(R\) 与 \(S\) 可以是同一个关系。例如对于例3按照参照完整性规则，“班长”属性值可以取两类值：
  ◦空值，表示该学生所在班级尚未选出班长。
  ◦非空值，这时该值必须是本关系中某个元组的学号值。

用户定义的完整性

  任何关系数据库系统都应该支持实体完整性和参照完整性。这是关系模型所要求的。除此之外，不同的关系数据库系统根据其应用环境的不同，往往还需要一些特殊的约束条件。用户定义的完整性就是针对某一具体关系数据库的约束条件，它反映某一具体应用所涉及的数据必须满足的语义要求。例如某个属性必须取唯一值、某个非主属性不能取空值等。例如，在例1的学生关系中，若按照应用的要求学生不能没有姓名，则可以定义学生姓名不能取空值；某个属性（如学生的成绩），的取值范围可以定义在0〜100之间等。
  关系模型应提供定义和检验这类完整性的机制，以便用统一的系统的方法处理它们，而不需由应用程序承担这一功能。
  在早期的关系数据库管理系统中没有提供定义和检验这些完整性的机制，因此需要应用开发人员在应用系统的程序中进行检查。例如在例2的选修关系中，每插入一条记录,必须在应用程序中写一段程序来检查其中的学号是否等于学生关系中的某个学号，并检查其中的课程号是否等于课程关系中的某个课程号。如果等于，则插入这一条选修记录，否则就拒绝插入，并给出错误信息。

关系代数

  关系代数是一种抽象的查询语言，它用对关系的运算来表达查询。任何一种运算都是将一定的运算符作用于一定的运算对象上，得到预期的运算结果。所以运算对象、运算符、运算结果是运算的三大要素。关系代数的运算对象是关系，运算结果亦为关系。关系代数用到的运算符包括两类：集合运算符和专门的关系运算符，如表4所示。关系代数的运算按运算符的不同可分为传统的集合运算和专门的关系运算两类。其中，传统的集合运算将关系看成元组的集合，其运算是从关系的“水平”方向，即行的角度来进行：而专门的关系运算不仅涉及行，而且涉及列。比较运算符和逻辑运算符是用来辅助专门的关系运算符进行操作的。

表4 关系代数运算符

传统的集合运算

  传统的集合运算是二目运算，包括并、差、交、Cartesian乘积4种运算。
  设关系 \(R\) 和关系 \(S\) 具有相同的目 \(n\) （即两个关系都有 \(n\) 个属性），且相应的属性取自同一个域， \(t\) 是元组变量， \(t \in R\) 表示 \(t\) 是 \(R\) 的一个元组。

  可以定义并、差、交、Cartesian乘积运算如下。

并(union)

  关系 \(R\) 与关系 \(S\) 的并记作

  其中 \(\lor\) 是或运算符。其结果仍为 \(n\) 目关系，由属于 \(R\) 或属于 \(S\) 的元组组成。

差(except)

  关系 \(R\) 与关系 \(S\) 的差记作

  其中 \(\land\) 是与运算符。其结果关系仍为 \(n\) 目关系，由属于 \(R\) 而不属于 \(S\) 的所有元组组成。

交(intersection)

  关系 \(R\) 与关系 \(S\) 的交记作

  其结果关系仍为 \(n\) 目关系，由既属于 \(R\) 及又属于 \(S\) 的元组组成。关系的交可以用差来表示，即

Cartesian乘积(cartesian product)

  这里的Cartesian乘积严格地讲应该是广义的Cartesian乘积(extended cartesian product)，因为这里Cartesian乘积的元素是元组。
  两个分别为 \(n\) 目和 \(m\) 目的关系 \(R\) 和 \(S\) 的Cartesian乘积是一个 \((n+m)\) 列的元组的集合。元组的前 \(n\) 列是关系 \(R\) 的一个元组，后所列是关系 \(S\) 的一个元组。若 \(R\) 有 \(k_1\) 个元组，S有 \(k_2\) 个元组，则关系 \(R\) 和关系 \(S\) 的Cartesian乘积有 \(k_1\times k_2\) 个元组。记作

  图4(a)、图4(b)分别为具有三个属性列的关系 \(R\) 、 \(S\) 。图4(c)为关系 \(R\) 与 \(S\) 的并。图4(d)为关系 \(R\) 与 \(S\) 的交。图4(e)为关系 \(R\) 和 \(S\) 的差。图4(f)为关系 \(R\) 和 \(S\) 的Cartesian乘积。

图4 传统集合运算举例

专门的关系运算

  专门的关系运算包括选择、投影、连接、除运算等。为了叙述上的方便，先引入几个记号。

  (1) 设关系模式为 \(R(A_1,A_2,\cdots,A_n)\)，它的一个关系设为 \(R\) 。 \(t \in R\) 表示 \(t\) 是 \(R\) 的一个元组。 \(t[A_i]\) 则表示元组 \(t\) 中相应于属性 \(i\) 的一个分量。
  (2) 若 \(A=\set{A_{i1},A_{i2},\cdots,A_{ik}}\) ，其 \(A_{i1},A_{i2},\cdots,A_{ik}\) 是 \(A_1,A_2,\cdots,A_n\) 中的一部分,则 \(A\) 称为属性列或属性组。 \(t[A]=(t[A_{i1}],t[A_{i2}],\cdots,t[A_{ik}])\) 表示元组 \(t\) 在属性列 \(A\) 上诸分量的集合， \(\bar{A}\) 则表示 \(\set{A_1,A_2,\cdots,A_n}\) 中去掉 \(\set{A_{i1},A_{i2},\cdots,A_{ik}}\) 后剩余的属性组。
  (3) \(R\) 为 \(n\) 目关系， \(S\) 为 \(m\) 目关系。 \(t_r\in R,t_s \in S\) ， \(\overgroup{t_rt_s}\) 称为元组的连接(concatenation)‌或元组的串接。它是一个 \(n+m\) 列的元组，前 \(n\) 个分量为 \(R\) 中的一个 \(n\) 元组，后 \(m\) 个分量为 \(S\) 中的一个 \(m\) 元组。
  (4) 给定一个关系 \(R(X,Z)\) ， \(X\) 和 \(Z\) 为属性组。当 \(t[X]=x\) 时， \(x\) 在 \(R\) 中的象集(images set)‌定义为 \[ Z_x=\set{t[Z]|t \in R, t[X]=x} \tag{19} \]   它表示 \(R\) 中属性组 \(X\) 上值为 \(x\) 的诸元组在 \(Z\) 上分量的集合。
  例如，图5中， \(x_1\) 在 \(R\) 中的象集为 \(Z_{x_1}=\set{{Z_1,Z_2,Z_3}}\) ， \(x_2\) 在 \(R\) 中的象集为 \(Z_{x_2}=\set{Z_2,Z_3}\) ， \(x_3\) 在 \(R\) 中的象集为 \(Z_{x_3}=\set{Z_1,Z_3}\) 。

图5 象集举例

  下面给出这些专门的关系运算的定义。

选择

  选择又称为限制(restriction)。它是在关系 \(R\) 中选择满足给定条件的诸元组，记作

  其中 \(F\) 表示一个选择条件，它是一个逻辑表达式，取逻辑“真”或“假”。
  逻辑表达式 \(F\) 的基本形式为

  其中 \(\theta\) 表示比较运算符，它可以是 \(>,\ge,<,\le,=\) 或 \(<>\) 。 \(X_1,Y_1\) 是属性名，或为常量，或为简单常数；属性名也可以用它的序号来代替，在基本的选择条件上可以进一步进行逻辑运算，即进行求非（ \(\lnot\) ）、与（ \(\land\) ）、或（ \(\lor\) ）运算。条件表达式中的运算符如20241026141516CST所示。

表5

  选择运算实际上是从关系火中选取使逻辑表达式 \(F\) 为真的元组。这是从行的角度进行的运算。

  设有一个学生—课程数据库，包括学生关系Student，课程关系Course和选修关系SC。如图6所示。下面的多个例子将对这三个关系进行运算。

图6 学生—课程数据库

  例4：查询信息系（IS系）全体学生。

  结果如图7(a)所示。

  例5：查询年龄小于20岁的学生。

  结果如图7(b)所示。

图7 选择运算举例

投影(projection)

  关系 \(R\) 上的投影是从 \(R\) 中选择出若干属性列组成新的关系。记作

  其中 \(A\) 为 \(R\) 的属性列。
  投影操作就是从列的角度进行运算。

  例6：查询学生的姓名和所在系，即求Student关系上学生姓名和所在系两个属性上的投影。

  结果如图8(a)所示。
  投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组，因为取消了某些属性列后，就可能出现重复行，应取消这些完全相同的行。

  例7：查询学生关系Student中都有哪些系，即查询关系Student上所在系属性上的投影。

  结果如图8(b)所示。Student关系原来有4个元组，而投影结果取消了重复的CS元组，因此只有三个元组。

图8 投影运算举例

连接(join)

  连接也称为 \(\theta\) 连接。它是从两个关系的Cartesian乘积中选取属性间满足一定条件的元组。记作

  其中， \(A\) 和 \(B\) 分别为 \(R\) 和 \(S\) 上列数相等且可比的属性组， \(\theta\) 是比较运算符。连接运算从 \(R\) 和 \(S\) 的Cartesian乘积 \(R\times S\) 中选取R关系在 \(A\) 属性组上的值与 \(S\) 关系在 \(B\) 属性组上的值满足比较关系 \(\theta\) 的元组。
  连接运算中有两种最为重要也最为常用的连接，一种是等值连接(equijoin)，另一种是自然连接(natural join)。
   \(\theta\) 为“ \(=\) ”的连接运算称为等值连接。它是从关系 \(R\) 与 \(S\) 的广义Cartesian乘积中选取 \(A\) 、 \(B\) 属性值相等的那些元组，即等值连接为

  自然连接是一种特殊的等值连接。它要求两个关系中进行比较的分量必须是同名的属性组，并且在结果中把重复的属性列去掉。即若 \(R\) 和 \(S\) 中具有相同的属性组 \(B\) ， \(U\) 为 \(R\) 和 \(S\) 的全体属性集合，则自然连接可记作

  一般的连接操作是从行的角度进行运算，但自然连接还需要取消重复列，所以是同时从行和列的角度进行运算。

  例8：设图9(a)和(b)分别为关系 \(R\) 和关系 \(S\) ，图图9(c)为非等值连接及 \( R \underset{C\lt E}{\Join} S \) 的结果，图9(d)为等值连接 \( R \underset{R.B=S.B}{\Join} S \) 的结果，图9(e)为自然连接 \( R \Join S \) 的结果。

图9 连接运算举例

  两个关系 \(R\) 和 \(S\) 在做自然连接时，选择两个关系在公共属性上值相等的元组构成新的关系。此时，关系 \(R\) 中某些元组有可能在 \(S\) 中不存在公共属性上值相等的元组，从而造成 \(R\) 中这些元组在操作时被舍弃了，同样， \(S\) 中某些元组也可能被舍弃。这些被舍弃的元组称为悬浮元组(dangling tuple)，例如，在图9(e)的自然连接中， \(R\) 中的第 \(4\) 个元组， \(S\) 中的第 \(5\) 个元组都是被舍弃掉的悬浮元组。
  如果把悬浮元组也保存在结果关系中，而在其他属性上填空值(NULL)，那么这种连接就叫做外连接(outer join)，记作 \(R⟗S\) ；如果只保留左边关系 \(R\) 中的悬浮元组就叫做左外连接（left outer join或left join），记作 \(R⟕S\) ；如果只保留右边关系 \(S\) 中的悬浮元组就叫做右外连接（right outer join或right join），记作 \(R⟖S\) 。在图10中，(a)是图9中的关系 \(R\) 和关系 \(S\) 的外连接，(b)是左外连接，(c)是右外连接。

图10 外连接运算举例

除运算

  设关系 \(R\) 除以关系 \(S\) 的结果为关系 \(T\) ，则 \(T\) 包含所有在 \(R\) 但不在 \(S\) 中的属性及其值，且 \(T\) 的元组与 \(S\) 的元组的所有组合都在 \(R\) 中。
  下面用象集来定义除法：
  给定关系 \(R(X,Y)\) 和 \(S(Y,Z)\) ，其中 \(X,Y,Z\) 为属性组。 \(R\) 中的 \(Y\) 与 \(S\) 中的 \(Y\) 可以有不同的属性名，但必须出自相同的域集。
   \(R\) 与 \(S\) 的除运算得到一个新的关系 \(P(X)\) ， \(P\) 是 \(R\) 中满足下列条件的元组在 \(X\) 属性列上的投影：元组在 \(X\) 上分量值 \(x\) 的象集 \(Y_x\) 包含 \(S\) 在 \(Y\) 上投影的集合。记作

  其中 \(Y_x\) 为 \(x\) 在 \(R\) 中的象集， \(x=t_r[X]\) 。
  除操作是同时从行和列角度进行运算。

  例9：设关系 \(R\) 、 \(S\) 分别为图11中的(a)和(b)， \(R \div S\) 的结果为图11(c)。
  在关系 \(R\) 中， \(A\) 可以取 \(4\) 个值 \(\set{a_1,a_2,a_3,a_4}\) 。其中：
   \(a_1\) 的象集为 \(\set{(b_1,c_2),(b_2,c_3),(b_2,c_1)}\) 。
   \(a_2\) 的象集为 \(\set{(b_3,c_7),(b_2,c_3)}\) 。
   \(a_3\) 的象集为 \(\set{(b_4,c_6)}\) 。
   \(a_4\) 的象集为 \(\set{(b_6,c_6)}\) 。
   \(S\) 在 \((B,C)\) 上的投影为 \(\set{(b_1,c_2),(b_2,c_1),(b_2,c_3)}\) 。
  显然只有 \(a_1\) 的象集 \((B,C)_{a_1}\) 包含了 \(S\) 在 \((B,C)\) 属性组上的投影，所以

图11 除运算举例

  下面再以学生—课程数据库（图6）为例，给出几个综合应用多种关系代数运算进行查询的例子。

  例10：查询1号课程和3号课程都选秀了的学生的号码。
  首先建立一个临时关系 \(K\) ：

图12 临时关系 \(\text{K}\)

  然后求

  结果为 \(\set{201215121}\) 。
  求解过程与例9类似，先对 \(\text{SC}\) 关系在 \((\text{Sno},\text{Cno})\) 属性上投影，然后逐一求出每 一学生（ \(\text{Sno}\) ）的象集，并依次检查这些象集是否包含 \(\text{K}\) 。

  例11：查询选修了 \(2\) 号课程的学生的学号。

  例12：查询至少选修了一门其直接先行课为5号课程的学生姓名。

  或

  例13：查询选修了全部课程的学生号码和姓名。

  本节介绍了8种关系代数运算，其中并、差、Cartesian乘积、选择和投影这5种运算为基本的运算。其他三种运算，即交、连接和除，均可以用这5种基本运算来表达。引进它们并不增加语言的能力，但可以简化表达。
  关系代数中，这些运算经有限次复合后形成的表达式称为关系代数表达式。

关系演算

  关系演算是以数理逻辑中的谓词演算为基础的。按谓词变元的不同，关系演算可分为元组关系演算和域关系演算。本节先介绍元组关系演算，然后简单介绍域关系演算。

元组关系演算语言ALPHA

  元组关系演算以元组变量作为谓词变元的基本对象。一种典型的元组关系演算语言是E.F.Codd提出的ALPHA语言。这一语言虽然没有实际实现，但关系数据库管理系统INGRES最初所用的QUEL语言是参照ALPHA语言研制的，与ALPHA十分类似。ALPHA 语言主要有GET、PUT、HOLD、UPDATE、DELETE、DROP6条语句，语句的基本格式为

1

操作语句 工作空间名 (表达式)：操作条件

  其中表达式用于指定语句的操作对象，它可以是关系名或（和）属性名，一条语句可以同时操作多个关系或多个属性。操作条件是一个逻辑表达式，用于将操作结果限定在满足条件的元组中，操作条件可以为空。除此之外，还可以在基本格式的基础上加上排序要求以及指定返回元组的条数等。

检索操作

  检索操作用GET语句实现。

1. 简单检索（即不带条件的检索）

  例14：查询所有被选修的课程号码。

1

GET W (SC.Cno)

W为工作空间名。这里条件为空，表示没有限定条件。

  例15：查询所有学生的数据。

1

GET W (Student)

2. 限定的检索（即带条件的检索）

  例16：查询信息系(IS)中年龄小于20岁的学生的学号和年龄。

1

GET W (Student.Sno,Student.Sage): Student.Sdept='IS'∧Student.Sage<20

3. 带排序的检索

  例17：查询计算机科学系(CS)学生的学号、年龄，结果按年龄降序排序。

1

GET W (Student.Sno,Student.Sage): Student.Sdept='CS' DOWN Student.Sage

  DOWN表示降序排序。

4. 指定返回元组的条数的检索

  例18：取出一个信息系学生的学号。

1

GET W (1) (Student.Sno): Student.Sdept='IS'

  在W后括号中的数量就是指定的返回元组的个数。

  例19：查询信息系年龄最大的三个学生的学号及其年龄，结果按年龄降序排序。

1

GET W (3) (Student.Sno,Student.Sage): Student.Sdept='IS' DOWN Student.Sage

5. 用元组变量的检索

  前面已讲到，元组关系演算是以元组变量作为谓词变元的基本对象。元组变量是在某一关系范围内变化的，所以也称为范围变量(range variable)，一个关系可以设多个元组变量。

  元组变量主要有两方面的用途：
  (1) 简化关系名。如果关系的名字很长，使用起来就会感到不方便，这时可以设一个较短名字的元组变量来代替关系名。如例20。
  (2) 操作条件中使用量词时必须用元组变量。如例21至例23。

  例20：查询信息系学生的名字。

1
2

RANGE Student X 
GET W (X.Sname): X.Sdept='IS'

  ALPHA语言用RANGE来说明元组变量。本例中X是关系Student上的元组变量，用途是简化关系名，即用X代表Student。

6. 用存在量词(existential qualifier)检索

  例21：查询选修2号课程的学生的名字。

1
2

RANGE SC X
GET W (Student.Sname): ∃X(X.Sno=Student.Sno∧X.Cno='2')

  例22：查询选修了这样课程的学生学号，其直接先行课是6号课程。

1
2

RANGE Course CX 
GET W (SC.Sno): ∃CX(CX.Cno=SC.Cno∧CX.Pcno='6')

  例23：查询至少选修一门其先行课为6号课程的学生名字。

1
2
3
4

RANGE Course CX
      SC SCX  
GET W (Student.Sname): ∃SCX(SCX.Sno=Student.Sno∧ 
                       ∃CX(CX.Cno=SCX.Cno∧CX.Pcno='6'))

  在本例中的元组关系演算公式可以变换为前束范式(prenex normal form)‌的形式：

1
2

GET W (StudentSname): ∃SCX∃CX(SCX.Sno=Student.Sno∧
                               CX.Cno=SCX.Cno∧CX.Pcno='6')

  例21、例22、例23中的元组变量都是为存在量词而设的。其中例2.23需要对两个关系使用存在量词，所以设了两个元组变量。

7. 带有多个关系表达式的检索

  上面所举的各个例子中，虽然查询时可能会涉及多个关系，即公式中可能涉及多个关系，但查询结果表达式中只有一个关系。实际上表达式中是可以有多个关系的。

  例24：查询成绩为90分以上的学生名字与课程名字。
  本查询所要求的结果是学生名字和课程名字，分别在Student和Course两个关系中。

1
2
3

RANGE SC SCX 
GET W (Student.Sname,Course.Cname): ∃SCX(SCX.Grade⩾90∧ 
                                     SCX.Sno=Student.Sno∧Course.Cno=SCX.Cno)

8. 用全称量词(generality quantifier)的检索

  例25：查询不选1号课程的学生名字。

1
2

RANGE SC SCX
GET W (Student.Sname): ∀SCX(SCX.Sno≠Student.Sno∨SCX.Cno≠'1')

  也可以用存在量词表示。

1
2

RANGE SC SCX
GET W (Student.Sname): ¬∃SCX(SCX.Sno=Student.Sno∧SCX.Cno='1')

9. 用两种量词的检索

  例26：查询选修了全部课程的学生姓名。

1
2
3

RANGE Course CX
      SC SCX
GET W (Student.Sname): ∀CX∃SCX(SCX.Sno=Student.Sno∧SCX.Cno=CX.Cno)

10. 用蕴涵(implication)的检索

  例27：查询最少选修了 201215122学生所选课程的学生学号。

  本例题的求解思路是，对Course中的所有课程依次检查每一门课程，看201215122是否选修了该课程，如果选修了，则再看某一个学生是否也选修了该门课。如果对于201215122所选的每门课程该学生都选修了，则该学生为满足要求的学生。把所有这样的学生全都找出来即完成了本题。

1
2
3
4
5

RANGE Course CX  
      SC SCX
      SC SCY
GET W (Student.Sno): ∀CX(∃SCX(SCX.Sno='201215122'∧SCX.Cno=CX.Cno) 
                         ⇒∃SCY(SCY.Sno=Student.Sno∧SCY.Cno=CX.Cno))

  蕴涵（⇒）见命题逻辑。

11. 聚集函数

  用户在使用查询语言时经常要作一些简单的计算，例如要求符合某一查询要求的元组数，求某个关系中所有元组在某属性上的值的总和或平均值等。为了方便用户，关系数据语言中建立了有关这类运算的标准函数库供用户选用。这类函数通常称为聚集函数或内置函数（built-in function），关系演算中提供了COUNT、TOTAL、MAX、MIN、AVG等聚集函数，其含义如表6所示。

表6 关系演算中的聚集函数

  例28：查询学生所在系的数目。

1

GET W (COUNT(Student.Sdept))

  例29：查询信息系学生的平均年龄。

1

GET W (AVG(Student.Sage): Student.Sdept='IS')

更新操作

1. 修改操作

  (1) 首先用HOLD语句将要修改的元组从数据库中读到工作空间中：
  (2) 然后用宿主语言修改工作空间中元组的属性值。
  (3) 最后用UPDATE语句将修改后的元组送回数据库中。

  例30：把201215127学生从计算机科学系转到信息系。

1
2
3
4

HOLD W (Student.Sno,Student Sdept): Student.Sno='201215127'
                           (从Student关系中读出201215127学生的数据)
MOVE 'IS' TO W.Sdept       (用宿主语言进行修改)
UPDATE W                   (把修改后的元组送回Student关系)

  在该例中用HOLD语句来读201215127的数据，而不是用GET语句。如果修改操作涉及两个关系的话，就要执行两次HOLD-MOVE-UPDATE操作序列。
  在ALPHA语言中，修改关系主码的操作是不允许的，例如不能用UPDATE语句将学 号201215121改为201215122。如果需要修改主码值，只能先用删除操作删除该元组，然后再把具有新主码值的元组插入到关系中。

2. 插入操作

  插入操作用PUT语句实现。其步骤是：
  (1) 首先用宿主语言在工作空间中建立新元组。
  (2) 然后用PUT语句把该元组存入指定的关系中。

  例31：学校新开设了一门2学分的课程"计算机组织与结构”，其课程号为8,直 接先行课为6号课程。插入该课程元组。

1
2
3
4
5

MOVE '8' TO W.Cno
MOVE '计算机组织与结构' TO W.Cname
MOVE '6' TO W.Cpno
MOVE '2' TO W.Ccredit
PUT W (Course)      (把W中的元组插入指定关系Course中)

  PUT语句只对一个关系操作，也就是说表达式必须为单个关系名。

3. 删除操作

  删除操作用DELETE语句实现。其步骤为：
  (1) 用HOLD语句把要删除的元组从数据库中读到工作空间中。
  (2) 用DELETE语句删除该元组。

  例32：201215230学生因故退学，删除该学生元组。

1
2

HOLD W (Student): Student.Sno='201215230'
DELETE W

  例33：将学号201215121改为 201215122。

1
2
3
4
5
6
7
8

HOLD W (Student): Student.Sno='201215121'
DELETE W
MOVE '201215122' TO W.Sno
MOVE '李勇' TO W.Sname 
MOVE '男' TO W.Ssex 
MOVE '20' TO W.Sage 
MOVE 'CS' TO W.Sdept 
PUT W (Student)

  例34：删除全部学生。

1
2

HOLD W (Student)
DELETE W

  由于SC关系与Student关系之间具有参照关系，为保证参照完整性，删除Student中元组时相应地要删除SC中的元组（手工删除或由数据库管理系统自动执行）：

1
2

HOLD W (SC)  
DELETE W

元组关系演算

  为了讨论方便，先允许关系（的基数）是无限的，然后再对这种情况下定义的演算做适当的修改，保证关系演算中各个公式表示的是有限关系。
  在元组关系演算系统中，称 \(\set{t|\phi(t)}\) 为元组演算表达式。其中， \(t\) 是元组变量， \(\phi(t)\) 为元组关系演算公式，简称公式，它由原子公式和运算符组成。
  原子公式有以下三类：
  (1) \(R(t)\) 。 \(R\) 是关系名， \(t\) 是元组变量。 \(R(t)\) 表示 \(t\) 是 \(R\) 中的元组。于是，关系 \(R\) 可表示为 \(\set{t|R(t)}\) 。
  (2) \(t[i]\theta u[j]\) 。 \(t\) 和 \(u\) 是元组变量， \(\theta\) 是算数比较运算符。 \(t[i]\theta u[j]\) 表示断言“元组 \(t\) 的第 \(i\) 个分量与元组 \(u\) 的第 \(j\) 个分量满足比较关系 \(\theta\) ”。例如， \(t[2] < u[3] \) 表示元组 \(t\) 的第 \(2\) 个分量小于元组 \(u\) 的第 \(3\) 个分量。
  (3) \(t[i]\theta c\) 或 \(c\theta t[i]\) 。这里 \(c\) 是常量，该公式表示“ \(t\) 的第 \(i\) 个分量与常量 \(c\) 满足比较关系 \(\theta\) ”。例如， \(t[4]=3\) 表示元组 \(t\) 的第 \(4\) 个分量等于 \(3\) 。

  在关系演算中定义了"自由元组变量”和"约束元组变量”的概念。这些概念和谓词演算中的概念完全一样。若公式中的一个元组变量前有“全称量词”或“存在量词"，则称该变量为约束元组变量，否则称自由元组变量。

  公式可以递归定义如下：
  (1) 每个原子公式是公式。
  (2) 如果 \(\phi_1\) 和 \(\phi_2\) 是公式，则 \(\phi_1\land\phi_2\) 、 \(\phi_1\lor\phi_2\) 、 \(\lnot\phi_1\) 是公式。
  ①如果 \(\phi_1\) 和 \(\phi_2\) 同时为真，则 \(\phi_1\land\phi_2\) 才为真，否则为假。
  ②如果 \(\phi_1\) 和 \(\phi_2\) 中一个或同时为真，则 \(\phi_1\lor\phi_2\) 为真，仅当 \(\phi_1\) 和 \(\phi_2\) 同时为假时， \(\phi_1\lor\phi_2\) 才为假。
  ③若 \(\phi_1\) 为真，则 \(\lnot\phi_1\) 为假。
  (3) 若 \(\phi\) 是公式，则 \(\exist t(\phi)\) 是公式，其中符号 \(\exist\) 是全称量词符号， \(\exist t(\phi)\) 表示，如果对所有 \(t\) 都使 \(\phi\) 为真，则 \(\exist t(\phi)\) 为真，否则 \(\exist t(\phi)\) 为假。
  (4) 若 \(\phi\) 是公式，则 \(\forall t(\phi)\) 是公式，其中符号 \(\forall\) 是全称量词符号， \(\forall t(\phi)\) 表示，如果对所有 \(t\) 都使 \(\phi\) 为真，则 \(\forall t(\phi)\) 为真，否则 \(\forall t(\phi)\) 为假。
  (5) 在元组演算公式中，各种运算符的优先次序为：
  ①算术比较运算符最高。
  ②量词次之，且 \(\exist\) 的优先级高于 \(\forall\) 的优先级。
  ③逻辑运算符最低，且 \(\lnot\) 的优先级高于 \(\land\) 的优先级， \(\land\) 的优先级高于 \(\lor\) 的优先级。
  ④加括号时，括号中的运算符优先，同一括号内的运算符之优先级遵循①、②、③各项。
  (6) 有限次地使用上述5条规则得到的公式是元组关系演算公式，其他公式不是元组关系演算公式。

  一个元组演算表达式 \(\set{t|\phi(t)}\) 表示了使 \(\phi(t)\) 真的元组集合。

  关系代数的运算均可以用关系演算表达式来表示（反之亦然）。下面用关系演算表达式来表示5种基本运算。

  (1) 并 \[ R \cup S = \set{t|R(t) \lor S(t)} \tag{37} \]

  (2) 差 \[ R-S=\set{t|R(t) \land \lnot S(t)} \tag{38} \]

  (3) Cartesian积 \[ R\times S=\set{t^{(n+m)}|(\exist u^{(n)})(\exist v^{(m)})(R(u)\land S(v) \land (t[1]=u[1]) \land \cdots \land (t[n]=u[n])\\[5pt] \land (t[n+1]=v[1])\land\cdots\land(t[n+m]\land v[m]))} \tag{39} \]   这里 \(t^{(n+m)}\) 表示 \(t\) 的目数是 \((n+m)\) 。

  (4) 投影

  (5) 选择 \[ \sigma_F(R)=\set{t|R(t)\land F'} \tag{41} \]    \(F'\) 是公式 \(F\) 用 \(t[i]\) 代替运算对象 \(i\) 得到的等价公式。

  下面用关系演算来对图6中的学生—课程数据库进行查询。

  例35：查询信息(IS)系全体学生。 \[ S_{IS}=\set{t|\text{Student}(t)\land (t[5]=\text{'IS'})} \tag{42} \]

  例36：查询年龄小于 \(20\) 岁的学生。 \[ S_{20}=\set{t|\text{Student}(t)\land (t[4]<20)} \tag{43} \]

  例37：查询学生的姓名和所在系。 \[ S_1=\set{t^{(2)}|(\exist u)(\text{Student}(u)\land(t[1]=u[2])\land(t[2]=u[5]))} \tag{44} \]

  上面的定义的关系演算允许出现无限关系。例如， \(\set{t|\lnot R(t)}\) 表示所有不属于 \(R\) 的元组（元组的目数等于 \(R\) 的目数）。要求出这些可能的元组是做不到的，所以必须排除这类无意义的表达式。把不产生无限关系的表达式称为安全表达式，所采取的措施称为安全限制。安全限制通常是定义一个有限的符号集 \(\text{dom}(\phi)\) ， \(\text{dom}(\phi)\) 一定包括出现在 \(\phi\) 以及中间结果和最后结果的关系中的所有符号（实际上是各列中值的汇集）。 \(\text{dom}(\phi)\) 不必是最小集。
  当满足下列条件时，元组演算表达式 \(\set{t|\phi(t)}\) 是安全的：
  (1) 如果 \(t\) 使 \(\phi(t)\) 为真，则 \(t\) 的每个分量是 \(\text{dom}(\phi)\) 中的元素。
  (2) 对于 \(\phi\) 中每一个形如 \((\exist u)(W(u))\) 的子表达式，若 \(u\) 使 \(W(u)\) 为真，则 \(u\) 的每个分量是 \(\text{dom}(\phi)\) 中的元素。
  (3) 对于 \(\phi\) 中每一个形如 \((\forall u)(W(u))\) 的子表达式，若 \(u\) 使 \(W(u)\) 为假，则 \(u\) 的每个分量必属于 \(\text{dom}(\phi)\) 。换言之，若 \(u\) 某一分量不属于 \(\text{dom}(\phi)\) ，则 \(W(u)\) 为真。

  例38：设有关系 \(R\) 如图13(a)所示， \(S=\set{t|\lnot R(t)}\) ，若不进行安全限制，则可能是一个无限关系。所以定义

  则 \(S\) 是 \(\text{dom}(\phi)\) 中各阈值中元素的Cartesian积与 \(R\) 的差集。结果如图13(b)所示。注意，在做Cartesian积时各个域中的元素不能搞混。

图13 关系演算安全限制示例

域关系演算语言QBE

  关系演算的另一种形式是域关系演算。域关系演算以元组变量的分量（即域变量）作为谓词变元的基本对象。1975年由M.M.Zloof提出的QBE就是一个很有特色的域关系演算语言，该语言于1978年在IBM370上得以实现。
  QBE是Query By Example（即通过例子进行查询）的简称，它最突出的特点是操作方式。它是一种高度非过程化的基于屏幕表格的查询语言，用户通过终端屏幕编辑程序，以填写表格的方式构造查询要求，而查询结果也是以表格形式显示，因此非常直观、易学易用。
  QBE中用示例元素来表示查询结果可能的情况，示例元素实质上就是域变量。QBE操作框架如图14所示。

图14 QBE操作框架

  下面以学生—课程数据库为例，说明QBE的用法。

检索操作

1. 简单查询

  例39：求信息系全体学生的姓名。
  操作步骤为：
  ①用户提出要求。
  ②平面显示空白空格。

  ③用户在最左边一栏输入关系名Student。

  ④系统显示该关系的属性名。

  ⑤用户在上面构造查询要求

  这里 \(T\) 是示例元素，即域变量。QBE要求示例元素下面一定要加下划线。IS是查询条件，不用加下划线。P.是操作符，表示打印(Print)，实际上是显示。
  查询条件中可以使用比较运算符 \(>\)，\(\ge\)，\(<\)，\(\le\)，\(=\) 和 \(\ne\) ，其中 \(=\) 可以省略。
  示例元素是这个域中可能的一个值，它不必是查询结果中的元素。比如要求信息系的学生，只要给出任意的一个学生名即可，而不必真是信息系的某个学生名。
  对于例39，可如下构造查询要求：

  这里的查询条件是 \(\text{Sdept}=\text{'IS'}\) ，其中“\(=\)”被省略。
  ⑥屏幕显示查询结果。

  即根据用户的查询要求求出了信息系的学生姓名。

  例40：查询全体学生的全部数据。

  显示全部数据也可以简单地把P.操作符作用在关系名上。因此本查询也可以简单地表示如下：

2. 条件查询

  例41：求年龄大于19岁的学生的学号。

  例42：求计算机科学系年龄大于19岁的学生的学号。
  本查询的条件是 \(\text{Sdept}=\text{'CS'}\) ，和 \(\text{Sage>19}\) 两个条件的“与”。在QBE中，表示两个条件的“与”有两种方法：
  ①把两个条件写在同一行上

  ②把两个条件写在不同行上，但是用相同的示例元素值。

  例43：查询计算机科学系或者年龄大于19岁的学生的学号。
  本查询的条件是 \(\text{Sdept}=\text{'CS'}\) ，和 \(\text{Sage>19}\) 两个条件的“或”。在QBE中把两个条件写在不同行上，并且使用不同的示例元素值，即表示条件的“或”。

  对于多行条件的查询，例42②和例43，先输入哪一行是任意的，不影响查询结果，这就允许用户以不同的思考方式进行查询，十分灵活、自由。
  例44：查询既选修了1号课程又选修了2号课程的学生的学号。
  本查询条件是在一个属性中的“与”关系，它只能用“与”条件的第②种方法表示，即写两行，但示例元素相同。

  例45：查询选修1号课程的学生姓名。
  本查询涉及两个关系：SC和Student。在QBE中实现这种查询的方法是通过相同的连接属性值把多个关系连接起来。

  这里示例元素 \(\text{Sno}\) 是连接属性，其值在两个表中要相同。

  例46：查询未选修1号课程的学生姓名。

  这里的查询条件中用到逻辑非。在QBE中表示逻辑非的方法是将逻辑非写在关系名下面。

  注意除了该学生选的课程里没有1号课程，还有一种可能就是该学生什么课程都没有选修，因此还需要加上下面那一行查询条件。

  例47：查询有两个人以上选修的课程号。
  本查询是在一个表内连接。这个查询就是要显示这样的课程1，它不仅被201215121选修，而且也被另一个不是201215121学生（\(\lnot\)201215121）选修了。

3. 聚集函数

  为了方便用户，QBE提供了一些聚集函数，主要包括CNT、SUM、AVG、MAX、MIN 等，其含义如表7所示。

表7

  例48：查询信息系学生的平均年龄。

4. 对查询结果进行排序

  对查询结果按某个属性值的升序排序，只需在相应列中填入“AO.”，按降序排序则填“DO.”。如果按多列排序，用AO(i).或DO(i).表示，其中i为排序的优先级，i值越小，优先级越高。

  例49：查全体男生的姓名，要求查询结果按所在系升序排序，对相同系的学生按年龄降序排序。

更新操作

1. 修改操作

  修改操作符为“U.”。在QBE中关系的主码不允许修改，如需修改某个元组的主码，只能先删除该元组，然后再插入新的主码的元组。

  例50：把201215121学生的年龄改为18岁。
  这是一个简单修改操作，不包含算术表达式，因此可以有两种表示方法：
  ①将操作符“U.”放在值上。

  ②将操作符“U.”放在关系上。

  这里，码201215121标明要修改的元组。“U.“标明所在的行是修改后的新值。由于主码是不能修改的，所以即使在第二种写法中，系统也不会混淆要修改的属性。

  例51：把201215121学生的年龄增加1岁。
  这个修改操作涉及表达式，所以只能将操作符"U.“放在关系上。

  例52：将计算机科学系所有学生的年龄都增加一岁。

2. 插入操作

  插入操作符为"I”。新插入的元组必须具有码值，其他属性值可以为空。

  例53：把信息系女生201215801，姓名张三，年龄17岁存入数据库中。

3. 删除操作

  删除操作符为“D.”。

例54：删除学生201215189。

  由于SC关系与Student关系之间具有参照关系，为保证参照完整性，删除201215189学生后，通常还应删除201215189学生选修的全部课程。

无言是最大的轻蔑。

― 刘慈欣, 《三体Ⅲ：死神永生》