基于遗传算法的分布式数据库查询优化-研究

《基于遗传算法的分布式数据库查询优化-研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国石油大学或其它教育机掏的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。签名：．1诉4月砑日关于论文使用授权的说明本人完全了解中国石油大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密论

2、文在解密后应遵守此规定)导师签名：附雌4月"-7日弘矿缸#々月；p日中国行油大学(华东)硕士论文第1章前言1．1课题的提出、研究目的及意义目前，分布式数据库已得到广泛应用，它在信息集成及查'自j等方面有着重要作用。查询作为数据库应用的核心功能，在分布式环境中更具有复杂性，如何在分布式特性上进行优化查询，是衡量分布式数据库系统性能的关键问题之一【Ⅲ。自上世纪七十年代，研究者在分布式查询处理方面一直进行“探索”，寻找好之又好的算法，找到了一定的规律，遗憾的是，这些经典理论要么局限于某方面Is-7]，要么过于复杂而不适合应用‘堋。另外，研究发现，分布式数据库中数据分

3、布和查询优化均是NP完全问题，至今都没有得到彻底解决【10-121。在这个“信息爆炸”时代，分布式数据库的应用日益广泛，解决分布式数据库的查询优化问题显得日益重要。大量研究发现，有效解决分布式数据库查询优化问题，需要保证问题求解搜索空间，尽量包含具有最低代价的查询执行计划，查询代价估计是精确的，并且搜索算法是有效的【1t6'7，9’131。对分布式数据库查询优化的搜索空间分析，并对相应的查询代价模型研究，是解决查询优化的问题关键。高效的搜索算法是查询优化实现的重要手段。因此，分布式数据库查询优化的代价估计模型和高效搜索算法一直是研究的热点【6-151。本课题的

4、研究是从上述两个主要方面入手。一方面是，对查询优化的搜索空间进行研究，提出相应的代价评估模型；另一方面是，应用遗传算法解决复杂组合优化问题的独特优势和特点[14-18】，构造了一种具有更好寻优性能优化组合遗传算法，实现了基于此模型的分布式数据库查询优化。中国石油大学(华东)硕士论文第1章前言1．2国内外研究现状物理上分布、逻辑上集中是分布式数据库的根本特点，数据存储的冗余和站点自治是提高系统可靠性的重要手段。分布式查询和集中式查询最大区别在于：分布式查询需要在不同站点之间进行数据传输。因此，一个完善的分御式数据库查询优化求解空间应包括：关系副本的选择、关系多连

5、接次序、操作站点的选择、数据传输和局部处理代价等”9-221。站点间的通信开销成为分布式数据库查询必须考虑的问题，对于以通信代价最小为目标的代价模型，国内外对其进行了广泛研究№13,23斟】。另外，对于分布式数据库查询优化中，多连接的查询次序和数据传输等问题，也有深入研究‘20捌。但是，在关系副本的选择和操作站点选择等方面，研究相对较少，其主要原因是，在数据存储冗余较小、网络站点性能差异不明显的情况下，关系副本选择、操作站点选择及局部处理代价，对分布式数据库查询执行代价影响较小，数据传输和多连接次序决定查询执行速度【2“。在分布式数据库查询代价模型的研究方面，

6、[4，5，6，121等提出了多连接次序的优化和操作站点的选择的启发式算法，但没有考虑涉及到关系的多副本选择。[25】虽然对关系副本选择优化和连接操作站点的确定进行了深入研究，但它是在假定多连接次序不变的前提下进行的。国内方面，曹阳、钟武等研究了多连接表达式的并行查询优化，对关系副本、操作站点选择等方面没有涉及【7，1啦!1,14,15,26]。然而，随着“海量信息”出现，数据冗余存储是不可回避的问题，数据局部处理的差异也不可像以前那样忽略不计[1．20,3”。因此，对于分布式数据库的查询，评估查询执行代价的模型应该更加完善。另一方面，查询优化算法是实现查询优化

7、的手段，同样得到了深入研究[xg-2zl。优化算法的研究大多数是在关系代数基础上进行的，如：基于图2中国打油大学(华东)硕士论文第l章前言论、动态规划及线性规则等常规优化策略。具有代表性的研究有：E．Wong首先针对SDD．1系统的情况提出了减少通信丌销的算法【271；P．A．Bemstein等对Wong的算法作了进一步优化，提出了半连接和缩减器的概念【281；【291提出了在SystemR中优化器的实现方法等。近几年来，遗传算法在分布式数据库查询优化的应用得到了国内外研究者的关注。[14，151提出了基于遗传算法的异构分布式数据库查询优化算法，【10，l1,

8、26]等应用遗传算法实现分布式数据库中