（计算机软件与理论专业论文）lav数据集成系统的查询处理.pdf

l a v 数据集成系统的商询处理 摘要 分布式数据集成系统连接物理或逻辑上分布于不同位置的数据源，向用户提 供对这些数据源的一个综合全面的全局视图，同时负责对这些数据源的自动访问 和访问结果的集成。 分布式数据集成具有广泛的应用前景，例如因特网上商务信息的集成，集成 各个政府部门信息的面向公众的电子政务系统，企业之间以及企业各部门之间的 信息共享和协作都需要数据集成。 数据仓库、对等( p e e r t o p e e r ) 结构以及中介器结构都可以用于实现分布 式数据集成。本文以中介器结构数据集成为背景，重点研究了实现中介器上查询 处理的若干关键问题。作为后续内容的基础，本文首先介绍了构成数据集成系统 基本结构的全局数据模式、基于这个全局模式描述的每个数据源局部模式。随后 的内容在以下几方面展丌。 1 基于数据源的查询重写：本文的数据集成系统采用l a v 方式，数据 源被描述为基于全局模式的视图，因此可以通过查询重写技术构造 对全局查询的处理过程。查询重写技术来源于利用实化视图 ( m a t e z i a l i z e dv i e w ) 处理查询的需要。其算法复杂性龟括构造视 图与查询之间的变量映射和组合这些变量映射这商个相互独立的 n p 完全问题，现有算法往往通过简单的枚举检查所有可能的变量映 射和这些映射的所有组合，其结果是需要做很多无效或冗余的检查 和计算。本文针对这两个问题提出了在实现中的优化方法，在构造 视图与查询之间的变量映射关系时限定只产生不被包含的映射，并 且提出一种方法在特定情况下可以利用b a c h m a n 图按唯一的计算顺 序构造出所有不被包含的映射。在组合各种映射构造查询重写阶段， 本文提出的算法避免了对所有可能的映射组合的构造，而只组合和 检查能够覆盖当前查询所有子目标的奄询重写。此外，本文还针对 数据源具有查询能力约束或某些语义约束的情况改进了有关的算 法。 2 查询优化：分布式数据集成系统查询优化的目标与集中式数据库有 所不同。本文从降低网络数据流量和提高查询响应速度两个方面研 究优化问题。首先，在安排多个联接操作的顺序方面，本文证明了 以降低网络数据流量为优化目标时只需要考虑线性联接树构成的联 接顺序，但如果以提高查询响应速度为目的，则需要同时考虑包括 灌木型树在内的所有联接顺序，并提出了相应的算法。其次，在实 际环境中，数据源以及网络的性能在一定程度上是动态变化的，静 态的查询计划很难适应，但以往的研究几乎都忽视了这个问题。而 本文则提出了直接把联接计划的构造策略结合到查询执行过程中的 方法，能够根据网络的当前状况动态调整联接操作的执1 亍顺序。最 后，为了优化选择操作，本文提出了在数据源之间分配选择条件的 方法，能够尽量多地利用数掘源本地的处理能力以降低网络数据流 量和提高查询响应速度。 3 构造d a t a l o g 程序处理查嘲：在丌放世界假设下，为了得到尽量多 的查询结果并避免对相同数据源的重复访问，个更好的方法是把 复口人学博十学位论文 l a v 数据集成系统的查询处理 ! 查询过程表达为d a t a l o g 程序。采用d a t a l o g 程序的另一个优点是 可以在程序中包含对信息查询路径的利用，真正从全局上利用来自 所有数据源的信息处理查询。但在构造这种d a t a l o g 程序时，需要 保证数据的语义，避免构造出无意义的d a t a l o g 规则，这在以往的 有关工作中没有得到应有的重视。本文提出的算法在这方面做了增 强，并通过有关实验证明了这个算法的有效性。这种方法的一个缺 点是每处理一个新的查询，都需要重新构造数据源之间的信息查询 路径，但在一个数据集成系统中数据源是相对固定的，因此可以事 先建立好这种信息查询路径，并保存为有向图的形式，这样还可以 在一定程度上把构造d a t a l o g 程序的问题转换为图中的路径查找问 题。 本文最后介绍了一个初步的分布式数据集成系统体系结构，这个系统目前正 结合上海市洋山港信息系统的有关部分进行实施。 关键词：自治数据源，查询重写，绑定模式，查询计划，数据源能力，数据集成， d a t a l o g 程序，线性联接树，灌木型联接树，执行空间。 复咀大学博士学位论文 一一 生! 型! ! ! ! ! 型! ! ! ! ! 型! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! _ _ _ _ _ - _ _ _ - _ _ _ _ _ _ _ _ _ - _ _ _ _ - _ _ a b s t r a c t ad i s t r i b u t e dd a t ai n t e g r a t i o ns y s t e mc o n n e c t sd a t as o u r c e ss c a t t e r e d a c r o s sd i f f e r e n ts i t e s ，a n d p r o v i d e sa u t o m a t i c a l l ya c c e s s i n gt ot h e m a l s o ，i ti n t e g r a t e s t h eu n d e r l y i n gd a t as o u r c e si n t oa r e c o n c i l e da n du n i f i e dg l o b a lv i e w s u c has y s t e mm a yb e n e f i tm a n ya p p l i c a t i o n s ，i n c l u d i n gc o m m e r i c a li n f o r m a t i o ni n t e g r a t i o n s y s t e m so nt h ew e b ，g o v e r n m e n t a l i 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 sf o r t h ep u b l i c s ，a n d i n f o r m a t i o ns h a r ea n dc o o p e r a t i o ns y s t e m so f e n t e r p r i s e s d a t aw a r e h o u s e p e e r - t o p e e rs t r u c t u r ea n dm e d i a t o rs t r u c t u r ea r ea l lp o s s i b l ei m p l e m e n t a t i o nf o r d a t ai n t e g r a t i o n o u rw o r ki sb a s e do nam e d i a t o rs t r u c t u r es y s t e m ，c o n c e n t r a t e so ns e v e r a ik e y i s s u e sf o rt h eq u e r yp r o c e s s i n g a st h eb a c k g r o u n dk n o w l e d g ef o rr e l e v a n td i s c u s s i o n ，t h ep a p e r b e g i n sw i t ha ni n t r o d u c t i o no nt h ea r c h i t e c t u r eo ft h es y s t e m ，c o n c e r n i n gi t sg l o b a ls c h e m aa n d l o c a ls c h e m a s t h er e s tc o n t e n t sf o r mt h em a j o rp a r t so f t h ep a p e r ： 1 q u e r yr e w r i t t i n gb a s e do nd a t as o u c e s ：o u rs y s t e mi sc o n s t r u c ti nl a vs t y l e ，w h i c hd e s c r i b e s d a t as o u r c e sa sv i e w so v e rg l o b a ls c h e m a , s oq u e r yr e w r i t t i n gt e c h n i q u ec a nb eu s e df o rq u e r y p r o c e s s i n gh e r e q u e r yr e w r i t t i n gc o m e sf r o mt h er e q u i r e m e n to fa n s w e r i n gq u e r i e su s i n g m a t e r i a l i z e dv i e w s i th a st w oi n d e p e n d e n ts o u r c e so fc o m p l e x i t y ，o n ei sf i n d i n gm a p p i n g s b e t w e e nv i e w sa n dt h ec u r r e n tq u e r y , t h eo t h e ri sc o s t r u c t i n gr e w r i t t i n g sf r o mm a p p i n g s ，b o t h a r en pc o m p l e t e d p r e v i o u sw o r k ss i m p l ye n u m e r a t e da n dc h e c k e de a c hk i n do f p o s s i b i l i t i e s ， t h i sc a u s e dal o tu s e l e s sc o m b i n i n ga n dc h e c k i n gw o r k w ep r o v i d ea d a p t a t i o nt or e d u c et h e s e k i n d so fr e d u n d a n c y f o rm a p p i n g sb e t w e e nc u r r e n tq u e r ya n de a c hv i e w ，o u rm e t h o dn o t o n l yr e d u c er e d u n d a n tm a p p i n g s ，b u ta l s o m a k eu s eo fb a c h m a ng r a p h ，w h e nc e r t a i n c o n d i t i o ns t a t i s f i e d ，i tc a nh e l pt of i n dau n i q u eo r d e ro fc o m p u t i n gt h e s em a p p i n g s f o r f o r m i n gq u e r yr e w r i t t i n g s f r o mt h e s e m a p p i n g s ，o u rm e t h o do n l yg e n e r a t e s t h o s e c o m b i n a t i o n sc o v e r i n ga l ls u b g o a l so fc u r r e n tq u e r y t h ea l g o r i t h mi sf u r t h e ra d a p t e di nt h i s p a p e rf o rd a t as o u r c e sw i t hq u e r yc a p a b i l i t yl i m i t a t i o n s 2 q u e r yo p t i m i z a t i o n ：t h eg o a l so fq u e r yo p t i m i z a t i o ni nd i s t r i b u t e dd a t ai n t e g r a t i o ns y s t e ma r e d i f f e r e n tf r o mt h o s ei nt r a d i t i o n a ld a t a b a s es y s t e m w es t u d yt h eo p t i m i z a t i o no fj o i n o p e r a t i o na tf i r s t , f o ro r d e r i n gt h ee x e c u t i o no fs e v e r a lj o i no p e r a t i o n s w h e nr e d u c i n gd a t a f l o wi st h ea i m ，w ep r o v et h a to n l yl i n e a r j o i nt r e en e e dt ob ec o n s i d e r e d w h i l ef o ri m p r o v i n g t h es p e e do fq u e r y r e s p o n s e ，b o t hl i n e a ra n db u s h yj o i nl l e e ss h o u l db ei n c l u d e di nt h e e x e c u t i o ns p a c ef n ? q u e r yp l a ns e a r c h i n g t h ep e r f o r m a n c eo fe a c hd a t as o u r c ea n dt h e n e t w o r ka r ec h a n g i n ga l lt h e t i m e ，s t a t i cq u e r yp l a n sm a yn o ts a t i s f i yt h i sd y n a m i c e n v i r o n m e n t i ti si n c r e d i a b l e 。b u ts u c ha no b v i o u sp r o b l e mi si g n o r e di na l m o s ta l ip r e v o n s r e l e v a n tr e s e a r c h e s w ep r o p o s eaq u e r yp r o c e s s i n ga l g o r i t h mc o m b i n e dw i t ho p t i m i z a t i o n s t r a t e g i e s ，w h i c hc a na d j u s tt h eq u e r yp r o c e s sa c c o r d i n gt h ec u r r e n ts t a t eo ft h en e t w o r k e n v i r o n m e n t t h eo t h e rm a j o rp a r to f q u e r yo p t i m i z a t i o ni sf o rs e l e c t i o no p e r a t i o n ，w ei n v e n t am e t h o dt od i s t r i b u t es e l e c t i o nc o n d i t i o no fc u r r e n tq u e r ya m o n gd i f f e r e n td a t as o u r c e s ， w h i c hc a nm a k eu s eo fl o c a lc a p a b i l i t yo f e a c hd a t as o u r c ea sm u c ha sp o s s i b l e 3 。c o n s t r u c t h a gd a t a l o gp r o g r a mf o rq u e r ya n s w e r i n g ：t og e ta sm u c hd a t as a r i s f i n ec u r r e n tq u e r y a sp o s s i b l e ，w eh a v et op r o c e s sa l lt h eq u e r yr e w r i t t i n g s ，t h i sc a u s eal o tr e p e a ta c c e s s i n gt o s a m ed a t as o u r c e s b e t t e rm e t h o di st oc o n s t r u c tad a t a l o gp r o g r a mf o r t h eq u e r yp r o c e s s i n g a n o t h e ra d v a n t a g eo ft h i sm e t h o di st h ep r o g r a mc a nm a k eu s eo fw h a tw ec a l l e dq u e r y i n f o r m a t i o np a t ha m o n gd i f f e r e n td a t as o u r c e s t h em a j o rc o n t r i b u t i o n so fo u ra l g o r i t h mi so n 复火学博士学位论文 q u e r yp r o c e s s i n go fl “d a t ai n t e g r a t i o ns y s t e m s e m a n t i cc o r r e c t n e s so fe a c hg e n e r a t e dd a t a l o gr u l e ，t h i sw a sl a r g e l yi g n o r e di nt h ep r e v i o u s w o r k s r e l e v a n te x p e r i m e n t ss h o w i n go u rm e t h o dc a nr e a l l yr e d u c et h i sk i n do fm e a n i n g l e s s d a m l o gr u l e s as h o r t a g ei st h a tt h er e l a t i o n s h i p sa m o n gd a t as o u r o e sh a v et ob er e c o n s t r u c t e d e a c ht i m ew h e nan e wq u e r yi s p r o c e s s e d ，t h i si su n n e c e s s a r y , s i n c et h ed a t as o b r c e s i n t e g r a t e di nas y s t e mi s n o ta l w a y si nc h a n g i n g ，s ot h e i rr e l a t i o n s h i pc a nb ec o n s t r u c t e da n d s a v e da s ad a gi n d e p e n d e n tf r o me a c hq u e r y , w h i c hc a r lb eu s e dt oh e l pt h eg e n e r a t i n go f t h e d a t a i o gp r o g r a m t h i sp a p e ri sc o n c l u e dw t i hat e n t a t i v ed e s i g no fo u rd i s t r i b u t e dd a t ai n t e g r a t i o ns y s ：e m ，w h i c hi s g c 嘲gt ob ei m p l e m e n t e da sp a r to f s h a n g h a iy a n g s h a nh a r b o u ri n f o r m a t i o ns y s t e m k e yw o r d s a u t o n o m o u sd a t as o u r c e s ，q u e r yr e w r i t i n g ，b i n d i n gp a t t e r n ，q u e r yp l a n ，d a t as o u r c e c a p a b i l i t y , d a t ai n t e g r a t i o n ，d a t a l o gp r o g r a m ，l i n e a r j o i nt r e e ，b u s h y j o i nt r e e e x e c u t i o i ns p a c e 复丑大学博士学位论文 第一章绪论1 1 1 数据集成系统 第一章绪论 随着网络技术，特别是i n t e r n e t 和w w w 的发展，信息查询受到越来越多的 关注，随之产生了各种搜索引擎( s e a r c he n g i n e ) 或基于静态w e b 页面和其中链 接关系的信息收集和检索系统”，为人们在网络环境下查找信息提供了很多便 利，提高了网络信息的利用效率。目前搜索引擎的一般工作过程是根据用户输入 的关键字在搜索引擎服务器的数据库中对事先从各个网站收集到的信息内容进 行扫描，当发现关键字匹配以后，将相应的u r l 返回给用户，由用户自己按这些 u r l 逐一访问各个w e b 页面。搜索引擎的这种工作方式导致了一系列问题：首先， 搜索引擎的数据库中存放的信息是在几小时或几天其至几个月以前被收集的，实 际页面中的内容可能已经改变。用户需要自已访问相应的u r l 才能得到最新的信 息。第二，搜索引擎服务器中存放的主要是静态w e b 页面的内容，无法反映动态 发布的信息。但动态信息却是w w w 上越来越重要的部分。第三，由于只是进行关 键字的字符串匹配，搜索很不精确，返回的u r l 常常会很多，以至用户经常只能 以猜测的方式选择其中一些进行访问，或者侥幸找到需要的信息，或者不得不放 弃搜索。搜索引擎不能满足数据集成系统要求更主要的原因在于搜索引擎简单地 把所有的数据都看作文本，对它们做各种字 守串的匹配运算，不能进行跨越数据 源的数据比较和运算。例如不能处理像“查找作者a 发表的被e i 索引的论文的 内容”这样对一般数据库而言非常普通的查询。 定义1 1 ：分布式数据集成系统把来自不同数据源的数据综合成统一的全局 视图，这些数据源可以是自治的，并分布在不同的物理位置。 查询处理是数据集成系统的基本功能，由于具体的数据分布在不同的数据源 中，回答一个查询可能需要访问多个数据源，比较并合成来自这些数据源的数 据，因此数据集成的功能要远远超过搜索引擎。例如现有的一个数据源d 。可以 根据论文的标题查找对应的论文内容，数据源d 2 提供e i 索引信息，可以根据作 者姓名查询他所发表的被e i 索引的论文的标题，为了回答“查找作者a 发表的 被e i 索引的论文的内容”这样一个查询，数据集成系统会自动地先访问d ：找到 作者a 发表的被e i 索引的论文的标题，根据这些标题查询d 。得到论文的内容， 合成访问这两个数据源得到的数据作为对用户查询的回答。 数据集成可以有多种方法，例如以本地计算为主的数据仓库方式，这种方式 通常要周期性地把各个数据源的数据收集到数据仓库本地，按某种粒度进行概 括，而对于用户查询的响应则主要是通过对数据仓库本地数据的查询和计算实 现。这种方法主要适用于数据源和应用需求相对稳定的环境。 以分布式计算为主的中介器( m e d i a t o r ) 或代理( a g e n t ) 方式是另一种常 见的数据集成途径。这种方式通常不在中介器本地保存实际的数据内容，用户的 查询被转发给各个数据源处理，这种方式主要应用于自治数据源的集成，可以适 应数据源变动频率较高的情况。 复垦大学博十学位论文 第一章绪论 在像w w w 这样的分布式信息系统中，虽然各数据源内部的信息通常都是按某 种结构组织的，但由于各种原因，例如服务对象、信息来源或语言文化等因素的 不同，并不存在所有信息源通用的信息组织结构。 例如同样都是提供论文的信息，数据源d 可以根据作者姓名查询论文的标 题，发表日期，内容等信息，并且把这些数据组织成关系型数据记录。而数据源 d ：则只提供论文的标题，作者姓名等索引信息，不提供论文的内容，并且把这些 数据组织成用h t m l 表达的半结构化数据。 可以有两种方法集成这些按不同信息结构组织起来的数据源，一种是在这些 数据源的两两之间建立映射关系。例如文献。“”1 中建议在数据源之间建立对等 的点到点( p e e r - t o - p e e r ) 映射和翻译关系。其主要依据是认为数据源的管理者 倾向于点对点的数据翻译和传输，用户则只要访问它们所熟悉的数据源，由这些 数据源根据自身的数据并通过点对点的翻译关系从其它数据源收集信息响应给 用户。 这种点对点的方式虽然具有其自身的特点并在一定程度上具有应用价值，但 从数据集成的角度看是有缺点的。假设存在n 个数据源，如果要实现数据的充分 集成，就必需在这r 1 个数据源的每两个之间建立映射关系，总共要建立的映射关 系是n ( n 一1 ) 个，当一个数据源改变了它的信息结构后，就需要修改它与其它( n 1 ) 个数据源之间的映射关系，这样，数据源之间的映射关系无论是最初的构造还是 以后的维护都很复杂。另一方面，如果不建立这么多的映射关系，那么有些数据 源之间的信息传递就需要通过一个或多个中间数据源，导致信息传递成本的上 升。 另一种方式是基于全局模式的数据集成框架，这种形式的数据集成系统通过 中介器集成一组数据源，在中介器中包含了一个全局模式、一组数据源接口、以 及全局模式和数据源模式之间的映射关系。 1 2l a v 和6 a v 数据集成 般意义上，一个具有特定模式s 的数据库d b 是一个集合，d b 中的每个元 素本身又是一个集合并且对应于模式s 中的个元素。例如在关系模型中，数据 库的一个关系( 出元组构成的集合) 对应于s 中的一个关系模式：在面向对象模 型中，数据库的一组同类对象对应于s 中的一个类。 全局模式是数据集成系统的基础，实际的数据保存在具体的数据源中。在一 个数据集成系统中，每个数据源都有自己的数据模式，在中介器上所有的数据源 模式都被集成到一个全局模式上，这是通过在数据源的局部模式和整个系统的全 局模式之间建立映射关系实现的，全局模式以一种容易被用户理解的方式提供整 个系统完整的视图。 定义1 2 ：全局模式g 由字符集凡上的语言k 表达，g 中的每个元素在字 符集扎中都有一个对应的表示符号( 例如当g 是基于关系模式时，关系就是a 。 上的一种元素，如果g 是面向对象的模式时，类就是扎上的一种元素) 。“2 。”1 每个具体数据源则用一个数据源模式描述。 定义1 3 ：数据源模式s 由字符集凡上的语言l s 表达，s 中的每个元素在 复咀大学博士学位论文 2 第一章绪论 字符集a s 中都有一个对应的表示符号。“”2 建立具体数据源和全局模式之间的映射关系有两种基本途径 一g a v ( g l o b a l a s v i e w ) 和l a v ( l o c a l - a s v i e w ) 。g a v 基于实际数据源描述全局 模式，对全局模式g 中的每个元素g 建立映射关系g 一 q 。，这里q 。表示对具体数 据源集合s 的查询。而l a v 则以独立于数据源的方式表示全局模式，对具体数据 源集合s 中的每个元素s 建立映射关系s 一 q ，这里q c 表示对全局模式g 的查询。 表面上，这两种方式只是映射方向上的不同，却导致了查询能力和处理查询 在复杂性方面的差异。在g a v 方式下，回答一个查询只需要对用户发出的查询简 单地用具体数据源孵视图做扩展，把用户查询翻译为对具体数据源的查询。在 g a v 中隐含了确切视图( e x a c tv i e w s ) 的假设，这样容易表达全局模式和数据 源之间的映射关系，也容易进行查询处理。由于g a v 相对于l a v 的简单性，很多 系统都采用了g a v 的方式，例如t s i m m i s “”1 ，g a r i i c ”6 研”1 。而l a v 方式 则需要较为复杂的查询重写技术，因为l a v 方式中描述具体数据源的视图在查询 处理时需要被反向使用，而这并不是一个简单的映射关系的反转。但l a v 却比 g a v 具有更大的灵活性，例如在全局模式上有一个类s t u d e n t ( s n o ，c n o ) ，表示一 个学生的学号和班级号，在某个具体数据源上提供了同学关系 c l a s s m a t e ( s n o ，s n o z ) ，如果按照l a v 的方式，可以把同学关系数据源表示为： c l a s s m a t e ( s n o i ，s n o ：) ：一s t u d e n t ( s n o i 。c n o ) s t u d e n t ( s n o z 。c n o ) 如果需要查询学号为0 0 1 的学生的同学的学号，查询表达式如下： s t u d e n t ( “0 0 1 ”，c n o ) s t u d e n t ( s n 0 2 ，c n o ) l a v 数据集成系统可以立刻发现数据源c l a s s m a t e 能够回答这个查询，从而 把这个查询转发给这个数据源处理。 相反，如果是g a v 方式，由于是用具体数据源的视图来描述全局模式上的类， 全局模式上的s t u d e n t 被描述为： s t u d e n t ( s n o l ，n u l l ) ：一c l a s s m a t e ( s n 0 1 s n 0 2 ) s t u d e n t ( s n 0 2 ，n u l l ) ：一c l a s s m a t e ( s n o i ，s n o z ) 原来的s n o ，和s n o ：之间的c l a s s m a t e 关系在这个描述中就丢失了，也就无 法回答给定学生学号查找其同学的查询。 因此，对于一个具有良好构造的稳定的全局模式而言，l a v 应该是比g a v 更 好的选择a 而且，采用l a v 方式的系统具有良好的可扩展性，增加一个新的数据 源只要增加相应的映射描述，不需要其它的修改。 基于上述考虑，本文采用l a v 方式来描述全局模式和数据源之间的映射关 系a 这样，用户所面对的全局模式是一个综合、一致的视图，用户可以针对这个 视图提出查询，系统则根据全局模式与具体数据源的局部模式之间的映射关系， 把用户查询翻译成对具体数据源的查询，然后合成来自这些数据源的返回结果作 为查询响应。 1 3l a v 数据集成系统的基本结构 采用l a y 方式的数据集成系统通常是两层结构，一层是中介器( m e d i a t o r ) ， 另一层由包装器( w r a p p e r ) 。”删构成。中介器需要进行跨数据源的查询 处理，当然- 中介器并不直接访问这些数据源，而是通过数据源的包装器访问。 中介器的作用主要在于解决分布式数据源集成时的两个问题：一是在单独的w e b 复曩大学博十学位论文3 第一章绪论 4 站点中的数据可能是不完整的，例如在e i 索引数据源中就没有包含论文的内容。 另一个问题是数据源查询能力的差异，不同的数据源能够处理的查询是不同的， 例如有的数据源能够接受按论文标题查询论文，而另一些数据源则能够接受按作 者姓名查询论文。为了解决第一个问题，要求中介器可以访问多个数据源综合出 全面的信息。而对于第二个问题，则要求中介器能够根据这些数据源的能力访问 它们。 包装器为每个数据源( 例如一个w e b 站点) 提供一个接口，这个接口通常会 把数据源中的数据按特定的结构输出e 在w e b 这样的环境中集成各种数据源面临 着多种困难，其中包括数据源之问在信息结构上的不同【b h ”i s s r l 9 9 4 1 1 c a ”l ，例如 有的数据源采用分类层次结构，而另一些数据源则采用表格形式表示数据。还有 就是在词汇上的不一致，不同的数据源可能用不同的词汇代表相同的概念，例如 表示教学用的教材时，有的数据源用“教材”这个词，而另一些数据源则用“课 本”这个词，虽然用词不同，但含义则是一样的。词汇上的不一致还可能表现为 在不同数据源中的相同词汇代表了不同的含义，例如“计算机”，可能在有些数 据源中表示个人电脑，而在另一些数据源中则可能泛指所有各种计算机。 已经有很多工作是针对包装器的，由于本文的重点不在于为数据源构造包装 器，因此只在第2 章中简单介绍包装器及其描述，第2 章还简单介绍了本文讨论 的数据集成系统中全局模式的构造，以及包装器输出的数据模式与全局数据模式 之间的映射关系。 1 4 中介器 本文的重点集中在中介器功能的实现，特别是当用户发出查询以后，中介器 怎样根据系统中现有的数据源描述构造对于当前查询的处理方法，包括对原有查 询的重写以及这些重写的优化执行。 由于关系数据模型具有很强的表达能力和逻辑功能，而且现有大量的应用程 序都是以关系数据库为核心的，关系数据库的模式和查询表达已经为大部分用户 所接受和熟悉，采用关系模型的数据集成系统既可以建立与其它数据模型的映射 关系“”，又可以与基于关系模型的系统顺利衔接。 ，一 查询重写是利用各个数据源处理全局查询的关键，现有的查询重写技术来源 于利用实化视图处理查询的需要。其算法复杂性来源于两个阶段1 ，即构造 视图与查询之间的变量映射和对这些视图进行组合。由于这是两个相互独立的 n p 完全问题，现有的算法往往简单地采用枚举方法检查所有可能的组合”“， 需要检查很多无效或冗余的组合。通过对这两个阶段的分析，本文提出了相应的 算法，可以减少这些冗余或无效组合的产生，特别是在构造视图与查询之间的变 量映射关系时，可以利用变量映射之间的包含关系剔除冗余的变量映射，进一步 还可以利用b a c h m a n 图在特定情况下按唯一的计算顺序构造各种组合，从根本上 避免冗余变量映射的产尘。在构造查询重写阶段，本文的算法只产生能够覆盖当 前查询所有子目标的组合，从而减少了所要检查的组合的数量。此外，不同于一 般的视图，有些数据源只能接受特定的查询输入，因此在构造查询重写时还需要 考虑是否存在能够满足数据源查询能力的访问顺序“”“”m “1 。考虑到数据 源之间还可以相互提供查询数据，可以先根据数据源之间的关系以及查询条件确 定当前可查询数据源及其查询方法，然后将当前可查询数据源作为普通意义上的 视图构造重写。 复旦大学博士学位论文 4 第一章绪论 由于在网络环境中，查询优化的目标有所改变，本文针对降低网络数据流量 和提高查询响应速度这两个方面考虑多个联接操作之间的执行顺序的优化，证明 了当仅仅考虑降低网络数据流量时，可以把查询计划限定在线性联接树构成的执 行空间中，而当以减少响应时间为目的时，因为在分布式环境中每个数据源都有 独立的处理能力，很多工作可以由多个数据源并行完成，所以也需要把灌木型联 接树包含在所要搜索的查询执行计划空间中，并提出了相应的查询计划构造算 法。由于网络以及各数据源的性能都可能随着负载等因素动态改变，静态构造的 查询计划未必能够适应这种变化，因此本文提出了一种将优化策略结合到查询执 行过程中的方法。选择操作也是查询优化需要考虑的重要部分，本文提出了选择 条件在数据源之间的分配方法，能够充分利用数据源本身的处理能力，降低网络 数据流量并提高查询响应的速度。虽然联接操作仍然是查询代价的主要部分，但 在分布式环境中联接操作的执行方式已经发生了变化，需要通过对数据源的循环 访问实现，本文对联接操作本身也做了优化，通过实验证明了其有效性。 当需要尽可能多地得到符合查询条件的数据时，可以执行全部的查询重写， 但这会导致对一些数据源的重复访问。另外由于数据源之间的数据是相互关联 的，查询一个数据源所需要的条件可以从其它数据源得到。可以构造回答查询的 d a t a l o g 程序来解决这个问题，但在利用与当前查询没有直接变量映射关系的数 据源时必须保证构造出的d a t a l o g 规则的语义正确性，本文的算法在这方面比现 有的其它算法做了较大改进：实验证明它可以大大减少无效或冗余的d a t a l o g 规则。由于每次为一个查询生成d a t a l o g 程序都需要重新构造数据源之间的关 系，但在一个数据集成系统中的数掂源是相对固定的。可以事先建立数据源的关 系，并保存为有向图的形式，把构造d a t a l o g 程序的问题转换为图中的路径查找 问题，避免每处理一个查询都要为各个数据源的查询条件重新构造查询重写。 1 5 本文内容安排 本文考虑的核心问题是：给定基于全局模式的数据源和查询的描述，寻找可 能的查询方法，通过对数据源的访问以及对访问结果的综合和附加处理，回答给 定的查询。第2 章到第7 章的内容安排如下： 第2 章主要介绍了对于数据源的包装和描述方法，全局和局部模式的构造以 及它们之间映射关系的表达。 第3 章讨论了利用查询重写的方法进行查询处理，讨论的问题包括怎样构造 数据源和当前查询之间的变量映射，考虑了数据源查询能力限制的查询重写构造 方法，数据源查询能力可变以及包含内置谓词情况下查询重写的构造， 第4 章为数据集成系统的查询工作建立了初步的执行代价模型，在此基础上 提出了以降低网络数据流量和减少响应时间为目的的查询执行计划的优化算法。 考虑到网络环境的特殊性，还提出了一种能够根据网络当前状态动态调整访问数 据源顺序的查询算法。 第5 章从另一个角度研究了数据集成系统的查询处理问题，也就是构造 d a t a l o g 程序用于一个查询的处理，其中特别考虑了利用不同数据源的数据内容 之间的关系为具有查询能力限制的数据源构造查询条件的方法。在语义正确性方 面对现有方法做了改进。为了减少构造d a t a l o g 程序的工作量，提出了一种用于 表达数据源的数据内容之间关系的有向图模型。 复且大学博士学位论文 第一章绪论 第6 章简单介绍了一个实际的数据集成原型系统的基本体系结构。 第7 章是全文的总结和未来研究工作的展望。 复q 大学博士学位论文 6 第二章全局模式和局部模式 第二章全局模式和局部模式 作为后续章节的基础，本章从数据模式角度介绍全局模式、数据源模式、全 局模式和数据源模式之间映射关系的构造和描述。 2 1 相关工作 在文献 k l s s l 9 9 5 中介绍的系统采用了l a v 映射模式，用描述逻辑 ( d e s c r i p t i o nl o g i c ) 表达全局模式，采用合取查询作为查询语言。类似的工 作还有很多”“”“”“，但处理查询的方法比较简单，没有考虑数据源与当前查 询之间变量映射较为复杂的情况以及数据源的查询能力等问题。 也有很多其它的描述体系，例如文献 v p l 9 9 7 提出了一种表达能力非常强的 描述数据源能力的语言。文献 m f k 2 0 0 1 介绍了一个系统，用x m l 描述全局模式， 并采用x m l 表达用户查询和数据源与全局模式之间的变量映射。此外，还有一些 具有自身特点的信息集成系统“”，其中采用的描述方法往往与特定的系统实 现有较为紧密的关系，不容易应用于其它环境。 文献 l e n 2 0 0 2 较为全面地介绍了目前在数据集成方面开展的工作和取得的 成果。 对w w w 信息的描述和集成是目前的研究热点之一呻”“”“”呻”。 目前受到广泛关注的w e b 服务也可以被认为是对w 啊信息描述和集成的一个方 向，僵目前都还只能适应简单的应用。其关键技术包括w e b 资源描述语言，统一 描述、发现和集成结构以及简单对象访问协议等。 w e b 资源描述语言( w s d l ) ”。州是一种基于x m l 的网络服务描述语言，把 网络服务描述为一组对包含文档或过程信息的消息进行操作的终点( e n d p o i n t ) 。 操作和消息以抽象的方式描述，并与具体的网络协议和消息格式结合来定义一个 终点。相关的终点被组合成抽象的终点( 或服务) 。w s d l 具有可扩充性，允许以 与具体网络协议或消息格式无关的方式描述终点。w s d l 更多地是把每个w e b 资 源看作一个功能点，但要描述输入输出数据之间的语义关系仍然很困难。 统一描述、发现和集成( u d d i ) ”1 是一个开放项目，其目的是使企业能够 互相发现，并在一个全球目录体系中通过因特网互相联系和共享信息。u d d i 同 时也是一个集成w e b 服务的框架，包括了基于标准的服务描述和发现。u d d i 规 范利用了w 3 c 和i e t f 的有关标准，如x m l 、h t t p 和d n s 协议。另外，还通过采 用s o a p 协议，提供跨平台的编程能力。u d d i 更多地起到了目录服务的作用，但 不容易表达全局模式的语义。 与本文工作有关的其它重要研究领域还包括信息元数据和网络资源描述。元 数据( m e t a d a t a )