元组关系演算语言ALPHA

 

一、 元组关系演算  1。 元组关系演算概念 在元组关系演算系统中，称       {t|Φ(t)} 为元组演算表达式。其中t是元组变量，Φ(t)为元组关系演算公式，简称公式。它由原子公式和运算符组成。      2。 原子公式 （1）  R(t) R是关系名，t是元组变量。R(t)表示t是R中的元组。于是，关系R可表为： {t|R(t)}          （2）  T[i]θu[j] t和u是元组变量,θ是算术比较运算符。T[i]θu[j]表示“元组t的第i个分量与元组u的第j个分量满足比较关系θ”。例如,t[2]<u[3]表示元组t的第2个分量小于元组u的第3个分量。        （3） t[i]θc或cθt[i] 这里c是常量,该公式表示“t的第i个分量与常量c满足比较关系θ”。例如,t[4]=3表示元组t的第4个分量等于3。         3。 若公式中的一个元组变量前有“全称量词 P （universal quantifier）”或“存在量词 v（existential quantifier）”,则称该变量为约束元组变量,否则称自由元组变量。         4。 公式递归定义 定义： (l) 每个原子公式是公式。 (2) 如果Φ1和Φ2是公式,则Φ1∧Φ2, Φ1∨Φ2，┓Φ1也是公式。表示: ·如果Φ1和Φ2同时为真，则Φ1∧Φ2才为真，否则为假； ·如果Φ1和Φ2中一个或同时为真,则Φ1∨Φ2为真,仅当Φ1和Φ2同时为假   时, Φ1∨Φ2才为假； ·若Φ1为真,则┓Φ1为假。 (3) 若Φ是公式，则 vt(Φ)也是公式。v t(Φ)表示：若有一个t使Φ为真，   则 vt(Φ)为真,否则 vt(Φ)为假。 (4) 若Φ是公式，则 Pt(Φ)也是公式。P t(Φ)表示：如果对所有t，都使Φ   为真，则 Pt(Φ)为真，否则 Pt(Φ)为假。 (5) 在元组演算公式中,各种运算符的优先次序为:    （ ）—> 算术比较运算符—> v—> P—> ┓—> ∧—> ∨ (6)有限次地使用上述五条规则得到的公式是元组关系演算公式,其他公式不是元组关系演算公式。       5。 元组关系演算表达式表示关系代数的基本运算 一个元组演算表达式{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)︱(vu(n))( vv(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)    投影 πi1,i2,…….,ik®={t(k)︱(vu)(R(u) ∧t[1]=u[i1] ∧……t[k]=u[ik])} (5)    选择: σF(R)={t︱R(t) ∧F’} F‘是公式F用t[i]代替运算对象i得到的等价公式。 例1查询信息系(IS系)全体学生。     SIS={t︱Student(t) ∧t[5]=’ IS’} 例2查询年龄小于20岁的学生。     S20={t︱Student(t) ∧t[4]<20} 例3查询学生的姓名和所在系。     S1={t(2)︱(vu)(Student(u) ∧t[1]=u[2] ∧t[2]=u[5])} 　       6。 关系演算的安全限制 上面定义的关系演算允许出现无限关系。例如,{t|┓R(t)}表示所有不属于R的元组(元组的目数等于R的目数)。要求出这些可能的元组是做不到的,所以必须排除这类无意义的表达式。把不产生无限关系的表达式称为安全表达式,所采取的措施称为安全限制。 安全限制通常是定义一个有限的符号集dom(Φ)。dom(Φ)一定包括出现在Φ以及中间结果和最后结果的关系中的所有符号(实际上是各列中值的汇集)。dom(Φ)不必是最小集。 当满足下列条件时,元组演算表达式{t|Φ(t)}是安全的： (1)    如果t使Φ(t)为真,则t的每个分量是dom(Φ)中的元素。 (2)    对于Φ中每一个形如(vu)(W(u))的子表达式,若u使W(u)为真,则u的每个分量是dom(Φ)中的元素。 (3)    对于Φ中每一个形如(Pu)(W(u))的子表达式,若u使W(u)为假,则u的每个分量必属于dom(Φ)。换言之,若u某一分量不属于dom(Φ),则W(u)为真。 例4  设有关系R如图2.8(a),S={t|┓R(t)},若不进行安全限制,则可能是一个无限关系。所以定义      dom(Φ)= πA(R) ∪πB∪πC(R)          ={{a1,a2},{b1,b2},{c1,c2}} 则S是dom(Φ)中各域值中元素的笛卡儿积与R的差集。结果如图2.8(b)。注意，在做笛卡儿积是各个域中的元素不能搞混。 　 二、 元组关系演算语言ALPHA 元组关系演算以元组变量作为谓词变元的基本对象。一种典型的元组关系演算语言是E.F.Codd提出ALPHA语言，这一语言虽然没有实际实现，但关系数据库管理系统INGRES所用的QUEL语言是参照ALPHA语言研制的，与ALPHA十分类似。 ALPHA语言主要有GET、PUT、HOLD、UPDATE、DELETE、DROP六条语句，语句的基本格式是： 操作语句　　工作空间名（表达式）：　操作条件 其中表达式用于指定语句的操作对象，它可以是关系名或属性名，一条语句可以同时操作多个关系或多个属性。操作条件是一个逻辑表达式，用于将操作对象限定在满足条件的元组中，操作条件可以为空。除此之外，还可以在基本格式的基础上加上排序要求，定额要求等。 以下仍以P58的实例讨论ALPHA语言：  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<20v 　　 (3)带排序的检索 举例 例4 查询计算机科学系(CS)学生的学号、年龄，并按年龄降序排序 GET W (Student.Sno, Student.Sage): Student.Sdept=‘CS‘ DOWN Student.Sage (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‘ 这里元组变量X的作用是简化关系名Student。 (6)用存在量词的检索 举例 例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号课程的学生名字 RANGE Course CX SC SCX GET W (Student.Sname): ヨSCX (SCX.Sno=Student.Sno ∧ ヨCX (CX.Cno=SC.Cno ∧ CX.Pcno=‘6‘)) 本例中的元组关系演算公式可以变换为前束范式（Prenex normal form）的形式： GET W (Student.Sname): ヨSCXヨCX (SCX.Sno=Student.Sno ∧ CX.Cno=SCX.Cno ∧ CX.Pcno=‘6‘) 例8、例9、例10中的元组变量都是为存在量词而设的。其中例10需要对两个关系作用存在量词，所以设了两个元组变量。 (7)带有多个关系的表达式的检索 举例 (1) 上面所举的各个例子中，虽然查询时可能会涉及多个关系，即公式中可能涉及多个关系，但查询结果都只在一个关系中，即表达式中只有一个关系。实际上表达式中是可以有多个关系的。 例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)用全称量词的检索 举例 例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 查询选修了全部课程的学生姓名 RANGE Course CX SC SCX GET W (Student.Sname): ∨CXヨSCX (SCX.Sno=Student.Sno ∧ SCX.Cno=CX.Cno) (10)用蕴函（Implication）的检索 举例 例14 查询最少选修了95002学生所选课程的学生学号 本例题的求解思路是，对Course中的所有课程，依次检查每一门课程，看95002是否选修了该课程，如果选修了，则再看某一个学生是否也选修了该门课。如果对于95002所选的每门课程该学生都选修了，则该学生为满足要求的学生。把所有这样的学生全都找出来即完成了本题。 RANGE Couse CX SC SCX SC SCY GET W (Student.Sno):∨CX(ヨSCX (SCX.Sno=‘95002‘ ∧ SCX.Cno=CX.Cno) ＝> ヨSCY (SCY.Sno=Student.Sno ∧ SCY.Cno=CX.Cno)) (11)集函数 举例 用户在使用查询语言时，经常要作一些简单的计算，例如要求符合某一查询要求的元组数，求某个关系中所有元组在某属性上的值的总和或平均值等。为了方便用户，关系数据语言中建立了有关这类运算的标准函数库供用户选用。这类函数通常称为集函数（Aggregation function）或内部函数（Build-in function）。关系演算中提供了COUNT，TOTAL，MAX，MIN，AVG等集函数，其含义如表2-5所示。 表2-5 关系演算中的集函数 函 数 名 功 能 COUNT 对元组计数 TOTAL 求总和 MAX 求最大值 MIN 求最小值 AVG 求平均值 例15 查询学生所在系的数目 GET W (COUNT(Student.Sdept)) COUNT函数在计数时会自动排除重复的Sdept值。 例16 查询信息系学生的平均年龄 GET W (AVG(Student.Sage): Student.Sdept=‘IS‘)          2、 更新操作 (1) 修改操作 修改操作用UPDATE语句实现。其步骤是： ·首先用HOLD语句将要修改的元组从数据库中读到工作空间中 ·然后用宿主语言修改工作空间中元组的属性 ·最后用UPDATE语句将修改后的元组送回数据库中 详细信息… 需要注意的是，单纯检索数据使用GET语句即可，但为修改数据而读元组时必须使用HOLD语句，HOLD语句是带上并发控制的GET语句。有关并发控制的概念我们将在第五章中详细介绍。 　 　例17 95007学生从计算机科学系转到信息系 HOLD W (Student.Sno, Student.Sdetp): Student.Sno=‘95007‘　 （从Student关系中读出95007学生的数据） MOVE ‘IS‘ TO W.Sdept （用宿主语言进行修改） UPDATE W 　（把修改后的元组送回Student关系） 　　在该例中我们用HOLD语句来读95007的数据，而不是用GET语句。 　　如果修改操作涉及到两个关系的话，就要执行两次HOLD－MOVE－UPDATE操作序列。 修改主码的操作是不允许的，例如不能用UPDATE语句将学号95001改为95102。如果需要修改关系中某个元组的主码值，只能先用删除操作删除该元组，然后再把具有新主码值的元组插入到关系中。               (2) 插入操作 　　 插入操作用PUT语句实现。其步骤是： 　　 ·首先用宿主语言在工作空间中建立新元组 ·然后用PUT语句把该元组存入指定的关系中 举例 例18 学校新开设了一门2学分的课程“计算机组织与结构”，其课程号为8，直接先行课为6号课程。插入该课程元组。 　　 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语句只对一个关系操作，也就是说表达式必须为单个关系名。如果插入操作涉及多个关系，必须执行多次PUT操作。     (3) 删除 删除操作用DELETE语句实现。其步骤为： 　　 ·用HOLD语句把要删除的元组从数据库中读到工作空间中 ·用DELETE语句删除该元组 举例 例19 95110学生因故退学，删除该学生元组 HOLD W (Student): Student.Sno=‘95110‘ DELETE W 例20 将学号95001改为95102 HOLD W (Student): Student.Sno=‘95001‘ DELETE W MOVE ‘95102‘ TO W.Sno MOVE ‘李勇‘ TO W.Sname MOVE ‘男‘ TO W.Ssex MOVE ‘20‘ TO W.Sage MOVE ‘CS‘ TO W.Sdept PUT W (Student) 例21 删除全部学生 HOLD W (Student) DELETE W 由于SC关系与Student关系之间的具有参照关系，为保证参照完整性，删除Student关系中全部元组的操作将导致DBMS自动执行删除SC关系中全部元组的操作： HOLD W (SC) DELETE W

  厦门大学计算机科学系   薛永生