2.5 *关系演算
关系演算是以数理逻辑中的谓词演算为基础的。按谓词变元的不同，关系演算可分为元组关系演算和域关系演算。本小节先介绍元组关系演算，然后简单介绍域关系演算。
一、元组关系演算语言ALPHA
元组关系演算以元组变量作为谓词变元的基本对象。一种典型的元组关系演算语言是E. F. Codd提出的ALPHA语言。这一语言虽然没有实际实现，但关系数据库管理系统INGRES最初所用的QUEL语言是参照ALPHA语言研制的，与ALPHA十分类似。
ALPHA语言主要有GET，PUT，HOLD，UPDATE，DELETE，DROP 6条语句，语句的基本格式是：
操作语句 工作空间名（表达式）：操作条件
其中表达式用于说明要查询的结果，它可以是关系名或（和）属性名，一条语句可以同时操作多个关系或多个属性。操作条件是一个逻辑表达式，说明查询结果要满足的条件，用于将操作结果限定在满足条件的元组中，操作条件可以为空。除此之外，还可以在基本格式的基础上加上排序要求、定额要求等。
1检索操作
检索操作用GET语句实现。
（1）简单检索（即不带条件的检索）
【例1】查询所有被选修的课程号码。
Get W（SC.Cno），W为工作空间名。这里条件为空，表示没有限定条件。
【例2】查询所有学生的数据。
GET W（Student）
（2）限定的检索（即带条件的检索）
【例3】查询信息系（IS）中年龄小于20岁的学生的学号和年龄。
GET W（Student.Sno，Student.Sage）：Student.Sdept＝‘IS’∧Student.Sage＜20
（3）带排序的检索
【例4】查询计算机科学系（CS）学生的学号、年龄，结果按年龄降序排序。
GET W（Student.Sno，Student.Sage）：Student.Sdept＝‘CS’DOWN Student.Sage
DOWN表示降序排序。
（4）带定额的检索
【例5】取出一个信息系学生的学号。
GET W（1）（Student.Sno）：Student.Sdept＝‘IS’
排序和定额可以一起使用。所谓带定额的检索是指规定了检索出元组的个数，方法是在W后括号中加上定额数量。
【例6】查询信息系年龄最大的三个学生的学号及其年龄，结果按年龄降序排序。
GET W（3）（Student.Sno，Student.Sage）：Student.Sdept＝‘IS’DOWN Student.Sage
（5）用元组变量的检索
前面已讲到，元组关系演算是以元组变量作为谓词变元的基本对象。元组变量是在某一关系范围内变化（所以也称为范围变量Range Variable），一个关系可以设多个元组变量。元组变量主要有两方面的用途：
①简化关系名。如果关系的名字很长，使用起来就会感到不方便，这时可以设一个较短名字的元组变量来代替关系名。
②操作条件中使用量词时必须用元组变量。
【例7】查询信息系学生的名字。
RANGE Student X GET W（X.Sname）：X.Sdept＝‘IS’
ALPHA语言用RANGE来说明元组变量。本例中X是关系Student上的元组变量，用是简化关系名，即用X代表Student。
（6）用存在量词（existential quantifier）的检索操作条件中使用量词时必须用元组变量。
【例8】查询选修2号课程的学生名字。
RANGE SC X GET W（Student Sname）：∃ X（X.Sno＝Student.Sno∧X.Cno＝‘2’）
【例9】查询选修了这样课程的学生学号，其直接先行课是6号课程。
RANGE Course CX GET W（SC Sno）：∃ CX（CX.Cno＝SC.Cno∧CX.Pcno＝‘6’）
【例10】查询至少选修一门其先行课为6号课程的学生名字。
在【例10】中的元组关系演算公式可以变换为前束范式（Prenex normal form）的形式：
GET W（Student Sname）：∃ SCX ∃ CX（SCX.Sno＝Student.Sno∧CX.Cno＝SCX.Sno∧CX.Pcno＝‘6’）
【例8】、【例9】、【例10】中的元组变量都是为存在量词而设的。其中【例10】需要对两个关系作用存在量词，所以设了两个元组变量。
（7）带有多个关系的表达式的检索
上面所举的各个例子中，虽然查询时可能会涉及多个关系，即公式中可能涉及多个关系，但查询结果表达式中只有一个关系。实际上表达式中是可以有多个关系的。
【例11】查询成绩为90分以上的学生名字与课程名字。
本查询所要求的结果是学生名字和课程名字，分别在Student和Course两个关系中。
RANGE SC SCX GET W（Student.Sname，Course.Cname）：∃ SCX（SCX.Grade≥90∧SCX.Sno＝Student.Sno∧Course.Cno＝SCX.Cno）
（8）用全称量词（generality quantifier）的检索
【例12】查询不选1号课程的学生名字。
RANGE SC SCX GET W（Student.Sname）：∀ SCX（SCX.Sno≠Student.Sno∨SCX.Cno≠‘1’）
本例也可以用存在量词来表示：
RANGE SC SCX GET W（Student.Sname）：￢∃ SCX（SCX.Sno＝Student.Sno∧SCX.Cno＝‘1’）
（9）用两种量词的检索
【例13】查询选修了全部课程的学生姓名。
（10）用蕴涵（Implication）的检索
【例14】查询最少选修了95002学生所选课程的学生学号。
本例题的求解思路是，对Course中的所有课程，依次检查每一门课程，看95002是否选修了该课程，如果选修了，则再看某一个学生是否也选修了该门课。如果对于95002所选的每门课程该学生都选修了，则该学生为满足要求的学生。把所有这样的学生全都找出来即完成了本题。
（11）聚集函数
用户在使用查询语言时，经常要作一些简单的计算，例如要求符合某一查询要求的元组数，求某个关系中所有元组在某属性上的值的总和或平均值等。为了方便用户，关系数据语言中建立了有关这类运算的标准函数库供用户选用。这类函数通常称为聚集函数或内置函数（Built.in Function）。关系演算中提供了COUNT，TOTAL，MAX，MIN，AVG等聚集函数，其含义如表2-3所示。
【例15】查询学生所在系的数目。
GET W（COUNT（Student.Sdept）），COUNT函数在计数时会自动排除重复值。
表2-3 关系演算中的聚集函数
【例16】查询信息系学生的平均年龄。
GET W（AVG（Student.Sage）：Student.Sdept＝‘IS’）
2更新操作
（1）修改操作
修改操作用UPDATE语句实现。其步骤是：
①首先用HOLD语句将要修改的元组从数据库中读到工作空间中；
②然后用宿主语言修改工作空间中元组的属性值；
③最后用UPDATE语句将修改后的元组送回数据库中。
需要注意的是，单纯检索数据使用GET语句即可，但为修改数据而读元组时必须使用 HOLD语句，HOLD语句是带上并发控制的GET语句。有关并发控制的概念将在第11章中详细介绍。
【例17】把95007学生从计算机科学系转到信息系。
在该例中用HOLD语句来读95007的数据，而不是用GET语句。
如果修改操作涉及到两个关系的话，就要执行两次HOLD-MOVE-UPDATE操作序列。在ALPHA语言中，修改关系主码的操作是不允许的，例如不能用UPDATE语句将学号95001改为95102。如果需要修改主码值，只能先用删除操作删除该元组，然后再把具有新主码值的元组插入到关系中。
（2）插入操作
插入操作用PUT语句实现。其步骤是：
①首先用宿主语言在工作空间中建立新元组；
②然后用PUT语句把该元组存入指定的关系中。
【例18】学校新开设了一门2学分的课程“计算机组织与结构”，其课程号为8，直接先行课为6号课程。插入该课程元组。
PUT语句只对一个关系操作，也就是说表达式必须为单个关系名。
（3）删除
删除操作用DELETE语句实现。其步骤为：
①用HOLD语句把要删除的元组从数据库中读到工作空间中；
②用DELETE语句删除该元组。
【例19】95110学生因故退学，删除该学生元组。
【例20】将学号95001改为95102。
【例21】删除全部学生。
HOLD W（Student） DELETE W
由于SC关系与Student关系之间的具有参照关系，为保证参照完整性，删除Student中元组时相应地要删除SC中的元组（手工删除或由DBMS自动执行）：
HOLD W（SC） DELETE W
二、元组关系演算
上一节讲解了一种具体的元组关系演算语言，这一节讲解抽象的元组关系演算。
为了讨论方便，先允许关系（的基数）是无限的。然后再对这种情况下定义的演算作适当的修改，保证关系演算中的每一个公式表示的是有限关系。
在元组关系演算系统中，称{t|φ（t）}为元组演算表达式。其中t是元组变量，φ（t）为元组关系演算公式简称公式。它由原子公式和运算符组成。
原子公式有三类：
a．R（t）
R是关系名，t是元组变量。R（t）表示t是R中的元组。于是，关系R可表示为{t|R（t）}
b．t[i]θu[j]
t和u是元组变量，θ是算术比较运算符。t[i]θu[j]表示断言“元组t的第i个分量与元组u的第j个分量满足比较关系θ”。例如，t[2]＜u[3]
表示元组t的第2个分量小于元组u的第3个分量。
c．t[i]θc或cθt[i]
这里c是常量，该公式表示“t的第i个分量与常量C满足比较关系0”。
例如，t[4]＝3表示元组t的第4个分量等于3。
在关系演算中定义了“自由元组变量”和“约束元组变量”的概念。这些概念和谓词演算中的概念完全一样。若公式中的一个元组变量前有“全称量词”或“存在量词”，则称该变量为约束元组变量，否则称自由元组变量。
公式可以递归定义如下：
（1）每个原子公式是公式。
（2）如果φ1，和φ2是公式，则φ1∧φ2，φ1∨φ2，￢φ1也是公式。分别表示：
·如果φ1和φ2同时为真，则φ1∧φ2才为真，否则为假；
·如果φ1和φ2中一个或同时为真，则φ1∨φ2为真，仅当φ1和φ2同时为假时，φ1∨φ2才为假；
·若φ1为真，则￢φ1为假。
（3）若φ是公式，则∃t（φ）也是公式。其中符号∃是存在量词符号，∃t（φ）表示：若有一个t使φ为真，则it（φ）为真，否则it（φ）为假。
（4）若φ是公式，则∀t（φ）也是公式。其中符号∀是全称量词符号，∀t（φ）表示：如果对所有t，都使φ为真，则∀t（φ）为真，否则∀t（φ）为假。
（5）在元组演算公式中，各种运算符的优先次序为：
①算术比较运算符最高；
②量词次之，且∃的优先级高于∀的优先级；
③逻辑运算符最低，且￢的优先级高于∧的优先级，∧的优先级高于∨的优先级；
④加括号时，括号中运算符优先，同一括号内的运算符之优先级遵循①，②，③各项。
（6）有限次地使用上述五条规则得到的公式是元组关系演算公式，其他公式不是元组关系演算公式。
一个元组演算表达式{t|φ（t）}表示了使φ（t）为真的元组集合。
关系代数的运算均可以用关系演算表达式来表示（反之亦然）。下面用关系演算表达式来表示五种基本运算：
（1）并
R∪S＝{t|R（t）∨S（t）}
（2）差
R－S＝{t|R（t）∧￢S（t）}
（3）笛卡尔积
R×S＝{t（n＋m）|（∃u（n））（∃v（m））（R（u）∧S（v）∧t[1]＝u[1]∧…∧t[n]＝u[n]∧t[n＋1]＝v[1]∧…∧t[n＋m]＝v[m]）}
这里t（n＋m）表示t的目数是（n＋m）。
（4）投影
（5）选择
σF（R）＝{t|R（t）∧F′}
F′是公式F用t[i]代替运算对象i得到的等价公式。
下面用关系演算来对2.4.2小节中学生-课程数据库进行查询。
【例1】查询信息系（IS系）全体学生。
SIS＝{t|Student（t）∧t[5]＝‘IS’}
【例2】查询年龄小于20岁的学生。
S20＝{t|Student（t）∧t[4]＜‘20’}
【例3】查询学生的姓名和所在系。
S1＝{t（2）|（∃u）（Student（u）∧t[1]＝u[2]∧t[2]＝u[5]）}
上面定义的关系演算允许出现无限关系。例如，{t|￢R（t）}表示所有不属于R的元组（元组的目数等于R的目数）。要求出这些可能的元组是做不到的，所以必须排除这类无意义的表达式。把不产生无限关系的表达式称为安全表达式，所采取的措施称为安全限制。
安全限制通常是定义一个有限的符号集dom（φ），dom（φ）一定包括出现在φ以及中间结果和最后结果的关系中的所有符号（实际上是各列中值的汇集）。dom（φ）不必是最小集。
当满足下列条件时，元组演算表达式{t|φ（t）}是安全的：
（1）如果t使φ（t）为真，则t的每个分量是dom（φ）中的元素。
（2）对于西中每一个形如（∃u）（W（u））的子表达式，若u使W（u）为真，则U的每个分量是dora（西）中的元素。
（3）对于φ中每一个形如（∀u）（W（u））的子表达式，若u使W（u）为假，则U的每个分量必属于dom（φ）。换言之，若u某一分量不属于dom（φ），则W（u）为真。
【例4】设有关系R如图2-1（a），S＝{t|￢R（t）}，若不进行安全限制，则可能是一个无限关系。
R
图2-1（a）
所以定义
dom（φ）＝πA（R）∪πB（R）∪πC（R）＝{{a1，a2}，{b1，b2}，{c1，c2}}
则S是dom（φ）中各域值中元素的笛卡尔积与R的差集。结果如图2-1（b）。
S
图2-1（b）
注意，在做笛卡尔积时各个域中的元素不能搞混。
三、域关系演算语言QBE
关系演算的另一种形式是域关系演算。域关系演算以元组变量的分量即域变量作为谓词变元的基本对象。1975年由M. M. Zloof提出的QBE就是一个很有特色的域关系演算语言，该语言于1978年在IBM370上得以实现。QBE也指此关系数据库管理系统。
QBE是Query By Example（即通过例子进行查询）的简称，其最突出的特点是它的操作方式。它是一种高度非过程化的基于屏幕表格的查询语言，用户通过终端屏幕编辑程序以填写表格的方式构造查询要求，而查询结果也是以表格形式显示，因此非常直观，易学易用。QBE中用示例元素来表示查询结果可能的情况，示例元素实质上就是域变量。
图2-2 QBE操作框架
下面以学生-课程关系数据库为例，说明QBE的用法。
1检索操作
a．简单查询
【例1】求信息系全体学生的姓名。操作步骤为：
（1）用户提出要求；
（2）屏幕显示空白表格；
（3）用户在最左边一栏输入关系名Student；
（4）系统显示该关系的属性名；
（5）用户在上面构造查询要求。
这里T是示例元素，即域变量。QBE要求示例元素下面一定要加下划线。IS是查询条件，不用加下划线。P.是操作符，表示打印（Print），实际上是显示。
查询条件中可以使用比较运算符＞，≥，＜，≤，＝和≠。其中＝可以省略。
示例元素是这个域中可能的一个值，它不必是查询结果中的元素。比如要求信息系的学生，只要给出任意的一个学生名即可，而不必真是信息系的某个学生名。
对于【例1】，可如下构造查询要求：
这里的查询条件是Sdept＝‘IS’，其中“＝”被省略。
（6）屏幕显示查询结果
根据用户的查询要求，求出了信息系的学生姓名。
【例2】查询全体学生的全部数据。
显示全部数据也可以简单地把P.操作符作用在关系名上。因此本查询也可以简单地表示如下：
b．条件查询
【例3】求年龄大于19岁的学生的学号。
【例4】求计算机科学系年龄大于19岁的学生的学号。
本查询的条件是Sdept＝‘CS’和Sage＞19两个条件的“与”。在QBE中，表示两个条件的“与”有两种方法：
（1）把两个条件写在同一行上；
（2）把两个条件写在不同行上，但使用相同的示例元素值。
【例5】查询计算机科学系或者年龄大于19岁的学生的学号。
本查询的条件是Sdept＝‘CS’和Sage＞19两个条件的“或”。在QBE中把两个条件写在不同行上，并且使用不同的示例元素值，即表示条件的“或”。
对于多行条件的查询，如【例4】（2）和【例5】，先输入哪一行是任意的，不影响查询结果。这就允许查询者以不同的思考方式进行查询，十分灵活、自由。
【例6】查询既选修了1号课程又选修了2号课程的学生的学号。
本查询条件是在一个属性中的“与”关系，它只能用“与”条件的第（2）种方法表示，即写两行，但示例元素相同。
【例7】查询选修1号课程的学生姓名。
本查询涉及两个关系：SC和Student。在QBE中实现这种查询的方法是通过相同的连接属性值把多个关系连接起来。
这里示例元素Sno是连接属性，其值在两个表中要相同。
【例8】查询未选修1号课程的学生姓名
这里的查询条件中用到逻辑非。在QBE中表示逻辑非的方法是将逻辑非写在关系名下面。
这个查询就是显示学号为95001的学生名字，而该学生选修1号课程的情况为假。
【例9】查询有两个人以上选修的课程号。
本查询是在一个表内连接。
这个查询就是要显示这样的课程1，它不仅被95001选修，而且也被另一个学生（95001）选修了。
c．聚集函数
为了方便用户，QBE提供了一些聚集函数，主要包括CNT，SUM，AVG，MAX，MIN等，其含义如表2-4所示。
表2-4 QBE中的聚集函数
【例10】查询信息系学生的平均年龄。
d．对查询结果排序
对查询结果按某个属性值的升序排序，只需在相应列中填入“AO.”，按降序排序则均“DO.”。如果按多列排序，用“AO（i）.”或“DO（i）.”表示，其中i为排序的优先级，i值越小，优先级越高。
【例11】查全体男生的姓名，要求查询结果按所在系升序排序，对相同系的学生按年龄降序排序。
2更新操作
a．修改操作修改操作符为“U.”。在QBE中，关系的主码不允许修改，如果需要修改某个元组的主码，只能先删除该元组，然后再插入新的主码的元组。
【例12】把95001学生的年龄改为18岁。
这是一个简单修改操作，不包含算术表达式，因此可以有两种表示方法。
（1）将操作符“U.”放在值上；
（2）将操作符“U.”放在关系上。
这里，码95001标明要修改的元组。“U.”标明所在的行是修改后的新值。由于主码是不能修改的，所以即使在第二种写法中，系统也不会混淆要修改的属性。
【例13】把95001学生的年龄增加1岁。
这个修改操作涉及表达式，所以只能将操作符“U.”放在关系上。
【例14】将计算机科学系所有学生的年龄都增加1岁。
b．插入操作
插入操作符为“I.”。新插入的元组必须具有码值，其他属性值可以为空。
【例15】把信息系女生95701，姓名张三，年龄17岁存入数据库中。
c．删除操作
删除操作符为“D.”。
【例16】删除学生95089。
由于SC关系与Student关系之间具有参照关系，为保证参照完整性，删除95089学生后，通常还应删除95089学生选修的全部课程。
