（计算机应用技术专业论文）基于XML的元数据近似匹配模型研究.pdf

摘要 x m l 技术和元数据技术作为资源对象描述与检索的基础，正在众多领域中 得到广泛研究与应用，尤其基于x m l 的检索技术研究方兴未艾。目前虽有许多 面向x m l 文档的检索方案被提出，但它们都不能在高效率的情况下保证资源的 查全率与查准率，难以满足用户多样性的检索需求。本文围绕查全率和查准率 的效率问题，引入树匹配思想，对基于x m l 的元数据检索进行了深入的研究。 本文首先系统地讨论了基于x m l 的信息检索技术的基本原理和方法，研究 了x m l 检索技术的发展现状，对信息检索中的树匹配理论和相关问题进行了深 入探讨。 为提高查全率，本文把无序标签树匹配分解为树结构匹配和标签语义匹配， 采用树结构匹配和语义匹配相结合的方法，对传统树匹配算法进行了改进，提 出了近似匹配的概念。针对元数据x m l 描述的树型结构特征，本文设计了一个 由树嵌入近似匹配、树包含近似匹配、树包容近似匹配共同组成的三层近似匹 配模型，此模型可根据用户的不同需求有效地调节元数据的查准率和查全率。 由于传统的无序标签树的包含问题是一个n p 难问题，所以本文在近似匹配 模型中根据树匹配检索的结构化特征，通过n a 节点之间亲和度的限制条件， 使得包含近似匹配代价的计算问题可以在多项式时间内得到解决。本文引入树 编辑距离、映射代价等相关理论和动态规划的思想，详细分析了近似匹配模型 的匹配代价计算问题，证明了三类近似匹配问题可在多项式时间内求解。 最后，本文利用近似匹配模型以及匹配代价计算，设计了基于x m l 的元数 据查询系统的体系结构和检索过程，构建了元数据查询系统的原型系统，并进 行了一系列实验，实验结果表明：近似匹配模型能很好地将查全率和查准率结 合起来，在元数据检索的实际应用中具有可行性和有效性。 关键词；x m l ：元数据检索：近似匹配：匹配代价：匹配模型 董三兰坚：笠垄竺耋誓2 竖墼堡型塑耋 a b s t r a c t a st h eb a s e o fd e s c r i p t i o na n dr e t r i e v a lo fr e s o u r c eo b j e e t s ，x m l a n dm e t a d a t at e c h n o l o g i e sh a v eb e e nw i d e l yr e s e a r c h e da n da p p l i e di na l l k i n d so ff i e l d s t h o u g hm a n ye x p e r t sh a v ee s p e c i a l l yf o c u s e do nt h e s t u d y o fr e t r i e v a lt e c h n o l o g yo nx m la n dm e t a d a t a ，b u ts t i l ln oe f f i c i e n t r e t r i e v a lm e t h o d sc o u l de n s u r et h ea c c u r a c ya n dr e c a l lr a t e t h i st h e s i s a i m sa tt h ee f f i c i e n c yp r o b l e mo fa c c u r a c ya n dr e c a l lr a t ei nx m l r e t r i e v a l b a s e do nt r e em a t c h i n g ，t h et h e s i sm a k e saf u r t h e rs t u d yo nt h e x m lr e t r i e v a lt e c h n o l o g ya b o u tm e t a d a t a t h i st h e s i si n t r o d u c e st h eb a s i ct h e o r ya n dm e t h o da b o u tx m l i n f o r m a t i o nr e t r i e v a l ，a n ds t u d i e st h ed e v e l o p m e n to fx m lr e t r i e v a l m e t h o d s ，e s p e c i a l l ya b o u tt h et r e em a t c h i n gt h e o r ya n dr e l a t i v e a l g o r i t h m s i no r d e rt oi m p r o v et h er e c a l lr a t ei nx m lr e t r i e v a l t h i st h e s i st a k e s a p a r tt h eu n o r d e r e dl a b e lt r e em a t c h i n gi n t ot r e es t r u c t u r em a t c h i n ga n d t r e el a b e ls e m a n t i c m a t c h i n g t h i st h e s i sc h a n g e st h ec l a s s i c a lt r e e m a t c h i n ga l g o r i t h m si n t oa p p r o x i m a t em a t c h i n gb yc o m b i n i n gt h et r e e s t r u c t u r em a t c h i n gw i t hs e m a n t i c m a t c h i n g a c c o r d i n g t ot h et r e e c h a r a c t e r i s t i c so fm e t a d a t a d e s c r i p t i o n ，i tp u t s f o r w a r dam e t a d a t a r e t r i e v a lm e t h o db a s e do nt r e ea p p r o x i m a t em a t c h i n ga n dg a v eo u tan e w r e t r i e v a lm e t h o db a s e dont h r e e - l e v e lt r e ea p p r o x i m a t em a t c h i n gm o d e l t h i sr e t r i e v a lm e t h o dc a na d j u s tt h ea c c u r a c ya n dr e c a t lr a t eo fs e a r c h i n g m e t a d a t ab yd if f e r e n tu s e r s b e c a u s eo fu s i n gt h ec o n c e p t i o no fe d i t i o nd i s t a n c ea n dm a p p i n g c o s ta n dt h em e t h o do fd y n a m i cp r o g r a m m i n g ，t h et h e s i s a n a l y z e st h e c o u n t i n gq u e s t i o no fa p p r o x i m a t em a t c h i n gc o s ti nd e t a i l d u et ot h e c a l c u l a t i o nf ort h ee d i t i o nd i s t a n c eo fu n o r d e r e dl a b e lt r e eb e l o n g st o n p h a r dp r o b l e m ，a c c o r d i n gt ot h es t r u c t u r e df e a t ur e s0 fx m lm e t a d a t a s e a r c h i n gi nt h ea b o v em a t c hm o d e l s ，t h i st h e s isa d d si n t os o m ep r o p er 1 i m i t i n gc o n d i t i o n s ，s ot h a tt h et a l c u l a t i o n0 ft h ea p p r o x i m a t em a t c h i n g c o s tc a nb es o l v e di nml 1 1 t i n o m i a it i m e i nt h ee n d ，u s i n gt h ea b o v ea p p r o x i m a t em a t c h i n gm o d e la n dt h e c a l c u l a t i o no fm a t c h i n gc o s t ，t h i st h e s i sp u t sf o r w a r dt h er e t r i e v a lp r o c e s s b a s e do nt h ex m ld e s c r i p t i o nm e t a d a t a ，a n dd e s i g n st h ea r c h i t e c t u r eo f q u e r ys y s t e mf o rx m lr e s o u r c eo b je c t s t h ee x p e r i m e n t a lr e s u l t sp r o v e t h a tt h ea p p r o x i m a t em a t c h i n gm o d e li sf e a s i b l ea n de f f i c i e n ti nt h e p r a c t i c a la p p l i c a t i o no fm e t a d a t ar e t r i e v a l k e yw o r d s ：x m l ；m e t a d a t ar e t r i e v a l ；a p p r o x i m a t em a t c h i n g ；m a t c h i n g c o s t ；m a t c h i n gm o d e l 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：i 影 y c 吸日期：二柙够年f - 月五! e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请侄以上相应方框内打“”) 作者签名：彦，纪f 岔 剥鹳：移辫 嗄f 谚江 日期：删 f r 月z 目 日期：2 - 。牛：r r , j , - u r h 基于x m l 的元数据近似匹配模型研究 本文中经常使用的符号及其表示意义 符号 l 习 v f 玎司 研司 c ( o d ( o a ( f ) l a b e l ( v ) d o m a m ( 1 ) r a n g e ( ) s p e c t r u m g p e c t r u m ( t ) r ( v x ，v 2 ) p a r a e n t ( v ) a n c e s t o r ( v ) 呦 幼 肋 r c o s t m , ( 乃，r 2 ) a 0 q d 含义 树t 的节点数日 树t 中编号为i 的节点 树t 中以v i 为根节点的子树 t f i l 中以删除节点v i 得到的森林 节点u 的儿子节点集合 节点v f 的子孙节点集合 节点的前辈节点集合 节点的标签 映射厂的定义域 映射厂的值域 映射厂的映射谱 映射厂的广义映射谱 ，v 2 的亲和度 v 的父节点 v 的祖先节点 匹配厂的结构匹配代价 匹配厂的语义匹配代价 匹配厂的近似匹配代价 树乃和乃之间的m 匹配类型的结构匹配代价 空节点或空标签 空树 查询树 元数据描述树 v 工程硕士学位论文 第1 章绪论 1 1 引言 随着计算机与网络技术的广泛应用，海量信息资源要求能有与现代计算机 技术和网络环境相适应的方便、快捷、有效的数据发现和获取方法，为此9 0 年 代以来，各种领域的信息资源元数据标准被相应制定【l t 2 】，如网络资源、文献资 料、人文科学、社会科学数据集、博物馆与艺术作品、政府信息、地理空间信 息、科学观测数据、数字图像、软件复用构件库、档案库与资源集合、技术报 告、连续图像等。元数据标准为分布的、由多种数字化资源有机构成的信息体 系提供整合的工具与纽带，为各种形态的数字化信息单元和资源集合提供了规 范、普遍的描述方法和检索工具，为资源对象的管理、发现和获取提供了实际 而简便的基础。 元数据( m e t a d a t a ) 又叫描述数据或诠释数据刚】，是“关于数据的数据( d a t a a b o u td a t a ) ”。元数据是描述一个具体的资源对象，并能对这个对象进行定位、 管理，且有助于它的发现与获取的数据。一个元数据由许多完成不同功能的具 体数据描述项构成，具体的数据描述项又称元数据项、元素项或元素，用于说 明数据内容、质量、条件、查询和其他有关特征的背景信息。元数据描述的基 本对象是数据集，其存储形式为格式化的文本或关系数据库表。元数据是使数 据充分发挥作用的重要条件之一，可用于数据文档的建立、数据发布、数据浏 览、数据转换等，对于促进数据的管理、使用和共享有重要的作用。原始数据 如果没有元数据，就难以有效的进行管理和使用。 元数据库( m e t ad a t a b a s e ) 是为保存和处理元数据而设计和建立的数据库。元 数据库的运行方式和正常数据库相同。 元数据标准是描述某类资源的具体对象时所有规则的集合。不同类型的资 源可能会有不同的元数据标准，它一般包括了完整描述一个具体对象时所需要 的数据项集合、各数据项语义定义、著录规则和计算机应用时的语法规定。元 数据标准设计首要的问题是要利用元数据实现哪些功能，根据对八种国外常用 元数据及已有较成熟的中文元数据标准进行的研究和比较分析【l 。4 l ，并结合对国 家野外科学观测数就冲l 田家地理信息无数据相关文献【5 6 1 的了解，i 叮纳出元数 据f 要功能订如f 儿个： ( 1 ) ，描述功能。对资源对象的内容、属性等的描述能力是元数槲最基本 的功能，应当能比较完整地反映出资源对象的全貌。衡量描述能力最重要的一 基于x m l 的元数据近似匹配模型研究 点是它能否准确地区别不同的具体资源对象，这是元数据标准制订工作中最困 难的一部分。针对每一类具体的资源对象需分别研制。 ( 2 ) 、检索功能。支持用户发现资源的能力，即利用元数据来更好地组织 信息对象，建立它们之间的关系，为用户提供多层次、多途径的检索体系和方 法，支持用户在不必浏览资源对象本身的情况下，能够对资源对象有基本的了 解和认识，决定对检出信息的取舍，从而有利于用户便捷快速地发现其真正需 要的信息资源。 ( 3 ) 、定位功能。提供信息资源本身的位置方面的信息，如d o i 、u r l 、 u r n 等信息，由此可准确获知信息对象之所在，便于信息的获取。 ，( 4 ) 、管理功能。保存信息资源的加工存档、结构、使用管理等方面的相 关信息，以及权限管理( 版权、所有权、使用权) 、防伪措施( 电子水印、电子 签名) 等。 ( 5 ) 、评估功能。保存资源被使用和被评价的相关信息。通过对这些信息 的统计分析，方便资源的建立与管理者更好地组织资源，并在一定程度上帮助 用户确定该信息资源在同类资源中的重要性。 ( 6 ) 、交互功能。有些资源对象元数据的数据项内容需经过专家考据才能 确定，尤其是在描述比较复杂的对象( 例如天气) 的时候。对使用元数据的专 家学者提供专门的元素，允许他们对某些数据项的内容进行反馈，有利于建立 更为准确的元数据，提供更为良好的服务功能。 以上功能的实现反映在具体元数据项的设立、定义和语法结构上。本文不 作进步讨论。 1 2 使用x m l 描述元数据的优点 随着w e b 技术的发展，传统的w e b 语言h t m l 的弊端逐渐显露出来，特 别是想要做到资源共享、数据的物理分散而逻辑集中，基于h t m l 的w e b 应用 很难做到，同时，h t m l 只给出了处理对象的现实信息，没有给出描述对象的 其它属性信息，大量可本地完成的处理工作必须由服务器处理，大大增加了网 络流量，影响了网络效率，制约了各类资源、数据的共享。x m l 具备许多公认 的优点【7 8 】，如：纯丈本表示；具有平台无关性；信息的内容与信息的表示分开， 呵满足不同的需要等，同时在表达和处理元数据方面还有如下的。些优势： ( 1 ) 、x m l 可办便地用柬表达元数据 x m l 的+ 个 h 人的优点是自定义性d t d 干x m ls c h e m a 从功能【：柬说就 是种无数据，是天j ：数据集关系和数据i 索限制条件的元数扔：，所以用它们 束表达数据集之间f 内关系显得很自然。另疗面，利用x m l 的n a m e s p a c e ( 命 工程硕士学位论文 名空间) ，用户在定义自己的元数据格式时不用担心自己定义的标签与他人的相 冲突，并且用户可以无歧义地直接引用现有的元数据标准。 ( 2 ) 、x m l 的样式语言可实现元数据间的转换和显示 元数据的转换包括两方面：一方面是为了实现信息的共享而进行的转换， 另一方面是为了满足用户多种格式的输出和显示而进行的转换。x m l 由于对信 息的内容与信息的表示是分开的，并且x m l 对于数据转换有很强的支持，利用 x s l t 技术，在对相互的信息定义和结构了解的基础上。可以定义相应的样式文 件来让x s l 处理器进行相应的转换工作，同时输出元数据时可以根据用户的需 要将系统中的元数据信息按照某种格式来输出。 ( 3 ) 、利用x m l 可方便地实现元数据的查询 各种元数据的查询都是在w w w 上进行的，传统的w e b 语言h t m l 与x m l 相比在信息的组织上结构性很差，而信息的结构化程度是与查询的效果面正比 的，所以用x m l 来实现查询比h t m l 要方便有效。同时基于x m l 的查询语言 可以同时支持结构化和半结构化的查询。比如，用x m l 表示的数据在不知道具 体的d t d 或x m ls c h e m a 时，可以认为是一种半结构化的数据，因为它满足 x m l 规范，具有定的结构性。当用户知道元数据的具体结构时，可直接构造 查询语句来进行查询。 ( 4 ) 、众多软件对x m l 的支持 随着x m l 的发展，越来越多的软件包和应用程序对x m l 进行支持，如i b m 、 m i c r o s o f t 、o r a c l e 、s u n 等著名软件公司，这些都大大促进了x m l 的发展。x m l 正在成为w e b 上的数据组织与交换的事实标准。 1 3x m l 匹配检索技术的研究进展 x m l 正在快速发展成为w e b 上数据表示、集成和交换的标准，目前大量 的基于x m l 描述的元数据已在使用，但对资源对象元数据的检索却沿用传统数 据库检索技术，仍使用基于关键字匹配的传统的图书馆及信息科学编目语言查 询技术【9 l ，一个资源对象的结构化x m l 描述文档包含其标准的元数据内容，但 是基于x m l 的查询语言( x q l ) 只能查到与查询条件精确匹配的结果【1 0 ，从 而使得资源对象的查全率很低。在元数据使用不断普及与深入的今天，传统方 法受到越来越严峻的考验，它的不足性主要体现在以下几方面： 第，侄存储海量信息的大型数据库中，缺乏有效的手段在保证查伞率的 艰础：傈汪资源对象的贪准率； 第二，针对不同类型的资源对象制定钉小州的元数据标准，查询f = f i ，、在查 询时需要详细了解资源鹰i 的分类方案对用户提出了较高要求： 基于x m l 的元数据近似匹配模型研究 第三，要求用户精通所用的x m l 查询语言； 第四，有的用户需要高效率地精确查询，有的用户需要对资源对象进行模 糊查询，以通过较高查全率寻找自己期望的结果，而传统的查询方案难以同时 满足用户对资源对象元数据库的复杂多样的检索需求。 为解决这些问题，近年来学者们提出了许多的基于x m l 文档匹配的检索技 术和方案。 r i c h t e r l l 2 提出一种基于结构的x m l 文档查询方法。尽管该方法具有较高的 查全率，且算法的时间复杂度为多项式级，但其所应用的是有序树的匹配思想。 由于同一层次上的元数据描述信息没有先后顺序上的限制，因此这种基于有序 树匹配的查询方法不适应于x m l 描述的元数据查询。 t o r s t e n ”1 提出了一种新的x m l 查询模型和算法，虽然应用了无序树包含匹 配的思想，但算法的时间复杂度是指数级的，在实践使用时需要对查询树的度 d e g r e e ( q ) 进行严格的控制，无法保证较高的元数据查询效率。 dfs u n 在文献 1 4 】中针对x m l 文档提出了一种新的基于结构检索和语义 检索相结合的概念检索，进行了概念检索原型系统设计，但无论从结构检索还 是语义检索上都缺乏详细有效的算法设计与分析，要进行实际应用还需进行深 入的探讨。 路燕等【l5 】提出了将x m l 查询树与d t d ( d o c u m e n t t y p e d e f i n i t i o n ) 简图匹配 的方法，有效地解决了现有x m l 查询语言需要用户必须明确知道所查x m l 文 档结构、不能从整体上对w e b 上的x m l 文档进行查询、要求用户精通x m l 查 询语言等问题，提高了查全率，但在查询的优化方法、查询结果重组和提高查 准率等方面仍有待进一步探讨。 针对这种情况，本文提出了将树匹配理论和语义匹配概念引入元数据查询 的思想。为了提高这种新方法的检索效率并满足元数据查询用户的具体要求， 本文根据元数据x m l 描述方法的具体特征，对几类树匹配方法进行了分析与研 究，提出了一个包含多层次的，赋予匹配代价计算的元数据查询近似匹配模型， 并且设计了一个基于该近似匹配模型的元数据查询系统的原型。 这种新的基于x m l 的元数据查询方法可以满足不同用户的查询要求，使得 查询用户可以通过近似匹配层次的选择以及匹配代价的计算等手段，在保证资 源对象查全率的基础上有效地提高资源对象的查准率。并且，这种方法不给用 户带来更多的代价，不象传统方法中要求查询用户需要了解资源库的分类方案 和元数据标准的详细结构，利用此模型可以实现不同分类方案的资源库之问的 元数就：舱索，有利于鲥向基r 网络的分伽o 资源阼检索。 工程碗士学位论文 1 4 本文的主要工作 本文对信息检索中的树匹配算法的当前发展状况进行了探讨，从树及映射 的基本概念入手，主要对无序树的嵌入匹配、包含匹配和包容匹配进行了分析， 对几类树匹配算法的性能与效率进行了比较研究。 在深入研究树匹配查询的工作原理的基础上，本文针对x m l 元数据查询树 中节点的结构化特征和元素内容的语义特征，采用结构检索与语义检索相结合 的思路，对传统的无序树嵌入匹配和包含匹配进行了适当的改进，给出了树嵌 入近似匹配和树包含近似匹配的定义，采用动态规划的方法对几类近似匹配算 法的匹配代价进行了详细分析，证明了近似匹配代价计算可在多项式时间内解 决。在此基础上提出了一个适用于基于x m l 描述的元数据查询的三层近似匹配 模型。 本文最后给出了三层近似匹配模型在野外科学观测数据查询系统中的应用 设计，构建了一个元数据查询系统原型，并进行了一系列实验，证明了该近似 匹配模型很好地将查全率和查准率结合起来，在元数据查询的实际应用中具有 可行性和高效性。 全文共分四章，主要内容如下： 第一章概述了本文课题研究的背景、意义和目标，介绍了本文所做的主要 工作；第二章阐述了基于x m l 描述的元数据表示方法；介绍了目前基于x m l 文档的元数据检索研究领域中的几种主要技术和算法，介绍了树匹配理论中的 几个重要概念：详细阐述了面向x m l 的概念检索技术和x m l 查询树与d t d 简图匹配算法；第三章分析了树匹配领域中几个重要问题和研究现状，并对其 进行了改进，提出了基于x m l 的元数据查询的三层树近似匹配模型，并采用动 态规划方法对三种近似匹配算法的匹配代价计算进行了详细分析；第四章设计 了一个基于近似匹配模型的元数据查询系统的原型，针对不同用户的需求设计 了两种用户查询方式，一种是用户指定具体匹配类型的查询，另一种是系统自 动寻优查询，通过一系列实验，证明了近似匹配模型在元数据查询的实际应用 中具有可行性和有效性。最后对本文的工作进行了总结，并建议了下一步的研 究方向。 皋于x m l 的元数据近似匹配模型研究 第2 章树匹配理论与x m l 检索技术分析 本章对基于x m l 的元数据描述文档树型表示和查询表示方法进行了探讨， 尤其对布尔查询的树型表示进行了详细地阐述，介绍了树匹配领域中的树、亲 和度、编辑操作、编辑代价、映射和映射谱等重要概念，并详细阐述了基于结 构和语义相结合的x m l 文档检索思想和d t d 简图匹配查询技术，最后介绍树 匹配领域中几个重要问题及其研究现状。 2 1 基于x n i l 的元数据描述与查询表示 2 ，1 1 基于x m l 的元数据描述文档树型表示 元数据的结构指一个完整的元数据标准通常由哪几部分的数据项( 元素) 组成，各有什么特点。一个被元数据描述的资源对象往往是一个较为复杂的复 合对象，或是一个抽象的对象集合体。是对抽象的对象集合体还是对具体的资 源对象进行检索，处决于用户的需求和元数据的结构及具体元素的设计。资源 对象本身的表示可以是完全结构的、半结构或无结构的，传统的关系数据库中 的信息具有很强的结构性，可称为完全结构化数据，如数字、符号等，半结构 化数据是相对于完全结构化数据而言的，主要泛指w e b 上的信息数据，如一个 w e b 页面等，无结构化数据一般无法用统一的数字和结构表示，如图像、声音等。 x m l 是针对包含结构化、半结构化信息的文档而设计的一种标记语言，结构化的 资源对象元数据可以方便地进行基于内容的检索和版本控制，非常适合采用 x m l 技术进行处理。 资源对象的元数据检索方法依赖于资源对象的分类和元数据描述的表示方 法。根据资源对象的分类方案和元数据标准的结构化特点，可以将资源对象的 元数据进行x m l 绑定，x m l 描述文档可转化为相应的树型结构，下面针对树 型结构的连接查询和布尔查询的表示方法进行一些讨论。 一个基于x m l 的元数据描述文档可表示为一棵无序标签树，此树通常称为 元数据描述树( 在本文中将其简称为元数据树m d t 或数据树d t ) ，如图2 1 为 一个基于x m l 的元数据描述文档，如图2 2 为图2 1 的埘型表示。为便f 绘图 表示这学图2 2 中的部分竹点标签以图2 1 中对应描述的母缩写来表示，如 c r t 代表c r e a t et i m e ，s t d 代表s t a n d a r d d s i 代表d a t a s e ti d e n t i t i e r 。s t a 代 表s t a t i s t i c i a n 等。 9 2 1 2 0 0 2 刮c r e a t e l i m e 国家森林观测元数据标准 i o 森林面积 4 11 2 0 0 2 统计 张三联 0 1 0 8 7 1 2 3 4 5 5 ( ，s t a t i s t i c i a np h o n e 图2 1 x m l 文档 s t a np h o 图2 2x m l 元数据描述树 n 2 1 2 基于x m l 的元数据查询表示 一个基于x m l 的连接查询，是指在x m l 查询构造中只使用逻辑连接符 “s a n d s ”而没有使用“$ o r $ ”的a 询。它可以映射为一棵允序标签埘。如图2 3 所示每个名称顺如“c r t ”，“d s 【”分别映射为盘咖辫的个符点每个文本 项被映射为个叶节点，包含运讳失系映射为节点之蚓的父予天系，逻辑连接 符“s a n d s “映射为节点之i 训的兄弟关系。 董三蚤些：塑蚕鍪堡篓丝坚兰堡型丝塞 s 曼然祭潞彤? 舞警蹦嘲毒徽= j l 】 图2 3 一个连接查询到一棵树的映射 一个基于x m l 的布尔查询，是指在x m l 查询构造中既使用“s a n d s ”又使 用“$ o r $ ”的查询。它可以等价地分解为由多个连接查询组成的集合。一个含有 七个“$ o r $ ”的布尔查询，可等价地分解为2 个连接查询的集合，相应地，一个 布尔查询可映射为2 2 棵连接查询树，如果只用对连接查询树的匹配算法，则理 论上需要进行2 次查询匹配计算，然后再对所有查询匹配计算结果进行比较和 优选，这种方法显然计算复杂且容易出错。 为此，rzx u 在文献 1 6 中提出将逻辑连接符“$ o r $ i ，本身映射为查询树中 标签为“o r ”的特殊节点。如图2 4 所示，首先将“$ o r $ - 两侧的“t t y ”、“d s n ” 与“t t y ”、“d s n ”分别与其前面共同的名称项“d s i ”映射为一棵子树，“$ o r $ ” 映射为这两棵子树的父节点“o r ”，并使其成为前面更高一级的名称项“f m d ” 的子节点。然后通过此方式，在树中增加了类特殊类型的节点“o r ”，将布 尔查询映射为一棵查询树来表示，从而将元数据的布尔查询转化为一棵元数据 查询树到一棵元数据描述树的匹配计算，不再需要由多棵连接查询树分别与同 一棵元数据描述树进行匹配计算了。 d s n f d i ( rr | “9 1 2 1 2 0 0 2 ”is a n d sd s i i r t y i “缝：i ”i s a n d s d s n “a - 咖b ” s o r s lr 1 v l “啦测is a n d sd s n i “森林r 韭”i i i i 剀2 4 一个布尔卉向刮一棵树的映射 8 工程硕士学位论文 2 2 树匹配理论基础 2 2 1 节点的宗祖与亲和度 树是图的一种特例，一般用r 表示：z = ( k e ，r o o t ( d ) ，也可简记为r f f i ( v , e ) 。 其中v 表示一个有限节点集，r o o t ( 乃表示树的根节点，e 表示边集，它是v 上 的一个二元关系，它满足反自反性、对称性、可传递性。如果( “，v ) e e ，则称 节点是v 节点的父节点，记为u = p a r e n t ( v ) 或v = c h i l d ( u ) ，u 节点的所有子节点组 成的集合记为c ( “) 。一棵树必须满足如下三个条件： 1 节点r o o t ( 乃不存在父节点； 2 除根节点外，v 中其他节点有且仅有一个父节点； 3 树中每一个非根节点v y ，存在( r o o t ( d ，de e + 其中矿是e 的传递闭包。 如果两个节点v ，v 2 ，有( v ，r e ) e e + ，则称v j 是v 2 的祖先节点，记为 1 , 1 = a n c e s t o r ( v 2 ) 蔚v 2 = d e s c e n d a n t ( v 1 ) 。所有u 节点的祖先节点组成的节点集合记 为一( “) ，所有u 节点的子孙节点组成的节点集合记为d ( “) 。设“n 则丁中以 u 为根节点的子树记为】_ ( 矿，e ，“) ，有： v - u u d ( u ) a n d e 。= e n ( v v ) 如果两个节点v ，v 2 之间没有祖先后代关系，则利用亲和度【”1 的概念来描述 v ，v 2 之间的关系。为引入亲和度的概念先介绍宗祖的概念。 定义2 1 ( 宗祖) ：弘f 明j ，设m ，v ：v a ( v 。，v 2 ) 芒e + ( v 2 ，v i ) 芒e + ，则定义集 合a 为1 , 1 ，v 2 的宗祖： ，h = 扛陋= a n c e s t o r ( v 1 ) 口= a n c e s t o r ( v 2 ) j 。 定义2 2 ( 亲和度) ：皿( 啊) ，设v l ，v 2e v ( v l ，v 2 ) 芒e + ( v 2 ，v 1 ) 诺e + ，则定义 r ( v t ，) 为i i ，v 2 的亲和度：r ( v 。，v ：) = i 爿。l ，其中| | 表示集合的势。 由上述定义知，两个没有祖先后代关系的节点的亲和度是指这两个节点的 所有共同祖先节点的个数。 值得注意的是，亲和度只是两个无祖先后代关系的节点之间的一个简单的 度量，它的值只有存在共同祖先节点时才有意义，否则是无意义的。如果 r ( v ，v 2 ) r ( v l ，”) 时，可以认为n 与v ，的关系比v j 与v ，的关系要近，但如果 r ( v t ，”) 月( ”j ，v 4 ) 时，则不可认为n 与v ，的关系比v ，与v 4 的关系要近，因为这时 还要考虑节点的深度，单纯依靠节点的亲和度是不能下结论的。 如果将树的每一个节点对应一个标签，这样的树称为标签树，用l a b e l ( v ) 表 示节点ve 的标签。如果树中节点的顺序是有意义的这样的树称为有序树， 盘则称为尢序树。在后文中出现的树如未作特别说州，律认为是无序的标 签树。 基于x m l 的元数据近似匹配摸型研究 2 2 2 编辑操作与编辑序列 对一棵无序标签树，允许以下三种编辑操作u s j g j ： c h a n g e ：改变一个节点的标签。即将一个节点的标签改为另一个标签。图2 5 给出了将一个节点p 的标签改变为节点留的标签的c h a n g e 操作图示，r 为编辑 操作前的树，r 为编辑操作后的树。 图2 5改变标签编辑操作示例 d e l e t e ：删除一个节点，指从树中删去一个节点，使该节点的子节点成为该节点 的父节点的新的予节点。图2 6 给出了将一个删除节点p 的d e l e t e 操作图示，r 为编辑操作前的树，为编辑操作后的树。 图2 6 删除节点编辑操作示例 若删除的是根节点，那么将得到一个森林。 i n s e r t ：插入一个节点，图示2 7 表示了在节点a 下插入节点v 的操作，使得节 点v 成为节点a 的予节点，并把节点a 的一部份原有子节点移作新节点v 的子 节点。这一部份子节点究竟是哪一部份 环境来决定。 是在执行i n s e r t 操作时由具体的上下文 幽2 7 插入- _ 编辑擞竹：示例 设表示所j j 标签的集合a f ，址中的一个特殊标签表示空。l j r 工程顽上学位论文 将上述三种编辑操作简单的统一表示为：p g ，p ，q e z ，缉1 7 , 叮不能同时为 。 当p ，口 时表示将节点的标签从p 改变到函当p ，口= 时表示将当 前标签为p 的节点的删除，当p = ，口 时表示插入一个标签从q 的节点。 如图2 5 中的编辑操作可以表示为：l a b e t f p ) - - l a b e l ( q ) 。如果上下文不引起 混淆，也可简记为：p 一口。 定义2 3 ( 编辑序列) ：一个编辑序列s = o p l ，o p 2 。o p k ，k 为正整数，其中印f 代表一个编辑操作，有叩e a - - b a ，b e 三) - ( a 观) ，! f - a ) + ，( 2 斗l a b e l ( w ) ) f y ) e ，l u d d m 口州h )h e 虬一r a n g d m ) 从这个定义可以看出一个从乃到疋的纠吵射代价计算t 叮分为以下三个部分： 一是y ( 1 a b e l ( v ) - h l b e l ( w ) ) ：它嵌示对参与映射的前点进行标签改变操作的代 基于x m l 的元数据近似匹配模型研究 价：二是 r ( 1 a b e j ( v ) - - a ) ：它表示对出现在1 1 中的未参与映射的节点进行删 除的代价；三是 ( 五- , m a b e i i w ) ) ：它表示对出现在i 2 中的，并且未参与映射 一j 瓦耐) 的节点进行节点插入的代价。由此可知，每一个树映射都有一个对应的编辑序 列，所以树映射是将一棵树转化为另一棵树的新的表达方式。 下面介绍映射谱【l7 l 的概念： 定义2 7 ( 狭义树映射谱) ：设，为一个从乃到乃的树映射，则定义该树映射厂 的树映射谱s p e c t r u m 6 9 为满足以下条件的节点集合： 妒e c t r u m 瑚口n g e ( f ) u 。曲茹鬻一f ) , 3 v 1 ( v ) , v 2 v 2 r a ：n 蜘g e ( f ) 棚( 0 定义2 8 ( 广义树映射谱) ：设，为一个从乃到乃的树映射，则厂的广义树映射 谱g p e c t r u m 0 9 为满足以下条件的节点集合： g p e c t r u 舻印e c t r u m ( f ) u 萑s 。p 咖e c t r 慨u m ( f 川) , 3 u 以螂es p 删e c t r u 州门 映射谱的概念可由图2 8 来示例： t 、，一， s p e c t r u m = w 2 ”j w w 5 ，w 7 ，w 、一 z ；p c c t r u m ( ，) = 细“w 2 。w 3 ，w w 5 ，w 7 ，w s t 蚓2 8 树映射i 齿f f j 小圳 树映射代价和编辑序列代价之间的关系j r 由如下定l 里阐述1 8 1 0 1 ： 工程硕士学位论文 定理z 1 ：设s , m 分别为从乃到乃的编辑序列和映射，则对一个s 必能找到一 个对应的 f ，使得托旧“回。 定理2 2 ：设s , m 分别为从乃到乃的编辑序列和映射，则对一个肘必能找到一 个对应的s ，使得必 d = h $ 。 定义2 9 ( 编辑距离) ：设r 和r 是两棵无序的标签树，则它们之间的编辑距离 t d i s t ( t , t ) 定义为：t d i s t ( t t ) = m i n “两it 一7 也可以用树映射代价定义两棵树的编辑距离如下： 定义2 1 0 ( 编辑距离) ：设r 和r 是两棵无序的标签树，它们之间的编辑距离 t d i s t ( t , t 3 定义为：r d i s t ( t , t ) = m i n “m ) l m 为一个从r 到r 的树映射 定义2 9 和定义2 1 0 的等价可以从定理2 1 和定理2 2 直接得出。类似地可定义 树与树、森林与森林之间的编辑距离，不再赘述。 2 3x m l 检索技术分析 目前针对x m l 数据检索技术的研究2 1 。2 31 方兴未艾，出现了多种x m l 查 询语言的提案，在此基础上的检索算法和x m l 数据管理【2 4 2 5 1 的研究成为x m l 技 术及其相关的w e b 应用领域的研究热点。结合本文的需要，下面介绍概念检索 和d t d 简图匹配两类x m l 检索技术。 2 3 1x m l 概念检索技术 目前，信息检索技术已经不仅仅满足于简单的基于字面匹配的全文检索， 而是正在向概念层次提升，以期达到更深入的应用。“概念检索”这一术语也频 繁出现于信息检索、人工智能等领域的有关文献中，但迄今为止一直没有看见 明确严格的定义。概念检索可以有广义和狭义两种理解：广义上讲，只要不仅 仅局限于单纯的字面匹配的检索，都可以称之为概念检索；而狭义上则专指语 义检索( 包括同义词、广义词、相关词等等) 。因此，在广义上，文档的结构信 息也从个侧面反映了定程度上的主题概念信息。x m l 文档区别于传统文档 最主要的一点就是其文档组织的结构化，而结构化本身就可以认为是一种概念 层次上的文档组织过程。针对x m l 文档的信息检索，不仅涉及传统的全文检 索技术以及目前i i 在广泛研究的语义硷索技术，还应当将文档的结构信息作为 一个重要的概念l q 索考虑进去，通过z tx m l 文档的结构建订索引，丈现结构 检索。 dfs u n 挺j 上，了将结构检索和语义硷索相结合( h i ，通过结构检索帮助用户快 基十x m l 的元数据近似匹配模型研究 速定位到文档结构细节，利用语义检索则满足读者语义层次的需求，从而实现 较全面的概念检索。该方法结合了中文分词技术的x m l 文档解析器对x m l 文 档进行结构分析和分词处理，采用b u s 技术【2 6 】对x m l 文档建立结构索引。同 时应用“上下文共现(