查询优化、恢复、并发控制全文

覆盖图片：546F40F2C52B5C38C4499ACAFD01FEDD.png、4B47BA6244099451BB27641110ABD42A.png、01BC0C9A088A35C1E0B81ED19A685DF9.png、C921AF903DCA13A80965ACDB7CEF8F9C.png、cab4c3c8b24470d4ddf52b9df6207c11.jpg、IMG_0689.JPG、IMG_0689 (1).JPG、IMG_0758.JPG、IMG_0758 (1).JPG、IMG_0759.JPG、IMG_0759 (1).JPG、C9D8CB7A918276A0773E0692137C82A9.png、45CF842DC915B004480C3FA46A6D8877.png、3616296FFDE186166B4E653F08EFFBEC.png、FFE74D06B1635830F1A4C3D7C083A176.png、7527539A3DBAAE0A5038034B956F2ECD.png、14BF3623B362548EEFD56F6081DAEC07.png、FC354D38D2E9BFC51DD56129E8A8BF83.png、7EFBDE17B0116BB9766F10AC8BFF9AE4.png。

查询优化题面

题面：

Query Optimization

Consider the query:

SELECT p.PNO, PName, Price, StockNum
FROM Product p, Stock s
WHERE p.PNO = s.PNO
  AND StockPlace = 'Warehouse1'
  AND Price > 4;

1. Give a relational algebra expression using Cartesian product equivalent
   to the query.
2. Draw a syntax tree for the above relational algebra expression and give
   a procedure for query optimization.
3. Give the optimized relational algebra expression.

笛卡尔积等价关系代数表达式：

π_{p.PNO, PName, Price, StockNum}
  ( σ_{p.PNO = s.PNO ∧ StockPlace = 'Warehouse1' ∧ Price > 4}
    ( Product × Stock ) )

优化思想：

将选择条件分解。
将选择尽早下推到对应基本关系。
将笛卡尔积加选择转换为连接。
将投影尽早下推，只保留后续需要的列。

优化后的关系代数：

π_{PNO, PName, Price, StockNum}
(
  (π_{PNO, PName, Price}(σ_{Price > 4}(Product)))
  ⋈_{Product.PNO = Stock.PNO}
  (π_{PNO, StockNum}(σ_{StockPlace = 'Warehouse1'}(Stock)))
)

对应查询树，文本版：

π PNO, PName, Price, StockNum
└── ⋈ Product.PNO = Stock.PNO
    ├── π PNO, PName, Price
    │   └── σ Price > 4
    │       └── Product
    └── π PNO, StockNum
        └── σ StockPlace = 'Warehouse1'
            └── Stock

规范的查询优化步骤

课堂清单：

规范的查询优化的步骤：
1. 文字描述的应用问题场景。
2. 给出其实现的 SQL 语句。
3. 写出 SQL 语句对应的关系表达式。
4. 绘制相应的查询树：project/select/join。
5. 绘制对应的关系代数语法树。
6. 对其进行优化，给出优化依据的规则。
7. 给出优化后的结果语法树。
8. 给出对应的关系表达式。
9. 编写查询执行策略/计划书。

关系代数等价变换规则

课堂可见规则：

关系代数等价变换规则
关系代数表达式等价
常用的等价变换规则：

1. 连接、笛卡尔积交换律。
2. 连接、笛卡尔积结合律。
3. 选择的串接定律。
4. 投影的串接定律。
5. 选择与投影的交换律。
6. 选择与笛卡尔积的交换律。
7. 投影与笛卡尔积的交换。
8. 选择与并的交换。
9. 选择与差运算的交换。
10. 投影与并的交换。

E 是关系代数表达式，F 和 F_i 是连接/选择条件。

常用公式：

R × S = S × R
(R × S) × T = R × (S × T)
R ⋈ S = S ⋈ R
(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)
σ_{F1 ∧ F2}(E) = σ_{F1}(σ_{F2}(E))
π_{A}(π_{A,B}(E)) = π_{A}(E)
σ_F(R × S) 可在条件只涉及 R 或 S 时下推
π 可在保留连接属性和最终输出属性前提下下推

数据库恢复：检查点恢复题

题面可见：

运用检查点恢复技术，填写以下策略和内容：
图中划线、箭头、实心圆分别表示事务开始/结束，事务未结束。

对事务的处理策略：
T1 事务：____
T2 事务：____
T3 事务：____
T4 事务：____

在基于检查点恢复过程中：
开始：
ACTIVE-LIST = { ... } （2分）

处理后，生成的事务队列：
UNDO-LIST = { ... } （2分）
REDO-LIST = { ... } （原图下部被遮挡）

图形内容文本化：

左竖线：检查点。
右竖线：系统故障/恢复时刻。
多条事务时间线 T1、T2、T3、T4、T5、T6、T7、T8。

可见状态：
- 有些事务在检查点前开始，检查点后提交。
- 有些事务在检查点前开始，到故障时仍未结束。
- 有些事务在检查点后开始并在故障前提交。
- 有些事务在检查点后开始，到故障时仍未结束。

做题方法：

1. 检查点时正在执行的事务进入 ACTIVE-LIST。
2. 从检查点之后的日志向后扫描：
   - 遇到 begin/start，加入 UNDO-LIST。
   - 遇到 commit，若事务在 UNDO-LIST 中则移出，加入 REDO-LIST。
3. 故障时未提交事务进入 UNDO-LIST。
4. 故障前已提交事务进入 REDO-LIST。

注意：照片中各事务编号笔迹较模糊，无法可靠确定每条事务线的编号，因此此处保留方法和可辨结构，不强行猜具体集合。

并发控制题面

题面：

Concurrency Control:
Consider the following two transactions:

T1:
read(A);
read(B);
if A = 0 then B := B + 1;
write(B);

T2:
read(B);
read(A);
if B = 0 then A := A + 1;
write(A);

Add lock and unlock instructions to transactions T1 and T2 so that
they observe the two-phase locking protocol.
Can the execution of these transactions result in a deadlock?

两阶段封锁协议参考答案：

T1:
SLock(A);
SLock(B);
read(A);
read(B);
if A = 0 then B := B + 1;
XLock(B);      -- 或一开始直接 XLock(B)
write(B);
Unlock(A);
Unlock(B);

T2:
SLock(B);
SLock(A);
read(B);
read(A);
if B = 0 then A := A + 1;
XLock(A);      -- 或一开始直接 XLock(A)
write(A);
Unlock(B);
Unlock(A);

更严格且避免锁升级细节的写法：

T1:
SLock(A);
XLock(B);
read(A);
read(B);
if A = 0 then B := B + 1;
write(B);
Unlock(A);
Unlock(B);

T2:
SLock(B);
XLock(A);
read(B);
read(A);
if B = 0 then A := A + 1;
write(A);
Unlock(B);
Unlock(A);

是否可能死锁：

可能。
例如 T1 先持有 A 的 S 锁并等待 B 的 X 锁；
T2 先持有 B 的 S 锁并等待 A 的 X 锁；
双方互相等待，可能形成死锁。

一级、二级、三级封锁协议课堂片段

可见代码片段：

VII. Concurrency Control

T1【三级封锁协议】
SLock(A)
while ... GET
XLock(B)
while ... GET
read(A);
read(B);
if A = 0 then B = B + 1;
write(B);
COMMIT;
Unlock(A);
Unlock(B);

T1【一级封锁协议】
XLock(B)
while ... GET
read(A);
read(B);
if A = 0 then B = B + 1;
write(B);
Unlock(B);

T1【二级封锁协议】
SLock(A)
while ...
read(A);
Unlock(A);
XLock(B)
while ... GET
read(B);
if A = 0 then B = B + 1;
write(B);
Unlock(B);

课堂结论：

可能会导致死锁。

封锁协议方法

一级封锁协议：
事务 T 修改数据 R 之前必须对 R 加 X 锁，直到事务结束才释放。
可防止丢失修改。

二级封锁协议：
在一级基础上，读数据前必须加 S 锁，读完即可释放 S 锁。
可防止读脏数据。

三级封锁协议：
在一级基础上，读数据前必须加 S 锁，并保持到事务结束。
可防止不可重复读。

两阶段封锁协议：
事务分为加锁阶段和解锁阶段。
一旦释放任何锁，就不能再申请新锁。
可保证冲突可串行化，但可能发生死锁。