分布式查询处理(数据库)

时间：2022-12-20 06:30:01 | 来源：信息时代

时间：2022-12-20 06:30:01 来源：信息时代

    分布式查询处理 : 采用全局查询处理和局部查询处理来实现分布式数据库查询的一种技术。通常,用户或应用只能看到全局关系组成的全局数据库,且只能在全局关系上完成查询,并要采用高层数据操纵语言来表达全局查询。之后,由系统将其转换成内部表示,并将全局查询转换为片段查询。在查询执行过程中,最终涉及的是具体场地上的物理关系的查询。可见,分布式查询处理主要完成将高层的查询语言(典型的为关系验算)正确地转换为语义等价的内部语言(典型的为关系代数),并将全局查询转换为片段查询。其中,查询优化具有重要作用,因为许多等价的内部表示语言的执行代价差别很大。因此,为提高查询效率,在查询处理过程中需要进行优化处理。
查询优化就是确定出一种执行代价最小的查询执行策略或寻找相对较优的操作执行步骤,以提高系统执行效率。在分布式数据库系统中,影响查询处理效率的因素主要有: 网络传输代价、局部I/O代价及CPU处理代价等。分布式查询优化的目标就是指局部执行代价和网络传输代价的和最小。局部执行代价主要指输入/输出次数(I/O代价)及CPU处理代价。网络传输代价主要指传输启动代价和数据传输代价。通常,查询优化包括全局优化和局部优化两部分。这里主要介绍全局查询优化,主要包括全局优化和片段优化。
1.全局优化
全局优化是将用户请求构成的查询树进行等价变换,得到一种“最好”的操作顺序。等价变换的基本思想是先进行中间结果变小的运算。可见,全局优化就是尽量先进行一元运算,使中间结果变小,以减少后续的二元运算代价,从而将一元运算推向查询树的底部。变换的通用准则为:
准则1: 尽可能将一元运算移到查询树的底部(树叶部分),使之优先执行一元运算。
准则2: 利用一元运算的重复律,缩减每一关系,以减少关系尺寸,降低网络传输量和I/O大小。
假设一供应关系数据库中有供应者SUPPLIER{SNO,SNAME,AREA}和供应SUPPLY{SNO,PNO,QTY}两关系,SNO、SNAME和AREA分别为供应者编号、供应者姓名和供应者所属地域。PNO和QTY分别为零件号和数量。
若有查询要求: “找出地域在 ‘北方’ 且供应100号零件的供应商的信息”,则SQL查询语句为:
SELECT SNO,
SNAME FROM SUPPLIER,
SUPPLY WHERE AREA="北方"
AND PNO=100
AND SUPPLIER.SNO=SUPPLY.SNO
等价的关系表达式为:
Q₁:∏_SNO,SNAMEσ_{AREA="北方"and PNO=100}(SUPPLIER⋈SUPPLY)。
Q₁的查询树如图1(a)所示。
在查询树Q₁的基础上进行全局优化。根据分配律,将一元运算向下移,得到全局优化后的查询树Q₂,如图1(b)所示。在全局关系上的查询,称为全局查询。如图1中的Q₁和Q₂。

图1 查询树

查询的处理过程是从全局关系到片段关系,最后再到实际操作的副本关系。为此,需要利用全局关系与其片段关系的等价关系,将全局查询中的全局关系替换为对片段关系的查询,变换后的查询称为片段查询。对应于片段查询的查询树,称为片段查询树。
基于全局查询与片段查询的等价关系,生成片段查询树,具体生成步骤: ①将分片树的h(水平)结点转换为查询树的∪(并集)结点;②将分片树的v(垂直)结点转换为查询树的⋈(连接)结点; ③用替换后的分片树代替全局查询树中的全局关系,得到片段查询树。
假设SUPPLIER和SUPPLY的分片定义为:
S₁＝σ_{AREA="北方"}(SUPPLIER);
S₂＝σ_{AREA="南方"}(SUPPLIER);
SUPPLY₁＝σ_{AREA="北方"}(SUPPLY);
SUPPLY₂＝σ_{AREA="南方"}(SUPPLY)。
则分片树和转换表示如图2所示。

图2 分片树与转换

在Q₂基础上,用SUPPLIER分片树替换后的∪结点替换查询树Q₂的全局关系SUPPLIER,用SUPPLY分片树替换后的∪结点替换查询树Q₂的全局关系SUPPLY,即得到转换后的片段查询树为Q₃(见图3)。

图3 Q₃查询树

2. 片段优化
片段优化使全局优化树转换的片段查询树进一步优化,得到片段优化树。这里需了解两个基本概念——限定条件和属性表。限定条件指每个水平片段中数据元组所满足的分片条件,也称水平分片的取值范围。属性表指每个垂直片段中元组所包含的分片属性,也称垂直分片的属性范围。
例如,存在雇员关系EMP{ENO,ENAME,BIRTH,SALARY,DNO},其分片定义:
E₁＝∏_{ENO,ENAME,BIRTH}(EMP);
E₂＝∏_{ENO,SALARY,DNO}(EMP);
E₂₁＝σ_DNO=201(E₂₎;
E₂₂＝σ_DNO=202(E₂₎;
E₂₃＝σ_{DNO201 AND DNO202}(E₂₎。
则其分片树如图4所示。

图4 EMP分片树

针对E₂₁定义,其属性表为ENO,SALARY,DNO,限定条件为DNO=201。
片段查询优化的目的是化简片段查询树,具体思想是依据水平分片的限定条件,去除空关系,如Q1中AREA="南方"的关系;依据属性表,去除无用的中间关系,即无查询所需属性的关系。片段查询优化规则如下:
准则1: 对于一元运算,根据一元运算的重复律,将叶子结点之前的选择运算作用于片段,如果不满足片段的限定条件,则置为空关系。
准则2: 对于连接运算的树,若连接条件不满足,则将其置为空关系。
准则3:在查询树中,将连接运算(⋈)下移到并运算(∪)之前执行。
准则4: 消去不影响查询运算的垂直片段。
例如,以片段查询树Q₃为基础,依据片段查询优化准则进行化简的步骤:
(1)根据片段查询优化准则1,将叶子结点之前的选择运算作用于片段,得到Q₄(见图5)。

图5 Q₄片段查询树

(2)若存在如下分片定义:
S₁＝σ_{AREA="北方"}(SUPPLIER);
S₂＝σ_{AREA="南方"}(SUPPLIER);
SUPPLY₁＝σ_{AREA="北方"}(SUPPLY);
SUPPLY₂＝σ_{AREA="南方"}(SUPPLY)。
则Q₄中的虚线部分为空关系。按限定条件化简,去除空关系,得到Q₅查询树(见图6)。

图6 Q₅查询树

(3)根据准则3,将连接运算(⋈)下移到并运算(∪)之前,得到Q₆(见图7)。

图7 Q₆查询树

由于:
S₁＝σ_{AREA="北方"}(SUPPLIER);
S₂＝σ_{AREA="南方"}(SUPPLIER);
SUPPLY₁＝σ_{AREA="北方"}(SUPPLY);
SUPPLY₂＝σ_{AREA="南方"}(SUPPLY)。
因此,Q₆查询树中虚线部分满足准则2,即其连接条件不满足,则将其置为空关系。将虚线部分从查询树中去掉,得到Q₇(见图8)。Q₇为化简后的最终的优化查询。

图8 Q₇优化后的查询树