错题集

关系代数与 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 次寻道。

Suppose there is a relation r with 20000 records on which a clustering B+-tree index is constructed on a non-candidate key. Each B+-tree node has a maximum size of 2048 bytes. Each search key occupies 32 bytes, and each pointer occupies 8 bytes. A selection operation is performed by scanning the B+-tree index, where the selection condition specifies an equality comparison on the search key. 5 blocks contain records that match the specified search key. In the worst case, how many seeks and block transfers are required for the selection operation?

(A) 4 seeks and 8 block transfers

(B) 4 seeks and 9 block transfers

(C) 5 seeks and 8 block transfers

(D) 5 seeks and 9 block transfers

答案

D

解析
  1. 计算B+树节点扇出
  2. 节点最大容量：2048字节
  3. 内部节点：设包含 \(n\) 个搜索键，则有 \(n+1\) 个指针
    \(32n + 8(n+1) \le 2048 \Rightarrow 40n \le 2040 \Rightarrow n \le 51\)
    扇出 = 52

  4. 叶子节点：设包含 \(n\) 个搜索键和 \(n\) 个记录指针，外加1个链表指针
    \(32n + 8n + 8 \le 2048 \Rightarrow 40n \le 2040 \Rightarrow n \le 51\)

  5. 确定B+树高度

  6. 记录总数：20000，每个叶子节点最多51条索引项
    叶子节点数 = \(\lceil 20000 / 51 \rceil = 393\)
  7. 第二层内部节点数 = \(\lceil 393 / 52 \rceil = 8\)
  8. 根节点（第三层）：1

  9. 树高 = 3（从根到叶子需经过根、内部节点、叶子节点）

  10. 最坏情况I/O分析

  11. 遍历索引：根、内部节点、第一个叶子节点均不在内存，且物理上不连续，需 3次寻道 + 3次块传输
  12. 叶子节点扫描：非候选键等值匹配可能跨叶子节点边界，最坏需额外读取下一个叶子节点，物理不连续，需 1次寻道 + 1次块传输

  13. 数据块读取：5个匹配数据块在聚簇索引中连续存储，需 1次寻道 + 5次块传输

  14. 合计

  15. 寻道 = 3 + 1 + 1 = 5次
  16. 块传输 = 3 + 1 + 5 = 9次

因此最坏情况下需要 5次寻道和9次块传输，对应选项 (D)。

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}\) 字节。

索引

When creating a secondary index, if we want to reduce space overhead, we can use a sparse index with one index entry per data block.

答案

F

解析

稀疏索引要求数据必须按索引键物理有序，二级索引建立在非排序字段上，数据块内键值混杂，无法用单个条目代表整个块，因此必须使用稠密索引。

Schedules, which are impossible under two-phase locking, can be possible under the tree protocol.

答案

T

解析

两阶段锁定（2PL）要求事务释放任何锁后不能再获取新锁，而树协议允许按“从根到叶”的方向锁定，并可以提前释放父节点锁后再锁定子节点。这种“先放后锁”的操作在2PL下是禁止的，但在树协议下是合法且能保证可串行化的调度。因此，某些2PL无法实现的调度，在树协议下可以做到。