第七章
2017-01-02 13:31:45 0 举报AI智能生成
第七章，是故事的高潮部分。在这一章中，主角经历了一系列的挑战和困难，最终达到了他的目标。他的决定和行动引发了一系列的连锁反应，改变了他的生活和他周围人的生活。这一章充满了紧张和激动，让读者无法停止阅读。主角的勇气和决心在这一章中得到了充分的展现，他的故事也在这一章中达到了高潮。这一章的结局是令人惊讶的，但又完全符合故事的发展逻辑。总的来说，第七章是一个充满悬念和冲突的章节，它让读者对主角的命运产生了深深的关注。
作者其他创作
大纲/内容
2.查询优化
执行代价
集中式数据库
I/O代价
CPU代价
内存开销
分布式数据库
集中式数据库代价+通信代价
总目标
选择有效的策略
得到关系表达式的值
使查询代价最小
分类
代数优化
物理优化
基于存取路径的优化
基于代价估算的优化
两者结合的优化
方法选择依据
基于规则
基于代价
基于语义
4.基于存储路径的优化
选择操作
小关系
全表顺序扫描
大关系
主键=值查询
主键索引
非主属性=值查询
估算结果个数
比例较小（<10%） 索引
比例较大 全表顺序扫描
非等值查询、范围查询
AND连接的合取选择
有组合索引，优先组合索引扫描方法
有一般索引，索引扫描方法
否则，全表顺序扫描
OR连接的析取选择
全表顺序扫描
连接操作
按照连接属性排序
排序合并法
一个表在连接属性有索引
索引连接法
其中一个表较小
散列连接法
嵌套循环法
选择占用块数较少的表作为外表
5.基于代价估算的优化
选择操作
顺序扫描法
基本表大小为B块，扫描代价B
条件为键=值，平均扫描代价B/2
索引（散列）扫描法
键=值，L层B+树，代价L+1
涉及非键属性，有S个结果符合条件，代价L+S
连接操作
嵌套循环法
Br + Bs/(k-1)Br
Br + Bs/(k-1)Br + (Frs*Nr*Ns)/Mrs
需要将连接结果写回磁盘
Frs为连接选择性，表示连接结果元组的比例
Mrs表示每块可以存放的元组数
排序法
已排好序
Br + Bs + (Frs*Nr*Ns)/Mrs
B块文件排序代价
(2*B) + (2*B*logB)
1.查询处理
过程
查询分析
语法分析
词法分析
语义分析
查询检查
安全性检查
完整性检查
有效性检查
建立查询的内部表示
语法树
语法图
查询优化
查询执行
基本算法
选择操作
顺序扫描法
二分查找法
使用索引（或散列）的扫描法
复合选择
组合索引
单独索引
多个索引
连接操作
嵌套循环法
排序合并法
索引连接法
散列连接法
投影操作
包含主键
直接执行
不包含主键
消除重复元组
排序，消除重复副本
散列法
集合运算
并、差、交
排序合并法
笛卡尔积
嵌套循环法
3.代数优化
等价变换规则
连接、笛卡尔积交换律
连接、笛卡尔积结合律
投影的串接定律
ΠL1 ( ΠL1 ( ··· ( ΠL1( E ) ) ··· ) ) ≡ ΠL1(E)
选择的串接定律
σF1 ( σF2( E ) ) ≡ σF1∧F2 ( E )
选择与投影的交换律
ΠA1,A2,···,An (σF ( E ) ) ≡ ΠA1,A2,···,An ( σF ( ΠA1,A2,···,An,B1,B2,···,Bm ( E ) ) )
选择与笛卡尔积的交换律
σF(E1×E2) ≡ σF(E1) ×E2
σF(E1×E2) ≡ σF1(E1) × σF2(E2)
σF(E1×E2) ≡ σF2( σF1(E1) × E2)
选择与并的分配律
σF(E1∪E2) ≡ σF( E1) ∪ σF(E2)
选择与差的分配律
σF(E1 - E2) ≡ σF( E1) - σF(E2)
选择对自然连接的分配律
σF(E1 ∞ E2) ≡ σF( E1) ∞ E2
σF(E1 ∞ E2) ≡ σF1( E1) ∞ σF2(E2)
投影与笛卡尔积的分配律
ΠA1,A2,···,An,B1,B2,···,Bm(E1×E2) ≡ ΠA1,A2,···,An(E1)×ΠB1,B2,···,Bm(E2)
投影与并的分配律
ΠA1,A2,···,An(E1∪E2) ≡ ΠA1,A2,···,An(E1)∪ΠA1,A2,···,An(E2)
启发式规则
选择运算应尽可能先做
投影运算和选择运算同时进行
投影同其前或其后的双目操作结合起来
选择操作同笛卡尔积操作结合成为连接操作
找出公共子表达式
算法
将σF1∧F2 ( E )化为σF1 ( σF2( E ) )
将选择操作尽可能移向叶端
将投影操作尽可能移向叶端
把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影
语法树内节点分组，双目运算和其直接祖先一组
0 条评论
下一页
为你推荐
查看更多
