关系代数、关系演算、关系逻辑

1、关系代数、关系演算、关系逻辑数据库技术内容提要一、关系模型的基本术语二、关系查询语言的基础关系代数关系演算关系代数表达式的优化关系逻辑一、关系模型的基本术语关系模式属性值域元组关系（实例）元数基数ABCDEa1 b1c1d1e1a2 b2c2d2e2a3 b3 c3d3e3a4 b4c4d4e4属性元组1元组2元组3元组4属性值元数=5 基数=4R关系模式名关系一、关系模型的基本术语超键候选键主键外键二、关系查询语言关系代数基本操作并(Union)差笛卡尔积投影选择并（union）符号表示：RS 前提条件：R和S有相同的关系模式形式定义：RSt | tR tS 差（difference）符号表

2、示：RS 前提条件：R和S有相同的关系模式形式定义：RS t | tR tS 笛卡尔积（Cartesian Product）符号表示：RS 形式定义： RS t | t trR tsS ABCabcdafcbdDEFbgadafABCDEFabcbgaabcdafdafbgadafdafcbdbgacbddaf关系R关系SRS 投影（Projection）符号表示：i1，im（R） 形式定义：i1，im（R） t | tti1，timt1，tkR ABCabcdafcbdCAcafddc关系RC，A（R）3，1（R）选择（selection）符号表示：F（R） 形式定义：F（R） t | tR

3、 F（t）= true 其中F包括：运算对象和运算符ABCabcdafcbdABCabccbd关系RB=b（R） 二、关系查询语言关系代数2. 组合操作交（Intersection）联接（Join）自然联接（Natural Join）除法 （Division）交（Intersection）符号表示：RS 前提条件：关系R和S具有相同的关系模式形式定义：RSttR tS 联接（Join）联接 R S t t= trR tsS 含义：从关系R和关系S中选取满足某一操作的元组。F联接 RS，其中F是形为F1F2Fn的公式，每个FP是形为ij的式子 ij F自然联接（Natural Join）符号表示

4、：设R和S具有公共属性A1.Ak。则形式定义为： i1,im (R.A1=S.A1.R.AK=S.AK(RS), 其中i1,im为R和S的全部属性，但公共属性只出现一次。 R S 除法（Division）符号表示：RS前提：S的属性集是R的属性集的子集含义：下列条件的最大关系：其中每个元组t与S中每个元组u组成的新元组必在关系R中 设r和s分别为R和S的元数，假设S的属性为R中后s个属性，则RS的计算过程为： T = 1，2，r-s（R） W =（TS）-R（计算TS中不在R的元组） V = 1，2，r-s （W） RS = T V SNOSNAMECNOCNAMES1BAOC1DBS1BAO

5、C2OSS1BAOC3DSS1BAOC4MISS2GUC1DBS2GUC2OSS3ANC2OSS4LIC2OSS4LIC4MISCNOCNAMEC2OSCNOCNAMEC1DBC2OSC4MISSNOSNAMES1BAOS2GUS3ANS4LISNOSNAMES1BAORS1S2RS1RS2例：设教学数据库中有三个关系： 学生关系S（S#，SNAME，AGE，SEX） 学习关系SC（S#，C#，GRADE） 课程关系C（C#，CNAME，TEACHER） 检索学习课程号为C2的学生学号与成绩。 S#，GRADE（C#=C2（SC） 检索学习课程号为C2的学生学号与姓名。 S#，SNAME（C#

6、=C2（SSC） 检索选修课程名为MATHS的学生学号与姓名。 S#，SNAME（CNAME=MATHS（SSCC） 检索选修课程号为C2或C4的学生学号。 S#（C#=C2C#=C4（SC） 检索至少选修课程号为C2和C4的学生学号。 1（1=42=C25=C4（SCSC） 检索不学C2课的学生姓名与年龄。 SNAME，AGE（S）SNAME，AGE（CNO=C2（SSC） 检索学习全部课程的学生姓名 SNAME（S（S#，C#（SC）C#（C）编写这个查询语句的关系代数表达式过程如下：学生选课情况可用操作S#，C#（SC）表示；全部课程可用操作C#（C）表示；学了全部课程的学生学号可用除法

7、操作表示，操作结果是学号S#集： S#，C#（SC）C#（C）从S#求学生姓名SNAME，可以用自然联接和投影操作组合而成： SNAME（S（S#，C#（SC）C#（C） 检索所学课程包含学生S3所学课程的学生学号。学生选课情况可用操作S#，C#（SC）表示；学生S3所学课程可用操作C#（S#=S3（SC）表示；所学课程包含学生S3所学课程的学生学号，可以用除法操作求得： S#，C#（SC）C#（S#=S3（SC） 二、关系查询语言关系代数3. 扩充操作改名广义投影赋值外联接外部并半联接聚集操作改名 S(A1,An)（R），表示将关系R改名为S，而R中的属性依次命名为 A1,An 。如 设关系

8、R(A,B)和S(B,C,D),则RS可以表示成RS(X，C，D)（S）广义投影 使用算术函数，如 S#，C#，GRADE*1.05（C#=C4（SC） 赋值 “” ，把赋值运算符右侧的表达式结果赋给左侧的关系，如 TEMP1 1，2，r-s（R） 外联接ABa1b1a2b2ACa1c1a3c3ABCa1b1c1a2b2nullABCa1b1c1a3nullc3ABCa1b1c1a2b2nulla3nullc3RSRSRSRS外部并 元组在新增加的属性上填上空值半联接 R S R（RS）聚集操作 使用聚集函数max,min,avg,sum,count 。例如： 在S（S#，SNAME，AGE，

9、SEX）中，求男同学的平均年龄，可以用式子 avgage（sex=M（S）表示，求年龄为18岁的人数可用式子countS#（age=18（S） 三、关系查询语言关系演算元组关系演算元组表达式 元组表达式的一般形式为 t | P（t），表示满足公式P的所有元组t的集合。 原子公式R（s） “s是关系R的一个元组”siuj “元组s的第i个分量和u的第j个分量之间满足关系 ”sia “元组s的第i个分量值与常量a之间满足关系” 公式每个原子是一个公式。如果P1和P2是公式，那么P1、P1P2、P1P2和P1P2也都是公式。 如果P1是公式，那么（s）（P1）和（s）（P1）也都是公式。 公式中各种

10、运算符的优先级从高到低依次为：，和，和，。在公式外还可以加括号，以改变上述优先顺序。 公式只能由上述四种形式构成，除此之外构成的都不是公式。 例：设教学数据库中有三个关系： 学生关系S（S#，SNAME，AGE，SEX） 学习关系SC（S#，C#，GRADE） 课程关系C（C#，CNAME，TEACHER） 检索学习课程号为C2的学生学号与成绩。 t|(u)（SC(u)u2=C2tl=u1t2=u3） 检索学习课程号为C2的学生学号与姓名。 t|(u)(v)（S(u)SC(v)v2=C2ul=v1tl=u1t2=u2） 检索选修课程名为MATHS的学生学号与姓名 t|(u)(v)(w)（S(u

11、)SC(v)C(w)ul=v1v2=w1w2=MATHStl=u1t2=u2） 检索选修课程号为C2或C4的学生学号 t|(u)（SC(u) （u2=C2u2=C4）tl=u1） 关系代数表达式与元组表达式的转换 RS t | R（t）S（t） ； R-S t | R（t）S（t） ； RS t |（u）（v）（R（u）S(v) t1=u1 t2=u2t3=u3t4=v1 t5=v2 t6=v3） ； 2,3（R） t |(u)（R（u）tl=u2t2=u3） 检索至少选修课程号为C2和C4的学生学号 t|(u)(v)(SC(u)SC(v)u2=C2v2=C4 ul=v1tl=u1) 检索不学

12、C2课的学生姓名与年龄 t|(u)(v)（S(u)SC(v)（ul=v1 v2C2） t1=u2 t2=u3） 检索学习全部课程的学生姓名 t|(u)(v)(w)（S(u)C(v)SC(w)ul=w1v1=w2t1=u2） 检索所学课程包含学号S3所学课程的学生。 t|(u)(SC(u)(v)(SC(v)(v1=S3 (w)(SC(w)w1=u1w2=v2)tl=u1) 域关系演算域演算表达式 t1tkP（t1，tk）, P（t1，tk）是关于域变量t1，tk 的公式。原子公式R（x1xk），R是一个k元关系，每个xi是常量或域变量； xy，其中x、y是常量或域变量 ，是算术比较符公式 同元组

13、关系演算的公式定义 R1= xyz| R（xyz） x3 R2= xyz| R（xyz）（S（xyz） y = 4）R3= xyz|（u）（v）（R（zxu） w（yv） uv ） ABC123346569ABC123456789DE7548ABC455BDA574877847ABC123456789346关系R关系S关系WR1R2R3元组表达式到域表达式的转换对于k元的元组变量t，可引入k个域变量t1tk，在公式中t用t1tk替换，元组分量ti用ti替换。 对于每个量词（u）或（u），若u是m元的元组变量，则引入m个新的域变量u1um。在量词的辖域内，u用u1um替换，ui用ui替换，（u）

14、用（u1）（um）替换，（u）用（u1）（um）替换。对于前面的例子： 检索学习课程号为C2的学生学号与成绩元组表达式： t|(u)（SC(u)u2=C2tl=u1t2=u3）域表达式： t1t2|(u1)(u2)(u3)(SC(u1u2u3)u2=C2t1=u1t2=u3) 可化简为： t1t2|（SC(t1C2t2) ） 检索学习课程号为C2的学生学号与姓名元组表达式： t|(u)(v)（S(u)SC(v)v2=C2ul=v1tl=u1t2=u2）域表达式： t1t2|(u1)(u2)(u3)(u4)(v1)(v2)(v3)（S（u1u2u3u4）SC（v1v2v3）v2= C2u1=v1

15、t1=u1t2=u2） 可化简为： t1t2|(u3)(u4)(v3)（S（t1t2u3u4）SC（t1C2v3） 四、关系代数表达式的优化关系代数表达式的等价变换规则 联接和笛卡尔积的交换律 设El和E2是关系代数表达式，F是联接的条件，那么下列式子成立（不考虑属性间顺序）： E1E2 E2 E1 E1E2 E2 E1 E1 E2 E2 E1 联接和笛卡尔积的结合律 设El、E2和E3是关系代数表达式，F1和F2是联接条件，F1只涉及到E1和E2的属性，F2只涉及到E2和E3的属性，那么下列式子成立： （E1 E2）E3 E1（E2E3） （E1 E2） E3 E1（E2E3） （E1 E2

16、） E3 E1 （E2 E3）FFF1F2F1F2涉及到选择和投影的规则有下面的十条： 投影的级联 L1（L2（Ln（E）L1（E） 此处L1、L2、Ln为属性集，并且L1L2Ln。 选择的级联 F1（F2（E）F1 F2（E） 由于F1 F2 = F2 F1，因此选择的交换律也成立： F1（F2（E）F2（F1（E） 选择和投影操作的交换 L（F（E）F（L（E） 此处要求F只涉及到L中的属性，如果条件F还涉及到不在L中的属性集L1，那么下式成立： L（F（E）L（F（LL1（E）选择对笛卡尔积的分配律 F(E1E2)F(E1)E2(此处F只涉及到E1中的属性） 如果F形为F1 F2，且F1

17、只涉及到E1的属性，F2只涉及到E2的属性，那么使用规则和可得到下列式子： F（E1E2）F1（E1）F2（E2） 如果F形为F1 F2，且F1只涉及到E1的属性，F2只涉及到E1和E2的属性，那么可得下式： F（E1E2）F2（F1（E1）E2） 也就是把一部分选择条件放到笛卡尔积中关系的前面。选择对并的分配律 F（E1E2）F（E1）F（E2） 此处要求E1和E2具有相同的属性名，或者E1和E2表达的关系的属性有对应性。选择对集合差的分配律 F（E1E2）F（E1）F（E2）或者，F（E1E2）F（E1）E2 此处也要求E1和E2的属性有对应性。由于求F（E2）比求E2容易得多，因此一般使

18、用前一个式子。选择对自然联接的分配律。 F （E1 E2） F （E1） F （E2） 此处要求F只涉及到表达式E1和E2的公共属性；投影对笛卡尔积的分配律 L1L2（E1E2）L1（E1）L2（E2）此处要求L1是E1中的属性集，L2是E2中的属性集。投影对并的分配律 L（E1E2）L（E1）L（E2）此处要求E1和E2的属性有对应性。选择与联接操作的结合 根据F联接的定义可得F（E1 E2） E1 E2F1（E1 E2） E1 E2涉及到集合操作的有下面两条规则：并和交的交换律 E1E2 E2E1 E1E2 E2E1并和交的结合律 （E1E2）E3 E1（E2E3） （E1E2）E3 E1

19、（E2E3）F1F2F2四、关系代数表达式的优化2.启发式优化算法 在关系代数表达式中，最花费时间和空间的运算是笛卡尔积和联接操作，为此，引出三条启发式规则，用于对表达式进行转换，以减少中间关系的大小。尽可能早地执行选择操作；尽可能早地执行投影操作；避免直接做笛卡尔积，把笛卡尔积操作之前和之后的 一连串选择和投影合并起来一起 做。 通常选择操作优先于投影操作比较好，因为选择操作可能会大大减少关系，并且选择操作可以利用索引存取元组。例: 对于教学数据库 S (S#，SNAME，AGE，SEX) SC (S#，C#，GRADE) C (C#，CNAME，TEACHER) 现有一个查询语句：检索至少

20、学习LIU老师所授一门课程的女学生学号和姓名。该查询语句的关系代数表达式如下： S#，SNAME（TEACHER=LIUSEX=F(C SC S)） 上式中， 符号用、操作表示，可得下式： S#，SNAME（TEACHER=LIUSEX=F(L（C.C# = SC.C#SC.S# = S.S#（CSCS）)） 此处L是（C.C#，CNAME，TEACHER，S.S#，GRADE，SNAME，AGE，SEX）。该表达式构成的语法树如下图所示。 S.S#，SNAMEC.C#，CNAME，TEACHER，S.S#，GRADE，SNAME，AGE，SEXTEACHER=LIUSEX=FC.C# = S

21、C.C#SC.S# = S.S#SSCC图2-2 关系代数表达式的语法树 使用等价变换规则，把四个选择操作尽可能向树的叶端靠拢。据规则和可以把TEACHER =LIU和SEX =F移到投影和另外两个选择操作下面，直接放在笛卡尔积外面得到子表达式： TEACHER =LIU（SEX =F（CSC）S） 其中，外层选择仅涉及到关系C，内层选择仅涉及到关系S，所以上式又可变换成： （TEACHER=LIU(C)SC）SEX =F(S) SC.S# = S.S# 不能再往叶端移动了，因为它的属性涉及到两个关系SC和S，但 C.C# = SC.C# 还可向下移，与笛卡尔积交换位置。 然后根据规则，再把两

22、个投影合并成一个投影S#，SNAME 。这样，原来的语法树（图2-2）变成了图2-3的形式。图2-3 优化过程中的语法树S.S#，SNAMESC.S# = S.S#SCSEX =FSCC.C#=SC.C#TEACHER=LIU据规则，把投影和选择进行交换，在前增加一个投影操作。 用 代替S.S#, SNAME和SC.S# = S.S#。 再把SC.S#,S.S#,SNAME分成SC.S#和S.S#,SNAME，使它们分别对C.C# = SC.C#（）和 SEX =F（）做投影操作。 再据规则，将投影SC.S#和S.S#,SNAME分别与前面的选择操作形成两个级联运算： 图2-4中用虚线划分了两

23、个运算组。S.S#，SNAMESC.S# = S.S#SC.S#，S.S#，SNAMESC.S#S.S#,SNAMEC.C# = SC.C#C.C#, SC.S#,SC.C#SEX=FS#, SNAME, SEXSEX = FC.C#=SC.C#图2-4 优化的语法树及其分组S.S#，SNAMESC.S# = S.S#SS.S#,SNAMESC.S#C.C#TEACHER=LIUCSCSC.S#,SC.C#五、关系查询语言关系逻辑谓词和原子谓词 用谓词符号表示关系。例如，P是谓词符号，可以用P(x,y,z)，变量x,y,z分别表示与谓词P相对应的关系的某元组的第一、第二、第三个成分。 谓词分两

24、种：外延谓词和内涵谓词原子 关系逻辑中的谓词分为两种：关系原子是一个谓词符号，带一个参数表，每个参数可以是变量或常量。用大写字母表示谓词符号，用小写字母表示变量，常量用引号括起来。 算术原子是算术比较表达式 例如，关系R(A,B,C)，那么关系原子R(2345,b,c)代表关系代数表达式1=2345(R) ；关系原子R(x,b,x)表示了关系代数表达式1=3(R) 。规则和查询规则 规则是形为WP1P2Pn的式子，规则有三部分组成：一个称为头部（head）的关系原子；符号“”，通常读作“if”；包括一个或多个原子的体（body），称为子目标（subgoal），它可能是关系原子，也可能是算术原子

25、。各子目标用“与”运算符 连接，并且子目标前面可以有“非”运算符，也可以没有。含义：if（P1P2Pn）then W 例如：设关系S（S#，SNAME，AGE，SEX），现有一个规则 W（a，b） S（a，b，c，M） c20规则的头部： W（a，b）第一个子目标：谓词S和4个参数，对应于关系S的4个属性。这些参数中的每一个都有不同的值：a、b、c分别对应于S#、SNAME、AGE等分量，常量M表示第4个分量的值。这个子目标是在表明“（a，b，c，M）是关系S中的元组”这样一个断言。 第二个子目标：算术原子c20。当S中元组的AGE值大于20时为真。该规则等价于关系代数表达式： W=S#，SNAME（AGE20 SEX=M(S)） 用关系逻辑的规则模拟关系代数操作交 设有关系R(A,B,C)和S(A,B,C)，那么RS 用规则表示为：W（a，b，c） R（a，b，c） S（a，b，c） 并 W（a，b，c） R（a，b，c） W（a，b，c） S（a，b，c）差 W（a，b，c） R（a，b，c）S（a，b，c） 投影 C，A（R） 用规则表示为： W（c，a） R（a，b，c）选择 设有关系R(A,B,C) B5 C=18(R)可以写成下列规则： R（a，b，c） R（a，b，c） B5 C=18 B5 C=18(R)可以用下面两个规则表示 R（a