（计算机系统结构专业论文）嵌入式分布数据库的查询优化算法研究.pdf

山东大学硕士学位论文 摘要 海洋信息服务在维护海洋权益、开发海洋资源、预警海洋灾害、 保护海洋环境等方面都有着重大意义。而查询优化作为提升数据库处 理性能的关键技术，对于有效地实现海洋信息领域的数据资料利用和 实时信息服务有至关重要的影响。本文以海洋环境在线监测及灾害智 能预警系统的研制为基础，深入研究了适应嵌入式分布数据库特性的 查询优化算法的设计和实现。 文中首先给出了海洋环境在线监测及灾害智能预警系统的整体架 构及功能划分，并重点介绍了基于嵌入式技术的海洋监测数据管理子 系统的架构设计。考虑到系统中数据处理对嵌入式环境下查询处理性 能的需求，本文在全面分析嵌入式实时数据库系统特性对查询优化的 影响以及传统查询优化方法特点的基础上，对贪婪算法和随机搜索算 法进行了有效的结合，将贪婪算法快速求解的特点引入到随机搜索过 程中，使算法能较快地收敛，并通过迭代采样拓展了搜索空间，有利 于算法跳出局部极小。并且，算法可以通过设置终止条件来控制优化 本身的时间长短，从而能在满足系统实时要求的前提下更好地适应不 同类型事务的需要。模拟实验表明，与传统查询优化算法相比，本文 的改进算法无论从运行时间、空间复杂性和计划质量方面都具有一定 优势。针对海洋监测数据管理系统分布式体系结构下的复杂多连接查 询，本文系统地介绍了粒子群优化算法的原理和特点，并分析了用粒 子群优化算法求解多连接查询优化问题的有效性，算法以左深树为搜 索空间，采用有序串编码并改进了基本粒子群优化算法的速度位置公 式，将其应用于海洋监测数据的测试实验中，取得了良好的效果。高 效的数据传输同样也是影响海洋信息服务水平的重要因素，本文结合 c l i e n t s e r v e r 通信模型和x m l 技术，提出了一种实时海洋数据传输的 实现方案，采用基于x m l 的海洋数据交换规范，有效地解决了异构平 台、不同数据格式之间的数据交换问题。 关键词：嵌入式数据库；多连接查询；查询优化；粒子群优化算法 山东大学硕士学位论文 a b s t r a c t m a r i n ei n f o r m a t i o ns e r v i c ei so fg r e a ts i g n i f i c a n c eo ns a f e g u a r d i n g m a r i n er i g h t sa n di n t e r e s t s ，e x p l o i t i n gm a r i n er e s o u r c e s ，w a r n i n gm a r i n e d i s a s t e r sa n dp r o t e c t i n gm a r i n ee n v i r o n m e n t q u e r yo p t i m i z a t i o n ，a sa k e yt e c h n o l o g yo ni m p r o v i n gt h ed a t a b a s ep r o c e s s i n gp e r f o r m a n c e ，h a sa n i m p o r t a n ti m p a c to nt h ee f f e c t i v ei m p l e m e n t a t i o no fd a t au t i l i z a t i o na n d r e a l t i m ei n f o r m a t i o ns e r v i c ei nt h ef i e l do fm a r i n ei n f o r m a t i o n t h i s t h e s i si sb a s eo nt h er e s e a r c ho ft h em a r i n ee n v i r o n m e n to n l i n e m o n i t o r i n ga n dm a r i n ed i s a s t e ri n t e l l i g e n tf o r e c a s t i n gs y s t e m ，a n ds t u d y d e e p l yt h ed e s i g na n di m p l e m e n t a t i o no ft h eq u e r yo p t i m i z a t i o na l g o r i t h m s u i t a b l ef o rt h ee m b e d d e dd i s t r i b u t e dd a t a b a s e ， t h i st h e s i s f i r s t g i v e s t h ew h o l ea r c h i t e c t u r ea n df u n c t i o n c l a s s i f i c a t i o no ft h em a r i n ee n v i r o n m e n to n l i n em o n i t o r i n ga n dm a r i n e d i s a s t e r i n t e l l i g e n tf o r e c a s t i n gs y s t e m ，a n df o c u s e so n t h ef r a m e w o r k d e s i g no ft h em a r i n em o n i t o r i n gd a t am a n a g e m e n ts u b s y s t e mb a s e do n e m b e d d e dt e c h n o l o g y i nv i e wo ft h er e q u i r e m e n to fq u e r yp r o c e s s i n g p e r f o r m a n c eo ne m b e d d e de n v i r o n m e n ti nt h es y s t e m ，w ea n a l y z ei n d e t a i lt h ei m p a c to ft h ec h a r a c t e r i s t i c so fe m b e d d e dr e a l t i m ed a t a b a s e s y s t e mo nq u e r yo p t i m i z a t i o na n dt h ec h a r a c t e r i s t i c so ft r a d i t i o n a lq u e r y o p t i m i z a t i o nm e t h o d s b a s e do nt h i sa n a l y s i s w ec o m b i n et h eg r e e d y a l g o r i t h ma n dr a n d o ms e a r c ha l g o r i t h m se f f e c t i v e l ya n di n t r o d u c et h ef a s t s o l v i n gc h a r a c t e r i s t i c so ft h eg r e e d ya l g o r i t h mt o t h er a n d o ms e a r c h p r o c e s s t h i sc a nm a k et h ea l g o r i t h m sc o n v e r g er a p i d l ya n de x t e n dt h e s e a r c hs p a c et h r o u g hi t e r a t i v es a m p l i n g ，a n dh e l pt h ea l g o r i t h m st ob eo u t o fl o c a lm i n i m u m m o r e o v e r ，t h ea l g o r i t h m sc a nc o n t r o lo p t i m i z a t i o n t i m eb ys e t t i n gt e r m i n a t i o nc o n d i t i o n s ，w h i c hn o to n l yf u l f i lt h er e a l t i m e r e q u i r e m e n t b u ta l s o b e t t e rm e e tt h en e e do fd i f f e r e n t t y p e s o f t r a n s a c t i o n s ，s i m u l a t i o nr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h m sh a v e m o r ea d v a n t a g e st h a nt r a d i t i o n a lo p t i m i z a t i o nm e t h o d si nt e r mo fr u n n i n g t i m e ，s p a c ec o m p l e x i t ya n dp l a n n i n gq u a l i t yc o m p a r e dw i t ht r a d i t i o n a l i i 山东大学硕士学位论文 o p t i m i z a t i o na l g o r i t h m s i nt e r mo ft h ec o m p l i c a t e dm u l t i - j o i nq u e r yi n t h ed i s t r i b u t e da r c h i t e c t u r eo fm a r i n e m o n i t o r i n g d a t am a n a g e m e n t s y s t e m ，t h i s t h e s i si n t r o d u c e s s y s t e m i c a l l y t h e p r i n c i p l e s a n d c h a r a c t e r i s t i c so fp a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a l g o r i t h m a n d a n a l y z e st h ee f f e c t i v e n e s so fa p p l y i n gp s o t os o l v et h em u l t i - jo i nq u e r y o p t i m i z a t i o np r o b l e m t h ea l g o r i t h mt a k e st h el e f t - d e e pt r e ea ss e a r c h s p a c ea n da d o p t so r d e r e ds t r i n ge n c o d i n gt oi m p r o v et h eb a s i cf o r m u l a si n p s oa l g o r i t h m w ea p p l yt h i sa l g o r i t h mt ot h em a r i n em o n i t o r i n gd a t a e x p e r i m e n t sa n dg e tg o o dr e s u l t s e f f i c i e n td a t at r a n s m i s s i o ni sa l s oa n i m p o r t a n tf a c t o ri nm a r i n ei n f o r m a t i o ns e r v i c e t h i st h e s i sc o m b i n e st h e c l i e n t s e r v e rc o m m u n i c a t i o nm o d e la n dx m l t e c h n o l o g y ，a n dp r e s e n t sa n i m p l e m e n t a t i o ns c h e m ef o rr e a l - t i m em a r i n ed a t at r a n s m i s s i o n t h i s t h e s i sa d o p t sx m l b a s e dm a r i n ed a t ae x c h a n g es t a n d a r d ，w h i c hc a ns o l v e e f f e c t i v e l y t h ed a t ae x c h a n g eb e t w e e nd i f f e r e n td a t af o r m a t si nt h e h e t e r o g e n e o u sp l a t f o r m s k e y w o r d s ：e m b e d d e dd a t a b a s e ：m u i t i j o inq u e r y ：q u e r yo p t i m iz a t i o n p a r t i0 i e8 w ar mo p t i m iz a t i o na i g o r i t h m m 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：蹲日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：- 二晕鸳驽一导师签名：巡日期：竺丝 山东大学硕士学位论文 1 1 论文的选题背景 1 1 1 研究背景 第1 章绪论 本课题的研究以山东省科学技术发展计划重点项目“海洋环境在 线监测及灾害智能预警系统的研制( 2 0 0 4 g g 2 2 0 5 1 0 8 ) ”为背景。 海洋是人类社会可持续发展的宝贵财富和最后空间，是能源、矿 物、食物和淡水等资源的战略基地。我国是一个海洋大国，海岸线长 达1 8 ，0 0 0 公里，管辖的海域面积近3 0 0 万平方公里，合理开发海洋 资源，顺利发展海洋经济，对我国经济可持续发展战略的实施有着举 足轻重的作用。然而海洋的存在也给我们带来一定的灾害威胁和经济 损失。以赤潮为例，随着海洋污染的日益加重，我国沿海赤潮频繁发 生，并且规模越来越大，持续时间越来越长，从1 9 9 0 年到1 9 9 4 年，5 年里发生赤潮1 5 3 次，1 9 9 8 年全年赤潮灾害导致的经济损失超过7 亿 元，z j 。海洋灾害对沿海地区社会经济发展和人民生命财产安全已造成 了巨大的危害，进而对国家的经济建设产生不良影响。因此，迫切需 要研制有效的海洋环境在线监测及灾害智能预警系统，以满足海洋资 源开发、利用和社会、经济发展的需求。 目前，海洋环境的监测与预警已经引起了我国政府和公众的高度 重视，将其列为国家8 6 3 计划的一个主题，在“九五”、“十五”期 间持续加大研究的投入力度，旨在提高对海洋环境的监测和保护能力， 并支持海洋资源开发和海上国际建设【3 1 。一些8 0 、9 0 年代兴起的计算 机、通信等技术日趋成熟，其中不少理论成果已在实践中大量应用， 这为研制新型、高性能的海洋环境在线监测系统提供了有力的技术支 持与保障。在此背景下，研制海洋环境在线监测与预警系统完全符合 国家海洋开发战略部署和社会发展的迫切需要。而海洋监测数据管理 作为整个系统的核心，其相关技术的研究是本文探讨的主要内容。 山东大学硕士学位论文 1 1 2 问题的提出 随着计算机监控、网络通讯技术的飞速发展以及嵌入式i n t e r n e t 技术的日趋成熟并应用于海洋监测领域，各种海洋监测设备可以直接 接入网络，成为实时网络控制中的节点。在这种形式下，海洋环境监 测系统逐渐向实时、密集、立体、长期、系统的方向发展。 本课题所研究的海洋环境在线监测及灾害智能预警系统是由嵌入 式监测设备和数据中心、数据通信网络共同构成的立体监测网络体系。 海洋数据管理和信息服务是系统的核心功能，在维护海洋权益、开发 海洋资源、预警海洋灾害、保护海洋环境等方面都有着重大意义。而 查询优化作为提升数据库处理性能的关键技术，对于有效地实现数据 资料利用和实时信息发布有至关重要的影响，成为系统开发中迫切需 要解决的问题。此外，在该监测网络体系下，数据库大多建立在不同 操作系统、数据库平台之上，分布式、异构的特点使得系统中的数据 传输和资源共享也非常不便。 针对上述问题，本文作为“海洋环境在线监测及灾害智能预警系 统”的子课题，重点探讨了系统中的数据管理问题，对嵌入式实时数 据库以及分布式环境下的查询优化算法进行了深入研究，并提出了一 种实时海洋数据传输系统的设计方案。 1 2 国内外研究现状 查询优化问题一直是数据库领域的一个研究重点，尽管很多研究者 做了大量的工作，但与关系数据库技术在数据处理中的成功应用不相 称的是，多连接查询优化一直是关系数据库系统中的一个没有很好解 决的问题。迄今为止，所提出的算法大都属于以下三种类型之一或是 这几类基本算法的组合。 ( 1 ) 穷尽式搜索。此类算法如动态编程( d y n a m i cp r o g r a m m i n g ， d p ) 算法可以保证根据优化代价模型找到最好的查询执行计划。但由于 多连接查询优化问题是一个组合优化问题，每一个查询对应的执行计 2 山东大学硕士学位论文 划空间随着关系个数的增加而成指数级增长，传统的穷尽( 精确) 优 化算法的时间复杂性和空间复杂性也随之成指数级增长，因此无法对 规模太大的查询进行优化【”。 ( 2 )启发式。此类算法具有多项式级的时间和空间复杂度，但 其生成计划的代价往往比穷尽式优化算法高数量级。这类算法的典型 代表有贪婪算法【5 】等。 ( 3 ) 随机算法。此类算法最大的优点是只需常数级的空间开销， 但其运行时间是不好预计的 6 1 。这类算法中最有名的是两段优化 ( t w o - p h a s eo p t i m i z a t i o n ，2 p o ) 7 1 ，它是迭代改进( i t e r a t i v ei m p r o v e m e n t ， i i ) 和模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 算法的综合应用。 1 3 论文的主要工作 本文共分六章，各章的主要内容如下： ( 1 ) 第一章介绍了选题背景，研究意义，关键技术的研究现状以 及论文的主要工作。 ( 2 ) 第二章提出了整个海洋环境在线监测与灾害智能预警系统的 整体架构，并重点介绍了基于嵌入式技术的海洋监测数据管理子系 统的架构设计。 ( 3 ) 第三章在详细介绍多连接查询优化问题的基础上，针对嵌入 式实时数据库系统特性以及传统查询优化方法的不足，对贪婪算法 和随机搜索算法进行了有效的结合，提出了两种改进的优化算法， 并经模拟实验证明了改进算法的有效性。 ( 4 ) 第四章探讨了粒子群优化算法在嵌入式分布数据库的复杂多 连接查询优化中的应用。系统地介绍了粒子群优化算法的基本原 理，提出了一种求解多连接查询优化问题的m p s o 算法。该算法 以左深树为搜索空间，采用有序串编码并改进了基本粒子群优化算 法的速度位置公式，将其应用于海洋监测数据的测试实验中，取得 了良好的效果。 ( 5 ) 第五章针对海洋资料信息共享的需求以及数据平台的异构特 点，提出了一种实时海洋数据传输系统架构。设计了基于x m l 的 山东大学硕士学位论文 海洋数据标记语言，对x m l 在海洋信息领域中的应用做出了有益 的探索和尝试。 ( 6 ) 第六章对全文进行总结，并对今后的工作提出了展望。 4 山东大学硕士学位论文 第2 章基于嵌入式技术的海洋监测数据管理系统设计 近年来，随着信息网络技术的发展成熟和大量网络通信基础设施 的兴建，信息系统建设的重点开始从单个应用系统的建设向应用集成 系统的建设转移，如“数字地球”和“数字海洋”等大型应用集成系 统【8 】。同时，随着高性能、低价格的嵌入式处理器不断涌现，以它们 为中心的嵌入式系统【9 ，1 0 1 和网络技术的有机结合成为大势所趋，使得 传感器、执行器等现场监控仪器、设备可以直接接入i n t e r n e t 成为实时 网络控制中的节点，从而打破了传统的工业控制网络和信息网络的界 限，为计算机监控领域带来了前所未有的发展空间和机遇。 作为一种特殊的工业环境监控系统，海洋环境监测系统逐渐发展 为集空中、海面、水下、海岸多平台监测设备为一体，和数据中心、 数据通信网络共同构成的立体监测网络体系。在该体系结构下，数据 库大多建立在不同操作系统、数据库平台之上。嵌入式实时数据库技 术的引入以及这种分布式、异构的特点使得有效的数据处理成为整个 系统的核心问题。 本章首先给出了海洋环境在线监测及灾害智能预警系统的总体架 构，随后介绍了分布式海洋监控中的数据管理子系统的架构设计以及 数据处理面临的问题。 2 1 海洋环境在线监测及灾害智能预警系统总体架构 本课题以当今先进的计算机技术、网络技术、控制理论与技术、 数据库技术，以及嵌入式系统等为背景，结合国内外海洋环境科学领 域内的研究成果及最新发展趋势1 1 1 , 1 2 , 1 3 , 1 4 ，提出了海洋环境在线监测 及灾害智能预警系统的架构，为实现海洋环境要素的实时、延时、历 史数据的采集、处理、分析、管理和数据通信网络、数据库、海洋灾 害预报模型、信息产品开发、数据资源共享与信息服务等功能模块的 集成，构造网络化、分布化、智能化、综合化的海洋环境在线监测及 灾害智能预警系统奠定了基础。 山东大学硕士学位论文 海洋环境在线监测及灾害智能预警系统总体架构的设计、构建、 实施都是围绕海洋环境资源这一特殊的工业生产背景展开的。根据系 统的功能需求，进行可行性分析，确立了系统总体结构由数据监测子 系统、数据管理子系统、模型分析子系统和数据产品子系统组成，功 能结构模型如图2 1 所示。 图2 1 系统功能结构模型 作为一个综合性的信息监测与管理系统，海洋环境在线监测及灾 害智能预警系统在空间位置上具有分布性，由监测设备组成的数据监 测子系统处于近海环境，数据管理子系统、模型分析子系统和数据产 品子系统位于陆上数据中心，它们之间通过无线和有线相结合的通讯 网络联系起来。如图2 2 所示。 6 山东大学硕士学位论文 图2 - 2 整个系统的空间分布图 2 2 海洋监测数据管理子系统架构设计 在整个系统的立体监测网络体系结构下，本文提出了基于嵌入式 技术和网络化的海洋监测数据管理子系统的设计结构。该子系统由嵌 入式监测台站、海洋数据中心、数据通信网络和远程客户端组成，如 图2 - 3 所示。 嵌入式台站l嵌入式台站2嵌入式台站n - 1嵌入式台站n 图2 - 3 海洋监测数据管理系统体系结构 7 山东大学硕士学位论文 各组成部分的主要功能是； ( 1 ) 嵌入式监测台站 每个嵌入式台站中的实时数据库定时保存由数据监测子系统采集 的海洋环境要素信息和设备状态诊断数据。嵌入式w e b 服务器的功能 是处理远程客户端的网络请求和实时信息发布的服务需求。 ( 2 ) 海洋数据中心 海洋数据中心通过定期获取嵌入式数据库中的监测数据实现数据 更新以及对各嵌入式数据库进行备份，并向客户端提供数据查询和分 析服务。备份的作用是为了对重要的历史数据进行长期的保存和为工 作人员提供历史记录参考，在此基础上可以构建海洋环境资料数据仓 库，为模型分析子系统和数据产品子系统提供强大的数据支撑。 ( 3 ) 远程客户端 远程客户端可以是位于i n t e r n e t 任一个地点的p c 机，授权用户可 以通过w e b 浏览器查询和显示各种数据信息。 ( 4 ) 数据通信网络 由于数据管理子系统的网络化架构，数据通信网络需要实现高效、 可靠的实时海洋数据传输。 嵌入式实时数据库建立在监测台站中，有利于现场监测系统具有 强大的数据管理功能和扩展更多基于数据库的本地智能应用，如建立 高精度的诊断、报警等服务，方便工作人员维护。但由于嵌入式系统 上存储空间有限，且处理能力和网络通信能力相对较弱，导致嵌入式 系统中的数据有一定更新周期，不能为远程客户端提供复杂的历史数 据查询和分析服务。因此，需要将监测数据上传至海洋数据中心进行 备份，并且上层中心数据库可以对下一级的各嵌入式数据库进行远程 管理监控，监控的目的是为了保持应用的连续性以及系统的稳定性。 通过对获得的监控信息进行分析，能够对可能出现的问题进行预测。 例如，在中心数据库建立一张实时监控表m o n i t o r l t e m ，存储数据最近 的两个更新周期内下一级数据库中的各监测要素表的索引信息，该表 每隔一定时间间隔进行动态更新。通过对比实时监控表中的记录索引 和数据库中实际接收到的监测数据，可以及时发现未能成功上传的记 录信息，以实现数据的重传。 8 山东大学硕士学位论文 2 3 海洋监测数据处理需要考虑的问题 海洋环境在线监测及灾害智能预警系统是一个集数据采集，数据 集成，数据管理，数据分析，实时数据监控为一体的综合性信息系统。 数据处理性能是影响海洋信息服务水平的重要因素，而由于系统采用 了基于嵌入式技术的立体监测网络体系，数据中心与监测数据库建立 在不同操作系统、数据库平台上，这种嵌入式分布、异构的特点使得 如何有效地利用嵌入式系统有限的资源进行数据处理，以及实现可靠、 高效的实时数据传输成为系统开发迫切需要解决的问题。因此，本文 的后续章节将详细介绍嵌入式分布数据库的查询优化算法和实时海洋 数据传输的解决方案。 2 4 小结 本章以当今先进的计算机技术、网络技术、控制理论与技术、数据 库技术，以及嵌入式系统等为背景，结合国内外相关研究成果及最新 发展趋势，提出了海洋环境在线监测及灾害智能预警系统的总体架构， 并给出了基于嵌入式数据库技术的分布式海洋监测数据管理子系统架 构设计，为实现海洋环境要素的实时、延时、历史数据的采集、处理、 分析、管理和数据通信网络、数据库、信息产品开发、数据资源共享 与信息服务等功能模块的集成，构造网络化、分布化、智能化、综合 化的海洋环境在线监测及灾害智能预警分析系统奠定了基础。 9 山东大学硕士学位论文 第3 章嵌入式实时数据库查询优化的研究 海洋环境在线监测及灾害智能预警系统是一个集数据采集，数据 集成，数据管理和数据信息服务为一体的综合性信息系统。在海洋信 息服务应用中，对特定监测站点上实时数据的远程查询和嵌入式分布 环境下的全局查询是系统查询处理的主要内容。其中，远程查询只涉 及单个站点上的数据，其局部处理的优化策略与本地查询相同：而涉 及多个嵌入式台站实时数据的全局查询要复杂一些，但根据查询处理 的层次结构，经过分解之后的局部查询也需要在本地数据库中进行进 一步优化。因此，必须考虑如何高效地实现嵌入式实时数据库系统的 查询处理。与传统的关系数据库系统一样，有效的查询优化是提升嵌 入式数据库系统处理性能的一个关键。然而，由于嵌入式平台在实时 特性、空间负载方面的特点，传统的查询优化算法不能完全适用于嵌 入式实时数据库。例如，目前用于大多数商业数据库系统中的动态编 程法属于穷尽式搜索( e x h a u s t i v es e a r c h ，e s ) 。该类算法能为给定查询 找到最优解，但具有指数级的时间和空间复杂度1 4 】。对资源有限的嵌 入式实时数据库系统而言，穷尽式搜索显然不太可取。随机算法 ( r a n d o m i z e da l g o r i t h m s l 的优势在于具有常数的空间负载，但大多数随 机算法的运行时间无法预测【6 】，不利于满足系统的实时要求。与之相 比，启发式( h e u r i s t i c s ) 策略通常只有多项式时间复杂度，如贪婪算法 i s ，但其生成计划的代价往往比穷尽式优化算法高数量级。此外，实 时数据库还应考虑如何适应各种混合事务类型的环境，短事务和长事 务，实时事务和非实时事务的优化策略是不一样的，传统的查询优化 策略往往无法区分开来【l ”。 因此，本章针对嵌入式实时数据库系统特点，首先分析了查询优 化中常用的随机搜索算法与贪婪算法的优势和不足，在深入研究的基 础上提出了改进算法，利用贪婪算法快速求解的优势，并通过迭代采 样弥补了它在搜索空间上的不足，有利于算法跳出局部极小。并且， 改进算法可以通过设置终止条件来控制优化本身的时间长短，从而能 在满足系统实时要求的前提下更好地适应不同类型事务的需要。 l o 山东大学硕士学位论文 3 1 多连接查询优化问题描述 3 1 1 问题定义 本文讨论的多连接查询( m u l t i j o i nq u e r y ，m j q ) 是 s p j ( s e l e c t - p r o j e c t - j o i n ) 查询在经过投影和选择下推优化之后得到的n 个基本关系的连接操作构成的关系代数表达式。目前，多连接查询优 化问题的研究主要分为两个方面1 1 6 1 ：确定查询中包含的所有关系连接 操作的一个好的执行顺序和执行连接操作本身的有效算法。本文重点 探讨前者。 3 1 2 相关术语 查询图：优化问题的输入表示为查询图( 或称为连接图) g = ( v ， e 1 ，其中v 、e 分别是图中节点和边的集合。每个节点i v 代表查询包 含的一个基本关系r i ：每条边e i i e 表示关系r i 和r j 之间的连接。边以 j o i np r e d i c a t e 和j o i ns e l e c t i v i t y 标识，j o i np r e d i c a t e 根据元组是否包含 在结果中，将连接结点的笛卡尔积结果中的元组映射为 f a l s e ，t u r e 。 j o i ns e l e c t i v i t y 是一个比值，表示“结果中的元组个数笛卡尔积的元组 个数”。笛卡尔积作为一个特例，可以看作这样一个连接操作，它的j o i n p r e d i c a t e = t r u e 并且j o i ns e l e c t i v i t y 为1 。 连接树：表示优化问题的一个解，即连接操作的执行顺序。连接 树本身为一棵二叉树，树的叶子结点为基本关系，每个关系出现一次 且仅一次；分支结点表示连接操作，同时代表中间结果。连接操作的 子结点代表连接操作的输入数据源，连接操作的父结点代表该连接操 作的结果流向。1 9 9 0 年，s c h n e i d e r 等研究了连接树模型1 1 7 1 ，提出了左 深树( 1 e f t - d e e pt r e e s ) 、右深树( r i g h t d e e pt r e e s ) 和茂密树( b u s h yt r e e s ) 的 概念。如图3 1 中所示。 搜索空间：也称解空间。解空间中的任一点表示一个特定的查询 执行计划。很多查询优化算法都以连接树的某个子集作为搜索空间， 山东大学硕士学位论文 这是因为不同树结构对应的搜索空间大小不同。例如，对于一个n w a y 连接，左深树空间、整个策略空间和茂密树空间的大小分别为1 8 1 ： ( + 1 ) ! 、略! 和( 锚* n f 一2 术( + 1 ) ! ) 。因此，优化过程中，如果将查 询计划的模式限定为某种适当的形式，就可以减小搜索空间，提高优 化效率。但是若搜索空间选取不当，也可能无法找到最优的查询执行 计划。 在本文探讨的嵌入式实时数据库中，由于系统本身的资源有限性 及各台站实际监测需求有限，可能的多连接查询规模不会很大，因此， 选取了完整策略空间作为解空间。而对于分布式环境下的多连接查询， 则可能的查询比较复杂，可以缩小搜索空间规模，选择左深树空间作 为优化算法的搜索空间。 入d 入c a b ( ( ( a b ) 一c ) 一d ) a ) 左深树 3 1 3 代价估计 a bc d ( 位c o b ) o o ( c o o d ) ) c ) 茂密树 图3 - 1 连接树 a 八 b 八 ( a o o ( b o o ( c o o d ) ) ) b ) 右深树 多连接查询优化的目标是在搜索空间中找到一个具有最低代价的 执行策略。每一个执行计划都有相应的代价，代表了需要占用的系统 资源。 山东大学硕士学位论文 1 查询执行计划的代价组成 查询执行计划的代价主要可分为以下几方面：i o 代价、c p u 代价、 通信代价19 1 。 ( 1 ) i o 代价：指访问外存的开销。主要是寻找、读、写外存数据 块的代价。 ( 2 ) c p u 代价：计算开销。主要指在内存( 缓冲区) 执行各类操 作，如定位、排序、归并记录和计算属性值的开销。 ( 3 ) 通信代价：主要指分布式数据库系统中，数据在各结点之间 传输的开销。 在传统的关系数据库系统中，代价主要为i o 开销和c p u 开销，与 i o 开销相比，c p u 开销相对非常小，通常忽略不计：而分布式数据库 系统中，要强调压缩通信开销：对于嵌入式数据库，由于数据量非常 小，假定查询涉及的数据可以一次装入内存，则可认为处理过程中不 存在i o ，这时主要考虑c p u 代价。若一个系统同时要考虑各种开销， 不能将各项开销简单相加，需要进行适当的加权。假定每项开销对应 的权值构成了向量九( 九1 ，九2 ，九3 ) ，而系统的i o 开销、c p u 开销和通信开 销分别记为c l ，c 2 ，c3 ，那么各项开销作为代价的列向量c ( c l ，c 2 ，c3 ) ， 则执行计划的代价为： c o s t = 2 c = a c l + 也c j + 五c 3( 3 1 ) 2 统计参数 为了估算每个执行计划的代价，系统必须提供必要的统计信息， 它们一般保存在d b m s 的数据字典里，供查询优化器使用，这些统计信 息详见文献 2 0 , 2 1 , 2 2 。由于影响查询代价的因素很多，如果将它们都作 为代价方程的自变量必然导致方程过于庞大，所以必须对变量有所选 择，只考虑其改变将对代价造成显著影响的因素。在数据库管理系统 的统计信息中，常用于代价估计的参数主要有： 刀，关系r 中的元组数目； ，关系r 中一个元组的大小r i nb y t e s ) ； 6 ，含有关系r 的元组的块数目； 一个磁盘块( b l o c k ) 中能存储的关系r 的元组数； h 4 ，) 关系r 中属性a 所具有的不同值的数目。该数目与j i 一( r ) 的大 山东大学硕士学位论文 小相同。若a 为关系r 的码，v ( a ，r ) 即为n ，。 对于连接操作，设关系t 为关系r 和s 连接的结果，c 是r 与s 的 公共属性，则有： 巾) = 币蔫 v ( a , t ) = ( 3 - 2 ) v ( a ，1 a ，一s v ( a ，j ) 彳s 一， ( 3 - 3 ) m i n ( 矿( 彳，r ) ，矿( 4 ，s ) ) a e r & a es 为简便起见，本文后续章节的代价公式中均采用文献【5 】中的选择 因子0 ，作为估计关系r 、s 连接代价的一个参数。该参数的值可按式( 3 - 4 ) 计算得到： 2 未2 可磊丽石i 厕( 3 - 4 )2 而南2 可磊丽甭咿瓦两 可见为了建立一个精确的代价模型，需要在数据字典中保存大量 的基关系的统计信息，并且其中一些统计信息随数据库状态而改变。 为了保证基本统计信息的准确性，需要不断地修改数据字典中的有关 内容。如果这些统计信息不准确，或者不能表示当前的数据库状态下 的统计信息，就会导致估计结果的误差，并且随着查询中包含的连接 个数的增加，这种误差将成指数级增长。 然而，在海洋环境监测领域中，需要不断地采集各类数据信息， 数据库状态变化很频繁，修改统计信息的工作量会很大。并且，由于 实际应用中往往缺乏在优化过程中系统的一些实时信息，如可用资源、 系统负载等，因此实际应用中，建立一个精确的代价模型是一个很困 难的问题【2 。 3 2 随机搜索算法 为了达到“优化时间+ 找到的查询执行计划的执行时间”最小的目 的，即以合理的时间复杂性和空间复杂性为代价，为多连接查询问题 1 4 山东大学硕士学位论文 找到一个较好的执行计划，迄今，研究者们已提出了许多将随机因素 结合到搜索技术中的优化算法。模拟退火( s i m u l a t e da n n e a l i n g 。s a ) 和 迭代改进( i t e r a t i v ei m p r o v e m e n t ，i i ) 算法就是两种著名的随机搜索方 法。 迭代改进和模拟退火算法都是求解组合优化问题的有效技术，首先 介绍这两种算法的描述中常用的一些术语： 状态空间：组合优化问题的所有解。 状态：组合优化问题的一个解。 代价函数：评价状态的代价的函数。 移动：将一种状态转换到另一种状态的一个变换。 相邻状态：一种状态只使用一种移动得到另一种状态，这两种状态 称为相邻状态。 局部最小：代价低于所有相邻状态的代价的一种状态。 全局最小：所有局部最小状态中的最小代价者。 随机搜索算法通常从状态空间的一个随机状态出发，与随机选择的 一个邻居状态进行比较，若得到更优的状态或可以接受的状态，就将 当前状态移动到这个邻居状态，继续进行迭代；否则，在邻居状态中 继续寻找。直至获得满意解，算法终止。搜索过程中，一个状态的邻 居是由一系列转换规则决定的。下面在算法中将具体介绍多连接查询 优化问题的转换规则。 3 2 1 迭代改进算法 迭代改进算法是对爬山算法( h i l l - c l i m b i n ga l g o r i t h m ) 的改进，克服 了爬山法易陷入局部最优解的问题。 爬山法是启发式搜索的一种局部择优法【2 4 1 。算法沿着有可能改进 解的质量的方向进行单方向搜索( 爬山) ，具有较强的局部搜索能力。 但该算法只注重搜索当前附近的最好解而忽略了搜索空间的扩展，因 此，爬山算法只有对具有单峰分布性质的解空间才能实施行之有效的 搜素，并最终求得问题的最优解。而对于多峰问题，由于爬山算法缺 乏对问题的可行空间的全局性采样，陷入局部最优解的可能性极大。 山东大学硕士学位论文 i i 算法通过以下的方法来尽量解决这个问题：在选择随机起始状态 后，算法使用一种类似爬山法的策略来寻找一个最小代价点。i i 的内循 环称为局部优化。局部优化从起始状态开始，选择一个随机邻居( 比 如刚好可以通过一次移动到达的状态) ，如果邻居状态的代价比当前状 态代价小，则进行一次移动，并选择一个新的具有更低代价的邻居状 态，重复这种随机移动直至达到一个局部极小值。这种策略与原始的 爬山法不同，因为不需要尽量确定具有最低代价的邻居状态，原因就 是有非常多数目的邻居需要检查。同样也不会检查一个给定状态是否 是局部最小的。该方法不会系统的列举所有可能的邻居并单独进行检 查，如果在一定数目的试验中没有发现更低代价的邻居，则该状态被 认为是局部最小的。然后，i i 将随机产生另一个新的状态重新启动算法， 重复这些局部优化直到满足结束条件。如果对时间不加以限制，i i 算法 能够找到全局最优解。 i t e r a t i v ei m p r o v e m e n t 算法： m i n s = s m i n c o s t = w h i l en o t ( s t o p p i n g c o n d i t i o n ) d o s t a t e = ”r a n d o ms t a r t i n gp o i n t ” c o s t = c o s