访问策略的优化

《访问策略的优化》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第七章访问策略的优化在第六章中，我们已经讨论了对于全局关系的査询算符树，如何依据准则1…2通过关系代数的等价变换来改良查询；对于规范化算符树则再依据准则3…5通过限定关系代数的等价变换来改良查询；这种改良可提高访问效率，但没冇进行量化的讨论，如提高效率多少？减少开销多少？本章讨论内容已由标题醒目的点出：访问策略的优化，特点是基于数据库值的优化，冇具体的量化，比较深入。即在各种可能的方案中选择一种费用最少的方案，相对而言，效率也较高，但往往得不到最忧方案，只是找一个较好的方案。7.1查询优化概论本节首先讨论

2、査询处理问题、模型化问题和解决这些问题所需的假定，以及优化小使用的准则，然后建立査询的新模型及相应的定量参数。7.1.1查询优化中的问题査询处理策略的选择包括：1.对某一段，给定一个査询表达式，决定要对这个段执行査询的物理拷贝，一般在文献中使用实质这个术语來表示对其执行査询的一个非兀余的拷贝，实质相当于为每个段选择它的一个拷贝。不同的査询可能使用不同的实质。2.选择操作执行的次序。即如何决定结合、半结合和并集操作这儿种混合操作的次序。第六章査询变换以后产生的算符树隐含地定义了操作的部分次序，即从叶至根向上

3、的执行操作，但这并没冇完全规定优化问题的解，还要指出树的同一级上执行的各子表达式求值的次序，同时，从叶至根地向上执行并不一定能产生最佳结果。3.选择执行毎个操作的方法。包括在同一数据库访问中选择一起执行儿个代数操作（如同时对同一操作执行选择和投影操作），以及在各种可用的方法屮选择执行每个数据库访问的方法。戢怵I难的是决定结介求值的鼓佳方案。上述三个问题相互间有影响，并非孤立。但也相当复朵，这里假设三者独立，并重点讨论第二个问题。7.1.2查询处理优化的目标不管在集中式还是分布式环境中，査询执行策略都是根据

4、对各种方案的期望性能进行衡量來选择的。在集中式数据库中，典型的度量方法是计算输入/输出操作的次数以及CPU的使用情况（I/O次数要尽暈少、CPU占用尽量少）。在分布式数据库中，除上述两项外，还必须考虑数据的传输量及延迟。时间，针对考虑的方面不同，主尖EI标也不同。传输的要求可以依据费用和延迟这两方面來评价。1.当考虑费用时，一个应用的性能是用所冇传输的费用Z和來度量的。2.当考虑效率时，一个应用的性能是用此应用从激活到完成所经历的时间来度量的。一次传输的传输费用TC和传输延迟TD町用函数表示为：TC(X)

5、=C()+XXGTD(X)=D()+XXD]其中C()、D()、G、D

6、是与系统有关的常数，Co相当于在两站点间启动一次传输所需的固定费用；C

7、是网络范朗内统一的单位数据传输费用：D。是建立一个连接所需的固定时间，D]是网络范围内统一的传输单位信息的时间。如果全网各站点可能不均，考虑费用和延迟的更为详细的特性，即每对站点貝有不同的系数，一次传输的传输费用TC和传输延迟TD可用函数表示为：TC(X)=Coij+XXC?jTD(X)=Doij+XXD,ij其中两个上标I和j分别表示这次传输的源和宿。这里假设是

8、匀质。7.1.3一种新的查询模型7.13.1数据库的概貌对于段其槪貌其可由下列信息组成：1.每个段&的元组数目■…基数,表示为Card(A)；2.每个属性A的大小(即字节数)，表示为Size(A)：一个段的大小，表示为Size(R),等于其属性大小之和,即&的记录长度。3.对于每个段&中的每个属性A,在Ri中出现的不同的值的数目，农示为Vai(A[RiJ).对于全局关系的概貌也同样山这三种信息组成。例如：Card(SUPPLY)=50000.SNUMPNUMDEPTNUMQUANSize67210Vai3

9、000100030500Card(DEPT)=30.DEPTNUMNAMEAREAMGRNUMSize21517Vai303030(a)全局关系SUPPLY和DEPT的概貌Card(SUPPLYl)=30000Site(SUPLLYi)=1SNUMPNUMDEPTNUMQUANSize10Vai1500100030500Card(DEPTi)=10Site(DEPTj)=2\DEPTNUMNAMEAREAMGRNUMSize21517val1()1()210(b)段SUPPLY］和DEPT］的概貌图7.

10、1概貌的例了7.13.2代数操作结果的概貌的估算令S表示在关系R上执行一个一元操作的结果，并令T表示对两个关系R和S进行一个二元操作的结果。一、对R进行的一个选择操作1.基数，对于毎个选择我们有一选择度P,最简单的选择是：属性=值(A=v),P可以估计为1/Val(A[R]),假定这些值是均匀分布的,并且值v出现在R中,则有:Card(S)=PXCard(R)例：从在座的100个学生中，任给个学号，列出其信息。这时P可以估计为