? 解：

? 操作 ? ⑴ U∩V ? ⑵ U∪V ? ⑶ U?V ? ⑷σF(U)×V

? ⑸πL(U)－V

? 最小元组数

? 0 ?max(m,n) ? 0 ? 0 ? 0

? 最大元组数 ?min(m,n) ?m+n ?m×n ?m×n ?m

2.9 如果R是二元关系，那么下列元组表达式的结果是什么？

{t|( u)(R(t) ∧R(u) ∧(t[1] ≠u[1]∨t[2] ≠u[2]))}

答：当R的元组数≥2时，R中每个元组都存在与之不相同的元组，因此表达式的结果为关系R； 当R的元组数为0或1时，表达式的结果为空关系。

2.10 假设R和S分别是三元和二元关系，试把表达式π1,5(σ2=4∨3=4(R×S))转换成 等价的:①汉语查询句子;②元组表达式;③域表达式。

解：⑴ 在关系R和S的笛卡尔积中，选取第2个属性值与第4个属性值相等，或者第3个属性值与第4个属性值相等的那些元组，再取第1列和第5列组成新的关系。

⑵ 与（R×S）等价的元组表达式是：

{ t | (u) (v) (R(u) ∧ S(v) ∧ t[1]=u[1] ∧ t[2]=u[2] ∧ t[3]=u[3] ∧ t[4]=v[1]∧

t[5]=v[2] )}

与σ2=4 ∨ 3=4（R×S）等价的元组表达式是：

{ t | (u) (v) (R(u) ∧ S(v) ∧ t[1]=u[1] ∧ t[2]=u[2] ∧ t[3]=u[3] ∧ t[4]=v[1]∧

t[5]=v[2] ∧ (t[2]=t[4] ∨ t[3]=t[4]))}

与π1，5（σ2=4 ∨ 3=4（R×S））等价的元组表达式是：

{ w | (t) (u) (v) (R(u) ∧ S(v) ∧ t[1]=u[1] ∧ t[2]=u[2] ∧ t[3]=u[3] ∧

t[4]=v[1] ∧ t[5]=v[2] ∧ (t[2]=t[4] ∨ t[3]=t[4]) ∧ w[1]=t[1] ∧w[2]=t[5])}

再对上述元组表达式化简（消去t）可得：

{ w | (u) (v) (R(u) ∧ S(v) ∧ (u[2]=v[1] ∨ u[3]=v[1]) ∧ w[1]=u[1] ∧

w[2]=v[2])}

在熟练后，可以直接写出上式。 ⑶ 再转换成域表达式：

{ w1 w2 | (u1) (u2) (u3) (v1) (v2) (R(u1u2u3) ∧ S(v1v2) ∧ (u2=v1 ∨ u3=v1)

∧ w1=u1 ∧ w2=v2)}

再化简（消去u1，v2）可得：

{ w1 w2 | (u2) (u3) (v1) (R(w1u2u3) ∧ S(v1w2) ∧ (u2=v1 ∨ u3=v1))}

2.11 假设R和S都是二元关系，试把元组表达式{t|R(t) ∧(成等价的：

①汉语查询句子; ②域表达式; ③关系代数表达式。

u)(S(u) ∧u[1] ≠t[2])}转换

答：①在关系R中选取第2列的值与关系S中某个元组的第1列值不相等的那些元组，组成新的关系。

②域表达式为：

{ t1t2 | R(t1t2)∧(u1) (u2) ( S(u1u2) ∧ u1≠t2)} ③关系代数表达式为：

π

1，2（σ2≠3（R×S））或π1，2（R?S）

2≠1

2.12 试把域表达式{ ab | R(ab) ∧ R(ba)}转换成等价的：⑴汉语查询句子；⑵关系代数表达式；⑶元组表达式。

解：⑴ 在关系R中选取属性值交换后仍是R中元组的那些元组，组成新的关系。 ⑵ 关系代数表达式为：π1，2（σ1=4 ∧ 2=3（R×R））

也可写成：R∩π2，1（R） ⑶ 元组表达式为：{ t | (u) (v) (R(u) ∧ R(v) ∧ u[1]=v[2] ∧ u[2]=v[1] ∧ t[1]=u[1]

∧ t[2]=u[2])}

或：{ t | (v) (R(t) ∧ R(v) ∧ t[1]=v[2] ∧ t[2]=v[1])}

2.13 有两个关系R (A, B, C)和是S（D, E, F）,试把下列关系代数表达式转换成等价的元组表达式: ①πA(R)； ②σB=’17’(R)；

③ R×S； ④πA,F(σC=D(R×S) 解：①πA（R）：{ t | (u) ( R(u) ∧ t[1]=u[1])} ②σB='17'（R）：{ t | R(t) ∧ t[2]= '17'}

③ R×S：{ t | (u) (v) ( R(u) ∧ S(v) ∧ t[1]=u[1] ∧ t[2]=u[2] ∧t[3]=u[3]

∧ t[4]=v[1] ∧t[5]=v[2] ∧t[6]=v[3])}

④πA，F（σC=D（R×S））：{ t | (u) (v) ( R(u) ∧ S(v) ∧ u[3]=v[1] ∧ t[1]=u[1]

∧ t[2]=v[3])}

? 2.14 设有关系R（A，B，C）和S（A，B，C），试把下列关系代数表达式转换成等价的域表达式：

① πA(R) ② σ2=′17′(R) ③ R∪S ⑤ R－S

④ R∩S

⑥ π1,2（R） π2,3（S） u2) (

u3) ( R(t1u2u3))}

解：① πA(R): { t1 | (

② σ2=′17′(R): { t1t2t3 | R(t1t2t3) ∧ t2= '17'}

③ R∪S：{ t1t2t3 | R(t1t2t3) ∨ S(t1t2t3)}

④ R∩S：{ t1t2t3 | R(t1t2t3) ∧ S(t1t2t3)} ⑤ R－S：{ t1t2t3 | R(t1t2t3) ∧┓ S(t1t2t3)}

⑥ π1,2（R：{ t1t2t3 | (u3) (v1) | R(t1t2u3) ∧ S(v1t2t3)} ） π2,3（S）

? 2.15 设有关系R（A，B）和S（A，C），试把下列域表达式转换成等价的关系代数表达式：

? ① {a |（b）（R（ab）∧ b=17）} ? ② {abc |（R（ab）∧ S（ac））} ? ③ {a |（b）（R（ab））∨（c）（（d）（S（dc））?S（ac））} ? ④ {a |（c）（S（ac）∧（b1）（b2）（R（ab1）∧R（cb2）∧b1>b2））}

? 解：① π1（σ2=′17′（R）） ? ② R?S

? ③ π1（R）∪（S÷π2（S））

? ④ π1（σ1=3 ∧ 2=5 ∧ 4>6（S×R×R））

2.16 设两个关系R (A，B )和S (A，C )。用null表示空值，分别写出等价于下列表达式的元组关系演算表达式：

① R S； ② R S； ③ R S 。 解：① R S：

{ t | (u) (v) (R(u) ∧ S(v) ∧ u[1]=v[1] ∧ t[1]=u[1] ∧t[2]=u[2] ∧ t[3]=v[2])

∨ (v) (u) (S(v) ∧ R(u) ∧ v[1]≠u[1] ∧ t[1]=null ∧t[2]=v[1] ∧ t[3]=v[2])} ② R S: { t | (u) (v) (R(u) ∧ S(v) ∧ u[1]=v[1] ∧ t[1]=u[1] ∧t[2]=u[2] ∧ t[3]=v[2])

∨ (u) (v) (R(u) ∧ S(v) ∧ u[1]≠v[1] ∧ t[1]=u[1] ∧t[2]=u[2] ∧ t[3]=null) ∨ (v) (u) (S(v) ∧ R(u) ∧ v[1]≠u[1] ∧ t[1]=null ∧t[2]=v[1] ∧ t[3]=v[2])} ③ R S: { t | (u) (v) (R(u) ∧ S(v) ∧ u[1]=v[1] ∧ t[1]=u[1] ∧t[2]=u[2] ∧ t[3]=v[2])

∨ (u) (v) (R(u) ∧ S(v) ∧ u[1]≠v[1] ∧ t[1]=u[1] ∧t[2]=u[2] ∧ t[3]=null) 2.17 设有三个关系：

S（S#，SNAME，AGE，SEX) SC（S#，C#，CNAME） C（C#，CNAME，TEACHER） 试用关系代数表达式表示下列查询语句：

① 检索LIU老师所授课程的课程号和课程名。 ② 检索年龄大于23岁的男学生的学号和姓名。

③ 检索学号为S3学生所学课程的课程名与任课教师名。 ④ 检索至少选修LIU老师所授课程中一门课的女学生姓名。 ⑤ 检索WANG同学不学的课程的课程号。 ⑥ 检索至少选修两门课的学生学号。

⑦ 检索全部学生都选修的课程的课程号与课程名。

⑧ 检索选修课程包含LIU老师所授全部课程的学生学号。 解：⑴ πC#，CNAME（σTNAME='LIU'（C））

⑵ πS#，SNAME（σAGE＞'23' ∧ SEX='M'（SC））

⑶ π⑷ π⑸ π

CNAME，TNAME（σS#='S3'（SC?C））

SNAME（σSEX='F' ∧ TNAME='LIU'（S?SC?C）） C#（C）－πC#（σSNAME='WANG'（S?SC））

1=4 ∧ 2≠5（SC×SC））

⑹ π1（σ⑺ π

C#，CNAME（C?（πS#，C#（SC）÷πS#（S）））

⑻ πS#，C#（SC）÷πC#（σTNAME='LIU'（C））

2.18 试用元组表达式表示第2.17题中各个查询语句。

解：⑴ { t | (u) (C(u) ∧ u[3]='LIU' ∧ t[1]=u[1] ∧ t[2]=u[2])}

⑵ { t | (u) (S(u) ∧ u[3]＞23 ∧ u[4]='M' ∧ t[1]=u[1] ∧ t[2]=u[2])}

⑶ { t | (u) (v) (SC(u) ∧ C(v) ∧ u[1]='S3' ∧ u[2]=v[1] ∧ t[1]=v[2] ∧t[2]=v[3])}

（此处自然联接条件u[2]=v[1]不要遗漏） ⑷ { t | (u) (v) (w) (S(u) ∧ SC(v) ∧ C(w) ∧ w[3]='LIU' ∧ u[4]='F' ∧

u[1]=v[1] ∧ v[2]=w[1] ∧ t[1]=u[2])}

（此处自然联接条件u[1]=v[1]和v[2]=w[1]不要遗漏）

⑸ { t | (u) (v) (w) (C(u) ∧ S(v) ∧ SC(w) ∧ v[2]='WANG' ∧

(w[1]=v[1] => w[2]≠u[1]) ∧ t[1]=u[1])}

其意思是：在关系C中存在一门课程，在关系S中存在一个WANG同学，在关系SC中要求不存在WANG同学学这门课程的元组。也就是要求在关系SC中，WANG同学学的课程都不是这门课程（因此在元组表达式中要求全称量词）。

⑹ { t | (u) (v) (SC(u) ∧ SC(v) ∧ u[1]=v[1] ∧ u[2]≠v[2] ∧ t[1]=u[1])} ⑺ { t | (u) (v) (w) (C(u) ∧ S(v) ∧ SC(w) ∧ w[2]=u[1] ∧ w[1]=v[1] ∧

t[1]=u[1] ∧ t[2]=u[2])}

其意思是：在关系C中找一课程号，对于关系S中每一个学生，都应该学这门课（即在关系SC中存在这个学生选修这门课的元组）。

⑻ { t | (u) (SC(u) ∧ (v) (C(v)

∧(v[3]='LIU' => (w) (SC(w) ∧ w[1]=u[1] ∧ w[2]=v[1])))∧ t[1]=u[1])}

其意思是：在关系SC中找一个学号，对于关系C中LIU老师的每一门课，这个学生都学了（即在关系SC中存在这个学生选修这门课的元组）。

由于在括号中出现“=>”符号（包含有“∨”的语义），因此括号中的量词（w）就不能随意往左边提了。

2.19 试用域表达式表示第2.17题的各个查询语句。

解：① { t1 t2 | (u1 u2 u3) (C(u1 u2 u3) ∧ u3='LIU' ∧ t1=u1 ∧ t2=u2)} 再简化成：{ t1 t2 | C(t1 t2 'LIU')} 此处(u1 u2 u3)是(u1) (u2) (u3) 的简写，下同。

② { t1 t2 | (u1 u2 u3 u4) (S(u1 u2 u3 u4) ∧ u3>'23' ∧ u4='M' ∧ t1=u1∧ t2=u2)} 再简化成：{ t1 t2 | (u3) (S(t1 t2 u3 'M') ∧ u3>'23')}（以下各题的化简略）

③ { t1 t2 | (u1 u2 u3) (v1 v2 v3) (SC(u1 u2 u3) ∧ C(v1 v2 v3) ∧ u1='s3' ∧ u2= v1

∧ t1=v2 ∧ t2=v3)}

④ { t1 | (u1 u2 u3 u4) (v1 v2 v3) (w1 w2 w3) (S(u1 u2 u3 u4) ∧ SC(v1 v2 v3)

∧ C(w1 w2 w3) ∧w3='LIU' ∧ u4='F' ∧ u1=v1 ∧ v2=w1 ∧ t2=u2)}

（⑤~⑧题的域表达式，读者可以很容易写出，此处略）

2.20 设关系R和S的属性集相同，W是R的属性集的子集，试说明下列等式是否成立，并指出它们的正确表示：

① πW(R－S) =πW(R)－πW(S) ② πW(R∩S) =πW(R)∩πW(S) ③ πW(R∪S) =πW(R)∪πW(S)

答：① πW(R－S) =πW(R)－πW(S)是一个错误的式子。

譬如R只有一个元组（1，2，3），S只有一个元组（1，2，4），W为R、S中前两个属性。显然R和S不满足上式。正确的式子应该是πW(R－S) =πW(R)－S。

② πW(R∩S) =πW(R)∩πW(S)是一个错误的式子。

譬如R只有一个元组（1，2，3），S只有一个元组（1，2，4），W为R、S中前两个属性。显然R和S不满足上式。此时不可以把π操作往里移。

③ πW(R∪S) =πW(R)∪πW(S)是一个正确的式子。

2.21 在教学数据库的关系S、SC、C中，用户有一查询语句：检索女同学选修课程的课程名和任课教师名。

① 试写出该查询的关系代数表达式。 ② 画出查询表达式的语法树。

③ 使用启发式优化算法，对语法树进行优化，并画出优化后的语法树。 解：① 关系代数表达式为：

π

CNAME，TEACHER（σSEX=’F’（S?SC?C））

②上述关系代数表达式的语法树如图2.2所示。

π

CNAME，TEACHE

σ

SEX=’F’

?

? C

S SC

图2.2

③ 上述的关系代数表达式为：

πCNAME，TEACHER（σSEX=’F’（πL（σS.S#=SC.S# ∧ SC.C#=C.C#（（S×SC）×C）））） 此处L为S、SC、C中全部属性（公共属性只取一次）。 设L1=πS#（σSEX='F'（S）） L2=πS#,C#（SC）

则优化的关系代数表达式为：

πCNAME，TEACHER（σSC.C#=C.C#（πSC.C#（σS.S#=SC.S#（L1×L2））×C）） 优化后的语法树如图2.3所示。

π

CNAME，TEACHER

σ

SC.C#=C.C#