Note08- 查询处理

查询处理是指从数据库中提取数据时涉及的一系列活动。这些活动包括：将用高层数据库语言表示的查询语句翻译为能在文件系统的物理层上使用的表达式，为优化查询而进行各种转换，以及查询的实际执行。

基本概念

先介绍三种树的概念：

SELECT *
FROM R
WHERE C1 AND C2 OR C3

简单选择操作：仅包含关系 R 的一个属性的条件

复杂选择操作：由简单条件经 AND, OR, NOT 等逻辑运算符连接而成的条件

算法：

线性搜索算法
- 顺序地读取被操作关系的每个元组
- 测试该元组是否满足选择条件
- 如果满足，则作为一个结果元组输出
二元搜索算法
- 条件：某属性相等比较且关系按该属性排序
- 即二分查找，时间复杂度为 $O (l o g (N))$
主索引或 Hash 搜索算法
- 条件：主索引属性或 Hash 属性上的相等比较
使用主索引查找满足条件的元组
- 条件：主索引属性上的非相等比较
使用聚集索引查找满足条件的元组
- 条件：具有聚集索引的非键属性上相等比较
B+ 树索引搜索算法
- 条件：B+ 树索引属性上相等或非相等比较
合取选择算法
- 合取条件中存在简单条件 C
- C 涉及的属性上定义有某种存取方法
- 存取方法适应于上述六个算法之一
- 用相应算法搜索关系，选择满足 C 的元组，并检验是否满足其他条件
使用复合索引的合取选择算法
- 如果合取条件定义在一组属性上的相等比较
- 而且存在一个由这组属性构成的复合索引
- 使用这个复合索引完成选择操作

设 $Π_{A_{1}, \dots A_{k}} (R)$ 是 $R$ 上的投影操作，则就看投影属性中有无 $R$ 的码，如果有直接取即可，如果没有则需要去重，采用排序去重

以 $R(X,Y) ⋈ S(Y,Z)$ 为例，令

假设： $B(S) < B(R)$

举例：

算法分析：

算法分析：

假设： $B(S) < B(R)$

举例：

算法分析：

举例：

算法分析：

I/O 代价： $3B(R) + 3 B(S)$
- 对 R 创建归并段时，每块只读一次， $B(R)$
- 将 R 的归并段写入文件， $B(R)$
- 在归并阶段，扫描一次， $B(R)$
可用内存页数要求： $B(R)+B(S) < M^{2}$

算法分析：

I/O 代价： $3B(R) + 3 B(S)$
- 对 R 哈希分桶时，每块只读一次， $B(R)$
- 将 R 的桶写入文件， $B(R)$
- 使用一趟连接算法，扫描一次， $B(R)$
可用内存页数要求： $B(S) \leq (M - 1)^{2}$

假设：关系 S 上建有属性 Y 的索引

算法分析：

算法：首先利用排序算法在相同的键属性上排序两个关系，然后扫描，完成相应操作。