[CMU15445]:两阶段锁

Two-Phase Locking Protocol当一个调度遵循两阶段锁协议的时候，它就一定是冲突可串行化的，该协议将一个事务分成了两个阶段 增长阶段(growing phase) 该阶段中一个事务可以获得锁，但不能释放任何锁 缩减阶段(shrinking phase) 该阶段中一个事务可以释放锁，但是不能获得任何新锁 一个事务一开始时是处于增长阶段，一旦事务释放了锁，它就进入了缩减阶段

数据库

[CMU15445]:并发控制理论

ACID: AtomicDBMS会保证事务的执行时原子的，即事务要么全部执行，要么全部不执行 有两种方法可以保证原子性： Shadow Paging 当DBMS需要修改page的时候，就会拷贝一份这些需要被改动的page的副本，然后在这些副本上应用事务进行修改，当事务提交之后，这些修改后的副本就会代替原来的page，该方法的成本很高，因此没有人使用 Logging DBMS可以对所有的操作进行

数据库

[CMU15445]:查询优化1

Overview查询优化是数据库中最难的部分，由于SQL是声明式语言，用户只需要给出SQL语句，DBMS负责给出最优的查询方案 这里有两种查询优化的策略: 启发式方法(heuristic)/静态规则、基于代价的优化 启发式方法 在教科书上给出了两个启发式方法的例子 尽早执行选择 尽早执行投影 当然还有更多的启发式方法，当使用该策略时，不需要取检查真正的数据，通常只需要获取一些元数据即可

数据库

[CMU15445]:中级SQL

连接表达式当在SQL查询语句中使用from子句包含多个表的时候，默认会使用笛卡尔乘积对多个表中的元组进行连接 对于这样一个查询来说 12select A1, A2, ...from r1, r2, ... 迭代过程类似于下图 如果后面还使用了where子句的话，就会在此表的基础上进行过滤 一个典型的笛卡尔积关系如图 自然连接自然连接的关键字是natural join，当两个表有着相同的属性名

数据库

[CMU15445]:查询处理1

Query Plan查询计划指的是一系列查询操作的序列，通常使用一棵树来表示 查询过程中的输入从叶子节点开始，沿着路径向上，在进入每层时会进行各种运算，最终在根节点产生输出结果 下面顺便介绍一些查询树中会出现的一些算子的含义 连接运算 该运算之前有所介绍，代表着连接运算，右下角的下标给出了连接的表以及属性 投影(Projection)运算 该运算用来过滤输出结果，右下角的下标表明了最终产

数据库

[CMU15445]:Join算法

joins一个好的数据库设计的目标是尽量减少信息的重复，因此，需要连接来重构原始表。 本课程将介绍用于合并两个表的内部等值连接(inner equal-join)算法, 等值连接可以被修改以支持其他种类的连接，并且 等值连接也是实战中使用的最多的连接方式 等值连接使用记号 表示 操作的输出 假设有两个表R, S, 它们其中的tuple分别为r, s, 那么join操作在逻辑上的结果就是将两个表中

数据库

[CMU15445]:排序与聚合

sorting排序在数据库中发挥着重要作用，首先SQL会指明对输出进行排序(DESC…), 有些关系运算，比如连接运算，如果对输入关系进行排序，那么会得到更高效的实现 算法的选择 如果所有的数据都能够放入内存当中，那么当然是复杂度越低的排序算法越好，但是如果数据并不能够一次性全部放入内存，那么就需要考虑磁盘I/O, 如复杂度最低的快排，此时就需要进行大量的随机I/O, ,时间反而消耗比较高

数据库

[CMU15445]:索引并发控制

Index Concurrency ControlDBMS通过使用并发控制协议来确保在对一个共享的对象上进行并发操作能够得到正确的结果 一个协议的正确性可以分为两种 逻辑正确性 一个线程应该能够获取到他期望获取到的值 物理正确性 这意味着在我们的数据结构中没有指针指向非法的内存区域 在数据库中，我们关心的仅仅是逻辑正确性 Lock & Latch在之前已经介绍过Lock和Latch

数据库