（计算机软件与理论专业论文）压缩xml数据库查询处理方法的研究.pdf

中文摘要 中文摘要 近几年来，x m l 已经成为i n t e r n e t 上数据表示、交换和存储方面的标准，为 数据库的应用开辟了一个崭新的领域，然而由于x m l 数据的半结构化特性以及 x m l 数据所特有的路径表达式查询方式的特殊性，限制了使用关系数据库系统对 x m l 数据的管理功能，也正是由于x m l 的这些特点及冗余性特点，使得不但增加 了查询处理的i o 时间，同时也造成了一定的存储空间的浪费，从而降低了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 压缩查询模型的原型系统，其中的压缩 模块用的就是本文提出的) ( m l 压缩技术，并与其他压缩方法进行如压缩率、压缩 时间和查询处理时间等方面的对比实验，分析了实验结果，并发现本文提出的两 种) ( m l 压缩方法平衡了压缩率和查询处理时间两个方面，并能有效地支持压缩后 的直接查询处理，压缩效果有一定的提高。 关键词：文本压缩；x m l 压缩：x m l 编码：x m l 索引；x m l 查询 黑龙江大学硕士学位论文 a b s t r a c t r e c e n t l y x m lh a sa l r e a d yb e e nt h es t a n d a r do fd a t ae x p r e s s ，e x c h a n g ea n d s t o r a g e ，i tb r i n g san e wd o m a i no fd a t a b a s ed e v e l o p m e n t ，b u tb e c a u s eo fi t sh a l f s t m c t u r a lc h a r a c t e r i s t i ca n dt h es p e c i a jp a t he x p r e s s i o nq u e r ) ，w a yo fm ex m l d a t a ， w h i c hi ss od i 脏r e n tf 硒mt h er e l a t i o n a ld a t a b a s eq u e 吼t h e nr e s t r i c tx m l u s et h e d b m s d e e p l y ：b e c a u s eo ft h a t ，w eh a v et of ! l c et h eb i g g e s tf a u l to f ) 叫l ，、v i l i c hi si t s d a t ar e d u n d a u l c e ，i ti sr e d u n d a n ti nt w o2 l s p e c t s ：s 劬c t u m lr e d u n d a n c ya n dc o m e n t r e d l l i l d a n c y ，t l l a ti s i ti sr e p e a t e db o t hi np a t ha n de l e m e n t r e d u d e n c yn o t 0 1 1 l y e n h a n c et l l eq u e r yp r o c e s s i n gi ot i m e ，b u ta l s oaw a s t eo ft h es t o r a g e s p a c e ，a n di n 此 e n d ，i td e b a s et h ee 伍c i e n c yo fx m l ，、v h i c hl e a dt h ec o m p r e s s i o no fx m lan e c e s s a 巧 w o r k b u tt h e q u e 叫p r o c e s s i n ga n do t h e ro p e m t i o ns h o u l db ed o n ea j f t e rt 1 1 e d e c o m p r e s s i o no fx i ld o c 啪e n t ，w h i c hi sa l s oaw a s t e ，s oh o wt oq u e d ，e 币c i e n t l yi n c o m p r e s s e dx m l d o c u m e n ti sb e c o m i n gt h em o s ti m p o r t a n ti s s u eo fx m l s t u d y ，a n d m e c o m p r e s s o r 、v l l i c hs u p p o nt h ed i r e c t l yq u e 叮o nt h ec o m p r e s s e dd a t ai sb e c o m i n g m o r ea n dm o r ei m p o n ：叽t ，i tn o to n l yc a ns a v et h em e m o 巧u s a g es p a c e ，b u ta l s oc a i l a c c e l e r a t em eq u e 巧p r o c e s s i n gt i m e ，a n da tt h es 锄et i m eg e tab e n e rc o m p r e s s i o n r ：l t e t h ep a p e re l i m i n a t e sr e d u n d a n ti n f o 肌a t i o no fx m li ns t n l c t u r ea n dc o n t e n t a s p e c t s ，锄da c c o r d i n gt ot h ed r a w r b a c k so ft h ex m lc o m p r e s s o rw h i c ha r ea l r e a d y k n o w n ，t h et h e s i sp r o p o s e dt 、v ox m lc o m p r e s sa l g o r i t h r n sw h i c hs u p p o nt h ed i r e c t l y q u e 巧p r o c e s s i n gt h ec o m p r e s s e dx m ld o c u m e n t s ，f i n a l l y ，t h ep a p e rg i v e sa ne m c i e n t x m l c o m p r e s s i o nm o d e lw h i c hi ss o l v et h ep r o b l e m sw h i c ha r em e n t i o n e db e f o r e ， c o m p a r e sw i t ho t h e rm e t h o d sa n dm a k e sm a n ya n a l y s i s ，w h i c hs h o we 币c i e n ti ns o m e d o m a i n a tl a s t ，a c c o r d i n gt ot h eq u e d ，p r o c e s s i n gx m lc o m p r e s s i o nm o d e l ，t h et h e s i s a b s t r a c t i m p l e m e n t sax m lc o m p r e s s i o na n dq u e r ) rp r o t o t y p es y s t e ma n dc o m p a r et h e c o m p r e s s i o nt i m e ，c o m p r e s s i o nr a t ea n dq u e 叫p r o c e s s i n gt i m e ，a n dt h e na n a l y s e st h e r e s u l tw h i c hi ss h o w e dt h a tm yx m lc o m p r e s s i o nm e t h o d sa r eb o t hb a l a n c et h e c o m p r e s s i o nr a t ea j l dq u e 巧t i m e ，a n da tt h es a m et i m e ，t h e yb o t hs u p p o i r tt h eq u e r y d i r e c t l ya r e rt h ec o m p r e s s i o n ，a n d 、v ee n h a n c et h ec o m p r e s s i o ne 骶c tt os o m ee x t e n t k e yw o r d s ：t e x tc o m p r e s s i o n ，x m lc o m p r e s s i o n ，x m lq u e 阱x m li n d e x 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得墨蕉堑丕堂或其他教育机构的 学位或证书而使用过的材料。 学位论文作者签名： 1 、 耋俦 签字日期：年月 日 学位论文版权使用授权书 本人完全了解墨蕴堑太堂有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权墨蕉适太堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或其他复制手段保存、汇编本学位论文。 学位论文作者躲莲佝新虢施冲 签字日期： 年月日签字日期：年月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 第1 章绪论 第1 章绪论 2 0 世纪8 0 年代早期，i b m 提出了在各文档之间共享一些相似属性，并且设计 了一种新的文档系统，通过在该文档中添加一定的标记，来表示该文档中的各种 元素，i b m 把这种标记语言称做通用标记语言( g e n e r a l i z e dm a r k u pl a n g u a g e ， g m l ) 。经过若干年的发展，1 9 8 4 年国际标准化组织( i s 0 ) 开始对此提案进行讨论， 并于1 9 8 6 年正式发布了为生成标准化文档而定义的标记语言标准( 1 s 0 8 8 7 9 ) ，成 为新的语言标准通用标记语言( s t a n d a r dg e n e r a l i z e dm a k e u pl a n g u a g e ，s g m l ) 。 它的功能非常强大，是可以定义标记语言的元语言，然而由于s g m l 过于复杂和庞 大，使得它并不适合在w e b 上应用，这就使得万维网联盟( w o r l dw i d ew e b c o n s o r t i u m ，w 3 c ) 在1 9 9 6 年开始发展一种新的标准标记语言，以便能将s g m l 的 丰富功能与h t m l 的易用性结合到w e b 应用中。1 9 9 8 年2 月，w 3 c 发布了x m l l o 标准，其目的是为了在w e b 上以现有的h t m l 的使用方式提供，接收和处理通用的 s g m l ，它比s g m l 更易于使用，比h t m l 的结构更严格。x m l 由x m l 工作组( 原先的 s g m l 编辑审查委员会) 开发，此工作组由w 3 c 在1 9 9 6 年主持成立。x m l 工作组由 s u nm ic r o s y s t e m s 的j o nb o s a k 负责，同样由w 3 c 组织的) ( m ls i g ( s p e c i a l i n t e r e s tg r o u p ) ( 原先的s g m l 工作组) 积极参与了x m l 工作组的工作。 ) 【m l 旧1 ( e x t e n s i b l em a r k u pl a n g u a g e ) 是一种可扩展的标记语言，是标准通用 标记语言 i s o8 8 7 9 s g m l 的针对特定应用领域的一个子集，或者说是s g m l 的一 种受限形式，它描述了一类称为x m l 文件的数据对象，同时也部分地描述了处理 这些数据对象的计算机程序的动作。x m l 提供了一种用于约束存储格式和逻辑结 构的机制。简单地说，x m l 文档应有一个根元素，所有开始标志要有响应的结束 标志，所有属性值要放到引号中，文档中只能使用x m l 中合法的u n i c o d e 字符。 每个x m l 文档都由一个逻辑结构和一个物理结构组成。 物理上而言，文档由称为实体的存储单元组成，实体都是具有内容并且都通 过实体的名字进行标识( 文档实体和外部d t d 子集除外) 。x m l 文档可以划分成若 黑龙江大学硕士学位论文 干的文本片，把这些文本片叫做实体，通过在文件中插入实体引用来使用实体。 实体又分为两种：一种是内部实体，是在文件内部定义的；另一种是外部实体， 它是在文档外部定义，存放在另外一个文件或存储在数据库中。通过使用外部实 体，可以将一个大型的x m l 文档分解为多个文件，便于处理。 逻辑上而言，文档由声明，元素，注释，字符引用和处理指令组成，在文档 中，所有这些都是通过显示的标记来指明的。x m l 标记包括开始标签，结束标签， 空元素标签，试题引用，字符引用，注释，c d a t a 段定界符，文档类型声明，处 理指令，) ( m l 声明，文本声明及任何在文档实体项层的空白。) ( m l 文档是一棵树， 有一个根结点，包含不同的子结点，其中有写子结点自己又有子结点，而有些则 是也结点，没有子结点。 1 1x m l 基础 研究者通常将x m l 文档表示成一颗x m l 树，在x m l 树中一般可以分为5 种不 同的结点，它们分别是： ( 1 ) 根结点，也称为文档结点，是一个抽象结点，包含整个x m l 文档，其子 结点包括说明语句，处理指令和文档的根元素。 ( 2 ) 元素，具有名称，一组属性，一组范围名字空间和一系列子结点。 ( 3 ) 文本结点，两个标志之间的分析字符数据。 ( 4 ) 注释结点，即说明注释语句，格式为 ，其内容 是内部的数据，没有任何子结点。 ( 5 ) 处理指令p i 结点，它的格式类似 样式的处理指令，它具有一定的目标和值，没有任何子结点。 而x m l 文档的基本单位是元素( e le m e n t ) ，每个x m l 文档至少有一个元素，即 x m l 文档至少有一个根元素，没有元素就无法写出x m l 文档，逻辑上而言，每个 元素由三个关键字段组成，它们分别是：标记名称( t a gn a l t l e ) 、元素属性 ( a t t r i b u t e ) 和元素内容( c o n t e n t ) 。简单地说，标记意味着对元数据的表达方法。 所有的标记语言都使用标记来为元数据限定主要的组件界限，称之为元素。元素 第1 章绪论 可以具有描述属性，属性描述与元素相关的信息，是与元素想关联的名称数值对， 可以是任何合法x m l 名称，其值可以是任何文本字符串，称之为元素属性。x m l 数据的图模型把x m l 数据表示成节点加标记的有向树。树的内节点表示x m l 的元 素所对应的内容，且标记为该元素。树的叶节点表示x m l 数据值，树的边表示元 素的嵌套关系，即“元素与子元素”或“元素与值”的关系。数据描述了文档的 自身结构，它没有单独的模式或辅助性的描述。 详细地说，x m l 文档的主要内容有以下三个方面： ( 1 ) 元素与属性：表示x m l 的逻辑结构，) ( m l 文档是由很多称作元素的组件构 成的，表示具体内容的文本称为文档的字符数据。x m l 元素用来描述文档的逻辑 结构。其中，包含所有元素的元素称为根元素，它是没有前导元素的唯一元素。 根元素直接包含的元素称为子元素，它们也可以包含自己的子元素。元素还可以 包含相关信息，这些信息称为属性，属性是用来描述元素特征的。 ( 2 ) 实体：表示x m l 的物理结构，又叫做“文本片”，x m l 提供了一种可以使文 本线性地组织的机制。x m l 元素是描述文档的逻辑结构，而实体则是描述组成x m l 文档的字节块的位置，即描述文档的物理结构。在文档中，可以通过插入实体引 用来使用实体，) 【m l 处理器将会用实体替换相应的实体引用，这一过程称为文本 替换。格式良好的) 【m l 文档形成了一种层次树结构。实体可以包含己解析的或未 解析的数据。在x m l 处理器分析x m l 文档时，凡是文档中出现引用以分析实体的 地方，都将被该试题的内容所替换。每一个未解析的实体有一个相关联的用名字 标识的记号。已解析的实体以实体引用的方式通过名字来调用；未解析的实体通 过e n t i t y 或e n t i t l e s 属性中给出的名字来调用。 ( 3 ) 标记：用来描述文档的逻辑结构、连接物理实体的记号称为标记。x m l 文 档就是由标记和字符数据构成的。两者都使用u n i c o d e ，都称为x m l 文本，即字 符数据+ 标记= x m l 文本。标记使用一种特殊的字符与其他区别开来，这种字符称 为分隔符。举例说明x m l 文档和文档树( 如图卜1 所示) 。 黑龙江大学硕士学位论文 e 习 图1 1x 胤文档和文档树 f i g 1 11 1 1 ex m l d o c u m e n ta n dd o c u m e n tt r e e 在x m l 文档树中，如果一个元素不再包含其它子元素，称它为叶元素或叶节 点，如果能够从根元素出发达到这个元素，称这个元素为分支元素或分支节点。 例如，g r o u p x m l 文件中m e m b e r 的是分支，而n a m e 元素和a g e 是叶。除了子元 素以外，元素还可以用属性来描述附加信息。属性用来描述元素的特征，记录元 素特有的信息用以与其它同名元素进行区别。g r o u p x m l 文件中的p r o j e c t 元素 就拥有一个属性 p n o ，用来记录该项目的编号。通常元素前面添加符号 ，用来区 别) ( m l 文件树中的元素和属性。 总的来说，x m l 旧1 是一种更简单，更轻便的标记语言，它很灵活，易于使用， 并可用于国际化文件。正是由于x m l 的如上特征，使得其适宜用做数据存储、数 据转发以及消息发送等各种用途。 1 2x m l 相关技术 ) ( m l 以一种开放的，自我描述的方式定义了数据结构，是一种专门在w e b 上 传递信息的语言，已经变成了数据存储和交换的标准，特别是在网络上。在描述 数据内容的同时能突出对结构的描述，从而体现出数据与数据之间的关系。w 3 c 工作组是这样描述) ( i i l 语言的：“扩展标记语言x m l 是标准标记语言s g m l 的子集， 第1 章绪论 其目标是允许普通的s g m l 在w e b 上以目前h t m l 的方式被服务，接收和处理。x m l 被设计成易于实现，且可在s g m l 和h t m l 之间互相操作”。 w 3 c 中描述的x m l 目标主要有如下几点：x m l 在因特网上可直接使用；x m l 应 该支持广泛的，多样化的应用程序；x m l 兼容s g m l ；容易编写处理x m l 文件的程 序；x m l 中可选特性的树木必须保持绝对最小化，最好为o ；x m l 文件应该清晰易 读；x m l 的设计应迅速完成；x m l 文件容易创建；保持x m l 标记的简洁性的重要性 仅次于保持简练的x m l 标准。这些目标都是为了使x m l 成为创建w e b 应用程序的 理想媒体。一个格式良好( w e l l 一f o r m e d ) 的) 【m l 文档是指该) ( m l 文档有且仅有一个 根元素，符合x m l 元素的嵌套规则，满足x m l 规范中定义的所有格式正确性的约 束，并且在文档中直接或间接引用的每一个已分析实体都是格式正确的x m l 文档。 其重要性表现在：可以创建没有d t d 的x m l 文档，便于利用x m l 文档做数据的交 换；x m l 的处理器可以做得很小很快。一个遵守x m l 语法规则，并遵守相应d t d 文件约束的x m l 文档称为有效的x m l 文档，将x m l 文档和它的d t d 文件进行比较 分析，看是否符合d t d 规则的过程叫验证( v a l i d a t i o n ) 。 x m l 格式的优势主要体现在它仅是一种数据格式，而这种数据格式比其它文 本数据格式等有重要的优势是它可以更有效地存储信息而同时表示一定的数据结 构特征等方面。) ( m l 允许开发者建立他们的属于自己的保存信息的标记结构，但 ) ( m l 文件比他们取代的二进制格式的更复杂。他们需要更多网络带宽和存储空间， 需要更多的处理器时间。x m l 解析语法是非常明确，而且是一种广泛应用的工具。 x m l 的重要优势使得其已经成为w e b 上数据存储和交换的标准，并且有越来越多 的应用使用x m l 格式，x m l 文档的应用好处主要是基于x m l 自身的四个优点的， 它们分别是： ( 1 ) x m l 具有良好的可扩展性，使得其应用十分广泛； ( 2 ) x m l 文档内容是自描述性：) ( m l 是面向内容的标记语言，在x m l 中的标记 一方面限定了元素的层次结构，另一方面也说明了元素的含义。在x m l 的搜寻结 果中由标记就可知道内容的含义，这也使得搜寻结果更有意义； ( 3 ) x m l 的数据内容和形式的分离表示：) 【m l 不仅允许自定义一套标记，而且 s 黑龙江大学硕士学位论文 这些标记不必局限于显示格式的描述。x m l 允许根据各种不同的规则来制定标记， 比如商业规则，根据数据描述甚至根据数据关系来制定标记。x m l 是自描述语言， 在x m l 中显示样式从数据文档中分离出来放在样式单文件中； ( 4 ) x m l 具有严格的语法要求：虽然严格的语法要求表面上显得繁琐，但具 有良好语法结构的文档可提供良好的可读性和可维护性，长远来看大有裨益。 具体而言，x m l 的优点使得其日益地称为数据表示何交换的事实标准，这些 特点分别是： ( 1 ) x m l 的结构化，增强后的结构使你可以创建标准化的有效的x m l 文件； ( 2 ) x m l 能够成为数据的容器，使用d t d ，可以有效地表现几乎所有的数据； ( 3 ) x m l 提供了灵活性且容易使用，它只比h t m l 轻微复杂一些，随着越来越 多的浏览器支持x m l 以及支持x m l 的工具的出现，其应用也会越来越广泛； ( 4 ) x m l 有标准的格式且是国际化的标准。正是由于x m l 上述的这些优势， 使得x m l 能够满足越来越复杂的企业需求，其应用也就越来越广泛和普遍了。以 下分别介绍了x m l 中常用的相关技术：( 1 ) x m l 查询语言，主要有x p a th 【l 订和 x q u e r y 哺引；( 2 ) x m l 的文档类型定义语言d t d ，它们使得x m l 的应用更加广泛了。 1 2 1x m l 查询语言 目前，当前的x m l 查询语言基本可以分为两类：( 1 ) 数据库领域：如l o r e ， x m l q l 、q u i l t 、x m l g l ；( 2 ) 文档领域：如x s l 、x q l 、x q u e r y 畸1 、x p a t h 1 等。 本文主要介绍两种x m l 查询语言是x p a t h 和x q u e r y ，w 3 c 的规范中对x p a t h 的描述 如下：“x p a t h 的主要目的是对一个x m l 文档进行寻址，提供了操纵字符串和数值 等的基本功能。x p a t h 在x m l 文档的一个抽象逻辑结构上进行操作，而不是在它 的表面语法上”。w 3 c 的规范中对x q u e r y 的描述如下：“被设计成能够在多种) ( i l 数据源中广泛应用的，被定义为对) 【m l 数据集进行查询的查询语言 。x q u e r y 是 一个从) ( m l 格式的数据源中获取数据的查询语言，起源于x m l 数据查询语言 q u i l t ，并将x p a t h2 0 作为其子集。所有这些查询语言共同点是都使用了基于正 则路径表达式r p e 来查询) ( m l 结构和数据，针对r p e 的查询处理技术是近年来x m l 第1 章绪论 研究的一个热点。下面将对文档领域的两种查询语言x p a t h 和x q u e r y m l 分别予 以介绍。 1 2 1 1x p a t h x p a t h 1 是x m lp a t hl a n g u a g e 的缩写，是一个独立的技术规范，定义了x m l 文档中的特定条目该如何定位，是一种对x m l 文档的内容进行定位、检索的语言。 在x p a t h 技术规范中，一个x m l 文档被认为是一个结点树，树中的每个节点都可 以通过详细描述该结点在树中的位置而进行相应的存取操作。在这里，结点指的 是任何) ( m l 数据段，包括元素属性或文本数据。x p a t h 的目的是在匹配x m l 文件 结构树时，能够准确地找到某个结点元素，使之能够完成x q u e r y 的基本功能。 x p a t h 将x m l 看作是一个树模型，压缩主要考虑其中包括三种不同的结点类型， 它们分别是：元素节点( e l e m e n t ) 、属性节点( a t t r i b u t e ) 和文本节点( t e x t ) ，以 下介绍了在压缩过程中需要压缩的结点的具体内容。 ( 1 ) 根节点。它是一棵树的开始，也是唯一的。树中的其它所有元素节点都 是它的子节点或后代节点。在x p a t h 中对树的匹配总是从根节点开始。 ( 2 ) 元素节点。它对应于文档中的每一个元素，可以为元素节点定义一个唯 一的标识i d ，可使用树的前序、后序以及层次遍历等为元素节点定义标识。 ( 3 ) 文本节点。文本节点包含了一组字符数据，即c d a t a 中包含的字符，文 本节点没有扩展名，用来存储数据信息。 ( 4 ) 属性节点。每个元素节点由一个相关联的属性节点集合，元素是每个属 性节点的父节点，但属性节点却不是其父元素的子节点，也就是说通过元素可以 查到属性节点，而反之不成立，原因在于x p a t h 规定元素的属性节点是单向的。 x p a t h 是针对x m l 文档部分内容定义的语法，是一种能在x m l 文档中查找定 位信息的语言，它能从x m l 文件中抽取单个项目或一组项目。通过x p a t h 路径表 达式，可以在x m l 层次结构中快速定位和提取信息，确定节点。x p a t h 因使用路 径标记在x m l 文档的层次结构中进行导航而得名，其工作方式和语法与操作系统 中用于文件定位的路径以及w e b 中的资源定位u r l 有些类似，就像我们熟知的 c ：w in d o w s 那样，但x p a t h 比后二者要复杂得多。类似于计算机系统中的文件路 7 黑龙江大学硕士学位论文 径，可以把x p a t h 比作文件管理路径：通过文件管理路径，能够按照一定的规则 查找到所需要的文件；并且，依据x p a t h 的制定规则，也可以很方便地找到x m l 结构文档树中的任何一个节点。x p a l h 最重要的语法构造为表达式，而其中最主 要的为路径表达式。 x p a t h 查询主要有四种类型：绝对路径查询或相对路径查询、简单路径查询或 复杂路径查询、正则路径表达式查询、多分支路径查询。其中，多分支路径查询 匹配多个正则路径表达式，多分支路径由一个根元素连接，查询语句表现出一个 树状结构，通常用t w i g 小枝查询表示。x m l 查询方法的选择是x m l 查询效率 高低的重要影响因素，高效的查询方法和索引结构将为x m l 查询系统带来最佳的 性能发挥。其中，元素之间的结构关系主要包括以下几种：祖先后代 ( a n c e s t o r d e s c e n d a n t ) 关系、父亲一孩子( p a r e n t c h 订d ) 关系、前一后 ( p r e c e d i n g f 0 11 0 w i n g ) 关系、左兄弟一右兄弟( p r e c e d i n g s i b li n g f 0 11 0 w i n g s i b l i n g ) 关系等。x p a t h 语法遵循的五个路径匹配规则如下： ( 1 ) 路径匹配：意义与文件路径类似，主要的几种路径操作，如表卜1 所示： 表1 1 路径匹配操作表 t a b 1 1p a t hm a t c ht a b l e 符号关系或表示查询举例 父亲一孩子a b c ：表示结点a 的子结点为b ，且c 为b 的子结点 | 祖先一后代d ：表示所有在x m l 文档中出现的d 元素 木 通配符 a b ：i c ：表示a 元素一 b 元素下的所有子元素 ( 2 ) 属性及属性值。在x p a t h 中，可以利用属性及属性值来匹配元素，要注 意的是元素的属性名前要有“ ”前缀。例如，“a i d ”表示所有具有属性i d 的a 元素。再如“a i d = ”m ” ”表示i d 值为“m ”的a 元素。 ( 3 ) 位置匹配，对于每个元素，它的各个子元素都是有序的，主要有以下几种 位置表示，如表卜2 所示： 第1 章绪论 表1 - 2 位置匹配操作表 t a b 1 2 p o s i t i o nm a t c ht a b l e 位置表示意义举例 数字i第i 子元素a b 2 ：表示a 一 b 元素第2 子元素 f ir s t l a s t第一最后子元素 a b 】a s t ：表示a 元素一 b 元素的最后一个子元素 p o s i t i o n ( )返回元素位置号a b p o s i t i o n ( ) 1 ：表示a 元素一 b 元素之下所有位 置号大于1 的子元素 ( 4 ) 亲属关系匹配。x m l 文件是树型结构，任何一个节点都不是孤立的，它 们之间具有亲属关系，如父子关系、祖先一后代关系、兄弟关系等。在对元素进 行匹配时，可以利用上述关系进行匹配。 ( 5 ) 条件匹配。条件匹配就是利用一些函数的运算结果的布尔值来匹配符合 条件的节点。这些函数通常包括节点函数、字符串函数、数值函数等。 1 2 1 2x q u e r y x q u e r y 哺即是w 3 cx m l 查询工作组提出的，该查询语言借鉴了结构化、半结构 化数据查询语言的许多特性，它是一种将查询表示成表达式的功能语言，通过它 所支持的多种表达式，它的查询可以有各种不同的形式，并且充分的考虑了对不 同类型数据源( 包括传统的数据库系统及文档系统等) 的访问能力以及在小型化、 易实现以及可读性等方面的要求。x m l q u e r y 工作组建立x q u e r y 的目的是提供一 种可以从w e b 上的真实和虚拟的文档中数据的灵活的查询工具，从而最终提供w e b 领数据库领域之间的接口。由于x q u e r y 还处于发展阶段，目前仅有很少的支持 x q u e r y 的商业产品出现。x q u e r y 融合了其它多种查询语言的优点，并且它是构建 在x p a t h 规范之上，换句话说，x p a t h 是x q u e r y 的核心部分，即是能够通过x p a t h 表达式从文档选择特殊的节点序列。x q u e r y 是由一些叫做查询模块的单元组成 的，各模块单元是彼此独立的，我们称其为表达式，用关键字、符号和操作符将 表达式组合成更复杂的表达式，各种x q u e r y 表达式可以完全嵌套，也支持子查询。 x q u e r y 表达式主要由以下8 种基本模式构成： 黑龙江大学硕士学位论文 ( 1 ) 路径表达式( p a t he x p r e s s i o n s ) ； ( 2 ) 元素构造符( e 1e m e n tc o n s t r u c t o r s ) ； ( 3 ) f l w r 表达式( f l w re x p r e s s io n s ) ； ( 4 ) 算子和函数表达式( e x p r e s s i o n si n v o l v i n go p e r a t o r sa n df u n c t i o n s ) ； ( 5 ) 条件表达式( c o n d it i o n a le x p r e s s jo n s ) ； ( 6 ) 限定表达式( q u a n t i f i e de x p r e s s i o n s ) ； ( 7 ) 列表构造符( l i s tc o n s t r u c t o r s ) ； ( 8 ) 数据类型表达式( e x p r e s s i o nt h a tt e s to rm o d i f yd a t a t y p e s ) 。 其中，f l w r 表达式是具有最强大特性的，它是一种典型的能够完成具有某种 实际意义的查询的表达式。f l w r 表达式是f o r l e t w h e r e r e t u r n 四个关键 字定义的子句的简写，可以绑定变量，并用这些变量帮助构造查询结果，包括模 式匹配、过滤选择和结果构造这三种操作，是x q u e r y 所具有的最接近于s q l 的 语句，以实例说明如下。 f o r $ ii nd o c u m e n t ( ”b i b x m l ”) b i b v e n d o r b o o k w h e r e $ i p r ic e 8 0 r e t u r n $ i t it l e ，$ i p r i c e ) 其语义为：在名为b i b x m l 的x m l 文档中从根节点开始，选择所有b i b 元素 的v e n d o r 子元素，然后选择所有v e n d o r 的b o o k 子元素，并且要求最终选择的 b o o k 元素须满足条件：它的价格p r i c e 需大于8 0 ，最终输出每一个满足条件的 b o o k 元素的t i t l e 和p r i c e 。该查询中，$ i 为绑定的变量，用以帮助构造查询结 果。这一查询返回的结果形式为： j a v a 9 9 h i g h p r j c e d b o o k ) 1 2 2 文档类型定义d t d 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 是由标记声明、参数实体引用及开始和结束标记构成。d t d 第1 罩绪论 的标记声明包括元素类型声明、元素属性声明、实体声明和注释声明等。元素类 型声明由e l e m e n t 关键词、元素名称及其包含的内容构成。元素的内容可以是文 本、子元素或为空。d t d 的主要内容包括以下几部分： ( 1 ) 元素声明。要用d t d 进行检验，就要在e l e m e n t 声明中声明文档使用的 每个元素，其格式形如 ，声明可以带子元素的元素时， 按顺序列出子元素名，并用逗号分隔，例如 ， 元素可以包含的项目清单防在括号中，成为元素的内容模型，可在元素名后增加 表卜3 所示的符号标记。最后，可以把整个内容模型换成关键字e m p t y ，指定这 个元素根本不包含任何内容。 ( 2 ) 属性声明。d t d 还可以指定每个元素可以，并且应该包含什么属性，属 性声明使用a t t l i s t 声明，其中指定以下内容：属性所属元素：属性名；属性类 型；属性默认值；例如 。 ( 3 ) 文档类型声明。文档通过文档类型声明与特定d t d 相联系。例如在m y x m l 中有 ，d t d 不仅用于检验，还可能影响实例 文档本身的内容，例如d t d 可以定义实体，符号以及提供默认属性值等。 表1 3x m l d t d 符号意义表 t a b 1 - 31 1 1 ed t dm e 锄i n gt a b l e 符号意义 u iv ：表示在两个元素u 和v 中任意选择一个 7 u ? ：表示该元素是可选择的，即可在该位置出现该元素的o 个或一个u ，l ： u 木：表示可以在这个位置出现该元素的0 个或多个u ，不出现或出现多次 + u + ：表示必须在这个位置出现该元素的一个或多个u ，至少出现一次 d t d 的主要作用是声明x m l 文件中出现的标记及其顺序等，用它来定义) ( m l 文件的逻辑结构，x m l 处理器可以在运行时用d t d 来对一个x m l 作合法性验证。 一个支持有效性验证的x m l 解析器和d t d 结合能确保所有必要的元素和属性在文 档中出现，并且文档中没有未经授权的元素和属性，确保了数据在被移交给应用 黑龙江大学硕士学位论文 程序之前就具有有效的结构。但是d t d 并不是x m l 文档存在的必要条件，也就是 说x m l 文档可以有d t d 定义也可以没有d t d 定义，d t d 有其自己的语法来声明x m l 文件中的元素类型和属性等，例如，d t d 与树型表示( 如图1 2 所示) 。 i d o c t y p e2 r o up i l e l e m e n tp r l e c t ( 叭i e m e m b e r p l e l e m e n tn a m e ( 抖p c d a t a p 回曰曰 图1 2d t d 及其树型表示图 f 1 9 1 2 l h ed + l da n dl t st r e ep i c t u r e 例如图卜2 左边的g r o u p d t d ，根元素类型g r o u p 包含一个或多个子元素类型 p r o j e c t ，而p r o j e c t 可以没有或有多个子元素类型m e m b e r ，将元素类型t i t l e 、 n 硼e 等定义为# p c d a t a ，是指它们可以包含文本元素，但不能包含标记。d t d 的 另一个重要组成部分是属性声明。一个元素可以不包含属性，也可以包含多个属 性。属性声明使用关键词a t t l i s t ，由三个部分组成：属性名称、属性类型和属 性特点。其中，属性名称表示属性的名字；属性类型表明该属性的类型，如c d a t a 表明该属性只能包含字符数据；属性特点表明属性的其它一些性质，例如 # r e q u i r e d 表明该元素的所有实例必须有该属性的值；# i m p l l e d 表明若该元素的 实例中没有指定该元素值，则忽略该属性；# f i x e d 表示属性的值是固定的某一个 值；d e f a u l t v a l u e 表明标记中如果没有指定该属性的值，那么此字符串就是此属 性的值。如图卜2 中，p r o j e c t 有一个属性，名称是p n o ，类型是# p c d a t a ，# r e q u i r e d 表示p n o 是不能被忽略的。 第l 章绪论 1 2 3x m l 主要应用 x m l 是跨平台的数据，是当前最被看好的信息交换格式之一。由于x m l 具有 以字符为基础，以标签为信息元素划分的半结构化的特点，天生就具有非常强的 可挖掘性与可移植性，这使得x m l 已经广泛的应用在资料存储、信息交换、资源 配置等各个方面，使得x m l 已经成为i n t e r n e t 以及电子商务中数据交换和表示 事实上的标准。但由于x m l 本身是基于文本方式的半结构化数据的表现形式，又 有着冗余性这一致命缺点，如何对半结构化数据x m l 进行有效的管理，包括存储、 索引、查询等，是一个有待解决的问题。x m l 数据的一个明显特征是其数据冗余 较大，无论采用那种模式来存储x m l 数据，都必须面对x m l 数据冗余较大这一 特点。冗余既造成了存储空间的浪费，又增加了查询处理的i o 时间，从而降低 了效率。但总的来说，x m l 还是有着很多优点，使得有着广泛的应用。 w 3 c 的成员认识到随着w e b 的发展，必须由一种方法能够把数据及其显示分 离开来，这样就导致了x m l 的诞生，目前，x m l 已成为w e b 上支持数据交换的标 准，适用于许多重要的应用。由于x m l 字描述、结构和数据分离等优点，使得其 已经成为数据表示和交换的标准，得到了很多应用，当有