（计算机应用技术专业论文）xml模式映射的建立、维护以及复合技术研究.pdf

论文摘要 作为一种共享异构数据源的途径。数据集成系统有着广泛的应用需求。模式映射是数据集成系 统的重要组成，通常由视图定义( 查询) 语言表示，它描述了不同模式之间的数据是如何转换的，是 系统实现查询重写和数据转换的重要依据。在系统能够运行之前，用户( 系统管理员) 必须在给定模 式之间建立这样的映射关系；另一方面。当模式、或者应用需求发生变化时，用户还必须对原来的 模式映射进行相应的维护。由于不同模式之间在结构、语义上都存在差异，因此映射的建立和维护 任务十分的烦琐复杂。当前已经有一些技术能够以半自动的方式来辅助用户处理这些任务，但是由 于这些技术的自动化程度等诸多因素，用户仍然不可避免的需要直接以手工方式来处理这些复杂的 映射表达式。本文以x m l 数据集成为背景，提出了一种称为m a c o r q 鱼撇c o r r e l a t i o n ，映射 关联) 的映射表示模型。与直接用查询语句来表示模式映射的方式相比，m a c o r 模型将映射表示成很 多简单的原子映射，这些原子映射由关联关系连接在一起，著构成树结构。m a c o r 模型为用户处理 映射任务带来了方便：对于映射的建立问题用户可以从简单的原子映射开始，逐步将它们组装成 复杂的全局的映射关系，这种由简到繁的处理方式，使得m a c o r 模型特别适合于解决复杂模式之间 的映射问题；对于模式映射的维护问题，用户可以修改局部的原子映射或者关联关系而保留和复 用映射的其余部分。我们区分了x q u e r y 查询语言的一个子集( 称为c o x q ) ，并以此分析了m a c o r 模型的表达能力。进一步。我们介绍了如何在m a e o r 模型的实现框架中结合当前一些半自动的映射 技术，以辅助用户处理m a g o r 映射。 在大规模的数据集成系统( 如p d m s p e e r 数据管理系统) 中不同结点之间的模式映射形成映 射链，其长度和数量都十分可观。根据映射链，系统以一种递归的方式处理用户提交的查询这种 查询处理方式的性能十分低，为此映射复合( m a p p i n g c o m p o s i t i o n ) 技术被用来预先计算出与映射链等 价的复合映射( c o m p o s e dm a p p i n g ) 。根据复合映射，系统能够将用户查询直接重写为各相关结点的 数据源查询。从而提高查询效率。然而映射链中任意一个映射的变化都将导致复合映射的更新维 护。当前并没有这方面的技术，只能采用重新复合计算的方法，严重影响了系统的可伸缩性。这是 因为一方面在w e b 这样的动态环境中，系统中任何一个映射都有可能随时发生变化；另一方面，对 于大规模的数据集成系统，一个映射的变化又可能影响到众多映射链的复合映射。基于前文的m a c o r 映射模型，本文提出了一种复合映射的增量维护技术。与其它复合技术不同，m a t o r 映射的复合计 算可以分解为原子映射之间的复合计算。因此在映射链的复合计算过程中，分属不同映射的各原子 映射之间存在一种复合路径轨迹我们以复合路径图( c o m p o s i t i o n p a t h g r a p h ) 记录这些轨迹当映射 链中某个映射发生变化时就能根据复合路径图来确定整个映射链中有哪些原子映射受到影响，从 而将完全重新复合计算的维护方法转化为复合计算这些原子映射的增量维护方法。算法分析和实验 结果表明，这种增量维护技术的效率不仅与映射本身的变化相关，还与映射链的长度有关。当映射 链的长度越长增量维护的方法就可能退化为完全维护的方法，但是当我们额外存储一些中间复合 结果后，可以消除映射链长度对增量维护效果的影响。 关键字：模式映射；映射模型；复合映射；增量维护；x m l ；x q u e r y ；数据集成 东南人学博l + 学位论立 a b s t r a c t n o w d a y s ，t h e r ei sar a p i dg r o w t ho fr e q u i r e m e n t sf o ri n t e g r a t i n g ，e x c h a n g i n ga n dt r a n s f o r m i n gd a t as t o r e di n d i f f e r e n th e t e r o g e n e o u ss o a l c e s s u c had a t ai n t e g r a t i o ns y s t e mu s e ss c h e m am a p p i n g st os p e c i f rh o wd a t a i n s t a n c e so v e ro n es c h e m ac o r r e s p o n dt od a t ai n s t a n c e so v e ra n o t h e r g e n e r a l l y d e s c r i b e di ns o m eq u e r y l a n g u a g e ， ；e h e m am a p p i n g sa r eu s e dt ou n f o l do rr e w r i t eau s e tq u e r yo v e rt h et a r g e ts c h e m ai n t os u b - q u e r i e s o v e rt h es o u r c es c h e m a s ，o rt r a n s l a t ed a t af r o mt h es o u r c e sj n t ot h et a r g e td a t a b a s e s t oe n a b l ed a t as h a r i n g , t h e u s o r 口t h es y s t e mm a n a g e rh a st of i r s tc o n s t r u c tt h es e m a n t i cm a p p i n g sb e t w e e nt h et a r g e ta n dt h es o u r e e s c h e m a s a l s o ，a st h ea p p l i c a t i o nr e q u i r e m e n t so rt h es c h e m a sc h a n g e ，t h eu s e rh a st om a i n t a i na n dm o d i f yt h e e a r l yc o n s t r u c t e dm a p p i n g s d u et ot h es t r u c t u r a la n ds e m a n t i cd i s c r e p a n c i e se x i s t i n gi nd i f f e r e n ts c h e m a s 。b o t h t h ep r o c e s s e sb y el a b o r - i n t e n s i v ea n de r r o r - p r o n e t h 伽昌l lan u m b e ro ft u n i sh a v er e c e n t l yb e e nd e v e l o p e dt o a s s i s tt h eu s h e ri ns u c hp r o c e s s e sb ys e m i a u t o m a t i c a l l yd i s c o v e r i n gm a p p i n g so ri x e s e r v i n gt h e i rs e m a n t i c sa s s c h e m a se v o l v e , i np r a c t i c ei ti ss t i l li n e v i t a b l ef o rt h e s e rt om a n u a l l yc o n s w u c la n dm a i n t a i nt h em a p p i n g s w h i l ec u r r e n t l yt h e s em a p p i n g sa r cm a i n l yr e p r e s e n t e da st r o u b l e s o m ee x p r e s s i o n s f o c u s i n go nx m l - b a s e d d a t ai n t e g r a t i o n , t h i sp a p e rp r o p o s e sam a p p i n gm o d e lc a l i e dm a c o rm ( 丛_ a p p i n g c o r r e l a t i o 帕c o m p a r e dw i t h q u e r ye x p r e s s i o n ，m a n o rm o d e l sam a p p i n ga san u m b 日o fs i m p l e ，p a r t i a la t o m i cm a p p i n g s 。w h i n ha l e c o r r e l a t e du s i n ge x p l i c i tc o r r e l a t i o n sa n da r eo r g a n i z e di n t oat r e e m a c o rf a c i l i t a t e sd e a l i n gw i t hm a p p i n g s t o c o n s t r u c tam a p p i n g t h emc a l lf n s ti n d e p e n d e n t l yc o o s t r u c ta t o m i cm a p p i n g s a n dt h e n i n c r e m e n t a l l y c o r r e l a t et h e mu s i n gt h ec o n - e l a t i o n s s u c hf l e x i b i l i t yi nm a p p i n gc o n s t r u c t i o nm a k e sm a w ra d a p tw e l lt o c o m p l e xa p p l i c a t i o n s o nt h eo t h e rh a n d 。i nm a i n t a i n i n go rr e f i n i n gm a p p i n g s ，m a r o rm a k e si tp o s s i b l et ol o c a t e m o d i f i c a t i o n st os u b - m a p p i n g s a n dr e m a i na n dr e u s eo t h e rp a r t so ft h em a p p i n g s u s i n gaf r a g m e n to fx q u e r y c a l l e dc o x q ，w ec h a r a c t e r i z et h ee x p r e s s i v e n e s so fm a c o r f u r t h e r , i ni m p l e m e n t a t i o nw ed i s c u s saw a yt o c o m b i n em a c o rw i t hc u r r e n ts e m i - a u t o m a t i cm a p p i n gt e c h n i q u e s i nl a r 擘e - a l ed a t ai n t e g r a t i o ns y s t e m e g p d m s ( p e e rd a t am a n a g e m e n ts y s t e m ) 。t h em a p p i n g sb e t w e e n d i f f e r e n tp e e r sf o r mm a p p i n gc h a i n s n e i rl e n g t ha n dn u m b e rm l a r g e ，a l o n gw i t ht h em a p p i n gc h a i n s 。t h e s y s t e mr e e t t r s i v e l ya n s w l ：l st h eu s e rq u e r y y e tt h i s 廊i p l eo fq u e r ya n s w e r i n gi si n e f f i c i e n t , a n dat e c h n o l o g y c a l l e dm a p p i n gc o m p o s i t i o ni si n t r o d u c e dt op r e e o m p u t eac h a i no fm a p p i n g sa n dd e r i v ea l l e q u i v a l e n t c o m p o s e dm a p p i n g w h i c hc a l lb eu s e dt od i r e c t l yr e w r i t et h eu s 盯q u e r yi n t oq u e r i e so v e rr e l a t e dp e e r s h o w e v 盯, a nu p d a t et oa n ym a p p i n gi nt h ec h a i nw i l lr e s u l ti nm a i n t e n a n c eo ft h ec o m p o s e dm a p p i n g c u r r e n t l y t h eo n l ys o l u t i o nt os u c hap r o b l e mi sc o m p l e t e l yr c e o m p u t i n gan e w - c o m p n s e dm a p p i n g ，n i sm a k e sal o s so f s y s t e ms c a l a b i l i 斜：i nd y n a m i ce n v i r o n m e n tl i k et h ew 曲a n ym a p p i n gm a yc h a n g e sa ta n y t i m e ；o nt h eo t h e r h a n d ，ac h a n g eo fm a p p i n gm a ya f f e c t sm a n yc o m p o s e dm a p p i n g si nt h es y s t e m b a e do n0 1 1 1 m e c o rm o d e l w e p r o p o s ea ni n e t _ e m a n ta p p r o a c ht om a i n t a i n i n gc o m p o s e dm a p p i n g s w 岫m a c o r , m a p p i n gc o m p o s i t i o nc a nb e c o m p l e t e da t t h e l e v e lo f a t o m i c m a p p i n g s i n c o m p u t i n g t h ec o m p o s e d m a p p i n g o f ac h a i n w er e c o r d i na c p g ( c o m p o s i t i o np a t hg r a p h ) t h et r a c ko fc o m p o s i n gt h ea t o m i cm a p p i n g s a sar e s u l t , w h e nam a p p i n gc h a n g e s t h ea f f e c t e da t o m i cm a p p i n g s ，i n d i c a t e db yt h ec p g c a r tb el o c a t e di nt h ec h a i n ，a n dt h e nt h ec o m p o s e d m a p p i n gc a nb em a i n t a i n e di n c r e m e n t l yi nt e r m so ft h el o c a t e da t o m i cm a p p i n g s b o t ht h ea l g o r i t h ma n a l y z a t i o n a n dt h ee x p e r i m e n t ss h o wt h a tt h ee f f e c t i v e n e s so ft h ei n c r e m e n t a la p p r o a c hi sd e c i d e dn o to n l y b yt h ec h a n g e i t s e l fb u ta l s ob yt h el e n g t ho ft h em a p p i n gc h a i n ，a st h ei n c r a s e m e n to ft h em a p p i n gc h a i n ，t h ee f f e c t i v e n e s s d e g e n e r a t e s y e ti f m e d i a t a dc o m p o s i t i o n sa l ea d d e dt ot h ec p g ，t h i sd e g e n e r a t i o nw i l lf a d ea w a y k e yw o r d s ：s c h e m am a p p i n g ；m a p p i n gm o d e l ；c o m p o s e dm a p p i n g ；i n c r e m e n t a lm a i n t e n a n c e ；x m l ； x q u e r y ；d a t ai n t e g r a t i o n 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 研究生签名：这i 塑日期：丛夕j ， 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和 电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内 容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：这主因导师签名： 第一苹前苦 1 1 研究背景 第一章前言 在信息化普及和推进的过程中，记录产生了大量的数据它们以不同的形式分布在不同的系统 中如何方便的访问、使用、共享这些数据，进而提高对数据资源的综合利用、综合查询能力已 经成为当前以及今后社会迫切需要解决的问题。这种综合多个数据源的信息需求不仅来自一个企业 或一个行业内部，还来自不同企业、不同行业之问。 比如在企业信息化建设中，象c r m 、e r p 、信息门户网站以及商务智能解决方案无疑加速了企 业的发展步伐。但是企业的信息可能以不同的形式存放在不同的地方对它们的访问方法也不尽相 同，因此对信息的综合查询和利用也变得极为复杂。再比如在电子政务领域，由于技术、业务、需 求，经费和管理等方面的问题，加上时间和历史等原因造成了各系统的开发平台不同、操作系统 不同，特别是数据库管理系统千差万别，形成了一个卟信息孤岛面对分散的、异构的数据源和系 统，如何为信息需求者屏蔽掉所有这些复杂特性。从而提供给用户单一的数据映像? 如何实现其中 的集成、转化以及统一的访问接口? 已经成为现代企业信息化建设、提高各类电子政务应用水平所 面临的关键问题。 有关数据的集成、共享问题，近年来的研究和应用做了大量的工作，其研究范围从规则的数据 库数据，发展到了不规则的半结构( 如x m l ) 、甚至无结构的数据，并先后提出了象联邦数据库“。1 、 数据集成系统“、p e e r 数据管理系统”等一系列的数据共享体系结构，以实现不同系统中数据资 源的集成、共享。虽然它们在计算模型、共享形式、以及适用范围上有所不同，但是数据模式以及 模式之间的映射关系( 模式映射) 是构成这些系统的重要基础 在联邦数据库“2 1 中，每个结点都有局部模式、输出模式和输入模式其中局部模式描述本地数 据：输出模式定义哪些数据可以与其它结点共享；输入模式定义哪些数据是从其它结点引进的。局 部模式和输入模式共同构成该结点的逻辑数据模式，也称为该结点的联邦模式各个结点上的数据 库系统一般是异构的，从一个结点的输出模式到另一个结点的输入模式须傲适当的转换。从某种程 度上来说，这种转换可以看成是一种映射关系。用户( 泛指应用程序) 根据联邦模式提交查询，由系 统负责将它分解成对相关结点的子查询。 敷据集成系统通常由包装器( w r a p p e r ) 和中介器( m e d i a t o r ) 组成”，如图l l 所示。包装器封装 了底层的数据源模式，而中介器提供一个集成的全局模式，它们之间的联系由模式映射表示。系统 以c l i e n t s e r v e r 计算模型处理查询，当用户根据全局模式提交全局查询时，中介器根据模式之间的 映射关系。负责将它分解( 重写) 为相关数据源的子查询，提交到对应的包装器。包装器将接收到的 查询请求翻译成本地数据源能够理解的形式，并将结果转换成一个公共的格式，返回到中介器。整 个查询处理过程对于用户是透明的，也就是说，通过数据集成系统，各种异构的数据源在逻辑上形 成一个统一的虚拟数据库。中介器可以组织成层次结构，以便新数据源的加入。 p e e r 数据管理系统”( p e e r d a t am a n a g e m e n ts y s t e m ，缩写为p d m s ) 是最近提出的种数据共 享体系结构。如图1 ，2 所示，不管是否保存有实际的数据，每个结点都拥有自己的局部模式，它也 是用户提交查询的接口。任何结点可以随时加入或者离开系统逻辑上，结点之间由模式映射相互 关联，形成一个结点网络与数据集成系统相比，p d m s 没有集成的全局模式，这一点与联邦数据 库类似但是在p d m s 中，查询处理是基于对等( p 2 p ) 计算模型的。根据模式映射，p d m s 递归的 把对一个结点的查询分解到所有与之有直接或者间接映射关系的结点。由于其灵活性，p d m s 适用 于大规模的、动态的、开放的数据共享。 总之t 在数据头，应川中模，映射是帝洵重弓、数据转换的重要依据。”。从概念上说，模 东南人学博i ：学位论义 图1 1 数据集成系统示意图图i 2p e e r 数据管理系统示意图 式描述数据的结构，模式映射描述数据之间的关系。根据数据模型，模式映射可以由相关的查询( 视 图) 定义语言表示。当数据源模式和目标模式( 全局模式) 都由关系模型表示时，那么模式映射可以由 $ q l 、d a t a l o g 1 等关系查询语言来表示。随着x m l 数据模型的提出，w e b 数据的集成、交换、共 享有了一种通用的标准。由于其表示数据的不规则性和灵活性，基于x m l 的数据共享系统已经在 研究和实践中得到了广泛的认同和接受。比如，s i l k r o u t e ”“等数据集成系统给出了在x m l 模型和 关系模型之间定义映射的例子。更为一般的情况，在基于x m l 的集成系统中数据源可以包括其 它非数据库数据。而包装器以x m l 作为一种公共模型来定义数据源的输出模式此时，作为x m l 数据的查询语言，x q u c | y ”可以自然地用来描述嵌套模式( 如d 1 1 ) ) 之间的映射关系。 在数据共享系统能够运行之前，用户( 管理员) 必须在目标模式( 全局模式) 和数据源模式之间建 立起映射关系由于模式之间存在结构、语义上的差异，使得这样的建立过程十分烦琐、复杂、并 且十分容易发生错误。通常，这样的建立过程并不是一次就能完成的，往往要经过不断的修正、调 整、求精“”后，才可能最终得到符合应用需求的映射关系。这种现象在一些复杂应用中显得尤其特 出，如今各行业都在推行标准的模式，这些模式十分庞大，可能包含数以千计的元素”，在这些模 式之间定义映射关系的困难程度是难以想象的另一方面，当应用需求或数据模式发生变化时用 户还得维护、修改已经建立的映射关系。特别是在w e b 这样的动态环境下，不仅数据源的数据经常 发生变化，其模式的结构、语义、以及系统提供的查询能力都可能经常发生变化如何将这些变化 反映到已经建立的映射中，即如何维护模式之间的映射，将关系的系统的可用性。同样的原因，完 全由手工方式来完成映射的维护工作将是不现实的 和传统的数据库管理系统相比在数据共享系统中。元数据的管理不再仅仅局限于数据模式以 及其它一些统计信息，模式映射同样需要作为元数据加以管理、维护和分析“5 ”1 。本文将重点研究 x m l 模式映射的建立、维护“4 以及复合问题，这也是映射管理的重要内容。对于这类映射问题本 文力求解决当前面临的主要问题，这对提高数据共享系统的实用性、可扩展性具有重要意义。 1 2 研究现状 1 2 1 模式映射的建立问题 如前所述，模式映射的建立问题是数据共享系统中基本的又是复朵的任务，为了减轻用户的负 担，目前大部分研究集中在如何刚( 半) 自动的方式来解决这类问题，这士要体现在模式匹配”一和 映射发现：。两类技术上。给定个目标模式以及一组渊模式，模式匹配的任务是建立元素之问的 2 第一章前高 对应关系，文献 2 4 讨论了如何发现元素之问1 ：l 的简单匹配进一步，文献 2 5 2 6 对l ：h 、，l ：1 的复杂匹配进行了探讨。这方面的技术主要包括了幽的匹配、自然语言的处理、领域知识的利用、 机器学习和数据挖掘等，文献 2 3 对此进行了分类和总结。模式匹配只给出了不同模式中各个元素 之间的对应关系，但是同一模式中的元素是相互联系在一起、从而构成具有实际意义实体的，因此 仅仅由这些匹配关系并不能正确的描述模式之间的关系。在假定这些匹配已经给定并且完全正确的 前提下c l i o 系统进而采用启发方式，利用模式中元素之间存在的结构约束和引用约束，以发现 不同匹配之间潜在的语义联系，从而将它们提升并转换为模式之间的映射联系”。“ 在一定程度上。这些技术确实能够辅助用户建立模式之间的映射关系，但是在实际应用中这是 不够的，用户仍然不可避免的需要经常直接处理映射，对此我们从下面几个方面进行分析说明： 匹配技术总是限制在某一特定领域，而且，即使是1 ：l 的简单匹配，也只有6 0 7 0 的准 确率1 ，以这种不完全准确的匹配结果为基础，应用映射发现技术所得到的模式映射也是 不准确的，这时就需要用户对结果做进一步的修复； 映射发现问题实际上是一个搜索问题：给定目标模式和数据源模式之间的元素匹配，映射 发现技术将根据模式中隐含的结构、语义约束，在这些匹配之间搜索出语义上正确的组合， 从而给出模式之间可能存在的映射关系，即候选映射“7 “通常候选映射的数量很多，而 从中选出符合应用要求的映射则由用户决定，而且在有些情况下，实际应用所需要的映射 可能并不包含在得到的候选映射集中，这时用户就得完全以手工的方式来建立模式映射。 即使在候选映射集中存在符合实际应用所需要的映射仍然需要进一步的求精处理才能得 到最终的映射，文献 1 4 通过有选择的生成具有代表性的数据实例来帮助用户确定如何 对映射进行求精处理。 【2 7 ，2 8 1 中的映射发现技术只能以整个模式为单位来搜索候选映射，当修改元素之间的匹配 时。将导致映射发现技术对整个模式的重新搜索 1 2 2 模式映射的维护问题 当目标模式或者数据源模式发生变化时，目前文献中给出了三种主要的映射维护技术第一种 仍然是基于搜索技术的“”，该技术首先确定受到模式变化影响的映射，从而确定出相应的元素匹配， 然后重新应用映射发现技术，从这些匹配中搜索出候选映射。第二种解决途径是运用映射复合技术 。1 ，所谓映射复合“。就是说，给定模式岛到岛之间的映射啦j 、到晶之间的映射 i 映射复 合就是求解模式岛到岛之间的直接映射 而j ，使得任何岛的数据实例经过尬j 和m 】连续转换后 所得到的结果，与直接经过心j 转换后所得到的结果是一样的。映射复合技术也可以用来解决模式 映射的维护问题，比如目标模式r 演化成n 那么要计算数据源模式s 和z 之间的映射关系只要 复合模式s 和r 之间的映射以及r 和r 之间的映射。pa b e r m t e i n 等在文献 1 6 ，1 7 中提出用抽象 的模型来表示模式映射，从而可以象模式那样作为元数据来管理，并为此定义了m a t c h 、d i f f m e r g e 、 c o m p o s i t i o n 等操作，这被称为模型管理问题。模型管理为模式演化问题提供了另外一种解决途径， 使得_ 【 j 户能够以程序脚本的形式，逐步计算出新的映射 这些方法都是根据模式来更新映射的，但是在实际应用中，仍然由许多因素需要仅仅对映射做 出修改比如映射的求精，这些情况下模式本身并没有发生变化，这使得以上这些方法不再适用。 当模式映射由类似s q l 、x q u e r y 的布询表达式描述时。我们发现除了不同模式之间存在结构、语 义上f j 差异外。这种质朴的映射表示方式( 如亢询表达式) 是造成它们难以建立午i i 维护的另个主要 东南人学博1 学位论文 原因。更为糟糕的是，在基于x m l 的数据集成中，由x q u e r y 表示的模式映射可能十分庞大，因 为这里的模式映射需要计算的是一个嵌套的x m l 数据其复杂程度取决于全局( 目标) 模式“。下 面分析说明了实际应用中可能经常遇到的几种情形从中可以看出，即使运_ l l j 以上提及的辅助映射 工具，质朴的映射表示方式( 即查询表达式) 难以适应实际需要。 m a p p i n gr e f i n e m e n t 由于模式中大都隐含了一些不明确的语义，用户往往得经过不断的 修正、求精才能得到最终所需要的映射关系1 。值得注意的是。每次的修正大都只是对映 射语义的一次微调，比如从内连接修正为外连接、修改元素之问的对应关系、或者添加部 分的子映射等等。但是，类伽x q u e r y 这样的查询语言并没有提供一种适合的机制，以便于 映射语义的求精。相反，一次语义上的局部修正可能从语法上导致对映射的完全修改，即。 用户不得不全盘考虑整个映射 s c h e m ae v o l u t i o n 随着应用需求的变化，模式可能会发生调整，相应的，原来建立的映射 也得随之做出应有的修改。除了烦人的语法修改外这里还有另外一个重要任务就是根 据模式的变化定位出受到影响的、即需要修改的子映射”因为同样的原因：模式演化往 往是局部的，对映射的修改往往也是局部的。但是在映射表达式中很难明确区分出各个子 映射，更多的时候它们相互关联成一个整体，要从中定位出相关的子映射并不是一件容易 的事情。尤其在w e b 这样的动态环境下，数据模式可能经常发生变化 c o m p l e xa p p l i c a t i o n 庞大而又复杂的模式已经开始在w e b 中大量使用，比如有些公共的 d t d 可以包含致以千计的元素和属性。我们知道，求解一个复杂问题( 比如在这类模式之间 建立映射关系) 的有效方法就是分而治之的策略，然而当前大部分的映射定义语言只提供了 基于i d 的融合机制“1 我们认为，提供更丰富的映射组合机制将有益于灵活的问题划分 1 2 3 模式映射的复合问题 作为一种重要的映射技术，映射复合( m a p p i n gc o m p o s i t i o n ) 是数据集成、共享所研究的另一 个重要内容。前面- - d 节已经说明，映射复合问题就是求解3 和埘。2 的等价映射拍，在数据 集成的体系结构中，中介器可以组成层次结构“，也就是说，一个中介器的全局模式可以是另一个 中介器的源模式。使用映射复合技术可以直接在中介器和数据源之间预先计算出映射关系，从而使 得查询分解时避免中间层的计算，间接提高查询执行效率。这种优化技术在p d m s 中尤其重要”1 ， 因为其执行时间高度依赖于映射链的长度。有选择的在那些有间接映射关系的结点之间预先计算出 等价的复合映射。并进行适当的优化，可以明显的提高p d m s 的查询效率4 。映射复合是一项耗时 的计算。，当它具备查询优化之功效时却也带来了负面影响：复合映射的更新问题。当参与复合 的映射链中任意一个映射发生变化时，已经复合的映射需要作出相应的修改。在p d m s 这类大规模 的数据共享系统中，复合映射的更新时间不仅与映射本身有关，还与映射链的长度、每个结点( p d m s 目录) 需要更新复合映射的数量有关。 除了作为查询处理时的一种预优化技术文献 1 6 ，1 7 ，1 9 从元数据管理的角度讨论了映射复合 操作。除了语义上的差别，映射复合技术本质上与查询复合技术”4 “类似，所以当前的研究主要 集中在映射复合的计算复杂度和语义问题上”“。对于复合映射的更新问题，当前并没有研究。 一个直接的方法就是重新计算复合映射，但是映射的修改往往是局部的，让整个映射参与更新会造 成重复计算，对于复杂映射( 如嵌套模式之间的映射) 尤其如此。如前所说，质朴的映射表示方式很 难明确的区分出各个子映射，这是当前在复合映射的更新问题上只能采取重新计算策略的主要原因。 4 第一章前苦 1 3 主要研究目标 数据共享应用在信息系统中占有重要的地位，虽然在这方面已经开展很多有用的研究但是仍 然面临很多问题和困难。根据我们前期已经在模式映射方面所做的主要工作42 。，本文着重从元 数据的角度，分析、探讨与模式映射相关的系列问题，这对提高数据共享系统的易用性、实用性均 有重要的意义。针对以上分析中提到的问题，本文对x m l 模式映射的建立、维护、以及复合技术 展开较为深入的研究，以期达到以下目标： 1 ) 在自动化技术不能完全解决模式映射的建立以及维护问题的情况下，本文力图寻求另外的可 行途径，以辅助用户完成映射处理的任务，并使得这种解决途径能够与现有映射自动技术相 互结合； 2 ) 映射复合技术可以用来提高大规模数据共享系统的性能，在w e b 这样的动态环境中，映射 可能经常发生变化，但是与整个模式映射相比，这些修改往往只占一小部分，本文的第二个 目标是研究一种动态的映射复合技术，使得我们可以仅仅根据映射的修改以增量的方式实现 对复合映射的维护 1 4 主要研究内容 本文主要包括三个方面的研究内容：映射表示技术，映射复合技术和复合映射的维护技术。本 文提出了一种映射表示模型，以方便映射的建立和维护过程。基于这样的模型，论文进一步讨论了 映射复合技术，它是对复合映射进行增量维护的基础。 1 4 1 映射表示技术 在第1 2 小节我们已经说明当前有很多研究结合了人工智能等相关技术，力求以一种半自动 的方式来辅助用户建立和维护复杂的模式映射，尽管取得了很多进步。但是当前很多流行的数据模 型缺少明确的形式语义，这就决定了这些技术的自动化能力、以及适用范围都受到很多的限制，在 很多情况下用户仍然不可避免的需要直接参与处理这些映射问题。 基于这样的事实，我们试图从另一个角度寻找可能的解决途径以尽量方便用户对映射问题的 处理。我们注意到，当前模式映射主要是由查询语句表示的，这就是说，在用户直接处理映射问题 时，不得不面对这些复杂的映射表达式，在1 2 2 小节中，我们已经分析说明了直接用查询语句来表 示模式映射，会给用户带来什么样的麻烦。 基于这样的观察。我们提出了一种称为m a e o r ( m _ a p p i n g c o r r e l a t i o n ) 的x q u e r y 模型来表示嵌 套模式之间的映射“。在m a e o r 模型中，原子映射是构成复杂模式映射的基本单位，它们之间由 不同的c o r r e l a t i o n 显式地关联在一起。直觉上，一个原子映射为单个的模式元素定义了局部的视图， 而关联( c o r r e l a t i o n ) 关系则表明了原子映射之间的语义关系。与直接用查询语句表示映射的方式相 比，m a c , o r 模型将映射表示成m a c o r 树结构。这样要为整个目标( 全局) 模式建立映射，可以先分 别为模式中的每个元素分别建立原子映射，然后逐步的将它们关联在一起，这种建立模式映射过程 中所具备的灵活性，使得m a c , o r 十分适合于那些复杂应用。另一方面，由于m a c , o r 树中各原子映射 之间有明确的关联关系，在对映射的求精、修改、维护过稃中，易于区分出相关的子映射，更为重 要的是，m a e o r 可以将修改只局限在那些受到影响的子映射而其余部分则被保留和复用。基于m a e o r 表示模型，映射的处理问题就转化成以f 的树结构操作问题。 东南人学博l ：学位论j ：= = 图1 3 嵌套模式之问的映射关系可以表示成树结构 a 脚5 、a r a e ( d 建立映射的过程相当于建立树结构的过程，主要包括映射结点的建立和插入操作 映射的维护就相当于树结构的维护，如结点的删除、更新等。 图1 3 示意了m a c o r 映射的一般形式第三章将对此做详细的讨论。但是从上图可以看到，与 质朴的查询语句相比，m a e o r 模型的最大特点就是结构化地表示了模式之间的映射关系，这也为我 们研究其它的映射问题( 如本文所研究的映射复合问题) 提供了很多有用的特性。 我们可以任意的操作m a c o r 树，以表明如何从部分的映射逐步构建更为复杂的映射关系。事实 上，对m a c o r 树的操作比模型操作”处于更低的层次。另一方面，文献 1 6 中的映射模型是一个 抽象表示。其表达能力是有限的，并不适用于数据共享这类应用，因为这里的映射是定义在具体数 据上的，为此文献 1 9 将这一思想扩展到了关系模型。与此相比，m a c o r 模型使得在x m l 环境 下具体化上述抽象映射模型成为可能。 在某种程度上，m a c o r 模型中的原子映射与d a t a l o g 模型“”定义集成视图时的子目标( s u b g o a l ) 有某种类似之处。在d a t a l o g 程序中，目标查询可以由子目标表示，这样的思想与m a c o r 模型中用 原子映射来表示全局映射的思想是一致的对于当前文献中介绍的大部分数据集成原型系统( 如 t m m m i s 9 1 、y a r “、s i l k r o u t e “等) ，用来描述模式映射的语言一般都支持数据融合( o b i e c tf u s i o n “ ”) 。通常，这种机制是由s k o l e m 函数实现的，它定义了对象的j d 标识，当j d 相同时，由不同映 射定义的同一对象将融合为一个更大的对象。比如，x m l - q l 查询语言”就支持s k o l e m 函数的定 义。与此相比，m a c 钟模型将映射的定义与融合机制相分离，以显式的方式来融合数据这种融合 机制更加灵活，而且不再以m 这种单一的标识作为数据融合的条件，而是以更为通用的关联关系 作为融合条件。 论文进一步区分出x q u e r y 的一个子集，称为c o x q ，它包括了x q u e r y 的大部分功能，比如可 以表示不周数据源之间的连接、结果的任意嵌套、拼接等等。我们从表达能力方面证明了c o x q 和 m a c , o r 之间的等价性，即任意一个c o x q 表达式都可以由m a c o r 表示，反之，任意一棵m a c o r 树所 表示的合成映射也符合c o x q 语法。 最后，我们给出了实现m a c o r 的一个框架，用户可以通过脚本、或者g u i 直接操作映射，从而 完成相关的建立、维护等任务。对于用户已经用查询表达式表示了模式之间映射关系的情形，通过 这样的框架，可以将这些表达式转换成m a r , o r 树结构，只要它们符合c o x q 的语法规则，用户可方 便地对它们进行维护。另一方面对于需要在模式之间建立映射关系的情形，这样的实现框架给出 了如何结合当前一些主要的映射技术使之能够为m a e o r 树( 即模式映射) 的建立和维护提供半自动 化的支持，比如原子映射根据模式匹配的结果生成，而关联关系则根据模式本身蕴涵的语义关系 推断。注意r 这里并不要求模式匹配的结果是完全的、准确的，这是因为m a c o r 模型将整个模式之 间的映射细分为不同的子映射