错题集

关系代数与 SQL 查询的等价性判断

For the table student(id, name, age, gender, dept_name), and the following query:

select s1.id, s2.id
from student s1, student s2
where s1.dept_name=s2.dept_name and s1.age<18 and s2.age>28;

What algebra expression is not equivalent to above query?

(A) \(\Pi_{s1.id,\ s2.id}\left(\sigma_{s1.dept\_name=s2.dept\_name \land s1.age<18 \land s2.age>28}\left(\rho_{s1}(\text{student}) \times \rho_{s2}(\text{student})\right)\right)\)

(B) \(\Pi_{s1.id,\ s2.id}\left(\sigma_{s1.age<18 \land s2.age>28}\left(\rho_{s1}(\text{student}) \bowtie \rho_{s2}(\text{student})\right)\right)\)

(C) \(\Pi_{s1.id,\ s2.id}\left(\sigma_{s1.dept\_name=s2.dept\_name}\left(\sigma_{age<18}\left(\rho_{s1}(\text{student})\right) \times \sigma_{age>28}\left(\rho_{s2}(\text{student})\right)\right)\right)\)

(D) \(\Pi_{s1.id,\ s2.id}\left(\sigma_{s1.dept\_name=s2.dept\_name}\left(\sigma_{age<18}\left(\rho_{s1}(\text{student})\right) \times \Pi_{id,\ dept\_name}\left(\sigma_{age>28}\left(\rho_{s2}(\text{student})\right)\right)\right)\right)\)

答案

自然连接的自动对两张表中所有同名属性做等值匹配，但 student 表的所有属性（id, name, age, gender, dept_name）在 s1 和 s2 中都同名，因此这个自然连接会强制要求 s1.id=s2.id、s1.name=s2.name、s1.age=s2.age 所有列都相等，这和原始 SQL 只要求 dept_name 相等完全不同。因此选项 B 的逻辑和原查询不等价。

自引用外键与级联操作计算

The table r (pid, qid) is defined as following:

create table r
(
    pid char(2) primary key,
    qid char(2),
    foreign key (qid) references r
        on delete cascade
        on update cascade
);

An instance of r is as following:

pid	qid
11
22	11
33	22
44	22
55	11

Executing the following SQL statements one by one:

a) insert into r values ('11','55');

b) delete from r where pid='22';

c) update r set pid= '22' where pid='11';

d) select count(*) from r where qid='22';

What is the result of the statement d) above?

(A) 1 (B) 2 (C) 3 (D) 4

答案

执行以下SQL语句后，查询 select count(*) from r where qid='22'; 的结果是 1，对应选项 (A)。

a) insert into r values ('11','55');

试图插入 pid='11'，但 pid 是主键，值 '11' 已存在，违反主键约束，插入失败，数据保持不变。

b) delete from r where pid='22';

删除 pid='22' 的行 (22, 11)。由于外键设置了 on delete cascade，所有 qid 引用 '22' 的行也被级联删除：即 (33, 22) 和 (44, 22)，剩余数据：

pid	qid
11	NULL
55	11

c) update r set pid= '22' where pid='11';

将 pid='11' 的行的 pid 更新为 '22'，该行变为 (22, NULL)。由于外键设置了 on update cascade，引用原 pid='11' 的 qid 也会同步更新：pid='55' 的 qid 从 '11' 变为 '22'，最终数据：

pid	qid
22	NULL
55	22

d) select count(*) from r where qid='22';

检查 qid='22' 的行，只有 (55, 22) 符合条件。结果为 1。

B+ 树索引遍历

Assuming the height of the B+-tree index on the table student(ID) is 4. Considering the query: select * from student where ID='2020160008', the estimated cost for evaluating above query using the Index Scan algorithm is:

(A) 4 block transfers + 4 seeks.

(B) 5 block transfers + 5 seeks.

(C) 3 block transfers + 3 seeks.

(D) 5 block transfers + 4 seeks.

答案

B

解析

树高 4，遍历索引需 4 次块传输 + 4 次寻道，回表读取数据块再加 1 次传输 + 1 次寻道，总计 5 次块传输 + 5 次寻道。

Hash Join 无递归分区的条件

Assuming the table r and s has 256 and 1024 blocks respectively. Each block has 4K bytes. To do natural join r and s with the Hash Join algorithm, what is the approximate minimum memory needed to avoid recursive partitioning?

(A) 64K bytes

(B) 128K bytes

(C) 1M bytes

(D) 2M bytes

答案

A

解析

小表共 256 块，避免递归分区的近似条件为内存块数 \(M\approx\sqrt{256}=16\) 块。每块 4K 字节，总内存约 \(16 \times 4\mathrm{K}=64\mathrm{K}\) 字节。