（计算机应用技术专业论文）综合信息集成及查询优化的研究.pdf

大连理工大学博士学位论文 摘要 随着i n t e r a e t 技术的发展，w e b 上各种在线信息源不断涌现，这些信息源种类繁多， 结构各异。在互联网这样一个动态的环境中，各信息源不断地发生着变化，在这样一个 动态、异构、开放的环境下快速、准确地获取信息是十分困难的。因此，研究信息集成 系统，为用户提供一个访问异构数据源的统一接口有着非常重要的意义。在这种背景下， 本文对信息集成系统的主要技术进行了深入的研究，具体研究工作如下： 信息集成系统体系结构是研究系统的组成模块以及各模块之间关系的。本文对目前 几种典型的信息集成系统体系结构进行了分析，总结了这些体系结构的优点和不足。在 对实际的信息集成工作中遇到的问题及其他相关需求进行分析的基础上，提出了综合信 息集成系统体系结构。该体系结构既考虑对已有投资的保护，又考虑对不断生成的新数 据的有效处理；既考虑对传统数据库中的数据和x m l 数据的处理，又考虑信息检索和辅 助决策的需求。是一个面向目前大多数企业的综合信息集成系统。 模式映射的建立是信息集成系统的重要环节之一。本文提出了基于划分的映射模式 发现框架p b m s d f ( p a r t i t i o n 显a s e dn a p p i n gs c h e m ad i s c o v e r yf r a m e w o r k ) 。 d h a r a a n k a r 等提出了n 山诤框架，该框架采用搜索器集合和b e a ms e a r c h 的方法，可以 自动发现1 ：1 映射、1 ：九和以：l 的复杂映射，但是存在以下不足：一是不能发现肌： 疗的复杂映射；二是该框架需要对属性及属性值实例进行分析，导致系统开销很大：三 是对于w e b 信息集成，获取属性值的数据实例有时是不可能的，因此该框架不能用于 w e b 信息集成。h e 等提出了d c m ( d u a lc o r r e l a t i o n m i n i n g ) 框架，该框架采用对属性 在模式中的分布进行分析发现属性之间相关度的方法来发现属性之间的映射关系，可以 解决i m a p 框架中存在的问题，仍存在以下不足：一是由于该框架采用的相关度衡量标 准对部分属性的评价结果不准确，导致发现结果准确性不高；二是该框架中采用的 a p r i o f i c o m n i n i n g 和d u a l c o r r e l a t i o n m i n i n g 挖掘算法在由相关f 项集生成相关升l 项集的 过程中，将整个属性集合中的每一个属性添加到相关f 项集中构成候选相关升1 项集， 然后再判断该升l 项集是否相关，增加了许多不必要的计算，致使搜索空间过大，算法 的效率较低。本文提出了比较适合于衡量属性之间相关度的c 衡量标准，并在p b m s d f 框架中采用了该标准以提高发现结果的准确度；提出了基于划分和栈的模式映射发现算 法，理论分析和实验结果均证明，该框架较i m a p 和d c m 具有较高的性能和较好的模 式发现能力。 x i v i l 成为目前w c b 上数据表示和信息交换的标准，处理x m l 数据是集成系统的 功能之一，x m l 查询的效率将直接影响集成系统的性能。本文提出了一种基于递归模 于红：综合信息集成及查询优化的研究 式的x m l 查询优化算法。该算法对x m l 模式中的节点和x m l 文档中的节点分别建立 索引，并用模式节点编号建立模式中的节点与文档中节点的关联。查询时先在x m l 模 式中进行查找，若无匹配结果，则无需在x m l 文档中查找：否则也只需对x m l 文档 中与对x m l 模式查询的结果节点编号相同的节点进行筛选，大大减小了搜索空间。对 具有递归模式的x v l l 的查询，先对查询树进行去除重复元素的预处理，然后将查询树 分解成主路径和分支路径，分别进行查找。查询过程中利用旺文档节点索引以加快 查询速度。该方法可以减少连接操作的次数，提高查询操作的效率，能处理较复杂的 x m l 模式。 多连接查询是影响信息系统查询效率的主要因素之一。本文提出了基于图的多连接 查询优化算法。该算法充分考虑与同一个关系相关的连接操作之间的相互影响，首先确 定与同一个关系相关的连接中结果关系最小的连接操作为优先进行的操作，再从这些优 先进行的连接操作中选择权重最小的执行；实验证明，该算法较i v i v p 算法、g m c 算法、 g m 算法和i m p r o v c d - g m c 算法具有较好的性能。 属性值的分布会对查询计划的执行效率产生影响。本文充分考虑了模式中属性值分 布的不均匀性和属性值之间的相关性对查询结果的影响，给出了基于值的简单查询优化 模型和带连接操作的查询优化模型，并根据优化模型给出相应的优化算法。通过实验证 明了该算法的有效性。 对集成系统的查询优化进行了初步的研究，在前人研究工作的基础上，提出了集成 系统的查询优化框架。 关键词：信息集成；模式映射；多连接查询优化；x m l 查询优化；p b m s d f 大连理工大学博士学位论文 r e s e a r c ho ns y n t h e t i c a li n f o r m a t i o ni n t e g r a t e da n dq u e r yo p t i m i z a t i o n a b s t r a c t w i 也t h ed e v e l o p m e n to fi n t e m e t , a l ls o r t so fo n l i n ei n f o r m a t i o ns o u l sa r ei n c r e a s i n g r a p i d l y n l et y p ea n ds t r u c t u r eo ft h e s ei n f o r m a t i o ns o u r c e sa r ed i f f e r e n t 1 1 1 es t t u e t l l r ea n d c o n t e n to ft h ei n f o r m a t i o ns o u r c , 嚣k e e pc h a n g i n g i tw i l lb ev e r yd i f f i c u l tt or e t r i e v e i n f o r m a t i o nf r o mt h ed y n a m i c ，h e t e r o g e n e o u s ，o p e nc i r c u m s t a n c e i ti sv e r ys i g n i f i c a t i v et o r e s e a r c ht h ei n f o r m a t i o ni n t e g r a w x ls y s t e ma n dp r o v i d eau n i f o r mi n t e r f a c ef o r 也eu s e r s u n d e rs u c hc i r c u m s t a n c e s t h em a i nt e c h n i q u e so fi n f o r m a t i o ni n t e g r a t i o nf i l ed i s c 琳s e d t h e k e ye o n t r i b u t i o ma i ea sf o l l o w s 1 1 ka r c l t i t e e t u r es h o wt h em o d u l e so f t h ei n f o r m a t i o ni n t e g r a t e ds y s t e ma n dt h er e l a t i o n s a m o n gt h em o d u l e s n 伦f a m o u sa r c h i t e c t u r e so fi n f o r m a t i o ni n t e g r a t e ds y s t e ma 托a n a l y z e d n 圮a d v a n t a g e sa n dd i s a d v a n t a g e so ft h ea r c h i t e c t u r e sa r ed i s c u s s e d o nt h eb a s i so f a n a j y z i n gt h er e q u i r e m e n to ft h ea c t u a li n f o r m a t i o ni n t e g r a t i o ns y s t e ma n do t h e rr a l a t i v e i n f o r m a t i o ni n t e g r a t e ds y s t e m , t h ea r c h i t e c t u r eo fs y n t h e t i c a li n f o r m a t i o ni n t e g r a t i o ns y s t e m i s p r o p o s e d i nt h en e wa r c h i t e c t u r e ，b o t ht h e e x i s t e n ti n f o r m a t i o na n dt h ep r o d u c i n g i n f o r m a t i o na r eh a n d l e d t h ed a t af r o mt r a d i t i o n a ld a t a b a s ea n dx m ls c h e m aa l em a n a g e d , t h ei n f o r m a t i o nr e t r i e v i n ga sw e l la st h ea s s i s t a n td e c i s i o na l ec o n s i d e r e d i tc 趾m e e tt h e r e q u i r e m e n to f m o s te n t e r p r i s e s 1 1 地c r e a t i o no ft h es c h e m am a p p i n gi so n eo ft h ei m p o r t m e n ts t e p si ni n f o r m a t i o n i n t e g r a t e ds y s t e m n 塘p b m s d f ( p a r t i t i o nb a s e dm a p p i n g s c h e m a d i s c o v e r y e r a m e w o r k ) i sp r e s e n t e dt oe f f i c i e n t l yd i s c o v e rt h em a p p i n gs e h e m & d h a m a n k a rp r o p o s e di m a pf l a m e , i nw h i c ht h es e to fs e a r c h e ra n db e a ms e a r c ha r ea p p l i e d 1 ：1 1 ：na n dn ：lm a p p i n g sc 趾b e d i s c o v e r e d h o w e v e r , t h e r ea l es o m ed i s a d v a n t a g e si ni n i a pf r a m e f i r s t l y t h e 肌? 拧m a p p i n g g a l l tb ed i s c o v e r e d s e c o n d l y t h ea t t r i b u t e sa n dt h ei i l s t a 愀o ft h ea t t r i b u t e sm u s tb e a n a l y z e dt 0d i s c o v e rt h em a a p i n gs c h e m as ot h a tt h ec o s to f t h es y s t e mi se x p e n s i v e f i n a l l y 。 g e e t i n gt h ei n s t a n c eo f a t t r i b u t e si si m p o s s i b l ef o rw e b i n f o r m a t i o ni n t e g r a t i o mt h e r e f o r e t h e i 队pf l a m ec a n tb eu s e di nw 曲i n f o r m a t i o ni n t e g r a 重e d h ep r o p o s e dd c m ( d u a l c o r r e l a t i o n m i n i n g ) f l a m e i n w h i c h t h e p r o b l e m s o f i m a p 雠l n ea r er e s o l v e d h o w e v e r , t h e s h o r t c o m i n g so fd c m a r ca sf o l l o w s o nt h eo n eh a n d , t h em e a s u r eo ft h ec o r r e l a t i o ni s i n a c c u r a t es o m e t i m e ss ot h a tt h et h er e s u l ti su n a u t h e n t i co l lo c c a s i o n o nt h eo t h e rh a n d , t h e t i m ec o s to fa p r i o r i c o r r m i n i n ga n dd u a i c o r r e l a t i o n m i n i n gm i n i n ga l g o d t h i n sh a sal o to f u n n e c e s s a r ys e a r c h i n g i nt h i sp 印mc - m e a s u r ei sp r o p o s e d , t h ep a r t i t i o na n ds t a c k b a s e da t t r i b u t eg r o u pa n dm a p p i n gs c h e m ad i s c o v e r ya l g o r i t h ma p r o p o s e d n 坨f o r m e r 锄 c a l c u l a t et h ec o r r e l a t i o na m o n ga t t r i b u t e sa n dt h el a t t e rc a l lr e d u c et h es e a r c ht i m e 1 1 - i i i 于红：综合信息集成及查询优化的研究 t h e o r e t i c a la n a l y s i sa n dt h ee m p i r i c a lr e s u l t ss h o wt h a tt h ep e r f o r m a n c eo fp b m s d fi sb e t t e r t h a nt h a to f i m 嗡pa n dd c m x m l i sb e c o m i n gt h es t a n d a r do f t h ed a t ap r e s e n t a t i o na n di n f o r m a t i o ne x c h a n g eo nt h e w e b o n ef u n c t i o no ft h ei n f o r m a t i o ni n t e g r a t e ds y s t e mi st om a n a g et h e ) m ld a t a t h e q u e r ye f f i c i e n c yo f t h ex m i w i l l a f f e c tt h ep e r f o r m a n c eo f t h ei n f o r m a t i o ni n t e g r a t e ds y s t e m ar e c u r s i o ns c h e m ab a s e di n d e x e sa r ep r o p o s e df o rx m lq u e r yo p t i m i z a t i o n 皿e p a r e n t c h i l dn o d ea n da n c e s t o r d e s c e n d a n tn o d ei nx m 匝s c h e m a a r ci n d e x e d n en o d e si n x m ld o c u m e n t sa r ci n d e x e d 鹊w e l l t h en o d en u m b e ri nx m ls c h e m ai su s e dt oa s s o c i a t e t h en o d ei nx m ls c h e m aw i t ht h en o d e si nx m ld o c u m e n t s w h e nt h eq u e r yi sc a l c u l a t e d , t h ex m ls c h e m ai sq u e r i e df i r s t l y i ft h e r ei sn om a p p i n gn o d e t h ex m ld o c u m e n td i d n t h a v et ob eq u e r i o d o t h e r w i s e t h en o d e st h a th a v et h es a m e 舭s c h e m an u m b e rw i t h 也e n o d e si nx m lq u e r yr e s u l t sa r ch a n d l e d t h es e a r c hs p a c ei sg r e a t l yr e d u c e d t h ex m l s c h e m a sw i t hr e c u r s i o ne l e m e n t sa r et a k e ni n t oa c c o u n t t h eq u e r yt r e ew i t hr e p e t i t i v el a b e l s i sp r e t r e a t e d t h er e p e t i t i v ee l e m e n t sa r er e m o v e d t h es i m p l i f i e dq u e r yt r e ei sd e c o m p o s e d i n t om a i np a t ha n db r a n c hp a t h s w h e nt h eq u e r yi se x e c u t e d , t h ei n d e x e s 辨a p p l i e dt o a c c e l e r a t et h eq u e r ye v a l u a t i o n r 1 1 1 en u m b e ro f j o i ni sg r e a t l yr e d u c e ds ot h a tt h ee f f i c i e n c yo f q u e r yi sg r e a t l yi m p r o v e d n ec o m p l i c a t e ds c h e m ac 锄b et r e a t e d m u l t i j o i nq u e r yi so n eo ft h em a i nf a c t o r st h a ta f f e c tt h eq u e r yp e r f o r m a n c eo ft h e i n f o r m a t i o ns y s t e m ag r a p hb a s e dm u l t i - j o i nq u e r yo p t i m i z a t i o na l g o r i t h mi sp r o p o s e d , i n w h i c ht h ei n f l u e n c e sa m o n gt h ej o i no p e r a t i o n sc o n c e r n i n gs a m er e l a t i o na r et a k e na d e q u a t e c o n s i d e r a t i o n t h ej o i no p e r a t i o nt h a tt h e 他s l l l tr e l a t i o ni sm i n i m a li sc h o o s e da st h e t o p p r i o r i t yo p e r a t i o n t h e n , t h em i n i m a lw e i g h tj o i no p e r a t i o na m o n gt h et o p - p r i o r i t y o p e r a t i o n si s s e l e c t e dt oi m p l e m e n t n 地r e s u l to ft h ee x p e r i m e n t si n d i c a t e st h a tt h e p e r f o r m a n c eo f t h ep r o p o s e da l g o r i t h mi sb e t t e rt h a nt h a to f pa l g o r i t h m 、g m ca l g o r i t h m 、 g ma l g o r i t h ma n di m p r o v e d - g m ca l g o r i t l m a 力l ed i s t r i b u t i o no ft h ev a l u e so ft h ea t 岱b u t e sc a 玎r e d u c et h eq u e r ye f f i c i e n c y i 碍| e b n e v e nd i s t r i b u t i o no ft h ea t t r i b u t e sv a l u ea n dt h ee f f e c to ft h ev a l u e so fo n ea t t r i b u t i o no n t h a to ft h eo t h c a sa r cc o n s i d e r e d ，t h es i m p l ev a l u eb a s e dq u e r yo p t i m i z a t i o nm o d e la n dt h e c o m p l i c a t e dv a l u eb a s e dq u e r yo p t i m i z a t i o nm o d e la r ep r e s e n t e d 1 1 1 ev a l u eb a s e dq u e r y o p t i m i z a t i o na l g o r i t h m sa r ep r o p o s e d n 嵋r e s u l t so ft h ee m p c r i m e n t so nr e a ld a t a s e ts h o w t h a tt h ea l g o r i t h m sa r ee f f e c t i v e n 地q u e r yo p t i m i z a t i o no ft h ei n t e g r a t e ds y s t e mi sd i s c u s s e d b a s e do nt h ew o r ko f 0 1 1 础1 ：s c h o l a r s ，aq u e r yo p u m i z 蕊o nf r a l n eo f i n t e g r a t e ds y s t e mi sp r o p o s e d k e yw o r d s ：i n f o r m a t i o ni n t e g r a t e d ：s c h e m am a p p i n g ：m u l t i - j o i nq u e r yo p t i m i z a t i o n ： x m l q u e r yo p t i m i z a t i o n ；p b m s d f i v 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 、 作者签名：三叁兰日期：a 1 4 ：金乡 大连理工大学博士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 ) 立盖苎 左舅耸 塑! 年l 月2 生日 大连理工大学博士学位论文 1 绪论 1 1 工作背景 随着i n t e m e t 技术的发展，w e b 成为一种重要的信息传播和交换的手段。w e b 上的 数据库快速增长，z h m a g 等在2 0 0 4 年4 月做的一项研究估计网络上有4 5 0 ，0 0 0 个在线 数据库。各种在线信息源不断涌现，这些信息源种类繁多，样式各异，主要包括各种数 据库、对象存储、知识库、文件系统、数字图书馆、信息检索系统、电子邮件系统等“1 。 信息类型包括结构化信息，如：传统的关系表中的信息；非结构化信息，如：e m a i l 和 文本信息等；半结构化信息，如：某些有一定模式的w e b 上的信息等。由于各个信息 源的信息模型、信息类型、内容的表示方法、查询语言、信息处理方法以及所使用的术 语等都存在很大差异，而互联网是一个动态的环境，各个信息源的内容、存在方式等在 不断地发生着变化。要在这样一个动态、异构、开放的海量信息环境下快速、准确地获 取所需信息是十分困难的。因此，为用户提供一个访问这样一个复杂信息环境的统一接 口，使用户实现对这种异构、分布、动态、开放的信息源的透明访问是目前数据库领域 亟待解决的研究课题之一。 信息集成是将大量分布的、异构的、动态的信息源中的信息看成一个整体，其目的 是对存在于不同信息源中的信息进行整合，并且以一个统一的视图提供给用户使用，将 用户从乏味的手工查询每个信息源的工作中解脱出来翻。是在现在这样一个信息爆炸的 时代，企业要想不被淘汰，就不仅要掌握企业内部的各种信息系统中的业务数据，而且 要了解企业外部的相关领域的信息；政府或组织如果要想做出正确的决策，就不仅要了 解各部门的信息管理系统的运行数据，而且还要知道其他相关部门或组织的信息。因此 无论是企业还是政府或组织都需要建立信息集成系统。信息集成系统可以满足不同用户 的各种信息需求，信息集成是目前数据库领域的热点研究内容之一。 由于信息集成系统需要为用户提供一个统一的视图，因此需要确定一个能准确表 达所有数据源模式的中间模式，还要建立中间模式和数据源的本地模式之间映射。为完 成一个查询，系统利用这种映射将一个针对集成系统的查询转化成多个针对分布在各站 点的数据源的查询，在每个数据源本地执行查询，然后将各个数据源的查询结果合并起 来，返回给用户。目前大部分集成系统中的这种映射是由系统管理员或映射建立者手工 建立的，手工完成这项工作既乏味又容易产生错误。为了保证信息集成系统所提供信息 的准确性，提高建立集成系统的自动化程度，研究信息集成系统的中间模式本地模式自 动映射具有十分重要的意义旷”1 。 于红：综合信息集成及查询优化的研究 查询优化是提高信息集成系统查询效率的有效手段。在一个综合信息集成系统中， 不仅包含传统的关系型数据源，而且包含了半结构化和非结构化数据源，因此既要考虑 传统数据库的查询优化，又要考虑半结构化和非结构化数据的查询优化，同时还要考虑 集成系统作为一个整体的查询优化。关系数据库中已经有很多成熟的查询优化算法以及 索引技术，例如：循环嵌套连接算法、合并连接算法、混合连接算法、多表连接算法、 b + t r e e 索引、b i t m a pj o i ni n d e x e s 等“”，但是对于一些边缘问题或复杂查询的优化问 题一直是近年数据库领域的研究重点，例如：对于连接查询的优化、复杂查询的选择度 估计、子查询优化和基于值的查询优化等还有必要进一步研究“例。由于传统的关系数 据库有着不同于半结构化和非结构化数据的特征，因此传统的关系型数据库系统中的查 询优化算法不同直接应用于半结构化和非结构化数据的查询优化。x m l 成为半结构化 数据和非结构化数据建模的标准侧，因此，研究x m l 查询优化，对提高半结构化和非 结构化数据源的查询效率是必要的。集成系统的运行环境具有动态性、不确定性，为提 高系统的性能，研究集成系统的查询优化对提高信息集成系统的效率，提高可用性有着 十分重要的意义。 1 2 本文的主要贡献 本文主要贡献如下： ( 1 )结合基于w e b 的信息集成系统中模式映射的特点，分析了目前已经提出的映射 发现框架 m a p 框架和d c m 框架中存在的系统开销大和准确率低等不足，提出了 基于划分的映射模式发现框架呻b m s d f 框架。针对d c m 框架中映射发现准确率低 的原因是属性相关度衡量标准及属性组不相关度衡量标准选用不当的事实，在分析了各 种相关度衡量标准的特点以及w e b 信息集成系统中属性相关特点的基础上，提出了适 用于w e b 信息集成系统的属性相关度衡量标准及属性组不相关度衡量标准c 衡量 标准，该标准充分考虑了w e b 信息集成的模式映射中可能出现的各种不同情况，提高 了发现的匹配模式的准确性。分析了a p r i o r 类数据挖掘方法和f p - t r e e 类方法的特点， 融合了这两类方法的优点提出了基于划分和堆栈的属性组发现算法和候选匹配发现算 法，该算法基于任务分解的思想，利用划分的方法避免了不同子任务空间属性之间的不 必要计算，同时利用堆栈存放可能相关的属性，而在后边的计算中只需要考虑与堆栈中 的属性相关的属性，大大减小了搜索空间，提高了算法的效率。并用实验证明了算法的 有效性。 ( 2 )分析了x m l 模式和x m l 文档之间的关系以及x m l 查询的特点，提出了一种 基于直接递归x m l 模式索引的x m l 查询优化方法。该方法分别对x m l 模式中的节点 大连理工大学博士学位论文 和x m l 文档中的节点建立索引，查询时考虑x m l 模式中带有直接递归的情况，先对 查询树进行去除重复元素的预处理，并将查询树分解成主路径和分支路径，然后利用模 式索引查找潜在目标节点的x m l 模式编号，最后利用x m l 文档索引对对应节点进行 筛选，找到目标节点。该方法可以减少连接操作的次数，提高查询操作的效率，能处理 较复杂的v 儿模式。实验表明，该方法具有较好的性能。 ( 3 )针对传统数据库的多连接查询开销较大的情况，对多连接查询的特点进行了分 析，发现多连接查询的执行顺序直接影响查询计划的执行效率以及多连接查询可以用图 来表示这一事实，提出了基于图的多连接查询优化算法，该算法充分考虑与同一个关系 相关的连接之间的相互影响，首先确定与同一个关系相关的连接中结果关系最小的连接 操作为优先进行的操作，再从这些优先进行的连接操作中选择权重最小的执行，从而使 得整个查询的执行代价最低。针对目前的查询优化算法均假设所有的属性值都是均匀分 布的，事实上属性值存在不均匀分布的情况，分析了属性值的不均匀分布对查询执行计 划的影响，并在此基础上提出了基于值的查询优化算法，该算法考虑到了属性值分布的 不均匀性以及属性值之间的相关性对查询结果的影响，从而保证查询执行计划的客观性 和科学性。用实验验证了算法的效率，实验结果表明，两个算法都具有较好的性能。 1 3 论文结构 本文共分六章，各章的内容组织如下； 第一章为绪论部分。1 1 节对本文的工作背景进行了介绍；1 2 节简要说明了本文 所作的几点主要贡献；1 3 节介绍了本文的结构。 第二章介绍了本文中提出的综合信息集成系统的体系结构。2 1 节介绍了信息集成 系统体系结构的研究现状，分析了各种体系结构的优缺点和适用范围：并对目前的信息 集成系统需求进行了系统地分析；2 2 节阐述了根据信息集成系统需求提出了综合信息 集成系统体系结构，并结合该体系结构阐述了综合信息集成系统需要研究的内容，并指 出了本文的研究重点：2 3 节对该体系结构中内部数据源的数据分布方法进行了阐述， 2 4 节对第二章进行了小结。 第三章介绍了集成系统模式映射的实现细节。3 1 节阐述了模式映射研究的必要 性，介绍了模式映射的主要研究内容以及目前的研究现状；3 2 节对映射建立的相关研 究成果进行了分析，指出了每种映射建立框架的优点和不足；3 3 节详细阐述了本文提 出的模式映射体系结构_ p b m s d f 框架，阐述了该框架的工作原理，介绍了每一部分 的功能及实现方法，指出了本文重点要解决的问题；3 4 节对现有的属性相关度衡量标 准进行了分析，指出了其中存在的问题并提出了p b m s d f 框架中采用的属性相关度衡 于红：综合信息集成及查询优化的研究 量标准和属性组不相关衡量标准c 衡量标准，在此基础上提出了基于划分和栈的属 性组发现算法和候选匹配发现算法；3 5 节阐述了映射构建方法；3 6 节对算法性能进行 了定性分析3 7 节给出了实验研究结果；3 8 节对第三章进行了小结。 第四章介绍了具有直接递归模式的x m l 查询优化问题。4 1 节阐述了x m l 查询 优化的研究现状，提出了进行具有递归模式的x m l 查询的必要性：4 2 节对基于d t d 的查询优化研究进行了分析，指出了每种方法的优点和不足：4 3 节对本文中提出的方 法进行了详细的阐述，包括对x m l 模式的处理、对m 。查询的预处理、对x m l 模式 的查询算法和对x m l 文档的查询处理算法；4 4 节设计了算法性能分析实验；4 5 节对 第四章进行了小结。 第五章介绍了传统数据库查询优化算法。在5 1 节分析了传统数据库查询优化的研 究现状，阐述了多连接查询优化和基于值的查询优化研究的必要性；5 2 节对多连接查 询优化算法的图模型和树模型、算法描述、算法性能分析及实验结果进行了详细的阐述； 5 3 节对基于值的查询优化的费用模型进行了分析，对基于值的查询优化算法进行了详 细的阐述，并对算法的实验结果进行了分析；5 4 节对第五章进行了小结。 第六章对集成系统查询优化进行了介绍。6 1 节对查询优化算法进行了分类，分析 了每种类型的查询优化算法的特点，并阐明了集成系统的查询需要动态优化的理由；6 2 节对集成系统查询优化的初步研究结果进行了简单的介绍；6 3 节分析了本文提出集成 系统的查询优化框架；6 4 节对第六章进行了小结。 最后在结论部分对全文进行了总结。阐述了本文所作的主要工作，并指出了本文 工作存在的不足以及进一步要解决的问题。 大连理工大学博士学位论文 2 综合信息集成体系结构 2 1 信息集成系统体系结构研究现状 信息集成系统是为了满足用户对信息的需求而建立的系统，信息集成系统的研究 已经经历了二十多年的发展，研究者提出了很多信息集成体系结构。”3 。这些体系结构 可以分成以下三种类型： ( 1 ) 联邦信息集成系统 1 9 8 5 年，d e n n i sh c i m b i g n e r 等提出了联邦信息集成系统”，该系统是将运行在不 同服务器上的多个独立数据源统一到一个逻辑上单一的集成系统中，这些服务器之间无 共享资源，通过l a n 连接起来o “删，其体系结构如图2 1 所示。这种结构比较简单， 集成系统有统一的数据模式，数据被水平地划分到不同的服务器上，不用考虑不同数据 源之间数据的转化和统一。但是，它存在以下问题：首先，无论是d b a 还是应用开发 人员都必须严格区分本地数据和远程数据；其次，构建这样一个系统需要很长的开发周 期，需要有高性能的主机设备，系统实现代价较高；再次，集成系统的扩展和维护代价 较大，且不同集成系统之间无法实现共享；最后，当系统规模较大时，系统性能会下降。 因此，随着信息资源的不断增长，联邦信息集成系统的应用受到一定的限制。 图2 1 联邦信息集成体系结构 f i 晷2 1f 酣e r 砒e da 蛐辨嘶f o ri n f o r m a t i o ni n 魄g r 砒e d 于红：综合信息集成及查询优化的研究 ( 2 ) 基于数据仓库的信息集成系统 数据仓库的概念是d e v l i n 和m u r p h y 于1 9 8 8 年首次提出的m 1 ，1 9 9 3 年w i l l i a m h i n n l o n 系统地阐述了数据仓库的思想、理论o ”。数据仓库是一个面向主题的、集成的、 随时间变化的、非易失性的数据集合，数据仓库体系结构如图2 2 所示。来自不同数 据源中的数据经过抽取、转换、清洗等操作加载到数据仓库中，终端用户使用o l a p 或 数据挖掘工具对数据仓库中的数据进行分析处理，获取自己想要的信息，主要用于为企 业各级管理人员从业务系统中获取决策支持提供服务。基于数据仓库的信息集成系统数 据高度集中，能够对企业决策所需求的大量信息进行有效处理。但是，该体系结构也存 在不足：一方面由于网络环境下w e b 数据源中数据是不断变化的，而用户使用的是数 据仓库中的数据，数据源中数据的变化在数据仓库中不能实时体现出来，要想尽可能为 用户提供准确、实时的信息，就需要不断地维护和更新数据仓库，使得数据仓库的数据 更新和系统维护的代价过大，该方法的实用性受到了挑战；另一方面，目前基于数据仓 库的信息集成系统在表达半结构化数据方面的能力不足，限制了该体系结构的应用范 围。 。一一一一一一一一一一ji；：i；：jj：j?l!j：三一一一一一一一一一一： t - - ： 图2 2 数据仓库体系结构 f i g 2 2d a t aw a r e h o u s ea r c h i t e c t u r e 6 一 前螭工 o l a p 服务器 数据仓库 首理系统 数据选择、转换、 集成、涪洗、复制工 大连理工大学博士学位论文 ( 3 ) 基于中介器包装器的信息集成系统 基于中介器包装器的信息集成体系结构如图2 3 所示，该体系结构中数据不是存 放在中间层，而是依然保存在数据源中，当用户发出查询请求时，由中介器对查询进行 分析，确定与该查询相关的数据源，并将查询分解为对相关数据源的子查询，由各数据 源的包装器将子查询转换成对相应数据源的查询语言，由各数据源本地的查询执行引擎 执行相应的子查询，各包装器将相应的执行结果抽取出来，中介器将从各数据源返回的 查询结果进行合并得到最终查询结果返回给用户。1 。该体系结构对用户完全透明，用 户可以不必了解每个数据源的模式，由中介器进行查询分解，包装器进行模式转换。同 时由于用户使用的数据是保存在数据源中的数据，因此数据源中数据的变化可以在用户 的查询结果中实时体现出来。该体系结构要解决的主要问题是模式映射和查询优化。一 方面，由于在目前这种异构、分布、动态、开放的环境下数据源的数量可能成千上万， 而数据源之间千差万别，中介器必须了解每个数据源的特性，中介器所提供的模式是一 个统一的模式，而各数据源的模式各不相同，因此，要建立各数据源与中介器之间的模 式映射。另一方面，对一个查询，当相关的数据源确定以后，需要进行查询转换，并在 每个相关数据源的本地执行具体的查询操作，为了提高整个系统的性能，查询优化是必 须要考虑的问题。该系统解决了数据的实时性问题和数据源的异构性问题，在一定程度 上弥补联邦信息集成系统和基于数据仓库的方法的不足，但是也存在不足：一是由于数 据保存在数据源中，查询必须要通过网络到数据源所在处进行，所以不能满足对响应时 间要求比较高的需求；二是该体系结构主要满足信息查询的需求，不能满足决策的需求。 图2 3 基于中介器包装器的信息集成体系结构 f i e 2 3 m e d i a t o r w r a p p e rb a s e di n f o r m a t i o nh i 嘲毋删a r c h i t e c u n 于红：综合信息集成及查询优化的研究 通过对这三种典型的信息集成系统体系结构分析发现，