πσ
SC.C#
C
S.S#=SC.S#
×
图2.3
?
? 2.22 为什么要对关系代数表达式进行优化？有哪三条启发式规则？对优化起什么作用？
答：关系代数表达式由关系代数操作组合而成。操作中，以笛卡尔积和联接操作最费时，并生成大量的中间结果。如果直接按表达式书写的顺序执行，必将花费很多时间，并生成大量的中间结果，效率较低。在执行前，由DBMS的查询子系统先对关系代数表达式进行优化，尽可能先执行选择和投影操作，以便减少中间结果，并节省时间。 优化工作是由DBMS做的，用户书写时不必关心优化一事，仍以简练的形式书写。
? 三条启发式规则是：尽可能早执行选择操作；尽可能早执行投影操作；把笛卡尔积与附近的一连串选择和投影合并起来做。
? 使用这三条规则，可以使计算时尽可能减少中间关系的数据量。
? 2.23 试解释关系逻辑中的名词:
? ·谓词：在关系逻辑中，每一个谓词符号表示了一个关系，但在规则中谓词符号类似于关系演算中的公式。
? ·外延谓词：其关系存储在数据库中的谓词称为“外延谓词”。 ? ·内涵谓词：由逻辑规则定义的谓词称为“内涵谓词”。
·外延数据库：用“外延数据库”的缩写EDB来引用外延谓词或相应关系。 ·内涵数据库：用“内涵数据库”的缩写IDB来引用内涵谓词或相应关系。
? ·原子：关系逻辑中的基本成分，称为原子。原子有关系原子和算术原子两种。 ? ·关系原子：关系原子是一个谓词符号，带一个参数表，每个参数可以是变量或常量。用大写字母表示谓词符号，用小写字母表示变量，常量用引号括起来。 ? ·算术原子：算术原子是算术比较表达式。
·规则：规则是形为W←P1∧P2∧…∧Pn的式子，规则有三部分组成： ① 一个称为头部（head）的关系原子；
② 符号“←”，通常读作“if”； ③ 包括一个或多个原子的体（body），称为子目标（subgoal），它可能是关系原子，也可能是算术原子。各子目标用“与”运算符 ∧ 连接，并且子目标前面可以有“非”运算符┐，也可以没有。
? ·查询：关系逻辑中的查询是一个或多个规则的聚集，规则之间的顺序无关紧要。
? 2.24 假设R（A，B，C），S（A，B，C）和T（A，B，C）为三个关系。试对下列关系代数表达式写出关系逻辑的规则或规则集：
? ① R∪S ② R∩S ③ R－S ④（R∪S）－T
? ⑤（R－S）∩（R－T） ⑥ πa，b(R) ? ? ? ? ? ? ? c)
? ⑥ πa，b(R): W(a，b)←R(a，b，c)
? 2.25 假设R（X，Y，Z）为一个关系，试写出下列关系代数表达式σF(R)的关系逻辑规则。其中F为以下条件：
? ① x = y ② x ? 解: ① F为x = y，此时关系选择规则为： ? W(x，y，z)←R(x，y，z) ∧ x=y ? ② F为x ? W(x，y，z)←R(x，y，z) ∧x ? ③ F为x ? W(x，y，z)←R(x，y，z) ∧x ? ④ F为┐(x ? ⑤ F为┐((x ? W(x，y，z)←R(x，y，z) ∧ x=y ? W(x，y，z)←R(x，y，z) ∧ y≥z ? ⑥ F为┐((x ? W(x，y，z)←R(x，y，z) ∧ x≥y ∧ x≥z ? W(x，y，z)←R(x，y，z) ∧ y≥z ? ? 2.26 假设R（A，B，C），S（B，C，D）和T（D，E）为三个关系。对每个自然联接写出单一的规则： 解: ① R∪S:W(a，b，c)←R(a，b，c) W(a，b，c)←S(a，b，c) ② R∩S: W(a，b，c)←R(a，b，c) ∧ S(a，b，c) ③ R－S: W(a，b，c)←R(a，b，c) ∧┐ S(a，b，c) ④（R∪S）－T: W(a，b，c)←R(a，b，c) ∧┐ T(a，b，c) W(a，b，c)←S(a，b，c) ∧┐ T(a，b，c) ⑤（R－S）∩（R－T）: W(a，b，c)←R(a，b，c) ∧┐ S(a，b，c) ∧┐ T(a，b， ? ① R S ② S T ③ （R S） T ? 解: ① R S: ? W（a，b，c，d）← R（a，b，c）∧ S（b，c，d） ? ② S T: ? W（b，c，d，e）← R（b，c，d）∧ S（d，e） ? ③ （R S） T ? W（a，b，c，d，e）← R（a，b，c）∧ S（b，c，d）∧ T（d，e） ? 2.27 对下列每个规则，写出关系代数表达式来定义与规则头部相同的关系： ? ① W（x，y）← Q（x，z）∧ R（z，y） ? ② W（x，y）← Q（x，z）∧ Q（z，y） ? ③ W（x，y）← Q（x，z）∧ R（z，y）∧ x ? ③π1,4（σ2=3∧ 1<4（Q×R）） ? 2.28 试用关系逻辑的规则来定义第2.17题的各个查询语句。 解: ① 检索LIU老师所授课程的课程号和课程名。 W（a，b）← C（a，b，'LIU'） ② 检索年龄大于23岁的男学生的学号和姓名。 W（a，b）← S（a，b，h，'M'）∧ h>23 ③ 检索学号为S3学生所学课程的课程名与任课教师名。 W（a，b）← SC（'S3'，e，f）∧ C（e，a，b） ④ 检索至少选修LIU老师所授课程中一门课的女学生姓名。 W（f）← S（e，f，g，'F'）∧ SC（e，h，i）∧ C（h，j,'LIU'） ⑤ 检索WANG同学不学的课程的课程号。 W（a）← C（a，b，d）∧ S（e，'WANG',f，g）∧ ┐SC（e，a，h） ⑥ 检索至少选修两门课的学生学号。 W（a）← SC（a，e，f）∧ SC（a，g，h）∧ e≠g ⑦ 检索全部学生都选修的课程的课程号与课程名。 W（a,b）← C（a，b，e）∧ ┐S（f，g，h，i）∧ ┐SC（f，a，j） ⑧ 检索选修课程包含LIU老师所授全部课程的学生学号。 W（a）← SC（a，b，e）∧ ┐C（f，g，'LIU'）∧ ┐SC（a，f，h） ? ? ? ? 2.29 试撰写短文，对关系运算的三种形式作一评估。 答：短文应提到以下几点： （1）三种关系运算的理论基础。 （2）三种关系运算的等价性。 ? 关系代数和关系演算在关系代数的五个基本操作的基础上是等价的。 ? 关系代数和关系逻辑在表达功能方面不相适应，每个都能表达另一个不能表达的内容。在作了严格的限制后，才能等价。但关系逻辑比关系代数更富于表现力。 ? （3）三种关系运算非过程性的强弱不一样。 2.3 自测题 2.3.1 填空题 1．关系中没有行序的原因是___________。 2. 3．关系模型的基本数据结构是___________，其数据库存储时的基本组织方式是___________。 4．实体完整性规则是对___________的约束，参照完整性规则是对___________的约束。 5．关系代数的理论基础是___________，关系演算的理论基础是___________，关系逻辑的理 论基础是___________。 6．关系代数的基本操作是___________。 7．安全运算是指不产生___________和___________的运算。 8．等式R S = R×S成立的条件是___________。 9．关系的并、差、交操作，要求两个关系具有___________。 10．一般，在关系代数运算中，当查询涉及到“否定”时，就要用到___________操作；当查 询涉及到“全部值”时，就要用到___________操作。 11．如果关系R和S做自然联接时，只把R中原该舍去的元组放到新关系中，那么这种操作 称为___________操作。 12．等式πL（σF（E））=σF（πL（E））成立的条件是___________。 13．等式πL1（πL2（E））=πL1（E）成立的条件是___________。 14．等式σF（E1×E2）= E1×σF（E2）成立的条件是___________。 15．等式σF（E1?E2）= σF（E1）?σF（E2）成立的条件是___________。 16.关系逻辑中，外延谓词是指_______________，内涵谓词是指_______________。 17.关系逻辑中的“安全条件”是指____________________。 18.设有关系R（A，B，C），那么与规则W（c，a）← R（a，b，c） 等价的关系代数操作是____________。 19.设有关系R（A，B，C），那么与规则W（a，b）← R（a，b，'18'）∧b≥'15' 等价的关系代数操作是____________。 20.设有关系R（A，B，C）和S（B，C，D），那么与规则 W（a，d）← R（a，b，c）∧ S（b，c，d） 等价的关系代数操作是____________。 2.3.2 单项选择题（在备选答案中选出一个正确答案） 1．在关系中，“元数”（arity）是指 [ ] A．行数 B．元组个数 C．关系个数 D．列数 2．在关系中，“基数”（cardinality）是指 [ ] A．行数 B．属性个数 C．关系个数 D．列数 3．由系统进行数据导航的语言称为 [ ] A．第三代语言 B．高级程序设计语言 C．过程性语言 D．非过程性语言 4．设关系R、S、W各有10个元组，那么这三个关系的自然联接的元组个数为 [ ] A．10 B．30 C．1000 D．不确定（与计算结果有关） 5．设W = R S，且W、R、S的元组个数分别为p、m、n，那么三者之间满足 [ ] iθj A．p＜（m+n） B．p≤（m+n） C．p＜（m×n） D．p≤（m×n） 6．设关系R和S的结构相同，且各有10个元组，那么这两个关系的并操作结果的元组个数 为 [ ] A．10 B．小于等于10 C．20 D．小于等于20 7．设关系R和S的属性个数分别为2和3，那么 R S等价于 1<2 [ ] A．σ1<2（R×S） C．σ1<2（R S） B．σ1<4（R×S） D．σ1<4（R S） ] 8．如果两个关系没有公共属性，那么其自然联接操作 [ A．转化为笛卡尔积操作 B．转化为联接操作 C．转化为外部并操作 D．结果为空关系 9．下列式子中，不正确的是 [ ] A．R－S=R－（R∩S） B．R=（R－S）∪（R∩S） C．R∩S=S－（S－R） D．R∩S=S－（R－S） 10．设关系R和S都是二元关系，那么与元组表达式 { t | (u) (v) (R(u) ∧ S(v) ∧ u[1]=v[1] ∧ t[1]=v[1] ∧ t[2]=v[2])} 等价的关系代数表达式是 [ ] A．πC．π 3，4（R?S） 3，4（R?S） B．πD．π 2，3（R?S） 1=3 1=1 3，4（σ1=1（R×S）） 11．在元组关系演算中，与公式P1∧P2等价的公式是 A．┐(P1∨P2) B．┐P1∨┐P2 C．┐(┐P1∧┐P2) D．┐(┐P1∨┐P2) 12．在元组关系演算中，与公式（s）（P1（s））等价的公式是 A．┐(s)(P1(s)) B．(s)(┐P1(s)) C．┐(s)(┐P1(s)) D．┐(s)(┐P1(s)) 13．在元组关系演算中，与公式P1=>P2等价的公式是 A．┐P1∨P2 B．┐P2∨P1 C．┐P1∧P2 D．┐P2∧P2 14．与域演算表达式{ab | R（ab）∧ R（ba）}不等价的关系代数表达式是 A．π 1，2（σ1=4∧2=3（R×R）） [ ] [ ] [ ] [ ] B．π 1，2（R ? R） 1=2∧2=1 C．R∩π2，1（R） D．σ1=2（R） 15．设R和S都是二元关系，那么与元组演算表达式 { t | (u) (v) (R(u)∧S(v)∧u[2]=v[2]∧t[1]=u[1]∧t[2]=v[1])} 等价的关系代数表达式是 A．πC．π 1，3（σ2=4（R?S）） 1，3（R 2＝4 [ ] B．π 1，3（σ2=2（R×S）） 1，3（R 2＝2 ?S） D．π?S） 16．设有关系R（A，B，C）和S（B，C，D），那么与R?S等价的关系代数表达式是 2=1 2=1 [ ] A．σ3=5（R?S） B．π 1，2，3，6（σ3=5（R ? S）） 3=2∧2=1（R×S）） C．σ3=5∧2=4（R×S）） D．π1，2，3，6（σ17．设R和S都是二元关系，那么与元组演算表达式