元组关系演算语言ALPHA

1、元组关系演算语言 ALPHA元组关系演算1。元组关系演算概念 在元组关系演算系统中，称t|(t) 为元组演算表达式。其中 t 是元组变量， (t) 为元组关 系演算公式，简称公式。它由原子公式和运算符组成。2。原子公式(1) R(t)R 是关系名， t 是元组变量。 R(t) 表示 t 是 R 中的元组。 于是， 关系 R 可表为：t|R(t)(2) Tiujt和u是元组变量，是算术比较运算符。Tiuj表示 元组 t 的第 i 个分量与元组 u 的第 j 个分量满足 比较关系。例如,t2<u3表示元组t的第2个分量小于元组 u 的第 3 个分量 ( 3) tic 或 cti这里 c 是常

2、量 ,该公式表示 t 的第 i 个分量与常量 c 满 足比较关系 。例如 ,t4=3 表示元组 t 的第 4 个分量等于 3。3。若公式中的一个元组变量前有 全称量词 P (universal quantifier ) 或 存在量词 v( existential quantifier ), 则称该变量为约束元组变量,否则称自由元组变量。4。 公式递归定义 定义：(l) 每个原子公式是公式。(2) 如果 1 和 2 是公式，则 1 A 2, 1 V 2，门 1 也是公式。表示： 如果1 和2 同时为真，则 1 A 2 才为真，否则为假； 如果1 和2 中一个或同时为真 ,则 1 V 2 为真,仅

3、当1 和2 同时为假时, 1 V 2 才为假；若1 为真，则门 1 为假。(3) 若 是公式，则 vt() 也是公式。 v t()表示：若有一个t使为真，则 vt() 为真,否则 vt() 为假。(4) 若 是公式，则 Pt() 也是公式。 P t()表示：如果对所有t，都使为真，则 Pt()为真，否则 Pt()为假。(5) 在元组演算公式中 , 各种运算符的优先次序为 :()>算术比较运算符一 > v > P > n> A > V(6) 有限次地使用上述五条规则得到的公式是元组关系演算 公式 ,其他公式不是元组关系演算公式。5。元组关系演算表达式表示关系代

4、数的基本运算 一个元组演算表达式 t|(t) 表示了使 (t) 为真的 元组集合。关系代数的运算均可以用关系演算表达式来表示 (反之亦然 )。下面用关系演算表达式来表示五种基本运算：(1) 并RS=t | R(t) V s(t)(2)差 :RS=t | R(t) An S(t)(3) 笛卡儿积RS=t(n+m)(vu(n)( vv(m)(R(u) A S(v) At1=u1 A A tn=un A tn+1=v1 A A tn+m=vm) 这里 t(n+m) 表示 t 有数目 (n+m)(4) 投影i1,i2,.,ik=t(k)| (vu)(R(u) At1=ui1 A tk=uik)(5)

5、选择 :F(R)=t | R(t) A FF 是公式F用ti代替运算对象i得到的等价公式。例 1 查询信息系 (IS 系 )全体学生。SIS=t | Student(t) A t5= IS例 2 查询年龄小于 20 岁的学生。S20=t | Student(t) A t4<20例 3 查询学生的姓名和所在系。S仁t(2) | (vu)(Student(u) A t1=u2 A t2=u5)6。关系演算的安全限制上面定义的关系演算允许出现无限关系。例如,t| n R(t)表示所有不属于 R 的元组 (元组的目数等于 R 的目数 )。要求出这 些可能的元组是做不到的,所以必须排除这类无意义的

6、表达式。把不产生无限关系的表达式称为安全表达式,所采取的措施称为安全限制。 安全限制通常是定义一个有限的符号集 dom() 。 dom() 一定包括出现在 以及中间结果和最后结 果的关系中的所有符号 (实际上是各列中值的汇集)。dom() 不必是最小集。当满足下列条件时 ,元组演算表达式 t|(t) 是安全的： 如果t使(t)为真，则t的每个分量是 dom() 中的元素。(2) 对于中每一个形如 (vu)(W(u) 的子表达式 ,若 u 使 W(u)为真，则u的每个分量是dom()中的元素。 对于中每一个形如(Pu)(W(u)的子表达式，若u使W(u)为假，则u的每个分量必属于 dom()。换

7、言之， 若u某一分量不属于 dom(),则 W(u)为真。例4设有关系R如图2.8(a),S=t| n R(t),若不进行安全限制， 则可能是一个无限关系。所以定义dom()= A(R)BC(R) =a1,a2,b1,b2,c1,c2则S是dom()中各域值中元素的笛卡儿积与R的差集。结果如图2.8(b)。注意，在做笛卡儿积是各个域中的元素不 能搞混。元组关系演算语言 ALPHA 元组关系演算以元组变量作为谓词变元的基本对象。一种典 型的元组关系演算语言是 E.F.Codd 提出 ALPHA 语言， 这一 语言虽然没有实际实现， 但关系数据库管理系统 INGRES 所 用的 QUEL 语言是参

8、照 ALPHA 语言研制的，与 ALPHA 十 分类似。ALPHA 语言主要有 GET 、PUT 、HOLD 、UPDATE 、DELETE 、 DROP 六条语句，语句的基本格式是：操作语句 工作空间名(表达式) ： 操作条件 其中表达式用于指定语句的操作对象，它可以是关系名或属 性名，一条语句可以同时操作多个关系或多个属性。操作条 件是一个逻辑表达式，用于将操作对象限定在满足条件的元 组中，操作条件可以为空。除此之外，还可以在基本格式的 基础上加上排序要求，定额要求等。以下仍以 P58 的实例讨论 ALPHA 语言： 1、检索操作检索操作用 GET 语句实现。 (1)简单检索(即不带 条件

9、的检索)举例例 1 查询所有被选修课程的课程号码 GET W (SC.Cno) 这里条件为空，表示没有限定条件。 W 为工作空间名。例2 查询所有学生的数据GET W (Student)(2) 限定的检索(即带条件的检索)举例例 3 查询信息系(IS)中年龄小于20岁的学生的学号和年龄GET W (Student.Sno, Student.Sage): Student.Sdept= IS AStudent.Sage<20v (3)带排序的检索举例例 4 查询计 算机科学系(CS)学生的学号、年龄，并按年龄降序排序GET W (Student.Sno, Student.Sage): Stu

10、dent.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)用元组变量的检索详细信息因为元组变量是在某一关系范围内变化的，所以元 组变量又称为范围变量(

11、Range variable)。元组变量主要有 两方面的用途： 简化关系名。在处理实际问题时，如果关系的名字很长， 使用起来就会感到不方便，这时我们可以设一个较短名字的 元组变量来简化关系名。 操作条件中使用量词时必须用元组变量。元组变量是动态的概念，一个关系可以设多个元组变量。例 7 查询信息系学生的名字 RANGE Student XGET W (X.Sname): X.Sdept=IS这里元组变量 X 的作用是简化关系名 Student。 (6)用存在量 词的检索举例例 8 查询选修 2号课程的学生名字RANGE SC XGET W (Student.Sname): H X(X.Sno=

12、Student.Sno A X.Cno=2)例9 查询选修了其直接先行课是6号课程的课程的学生学号RANGE Course CXGET W (SC.Sno): H CX (CX.Cno=SC.Cno A CX.Pcno=6) 例 10 查询至少选修一门其先行课为 6 号课程的学生名字 RANGE Course CXSC SCXGET W (Student.Sname): H SCX (SCX.Sno=Student.Sno AH CX (CX.Cno=SC.Cno A CX.Pcno=6) 本例中的元组关系演算公式可以变换为前束范式( Prenex normal form )的形式：GET W

13、 (Student.Sname): H SCX H CX (SCX.Sno=Student.Sno ACX.Cno=SCX.Cno A CX.Pcno=6)例 8 、例 9 、例 10 中的元组变量都是为存在量词而设的。其 中例 10 需要对两个关系作用存在量词，所以设了两个元组 变量。 (7) 带有多个关系的表达式的检索举例(1) 上面所举的各个例子中，虽然查询时可能会涉及多个关系，即公式中可 能涉及多个关系，但查询结果都只在一个关系中，即表达式 中只有一个关系。实际上表达式中是可以有多个关系的。例 11 查询成绩为 90 分以上的学生名字与课程名字 本查询所要求的结果学生名字和课程名字分别

14、在 Student 和 Course 两个关系中。RANGE SC SCXGET W (Student.Sname, Course.Cname): 3 SCX(SCX.Grade 90 ASCX.Sno=Student.Sno A Course.Cno=SCX.Cno)(8)用全称量 词的检索举例例 12 查询不选 1 号课程的学生名字RANGE SC SCXGET W (Student.Sname): V SCX(SCX.SnoStudent.Sno V SCX.Cno 1 )本例实际上也可以用存在量词来表示：RANGE SC SCXGET W (Student.Sname): 7 3 SC

15、X (SCX.Sno=Student.Sno ASCX.Cno= 1 )(9)用两种量词的检索举例例13查询选修了全部课程的学生姓名RANGE Course CXSC SCXGET W (Student.Sname): V CX H SCX(SCX.Sno=Student.Sno ASCX.Cno=CX.Cno)(10) 用蕴函( Implication )的检索举例例 14 查询最少选修了 95002 学生所选课程的学生学号 本例题的求解思路是，对Course中的所有课程，依次检查每一门课程，看 95002 是否选修了该课程，如果选修了，则再 看某一个学生是否也选修了该门课。如果对于 95002 所选的 每门课程该学生都选修了，则该学生为满足要求的学生。把 所有这样的学生全都找出来即完成了本题。RANGE Couse CXSC SCXSC SCYGET W (Student.Sno): V CX(H SCX (SCX.Sno=95002 ASCX.Cno=CX.Cno)=> H SCY (SCY.Sno=Student.Sno ASCY.Cno=CX.Cno)(11) 集函数举例用户在使用查询语言时， 经常要作一些简单的计算，例如要求符合某一查询要求的元 组数，求