开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第一课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/22
第一课（一）
内容介绍：
一、基于关系代数的查询优化算法及实例
二、物理查询优化（暨物理实现算法选择与次序优化）
三、代价估算
四、事务处理
五、数据库系统体系结构
上节课讲到查询优化，查询优化讲到两个内容，一个是物理优化，一个是代数优化。代数优化就是对一个关系代数表达式进行等价变换，把它从一个低效形式变成高效形式，这个变换主要是利用等价变换规则。等价变换规则主要是不同的运算，两两之间是否可以交换顺序，另外是否满足结合律，交换顺序就是一个先做，一个后做，将二者顺序改变，结果不变就是等价。
下面给出的是关系代数的优化算法，严格来说不是算法，只是给出了一个框架，就是优化需要做些什么，不是严格意义上的算法，但是习惯叫成算法。
一、基于关系代数的查询优化算法及实例
1.算法表达
Algorithm:关系代数表达式的优化算法
Input: 一个关系代数表达式的语法树
Output:计算该表达式的程序
Method:
(S1)依据定理 L4，把形如OF1 F2 A.. Fn (E))的选择表达式变成串接形式oF1( F2(…( Fn(E)))).
(S2)对每个选择，依据定理L4至L9，尽可能把它移至树的底部。
(S3)对每个投影，依据定理L3，L7，L10和 L5，尽可能把它移至树的底部。如果一个投影是对某表达式所有属性进行的，则去掉之。
(S4)依据定理L4至L5把串接的选择和投影组合为单个选择、单个投影，或者一选择后跟一个投影。
(S5)对修改后的语法树，将其内结点按以下方式分组:
每个二元运算结点(积、并、差、连接等)和其所有一元运算直接祖先结点放在一组;对于其后代结点，若后代结点是一串一元运算且以树叶为终点，则将这些一元运算结点放在该组中;若该二元运算结点是笛卡儿积，且其后代结点不能和它组合成等连接，则不能将后代结点归入该组。
(S6)产生一个程序:它以每组结点为一步，但后代组先执行。
这种用自然语言解释的不能叫算法，但是处理步骤基本都给出了。
基本思想：第一，把表达式中所有的筛选尽量往下推，什么是下推，就是它在表达式树上本来是靠根节点的，然后尽量往叶子推。因为这个表达式树，它是从叶子开始，它是倒着走的，叶子就是一个基本表，基本表结果已经有了。然后，对这个表进行扫描进行要扫描，连接投影，最后到最终的结果出来。那么这时候要把筛选下推，因为筛选预算，它是关系缩小，所以尽量让它提前做下推。另外一个是投影的下推，投完后对表达式做一些整理，具体过程就不详细说了。
2.示例
查询:“查出2021年1月1日前被借出的所有书的书名”
这个是图书馆里有一个叫借阅关系，这个借阅，然后就是查询这个书的书名或书的标题。借阅日期在2021年1月1日之前，是小于等于。上图第一行对应的是它的 SQL 语句啊，如果你把它转换成这个关系代数表达式，上图左侧内容就是它对应的关系代数表达式。XLOANS 实际上是一个跟借阅有关的一个视图，那么这样就得到一个语法树，大家注意到这个语法树，投影，然后筛选，然后视图，那么这个视图，把定义带进去之后，上图右侧就是视图的定义内容。实际上这个视图里借阅、读者先进行一个笛卡尔乘积，再和读书做一个笛卡尔乘积，这要求三个笛卡尔乘积，然后再按照这个条件做一个筛选，最后再做投影，再做筛选，再做投影。大家可以看到由树叶到树根反映了操作先后次序。如果将表达式推下去，就相当于先操作，这样关系表就缩小了。
F2，F3是两个表的连接条件，以上涉及到三个表，读者、图书和借阅三个表，三个表之间在进行连接时要进行两次连接，就是F2、F3。
F1是一个筛选条件，这个筛选条件是借阅日期，它只和借阅有关系，所以F1要尽量下推，也就是把在这之前的下推，这样关系表就缩小了，XLOANS就是借阅视图的定义。
此时，算法：
①依据定理L4，把形如σF1F2 八...Fn(E))的选择表达式变成串接形式σF1(σF2(-.(σFn(E)))).
②对每个选择，依据定理L4至L9，尽可能把它移至树的底部。
区别：左侧没有筛选展示的是所有借阅关系，而右侧是将2021年1月1日之前的过滤了。如果条件更具体，假设就查2021年1月1日的，那么这个筛选大部分都被筛选掉，因为借阅关系每天都有，比如有十年的借阅关系，十年里只查一天的借阅关系，就相当于与3600分之1，这个表3600分之1去连接和全部去连接相比，代价降很多
之后对投影进行下推：
投影也会使关系变小，因为它是把需要的列拿出来，但是投影下推不是把投影本身，投影是推不下去的，而是通过无中生有加一个投影，每一个表达式都是一个虚拟关系，这个关系会带有列，然后再往上再往上，那么到最上面最终的结果关系当中，如果只需要这个列，而到这个地方发现这个下面规约处理关系当中有多余的，不需要的点。就在这里头加一个投影，就无中生有的插入个投影。插入一个新的投影就是把不需要的东西过滤掉，这就是投影的下推。
投影的下推是追加一个投影，而不是将上面现有的投影挪下来。
表达式的优化主要是筛选下推和投影下推。
(S3)对每个投影,依据定理L3，L7，L10和L5，尽可能把它移至树的底部。如果一个投影是对某表达式所有属性进行的，则去掉之。
最后，对表达式做进一步整理，下图是整理之后得到的表达式。
最终得到的表达式树再下一步就是物理优化，对每个运行决定具体如何实现就属于物理优化。代数优化就是从一开始的表达式到最后得到目标表达式，这个过程就叫代数优化。
代数优化再下面一步要对其进行分组：
(S5)按以下方式分组:每个二元运算结点(积、并、差、连接等) 和其所有一元运爱直技祖先结点放任—一生;于其后代结点，若后代结点是一串一元运算且以树十为终点,则0二些一元运算结点放在该组中;若该二元运算结点是笛卡儿积,县灵豆代结点不能和它组合成等连接，则不有石1结点归入该组。
(S6)产生一个程序:它以每组结点为一步，但后代组先执行。
下图是表达式树计算实现的过程，这个实现叫流水线化，流水线化有两种，一种是推式，一种是拉式。推式是从下往上，先算这个，这个算完结果出来之后再往上算；拉式是启动一个，这个向下面要东西，下面再往下就是拉式。
这个程序执行就可看成是数据处理的流水线，这个程序执行时对磁盘进行操作，将磁盘的块掉进来，掉进来之后按照每一个运算方法去调用，最后完成整个计算过程。以上就是查询的代数优化。
下面提到一些复杂的 SQL 语句处理问题
3.复杂 SQL 语句的处理问题
复杂的问题：第一个，如果有分组计算和分组条件过滤如何去做？
这时需要关系代数表达式中增加一些新的算子，除了之前讲过的关系代数中几个基本算子，集合运算、并、交、插、投影、筛选和笛卡尔积，还要增加一个算子，分组，它有排序、聚集的意思。对于它要研究分组、聚合、排序运算是否有交换律，这个问题在代数优化中都有相应文章。
还有一个问题是嵌套查询如何处理？SQL 语句当中有嵌套查询，嵌套查询有两种，一种就是非相关的子查询，那么就可以把它转换成一个表连接查询，就是可以把它转换成等价的表连接查询，那么还有一些嵌套查询是没法转的，嵌套查询的实现实际上是专门有研究的，在 SQL 的查询引擎里头有专门研究，但是这里就不讲了。
