（计算机软件与理论专业论文）基于xml结构性约束的模式树查询最小化.pdf

山东大学硕士学位论文 摘要 随着计算机应用技术和电子商务的快速发展，企业可获取的信息数量和类型 有了极大的增长。由于x m l 的可扩展性、结构性以及平台无关性的优点，x m l 已经成为i n t e m e t 数据交换事实上的标准，在w e b 中得到广泛应用。如通过w e b 搜索引擎找到x m l 是自然而然的事情。在搜索引擎查找符合特定条件的x m l 文档时，即针对于x m l 数据库的进行查询。因此x m l 的查询优化具有巨大的 商业意义，成为目前研究的热点。 x m l 是专为w e b 设计的，把x m l 看作w e b 世界中的数据模型，目前流 行的x m l 数据模式有多种，如d t d ，x m ls c h e m a , r e l a xn g 等。定义x m l 数据的模式时，常遇到这样的情况，如定义的x m l 出现了某种形式的结构时， 必然有另一种形式的结构同时出现，这便是一类基于x m l 结构的完整性约束。 d t d 是一种基于语法的x m l 规范形式化定义，在考虑结构完整性约束时，一种 基于p a t t e r n 的x m l 规范形式化定义x s c s 模式可以与其联合使用，使得生成的 d t d 具有更为丰富的语义。 模式树是对像x m l 和l d a p 等树形结构数据进行查询的基础。在树形结构 数据库上进行树模式匹配的效率取决于模式树的大小，因而尽快发现和删除模式 中的冗余节点就显得十分的重要。模式树查询最小化问题，经证明是n p h a r d 问题。 在本文中，我们研究引入x m l 结构性约束时的x m l 模式树查询最小化问 题。具体来说，我们将在x s c s 模式下，基于几种路径的结构性约束，实现模 式树查询最小化。解决该问题的关键技术由c h a s e 技术和删除冗余节点算法两部 分组成。首先，我们使用c h a s e 技术对给定查询对应的模式树进行扩展，利用已 知的结构性约束，在不改变查询结果的前提下在模式树中增加节点，得到与原模 式树查询等价的一棵新的模式树；然后，利用约束独立情况下模式树查询最小化 算法，删除c h a s e 阶段生成的模式树中的冗余节点以及在c h a s e 过程中产生的新 节点，得到最终的模式树，此模式树对应的模式树查询即为原查询等价的最小化 查询。 山东大学硕士学位论文 本文中我们提出的x s c m 算法就是基于以上思路。经分析，该算法的时间 复杂度为多项式时间。实验结果表明，与x m l 查询的一般方法相比，x s c m 在 查询的数据量较小的情况下差别不大，但是查询数据量越大，查询效率越高，优 势越明显。x s c s 模式是针对x m l 数据模型定义了些常见的基于结构的完整 性约束，然而，还存在一类基于值的约束，基于值的约束在现实生活也是很常见 的，所以未来的工作我们将致力于基于x m l 值的完整性约束下的模式树查询最 小化，从而将x m l 模式树查询最小化问题扩展到更加广泛的应用范围。 关键词：结构性约束；x m l ：模式树；最小化 i i 山东大学硕士学位论文 a b s t r a c t d u et ot h er a p i dd e v e l o p m e n to fc o m p u t e ra p p l i c a t i o n t e c h n i q u e s a n d e c o m m e r c e t l l ea m o u n ta n dt y p eo fi n f o r m a t i o na v a i l a b l e t oe n t e r p n s e sh a sag r e a t i n c r e a s e b e c a u s eo fm ea d v a n t a g e s o ft h e e x p a n s i b l e ， s t r u c t u r a la n d p l a 廿0 1 1 = 1 1 i n d e p e n d e l np r o p e r t yo fx m l ，x m l h a si nf a c tb e c o m et h es t a n d a r do fd a t a e x c h 锄g eo ni n t e m e t x m li sd e s i g n e df o rw e bs p e c i a l l y a st h e i n t e m e td a t a e x c h a n g es t a n d a r d ，x m lh a sb e e nu s e dw i d e l yi nt h ew e b f o re x a m p l e ，n o w a d a y si t i so r d i n a r yt of i n dx m ld a t at h r o u g hw e bs e a r c he n g i n e t h a ts e a r c he n 粤n e ss e a r c h f o rx m ld o c 砌e n t st h a tm e e ts p e c i f i cc o n d i t i o n s ，i no t h e rw o r d s ，q u e r yo v e rt h e x m ld a t a b a s e t h e r e f o r ex m lq u e r yo p t i m i z a t i o n h a se n o r m o u sc o m m e r o a l s i g n i f i c a n c ea n d b e c o m e sar e s e a r c hh o t s p o t r e g a r dx m l 器t h ed a t am o d e li nt h ew e b w o r l d , x m lh a ss e v e r a ls c h e m a s ， s u c ha sd t d x m ls c h e m a , r e l a xn g a n ds 0o n i to f t e no c c u r r e dt ou st h a tw h e n 、ed e f i n et l l es t r u c t u r eo fx m l ，o n ef o r mo fs t r u c t u r e d e c i d e so n eo t h e rf o r m0 f s t r u c t u r e ，sa p p e a r i n g s u c hc o n s t r a i n ti so n ek i n do fs t r u c t u r a lc o n s t r a i n t s d t di s a g r a m m a r b a s e dx m ls c h e m af o r m a l i s m ，c o n s i d e r i n gt h e s t r u c t u r a lc o n s t r a m t s ，a p a 仳e m b 蚓觅s c h e m af o r m a l i s mc a l l e dx s c s c a nb ec o m b i n e dw i t hi t , a n dt t l e d e r i v e dd t dp r o v i d e sam o r eas e m a n t i cr i c hs p e c i f i c a t i o n p a t t e r nt r e e sf o r ma n a 觚a lb a s i st oq u e r yt r e e s t r u c t u r e dd a t as u c ha s 儿a n dl d a p s i n c et h e e f f i c i e n c yo ft r e ep a t t e r nm a t c h i n ga g a i n s ta t r e e s t r u c t u r e dd a t a b a s ed e p e n d so nt h e s i z eo ft h ep a t t e r nt r e e s ，i ti se s s e n t i a lt oi d e n t i f ya n de l i m i n a t et h er e d u n d a n t n o d e si n t h ep a t t e ma n dd os oa sq u i c k l ya sp o s s i b l e t h ep a t t e r nt r e em i n i m i z a t i o np r o b l e m h a sb e e np r o v e dt ob en p - h a r d i nt h i sp a p e r , w es t u d yt h ep a t t e mt r e eq u e r y n l i n i i m z a t i o np r o b l e mb yi n t r o d u c i n gs o m ex m l s t r u c t u r a lc o n s t r a i n t s t h ek e yt e c h n i q u e st ot h i s r e s e a r c ha r em a i n l yc o m p o s e do fc h a s ea n d 觚n i l l l i z 拍0 n f i r s t ，w ea p p l yt h ec h a s et e c h n i q u et o a r g u m e n tt h ep a t t e mt r e e c o r r e s p o n d i n g t ot h eg i v e nq u e r y w ea d dn e w n o d e st ot h ep a t t e r nt r e eb yu s i n gt h e l 【i l o 啪咖咖r a lc o n s t r a i n t si nt h ep r e m i s eo f n o tc h a n g i n gt h eq u e r yr e s u l t s t h e nw e o b t a i na ne q u i v a l e n tp a t t e r nt r e et ot h eg i v e nq u e r y n e x t ，b yu s i n g t h et r a n s f o r m a t i o n o ft h ee l ma l g o r i t h m ，w ee l i m i n a t et h er e d u n d a n tn o d e s i nt h ep a t t e mt r e ep r o d u c e d b yt h ec h a s ep h a s ea n d t h o s en o d e sa d d e dd u r i n gt h ec h a s ep h a s e e v e n t u a l l y ，w eg e t i i i 山东大学硕士学位论文 af i n a lp a t t e mt r e ew h i c hi sm i n i m a la n dc o r r e s p o n d st oaq u e r yw h i c hi se q u i v a l e n tt o t h eo r i g i n a lp a t t e r nt r e eq u e r y i nt h i sp a p e r ，w ep r o p o s ex s c ma l g o r i t h mw h i c hi sb a s e do nt h ea b o v ei d e a s a r e ra n a l y s i s ，t h ea l g o r i t h m st i m ec o m p l e x i t yi sp o l y n o m i a lt i m e t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tc o m p a r et ot h eg e n e r a lx m lq u e r yn l e t h o d s ，t h el a r g e rt h ed a t a a m o u n ti s ，t h em o r eo b v i o u st h ee f f i c i e n c yo fx s c m x s c ss c h e m ad e f m e ss o m e c o m m o ns t r u c t u r e b a s e dc o n s t r a i n t sf o rx m l h o w e v e rt h e r es t i l le x i s t sac l a s so f c o n s t r a i n t sw h i c ha r ev a l u e b a s e d f o re x a m p l e ，i ti sr e a s o n a b l et or e q u i r eam a n a g e r s a g eo f3 0 5 0y e a r so l d v a l u e b a s e dc o n s t r a i n t sa r ea l s ov e r yc o m m o n i nr e a ll i f e ，s o i no u rf u t u r ew o r kw ew i l lb ec o m m i t t e dt os t u d yt h ep a t t e r nt r e em i n i m i z a t i o n p r o b l e mu n d e rt h ev a l u e s b a s e dc o n s t r a i n t sf o rx m l t h u sw ec o u l de x t e n dt h e m i n i m i z a t i o no fp a t t e r nt r e eq u e r yp r o b l e mt oaw i d e ra p p l i c a t i o nf i e l d k e y w o r d s ：s t r u o t u r a lo o n s t r a i n t s ；x i m l ；p a t t e r nt r e e ；m i n i m i z a t i o n 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：社日期：上丝幽 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 文作者签名： 导师签名：谨弛期： 山东大学硕士学位论文 第一章绪论 x m l 规范已成为当前网络应用( 包括数字图书馆、w e b 服务以及电子商务) 中事实上的数据表达、交换的标准。针对x m l 数据的查询在当前x m l 数据 管理研究中占有重要的地位，也是当前x m l 数据处理研究领域的热点方向1 1 。 1 1 研究背景与意义 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) ( 最新的规范为2 0 0 4 年的x m l l 1 ) ，即可 扩展的标记语言，是一套定义语义标记的规范，其目标是能够定义计算机和人都 方便识别的数据类型。随着网络应用的快速发展，符合x m l 规范的数据( 称为 x m l 数据) 已大量存在于当前的信息社会，尤其是电子商务、w e 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 m l 模式树查询进行最小化。x m l 存储模型中加入一些基于结构的约束是很常 见的，这种基于结构性约束的x m l 模式具有更丰富的语义。当前x m l 查询技 术归入两大类：x m lq u e r y 方式和x m li r 方式，而x m l 模式树是x m lq u e r y 查询基础。在较短的时间内，解决基于x m l 结构性约束模式下的模式树最小化 问题，能够有效的提高对特定模式的x m l 数据检索的效率，从而提高w e b 数据 的访问率，因此具有巨大的商业意义。 1 2 研究现状 在本节中，我们将分别介绍x m l 模式和x m l 查询的研究现状。 山东大学硕士学位论文 1 2 1x m l 模式的相关研究 虽然x m l 文档是自描述的，它并不需要定义特定的模式或者类型，但为了更 方便和高效的支持查询和管理x m l 文档，提出了一些了用于描述b i t , 模式规范的 架构。其中，有一类是基于语法的x m l 模式形式化定义，包括已经被w 3 c 标准化 的d t d 以及x m ls c h e m a ，还有r e l a xn g 【2 1 等： ( 1 ) d t d 一个x m l 文件遵守d t d ( d o c u m e n tt y p ed e f i n i t i o n ) 中定义的种种规定。d t d 描述了一个x m l 文档的语法和词汇表，也就是定义了文档的整体结构以及语法。 简而言之，d t d 规定了一个语法分析器要解释一个“有效的”x m l 文件所需要 知道的所有规则的细节。d t d 原来是为使用s a v i i ，开发的，它可以是x m l 文 档的一部分，但是它通常是一份单独的文档或一系列文档。x m l 本身并没有一 个通用的d t d ，想使用x m l 进行数据交换的行业或组织可以定义他们自己的 d t d 。d t d 标记声明可以是元素类型声明，属性表声明，实体声明，或符号声 明。 x m l 提供一种称为文档类型声明的机制，用于定义对逻辑结构的约束，支 持预定义存储单元的使用。文档类型声明指定了文档使用的d t d 。文档类型声 明出现在文档的序言部分，处在x m l 声明之后和第一个元素之前。它可以包括 d t d ，也可以标识d t d 所在文档的u r l 。一个合法的x m l 文档必须符合文档 类型声明指定的约束条件。而且，它的基本元素必须是在文档类型声明中指明的。 d t d 的功用很多：定义内容模式，限制范围、属性的数据类型。 ( 2 ) x m ls c h e m a 由于d t d 本身也有着一些缺点，如采用了非x m l 的语法规则，不支持多 种多样的数据类型，扩展性较差，不支持名称空间( n a m e s p a c e ) 等等。w 3 c 又推 出了x m l s c h e m a 规范。事实上s c h e m a 也是x v l l 的种应用，它是将d t d 重 新使用x m l 语言规范来定义。这从某种意义上讲正好体现了x m l 自描述性的 优点。 x m ls c h e m a 中引入了丰富的数据类型，它们包括：布尔型，数字，e t 期时 间，u r l ，整数，十进制数，实数，时间段等。而且它还支持由这些简单的类 2 山东大学硕士学位论文 型生成复杂的类型，以及由用户定义的数据类型( 原型) 。同d t d 一样，s c h e m a 也提供了一套完整的机制以约束x m l 文档中标记的使用，而且支持名称空间。 每个人都可根据需要设计适合自己应用的s c h e m a ，并且可以同其他人交换 彼此的s c h e m a 。利用s c h e m a 能够书写x m l 文档，验证文档的合法性。另外， 通过映射机制，还可以将不同的s c h e m a 进行转换，以实现更高层次的数据交换。 ( 3 ) r e l a xn g r e l a xn g 模式提供了一种描述有效x m l 实例类的方法，这种方法比使 用w 3 cx m ls c h e m a 更强大、更简练并且在语义上更简单。r e l a xn g 的优 点在于：它在允许互不相关地可扩展数据类型以及方便地组合相关实例模型的同 时还扩展了d t d 经过良好证明的语义。 r e l a xn g 的语义非常简单，它是d t d 语义的自然扩展。r e l a xn g 模 式所描述的就是由量化、排序及交替组成的模式。另外，r e l a xn g 引入了用 于无序集合的模式，d t d 和w 3 cx m ls c h e m a 都不支持这种模式( s g 池支 持这种模式，但没有r e l a xn g 灵活) 。而且，r e l a xn g 几乎以相同的方 式来处理元素和属性。元素属性的一致性很符合x m l 的概念空间，这一点 比d t d 和x m ls c h e m a 中严格分离所做的要好得多。 假设如下场景：在定义一张商场的发票的x m l 结构时，如果顾客是会员身 份，发票联上应该包括会员折扣这一项，否则不包括。这是一种典型的基于结构 的约束。以上所述的x m l 模式规范均是基于语法的，然而x m l 数据同其它形 式数据一样，是现实世界的反映，也遵从现实世界的语义约束，单纯的基于语法 的d t d 或x m ls c h e m a 都没有足够的能力表示。a p r i lk w o n g 等人提出了一种基 于模式( p a t t e r n ) 的x m l 模式规范x s c s1 3 ( s t r u c t u r a lc o n s t r a i n t sf o rx m l ) ， 它在定义x m l 文档时引入了结构性约束。通过定义x m l 文档满足某种约束条件， x s c s 提供了一种有效的手段描述x m l 文档，这些约束以路径蕴含( p a t h i m p l i c a t i o n ) 、路径互斥( p a t ha b s e n c e ) 或路径同现( p a t hc o o c c u r r e n c e ) 为 形式。关于x s c s 的相关理论我们将在第二章详细介绍。 1 2 2x m l 查询优化的相关研究 早期的x m l 数据以文档方式存储，以关键字查询等信息检索手段查询，简 单、易用。由于缺乏系统的存储和查询机制的支持，造成查询能力低，不能满足 3 山东大学硕士学位论文 复杂条件的查询，更谈不上查询优化。一些现有的商业数据库系统扩充了处理 x m l 数据的功能，利用现有数据库成熟的技术，把x m l 查询要求转变为数据 库查询表达，由查询优化器优化查询表达并执行，再将查询的结果转变为x m l 数据。这种方法在一定程度上解决了查询复杂性的要求，但多级转换带来的问题 是效率的降低和查询语义的混淆。 与传统的数据库数据相比，x m l 数据具有如下特点： 数据是自描述的，内容与结构混杂在一起； 数据具有完整的嵌套层次； 数据是有序的。 x m l 数据的不规则性是对传统统计信息方法的重要挑战，其数据分布情况 使得一些传统的分布假设难以成立。为了达到所需的代价估计精度，需要更多的 统计信息。而结构的复杂性又为获得相对精确的统计信息带来存储和计算上的困 难。，的有序性制约了转换规则的灵活性。x m l 数据的上述问题无论是对关 系数据库或是对面向对象数据库的现有查询优化技术都是严峻的挑战。对于 x m l 查询的相关研究参见文献 4 1 4 】。 与传统的查询需求相比，x 池查询具有如下特点： 以长路径表达式为查询的核心语句，路径复杂，包含分支路径； 嵌套的查询表达，查询表达式中加入编程语言的嵌套和条件判断思想； 路径中包含不确定因素，这在之前的查询需求中未出现过； 查询对象和返回结果类型不确定。 面向对象数据库已有一些处理复杂长路径表达式的经验，但无法处理儿 查询中的路径表达式中的不确定情况：关系数据库中已有很多处理嵌套查询的方 法，但对掺杂编程语言风格的x 地查询语言却难以适应。 综上所述，来自数据结构和查询需求两方面的问题导致基于关系和面向对象 数据库的查询处理和查询优化技术均不能适应x m l 查询的需要。目前，从d t d 中获得的约束条件并不充分，这也是导致优化不彻底的一个因素。如何抽取更多 的语义约束条件，是未来研究的一个重要问题。 4 山东大学硕士学位论文 1 3 论文的主要贡献 本文针对基于p a t t e r n 的x m l 一种新模式：x s c s 的基础上，引入了结构性 约束，在此基础上对模式树查询进行最小化。本文提出了一种算法x s c m ，在给 定x m l 结构性约束情况下，在多项式时间生内成与原模式树查询等价的最小模 式树。最后，论文将证明x s c m 算法的正确性，并通过实验验证算法的精确性 以及有效性。 本文的主要工作和创新点在于： 1 论文对x m l 的几种常用模式进行综述，并对其优缺点进行比较。 2 对模式树查询的研究现状和存在的一些问题进行剖析。 3 论文提出一种基于结构性约束下进行模式树查询最小化的算法x s c m ， 并通过实验结果证明算法效率。 1 4 论文的组织结构 本文共分为五章，其后续章节的组织结构安排如下： 第二章x m l 结构性约束模式规范的相关概念，先对x m l 文档的路径表示 和x m l 结构性约束表示做了形式化描述，继而具体介绍了x s c s 模式规范的相 关理论。 第三章介绍了模式树查询最小化的相关概念，分别从语法优化和语义优化两 个方面说明模式树查询优化的研究现状，本章最后给出在x m l 满足某种结构的 条件下约束独立的模式树查询最小化算法c i m ，为下一章的x s c m 算法奠定基 础。 第四章先给出基于x m l 结构性约束的模式树查询问题的数据模型和该问题 的形式化描述，然后提出了x m l 结构性约束的模式树查询最小化的具体分析方 法、步骤以及算法实现，并通过实验数据得出相应参数的合适取值以及结果近邻 集更精确的结论。 第五章对课题研究做了客观总结，提出了它提高精确度的同时存在的影响精 确度的细节，以及有待进一步研究的部分。 山东大学硕士学位论文 第二章x m l 结构性约束模式概述 x m l 是半结构化的，而半结构化数据缺乏统一结构，并且通常是自描述的， 这就是说，模式和数据都存在于数据之中。某些半结构化数据并没有固定的模式， 另外一些半结构化数据虽然有模式但是对于数据的约束不大。这些特点决定了 x m l 数据不可能使用常规的关系模型来进行描述，而需要提出专门的半结构化 数据模型。由于目前流行的描述x m l 数据模型的规范包括诸如d t d ，x m l s c h e m a 等，却无法描述一些常用的语义约束。考虑到这些原因，因此我们选择 x s c s ，一种基于结构性约束的x m l 模式规范，作为我们的研究模式树查询的数 据模型。其他关于x m l 模式约束的研究可以参见文献 1 5 2 1 】。本章将首先介绍 x m l 文档的树表示以及x m l 路径表示，基于此对x m l 结构性约束表示做了形 式化描述，继而具体介绍了x s c s 模式规范的相关理论，从而为后文的研究工作 奠定理论基础。 2 1x m l 树和路径 我们有时需要为x m l 数据定义一些复杂的结构性约束，这些结构上的约束 通常不是指x m l 文档元素之间简单的父子或兄弟关系。试想这样一个场景，一 个x m l 文档片断中，存在着以某个类型的元素为起点的某条路径意味着同一片 段中存在着一条或者几条其他特定的路径。虽然这种情况在实际生活中十分常 见，但基于语法的d t d 或x m ls c h e m a 等传统的x m l 模式规范都没有足够能 力表示这种语义。本节中，我们将会在x m l 文档路径表示的基础上，给出x m l 结构性约束的形式化描述，以便于读者理解。 2 1 1x m l 文档的树表示 x m l 是一种m e t a - m a r k u pl a n g u a g e ( ：元；标记语言) ，可提供描述结构化资料的 格式。x m l 提供了一种独立于运行程序的方法来共享数据，用来自描述信息的 一种新标准语言。x m l 由若干规则组成，这些规则可用于创建标记语言，并能 用一种被称作分析程序的简明程序处理所有新创建的标记语言，正如h t m l 为 计算机用户订阅i n t e m e t 文档提供一种显示方式一样，x m l 也创建了一种任何人 6 山东大学硕士学位论文 都能读出和写入的世界语。v 几能增加结构和语义信息，可使计算机和服务器 及时处理多种形式的信息。 符合x m l 规范的数据称作x m l 数据，x ，数据的基本形式为x m l 文档。 这类数据有两个基本特点：一是自描述，x m l 数据本身就已经包含了元数据一 一关于数据本身的信息，表现为不同语义的标记( t a g ) ，如元素( e l e m e n t ) 和属 性( a t t r i b u t e ) 。在所有标记中，元素标记最为重要。一个标记由两个起、止标 签构成，起止标签所含的文本就是对应的语义单元；二是半结构化，即不同于传 统关系数据库( 传统的数据库都有一定的数据模型，可以根据模型来具体描述特 定的数据) ，x m l 数据的结构限制并不严格，表现为语义单元相互嵌套的层次关 系。下面我们将给出一个实际的x m l 文档，它记录了一次拍卖的相关信息，此 次拍卖成交了一个，拍卖的具体信息包括拍卖品，买家，买家，拍卖类型，价格 等。首先我们给出其自描述的d t d 定义如下( 其中，对于某些类型是# p c d a t a 的元素的说明我们没有特别给出) 。 i 殴j d 哐盯a u c t i o n s cle i d 悒n 了a u c t i o n ! e l e m e n tb u y e r ! e l 日促盯s e l l e r c ! 豇融但n tc o n t a c t ( i t q m ，s e l l e r ，b u y e r ，p r i c q ，p a ! r m e n t ) ( c o n t a c t ) c o n t a c t ，t y p e ) ( m e ，e m a l l ? ，p h o n e ? ) ( p e r s o n a lls t o r e ) ( n a m e ，珊i ) ( i 乞e m i d ，d e s c r ) c l o s i n g b l d ，t 缸? ) c r e d i t c a r dim o n e y o r d e rip a y s ) ( c a r d n u 盟，e x p d a t e ) 图2 - 1 的d t d 下面我们给出该x m l 文档的具体实例。 7 山东大学硕士学位论文 在实际处理x m l 数据时，更为常见的是x m l 标签有向图模型，由x p a t h 规范描述。形式上可以看成图2 3 即为 满足x p a t h 树模型定义对应 x m l 树。 8 山东大学硕士学位论文 沏i a k 刺| s u p e e 奶r e “ 9 9 3 9 9 争9 9 5 图2 - 3 对应的x m l 树 x m l 文档与x m l 树之间的对应关系显而易见，在此不再赘述。 2 1 2x 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 文档d 看成一棵标签有向树，e 为定义该x m l 文档所有元素 名称构成的字母表，乃为d 对应的x m l 树中所有的顶点集合，则路径p 是一个 简单的有序的元素名称的集合口e 2 e n ，其中e i e ，空路径记作。路径中 元素的数目为该路径的长度，记作l e n g t h ( p ) 。 一条路径如果出现在给定的x m l 文档d 中，则称它为文档路径。文档根路径 是指路径第一个元素是该文件的根元素的文档路径。在给定的x m l 文档d 中，同 一条文档根路径p j e 2 册可以指定玩中都由e n 标记的不同的节点，因此，一 条指向节点， 坛) 的文档根路径可以简单记作节点v 的路径。我们将d 中所有 表示文档根路径p 的节点集合，称作路径p 在文档d 中的扩展，将其记作 e x t e n t d ( p ) 。 9 甲一 山东大学硕士学位论文 由于任意文档路径都可以加上若干元素填充成为一条根路径，因此，如果不 加特殊说明，本文所指的路径都是文档根路径。最后，我们给出最长公共路径的 定义，给定两条路径p 1 和p 2 ，p 1 和p 2 的最长公共前缀为p 1 和p 2 的最长公共 路径，记作l c p ( p l ，p 2 ) 。 2 2x s c s 模式 x s c s 是一种基于模式( p a t t e r n ) 的x m l 模式规范，由a p r i lk w o n g 等人在 2 0 0 2 年提出，也可以说是为了解决基于语法的x m l 模式规范不足以表示某些语 义约束而应运而生。它在定义x m l 文档时引入了结构性约束，这些结构性约束以 路径蕴含、路径互斥或路径同现为主要形式。本节首先给出x s c s 中结构性约束 的形式化描述，然后简单介绍了x s c s 的相关理论，最后同使用最广泛的x m l 模 式规范d t d 做比较，分析二者的联系。 2 2 1x m l 结构性约束形式化表示 x s c s 提出了三种形式x m l 结构性约束，都是基于路径的，包括路径蕴含， 路径互斥或路径同现。其中，路径蕴含和路径互斥最为重要。在介绍三种路径约 束之前，我们首先给出后代扩展( d e s c e n d a n te x t e n t s ) 的定义。 定义l ( 后代扩展) ：p l 和p 2 是x m l 文档d 的两条文档根路径，p l 和p 2 的后代扩展记作d e x t d ( p l ，p 2 ) ， 是场的一个子集矿，y 的中的元素 ，e v 满足 下列两个条件： ( 1 ) ，e e x t e n t d 囟矽： ( 2 ) d 中存在v 后代节点 ，玩且， e x t e n t d ( p 2 ) ； 如果p l = p 2 ，则d e x t d 咖j ，p 2 ) = e x t e n t d 囟= e x t e n t d 囟矽。 下面我们在后代扩展的基础上，将分别给出路径蕴含和路径互斥的形式化定 义，并通过例子说明它们的现实意义。 定义2 ( 路径蕴含) ：p l 和p 2 是x m l 文档d 的两条路径，且l c p ( p l ，p 2 ) 2p ，路径蕴含约束表示为p 唧2 ， 当且仅当d e x t d 融p 矽= d e x t d 函p 矽，我们说 文档d 满足p l 蕴含p 2 ，记作d | _ p l _ p 2 。 我们说文档d 满足路径共现p 1 呻2 当且仅当p 1 _ p 2 且p 2 _ p l 。 1 0 山东大学硕士学位论文 定义3 ( 路径互斥) ：p l 和p 2 是x m l 文档d 的两条路径，且l c p ( p l ，p 2 ) = p ，路径互斥约束表示为p l _ l _ p 2 ，当且仅当对于任意元素e d e x t d ( p , p o ，有 e 矛d e x t d 积p 矽，我们说文档d 满足p l 互斥p 2 ，记作df = p l _ t _ p 2 。 我们用下图帮助读者理解这三种结构性约束。 o t 图2 4 一个示例x m l 树 图2 - 4 的x m l 树显示了某个x m l 文档的三个可由路径p 到达的片段d f l ， d f 2 ，d f 3 。当只有片段d f l 时，满足p 1 呻2 ；当没有片段d f l 时满足p l 上p 2 ： 在没有片段d f 2 时满足p l _ p 2 。 结合在上一节中给出的 及其d t d 的例子，我们给出该x m l 文档存在的几个路径约束，并从语义角度解释这三种基于路径的结构性约束的实 际意义。在描述路径约束时，为了形式简洁，可以提取公共路径前缀放在约束的 前一部分，而将路径的不同部分表示在约束的两端。 c l ：a u c f i o n s a u c t i o n ：s e l l e r t y p e s t o r e - - p r i c e t a x 这个路径蕴含约束表示：当拍卖的卖方类型是商店时，则拍卖的价格中必须 包含税。 c 2 ：a u c t i o n s a u c t i o n ：s e l l e r t y p e p e r s o n a l _ l t a x 这个路径互斥约束表示：当拍卖的卖方类型是个人时，则拍卖的价格中不必 包含税。 c 3 ：a u c t i o n s a u c t i o n ：p a y m e n t p a y p a l - - - b u y e r c o n t a c t e m a i l 这个路径蕴含约束表示：当拍卖的支付方式是贝宝( 种外国常用的网络支 付方式，类似于我们常使用的支付宝) 时，拍卖的买方必须留下e m a i l 的联系方 式。 山东大学硕士学位论文 c 4 ：a u c t i o n s a u c t i o n s e l l e r c o n t a c t ：一一p h o n e 这个路径共现约束表示：拍卖的卖方的联系方式必须包括电话。 c 5 ：a u c t i o n s a u c t i o n s e l l e r c o n t a c t ：一一e m a i l 这个路径共现约束表示：拍卖的卖方的联系方式必须包括电子邮件。 2 2 2x s c s 模式理论 x s c s 模式可以简单理解成为一组基于路径的结构性约束的集合。我们将在 本节系统的介绍x s c s 模式的相关理论，包括两部分，一是x s c s 的推理规则，逻 辑蕴含的概念，推理规则对逻辑蕴含的完备性定理；二是x s c s 同x m l 文档的一 致性的相关理论。 给出了x s c s 的结构性约束的形式化描述后，我们可知三种路径约束实际上 是两条路径的二元关系，表2 - 1 显示了这些二元关系与一些特殊的性质，诸如自 反性，对称性，传递性之间的关系。 表2 - 1x m l 结构性约束的性质总结 约束 自反性 对称性传递性 路径蕴含 _ 路径互斥 - 路径共现 -t0 我们现在给出x s c s 的推理规则如下： r i ：如果l c p ( p 1 ，p 2 ) = p l ，那么p 2 _ p 1 r 2 ：如果p 1 一p 2 且p 2 _ p 3 ，那么p 1 一p 3 r 3 ：如果p 1 上p 2 ，那么p 2 上p 1 r 4 ：p l _ p 2 且p 2 - - - ，p l ，当且仅当p 1 p 2 r 5 ：如果p l - - p 2 ，p l 上p 3 ，并且l c p ( p 2 ，p 3 ) 是l c p ( p l ，p 2 ) 的前缀，那 么p 2 上p 3 在我们把x s c s 模式看成一组基于路径的结构性约束的集合时，考虑x m l 文档同x s c s 的关系。假设是一组结构性约束的集合，当x m l 文档d 满足乏中 所有的约束时，记作df = z 。结合2 1 2 节中给出的实例，设 的 1 2 山东大学硕士学位论文 x s c s 记作= ( c 1 ，c 2 ，c 3 ，c 4 ，c 5 ，显然舭文档 满足z 中所有的 约束。 定义4 ( 逻辑蕴含) ：给定两个x s c s 集合z 和中，对任意x m l 文档d ，如 果d f = ，都有d l = 中，我们说z 逻辑蕴含中，记作窆l = 中。 定理1 ：推理规则f r l r s 对x s c s 的逻辑蕴含是健全和完备的。 由定理1 可知，规则f r i r 5 形成了x s c s 的公理系统。 定义5 ( p 一致性) ：给定一组路径的集合p 和一个x s c s 集合z ，我们说 是p 一致( p c o n s i s t e n c y ) 的，当且仅当存在这样一个x m l