首页
>
知识点
关系代数表达式中的查询优化
知识路径：
>
数据库技术
>
关系数据库
>
关系运算
>
查询优化
被考次数：
1次
被考频率：
低频率
总体答错率：
49%
知识难度系数：
由 软考在线 用户真实做题大数据统计生成
考试要求：
掌握
相关知识点：4个
>> 更多 本知识点历年真题
关系系统的查询优化是关系数据库管理系统实现的关键技术，又是关系系统的优点。因为，用户只要提出“干什么”，不必指出“怎么干”。在关系代数表达式中需要指出若干关系的操作步骤，问题是怎样做才能保证省时、省空间、效率高，这就是查询优化的问题。
需要注意的是，在关系代数运算中，笛卡儿积、连接运算最费时间和空间，究竟应采用什么样的策略，节省时间空间。这就是优化的准则。
优化的准则
优化的准则有如下6条：
（1）提早执行选取运算。对于有选择运算的表达式，应优化成尽可能先执行选择运算的等价表达式，以得到较小的中间结果，减少运算量和从外存读块的次数。
（2）合并乘积与其后的选择运算为连接运算。在表达式中，当乘积运算后面是选择运算时，应该合并为连接运算，使选择与乘积一道完成，以避免做完乘积后，需再扫描一个大的乘积关系进行选择运算。
（3）将投影运算与其后的其他运算同时进行，以避免重复扫描关系。
（4）将投影运算和其前后的二目运算结合起来，使得没有必要为去掉某些字段再扫描一遍关系。
（5）在执行连接前对关系适当地预处理，就能快速地找到要连接的元组。方法有两种：索引连接法、排序合并连接法。
（6）存储公共子表达式。对于有公共子表达式的结果应存于外存（中间结果），这样，当从外存读出它的时间比计算的时间少时，就可节约操作时间。
关系代数表达式的等价变换规则
优化的策略均涉及关系代数表达式，所以讨论关系代数表达式的等价变换规则显得十分重要。常用的等价变换规则有如下10种。
连接、笛卡儿积交换率
设
E
1
和
E
2
是关系代数表达式，
F
是连接运算的条件，则有：
连接、笛卡儿积结合率
设
E
1
、
E
2
、
E
3
是关系代数表达式，
F
1
、F
2
是连接运算的条件，则有：
投影的串接定律
设
E
是关系代数表达式，
A
1
，…，
A
n
和
B
1
，…，
B
m
是属性名，且
B
1
，…，
B
m
是
A
1
，…，
A
n
的子集。则有：
该规则的目的是使一些投影消失。
选择的串接定律
设
E
是关系代数表达式，
F
1
、F
2
是选取条件表达式，选择的串接定律说明选择条件可以合并，则有：
选择与投影的交换律
设
E
是关系代数表达式，
F
是选取条件表达式，并且只涉及
A
1
，…，
A
n
属性，则有：
若
F
中有不属于
A
1
，…，
A
n
属性，
B
1
，…，
B
m
，那么有更一般的规则：
该规则可将投影分裂为两个，使得其中的一个可能被移到树的叶端。
选择与笛卡儿积的交换律
若
F
涉及的都是
E
1
中的属性，则：
σ
F
（
E
1
×
E
2
）≡
σ
F
（
E
1
）×
E
2
如果
F
=
F
1
∧
F
2
，并且，
F
1
只涉及
E
1
中的属性，
F
2
只涉及
E
2
中的属性，则有：
选择与并的交换律
设
E
=
E
1
∪E
2
，
E
1
、
E
2
有相同的属性，则：
σ
F
（E
1
∪E
2
）
≡
σ
F
（E
1
）∪σ
F
（E
2
）
选择与差的交换律
设
E
1
、
E
2
有相同的属性，则：
σ
F
（E
1
-E
2
）≡σ
F
（E
1
）-σ
F
（E
2
）
投影与笛卡儿积的交换律
设
E
1
、
E
2
是两个关系表达式，
A
1
，…，
A
n
是
E
1
中的属性，
B
1
，…，
B
m
是
E
2
中的属性，则：
投影与并的交换律
设
E
1
、
E
2
有相同的属性，则：
查询优化的算法
利用上述的等价变换规则可以对关系代数表达式进行优化，使得优化后的关系代数表达式符合上述的6条基本优化的准则。
算法：关系代数表达式的优化。
输入：一个关系代数表达式的语法树。
输出：计算该表达式的程序。
方法：
（1）利用规则4将形如
变换为：
（2）对每一个选择，利用规则4~8尽可能将它移到树的叶端。
（3）对每一个投影，利用规则3、9、10，5中的一般形式尽可能将它移到树的叶端。
（4）利用规则3~5将选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时进行，或在一次扫描中全部完成。
（5）将上述得到的语法树的内节点分组。每一双目运算（×，∪，
，-）和它所有的直接祖先为一组（这些直接祖先是
σ
，
π
运算）。如果其后代直到叶子全部是单目运算，则将它并入该组。
（6）生成一个程序，每组节点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。
相关知识点：
查询处理的代价
查询优化
基本概念
查询处理
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师
系统分析师
系统架构设计师
网络规划设计师
系统规划与管理师
初级资格科目
程序员
网络管理员
信息处理技术员
信息系统运行管理员
中级资格科目
系统集成项目管理工程师
网络工程师
软件设计师
信息系统监理师
信息系统管理工程师
数据库系统工程师
多媒体应用设计师
软件评测师
嵌入式系统设计师
电子商务设计师
信息安全工程师
本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。
工作时间：9:00-20:00
客服
QQ 486577830
商务合作
QQ 486577830
客服邮箱
service@rkpass.cn
京B2-20210865
|
京ICP备2020040059号-5
|
京公网安备 11010502032051号
|
营业执照
| Copyright ©2000-2026 All Rights Reserved 软考在线版权所有
