查询过程
parse - convert（Parse Tree -> Logical Query Plan） - apply laws（Improving the L.Q.P） - estimate result sizes - consider physical plans - estimate costs - pick best - execute
选择和投影尽量早做
后面整个么懂——反正考试不做要求Parameters for Estimation
M: # of available main memory buffers (estimate)
Kept as statistics for each relation R:
–T(R) : # of tuples in R
–B(R): # of blocks to hold all tuples of R
–V(R, A): # of distinct values for attribute R.A
= SELECT COUNT (DISTINCT A) FROM R
•Physical operators
–to implement physical query plans
–selections, joins
–one-pass, two-pass, (multi-pass)
–based on scanning, sorting, hashing, existing indexes
Crash Recovery
Undo日志
从后向前恢复
例题
Consider a system that uses pure undo logging. After a system crash, we find the following log entries on disk:
\
The last four actions in the schedule were incrementing each object by 1(e.g.<T4,A,11> was updating A to 12). How many different combinations of values of values for A,B,and C could possibly exist on disk at the time of the system crash?
A: 10,11,12；B: 22,23；C: 7,8。共12种可能 <T4,A,11>的只能体现，此时内存中的A被T3改成了11，但是磁盘上有没有被T3改过呢？不知道。内存中写了<Ti, X, v>，才可以改内存中的数据，所有<Ti, X, v>flush之后，才可以改磁盘数据。Redo日志
从前向后恢复
恢复速度极慢 -> 静态检查点
例题
Consider a system that uses pure redo logging. The initial database state was A=0,B=1,C=2. After a system crash, we find the following log entries on disk:
\
How many different combinations of values for A,B, and C could possibly exist on disk at the time of the system crash?
A: 5；B: 11；C: 8。有一种可能
Undo/redo日志
<Ti, X, Old-X-value, New-X-value>
恢复时，从前向后redo完成(有commit)的，从后向前undo未完成的
动态检查点
例题
Consider a system that uses undo-redo logging. After a system crash, we find the following log entries on disk:
\
\
How many different combinations of values for A,B, and C could possibly exist on disk at the time of the system crash?
A: 0,10,11；B: 3,22；C: 8,9,7
共18种可能
undo: T3,T4；redo: T2
结果：0,3,9
Concurrency Control
优先图
可串行调度
乐观方法
悲观方法
两段锁协议
共享锁：
写读后写的元素，可以直接上写锁，或者先上读锁，写的时候再升级为写锁；提倡第二种。
更新锁：解决两个事务对同一元素上了读锁，形成死锁的问题。If Ti wants to read A and knows it
may later want to write A, it requests an update lock (not shared)
解决死锁
一次封锁法：对所有要用的数据都加锁
顺序封锁法
调度器1负责按照rule1，rule3给事务加锁；调度器2负责按照rule2形成调度。
意向锁 IX，IS
插入时需锁父表，上Lx；删除时上Lx
锁表
| IS | IX | S | X | |
|---|---|---|---|---|
| IS | T | T | T | F |
| IX | T | T | F | F |
| S | T | F | T | F |
| X | F | F | F | F |
| S | X | U | |
|---|---|---|---|
| S | T | F | T |
| X | F | F | F |
| U | F | F | F |
| Parent Child locked in | Child can be locked in |
|---|---|
| IS | IS,S |
| IX | IS,S,IX,X |
| S | [S,IS; not necessary] |
| X | NONE |
事务的特性（ACID)
•原子性（Atomicity）
•一致性（Consistency）
•隔离性（Isolation）
•持续性（Durability）