中间件异构数据库集成中基于半连接的查询优化算法

第３５卷　第２期　Ｖｏ１．３　５　Ｎｏ．２　西南师范大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｕｔｈｗｅｓｔ　Ｃｈｉｎａ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　２０１０年４月　Ａｐｒ．　２０１０　文章编号：１０００—５４７１（２０１０）０２—０１０７—０４　中间件异构数据库　算法　集成中基于半连接的查询优化　吴俊霖，　余建桥　西南大学计算机与信息科学学院，重庆４００７ｌ５　摘要：全局查询效率一直是中间件异构数据库集成中的热点和难点问题，由于目前异构数据库绝大多数是关系型数　据库，所以采用半连接方法优化连接操作，并在半连接图的基础上提出了多个站点的半连接执行方案优化算法，该　算法根据半连接图生成有向无序树，使多个半连接操作能够并行执行，盎分析能有效地提高全局查询效率．　关键词：半连接；半连接图；有向无序树；查询优化　文献标识码：Ａ　中图分类号：ＴＰ３１１　目前异构数据库集成方案中，中间件方式是使用较多的一种异构数据库集成方案，其目标是为用户提　供一个统一的查询接口，用户不必关心数据库的位置、数据库类型以及数据的存储格式，就像在本地查询　一样．中间件体系结构中的查询是将用户基于全局模式提交的查询动态分解为子查询到各异构数据库执　行．虽然中间件体系结构实现了信息共享，但其子查询语句的执行仍采用简单的顺序执行，且并未对子查　询语句进行优化，造成全局查询效率很低．如何提高全局查询效率一直是中间件异构数据库集成的热点和　难点问题…．考虑到目前绝大多数异构数据库是关系型数据库　，而在分布式查询中，连接操作是最常用　的且最费时间和空间的操作，而且多个关系的连接执行顺序优化也是整个查询处理的重点，直接影响全局　查询时间．传输费用是主要因素，而半连接操作从一个站点传送关系到另一个站点作连接之前，先除去了　与连接无关的数据，减少了作连接操作的关系数据量，从而减少了传输代价。。　．所以采用半连接方法，根　据半连接操作执行的优先级构造了半连接图，并在半连接图的基础上提出了一种多站点半连接执行方案的　优化算法，该算法根据半连接图构造有向无序树，使多个半连接能够并行执行．　１　中间件异构数据库与半连接　１．１　中间件异构数据库集成中的查询　在中间件的信息集成系统中，每个数据源都是独立自治的．其查询过程如下：用户提交的基于全局视　图的查询，由中间件的分解器分解为针对每个数据源的　子查询，然后按一定调度规则，顺序执行子查询，提交给　每个数据源执行，最后每个数据源将执行结果返回给中　用　全　子　户　全　局　查　询　局　查　询　分　船　查　ｒ、、　询　１，１　优　卜、、　询　查　调　度　间件的集成器．其查询调度过程如图１．　１．２半连接操作　化　半连接（ｓｅｍｉ—ｊｏｉｎ）操作　是由投影和连接操作导出　图１　查询调度图　收稿日期：２００９—０９—０４　作者简介：吴俊霖（１９８５一），女，四川达州人，硕士研究生，主要从事数据库技术研究　通讯作者：余建桥，教授，博士，研究生导师．　１０８　西南师范大学学报（自然科学版）　投稿网址ｈｔｔｐ：／／ｘｂｇｊｘｔ．ＳＷＵ．ｃｎ　第３５卷　的一种关系代数操作．假定有两个关系Ｒ和Ｓ，在属性Ｒ．ａ—Ｓ．ｂ上作半连接操作可表示为：　ＲＣｘ：　：ｂＳ—Ｒ∞　＿Ｉｌ（丌Ｉ］（Ｓ））或Ｓａｃ　Ｒ—Ｓ。。　＿Ｉｌ（丌　（Ｒ））　站点１的关系Ｒ与站点２的关系Ｓ在属性Ｒ．ａ和　Ｓ．ｂ上的连接操作用半连接来实现的具体执行过程共５　个步骤（图２）：　１）在站点２的关系Ｓ属性ｂ上做投影操作得到丌ｂ（Ｓ）；　图２半连接执行过程　２）把丌ｈ（Ｓ）送到站点１；　３）在站点１进行半连接，得到半连接结果Ｒ’一（Ｒｏｏａ＝ｂ（ｒｒｂ（Ｓ）））；　４）再把Ｒ’从站点１传送到站点２；　５）在站点２执行连接操作Ｒ’ｃｗ．．ＤＳ得到最终的结果．　由半连接的执行过程可知，采用半连接实现连接操作需要两次数据传输：连接属性投影结果Ｒ＇ｂ（ｓ）和　半连接结果Ｒ’．但在通常情况下，这两次数据传输的总量要远远小于整个Ｒ关系的数据量　，所以选择半　连接方法优化连接．　２半连接图及查询优化算法　基于中间件的异构数据库集成中的全局查询的查询优化主要目标是使网络数据传输总和更小，查询响　应时间更短．半连接能够有效地缩减关系的大小进而节省传输开销，因此半连接方法能够有效地优化中问　件体系中的查询效率．　２．１　半连接图及相关定义　由于半连接操作不具有对称性（Ｒｏｃ　ＳＪ－Ｓｏｃ　：　Ｒ），所以选择合适的半连接方案能使连接的代价最　小．半连接图就是多个连接进行时根据半连接最优执行方案所构成的反映关系间优先级的图．　下面给出关于半连接的相关定义：　（Ｒ，ｎ）：表示关系Ｒ中属性ａ不同值的个数；　Ｖｓ（Ｒ，ａ）：表示对Ｖ（Ｒ，ａ）的一个代价估算值（此代价估算值与Ｖ（Ｒ，Ｃｔ）成正比）；　定义１　对于多个要进行半连接的关系，用半连接图Ｇ（Ｖ，Ｅ）来表示．Ｇ（Ｖ，Ｅ）是一个有向无循环图，　其中：　是节点的集合，代表待连接的关系；Ｅ是有向边的集合，代表两个关系之间存在半连接　．　有向边指向方法：设关系Ｒ的属性ａ与关系Ｓ的属性ｂ之间存在连接，若满足Ｖｓ（Ｒ，ａ）≤Ｖｓ（Ｓ，６），　则该连接用有向边Ｅ（Ｒ，Ｓ）来表示，即Ｒ指向Ｓ，否则用有向边Ｅ（Ｓ，Ｒ）来表示，即Ｓ指向Ｒ．　例１　如果关系Ｒ１的属性“和关系Ｒ２的　属性ｂ之间存在连接并且满足　（Ｒ２，６）≤　（Ｒ１，ａ），关系Ｒ１的属性ｃ与关系Ｒ３的属性ｄ　ｇ）　之间存在连接并且满足Ｖｓ（Ｒ３，ｄ）≤Ｖｓ（Ｒ１，　ｃ），关系Ｒ１的属性　与关系Ｒ４的属性　之间　存在连接并且满足　（Ｒ１，　）≤Ｖｓ（Ｒ４，＿厂），关　系Ｒ２的属性ｇ和关系Ｒ４的属性ｈ之间存在连　接并且满足Ｖｓ（Ｒ２，ｇ）≤Ｖｓ（Ｒ４，ｈ），则可根据　定义１得到图３所示的半连接图：　定义２　如果关系Ｒ２半连接关系Ｒｌ（Ｒ２　图３半连接图　ｏｃＲ１），可以减少Ｒ２的代价，而关系Ｒ１半连　接关系Ｒ２，不能减少Ｒ１的代价，则称Ｒ１的优先级高于Ｒ２的优先级，并用Ｐ（Ｒ１，Ｒ２）表示．如果半连接　图中存在由关系Ｒ　到关系Ｒ的一条路径，则有Ｐ（Ｒ　，Ｒ）．半连接图中优先级关系存在传递性．即如果存　在优先级关系Ｐ（Ｒ１，Ｒ２）及Ｐ（Ｒ２，Ｒ３），可推出优先级关系Ｐ（Ｒ１，Ｒ３）．　根据前面的定义可知：半连接图３中Ｒ３到Ｒ１的有向边表示关系Ｒ３与关系Ｒ１存在半连接操作，且　关系Ｒ３的优先级高于关系Ｒ１的优先级，选择半连接执行方案为Ｒ３ｏｃＲ１．　第２期　２．２查询优化算法　吴俊霖，等：中间件异构数据库集成中基于半连接的查询优化算法　１０９　半连接图反映了执行半连接操作的关系之间的优先　级关系，这种优先级执行关系针对单个连接操作，减少　了网络通讯代价．而对于多个站点问连接的优化其基本　思想是：对多个半连接的执行顺序进行优化，在半连接　图的基础上进行整体优化，根据半连接图得到连接执行　方案图即有向无序图，以实现所有半连接的总执行时间　最小．　根据定义ｌ、定义２可知，图４表示１２个关系（分别　位于１２个站点）之间的１６个半连接的优先级关系图．因　为进行半连接的关系有优先级，所以要求出多个连接的　最优执行顺序需要根据半连接图求出其执行树．　由于半连接图是一个有向无环图，且有向边反映了　各个顶点之间的优先关系，可以认为半连接图是一个　图４半连接图　ＡＯＶ网（Ａｃｔｉｖｉｔｙ　Ｏｒｌ　Ｖｅｒｔｅｘ　ＮｅｔＷｏｒｋ）．对于ＡＯＶ网可以用拓扑排序来求得最优执行顺序．可以对拓扑　排序算法做一些改变就能形成一个求解半连接图中连接最优执行顺序的算法　．为了便于描述半连接图　的每条边，在有向边上加上一个唯一标示一条边（一个连接）的序号．注意这里必须保证半连接图中每个连　接都执行一次且只能执行一次．算法步骤如下：　１）在半连接图中找出所有没有前驱的顶点作为要构造的有向树的根节点．　２）依次访问从根节点出发的边，并将这些边和对应顶点添加到树中作为子节点．　３）分别从新加入的这些顶点出发，依次访问未曾访问过的边和对应的顶点并添加到树中作为子节点．　４）重复步骤３），使先被访问的顶点先于后被访问的顶点被访问，直至所有的有向边都被访问．　图５是根据图４的半连接图，采用此算法构造的两颗有向树：　图５　有向无序图　有向树组成的森林就是执行连接操作的顺序图．可以看到半连接图４中的１６条边，在图５中都可以执　行到，即１６个连接操作都能被执行到．以Ｒ１和Ｒ９为根节点的有向树是可以并行执行连接的方案图，如：　Ｒ１与Ｒ２的半连接操作可以和Ｒ１与Ｒ３的半连接操作并行执行，其所有连接总执行时间是这两颗有向树　中执行时问最长的一条路径的执行时间．　３算法性能分析　由于采用了半连接方法，并优化了半连接操作执行的优先级关系，降低了网络上的数据传输量，从而　节省了传输开销，降低了网络代价．影响算法性能的另一个主要因素是全局查询响应时间．假设图４中１６　个连接操作所用时问分别为ｔ　，￡　，ｔ。，…ｔ　ｔ　优化前执行所有连接操作所用时间Ｔ—ｔ　＋ｔｚ＋ｔ。＋…＋ｔ　ｓ＋ｔ　优化后９条路径并行执行连接操作　１１０　西南师范大学学报（自然科学版）　投稿网址ｈｔｔｐ：／／ｘｂｇｊｘｔ．ＳＷＵ．ｃｎ　第３５卷　所用时间分别为Ｔ１（Ｒ１－－Ｒ２－－Ｒ３）一ｔ２＋ｔ６，Ｔ２（Ｒ１一Ｒ３－－Ｒ５…Ｒ７）一ｔ３＋　８＋　９，Ｔ３（Ｒ１～Ｒ３－－Ｒ７）一　３＋ｔ７。Ｔ４（Ｒ１－－Ｒ３－－Ｒ８）一　３＋ｔｌ０，７＂５（Ｒ１　Ｒ４一一Ｒ５）一ｔｌ斗，￡５，Ｔ６（Ｒ１…Ｒ１２）一ｔ４，Ｔ７（Ｒ９…Ｒ１０　Ｒ１２）一ｔｌ２＋　１４，丁８（Ｒ９一一Ｒ１１一Ｒ６一Ｒ８）一ｔｌ３＋　１５＋　１６，丁９（Ｒ９一尺１２）－二ｔｌ１．　由于９条路径并行执行，所以执行所有连接所用时间为其中执行时间最长的一条路径的执行时间．由　于　＜　（　一１，２，…，９），所以，优化后的执行时问大大小于优化前的执行时间．　参考文献：　［１］卓国锋，罗　军．基于Ｍｅｄｉａｔｏｒ／Ｗｒａｐｐｅｒ信息集成的查询优化研究［Ｊ］．计算机工程与应用，２００７，４３（１２）：　１５９一ｌ６３．　［２］代宇，程瑶，刘　莉．数字化校园网格信息集成方案研究［Ｊ］．重庆邮电大学学报（自然科学版），２０Ｏ８，增刊：　７Ｏ一７２．　Ｅ３］Ｐｅｎｔａｒｉｓ　Ｆ，Ｉｏａｎｎｉｄｉｓ　Ｙ．Ｑｕｅｒｙ　Ｏｐｔｉｎ，ｉｚａｔｉｏｎ　ｉｎ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｎｅｔｗｏｒｋｓ　ｏｆ　Ａｕｔｏｎｏｍｏｕｓ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ　ＥＪ］．ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｄａｔａｂａｓｅ　Ｓｙｓｔｅｍｓ，２００６，３１（２）：５３７—５８３．　［４］　陈一栋．分布式数据库查询优化算法研究与实现ＬＤ］．长沙：长沙理工大学，２００８．　Ｅｓ］Ｂａｍｈａ　Ｍ．Ａｎ　Ｅｆｆｉｃｉｅｎｔ　Ｅｑｕｉ—ｓｅｍｉ　ｊｏｉｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ａｒｃｈｉｔｅｃｔｕｒｅｓ　ＥＪ］．Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｓｃｉｅｎｃｅ，２００５，　３５１５（２）：７５５—７６３．　Ｅ６］李慧芳．基于ＸＭＩ　和中间件的异构数据库集成研究［Ｄ］．长沙：长沙理丁大学，２００８．　［７］王意沽，王勇军，卢锡城．基于半连接的并行查询处理算法的研究［Ｊ］．软件学报，２００１，１２（２）：２１９—２２４．　［８］许新华，谌颃，李春．并行数据库的语义查询优化研究：基于Ａｇｅｎｔ［Ｊ］．西南师范大学学报（自然科学版），２００７，　３２（４）：７７～８１．　Ｑｕｅｒｙ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｍｅｄｉａｔｏｒ　Ｈｅｔｅｒ０ｇｅｎｅ０ｕｓ　Ｄａｔａｂａｓｅ　Ｉｎｔｅｇｒａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｓｅｍｉ－ｊ　ｏｉｎ　ＷＵ　Ｊｕｎ－１ｉｎ，　ＹＵ　Ｊｉａｎ—ｑｉａｏ　Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａ　ｔｉｏｎ　Ｓｃｉｅｎｃｅ，　Ｓｏｕｔｈｗｅｓｔ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ　４００７　１５，Ｃｈｉｎａ　Ａｂｓｔｒａｃｔ：Ｇｌｏｂａｌ　ｑｕｅｒｙ　ｅｆｆｉｃｉｅｎｃｙ　ｉｓ　ｔｈｅ　ｈｏｔ　ａｎｄ　ｄｉｆｆｉｃｕｌｔ　ｐｒｏｂｌｅｍ　ｏｎ　ｍｅｄｉａｔｏｒ　ｈｅｔｅｒ０ｇｅｎｅｏｕｓ　ｄａｔａｂａｓｅ　ｉｎｔｅ—　ｇｒａｔｉｏｎ　ｃｏｎｔｉｎｕｏｕｓｌｙ．Ｓｉｎｃｅ　ｔｈｅ　ｖａｓｔ　ｍａｊｏｒｉｔｙ　ｏｆ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｈｅｔｅｒｏｇｅｎｅｏｕｓ　ｄａｔａｂａｓｅ　ｉｓ　ｒｅｌａｔｉｏｎａｌ　ｄａｔａｂａｓｅ，　ｔｈｅ　ａｕｔｈｏｒｓ　ｏｐｔｉｍｉｚｅ　ｊｏｉｎ　ｑｕｅｒｙ　ｂａｓｅｄ　ｏｎ　ｓｅｍｉ—ｊｏｉｎ，ａｎｄ　ｐｕｔ　ｆｏｒｗｏｒｄ　ｑｕｅｒｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｅｍｉ—　ｊｉｏｎ　ｅｘｅｃｕｔｉｏｎ　ｐｌａｎ　ｏｎ　ｓｅｖｅｒａｌ　ｄａｔａｂａｓｅｓ　ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｓｅｍｉ—ｊｉｏｎ　ｇｒａｐｈ．Ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｐｒｏｄｕｃｅｓ　ｄｉｒｅｃｔｅｄ　ａｎｄ　ｄｉｓｏｒｄｅｒｅｄ　ｔｒｅｅ　ｂａｓｅｄ　ｏｎ　ｓｅｍｉ—ｊｏｉｎ　ｇｒａｐｈ，ＳＯ　ｔｈａｔ　ｎｕｍｂｅｒ　ｏｆ　ｓｅｍｉ—ｊｏｉｎ　ｏｐｅｒａｔｉｏｎｓ　ｃａｎ　ｂｅ　ｅｘｅｃｕｔｅｄ　ｉｎ　ｐａｒａｌｌｅ１．Ａｆｔｅｒ　ａｎａｌｙｓｉｓ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｉｍｐｒｏｖｅ　ｇｌｏｂａｌ　ｑｕｅｒｙ　ｅｆｆｉｃｉｅｎｃｙ　ｇｒｅａｔｅｌｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｓｅｍｉ—ｊｏｉｎ；ｓｅｍｉ—ｊｏｉｎ　ｇｒａｐｈ；ｄｉｒｅｃｔｅｄ　ａｎｄ　ｄｉｓｏｒｄｅｒｅｄ　ｔｒｅｅ；ｑｕｅｒｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　责任编辑张构