（计算机应用技术专业论文）基于自动机技术的xml文档处理研究.pdf

信息工程大学硕士学位论文 摘要 l 是w 3 c 于1 9 9 8 年推出的一种标记语言。由于其独特的技术优势，讧l 推出 后很快就成为网络中数据表示及交换的标准。因此，要构建基于x m l 的各种应用，准确 并高效的从l 数据源中查询并获取数据就成为其中关键的一步。论文以自动机技术作 为研究基础，对x q u e i y 文档的有效性验证和x m l 文档查询优化这两个方面进行了理论 与实验探讨。 针对x q u e f y 文档有效性验证问题，对几种x m ls d 嫩n a 类型验证方法进行了分析与 比较，然后选择其中一种基于树自动机的类型验证方法进行深入研究，指出该方法所用算 法在处理x q u e r y 这种具有嵌套复杂类型的数据结构时存在的局限性，继而对算法提出了 改进，并分析了改进后算法的正确性和复杂度。 针对目前订l 文档查询优化技术研究中存在的不足之处，提出了一种高效的查询优 化方法，此方法包含了两个关键技术：一是鉴于，( m l 树模式查询中出现的冗余节点，提 出一种有效的树模式查询优化技术，此技术针对无论是否存在完整性约束时，都能达到树 模式查询的最小化，使得查询表达式得到了简化；二是在此基础上结合基于视图的l 局部查询重写技术，更完善地实现了v i l 文档的查询优化。 最后设计并实现了一个讧l 文档处理系统。根据前面提出的x m l 验证技术和查询 优化技术的基本思想，分析和设计了此系统的体系结构。本系统首先对用户提交的x 0 u e r y 文档进行有效性验证，然后通过本文所提出的查询优化技术实现x m l 文档的查询优化处 理，并执行得到查询结果。另外，还设计了两组测试方案对本系统进行测试，并通过实验 结果分析，来验证本文所提出的查询优化技术的可行性和有效性。 关键词：x m l ，有效性验证，查询优化，自动机 第1 页 信息工程大学硕士学位论文 a b s t r a c t ) ( 1 li sr e l e a s e d 舔am a r k u pl a n g 吡g eb yw 3 ci n1 9 9 8 a sar e s u l to f i t s 吼i q u e t e c h n i q u ea d v 强t a g e x m lr a p i d l yb e c o m e s t l l es t a i l 删o f 如衄r e p f e s e n t a t i o na n de x c h a n g e o nm ew 曲t h e r e f o r e 旬rb u i l d i n g 叩v 撕o u sa p p l i c a t i o n sb a s e do nx m l ，i ti si n i t i a i i y i m p o r t 绷t t 0a c c l l r a t e l y 卸de 丘色c t i v d yq u e r y c a p t u r ed a t af 而mx m ld a t as o u r c e o nm eb a s i s o fm ea u t o m a t at c c h n i q u e ，t h i sp a p c rd i s c u s s e st l l ee 岱e c t i v ev a l i 出l t i o no fx q u e 叮d o c u m e n t a n dx m lq u e r yo p t i m i z a i o nb yb o t ht h c o r ya n de x p e d m e n t s w i t it l l ef o c u so nm e p r o b l e i no f e 丘t i v ev a l i d a t i o no f 1 cx q u e r yd o c i i m e m ，、靶m a k ea c o m p a r a t i v ea n a l y s i sb c t w 嘲s c v 酬：k m ls c h 啪at y p ev a l i d a t i o na p p a c h e s ，a n dc h o o s ea t y p ev a l i d a t i o na p p r o a c hb a s e do nt i ea u t o m a t at od e e p l ys t i l d y a n e rf i n d i n go u tm el i m i t a t i o n o ft h ea i g o r i t h r nw l e np m c e s s i n ga nx q u e 叮d o c u m e n t ( s u c had a t as 佃l c t u r et h a th a v e e i i l b e d d e dc o m p l e xt y p e ) ，w ep r o p o s eai m p r o v e da l g o r i t h r n ，t h e na n a l y z et h ec o r i 优t n e s sa n d c o m p l e x i t yo f t h ei m p r o v e da l g o r i m m w 曲t h ef o c u so nd 幽c i e n c yo ft h ec i l 仃e n tx m l q u e i yo p t i m i z a t i d n 嬲e a r c h e s ，w e p r e s e n ta ne 行b c t i v eq u e r yo p t i m i z a t i o n t h eo p t i m i z a t i o nc o n s i s t so f “幻l ( e yt e c h n o l o 百e s ：f 0 r t h er e d u n d a i l c yn o d e si nx m l 缸优- p a t t e r i lq u 耐e s ，w ep r e s e i l ta i le 任t i v en 一p a t t e mq u e r y o p t i m i z a t i o n w h e t h e rm e f ea r ei n t e 鲥t yc o n s t r a i n t so rn o t ，m e 船c e p a t t e n lq u 盯i e sa n d 山e q u e r ye x p r e s s i o i l sa r em i i l i m i z c d 0 nt h eb a s i so fa b o v er e s e a r c h 岱，w eu t i l i z et h ex m lp a r t i a l q u e r yr e 、砌t i n gt e c h n i q u eb a s e do nv i e w st or e a l i z em ex m l d o c i l m e i l tq u e 眄o p t i m i z a t i o n a tl 勰t ，w ed e s i g na l l dr e a l i z ea nx m ld o e n tp r o c 嚣s i i l gs y s t e r r i a c c o r d i n gt ot h e e s s t i a li d e ao f ：j ( m lv a l i d a t i o na n dq u e 叫o p t i m i z a t i o nt c c h n i q u ep r e s c n t c da b o v e ，w ea n a l y z e 雅dd e s i g n 出ea r c h j t e c m r eo ft l l es y s t c m t h es y s t 锄f i r s tp r o c e s s e se 丘如t i v ev a l i d a t i o nt om c ) ( q u e r yd o c u m tm a tl l s e r 鲫b m b ，t 1 1 e ni m p l e n l e n t st t l eo p t i m i z a t i o np m o 髑s m gw i mm e q u e r yo p t i m i z a t i o ni nt l l i sp 印f i i i a l l yc 枷e si to u ta n dg c t sr e s u l t s m o r e 0 v t h ep a p e ra l p r e s e f l t st w os c e n 撕0 st ot e s tt h es y s t e m i t sw 缸f i e df b mm ee x p e f i m e mr e s u l t sm a tn l en e w q u e r yo p t i i i l i z a t i o nm c l o dp f e s a l t l 甜i nt l l i sp a p e rc a n1 1 i g h l yi r n p r o v et h ex m lq u e r y e f f i d e i l c y k e 啊o r d s ：x m l e f f 宅c t i v ev a l i d a t i o n ，q u e r yo p t i m i z a t i o 玛a u t o m a t a 第1 i 页 原创性说明 本人声明所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写 过的研究成果，也不包含为获得信息工程大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并标示谢 意。 学位论文题目：基王自动扭撞苤的型l 塞挡处理班究 学位论文作者签名：查照基 日期： 作者指导教师签名： 细0 7 年年月幻日 日期：为0 7 年牛月2 d 日 学位论文版权使用授权书 本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学 可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借 阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：基王自动担撞盔的戮l 塞挡处堡班究 学位论文作者签名：查也整 作者指导教师签名： 名瞽毛丝_ 一 日期：如0 7 年 日期：7 年 4 月2 0 日 4 月2 q 日 信息工程大学硕士学位论文 1 1 研究背景 第一章绪论 ) 0 沮川( e x t e r 培i b l e 咄u pl a n g u a g e ，可扩展标记语言) 是w 3 c 组织于1 9 9 8 年发布 的标准。标准发布后，得到了i b m 、s u n 、o m c l e 和m i c r o s o f t 等大公司的支持，并取得 了迅猛的发展，获得了广泛的应用。大量的订l 数据不仅出现在w 曲上，而且出现在 信息处理的各个领域，它已成为数据组织和交换事实上的标准。随着l 技术应用的深 入，l 数据量以指数级疯狂增长，因此x m l 数据及文档的管理和查询问题也越来越 引起人们的重视。 对于x m l 的管理，x m l 数据库必须拥有完善的类型系统和灵活的类型处理机制， 以实现对各种讧l 数据的类型定义和类型处理。一个完善的类型系统应具有类型定义和 类型检验两项基本功能【2 】。通过定义类型，) 几文档中的属性和元素的数值范围可以得 到明确界定，具有相同或相似特性的数值可以得到有效的分类管理，应用程序的可重用性 也将得到提高。通过类型检验，在静态编译阶段就可以发现和避免程序动态执行时可能出 现的类型错误，从而保证了程序的稳定性和可靠性。一个与类型定义密切相关的问题是类 型验证问题，它主要是用于验证他数据是否符合相应的类型特性，从而实现了对订l 文档的有效性验证。目前针对江l 类型验证的研究也比较多，但已有的技术仍需进一步 的完善。 对于) ( ! “l 的查询，尽管l 数据表现形式灵活，可以描述非常复杂的结构，但儿 数据本质上是一种自描述的半结构化数据，它的数据模型不同于以往的层次、关系、面向 对象数据模型，是树状的模型。树中的每个节点对应于一个元素，树中的边描述了元素之 间的父子关系。针对这种树状数据的查询，学者们已经提出了多种) a 订l 查询语言，如 l o r e i 【3 l ，a t h 【4 】，x m lq “5 1 ，q u e r y 【6 1 等，它们都是基于正则路径表达式r p e ( r e g u l a r p a t l le x p r e s s ) 的查询语言。 所谓正则路径表达式，是指能够以l i k c s q l 语言的方法表示查询的内容，但却可以 结合一些特殊字母或符号，来描述) q 讧l 文件的阶层式及树状资料内容，如树状结构子孙 关系的描述等。举例来说，如果想查询某文件是否含有曲g r o u p m e l n b 既。伍c e r o o m 、 d b g r o u p m e m b 既f 0 0 m 、d b g r o u p v i p o 伍c c r o o m 、d b g r o u p v i p r o 锄的路径结构，我们只需 要正则路径表达式r = d b g r o u p ( m e m b e r | “p ) o 妇丘c e r o o m 的叙述，而不需要下达四个不同的 路径来查询。所以，利用正则路径表达式查询) ( 1 l 文件，将有助于增加语法的弹性能力， 并满足x m l 文件的结构特性，从而更好地实现查询的优化。 鉴于大多数的) ( 1 订l 查询都是基于正则路径表达式，而有限状态自动机能够很好地描 述和处理正则路径表达式，复杂的正则路径表达式都可以将其转换为相对应的非确定有限 第1 页 信息工程大学硕士学位论文 状态自动机来表示。因此本文将在基于自动机技术的基础上，实现对x m l 文档的处理研 究。 1 2 国内外研究现状 1 x m l 文档有效性验证问题研究现状 为了验证订l 文档的正确性，w 3 c 颁布了d t d ( d o c 啪e n tt y p ed c c l a r a t i o n ，文档 类型定义) 以定义某份讧l 文档的格式，也就是将每一个元素包含哪些子元素、属性以 及各元素出现的顺序等，清楚地加以定义与规范。若一份引用d 1 巾定义的v i i 。文档内 容违背了该d t d 的定义，在分析此订l 文档时，便会发生验证错误。 使用x m l 解析器来解析l 文档时要对其进行一系列的处理，其中包括基于d t d 或x m ls c h e m a 来验证文档的有效性，即审核目标订l 文档是否具有其d t d 或x m l s c h e m 中规定的文档结构和数据类型。因此) a l 文档的有效性验证问题包含了讧l 的 类型验证问题。所以说此领域的研究重点将是基于模式语言的订l 类型验证问题。 目前，人们对l 类型验证问题还在进行不断地研究。由于存在众多被广泛使用的 v i l 发布和转换语言，如a t l l 、x q u c r y 等，很难用某一种形式的语言来进行统一的描 述。此外还存在各式各样的讧l 模式语言，如讧ls c h 锄a 【7 一，r e l a x l 9 噜。发布和转 换语言以及模式语言的多样性无疑都使得x m l 类型验证的研究对象过于复杂，给类型验 证的解决带来了一定的困难。 研究发现：d t d 虽说严格定义了文档结构，但它只支持功能相对较弱的字符类型的 定义和约束，一旦需要对更丰富的类型进行描述时就会遇到困难。与之不同的是，讧l s c h e m a 允许用户为文档中元素声明各种特定类型，并在使用解析器检查文档结构是否有 效的同时也对数据类型进行有效性验证，并能从文档中提取实际数据信息传递给应用程 序。如果解析器支持订ls c h e m a ，则能进行基于) 0 d ls c h 锄的类型验证。 鉴于沮。s c h e m a 已经成为目前较为成熟且类型描述能力较强的咀模式语言，文 献 1 0 】中给出了一种基于) m i l s c h e m a 的x m l 类型验证系统的原型，通过使用树自动机 来描述订ls c h e m a 实现对输入文档的类型验证。可以证明在一般情况下，给定两种类 型t 1 和记，验证是否f l 记的问题的复杂性为指数级，而当记能由一个确定树自动机 产生时，其复杂度为多项式级【】。在文献【1 2 】中，m n i c o l a 和j j o l l i l 则从v i l 解析器 的分析出发，通过增加具有类型检验功能的过滤层来实现对类型验证的支持。 以上这些技术对于处理) 洲l 文档的有效性验证时都能起到很好的作用，但它们也有 不足之处，如在处理有嵌套复杂类型的x m ls c l l e m a 验证时可能无法正常运行，这需要 我们在此方面对其进行深入研究。 2 x m l 查询优化问题研究现状 由上节中提到的，目前大多数的) ( i 订l 查询都是基于正则路径表达式的，下面我们就 对此领域的研究现状分析如下： 第2 页 信息：i ：程大学硕士学位论文 目前主要有两种处理基于正则路径表达式的讧l 查询的方法。第一种方法利用传统 的数据库，如关系数据库或者面向对象数据库来存储和查询订l 文件。在这种情况下半 结构化查询语言将转化为相关的数据库的查询语言，并且可以使用传统数据库系统的一些 查询技术。为了使订l 的数据模型能够使用传统的数据库系统进行描述，就必须建立一 个合适的数据库结构，并建立正确的映射关系。第二种方法，由于x m l 文件可以被看成 一种图状的半结构化数据模型，所以可以使用对于半结构化数据的特殊的查询机制。在这 种情况下，正则路径表达式的查询可以定义为：给定正则路径表达式r 以及一个数据图d ， r 在数据图d 上进行查询得到的结果为在图d 中满足此路径表达式r 的一组对象的集合。 举例来说，正则路径表达式m o v i e ( + a c t o r ( t o m | j a c k ) ) 描述的是满足首先经过边 “n l o v i e ”，然后经过任意次边达到边“a c 幻r ”，最后再经过任意次边达到边“t 0 m ”或边 “j a c k ”的所有的路径。对于其在l 数据图的查询结果为) ( 1 l 数据图中的满足这些 路径的所有的节点的集合。 对于如何优化x m l 查询，提高查询效率，目前进行了许多的研究并提出了相关的技 术，主要分为两大类： 一类是利用一些索引、编码等方法，来提高x m l 查询检索的效纠b 1 4 ”】。此类方法 的主要目的都是希望能够快速且直接有效的改善查询检索时的效率，降低查询所花费的时 间或花费的成本。其中文献【1 3 】提出了一种针对基于正则路径表达式的订l 查询处理的 方法，文章中所提到的d a t a g u i d e 是一个具有方向性且无回路的有向图，利用图中每条唯 一的路径，描述订l 文件中出现的路径。对于d a t a g u i d e 中的各节点，都对应原) ( 1 v i l 文件中某个特定路径的节点码。简单的说d a t a g u i d c 是利用有限状态自动机的观点来解决 正则路径表达式查询的问题，即将x m l 文件作为非确定有限状态自动机，转换成为确定 有限状态自动机。利用此方式，将减少使用正则路径表达式查询讧l 文件，必须大量的 检查文件中所有可能的路径，达到加快查询的目的。而文献【1 4 】对 1 3 】进行了改进，对索 引结构建立了复杂度，并对正则路径表达式的查询方式，提出了一个更完善的索引机制 1 乙i n d e x 。 另一类是利用已有的视图资源对) 洲l 查询进行重写，来优化l 查询。由于目前 在因特网上存在着海量的类似于x m l 这样的半结构化数据，在信息集成中也产生了大量 的半结构化视图，因此如何利用己有的基于正则路径表达式的半结构化视图来重写用户查 询，减少响应时间也成为当前研究的一个热点问题。文献【1 6 ，1 7 ，1 8 】论述了关系数据查询 重写的问题，而文献 1 9 】则论述了面向对象数据的查询重写的瞎题。它们主要对通过视图 的定义、视图的维护、以及算法复杂度的分析和研究，提出了利用视图进行查询重写的一 些方法。在半结构化数据模式中，同样也进行了大量的研究。文献【2 l ，2 2 ，2 3 】中描述了对 于基于正则路径表达式的半结构化查询q 以及视图v - v l ，v n ，如何利用这些视图重写 查询q ，得到一个新的查询q 的方法。此方法主要解决了利用视图对查询进行完全重写 的问题，但如果视图只包含局部的查询信息时，如何对查询进行有效的重写并没有进行深 第3 页 信息工程大学硕士学位论文 入的研究。同时，在查询重写前对查询表达式进行简化来达到查询的优化也是在此领域值 得研究的方向。 1 3 本文所要完成的工作 本文在广泛的阅读与分析目前国内外的相关资料后，围绕着“) ( i l 文档处理研究” 这一主题展开，归纳了现有的v f l 验证及查询优化技术，并对现有技术进行科学性分析。 针对大多数订l 查询语言都支持的基于正则路径表达式查询方式，以自动机理论作为研 究基础，设计出一个) ( 1 v i l 文档处理系统。具体的，主要完成的工作如下： ( 1 ) 经过对现有的x m l 文档处理技术的研究和总结，将x m l 验证及x m l 查询优 化技术作为两大研究方向，并分别对这两个方向的研究现状进行分析，确定今后研究的具 体方向：使用基于x m ls c h 锄a 的类型验证技术来实现x m l 文档的有效性验证；使用基 于正则路径表达式的查询语言来进行查询优化处理。同时提出目前已有技术研究中存在的 一些有待完善的方面。 ( 2 ) 通过对目前基于x m ls c h e i i l a 的类型验证方法的对比分析，选择基于树自动机 的x m ls c h 锄a 验证方法进行深入研究。在分析已有算法的有限性后，提出一种改进的 基于树自动机的x m ls c h e m a 验证方法，通过它来实现x q u e r y 文档的有效性验证。 ( 3 ) 针对目前) ( 1 l 查询优化技术研究中存在的不足之处，提出一种高效的查询优 化方法，此方法包含两个关键技术：一是鉴于x m l 树模式查询中出现的冗余节点，提出 一种有效的树模式查询优化技术，此技术针对无论是否存在完整性约束时，都能达到树模 式查询的最小化，使得查询表达式得到简化；二是在此基础上结合基于视图的订l 局部 查询重写技术，更完善地实现x m l 文档的查询优化。 ( 4 ) 根据以上提出的技术方法，对x m l 文档处理系统进行设计和实现，并通过实 验来验证此系统可较大地提高x m l 文档的查询处理效率。 1 4 本文的组织结构 本文共分为六章，主要内容安排如下： 第一章，绪论。介绍研究课题的背景，并给出本文篇章的结构。 第二章，相关概念及理论。其中涉及的主要概念及理论包括：v i l 概述和自动机理 论。 第三章，x q u e r y 文档的有效性验证。通过对基于x m l s c h e m a 类型验证方法的分析， 提出了一种改进的基于树自动机的) 。ls d l c i n a 验证算法，实现了x q u e r y 文档的有效性 验证。并对此算法进行了有效性分析。 第四章，x m l 文档的查询优化处理。首先通过本课题提出的一种有效的x m l 树模 式查询优化算法删除了) 。q u e r y 查询语法解析树中的冗余节点，使得查询的树模式得到了 简化。然后在此基础上结合基于视图的局部查询重写技术实现了订l 文档的查询优化。 第4 页 信息工程人学硕士学位论文 最后对这两种技术分别进行了实验及实例分析。 第五章，x m l 文档处理系统的设计及实现。根据上面所提到的技术对x m l 文档处 理系统进行总体设计并实现，并对系统进行测试及实验结果分析。 第六章，结束语。对全文进行总结，并提出进一步需要开展的工作。 第5 页 信息工程大学硕士学位论文 第二章相关概念及理论 本章对本文主要涉及的x m l 及自动机相关理论进行简单的介绍，同时对与本课题相 关的具体知识进行详细地分析。 2 1x m l 概述 由于x m l 的一系列特性，使得订l 的相关概念在使用时容易造成混淆和误解，为 了使本文能准确的阐述观点，下面对本文研究时常用的一些概念进行分析。首先明确了本 文研究的x l v i l 文档的基本数据模型；然后对x m l 的数据模式结构文件，如d t d 和讧l s c h c l i l a 进行分析，它们是本文将要研究的x q u c r y 文档有效性验证的基础；最后对几种 x m l 查询语言进行比较分析，并选出一种结构完备、发展成熟的x m l 查询语言x q u e r y ， 以它来作为本文查询处理及优化研究的基础。 2 1 1 u l 数据模型 x m l 是典型的层次结构，为了能让机器更好的理解x m l 数据，建立适当的数据模 型是非常重要的。w 3 c 定义了四种x m l 数据模型，分别是：i n f o s e t ( x m l 信息集) ，d o m ( 文档对象模型) ，x p a t h 和x q u e r y 数据模型。如何处理已有的这些模型间的关系，在这 些或简单或复杂的模型中找到平衡点以满足自己的需要是研究x m l 数据模型的重点。 ) 。l 文档本质上是一种半结构化数据，但与一般的半结构化数据相比，它又有自己的特 点i “0 5 1 。本课题参照w 3 c 的一系列规范，考虑x m l 自身的特点，采用d o m 模型作为 本文研究的基础数据模型。 定义2 1 ( x m l 数据模型) 用二元组t 来描述x m l 数据。其中，t - ，e = ( o i d i o i d s e ) ，s e 是树中节点的 集合，r j ( l p ( x ，y ) 八( x ，y e ) ) ，p ( x ，y ) 是谓词，表示存在一条从节点x 到节点y 的边。 节点的标签表示元素名称，如果p ( x ，y ) 存在，那么说x 是y 的父节点。 定义2 1 把x m l 文档映射成为树模型，每一个元素只能有一个标记，标记放在节点 中，但元素的属性也有类似于元素把属性名放在节点中，可设置一个标志位与元素进行区 分。按照d o m 规范，把) ( 】l 文档分解为棵包含文档中所有元素和属性的树结构，程 序就可以通过类d o m 定义的接口访问和更新讧l 文档的样式、结构和内容。图2 1 对 应的x m l 数据的d o m 模型如图2 2 所示。d o m 模型的优点是：标记定在节点上，可以 直接知道对象的含义，从父节点出发可以直接访问子节点。 第6 页 信息工程大学硕士学位论文 3 9 9 5 唧r i c c ，b o o k ( b o o ky e 弱= ”1 9 9 9 ” t h ee n o m i c so f 储m o i o g ya n dc o n t e l l t 南rd i g i t a l1 v 嘲i t l e 图2 1 x m l 文档 口元素。属性o t e x t 图2 2 x m l 文档树模型 与关系数据库不同，x l 订l 数据中所有的文本数据类型都是字符串型。而x m l 元素 只分为两种类型，即简单元素和复合元素。其中，简单元素是指只包含文本的元素，如图 第7 夏 信息工程大学硕士学位论文 2 2 中的“t i l l e ”，“l a s t ”，“f i r s t ”元素等，简单元素的值是指简单元素所包含的文本内容， 也就是“t i t l e ”，“l a s t ”所对应的值。而复合元素是指含有子元素的元素，如图2 2 中的 “c d i t o r ”，“b o o k ”元素等。 2 1 2x m l 数据模式 模式是关于标记的语法规贝| j ，它详细描述了x m l 文档的结构，从而确定了文档的框 架。一个模式文件严格地规定了以它为标准的所有x m l 文档的树状层次结构的全部细节。 当某一x m l 文档引用该模式文件时，它必须通过有效性检验1 2 6 1 。) 。v i l 文档的模式有 d t d 、x m ls c h e l l l a 、x d r ( x m ld a t ar e d u c e d ，简化x m l 数据) 和s o x ( s c h e l l l af 0 r o b i e c t o r i e l l t e dx m l ，面向对象) a l 语言的模式) 等。本节只讨论使用得最广泛的d t d 和x m l s c h 锄a 模式。 x m l 的一个重要特性就是其可扩展性，) 0 l 文档的作者可任意定义文档数据的结构 以及元素的名称和属性。虽然这种可扩展性给文档的制作提供了很大的灵活性，但同时它 也使得不同组织的应用程序问的数据交换变得难以实现，原因是不同组织的应用程序对同 样的标记名称可能有不同的理解1 2 6 】。另外，对于个将不断发展的文档模型，x m l s c h 啪a 或d t d 可指导此发展过程【2 ”。 1 d t d d t d 源于s g m l 规范，它描述了一个“l 文档的结构。一个d t d 通过指定一个元 素的属性以及子元素的名称来规定其结构。所有的值都是字符型的，可以用特殊属性i d 来唯一指定一个元素。下面给出了图2 1 中l 文档的d t d 描述如图2 3 所示。 图2 - 3 文档d t d d t d 中的声明分为四类，它们分别是：元素类型声明、属性列表声明、实体声明、 记号声明。d t d 指定了文档结构的一系列规定，并且将文件的结构和文件的内容完全分 开。通过定义d 1 巾可以控制在) a l 文档中可以使用哪些标记符号，应该按什么次序出 现，哪些标记符号有属性等。但d t d 只支持功能相对较弱的字符类型的定义和约束，一 第8 页 信息工程大学硕士学位论文 旦需要对更丰富的类型进行描述时就会遇到困难。 2 x m l s c h 啪a 在订ls c h e m a 出现以前，d t d 一直是订l 技术领域所使用的最广泛的模式。但 是，由于d t d 在订l 之前就已经出现，因而它不可避免地不能完全满足x m l 处理的要 求，例如不支持名字空间，缺乏对文档结构、属性、数据类型等约束的足够描述等。而 x m ls c h 锄a 弥补了d t d 的不足，它允许用户为文档中元素声明各种特定类型，并在使 用解析器检查文档结构是否有效的同时也对数据类型进行有效性验证，并能从文档中提取 实际数据信息传递给应用程序。“ls c h e m a 逐渐成为“l 的标准模式，并在很多应用 中取代了d t d 。 鉴于ls c h 锄a 已经成为目前较为成熟且类型描述能力较强的x m l 模式语言，本 文在第三章中对x q u e r y 文档的有效性验证中将讨论基于ls c h e m a 的类型验证问题。 例2 1 所示的就是一个x m l s c h e r n a 的实例，它将作为第三章中的应用实例。 例2 1 ：c u s t o m e r p a g e s 黜d ( c o m p l e x i y p en 蜘e = a d d r e s s 晰： s e q u e n 舻 e l e m e n tn 锄e s t r e e rt y p e = t x s ：s t r i n g 。 c o m p l e 】【1 圮n 栅e = p e f s o n l 独e c o m p l e x t 卯p 第9 页 信息工程大学硕士学位论文 砒o m p l c x 马，p c 刮c o m p l c x t 卯e e l e i i l e n tn 锄e = n o t e s t y p e = x s ：s t r i n 罟胗 2 1 3x m l 查询语言 随着越来越多的信息用x m l 存储、交换和表示，智能地查询x m l 数据源的能力变 得越来越重要。x m l 的一个很大的优点就是它在表示各种不同信息源的多种信息时的灵 活性。为了利用这种灵活性，一个l 查询语言应该提供检索和解释不同数据源信息的 特征。以下简单的介绍几种) ( 1 v i l 查询语言： 1 x m l 广o l 【5 】：a t & t 实验室的数据库研究人员设计的，通过加入明确的构造语句 c 0 n s t r u c t 扩展s q l ，使用元素模式匹配进行查询处理。x m l q l 能表达对多数据源 的l 查询和转换。 2 x p a m ：，a t h 是x m l 树中导航查询的基本机制【2 s 】，它支持丰富的路径查询特性。 非形式化地，我们给出x p a t i l 中常见的操作符号语义：“”表示数据节点间的父子关系； “”表示节点间的祖孙关系；“口”表示路径问的条件关系：“ ”表示) 。“l 元素的属性； 第l o 页 信息工程大学硕士学位论文 “”表示任意的数据元素，另外支持在路径表达式中定义逻辑表达式，包括“ l l = i ”。 3 x q u e r y ：x q u e r y 工作组于1 9 9 9 年9 月正式成立，其任务是创建一种灵活的查询 语言以便从l 文档中抽取数据。目前w 3 c 所公布的最新x q u e 巧草案是2 0 0 3 年1 1 月的版本，它还在不断的修订和完善之中。作为一种新型的查询语言，x q u e u 吸取了其 它多种查询语言的优点，适用于各种类型的) ( 1 讧l 数据源的查询，不仅查询功能强大，而 且简洁灵活且易于实现。同时，x q u e r y 还具有从多种数据库中检索信息的特点，它能对 各种数据和文档进行查询。x q u e r y 构建在a 血规范之上，其核心是能够通过，a l l l 表 达式从文档选择特殊的节点序列。x q u e r y 是一种将查询表示成表达式的功能语言。通过 它所支持的多种表达式，它的查询可以有各种不同的形式。x q u e r y 除了支持路径表达式 和f l w r 表达式之外，还有5 种基本的表达式模式：元素构造符、算子和函数表达式、 条件表达式、限定表达式、列表构造符、数据类型表达式。通过它们的多种组合，可以产 生具有丰富而强大的查询检索功能的查询语句。 在x m l 的查询研究中，除了以上介绍的三种x m l 查询语言外，还有许多其它的查 询语言，如订【广g l ，x s l ，x q l 等，但它们中绝大多数的查询语言都是基于正则路径 表达式。针对订l 查询出现的语言主要是通过正则路径表达式导航讧l 文档的查询， 来合成、抽取和分析文档内容。 一个正则路径表达式定义如下： r = ) ir ir + lr ? l ( r 1 i r 2 ) i 群in 锄e i 其中，r l ，r 2 表示从f l 到r 2 的路径，“i ”表示路径中的选择关系；“”表示路径中结 点的分隔符；“群”代表任意结点；“”表示结点的o 或多次重复；“+ ”代表结点的l 或 多次重复：“? ”表示结点的o 或1 次重复；“”代表空路径；“m m e ”表示结点标记，还 可用“口”来表示一个谓词表达式。 例如，在图2 1 中我们要查询所有作者的名字，这个查询就可以表示为： b o o k 博，a u 吐l o r n 锄e 。使用r p e 可以有效地表示有嵌套结构的查询，在用户对数据库的结 构不是十分了解时，使用r p e 进行查询能灵活的适应用户的查询需求。 对于) 蹦l 文档来说，它本质上讲就是一个以顺序和层次为主要结构单元的轮廓，而 x q r i l e r y 查询语言正是基于l 的这种结构的，它使用此结构来为同样范围内的x m l 存 储的数据提供查询能力。x q u r 查询的每一个输入都是数据模型的实例，查询的输出同 样也是数据模型的实例。在x c 獗巧数据模型中，每一个文档都被描述为一个带结点的树。 x q u e r y 是一种功能性的语言，与程序设计语言那样执行命令不同的是，每一个查询 都是一个待求值的表达式，并且表达式之间可以进行非常灵活的组合来创建一个新的表达 式。支持路径表达式是x q u e r y 最基本的特征，路径表达式的开头可指定文件中的特定节 点或包含其它子节点的父节点，再根据文件的结构配合x p 础的语法，找到符合路径的数 据。 第l l 页 信息工程大学硕士学位论文 通过以上对x q u e r y 查询语言的分析，可以看出它已是众多v 几查询语言中较为成 熟的语言，且它最基本的特征就是支持路径表达式。因此，本文对讧l 文档进行处理时 的查询语言将确定为x q u e r y 语言。 2 2 自动机理论 2 2 1 基本概念 定义2 2 伫9 】：一个确定的有限状态自动机d f a ( d e t e 咖j l l i s t i cf i l l i t ea u t o m a t o n ) 包括： ( 1 ) 一个有穷的状态集合，通常记作q 。 ( 2 ) 一个有穷的输入符号集合，通常记作。 ( 3 ) 一个转移函数，以一个状态和一个输入符号作为变量，返回一个状态。转移函 数通常记作6 。在非形式化表示自动机的图中，用状态之间的箭弧和箭弧上的标记来表示 5 。如果q 是一个状态，a 是一个输入符号，则6 ( q ，a ) 是这样的状态p ，使得从q 到p 有带 a 标记的箭弧。 ( 4 ) 一个初始状态，是o 中状态之一。 ( 5 ) 个终结状态或接受状态的集合f 。集合f 是q 的子集合。 通常用一个五元组来表示d f a ：a = ( q ，6 ，q 0 ，f ) 。其中，a 是d f a 的名称，q 是状 态集合，是输入符号集合，6 是状态转移函数：q 一q ，q 0 是自动机的初始状态，q 0 q ， f 为自动机的终结状态集合，f q 。 定义2 3 【2 9 1 ：一个非确定的有限状态自动机n l 认( n o n _ d e 钯r m i n i s t i cf i n i t e a u t o m 砒o n ) a = ( q ，邑6 ，q o ，f ) 包括： ( 1 ) 一个有穷的状态集合，通常记作q 。 ( 2 ) 一个有穷的输入符号集合，通常记作z 。 ( 3 ) 一个初始状态q o ，是q 中状态之一。 ( 4 ) 一个终结状态或接受状态的集合f 。集合f 是q 的子集合。 ( 5 ) 一个转移函数6 是一个以q 中一个状态和中一个输入符号作为变量并返回q 的一个子集合的函数。注意，n f ：a 与d f a 之间的惟一区别在于6 返回值的类型：在n f a 的情况下，返回值是一个状态集合；而在d f a 的情况下，返回值是单个状态。 定义2 4 跚：带转移的非确定有限状态自动机- n f a 完全可以像表示n f a 那样来 表示，只有一处例外：转移函数必须含有在空串8 上转移的信息。形式化地，把姗aa 表示成a 气q ，z ，6 ，q 0 ，f ) ，其中除6 外，所有组成部分都有与n f a 同样的解释，6 现在是有 下列变量的函数： ( 1 ) q 中一个状态。 ( 2 ) uf 中一个元素，也就是说，要么是输入符号，要么是符号。要求空串符 号不是字母表中的元素，所以不会导致混乱。 第1 2 页 信息工程大学硕士学位论文 定义2 5 【2 9 】：设为一字母表，上的正则表达式e 所描述的语言记做e ) ，则正则 表达式及其所代表的语言递归定义如下： 基础：基础包括三个部分： ( 1 ) 常量和o 是正则表达式，分别表示语言 和空集o ，也就是说：工( 6 户 8 且 三) = 2 0 ； ( 2 ) 若a 是任意符号，a ，则a 是正则表达式，它表示语言 a ，也就是说，以垆 a ) ； ( 3 ) 变量，如三。它代表任意语言。 归纳：归纳有四个部分，三种运算符各自对应一个部分，括号的引入对应一个部分。 ( 1 ) 如果e 和f 都是正则表达式，则e + f 是正则表达式，表示三回和( f ) 的并。 也就是说工( 酎d = 【( e ) u 三( f ) 。 ( 2 ) 如果e 和f 都是正则表达式，则e f 是正则表达式，表示l ( e ) 和以f ) 的连接。 也就是说，砸f ) ：屯( e ) 砸) 。注意，可以任意地用点来表示连接运算符，既作为语言上的 运算，也作为正则表达式上的运算符。 ( 3 ) 如果e