当前课程知识点：高级数据库系统 > 第九讲 分布式数据库查询机制 > 3. 基于半连接算法的查询优化 > 3. 基于半连接算法的查询优化
下面我们来讲分布式查询的另外一种优化机制，基于半连接算法的查询优化
首先我们要知道什么叫做半连接运算
半连接运算，我们给出它的一个定义
半连接运算它是指由投影和连接操作导出的一种关系代数操作
它具体的定义是由下面的公式给出，比如说有一个关系R和关系S
他们在一个公共属性R.A=S.B上如果要进行半连接操作的话，它是一个什么样的操作方法呢
它是这样，R和S进行半连接操作运算，R在前S在后
他们是在公共属性A和B上进行等值连接，那么它的运算就等于什么呢
就等于我对R和S进行自然连接运算之后，然后再对R的属性上进行投影
形成的是这样一种结果，这样的话我们就可以把这个运算写成什么呢
我可以因为这个B的属性一定是在S上，A这个属性是在R上
所以我们就可以先对S在B属性上进行投影，投影出来一个非常小的关系
然后我再让R和这个小的关系来进行自然连接运算
那么这就是半连接运算的一个思想
这个半连接运算我还可以写成这样，S和R在公共属性A和B上进行等值的半连接运算
它就等于S和R进行自然连接运算之后，向S上的属性进行投影
它也就等于我先对R进行一个投影运算，把R向属性A上进行投影形成一个小关系
S再与这个小关系进行一个自然连接运算，半连接运算它是不对称的
也就是说R和S进行半连接运算，与S与R进行半连接运算它是不等价的
最后的结果是不同的，因为我们从这个公式就可以看出
我们既利用半连接运算就可以实现连接运算了，比如说我要做R和S进行自然连接运算
我就可以先利用R和S的半连接运算形成一个结果，然后再与S形成一个自然连接运算
这是刚才我们把半连接的定义实际上直接给拿过来
这就是我利用半连接运算来实现连接运算的一种思想
我们可以用一张图来给大家描述一下
利用半连接运算这个算法的思想，比如说有两个站点，站点1和站点2
站点1上有一个关系叫R，站点2上有一个关系叫S
我们可以用tuple（R）来表示R的元组数，用size（B）来表示某一个属性B的数据长度
现在比如有一个用户想从站点2上得到R与S的自然连接结果
假设说它是从站点2上发起的这样一种请求的话
如果我们用半连接运算，怎么去实现呢
它的实现过程基本上是这样，我首先在站点2上对S进行投影运算
把它投影到两个R和S进行自然连接运算的那个连接公共属性上
如果这个公共属性是B的话，第一步我就是对S向B上进行投影
投影就形成一个中间结果，然后我就把这个结果传送到站点1上
然后在站点1上利用这个结果，与站点1上的R进行自然连接运算
这样的话，我把这个自然连接运算如果我用一个R'来代表的话
在站点1上运算的R'回头来再传送给站点2
再由站点2上R'和S再进行自然连接运算
这样就形成了在站点2上R和S自然连接的过程
我利用半连接算法来实现自然连接
有同学可能会说，我费这么一大番周折是干什么呢
显然我们从这个运算的过程就可以看出，我们在站点2上进行投影
相当于把S这个片段变的更小，传输的数据量也就更少一些
然后我根据将这个传到站点1上，在站点1上对R进行自然选择
选择出来的R'肯定应该是更少的，然后再把R传送给站点2
这个目的就是使得我网络传输的数据量少
因为分布式的时候网络传输的代价是比较高的
所以如果我们这样做的话显然网络传输的数据量也少
如果我们说我们在这个站点2上S经过投影之后这个数据量已经很小了
然后再传到站点1上对R选择之后元组是更少，比如说可能只有1个或者2个元组
这样我们查询的效率就会很高
如果我们不这样做，而直接把站点1上的R传回给S的话
那么如果R比较大的话，这个传输的代价是比较高的
所以在这种情况下我们就可以用这种半连接算法来减少通信的代价
我们可以把刚才的过程的总代价可以用T来表示的话
它的代价基本上就是从站点2传到站点1再传回来
所以它有两次通信，它就有2C0再加上C1比如说是通信的速度或者说是速率
后面的size（B）和tuple（）指的就是S经过投影之后形成的小的关系和它所占用的大小
以及从这个站点1上我们R进行自然连接选择之后形成的结果的大小
它们再乘以通信速率实际上就是通信的代价
这就是我们采用半连接操作优化的一个代价
采用半连接优化的原理就是两个关系进行连接操作之前
要去掉一个无用的元组减少传输数据量，那么我们什么时候来使用它呢
我们并不是说在什么情况下都使用半连接算法，都是好用的
它会针对一些情况比较好用，比如说如果我们在R进行选择之后
它产生的中间结果R'非常小，在这种情况下我们使用半连接算法显然是非常有优势的
但是如果我们要是使用查询编辑器来选择的话
它肯定不会像我们人一样直接一眼看出来
它怎么去做呢，它肯定是先去计算各种可能
计算一下直接连接算法的代价，以及各种半连接的算法
我们用S半连接R来计算它的各种代价，然后与直接连接算法运算代价进行比较
最后从中选出一个最小的，它实际上是查询优化当中一种策略
什么时候去使用它，我们还要根据代价来进行衡量
-1. 数据文件的组织
-2. 索引的概念与分类
-3. B+树索引
-4. 散列索引
--1-4 散列索引
-5. 小结
--html
-6.练习--作业
-1. 查询代价的测量及查询处理过程概述
-2. 关系操作的基础算法
-3. 查询表达式的运算
-4.查询优化机制
-5.小结
--html
-6.练习--作业
-1. 数据库的故障及可恢复模型
-2. 事务及日志的相关概念
-3. 基于undo日志的恢复机制
-4. 基于redo日志的恢复机制
-5. 小结
--html
-6. 练习--作业
-1. 并发调度及相关概念
-2. 可串行化调度
-3. 冲突可串行化调度
-4. 小结
--html
-5. 练习--作业
-1. 锁的概念及封锁的原理
-2. 两阶段锁协议
-3. 多粒度锁及意向锁
-4. 死锁的处理
-5. 小结
--html
-6. 练习--作业
-1. 基于时间戳的调度
-2. 基于有效性检验的调度
-3. 小结
--html
-4. 练习--作业
-1. 分布式数据库系统的产生及定义
-2. 分布式数据库系统的模式结构与功能结构
-3. 分布式数据库系统中存在的技术问题
-4. 小结
--html
-5. 练习--作业
-1. 分布式数据库的设计方法、内容和目标
-2. 自顶向下方法构建数据库
-3. 数据的分片和分布设计
-4. 分布式数据库设计案例讲解
-5. 小结
--html
-6. 练习--作业
-1. 分布式查询处理的步骤和代价
-2. 基于等价变换的查询优化
-3. 基于半连接算法的查询优化
-4. 基于直接连接算法的查询优化
-5. 小结
--html
-6. 练习--作业
-1. 分布式事务概述
-2. 分布式事务的两阶段提交协议
-3.分布式并发控制概述
-4. 并发控制的加锁机制
-5. 并发控制的时标技术
-6. 小结
--html
-7.练习--作业
-试题--作业
