第五讲分布查询的存取优化.pptVIP

* * * * * * * * * ?传输代价的比较 假设： 关系R和S分别在不同的场地上，C0为启动代价，C1为单位传输代价。全连接代价： 设：在S所在的场地上执行，则传输关系R实现R∞S的代价 C=C0+C1*(Length(R)* Card(R) ) = C0+C1*Size(R) 5.3.2 半连接优化原理 传输代价的比较 C∝= CS′+ CR′ = C0+C1*(Length(S′)* Card(S′))+ C0+C1*(Length(R′)* Card(R′)) =2 C0+C1*(Length(S′)* Card(S′)+ Length(R′)* Card(R′)) =2 C0+C1*(Size(S′)+ Size(R′)) 分析：如果有：C∞≥C∝ 则：C0+C1*Size(R)≥2 C0+C1*(Size(S′)+ Size(R′))  C0/C1+ Size(S′)+ Size(R′)≤Size(R) 5.3.2 半连接优化原理 SDD-1是美国采用ARPANET远程网建立的世界上第一个分布式数据库管理系统。该系统为人们进一步理解和解决分布式数据库中的一些问题做出了很大贡献。SDD-1的查询优化就是对片段数据使用选择、投影、半联接操作来最大限度地缩减。SDD-1具体算法由两部分组成：一是根据评估缩减算法确定一个收益最大的执行策略，但此执行策略的效率可能不一定高；二是进行后优化处理，将基本算法得到的解进行修正，以得到更合理的执行策略。 SDD-1系统优化技术 SDD-1系统优化技术 优化模型 在SDD-1算法中，分别使用连接图（join graph）和概要图来描述查询中的条件限制和在关系上的特征参数。 例如： SELECT S.SNAME FROM SUPPLIER S, PARTS P, SUPPLY SP WHERE S.S#=SP.S# AND SP.P#=P.P# AND S.CITY=”Shanghai” 连接图 图的节点表示关系，边表示连接运算，边上标号表示连接条件，节点上标号表示关系名和场地。如下图表示形式。 S SP P S.S#=SP.S# SP.P#=P.P# SDD-1系统优化技术 优化模型 关系的概要图 主要用于表示一个关系上的特征参数，其中数据包括关系中元组数量Card(R)、每个关系属性的长度Length(A)和属性不同值的数量Val(R,A)。 如：关系SUPPLY{S#, P# , QUANTITY }，Card(R)=30000，则关系SUPPLY的概要图表示为： Card(SUPPLY)=30000 S# P# QUANTITY Length 6 4 10 Val 1800 1000 500 SDD-1系统优化技术 查询代价与收益估计 SDD-1算法的基本优化思想： 联接图中的每个关系都用一元运算进行局部缩减； 对受益半联接集合中的所有半联接进行操作，逐个找出最优的操作； 选择一个要求最少传输代价的场地，执行操作。 受益半连接集：对于一个给定的半连接集合，所有利益超过代价的半联接操作的集合，称为受益半联接集，记为P。 比传输R减少了（1－?）倍的数据 SDD-1系统优化技术 查询代价与收益估计（利益代价模型） 半连接的代价：传输关系在连接属性上的投影关系的代价。 假设关系R和S在不同场地上，连接属性为A，使用半连接算法将增加传输Size (?A(S))的通信代价，则半连接R?AS的代价计算如下： Cost(R?AS) = C0+C1*Val(S, A)* Length(S.A) 其中C0是通信启动代价，C1是传输单位数据的代价。 半连接的利益：半连接的利益是因半连接而节省了不需要传输的元组所对应的传输代价。 对于半连接R?AS，其利益可以看作是由原来传输关系R减少到传输R’的差值，计算公式如下： Benefit(R?AS)=C0+ C1*(1-ρ)*Card(R)* Length(R) 其中，ρ为连接的选择度，Length(R)为关系R的一个元组的长度。 SDD-1系统优化技术 查询代价与收益估计（利益代价模型） 代价： S’?R 获益： R’?S R S S1 S2 R.A=S.A 直接连接 （1）Size (R) 半连接 （1）Size (?A(S)) R’=R?S’ （2）Size (R’) R?S=R’?S 基本优化算法 输入信息：查询联接图及关系概要图 输出信息：半联接执行序列集合P′及最后的执行场地 Begin /*初始化*/ 包含所有可执行的一元操作和局部操作，构成执行策略集P′； 计算所有的半联接的代价和利益，构成受益半