（计算机软件与理论专业论文）xml簇聚存储及路径选择性代价估计研究.pdf

摘要 随着互连网的快速发展，出现了大量的w e b 数据，这些w e b 数据多以 x m l 文档形式出现，如何有效存储x m l 文档和从大量x m l 文档中检索有用 信息，已成为数据库研究领域的一个重要研究课题。本文的研究工作主要 围绕x m l 数据存储和查询优化展开，重点研究x m l 簇聚存储模型和路径选 择性代价估计。 首先对x m l 技术做了综述，分析了儿的研究现状和技术上的突破， 然后重点从x m l 簇聚存储和查询优化两个方面做了深入的研究工作。在 订l 簇聚存储方面，针对d o m ( 文档对象模型) 不能有效减少x m l 查询的 磁盘i o 问题，提出了x c l u s t e r 簇聚存储模型，此模型根据结点划分思想将 x m l 文档中结点结构与结点值最为“相似 的一组结点簇聚在一起，并为 不同的结点值类型引入了不同的存储模型和压缩方法，解决了以往簇聚模 型中人为地割裂结点结构与结点值之间的关系，簇聚误差过大的问题；在 x m l 查询优化方面，深入研究了x m l 路径选择性代价估计，详细分析了基 于直方图的路径选择性代价估计( m ) 方法，针对h p m 方法计算效率低， 选择性估计精度不高的缺点，将x - c l u s t e r 簇聚大纲统计信息模型引入路径选 择性代价估计中，提出了c h p m 方法。该方法通过计算选择率为百分之百的 结点或路径跳过不必参与直方图运算的结点或路径，减少了代价树的规模， 从而提高路径选择性代价估计的效率；同时为了避免中间结果直方图某些 格中的高频数据对后续直方图运算精度的影响，给出了直方图的压缩策略， 通过压缩使直方图中的数据近似满足均匀分布，从而降低路径选择性估计 的误差。 实验表明，x c l u s t e r 簇聚大纲及基于此大纲和压缩直方图技术的x m l 含值谓词路径选择性代价估计方法无论是针对单谓词简单路径选择性代价 估计还是多谓词复杂路径选择性代价估计，代价估计的相对误差都较低， 是一种可行而有效的方法。 关键词x m l 数据库，x m l 簇聚，代价估计，直方图，稳定性 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t al o to fw r e bd a t aa p p e a r s t h e ya r e a l m o s tr e p r e s e n t e db vx m ld o c u m e n t h o wt os t o r a g ex m ld o c u m e n ta n d r e t r i e v eu s e f u li n f o r m a t i o nf r o mal o to fx m ld o c u m e n tb e c o m e sa l li m p o r t a n t h o t s p o ti nt h ef i e l do fd a t a b a s es t u d y t h i sp a p e rr e s e a r c h e so nt h es t o r a g eo f x m la n dq u e r yo p t i m i z a t i o na n df o c u so nx m lc l u s t e rs t o r a g em o d e la n d s e l e c t i v i t ye s t i m a t i o no fp a t he x p r e s s i o n t h i sp a p e rb e g i n sw i t ht h es u m m a r yo fx m l t e c h n i q u e , a n a l y z e st h e i r c u r r e n ts t a t u sa n dt h eb r e a k t h r o u g ho ft h e i rt e c h n i q u e ，a n dd o e st h es t u d yi nt h e f i e l d so fx m lc l u s t e rs t o r a g ea n dq u e r yo p t i m i z a t i o n i nt h ef i e l do fx m l c l u s t e rs t o r a g e , f a c i n gt h ep r o b l e mt h a td o m ( d o c u m e n to b j e c tm o d e l ) c a nn o t r e d u c et h ed i s ki ot i m e se f f i c i e n t l yi nt h ep r o c e s so fx m lq u e r y , t h i sp a p e r p r o p o s e sx c l u s t e rs t o r a g em o d e lw h i c ha g g r e g a t e st h em o s ts i m i l a rn o d e si n t h ef i e l do fn o d e ss t r u c t u r ea n dn o d e sv a l u e sa c c o r d i n gt ot h ec o n c e p to fn o d e s d i v i s i o n ，p r o v i d e st h ed i f f e r e n ts t o r a g em o d e l sa n dm e t h o d sf o rd i f f e r e n tn o d e v a l u et y p e s ，s o l v e st h ep r o b l e mt h a ts e p a r a t i n gn o d e ss t r u c t u r ea n dn o d e sv a l u e i nt h ep r e v i o u sc l u s t e rm o d e lo b j e c t i v e l ya n dp r e t t ym u c hi n a c c u r a c yo fc l u s t e r a sw e l l i nt h ef i e l do fq u e r yo p t i m i z a t i o n ，t h i sp a p e rs t u d y st h es e l e c t i v i t y e s t i m a t i o no fp a t he x p r e s s i o n ，a n a l y s e st h em e t h o do fs e l e c t i v i t ye s t i m a t i o no f p a t he x p r e s s i o nb a s e do nh i s t o g r a m a i m e da tt h ep r o b l e mo fl o we f f i c i e n c ya n d s e l e c t i v i t ye s t i m a t i o na c c u r a c y , t h ep a p e rp r o d u c e st h es t a t i s t i ci n f o r m a t i o n m o d e lo fx - c l u s t e rs y n o p s i si n t ot h es e l e c t i v i t ye s t i m a t i o no fp a t he x p r e s s i o n a n dp r o p o s e sc h p mm e t h o d ，t h em e t h o dr e d u c e st h es c a l eo fc t ( c o s tt r e e ) b y c o m p u t i n gt h en o d ew i t hs e l e c t i v i t yr a t ei s10 0 a n ds k i p p i n gt h en o d ea n dp a t h m a tn o ti n v o l v e di nh i s t o g r a m s oi t i m p r o v e st h ee 伍c i e n c yo fs e l e c t i v i t y e s t i m a t i o no f p a t he x p r e s s i o n m e a n w h i l e ，i no r d e rt oa v o i dt h ee f f e c tc a u s e db y t h eh i g h f r e q u e n td a t ai nt h em i d d l er e s u l th i s t o g r a mt a b l ew h i c hi m p a c to nt h e a c c u r a c yo fc o n s e q u e n th i s t o g r a m , t h ei n a c c u r a c yo fs e l e c t i v i t ye s t i m a t i o no f p a t he x p r e s s i o ni sr e d u c e db e c a u s eo fc o m p r e s s i n gw h i c hm a k e st h ed a t ai nt h e h i s t o g r a mm o r es y m m e t r i c e x p e r i m e n t a l r e s u l t si n d i c a t et h a t x c l u s t e rs y n o p s i sa n dt h ex m l s e l e c t i v i t ye s t i m a t i o no fp a t he x p r e s s i o nw i t hv a l u ep r e d i c a t e sb a s e do nt h e s y n o p s i sa n dc o m p r e s s e dh i s t o g r a mt h c h n o l o g yh a v el o w e rr e l a t i v ec a c u l a t i o n i i n di se f f e c t i v ea n dp p l i c a b l em e t h o d nt e r m so f ：f l c c t i v i t yestimationerrora n dl sae t t e c t l v e a p p l i c a b l em e t h o di l lt e r m so ts e l e c t w l t ye s t i m a t i o n n o to n l yf o rs i m p l ep a t he x p r e s s i o nw i t hs i n g l ep r e d i c a t eb u ta l s of o rc o m p l e x p a t he x r p e s s i o nw i t hm u l t i p l ep r e d i c a t e s k e yw o r d sx m ld a t a b a s e ，x m lc l u s t e rs t o r a g e ，s e l e c t i v i t ye s t i m a t i o n ， h i s t o g r a m ，s t a b i l i t y l l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签 日期：砬争皇月单日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签 导师签趣日期：丑年月孚日 1 1 研究背景及意义 1 1 1 课题研究背景 第一章绪论 互联网的快速发展使w e b 数据变得更加复杂和多样化，面对庞大的信息海洋， 人们却遇到了w c b 上存在的大问题一虽然可以在线获得各种信息，但是找到所需 要的信息却极为困难。网上信息的海量而无组织使它只能成为庞大但杂乱无章的 信息仓库，人们在检索信息时常常会“迷失方向一，这主要是因为传统的w e b 语 言h t m l 着重描述w e b 页面的显示格式，它不易被解析、检索及“智能化处理一。 在这种情况下，半结构化数据的思想方法被广泛接受，它的具体表现形式之一的 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 ，可扩展标记语言) 数据及相关技术也获得越来 越多的应用。 x m l 是1 9 8 6 年由国际标准化组织( i n t e r n a t i o n a lo r g a n i z a t i o nf o r s t a n d a r d i z a t i o l l ，i s o ) 公布的标准通用标识语言( s t a n d a r dg e n e r a l i z e dm a r k u p l a n g u a g e ，s g m l ) 的子集，由w 3 c ( w o r l d w i d ew e bc o n s o r t i u m ) 所开发，它具有 以下一些特性【l 】：自描述性( 元素的标记描述了信息) ；可扩展性( 用户可以通 过d t d s c h e m a 来定义新的元素) ；提供了更为灵活的机制来表达更为复杂的链接 关系( 使它更适应于w e b ) ；把信息的结构、内容和显示分离开来，主要表示信 息的内容和结构，而把显示交给x s l 或c s s 处理。 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 主要应用于i n t e r n e t 上的信息 表示和信息交换，而传统的数据库技术并不擅长于这些应用，因此对x m l 数据库 技术的研究都集中在n a t i v ex m l 数据库技术上。 由于对x m l 数据库技术的研究才刚刚起步，目前没有统一的存储模型和查询 代数标准，更谈不上像传统的关系数据库那样有完善的关系理论，这就给x m l 数 据库操作及查询优化带来了很大的困难。对x m l 数据的操作主要集中在x m l 信息 检索上，检索的策略主要有两种：导航式遍历和结构连接算法，结构连接算法相 对于导航式遍历来说效率更高，但实现也更复杂，需要更多技术的支持。目前支 持x m l 结构连接的两项关键技术是x m l 存储策略及查询优化技术。前者可以从磁 盘i o 方面加快x m l 结构连接的速度，而后者则可以改变结构连接的顺序或使 x m l 查询树更小化。由于x m l 数据自身的特点，针对它的查询优化和关系数据的 查询优化不同，并不在于对查询代数树执行顺序的调整，而是在于减少查询树的 规模，和关系数据库查询优化相比，它更依赖于精确的统计信息和快速准确的代 价估计方法，同时对l 存储模型也提出了新的要求，因此对它们的研究还需进 一步深入。 1 1 , 2x m l 面临的挑战 目前大量的x m l 数据以文本文档的方式存储，难以支持复杂高效的查询，这 直接导致了n a t i v e 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 数据库领域面临的一个极具挑战性的 课题。 2 1 1 3 课题研究意义 研究为x m l 信息检索服务的x m l 簇聚存储模型及与其紧密相关的路径选择 性代价估计方法是非常有意义的，主要反映在以下两个方面： ( 1 ) 减少查询处理的磁盘i o 次数。x m l 簇聚研究的是在一定的存储粒度下 x m l 数据按照其结构值的最大相似度在磁盘上安置数据的问题，若能在簇聚的过 程中保持x m l 数据的结构值相关特征，则在实现x m l 数据查询处理时能提高信 息的磁盘定位速度，减少磁盘i o 。 ( 2 ) 能加速x m l 查询时导航式遍历或结构连接的速度和精度。在x m l 数据中， 结构信息存在冗余重复，相同结构的结点之间的区别体现在结点所包含的值上， 如果将x m l 数据簇聚并保持数据结构与其对应值的相关统计信息用于指导路径选 择性代价估计，那么无论是对于一次一结点的导航式查询还是一次一集合的结构 连接查询，都能更准更快地定位相关数据，减少中间结果的规模和计算量，提高 检索的速度和精度。 1 2 目前国内外的研究现状 由于x m l 数据半结构化的特点，其数据的存储模型及与存储模型密切相关的 路径选择性代价估计是x m l 数据库领域两项非常关键的技术。尤其是存储模型， 它对于x m l 信息检索意义重大，不仅直接影响着与路径选择性代价估计紧密相关 的统计信息的获取，而且制约着x m l 信息检索的速度和精度，国内外有不少学者 在此方面已做了相关的研究。前期主要受关系数据库成熟完善的关系理论影响， 试图将x m l 结点映射为关系中的属性，通过主- 夕i 、键来表达结点之间的嵌套关系 【2 】，从而将对x m l 数据的操作转化为对关系数据库中对应数据的同等操作。这种 方案的优点是可充分利用现有关系数据库领域完备的理论体系和成熟的市场产 品，但却失去了x m l 数据的可扩展性优势，且随着x m l 元素嵌套层次的增加，仅 靠主外键表达的嵌套关系的设计与维护变得非常困难，因此研究者们将焦点集中 在n a t i v ex m l 数据库技术上。最近的研究表明：无论是采用一次一结点的导航式 遍历还是一次一集合的结构连接算法，x m l 松散的半结构、自嵌套特征是制约其 信息检索的一大障碍【3 】，鉴于关系数据库簇聚的成功经验，各种x m l 簇聚策略相 继被提出。根据x m l 信息检索方式的不同，这些策略大致可分为两类：导航式簇 聚和结构连接式簇聚。前者又可进一步分为父子关系簇聚和兄弟关系簇聚【4 】，分 别对应导航遍历时的深度优先遍历和广度优先遍历。同样地，结构连接式簇聚也 分为两种：s l ( s a m el a b l e ) 聚簇、s p ( s a m ep a t h ) 聚簇【5 , 6 1 ，簇聚的原理是结点 划分或相似路径划分，其中s l 簇聚简单直接，很容易实现，但是目前对它的研究 3 还很不够，仅仅考虑其结构的簇聚，忽略结构与值的关系；s p 聚簇则以绝对路径 来标识簇聚，这种方法既可以通过路径索引又可以通过数据向导( 具有相同路径 的结点作为一个目标集合来管理) 来实现，当新的聚簇分配绝对路径时，聚簇的 数量与数据向导的数量一样，但当具有同样标签的结点由于绝对路径的不同时， 这些结点将被存储到不同的聚簇中，因而不能有效减少磁盘i o 。针对s l 、s p 各自 的优点和不足，国内有人提出p s i m 簇聚【7 】，基本思想是先对x m l 文档进行s l 聚簇 后，再s p 聚簇，然后将x m l 文档中具有相同路径的结点作为一个聚簇的基本单元， 比较这些基本单元的相似度，形成路径相似图，利用图分割技术分割结点，从而 达到在处理查询时减少页面f o 的目的。在此领域国外的研究更为深入，不仅研究 了v f l 元素结构簇聚【8 9 ，1 0 1 ，而且还将x m l 数字类型的元素值综合考虑到结构路径 中，形成结构值簇聚【1 1 , 1 2 , 1 3 】。这些基于结点划分【1 4 】理念的簇聚，特别是综合考虑 x m l 元素的结构和值的簇聚思想为我们进一步的研究带来了深刻的启示。 在x m l 路径选择性代价估计方面，最早研究路径表达式选择性代价估计的文 献可能是文献 1 5 】，在此文献中，作者虽然没有明确提到路径表达式选择性代价估 计的概念，但是某些优化的技巧是针对这一问题的。根据路径选择性代价估计依 赖的统计信息模型的不同，目前发展起来的路径选择性代价估计方法主要有基于 树理论，图理论，直方图理论三个方向。由p a h s r a f a b o u l n a g a 等提出的路径树【1 6 1 和z h i y u a nc h c n 、h 等提出的c s l 【1 7 l ( c o r r e l a t e ds u b p a t ht r e e 相关子路径树) 是基 于树模型路径选择性代价估计方面的典型代表。路径树方法通过遍历路径表达式， 用整个遍历过程中所有遍历结点的频数和作为路径表达式的选择性。此方法存在 一个粒度把握的问题，同时，当路径树规模比较大时，对路径树的概括比较困难； 至于c s t 方法，它又是基于p s t ( p r u n e ds u b p a t ht r e e ) 和后缀树( s u 伍xt r e e ) 的， 用它来计算t w i g 查询的路径选择性需通过路径解析( p a t hp a r s i n g ) 、t w i g l e t 分解 ( w c i g l c td e c o m p o s i t i o n ) 及合并( c o m b i n a t i o n ) 三步，由于在分解合并过程中存在 信息重复和可能的丢失，因此选择性代价估计的精度得不到保证。图理论方面的 典型代表是x s k e t c h t l 8 , 1 9 】及其改进的x s k c t c h c s 1 2 】，该方法用独立性分布假设成功解 决了简单路径和分枝路径的选择性代价估计，遗憾的是没进一步考虑谓词约束， 因而也就不能计算含有谓词的路径表达式。与前面介绍的两类方法不同，s t a t i x t 】 用基于模式统计信息的直方图【8 2 0 , 2 1 】来计算路径的选择性，它在模式验证时收集所 需要的统计信息，在收集过程中通过对x m ls c h e m a 的调整来调节统计信息收集的 粒度，而计算的方法相对简单，主要是针对直方图的各种运算，此方法不足之处 是需要全局模式信息的支持，这样虽然获得了精确的统计信息，但却大幅度地增 加了系统的存储负担，同时也加大了获取统计信息的计算复杂度，选择性代价估 计的效率不高。综合以上x m l 簇聚存储和路径选择性代价估计方面的研究我们发 4 现：路径选择性代价估计是和x m l 数据存储模型及统计信息模型密切相关的，以 何种粒度实现x m l 元素及值的簇聚存储并保持结构和值之间的关系，进而构建计 算量少、统计信息全面的统计模型用于x m l 复杂路径选择性代价估计是一个非常 有待进一步研究的课题。 1 3 论文的主要工作 本文所要做的主要工作如下： ( 1 ) 总结分析x m l 领域相关技术的研究情况，其中包括x m l 文档的数据模型 及模式特征；x m l 数据库领域中x m l 数据库发展趋势、数据库分类、数据库查询 语言、存储模型及查询优化技术等。论文主要讨论它们各自的研究进展和技术上 的突破，旨在为论文打下一个坚实的理论基础。 ( 2 ) 构建x - c l u s t e r 簇聚大纲模型。给出x - c l u s t e r 大纲的数据模型；阐述x c l u s t e r 大纲构建的原理、方法并推导模型的相关性质；介绍n u m e r i c 、s t r i n g 、t e x t 三种 数据类型在大纲中的存储模型及压缩策略；设计基于原子查询建立误差的簇聚误 差评估公式；设计并分析x c l u s t e r 簇聚大纲模型的构造算法。 ( 3 ) 研究x m l 路径选择性代价估计。首先将x - c l u s t e r 簇聚大纲引入路径选择性 代价估计，给出簇聚基的直方图表示的定义和x - c l u s t e r b 蒺聚大纲统计信息模型；然 后介绍基于直方图的路径选择性代价估计方法并分析其优缺点，在此基础上结合 x - c l u s t e r 簇聚大纲提出一个效率高，误差少的改进方法；最后通过两组实验分析说 明改进方法的实验性能。 ( 4 ) 总结全文的工作并指出本论文存在的不足及今后需进一步研究的内容。 1 4 论文的组织 论文全文共分五章，文章组织结构安排如下： 第一章绪论。本章主要介绍了本文研究的背景、研究的意义和论文要做的主 要工作。 第二章n a t i v ex m l 数据库相关技术研究。本章是全文的理论基础知识部分。 主要讨论当前x m l 研究领域各方面的研究成果及技术上的突破j 着重阐述一些已 经发展起来的重要概念和理论。 第三章构建x c h l s t e r 簇聚大纲模型。本章主要从x c l u s t e r 簇聚大纲数据模型， 结点合并，误差度量，结点值簇聚，结点值压缩，构建算法六个方面介绍簇聚大 纲构建的原理和具体方法。本章着重在于构建一个模型。 第四章基于x - c l u s t e r 簇聚大纲指导的路径选择性代价估计。本章是在上一章 5 的基础上将x - c l u s t e r 簇聚大纲模型用于路径选择性代价估计中，提出簇聚基的直方 图表示方法和x - e l u s t e r 簇聚大纲统计信息模型，在此基础上给出路径选择性代价估 计的新方法。最后进行实验性能测试。 第五章结论与展望。本章对本论文的研究工作做了个系统全面的总结，并对 下一步的研究工作做了大致的展望。 6 第二章n a t i v ex m l 数据库相关技术研究综述 2 1x m l 相关概念 2 1 1x m l 文档 w 3 c 提出的标准超文本标记语言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 ) 是一种 用于i n t e m e t 上交换和表示数据的格式。一个x m l 文档由嵌套的元素层次结构构 成，每个文档有一个唯一根节点，一个元素有一个标记，描述该元素的含义，一 个元素由从起始标记到终止标记的区域构成，该区域可以是嵌套的子元素，也可 以是属性或文本串值。图2 1 显示了一个描述员工信息的x m l 文档样例，它以 “e m p l o y e e s 元素为根。 图2 1 一个x m l 文档样例 由图2 1 可以看出x m l 文档的如下几个特点：首先一个元素可以由其一个或多 个子元素描述；其次x m l 数据是半结构化的数据，一个元素可以有多个标记相同 的子元素，且标记相同的子元素可能具有不同的结构，如“e m p l o y e e s ”有两个异构 的“e m p l o y e e 子元素。 7 订l 文档有两种基本类型： ( 1 ) 良构型x m l 文档 良构是x m l 文档基本的要求，良构型文档必须符合某些一致性约束并且不引 用任何外部的d t d s c h e m a 。一个符合x m l 标记规范的文档被称为良构 ( w e l l f o r m e d ) 的文档，一个良构x m l 文档可以没有d i d s c h e m a 定义。良构型文 档不必遵守其内部的d t d s c h e m a ，尽管它可能自身带有d t d s c h e m a 。 ( 2 ) 有效型x m l 文档 有效型x m l 文档是良构的，且必须满足正确性约束。有效型文档标注的结构 必须符合某个和文档关联的d t d s c h e m a ，它必须在内部包含d t d s c h e m a ，或者 显式地指明它所引用的外部d t d s c h e m a 文件。 2 1 2x m l 数据模型 数据模型是人们对现实世界的抽象，它是随着应用的需求和人类对信息管理 研究的不断深入而逐渐发展的。1 9 7 0 年e e c o d d 提出了关系模型，在此基础上建 立的关系数据库获得了巨大的成功。后来又出现了面向对象的数据模型，它能表 达数据间的嵌套、递归关系，并且具有面向对象技术的封装性和结构性的特点， 基于对象模型的面向对象数据库系统也应运而生。 传统的数据库管理系统使用的是基于结构化的数据模型，其特征就是数据库 预先都有一个固定的模式，数据遵守严格的类型定义，而x m l 数据的模式却是不 规则、不固定的。关于x m l 数据模型的研究，目前已取得了一些研究成果，下面 介绍两种常见的x m l 数据模型及其各自的特征。 ( 1 ) o e m 模型 1 9 9 4 年，斯坦福大学首次在t s i m m i s l 2 2 1 系统中提出o e m ( o b j e c te x c h a n g e m o d e l ) 模型，用于描述半结构化数据及异构数据的集成。目前o e m 己成为通用的 半结构化数据模型。 在o e m 模型中，半结构化数据可以用一个有向的标记图来表示，一个o e m 对 象由一个四元组 表示，其每个域的意义如下： 1 ) l a b e l ( 标注) ，字符串，描述对象的意义； 2 ) 砌口( 类型) ，对象值的类型，包括两种：一种为原子型，如i n t e g e r 、r e a l 、 s t r i n g 、i m a g e 、p r o g r a m 等；另一种为复杂类型，包含零个或多个子对象，每个子 对象用一条带标记的边与其相连。对象类型为原子型的称为原子对象，而对象类 型为复杂型的称为复杂对象。 3 1v a l u e ( 值) ，对象的值； 钔o l d ( 对象标识) ，用于唯一标识每个o e m 对像，而且在o e m 模型中，每 个对象允许有多个父对象，因此在有向图中允许有环的存在。 ( 2 ) d o m 模型 文档对象模型【捌( d o c u m e n to b j e c tm o d e l ) 是一个抽象数据结构，将x m l 文档 表示为由节点构成的树。d o m 把节点分成1 2 类：文档节点( d o c u m e n tn o d e ) ，元 素节点( d e m e n tn o d e ) ，文本节点( t e x tn o d e ) ，属性节点( a t t r i b u t en o d e ) ，处理 指令节点( p r o c e s s i n gi n s t r u c t i o nn o d e ) ，注释节点( c o m m e n tn o d e ) ，文档类型节 点( d o c u m e n tt y p en o d e ) ，文档段节点( d o c u m e n tf r a g m e n tn o d e ) ，符号节点( n o t i o n n o d e ) ，c d a t a 段节点( c d a t as e c t i o nn o d e ) ，实体节点( e n t i t y n o d e ) ，实体引用 节点( e n t i t yr e f e r e n c en o d e ) 。 图2 2 给出了图2 1 “e m p l o y e e s 文档部分内容对应的d o m 树的例子。 匿12 - 2 e m p l o y e e s ”文档部分的d o m 树 2 1 3d t d 与x m ls c h e m a d t d 2 4 1 ( d o c u m e n tt y p ed e f i n i t i o n ，文档类型定义) 用不同于x m l 的独立语法 来规定x m l 文档中各种元素集合的内容模式，它主要采用元素类型声明和属性表 声明限制x m l 文档中元素的结构。元素类型声明限制了元素的内容，通常也限定 了子元素的类型。属性表声明用于定义与给定元素类型有关的属性集，它还可以 指定这些属性的类型限制并能提供缺省值。通常属性表声明紧跟在元素类型声明 之后，其定义由属性名称、属性类型和缺省值声明组成。 d t d 是x m l 由s g m l 处继承而来并加以发展的文档类型定义方法，有着一定 9 的缺陷：本身不是用x m l 书写的；不支持名字空间嗍( n a m c s p a c e ) 提供了非常 有限的数据类型；不能表达元素中字符数据的数据类型；虽然有扩展的机制，但 这个机制太复杂而且很脆弱且参数体的属性之间不能建立任何联系。因此w 3 c 又 提出了讧l s c h e m a 2 6 】来表达x m l 的内容和结构，大大弥补了d t d 的不足： 1 ) x m ls c h c m a 本身就是x m l 文档 2 ) x m ls c h e m a 支持丰富的数据类型包括数字型、布尔型、整型、日期时间、 u r i ( 统一资源标识符) 、十进制数等。 3 ) x m ls c h e m a 内容模型是开放的，可以随意扩充、更新。 钔x m ls c h e m a 支持名字空间。 图2 - 3 “e m p l o y e e s 文档对应自ds c h c m a 1 0 x m l 支：档的d t d 或s c h e m a 定义了文档的结构和可能存在的元素，并定义各种 元素的相关信息。图2 3 与图2 _ 4 分别是图2 1 中“e m p l o y e e s ”文档对应的x m l s d l e m 拥d t d 。 ! e l e m e ! n t ! e l e m e n t ! a t t i ，i s t ! e l e m e 卜i ，r ! e l e m e n t ! e l e m e n t ! e l e m e n t e m p l o y e ei di d # r e q u i r e ds u p e r v i s o ri d r e f # i m p l i e d n a m e ( # p c d a t a ) s a l a r y ( # p c d a t a ) s a l a r yp a y p e r i o d c d a t a # i m p l i e d d e p a r t m e n t ( t i t l e + , d u t y d e s ) t i t l e ( # p c d a t a ) d u t y d c s ( # p c d a t a p 2 2x m l 数据库技术 2 2 1x m l 数据库定义 图2 4 “e m p l o y e e s 文档对应的d t d x m l 数据库【2 7 】是可以对x m l 文档进行存取管理和数据查询的数据库，是一 个能够在应用中管理x m l 和文档的数据库系统。一个x m l 数据库是x m l 文档及其 部件的集合，并通过一个能管理和控制这个文档集合本身及其所表示信息的系统 来维护。x m l 数据库不仅是结构化数据和半结构化数据的存储库，持久x m l 数据 管理包括数据的独立性、集成性、访问权限、视图、完备性、冗余性、一致性以 及数据恢复等。 2 2 2x m l 数据库分类 按照x m ld b i n i t i a t i v e 提出的分类【2 3 1 ，可以把现有的x m l 数据库分成两种： 原生x m l 数据库( n a t i v ex m ld a t a b a e s ，n x d ) 、支持x m l 的数据库( 订le n a b l e d d a t a b a s e ，x e d ) 。 ( 1 ) 原生x m l 数据库( n x d ) n x d 是专门设计用于存储x m l 数据的数据库，其特点是以x m l 数据自身 ( n a t i v e ) 的形式来存储x m l 数据，不需要进行数据转换就可以充分发挥x m l 的 优势。它有着特定的数据结构来描述层状的x m l 数据，并通过其层次特点来优化 查询。n x d 是被普遍认为代表发展方向的新型数据库，其定义如下： 它为x m l 文档( 而不是文档中的数据) 定义了一个( 逻辑) 模型，并根据该 模型存取文件。这个模型至少应包括元素、属性、p c d a t a 和文件顺序。这种模 型的例子有x p a t h 数据模型、x m li n f o s e t 以及d o m 所用的模型和s a x 的事件。 它以x m l 文档作为其基本( 逻辑) 存储单位，正如关系数据库以表中的行作 为基本( 逻辑) 存储单位。 它对底层的物理存储模型没有特殊要求。例如，它可以建在关系型、层次型 或面向对象的数据库之上，或者使用一个专门的存储格式，比如索引或压缩文件。 ( 2 ) 支持x m l 的数据库( x e d ) x e d 是在传统数据库的基础上增加对x m l 的支持，以便保存和输出x m l 形式 的文档，通过适当的捌l a p i ( 如o r a c l 9 ir 2 增加了一些数据包来操作x m l 数据等) 对x m l 文档进行查询和修改。从存储粒度上，可以把整个x m l 文档作为数据库表 中的一行，或把x m l 文档进行解析后，存储到相应的表格中。目前主流的关系型 数据库供应商都是采用这一种方式提供对x m l 的支持，他们通过将x m l 映射成关 系表，从而将x m l 结构变成了平面的行和列【2 9 1 。但是当遇到大型或复杂文档时或 当用户需要进行x m l 查询或其他处理时，在x m l 与数据库之间进行来回转换要耗 费相当多的处理时间，数据库需要重新组合这些数据，这就会降低数据的处理速 度，从而降低了w e b 页面的生成速度，因此实际应用受到限制。 2 3x m l 数据库查询语言 近年来，为了查询x m l 数据，提出了许多种x m l 查询语言，如l 0 r e l 、x m l - q l 、 x m l - g l 、x q l 、x s l t 、q u i l t 和x q u e r y 等。文献 3 0 】对这几种语言进行了比较和 详细的分析。 由于x q l l d 3 1 】是由w 3 c 组织提出的一种最新的x m l 查询语言标准，它吸收了 多种已有的x m l 查询语言的优点，己成为现在公认的x m l 查询语言标准，x q u e r y 的核心子集是x p a t h 3 2 1 ，因此本文主要采用x p a t h 作为处理x m l 文档的工具。 2 3 1x p a t h 查询语言 ( 1 ) x p a t h 简介 x p a t h 是由w 3 c t 亟j 建的。在w 3 c 的规范里，对x p a t h l 0 的描述是这样的： “x p a t h l 0 是致力于为x s l t 和x p o i n t 的公共功能提供一种共同的语法和语义的结 果。x p a t h 的主要目的是对一个x m l 文档进行寻址。为了支持这个主要目的，它也 为操纵字符串、数值和布尔值提供了一些基本功能。x p a t h 使用一种紧凑的