开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第一课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/22
第一课（三）
内容介绍：
一、基于关系代数的查询优化算法及实例
二、物理查询优化（暨物理实现算法选择与次序优化）
三、代价估算
四、事务处理
五、数据库系统体系结构
三、代价估算
1.什么是代价估算
代价估算是根据已知的统计信息，给出查询执行计划，然后估算出查询执行下来需要多长时间，估算代价。
已知表达式E中的各个关系的统计信息
TR或T(R):关系R 的元组数目;
Bp或B(R):关系R 的磁盘块数目;
l或I(R):关系R 的每个元组的字节数;
f或f(R):R 的块因子，即一块能够存储的R的元组数目
V(R, A):R 中属性A出现不同值的数目，即ПIa(R)的数目.
SC(R,A):R 中属性A的选择基数，满足 A 上等值条件的平均记录数
“给定一个表达式E，如何计算E的元组数目T(E)以及属性 A 上不同值的数目V(E,A)?”
●在E实际获得之前计算T(A),V(E,A)等是很难的事情;
●因而，要“估算”，代价估算
代价估算有几个东西，第一个叫代价估算模型，这个模型就是一个公式，简单讲就是类似一个公式，或者是一个程序。一个工具模型，再加上统计信息，根据这两个，然后再加上查询的表达式，就可以估算出这个代价估算。代价估算这个模型就是一堆公式，那么这个公式，当然可以根据算法分析去推出一些公式，然后在推出公式当中，大家注意，这个公式当中往往会有一些系数，这个系数的值有时候确定不了，只知道有这个系数，从数学的角度讲，可以推出来这个地方有一个系数，但这个系数值怎么得到？它可以通过大量的实际运行，大数据分析，如果我有实际数据库产品就可以从数据库里的大量查询计划中得到比较准确的系数，这个系数相当于配方，它通过大量的实验摸索，就可以摸索出精准的系数。那么这个估算还有一种方法，就是用 AI 的方法。虽然叫 AI，其实 AI 方法也算不上，就是利用机器学习的方法，如果我的数据库到处在运行，我把运行的查询计划，那些运行数据全拿来，它有代价，代价以后我通过训练训练出一个模型，那么它来估算，就是利用机器学习的方法来做。
2. 投影运算的代价估算?
“估算一个投影(R)的大小”
简单:T(πL(R))= T(R)
>投影运算只是对列有所取舍，并未对行有所变化，如并未消除重复
>投影运算并未减少行数，但可能有效地减少了存储结果关系的块数
>例如:磁盘块大小=1024 Byte
R的元组长度=120 Byte,8元组/块，T(R)=10,000,则
B(R)= 10000/8 = 1250;
T(R)的元组长度=20 Byte,50元组/块，则
B(T(R)) = 10000/50 = 200;
3.不同选择运算的代价估算
“估算选择运算S=σ A=c(R)的大小”
>T(S)介于0 to T(R)-V(R,A)+1之间
---最多:A属性不同值的元组都只存在一个，剩余的都是A=c的元组>估计:T(S) = T(R)/V(R,A)
---A属性不同值的元组数假设是平均分布的
>当不知道V(R,A)时，估计:T(S) = T(R)/10.
“估算选择运算S= σA
>T(S)介于0 to T(R)之间
---最多:所有元组都满足条件
>估计: T(S)= T(R)/2
---直觉，应有一半的元组，
>实际应用的估计:T(S)= T(R)/3
“估算选择运算 S= σA=10 ANDB
>估计:T(S) = T(R)/(V(R, A)*3)
---σA=10 AND B<20(R)= σB<20(σA=10(R))
---A=10，得出 T(S) = T(R)/V(R,A);
---B<20，得出 T(S)= T(S)/3
“估算选择运算 S = σc1or c2(R)的大小”
>估计:T(S)=n(1-(1-m,/n)(1-mz/n))
---R 有 n 个元组，其中有 m,个满足 C1,有 mz 个满足 C2
---(1-m,/n)是不满足C1的那些元组，(1-m2/n)是不满足 C2的那些元组
---两数之积是不在 S 中的那部分 R 的元组，1减去这个积就是属于 S 的那部分元组出现的概率。
“估算选择运算 S= σA=10 OR B<20(R)的大小”
>估计:T(S)=n(1-(1-m,/n)(1-m/n))
--- n= T(R)=10000，V(R,A)=50,
m1=T(R)/V(R.A)=10000/50=200；
m2=T(R)/3 = 10000/3 ~ 3333
(有 m,个满足 C1,有 mz 个满足 C2, (1-m1/n)(1-m2/n)不满足这个条件的元组的概率1- (1-m,/n)(1-m/n)满足这个条件的元组的概率)
---简单估计:T(S)= T(R)/3 = 10000/3 ~ 3333
---复杂估计:
T(S)=10000*(1-(1-200/10000)(1-3333/10000) ~ 3466
4.连接运算的代价估算?
“估算连接运算 S= R(X,Y) Natural Join s(Y,Z)的大小”
>估计:T (S)=T(R)T(S)/max(V(R,Y),v(S,Y))
---假定V(R,Y)>=V(S,Y),R中元组r和S中元组有相同Y值的概率=1/V(R,Y)
---假定V(R,Y)
---则，在Y上相等的概率= 1/max(V(R,Y),V(S,Y))
>例:T(R)=10000,T(S)=50000,V(R,Y) = 500, v(S, Y)=1000
估计:T(S)=10000*50000/1000=500000。
>例:T(R)=10000,T(S)=50000, V(R, Y) = 2000, v(S, Y)=1000
估计: T(S)=10000*50000/2000=250000。
5.简要结论
代价估计
>T(R)--R的元祖个数，V(R, A)—R 中属性 A 上出现的不同值的数目>判断满足单一条件元组出现的概率
√出现等于某一个值的概率=1/V(R,A)，或者简单的概率=1/10
√出现不等于某一个值的概率=1-1/V(R,A)，或者简单的概率=1-1/10
√出现小于或不等于某一个值的概率直觉上=1/2,实际处理概率=1/3>判断满足多个条件的元组出现的概率
√如果是“与”，则将满足两个条件的概率相乘
√如果是“或”，则=(1-(1-m,/n)(1-m2/n)，不出现满足条件1的元组的概率(1-m,/n)，不出现满足条件2的元组的概率(1-m2/n)，二者相乘是不同时出现的概率，则1-(1-m,/n)(1-m/n)即为去掉不同时出现的概率，即为或条件的概率。
>复杂的表达式可以依上原则进行估算，确定估算公式。
代价估算实际上就是概率统计，现在的方法是每一个运算给出一些公式，将相关统计参数反应到公式里面，然后统计参数信息，实际参数信息代入进来。所以，故算准不准确有两个因素，第一个是模型好坏，第二就是统计信息是否准确，这两个有一个有问题，估算结果就不准，估算不准的结果是优化决策是错误的。
5.归纳总结
查询处理和优化，首先语句进行编译，编译完成后，把它转换成一个内部的表达式树或者语法树，就是一个代数表达式。然后对它进行语法优化或叫代数优化，也就是进行等价变换。然后逻辑查询计划，因为还不能直接执行，因为每个运算具体怎么执行还没确定。那么下面就进行物理层优化，物理层优化就包括代价估算。然后进行算法选择，另外还有一个装配次序，表达式运算时候还有一个装备顺序的选择，那么这些东西都属于数据库管理系统的核心技术。
后面还有一个内容，事务处理，这个内容就不展开讲解了，大家了解即可。
四、事务处理
事务处理第一个内容就是事务的概念，大家首先搞清楚数据库里为什么会出现事务概念。事务，主要解决什么问题？就是数据库有两类操作，一类查询操作，查询操作的特点是它不改变数据库的东西，它是只读取。
我们前面讲还有一类操作是增删改查，查我们前面已经解决了，现在就增删改，就是插入删除修改，这个操作会改变数据库状态，而改变数据库状态，发现一个问题就是数据库在应用层面，它有时候数据库更新操作，可能两个操作、三个操作是关联操作。这个最典型的就是转账，就是转账，钱从一个账户转到另外账户，要做两个操作，在 a 账户里要减一笔钱，B 账户里加一笔钱。那么这两个操作有一个特点，就这两个操作，要么都做，要么都不做，必须做一个整体，那把这样的关联操作称为事务。
事务性质，说到事物性质，在传统数据库里就是有四个叫性质，叫 ACID，A 就是原子性，C 就是一致性，I 隔离性，D 持久性。原子性就说事物的操作是一个整体，要么都做，要么都不做。一致性，就是事物的操作不能破坏数据的一致性，隔离性，就是同时有多个事物在执多个事物就叫并行或叫并发。两个事物，同时访问同一个数据，那么这个时候会有冲突，有冲突就要进行调度，要排个序，把它隔离开，这个就叫隔离性。
持久性，就数据库运行当中，它可能会发生故障，就有可能会发生故障，比如宕机，就叫系统故障。还有事务本身执行出错了，就是程序出错了，或者最严重的，比如这个文件丢了或者磁盘坏掉造成数据丢失，在这种情况下，怎么来保证事物的 ACID？这就是这些技术，那么这个技术在数据库管理系统当中有两个，一个叫并发控制，并发控制主要就是几个概念，第一个就是调度，就是多个事务同时执行时，如何给它们其操作排序。
调度有一个重要的知识点是可串行性，具体细节不讲，用到的技术是基于锁的，还有基于时间戳的。另外一个叫故障恢复，故障恢复是一种预防措施或是保险措施，比如外机发生故障，如何将损失降到最低或者不造成损失，这时故障恢复要解决的问题。故障恢复用到的基本原理是冗余技术，冗余就是同一数据多存储几次，就是备份，主要是对付介质故障和系统故障，特别是介质故障，它必须有备份，就是提前将内容导出，将其托底保存，落到磁带上或者刻在光盘上。
另外在运行时有事务日志，日志有什么作用，就是实际上数据库为了保险，每个操作在做之前它会把这个操作的内容记在一个日志文件里做个日志记录，那这个日志记录有什么用？一旦操作失败了，我可以进行回退或进行重做，执行两个操作就保证原子性，保证事物持久性。另外，还有技术叫检查点，这个就是故障恢复技术，那么这个内容展开讲非常多。为什么不讲有，原因：一个就是这个内容都是很成熟的，另外，成功，可以讲数据库里的事务处理，这块技术非常成功，成功到我们现在每天都在不知不觉的用。
其实，在上个世纪80代90年代就做了大量的投入研究，研究的非常透彻的，为什么会这样？就是为了满足银行金融的业务需求，它实际上是银行要做电子化，那么当时信用卡、转账这些业务就必须要保证，首先这个整个业务的连续性、可靠性它要求很高，那么在这个时候发展出的一套东西就非常成熟，还有就是这些东西的创新性已经不高，不能绝对说这个东西以后就不会有创新，但是现在来说是一个很成熟的例子。第二，就是很成功，大家都在使用，所以这块内容就不展开进行讲解了。
五、数据库系统体系结构
本章内容特色:
>理解数据库系统体系结构必须从宏观和计算机系统体系结构的历史演化两个视角进行展开。
本章要解决的关键问题:
>如何认识和解决数据库系统体系结构演化过程中面临的“分”与“合”的矛盾。
不只是数据库，所有计算机体系架构当中都是一个分分合合的矛盾，那么在数据库里，它有两种架构，一种叫集中式，另外一种叫分布式，当然还有很多是介于两者之间的分、合架构。
原有内容是数据库体系结构、分布式数据库、并行数据库、大数据与云数据管理、区块链。现在是把前面的内容大幅压缩，然后后面多点时间讲区块链，因为近些年区块链发展很快，大家要了解区块链里的一些基本思路。另外区块链与钱有关，因为它要发行一种货币更容易招骗子。区块链颠覆了数据库原有的一些东西，但是正确性另说，但是至少在理论上颠覆了原来数据库的盲点，以前的数据库不考虑数据的可吸附问题，认为数据是应用层面的问题，数据是否可行与数据库无关，数据库只是将数据存储起来。当然后来数据库也有了一些措施，比如事务处理，其实某种意义上事务处理是为了保障数据可信、业务可信。
主要内容是系统体系结构概述、DDB 与数据集成系统、分布式系统的演进和架构、分布式架构的基本理论、云原生数据库还有 No SQL 数据库。
