数据库系统考试复习

发表于 Waline： 阅读次数：

这个课老师纯念 PPT，要命的是 PPT 做得很烂，懂得都懂

这次我做的笔记仅供回忆知识点用，先学会比较好

建议看一遍 Database System Concepts 来真正学习数据库原理

考试回忆

考试回忆里可能着重列一些我场上觉得不是很确定的题，难度参考下就得了

  1. 填空（15）：十五个空，考了如何由前趋图判断无法冲突串行等价（有环）
  2. 选择（15）：十五题，有锁相容矩阵、事务 UNDO REDO
  3. 简答（9）：三个题，非常坑，得理解一下再知道要列什么，老师说只需要列出概念不用详细解释；考了六级模型五级映像、查询优化分类、约束实现（CHECK 字句，断言，存储过程，触发器）
  4. 大题：计算关系代数、关系演算转换关系代数、查询优化
  5. 大题：SQL 查询
  6. 大题：判断范式，最小表示、求候选键、3NF 分解
  7. 大题（15）：画 ER 图

纯背诵合集

定义

数据库（DB）：是长期储存在计算机内、有组织的、可共享的大量数据的集合

数据库管理系统（DBMS）：为建立、使用和维护数据库而配置的通用软件系统，是整个数据库系统的核心

数据库系统（DBS）：实现有组织、动态地存储大量相关的结构化数据、方便各类用户访问的计算机软/硬件资源的集合；由数据库和数据库管理系统构成

数据库系统的软件成分：DBMS、高级语言和编译系统、应用开发工具、应用程序（DBAP）

数据库系统的用户：数据库管理员（DBA）、应用程序员、终端用户（End User）

数据：数据是信息的符号表示或称为载体，信息则是数据的内涵，是对数据语义的解释；数据有语法（Syntax，指格式规定）、语义（Semantic，指含义）两个方面

数据库语言：数据定义语言（DDL）、数据操纵语言（DML）、数据控制语言（DCL）、数据查询语言（QL）；嵌入型，自含型，双重型

数据库例程，多线程 DBMS：编译器、查询优化和实现、存储与索引、通信控制、事务处理、控制程序（安全性控制、完整性控制）、装载、重组、故障恢复、字典管理、性能分析

数据管理的发展

其中独立性指应用程序和数据之间的独立性

性质 人工管理阶段 文件系统阶段 数据库系统阶段
背景 Fortran+Batch OS+Realtime DBMS+Distributed
数据量 小 大 很大
持久性 无法保存 可持久 可持久
管理者 应用程序 文件系统 DBMS
共享度 无 差 好
独立性 无 差 好
结构化 无 记录内有整体无 有
数据控制 应用程序 大部分由应用程序 DBMS控制安全完整并发恢复
用户接口 无 物理存取 抽象接口

数据模型与模式

数据模型是规定现实世界数据特征的抽象，是用来描述数据的语法、语义和操作的一组概念的集合。描述内容包括数据库的静态特征、动态特征和完整性约束条件。由以下三部分组成

  1. 数据结构：指对象的类型集合
  2. 数据操作：对各种对象的实例允许执行的操作集合
  3. 完整性约束：一组完整性规则的集合（静态列级/元组/关系约束、动态列级/元组/关系约束，静态关系约束包含实体/参照/函数依赖/统计约束）

三级模型

  1. 概念数据模型：面向用户和现实世界的数据模型，如 ER 图
  2. 逻辑数据模型：数据库角度看到的数据模型，分为层次（只有 \(1:N\)）、网状（需导航式操作）、关系型、面向对象模型
  3. 物理数据模型：反映物理存储结构的模型，利用块、索引、聚簇等术语描述

数据模式（Schema）是数据库中全体数据的结构和特征的描述，它仅仅涉及类型的描述，不涉及具体的值

三级模式两级映像，两级映像分别保证逻辑独立性和物理独立性

  1. 外模式：用逻辑数据模型对用户局部数据的描述
  2. 模式：用逻辑数据模型对一数据库全体数据的描述
  3. 内模式：用物理数据模型对数据的描述

数据库设计

数据库生命周期：系统规划、数据库设计、系统实现、运行和维护

设计方法：面向数据的设计方法、面向过程的设计方法

扩充的 ER 模型：弱实体、普遍化/特殊化（子类、超类；disjoint/overlap）、范畴（合并；U）、聚集（is part of）

联系集：多于一个实体的数学关系（\(M:N:P\) 联系）

数据库设计六阶段：

  • 需求分析：信息要求、处理要求、安全与完整性要求；系统范围图、业务流程图、数据流图、数据字典
  • 概念结构设计（ER）：自顶向下、自底向上、由内而外（是自底向上）、混合策略；
    • 集中式设计：所有一起设计
    • 视图集成（合并 ER 图）（二元梯形即成、n 元集成、二元平衡集成）：解决冲突（命名冲突、属性冲突、类型冲突、约束冲突），消除冗余，
  • 逻辑结构设计（IDEF1x）：转换数据库模式、优化与调整、用户子模式设计
    • 联系基数（\(1:N\)）多端用圆点表示
    • 子实体上的外键标“（FK）”
    • 确定性关系实线，FK 是主键
    • 非确定性关系虚线，FK 不是主键：强制性关系（子实体存在依赖父实体）、非强制性关系（父实体菱形）
    • 参照完整性（删父实体怎么办）：限制、级连、设空、无规则
  • 物理结构设计：确定存储结构、存放位置、存放方法、系统配置、评价物理结构
  • 数据库实施：用 DDL 定义数据库结构、组织数据入库、编制与调试应用程序、数据库试运行
  • 数据库运行与维护：数据库转储与恢复、数据库性能监督分析改进、数据库重组、数据库重构

事务管理

事务（Transaction）是数据库环境下由一组数据库操作序列组成的逻辑工作单元

完成后 Commit 或 Rollback

事务特性 ACID：原子性、一致性（前后的数据库均是一致的）、隔离性、持续性（Durability 提交完了就持续了）

事务状态自动机：活动状态、局部提交状态、失败状态、终止状态、提交状态

故障分类：事务故障（逻辑错误和系统错误）、系统故障、介质故障

故障恢复（冗余）：

  • 数据备份（转储）：静态（脱机）备份和动态（实时）备份；全备份，部分备份和增量备份
  • 日志文件，先写日志后写数据库；建立检查点时刻正在执行的事物清单

并发的问题：丢失修改、读（已被 REDO 的）脏数据、不可重读（被写了）

并发正确性原则：调度为一个次序的安排；两个调度目标等价就是最后结果一定一样；冲突（读写冲突、写写冲突）；两个调度冲突等价即交换不冲突的顺序能使其相等；并发正确即和串行目标等价

前趋图：有冲突操作的事务，先向后建边

锁：排他锁 X（写锁）、共享锁 S（读锁）、更新锁 U（写入前可被别的事物读）

  1. 一级加锁协议（防丢失修改）：事务 T 在修改数据 T 之前必须先对其加 X 锁，直到事务结束才释放
  2. 二级加锁协议（+防脏数据）：+事务 T 在读取数据 A 之前必须先对其加 S 锁，读完后即可释放 S 锁
  3. 三级加锁协议（+防不可重复读）：+事务 T 在读取数据 A 之前必须先对其加 S 锁，直到事务结束才释放

SQL 中的一致性级别：Serializable, Repeatable Read, Read Committed, Read Uncommited

两段锁（保证可串行化，不一定保证无死锁）：第一阶段只能加锁，第二阶段只能放锁

防死锁：一次封锁；顺序封锁；事务重执：

  • wait-die：若后要锁的是老事务则老事务等待，否则先要锁的老事务回滚再执行
  • wound-wait：若后要锁的是新事务则新事务等待，否则先要锁的年轻事物回滚再执行

死锁检测：超时、等待图

活锁：可以随着一个事务的锁关掉自行解开；先来先服务避免活锁

多粒度锁：按资源的层次锁；意向锁（IS 要读所有元组, IX 要写元组, SIX 先读再写）：加锁时必须向高层次加的锁

多粒度锁强度偏序 \(-\prec IS \prec (S, IX)\prec SIX \prec X\)

多粒度锁相容矩阵

T1 S X IS IX SIX -
S Y Y Y
X Y
IS Y Y Y Y Y
IX Y Y Y
SIX Y Y
- Y Y Y Y Y Y

幻影现象：只对元组加锁的话，插入删除就会导致非串行化；可对数据字典加锁/对索引加锁

分布式与并行数据库

数据复制、数据分片

六级模式五级映像：

  1. 全局外模式
  2. 全局概念模式（逻辑数据独立性）
  3. 分片模式（分片透明性）
  4. 分配模式（位置透明性）
  5. 局部概念模式（局部数据模型透明性）
  6. 局部内模式（物理数据独立性）

DDBMS 的部分：全局数据库管理系统（GDBMS），全局数据字典（GDD），局部数据库管理系统（LDBM），通信管理（CM）

两种分类：物理分布逻辑集中/物理分布逻辑分布（联邦分布式数据库）

联邦分布式数据库：数据库转换、模式转换；多数据库系统 MDBS

分布式查询处理：

  1. 查询分解（和 DBMS 一样）
  2. 数据本地化：使用查询树，上推并，下推选择投影
  3. 全局优化
  4. 局部优化

分布式事务管理：全局事务、局部事务

  • 两阶段提交协议：投票阶段，决定阶段
  • 三阶段提交协议

分布式并发控制：单一锁管理器、多协调器、多数协议、有偏协议、主副本

死锁处理：局部等待图、全局等待图

并行数据库系统：事务间并行、查询间并行、操作间并行、操作内并行；水平并行、垂直并行（流水）

关系模型

定义

域（domain）是相同类型值组成的集合；

定义在 \(D_1,D_2,\cdots,D_n\) 上的关系是 \(D_1\times D_2\times\cdots \times D_n\) 的任意子集；

关系的属性 \(A,B,C,\cdots\) 是为每个列起的名称；

关系上的超键（SK）是能唯一确定元组的属性集；

关系上的候选键（CK）是能唯一确定元组的极小属性集；

主键（PK）一般从候选键中选择一个；

一个关系上的外键（FK）是另一个关系的候选键；

主属性是在任意候选键中出现过的属性。

关系模式 \(R(U,D,DOM,I,F)\) 是对关系的型的描述，其中

  • \(U=\{A_1,A_2,\cdots,A_n\}\) 是属性的有序集合
  • \(D=\{D_1,D_2,\cdots,D_n\}\) 域集合
  • \(DOM=\{A_1\to D_1,A_2\to D_2,\cdots,A_n\to D_n\}\) 是属性到值域的映射的集合
  • \(I\) 是完整性约束规则集，约束分为域完整性约束、实体完整性约束（键不重复）、参照完整性约束（外键约束）、用户自定义完整性约束
  • \(F\) 是函数依赖集合

关系模式的简记：仅列出 \(U\)，写作 \(R(A_1,A_2,\cdots,A_n)\)

关系代数

并 \(R\cup S\)、差 \(R-S\)、交 \(R\cap S\)、笛卡尔积 \(R\times S\)

选择 \(\sigma_F(R)\)、投影 \(\Pi_x(R)\)、\(\theta\) 连接 \(R\Join_{A\theta B}S\)、自然连接 \(R\Join S\)

外连接 \(R*\Join *S\)、左外连接 \(R*\Join S\)、右外连接 \(R\Join *S\)

半连接 \(R\ltimes S=\Pi_R(R\Join S)\)

设 \(R(X,Y)\)，\(S(Y)\) 除 \(R\div S=\Pi_X(R)-\Pi_X((\Pi_X(R)\times S)-R)\)，表示 \(R\) 中“包含” \(S\) 中“所有”元组的元组

最小完备集

  • \(\{\cup, -, \times, \sigma, \Pi\}\)
  • \(\{\cup, -, \Join, \sigma, \Pi\}\)

等价变换规则

  • 选择串接律：\(\sigma_{C_1}(\sigma_{C_2}(R))=\sigma_{C_1\wedge C_2}(R)\)
  • 选择交换律：\(\sigma_{C_1}(\sigma_{C_2}(R))=\sigma_{C_2}(\sigma_{C_1}(R))\)
  • 投影串接律（\(L_n\subseteq L_2\subseteq \cdots\subseteq L_1\)）：\(\Pi_{L_1}(\Pi_{L_2}(\cdots(\Pi_{L_n}(R))))=\Pi_{L_1}(R)\)
  • 选择投影交换律：\(\Pi_{L}(\sigma_C(R))=\sigma_{C}(\Pi_L(R))\)
  • 连接和笛卡尔积的交换律（仅优化时使用，数学上不甚正确）
  • 选择对连接/笛卡尔积的分配律（\(U_{C_1}\cap U_{S}=U_{C_2}\cap U_{R}=\emptyset\)）：\(\sigma_{C_1\wedge C_2}(R\Join S)=\sigma_{C_1}(R)\Join\sigma_{C_2}(S)\)
  • 投影对连接/笛卡尔积的分配律（和上条相似）
  • 选择对交并差的分配律：\(\sigma_{C}(R\cap S)=\sigma_C{R}\cap \sigma_C(S)\)
  • 投影对并的分配律：\(\Pi_{L}(R\cup S)=\Pi_L{R}\cup \Pi_L(S)\)
  • 连接、笛卡尔积、交、并各自的结合律

关系演算

元组关系演算

\(\{t\,|\,P(t)\}\)

\(P\) 为元组关系演算表达式，简化的 BNF 如下 \[ \begin{aligned} P(s,t,u,\cdots) & \to & P \vee P \\ & | & P \wedge P \\ & | & \neg P \\ & | & \exists s(P) & & \text{There exists a tuple }s\text{ that satisfies }P\\ & | & \forall s(P) & & \text{All tuples of }s\text{ satisfy }P\\ & | & (P) \\ & | & R(t) & & t\text{ is a tuple of relation} R\\ & | & s[i]\, \theta\, t[i] & & \text{The }i\text{ th attribute of }s\text{ has a }\theta\text{ relationship with the other}\\ & | & c\, \theta\, t[i] \\ & | & t[i]\, \theta\, c \\ \end{aligned} \] 蕴含运算 \(p\to q\) 可以表示为 \(\neg p\vee q\)

关系演算的安全表达式是不产生无穷验证和无限关系的表达式，其满足

  1. 若 \(P(t)\) 为真，\(t\) 的每个分量在 \(Dom(P)\) 中
  2. \(P\) 中对每个存在表达式 \(\exists u(Q)\)，若 \(u\) 使 \(Q\) 为真，\(u\) 的每个分量在 \(Dom(P)\)​ 中
  3. \(P\) 中对每个全称表达式 \(\forall u(Q)\)，若 \(u\) 使 \(Q\) 为假，\(u\) 的每个分量在 \(Dom(P)\) 中

其中 \(Dom(P)\) 是 \(P\) 中出现的所有常量和所有关系中的属性值集合

域关系演算

\(\{xyz\cdots\,|\,P(x,y,z,\cdots)\}\)

即把元组写开，剩余略

函数依赖

设 \(R\) 为关系模式，\(r\) 是 \(R\) 上的任意一个关系实例，\(X, Y\subseteq U\) 是两个属性子集，若 \(\forall t_1,t_2\in r \wedge t_1[X]=t_2[X]\) 有 \(t_1[Y]=t_2[Y]\)，则称 \(Y\) 函数依赖于 \(X\)，记为 \(X\to Y\)；若 \(Y\nsubseteq X\) 则称为非平凡函数依赖；一一对应 \(X\leftrightarrow Y\)

设 \(X\to Y\)，且不存在 \(X'\subset Y\) 使 \(X'\to Y\)，则有完全函数依赖 \(X\stackrel{f}{\to} Y\)；否则有部分函数依赖 \(X\stackrel{P}{\to} Y\)

若 \(X\to Y\)，\(Y\to Z\) 且 \(X\not\to Z\)，则 \(Z\) 传递函数依赖于 \(X\)

Armstrong 公理

  • 自反：若 \(Y\subseteq X\subseteq U\) 则 \(X\to Y\)
  • 增广：若 \(X\to Y\) 成立，且 \(Z\subseteq U\) 则 \(XZ\to YZ\) 成立
  • 传递：若 \(X\to Y\)，\(Y\to Z\) 成立，则 \(X\to Z\) 成立

推论

  • 合并规则：\(X\to Y\) 且 \(X\to Z\)，则 \(X\to YZ\)
  • 伪传递规则：\(X\to Y\) 且 \(WY\to Z\)，则 \(WX\to Z\)
  • 分解规则：\(X\to Y\) 且 \(Z\subseteq Y\) 则 \(X\to Z\)

设 \(F\) 是函数依赖集合，若 \(F\) 成立时有 \(X\to Y\) 成立，则称 \(F\) 逻辑蕴含 \(X\to Y\)，记为 \(F\models X\to Y\)

闭包 \(F^+=\{X\to Y\,|\, F\models X\to Y\}\)

若 F 满足如下三条属性，则称为最小函数依赖集

  1. \(F\) 右部均为单属性
  2. \(F\) 中不存在 \(X\to A\) 及 \(Z\subset X\) 使得 \(F^+=((F-\{X\to A\})\cup\{Z\to A\})^+\)，（就是去掉部分依赖）
  3. \(F\) 中不存在 \(X\to A\) 使得 \(F^+=(F-\{X\to A\})^+\)

属性集 \(X\) 关于 \(R(U,F)\) 上的函数依赖 \(F\) 的闭包 \(X_F^+=\{A\,|\, A\in U \wedge X\to A \in F^+\}\)；计算该闭包仅需重复应用函数依赖直至不变

三步构造最小函数依赖集：展开为单属性；缩小部分依赖；检查右部是否存在于剩余依赖的闭包，是则去除

由 \(R(U,F)\) 求全部的候选键（\(F\) 必须是最小覆盖）：

  1. 分四类：\(C_1\) 不在任何依赖中出现的属性；\(C_2\) 仅在左侧出现；\(C_3\) 仅在右侧出现；\(C_4\) 左右均出现。
  2. 若 \((C_1\cup C_2)^+=U\) 或 \(C_4=\emptyset\)，则 \(C_1\cup C_2\) 为唯一候选键；否则逐一将 \(C_4\) 的属性 \(A_i\) 加入计算闭包，若是 全集，则 \(C_1\cup C_2\cup \{A_i\}\) 是候选键

多值依赖

设关系 \(R(U)\)，\(X,Y,Z\subset U\)，\(Z=U-X-Y\)，若对 \(R\) 的任意实例 \(r\) 有：若 \(r\) 中存在两个元组 \(s\)，\(t\) 使得 \(s[X]=t[X]\)，则 \(r\) 中必然存在两个元组 \(u\)，\(v\) 使得，交换 \(s\)，\(t\) 在 \(Y\) 属性上的新元组仍在 \(r\) 中出现，则 \(Y\) 多值依赖于 \(X\)，记为 \(X\to\to Y\)

多值依赖的 Armstrong 公理

  • 互补：若 \(X\to\to Y\) 则 \(X\to\to(U-X-Y)\)
  • 多值增广：若 \(X\to\to Y\) 且 \(V\subseteq W\)，则 \(WX\to\to VY\)
  • 多值传递：若 \(X\to\to Y\) 且 \(Y\to\to Z\)，则 \(X\to\to(Z-Y)\)
  • 若 \(X\to Y\) 则 \(X\to\to Y\)
  • 若 \(X\to\to Y\)，\(Z\subseteq Y\)，且对某一 \(W\)，当 \(Y\cap W=\emptyset\) 时如有 \(W\to Z\)，则 \(X\to Z\)

分解

\(R(U,F)\) 的分解是一个关系模式的集合 \(\rho=\{R_1(U_1,F_1),R_2(U_2,F_2),\cdots,R_k(U_k,F_k)\}\)，其中属性集合的并为全集，各函数依赖为在对应属性集上的投影

关系集的投影连接算子

无损连接分解

假设 \(\rho=\{R_1,R_2,\cdots,R_k\}\) 是 \(R\) 的一个分解，\(r\) 是 \(R\) 的一个关系，设投影连接算子 \(m_\rho(r)=r_1\Join r_2\Join\cdots\Join r_k\)，有

  • 属性数量单调，\(r\subseteq m_\rho(r)\)
  • 可逆，设 \(s=m_\rho(r)\)，有 \(\Pi_{U_i}(s)=r_i\)
  • 幂等，\(m_\rho(m_\rho(r))=m_\rho(r)\)

无损连接分解指 \(r=m_\rho(r)\)

无损连接分解判定

  1. 构造一个 \(m\times n\) 的符号表，每行对应一个子关系模式，每列对应一个属性，\(A_j\in R_i\) 时， \(T[i,j]=a_j\)，否则 \(T[i,j]=b_{ij}\)
  2. 根据函数依赖进行变换，如果存在不满足依赖的行，则修改属性值为相同的 \(a\)，没 \(a\) 则改为 \(i,j\) 最小的 \(b_{ij}\)
  3. 若进行了变换回到 2
  4. 若存在全 \(a\) 行则是无损连接，否则不是

两个子模式 \(\rho=\{R_1,R_2\}\) 分解的快速判断：\((U_1\cap U_2)\to(U_1-U_2)\in F^+\) 或 \((U_1\cap U_2)\to(U_2-U_1)\in F^+\)

保持函数依赖分解

若 \(F^+=\left(\cup_{i=1}^k F_i\right)^+\) 则保持函数依赖

范式和规范分解

范式：

  • 若 \(R\) 每个属性是原子属性，且元组在属性的取值也是不可再分的，则满足 1NF
  • 若 \(R\in \text{1NF}\) 且所有非主属性都完全函数依赖于 CK 的所有属性，则满足 2NF
  • 若 \(R\in \text{2NF}\) 且所有非主属性不传递函数依赖于 CK 的任何属性，则满足 3NF
  • 若 \(R\in \text{3NF}\) 上的任何非平凡函数依赖都有决定子包含某个候选键，则满足 BCNF
  • 若 \(R\in\text{BCNF}\) 且其所有非平凡多值依赖都有决定子包含某个候选键，则满足 4NF

无损连接且保持函数依赖的 3NF 分解：

  1. 将 \(F\) 转换为最小覆盖
  2. 不在 \(F\) 中的属性构成 \(R_0(U_0)\)，剩余属性记为 \(U\)
  3. \(F\) 按照决定子相同原则分组，每组的所有属性构成一个关系 \(R_i(U_i)\)
  4. 加入由候选键构成的关系模式 \(R_{CK}\)

保证无损连接的 BCNF 分解

  1. 令 \(\rho=\{R(U,F)\}\)
  2. 若每个子关系是 BCNF，则终止，否则存在函数依赖 \((X\to A)\in F_i^+\) 不包含候选键，则分为 \(R_{i1}(XA,F_{i1})\)，\(R_{i2}(U_i-A,F_{i2})\)

SQL

请前往 W3C School 等地学习

数据库物理存储

文件

文件结构：

  • 定长记录文件：所有记录一样长，可以使用顺序移动法、末尾移动法、空闲列表法维护
  • 变长记录文件：字节流表示法、保留空间法、锚块/溢出块表示法（做链表）

文件组织指的是数据组织成记录、块和访问结构的方式，包括把记录和块存储在磁盘上的方式，以及记录和块之间相互联系的方法（应该是记录组织为逻辑结构的方式）；存取方法指的是对文件所采取的存取操作方法

文件组织：

  • 无序文件：插入尾，删除直接删/标志，定期整理；查需扫描
  • 顺序文件：维护有序；插入可使用溢出块形成链表，定期整理
  • 索引文件：使用索引维护文件
  • 散列文件：维护键到桶所在磁盘块地址的映射，可以用溢出桶；非相等比较的查找必须扫；动态散列即拿哈希值的高 \(k\) 位先分桶，不够了加大 \(k\) 值，用 Trie 树维护

索引

稠密索引：每个值都有索引；稀疏索引：部分值有索引

主索引：主键是排序域，是每个块的第一个主键值到这个块的映射

聚簇索引：用一个顺序文件中不是键的排序域建的索引，指向这个值第一次出现的块；这个索引文件是一个排序文件；原文件一个块可能被引用多次；只能有一个聚簇索引因为和物理相关

辅助索引：非排序域上的索引；索引指向存储一系列记录指针的磁盘块（类似二级索引）

B 树索引：秩为 \(n\)，每个结点至少 \(\lceil n/2 \rceil\) 个树指针，至多 \(n\) 个，内节点存储键和数据指针，有 \(q\) 个树指针的节点有 \(q-1\) 个键

B+ 树索引：数据指针仅存在最后一层叶节点并且是同一层，叶节点维护下一个叶节点的指针；一般除非只有一个叶，根可以拥有少于 \(\lceil n/2\rceil\) 个树指针，来形成至少两层；下溢时先看兄弟能否补足不然合并

查询处理和优化

过程：（查询）词法分析语法分析（语法树）优化（查询计划）系统执行（结果）

预编译：可执行访问模块（AM）

类型：

  • 规则优化
  • 代数优化：把选择展开，选择投影下推叶节点，合并选择投影和一个连接/笛卡尔积组成操作；找公共表达式，投影可与下方二元一起，适当预处理
  • 物理优化（依赖于存取路径的优化），估计选中占比（较大不用无序索引）
  • 代价估算优化：多做几个选最优
  • 语义优化

代价估算的单位 \(C_{I/O}=D_0+xD_1\)

代价估计模型：

  • 连接 \(R\Join S\) 中 \(js=|R\Join_C S|/|R\times S|\)，\(0\le js\le1\)，估算 \(js\sim 1/M\)；其中 \(n_R\)，\(n_S\) 为元组数，块因子 \(p_R\)，\(p_S\) 为一块的元组数，块数 \(b_R=\lceil n_R/p_R\rceil\)，假设外循环为 \(R\)，内存块数 \(n\ll b_r\sim b_s\)
  • 选择 \(\sigma_{P(A)}(R)\) 中 \(N_A\) 属性 \(A\) 在关系中不同值数，\(M_A\) 属性的值域大小，\(L_i\) 索引 \(i\) 的级数，\(s\sim N_a/M_A\) 为满足条件的元组数量

连接操作的代价：

  • 嵌套循环，则 \(R\) 的块放进去剩一块给 \(S\)，访问块数 \(b_R+\lceil b_R/(n-1)\rceil\times b_S\)，代价 \(C_{NLJ} = b_R+\lceil b_R/(n-1)\rceil\cdot b_S+(js\cdot n_R\cdot r_S)/p_{RS}\)
  • 索引嵌套循环，访问块数 \(b_R+n_R\cdot c\)，其中 \(c\) 是索引代价
    • 无序索引 \(C_{NSJ}=b_R+n_R\cdot (L_B+n_S/N_B)\)
    • 聚簇索引 \(C_{SJ}=b_R+n_R\cdot (L_B+n_S/N_B/p_S)\)
    • 散列索引 \(C_{SHJ}=b_R+n_R\cdot h\)，其中 \(h\sim 1\) 为散列一次访问的块数
  • 排序归并连接算法，访问块数 \(b_R+b_S\)
  • 散列连接算法，各自哈希进同一组桶，各桶里连接，访问块数 \(b_R+b_S\)，代价 \(C_{HJ} = b_R+b_S+js\cdot(n_R\cdot N_B+n_S\cdot N_A)\)

选择操作的代价：

  • 顺序扫描：\(C_{sa}=b_r\) 或 \(C_{sa}=1/2b_R\)
  • 利用索引 \(C_{lk}=L+1\)，散列索引 \(C_{hk}=1\)
  • 利用无序索引 \(C_{INK}=L+s\)
  • 聚簇索引等值 \(C_{CI}=L+\lceil s/p\rceil\)，范围 \(C_{CIR}=L+\lceil b/2\rceil\)