【数据挖掘】国科大苏桂平老师数据库新技术课程作业 —— 第一次作业
1
设关系
r
r
r 和
s
s
s 如下：
r
(
A
B
C
)
a
2
b
3
c
2
a
2
b
1
c
1
a
2
b
2
c
1
a
1
b
1
c
2
s
(
B
C
D
)
b
1
c
1
d
1
b
2
c
1
d
1
b
2
c
2
d
1
\begin{array}{c} r&(A & B & C) \\ &\;\;a_2 & b_3 & c_2\; \\ &\;\;a_2 & b_1 & c_1\; \\ &\;\;a_2 & b_2 & c_1\; \\ &\;\;a_1 & b_1 & c_2\; \\ \end{array} \;\;\;\;\;\;\;\;\;\;\;\;\; \begin{array}{c} s&(B & C & D) \\ &\;\;b_1 & c_1 & d_1\; \\ &\;\;b_2 & c_1 & d_1\; \\ &\;\;b_2 & c_2 & d_1\; \\ \\ \end{array}
r(Aa2a2a2a1Bb3b1b2b1C)c2c1c1c2s(Bb1b2b2Cc1c1c2D)d1d1d1
计算下列表达式的值：
（1） σ A = a 2 ( r ) \sigma_{A=a_2}(r) σA=a2(r)
σ A = a 2 ( r ) = ( A B C ) a 2 b 3 c 2 a 2 b 1 c 1 a 2 b 2 c 1 \sigma_{A=a_2}(r)=\\ \begin{array}{c} (A & B & C) \\ \;\;a_2 & b_3 & c_2\; \\ \;\;a_2 & b_1 & c_1\; \\ \;\;a_2 & b_2 & c_1\; \\ \end{array} σA=a2(r)=(Aa2a2a2Bb3b1b2C)c2c1c1
（2）设 A = { a 1 , a 2 } A=\{a_1, a_2\} A={a1,a2}， B = { b 1 , b 2 , b 3 } B=\{b_1, b_2, b_3\} B={b1,b2,b3}， C = { c 1 , c 2 } C=\{c_1, c_2\} C={c1,c2}， D = { d 1 , d 2 } D = \{d_1,d_2\} D={d1,d2}，求 r r r 和 s s s 的补和有效补
记 r r r 的补与有效补分别为 r ˉ \bar r rˉ 和 r ~ \widetilde r r ， s s s 的补与有效补分别为 s ˉ \bar s sˉ 和 s ~ \widetilde s s ，则
r ˉ = ( A B C ) a 1 b 1 c 1 a 1 b 2 c 1 a 1 b 2 c 2 a 1 b 3 c 1 a 1 b 3 c 2 a 2 b 1 c 2 a 2 b 2 c 2 a 2 b 3 c 1 \bar r =\\ \begin{array}{c} (A & B & C) \\ \;\;a_1 & b_1 & c_1\; \\ \;\;a_1 & b_2 & c_1\; \\ \;\;a_1 & b_2 & c_2\; \\ \;\;a_1 & b_3 & c_1\; \\ \;\;a_1 & b_3 & c_2\; \\ \;\;a_2 & b_1 & c_2\; \\ \;\;a_2 & b_2 & c_2\; \\ \;\;a_2 & b_3 & c_1\; \\ \end{array} rˉ=(Aa1a1a1a1a1a2a2a2Bb1b2b2b3b3b1b2b3C)c1c1c2c1c2c2c2c1
s ˉ = ( B C D ) b 1 c 1 d 2 b 1 c 2 d 1 b 1 c 2 d 2 b 2 c 1 d 2 b 2 c 2 d 2 b 3 c 1 d 1 b 3 c 1 d 2 b 3 c 2 d 1 b 3 c 2 d 2 \bar s =\\ \begin{array}{c} (B & C & D) \\ \;\;b_1 & c_1 & d_2\; \\ \;\;b_1 & c_2 & d_1\; \\ \;\;b_1 & c_2 & d_2\; \\ \;\;b_2 & c_1 & d_2\; \\ \;\;b_2 & c_2 & d_2\; \\ \;\;b_3 & c_1 & d_1\; \\ \;\;b_3 & c_1 & d_2\; \\ \;\;b_3 & c_2 & d_1\; \\ \;\;b_3 & c_2 & d_2\; \\ \end{array} sˉ=(Bb1b1b1b2b2b3b3b3b3Cc1c2c2c1c2c1c1c2c2D)d2d1d2d2d2d1d2d1d2
∵ a d o m ( A , r ) = { a 1 , a 2 } = d o m ( A ) a d o m ( B , r ) = { b 1 , b 2 , b 3 } = d o m ( B ) a d o m ( C , r ) = { c 1 , c 2 } = d o m ( C ) ∴ r ~ = r ˉ = ( A B C ) a 1 b 1 c 1 a 1 b 2 c 1 a 1 b 2 c 2 a 1 b 3 c 1 a 1 b 3 c 2 a 2 b 1 c 2 a 2 b 2 c 2 a 2 b 3 c 1 \because \\ \begin{align} {\rm adom}(A, r) &= \{a_1,a_2\} ={\rm dom}(A)\notag\\\notag {\rm adom}(B, r) &= \{b_1,b_2, b_3\} = {\rm dom}(B) \\\notag {\rm adom}(C, r) &= \{c_1,c_2\} = {\rm dom}(C)\notag \end{align}\\ \therefore \\ \widetilde r = \bar r=\\ \begin{array}{c} (A & B & C) \\ \;\;a_1 & b_1 & c_1\; \\ \;\;a_1 & b_2 & c_1\; \\ \;\;a_1 & b_2 & c_2\; \\ \;\;a_1 & b_3 & c_1\; \\ \;\;a_1 & b_3 & c_2\; \\ \;\;a_2 & b_1 & c_2\; \\ \;\;a_2 & b_2 & c_2\; \\ \;\;a_2 & b_3 & c_1\; \\ \end{array} ∵adom(A,r)adom(B,r)adom(C,r)={a1,a2}=dom(A)={b1,b2,b3}=dom(B)={c1,c2}=dom(C)∴r =rˉ=(Aa1a1a1a1a1a2a2a2Bb1b2b2b3b3b1b2b3C)c1c1c2c1c2c2c2c1
∵ a d o m ( A , s ) = { b 1 , b 2 } a d o m ( B , s ) = { c 1 , c 2 } a d o m ( C , s ) = { d 1 } ∴ s ~ = ( B C D ) b 1 c 2 d 1 \because \\ \begin{align} {\rm adom}(A, s) &= \{b_1,b_2\} \notag\\\notag {\rm adom}(B, s) &= \{c_1,c_2\} \\\notag {\rm adom}(C, s) &= \{d_1\} \end{align}\\ \therefore \\ \widetilde s= \\ \begin{array}{c} (B & C & D) \\ \;\;b_1 & c_2 & d_1\; \\ \end{array} ∵adom(A,s)adom(B,s)adom(C,s)={b1,b2}={c1,c2}={d1}∴s =(Bb1Cc2D)d1
（3）
π
B
(
r
)
\pi_B(r)
πB(r)
π
B
(
r
)
=
(
B
)
b
3
b
1
b
2
\pi_B(r)=\\ \begin{array}{c} (B) \\ \;b_3\\ \;b_1\\ \;b_2 \end{array}
πB(r)=(B)b3b1b2
2
设关系
r
r
r 和
s
s
s 如下：
r
(
A
B
C
)
2
4
6
3
5
7
7
4
6
5
4
7
s
(
B
C
D
)
5
7
3
4
6
2
5
7
9
5
6
3
\begin{array}{c} r&(A & B & C) \\ &\;2 & 4 & 6\; \\ &\;3 & 5 & 7\; \\ &\;7 & 4 & 6\; \\ &\;5 & 4 & 7\; \\ \end{array} \;\;\;\;\;\;\;\;\;\;\;\;\; \begin{array}{c} s&(B & C & D) \\ &\;5 & 7 & 3\; \\ &\;4 & 6 & 2\; \\ &\;5 & 7 & 9\; \\ &\;5 & 6 & 3\; \\ \end{array}
r(A2375B4544C)6767s(B5455C7676D)3293
求
r
r
r 与
s
s
s 的自然连接。
r
⋈
s
=
(
A
B
C
D
)
2
4
6
2
3
5
7
3
3
5
7
9
7
4
6
2
r\bowtie s=\\ \begin{array}{c} (A & B & C & D) \\ \;2 & 4 & 6 & 2\\ \;3 & 5 & 7 & 3\\ \;3 & 5 & 7 & 9\\ \;7 & 4 & 6 & 2\\ \end{array}
r⋈s=(A2337B4554C6776D)2392
3
关系 R R R 和 S S S 如表所示，求 R ÷ S R\div S R÷S
R ( A B C D ) a 1 b 1 c 1 d 1 a 1 b 1 c 2 d 2 a 1 b 1 c 3 d 3 a 2 b 2 c 2 d 2 a 3 b 3 c 1 d 1 a 3 b 3 c 2 d 2 S ( C D ) c 1 d 1 c 2 d 2 \begin{matrix} R&(A & B & C & D) \\ &\;\;a_1 & b_1 & c_1 & d_1\; \\ &\;\;a_1 & b_1 & c_2 & d_2\; \\ &\;\;a_1 & b_1 & c_3 & d_3\; \\ &\;\;a_2 & b_2 & c_2 & d_2\; \\ &\;\;a_3 & b_3 & c_1 & d_1\; \\ &\;\;a_3 & b_3 & c_2 & d_2\; \\ \end{matrix} \;\;\;\;\;\;\;\;\;\;\;\;\; \begin{matrix} S&(C & D) \\ &\;\;c_1 & d_1\; \\ &\;\;c_2 & d_2\; \\ \\\\\\\\ \end{matrix} R(Aa1a1a1a2a3a3Bb1b1b1b2b3b3Cc1c2c3c2c1c2D)d1d2d3d2d1d2S(Cc1c2D)d1d2
R ÷ S R\div S R÷S 可以通俗地理解为，将 S S S 视为一个整体，找到 R R R 中完全包含 S S S 这个整体的元组，提取这些元组的非 S S S 中的属性构成新的关系，故
R ÷ S = ( A B ) a 1 b 1 a 3 b 3 R\div S=\\ \begin{matrix} (A & B) \\ \;\;a_1 & b_1\\ \;\;a_3 & b_3\\ \end{matrix} R÷S=(Aa1a3B)b1b3
Appendix
从网上找到两个比较典型的除法关系运算题目。
1. 已知 Student、Course、SC 三个关系，查询至少选修 1 1 1 号和 3 3 3 号课程的学生号码，写出关系代数运算表达式。
首先，目标属性是“学生号码”，所以经过除法运算后保留的属性应该是“学生号码”。由于查询是要根据“课程号码”，所以可以确定与“课程号码”有关，进而判断出该查询仅涉及 SC 关系。作为被除数的关系应该包括“学生号码”和“课程号码”，作为除数的关系应该只包括“课程号码”，这样除后的关系只剩“学生号码”。显然，作为被除数的关系为
π
S
n
o
,
C
n
o
(
S
C
)
\pi_{\rm Sno,Cno}({\rm SC})
πSno,Cno(SC)。作为除数的关系为属性为“课程号码”，值为
1
1
1 和
3
3
3 的一个临时关系，这个临时关系也可以由 SC 关系轻松构造，
σ
C
n
o
=
1
o
r
C
n
o
=
3
(
π
C
n
o
(
S
C
)
)
\sigma_{\rm Cno=1 \;or\; Cno=3}(\pi_{\rm Cno}({\rm SC}))
σCno=1orCno=3(πCno(SC))。因此，最终运算表达式为
π
S
n
o
,
C
n
o
(
S
C
)
÷
σ
C
n
o
=
1
o
r
C
n
o
=
3
(
π
C
n
o
(
S
C
)
)
\pi_{\rm Sno,Cno}({\rm SC}) \div \sigma_{\rm Cno=1 \;or\; Cno=3}(\pi_{\rm Cno}({\rm SC}))
πSno,Cno(SC)÷σCno=1orCno=3(πCno(SC))
2. 已知 Student、Course、SC 三个关系，查询选修了全部课程的学生号码和姓名，写出关系代数运算表达式。
首先，目标属性是“学生号码”和“学生姓名”，除法运算后需要保留“学生号码”和”学生姓名“，这么看起来仿佛被除数关系应该是 Student 关系，因为只有 Student 关系中同时包含这两个属性，但从查询语句的语义中理解可以发现，被查询的关系应该为 SC 关系，本质上还是从选课关系中查找满足一定条件的学生。虽然 SC 关系中不包括”学生姓名“，但是确定了”学生号码“后，与 π S n o , S n a m e ( S t u d e n t ) \pi_{\rm Sno, Sname}({\rm Student}) πSno,Sname(Student) 做一下自然连接即可。因此，核心任务还是确定选修了全部课程的学生号码。
被除数关系是 SC 关系，除数关系对应的临时关系应该由”课程号码“属性和其全部取值构成，这显然不是通过 SC 关系实现，而是通过 Course 关系实现，即
π
C
n
o
(
C
o
u
r
s
e
)
\pi_{\rm Cno}(\rm Course)
πCno(Course)。因此，最终运算表达式为
(
π
S
n
o
,
C
n
o
(
S
C
)
÷
π
C
n
o
(
C
o
u
r
s
e
)
)
⋈
π
S
n
o
,
S
n
a
m
e
(
S
t
u
d
e
n
t
)
(\pi_{\rm Sno, Cno}({\rm SC})\div \pi_{\rm Cno}({\rm Course})) \bowtie\pi_{\rm Sno, Sname}(\rm Student)
(πSno,Cno(SC)÷πCno(Course))⋈πSno,Sname(Student)