Skip to content

数据库期末复习

以做题训练分析为主。

  • 经典习题来自 PPT 和教材。
  • Quiz 部分主要来自助教的复习课。

老师及往届学长的建议

授课老师

今年课改，试卷从往年的八道大题改成多选和三道大题。这意味着考点会变得很散，因为往年大题考点相对固定。那么这就关系到你平常学习时对知识整体的理解和把握。

RandomStar
  • 关系代数和 SQL 语句：感觉聚合操作和嵌套语句考的比较多
  • ER 图：画 ER 图，设计数据库 schema，注意各个实体之间的参与关系
  • 范式，闭包，函数依赖的相关计算，感觉必考 BCNF 分解
  • B+ 树的插入和删除，以及 buffer 的计算：buffer 那一块我到现在还没搞懂
  • 查询和 join 的估计：很诡异，有的题不能套公式
  • 并行处理：画前驱图，判断是不是冲突可串行化的，判断二阶段锁协议能不能使用
  • ARIES 恢复算法：照着 ARIES 恢复算法一步步操作就可以

第一部分 关系语言

第二部分 E-R 模型与范式

函数依赖 1

\(R=(A, B, C), F = \{A\rightarrow B, B\rightarrow C\}\)

  • 分解 \(R_1=(A, B), R_2 = (B, C)\) 是无损的，因为 \(R_1\cap R_2 = {B}, B\rightarrow BC\) 在 \(F^+\) 中。
  • 分解 \(R_1=(A, B), R_2 = (A, C)\) 是无损的，因为 \(R_1\cap R_2 = {A}, A\rightarrow AB\) 在 \(F^+\) 中。

无关属性

\(F=\{AB\rightarrow CD, A\rightarrow E, E\rightarrow C\}\)。

其中 \(AB\rightarrow CD\) 中的 \(C\) 是多余的，验证。

正则覆盖

依赖保留

BC 范式 1

  • 关系：\(in\_dep = (\underline{ID}, name, salary, \underline{dept\_name}, building, budget)\)
  • 依赖：\(F = \{dept\_name\rightarrow building, budget\}\)

上面的关系不符合 BC 范式，因为 \(dept\_name\) 不是超键。应当分解为以下两个关系：

  • \(Instructor = (\underline{ID}, name, salary, \underline{dept\_name})\)
  • \(Department = (\underline{dept\_name}, building, budget)\)

分解后的关系符合 BC 范式。

BC 范式 2

  • 关系：\(dept\_advisor = (s\_ID, i\_ID, department\_name)\)
  • 依赖：
    • \(i\_ID\rightarrow department\_name\)
    • \(s\_ID, dept\_name\rightarrow i\_ID\)

上面的关系不符合 BC 范式，因为 \(i\_ID\) 不是超键。

对该关系的任何一种 BC 分解都无法保留依赖，因为它们都不能囊括依赖 \(s\_ID, dept\_name\rightarrow i\_ID\) 涉及的属性。

第三范式 1

  • 关系：\(dept\_advisor = (s\_ID, i\_ID, department\_name)\)
  • 依赖：
    • \(i\_ID\rightarrow department\_name\)
    • \(s\_ID, dept\_name\rightarrow i\_ID\)

上面的关系符合第三范式：

  • \(s\_ID, dept\_name\) 是超键。
  • \(i\_ID\) 不是超键，但 \(dept\_name\) 包含在候选键中。

第三范式 2

多值依赖

第四范式

第五部分 存储管理和索引

第六部分 查询处理与优化

Quiz 5

Q1

How many descriptions below is correct?

  1. We generally rely on the comparison operator to determine whether to use an index in a selection including comparisons.
  2. In N-way merge, if memory is not large enough to allocate a block for each sorted run and reserve a block for output, the merge opeartion needs to be performed in multiple passes. In each pass, the amount of sorted runs reduces and the scale of the sorted runs grows.
  3. Generally, we performing the selection as early as possible to reduce the size of the relation to be joined.

A. 0 B. 1 C. 2 D. 3

分析：1 错误，应该是使用索引。2 正确。3 正确。答案为 C。

Q2

There are 30,000 records on relation r, and 200 records can be accommodated on each block. The size of the select operation \(\sigma_{A=a}(r)\) is approximately ______ when A is a candidate key of r.

A. 1 B. 150 C. 200 D. 30,000

分析：候选键的值是唯一的，所以只有一个。答案为 A。

Q3

Consider the following relational schema:

r(a1, char(18), a2 char(18), a3 integer)
s(a4 char(7), a5 tinyint(1))

Assume that:

  1. Table r has 1,020,000 records
  2. Table s has 3,072,000 records
  3. The file system support 4K-Byte blocks
  4. There are 60 buffer blocks for opearting join
  5. The attribute with integer type takes 4 Bytes
  6. The attribute with tinyint type takes 1 Byte

Please estimate the best cost for evaluating \(r \bowtie s\) with Block Nested-Loop Join method.

第七部分 事务管理