（计算机应用技术专业论文）xml数据流xpath查询模型研究.pdf

摘要 x m l 流数据处理系统通常运行在w 曲上，使用的用户可能增加 到十万、百万级的数量。而用户查询通常用x p a t h 语言表示，当x m l 数据以网络速度流入时，系统根据x p a m 描述，判断x m l 数据流是 否满足某个用户的需求。如果满足，则触发应用程序采取某种动作， 如向用户返回相关的文档等。由于一个用户可以提交若干查询，查询 的数量十分巨大。因此x m l 流数据处理研究的一个关键挑战是如何 同时有效处理大量来自用户的查询并及时将结果返回给用户。 本文针对x m l 数据流的特点，在总结目前x m l 数据流x p a t h 查询处理方法的基础上，针对很多应用数据环境不确定的状况，提出 一种新的查询模型g b r e n d e r ( g r o u p b a s e dr e n d e r i n go f ld a t a s t r e a mx p a t hq u e wm o d e l ) ，即基于组着色的l 数据流x p a t h 查 询模型，以及适应该模型的一种谓词处理模型，主要内容如下： l 、提出了一种新的查询模型g b r e n d e r ：基于组着色的x m l 数 据流x p a t h 查询模型。给出了组着色的概念、相关定义以及该模型的 结构特征和处理模型。 2 、提出了一种x p a t h 谓词处理的主动计算模型，在对谓词表达 式特点深入分析的基础上，给出的主动计算模型的基本思想，模型结 构及处理算法。 3 、给出了基于组着色查询模型对单枝查询的处理算法以及应用 主动计算模型进行复杂谓词处理的过程。 4 、通过实验证明了组着色查询模型的低依赖性与有效性。 关键词：x m l 数据流；x p a t h 查询；组着色；谓词处理：主动计算 a bs t r a c t x m ls t r e 锄d a t ap r o c e s s i n gs y s t e m st y p i c a l l yn mo nw 曲，t h eu s e r s m a yi n c r e a s et oh u n d r e d so ft h o u s a n d s ，m i l l i o n s a n du s e r s q u e r i e sa r e u s u a l l ye x p r e s s e di n ) a t hl a n g u a g e t h es y s t e md e t e m l i n e sw h e t h e rt h e x m ld a t as 拓e a mt os a t i s 矽as p e c i a lu s e r sd e m a n da c c o r d i n gt ot h e x p a t hd e s c r i p t i o nw h e nx m ld a t ai n f l o w sb yn e t w o r ks p e e d i fm e t ，i t w o u l d 仃i g g e rt h e 印p l i c a t i o nt ot a k es o m ea c t i o n s ，s u c h2 u sf e e d i n gb a c k r e l a t e dd o c u 【m e n t st ou s e r s au s e rm a ys u b n l i tan u l l ：1 b e ro fq u e r i e s t h e r e f o r eq u 嘶e s q u a l l t 蚵i sv e 巧h u g e t h u s ，f o rx m ld a t as t r e a m q u e r yr e s e a r c h ，ak e yc h a l l e n g ei sh o wt oe f f e c t i v e l yd e a lw i t hal a 唱e n u m b e ro fi n q u i r i e s 仔o mu s e r sa n dp r o m p t l yr e m mt h er e s u l t st ot h eu s e r t h i sa r t i c l ei nv i e wo ft h ex m ld a t as 仃e 锄sc h a r a c t e r i s t i c ，o nt h e f o u n d a t i o no ft h es u m m a r yo ft h ep r e s e n tx m ld a t as t r e 锄x p a t hq u e 巧 p r o c e s s i n gm e t h o d ，i nv i e wo ft h em a n ya p p l i c a t i o ni ni n d e f i n i t ed a t a e n v i r o n m e n t s c o n d i t i o n ， p r o p o s e d an e wq u e 巧m o d e lg b r e n d e r ( g r o u p b a s e dr e n d e r i n go fx m l d a t as 仃e 锄x p a t hq u e 巧m o d e l ) ，t h a t i s ，g r o u p - b a s e dr e 】d e r i n go fx m l d a t as 仃e a mx p a t hq u e r ym o d e l ，a s w e l la so n ek i n do fp r e d i c a t ep r o c e s s i n gm o d e lw h i c ha d a p t st h i sm o d e l t h em a i nc o n t e n t sa r ea sf 0 1 1 0 w s ： 1 i tp r o p o s e dan e wx m ld a t as 仃e a mx p a t hq u e r ym o d e ln 锄e d g b r e n d e r ：g r o u p - b a s e dr e n d e 打n gx m ld a t as t r e 锄x p a t hq u e 巧 m o d e l ，a n dt h e 伊o u pr e n d e r i n gc o n c 印t ，m er e l a t e dd e f i n i t i o n ，a sw e l la s t h em o d e ls t m c t u r a lf e a t u r ea 1 1 dt h ep r o c e s s i n gm o d e lh a v eb e e ng i v e n 2 i tp r o p o s e do n ek i n do fx p a t hp r e d i c a t ep r o c e s s i n gi n i t i a t i v e c o m p u t a t i o nm o d e l ， o nt h ef o u n d a t i o no ft h o r o u g ha n a l y s i so ft 1 1 e p r e d i c a t ee x p r e s s i o n c h a r a c t e r i s t i c s ， i th a s g i v e n t h ei n i t i a t i v e c o m p u t a t i o nm o d e l sb a s i ci d e a ，t h em o d e ls t n l c t u r ea n dt h ep r o c e s s i n g a l g o n t h i n 3 i th a sg i v e nt h es i n g l eb r a n c hq u e 巧p r o c e s s i n ga l g 耐t h i nu n d e r g b i 沁n d e rm o d e l ， a sw e l la st h es t m c t u r eo fu s i n gt h ei n i t i a t i v e c o m p u t a t i o nn l o d e l t o p r o c e s sc o m p l e xp r e d i c a t e s ，a n dp r o v e s i t s e m c i e n c y 4 t h eg r 0 1 l pr e n d e rq u e 巧m o d e l s1 0 wd 印e n d e n c ea n dv a l i d i t yh a s b e e np r o v e dt h i - o u g he x p e r i m e n t s k e y 、r d s ：x m ld a t as 仃e a n l ，x p a t hq u e 铲o u pr e n d e m g ，p r e d i c a t e p r o c e s s i n g ，i n i t i a t i v ec o m p u t a t i o n i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 13- 1 学位论文作者签名： 、1 毒拦，厂年 6 月lz 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： ；1 1 善经 如蛉 日期：叫年6 月他日 日期：圳年月i 日 x m l 数据流p a f h 奄询模璎研究 1 1 研究的背景和意义 1 1 1 研究背景 1 绪论 可扩展的标记语言x m “1 1 ( e x t e n s i b l em a r l ( u pl a n g u a g e ) 19 9 8 年 2 月由万维网协会w 3 c ( w b r l dw i d ew - e bc o n s o n i 啪) 推出，作为 s g m l ( s t a j l d a r dg e n e r a lm a r k u pl a n g u a g e ) 的精简子集，是一种简 单、灵活的文本格式。x m l 继承了s g m l 可扩展、自描述和简明性 的特性，能轻松地表示表格式数据( 如数据库中的关系数据或电子表 格) 和半结构化数据( 如w e b 页面或业务文档) 。它不依赖于任何编程语 言、操作系统或软件供应商，可以提供对各种数据处理、构建、转换 和查询技术的访问。经过多年的发展和应用，x m l 强大的数据表达 能力及其内容与表示分离的特性，使得它成为目前互联网上通用的数 据的表示和交换格式。 目前随着i n t e m e t 的普及和w e b 的广泛应用，以及i n t e m e t 上数 据信息量爆炸式的增长，出现了一类数据密集的应用。这种应用的特 征是数据以快速、实时的数据流形式持续到达，适宜用数据流建模。 由于x m l 已经成为w r e b 上数据交换的标准，用于各种应用和信息源 之间的数据交换，所以，x m l 数据流是这种流数据的主要形式。这 些实时到达的x m l 流中包含大量的信息，并需要根据不同用户的需 求从这些信息中过滤、抽取出各个用户关注的信息。因此x m l 数据 流的高效查询成了目前业界研究的热点。 流数据处理系统与传统数据库管理系统不同。传统数据库管理系 统的主要特点是数据持久存储，在某一时刻执行查询并通过稳定查询 计划给出精确的回答；而流数据处理系统强调数据在线到达，查询持 久存储。在流数据处理系统中，不可能控制数据到达的顺序，将所有 硕十学位论文 到达的数据存储在本地进行管理和查询也是不现实的。流数据处理技 术引起研究界的广泛兴趣，具有极其广阔的应用前景，可以应用在传 感器网络、位置搜寻、网络监控、金融分析、在线拍卖等诸多领域。 制定x m l 技术规范标准的w 3 c 在1 9 9 9 年推出了x m l 文档寻 址语言x p a t h1 o 。x p a t h 2 】使用和传统计算机文件系统路径相似的路 径表达式来选择x m l 文档中的n o d e s ( 节点) 或是n o d e s e t ( 节点集) 。 x p a t h 的出现给x m l 文档的查询提供了规范，也使得x m l 流查询 的重点转移到对x p a t h 表达式的处理。为了精确进行查找，在应用中 经常为查询附加很多限制条件，这些限制条件对应于x p a t h 表达式中 的谓词，包含谓词的x p a t h 表达式不再是线性的，这就增加了处理 x p a m 表达式的难度，如何高效的处理谓词是提高查询效率的关键因 素。 x m l 流数据处理系统通常运行在w 如上，其上的用户会迅速增 加到十万、百万级的数量。用户查询通常用x p a t h 语言表示。由于一 个用户可以提交若干查询，查询的数量十分巨大。x m l 流数据处理 研究的一个关键挑战是如何同时有效处理大量来自用户的查询并及 时将结果返回给用户。 1 1 2 研究的现实意义 随着网络应用的快速发展，符合x m l 规范的数据大量存在于当 前的信息社会，尤其是电子商务、w r e b 服务、数字图书馆等应用理念 的进一步发展，使得x m l 类型的数据成为当前主流的数据形式，用 于各种应用和信息源之间的数据交换，因此针对x l l 数据流的研究 赋予了数据流管理技术新的意义。 主动服纠3 】是近几年来提出的建立在w e b 服务技术规范之上的 新的服务模型。它能够根据用户的个性化要求和特点，对服务进行定 制和帮助，从而改变w 曲服务无法根据用户需要而动态变化、主动 适应用户要求的状况。目前广泛应用的订购和发布系统就是主动服务 x m l 数据流p a f h 查询模型研究 中的一个典型应用。而其中关键技术之一就是海量x m l 数据的x p a m 查询问题。在订购阶段，用户利用x p a t h 描述其需求，保存到系统中。 在发布阶段，当x m l 数据以网络速度流入时，系统根据x p a t h 描述， 判断x m l 数据流是否满足某个用户的需求。如果满足，则触发应用 程序采取某种动作，如向用户返回相关的文档等。此时如何在x m l 数据流上高效的执行大量的x p a t h 查询成为主动服务实现中要解决 的关键问题之一。 1 2 研究现状 针对x m l 流处理系统，目前所采用的主要方法是基于自动机的 方法【5 】【6 】【9 】 1 0 】【2 2 】【3 3 】【3 5 】【3 6 1 、其他的有基于索引的方法 12 1 、基于 b 1 0 0 m f i l t e 一1 3 1 的方法、f i s t 4 5 】方法等。 自动机可作为计算机和计算过程的数学模型，在查询匹配、模式 识别、生物变异等复杂过程建模中有许多应用。每个形式语言都存在 一个接受该语言的自动机【4 】。而任意一个a m 路径表达都可以用形 式语言表示。因此人们自然将自动机技术运用到x p a t h 查询处理中， 对x p a t h 表达式建模。 m e e ta 1 t l n e l 首先将自动机技术引入x m l 查询，实现了第一 个支持大规模查询、过滤x m l 文档的x f i l t e r 【5 】o 在x f i l t e r 中用有限 状态机f s m ( f i l l i t es t a t em a c h i n e ) 来表达，a t h 查询，即用户的查询 信息用x p a m 查询表示，而每个x p a t h 查询则分别对应着一个有限状 态机，然后利用一个建立在这些f s m 上的查询索引同时对所有的 x p a t h 查询进行处理。由于每个x p a t h 查询分别对应着一个f s m ，所 以对于用户的查询信息中可能存在大量相似查询的情形它并没有减 少这些冗余查询的处理。 y f i l t e r 【6 】是基于自动机方法的典型代表，具有较强的查询处理能 力，y f i l t e r 根据x p a t h 构造了n f a 自动机，所有自动机合并为一个 自动机。如果自动机在数据的驱动下到达某个终止状态，则数据流满 硕十学位论文 足该终止状态所对应的查询。y f i l t e r 能够减少不同查询处理中的重复 计算，高效地处理不包含 ) 的x p a t h ，但是需要保存中间状态上的 计算结果来处理支持 的x p a t h 查询。 x 嘣e 7 】提出了只包含父子关系的子路径表达式索引机制，并使用 索引提取多个查询的公共子路径，实现包含谓词逻辑的x p a t h 处理。 上述方法本质上是非确定处理机，即在运行过程中，处理机内部 存在若干活动状态，执行效率随着所支持x p a t h 的增加而减少。而现 有的另外一类x m l 数据流的查询处理，是基于确定自动机来构造的。 d a ns u c i u 等在文献【8 】中首先根据x p a t h 构造n f a 自动机，然后 在n f a 自动机之上执行确定化。这样，系统在运行的任意时刻，始 终只有一个运行状态，系统的处理效率与所处理的x p a t h 数目无关。 然而，这种方法可能导致相对于查询数目指数级别的空间复杂性。另 外，整个查询处理机表达能力有限，不支持x p a t h 中的 】) 操作符。 x p u s h 9 】解决了n f a 自动机的表达能力的问题。这一扩展主要利 用了支持表达路径之间a n d 0 r 关系的a f a 自动机，舢认自动机利 用扩展的状态来保存不同路径的执行情况。x p u s h 执行器也是基于确 定化自动机，提高了系统的查询效率，但是同样也面临着指数级别的 确定化空间代价的问题。 文献【l o 】就1 a z y d f a 共享n f a 状态表的优化算法提出了在状态结 构中增加一个状态转移条件表，避免为了不需要的事件而去查找n f a 状态表的情况来提高查询速度，但l a z y d f a 只适合于一定模式的 x m l 流文档。 x e b t 【1 1 】是一个基于树自动机的x p a t l l 查询模型，利用树自动机 的表达能力实现了高效的x p a t h 查询，但是其没有对谓词处理进行具 体的分析。 其他处理x m l 流的方法主要有基于索引的方法【1 2 】、基于b 1 0 0 m f i l t e r 【1 3 】的方法以及f i s t 【4 5 】方法。i n d e x f i l t e r 旧采用基于索引的技术 处理x m l 流数据。i n d e x f i l t e r 利用x m l 文档流的文档标记动态地 建立x m l 文档的索引，从而避免处理一部分x m l 文档。与y f i l t e r m l 数据流p a t h 查询模型研究 相比，他们通过实验表明：当查询数量相对较小而x m l 文档相对较 大时，i n d e x f i l t e r 更有效( 在不考虑建立索引所花费的代价的前提下) ； 当查询数量相对较大而x m l 文档相对较小时，y f i l t e r 更有效。在 i n d e x f i l t e r 的方法中，建立索引要花费一定的时间代价。另外，不能 单遍处理x m l 文档。i n d e x f i l t e r 没有考虑对a n d 或o r 谓词的处 理问题。基于b 1 0 0 mf i l t e r 的x m l 包过滤器是一种近似查询方法， 利用b 1 0 0 mf i l t e r ，将x p a t h 表达式作为字符串，将x p a t h 与x m l 包 之间的匹配转换为字符串之间的匹配，从而提高查询性能。它只是用 来处理简单的x p a t h 表达式( 不包括谓词，只包括“”、“ 、“妒， 称为x p ，) ，并且有一定的失误率。f i s t 针对t w i gp a t t e m 提出一 种有别于y f i l t e r 的方法，将一组t w i gp a t t 哪转换为p m f e r 序列，并 对一组t w i gp a t t e m 与x m l 流数据进行整体性匹配。f i s t 考虑的是 具有a n d 谓词的t w i gp a t t e m ，而没有考虑如何处理o r 谓词。 文献【m 】针对x m l 流数据的、具有嵌套a n d o r 谓词的复杂t w i g p a t t e m 查询处理，提出一种新方法。将所有t w i gp a t t e m 合并为一个 共享前缀的查询树，其中，舢岫0 r 谓词被表示为单独的抽象语法树， 因而能够以文档顺序、单遍地处理复杂t w i gp a t t e m 的匹配，并避免 y f i l t e r 中对嵌套谓词进行后置处理所产生的中间结果。但没有讨论递 归x m l 文档的处理。 在聚集函数的处理上，针对x m l 流数据上只能扫描一次情况的 聚集问题，文献 4 4 提出了一种算法，算法包括两个部分，一部分是 查询对象的获取，得到相应的维属性和度量属性，另一部分将获取到 的查询对象根据维属性聚集到相应的分组中，两部分在x m l 流数据 处理过程中交替进行。 文献 4 3 讨论了x m l 流处理系统中的缓存管理问题，提出了针 对x m l 数据流x q u e u 查询缓存的处理方法，其处理原则同样也适 用于x p a t h 查询，但对x p a t h 中谓词处理未作讨论。 此外，有文献【1 5 】使用某种结构预先编码x m l 文档的部分结构信 息，称为流索引( s t r e a mi n d e x ，简称s i x ) ，并把其加入x m l 文档流。 硕十学位论文 这样，流处理引擎就可以根据流索引提前决定略去对哪些元素的解 析。这种方法的缺点是流处理引擎必须了解数据源端的流索引信息。 基于自动机方法的一个瓶颈是随着查询的复杂性和数量的增加， 状态数目会呈指数级增长。而使用i n d e x b a s e d 的机制，其好处在于 可以忽略掉不符合查询要求的数据，但必须建立好索引结构。虽然建 立索引结构可以避免不必要的比对动作，以提升x m l 文件之查询效 率，但是却需要额外的存储空间。在x m l 流数据环境下，在传送端 建立好索引随流数据一起传送，这会增加传送端负担，在接收过程中 加入额外的索引机制需要额外的存储空间与处理机制。 1 3 本文所作工作 本文针对x m l 数据流的特点，在总结目前x m l 数据流x p a t h 查询处理方法的基础上，针对很多应用数据环境不确定的状况，提出 一种新的查询模型g b r e n d e r ( g r o u p b a s e dr e n d e r i n go f ld a t a s 仃e 锄x p a t hq u e r ym o d e l ) ，即基于组着色的x m l 数据流x p a t h 查 询模型，以及适应该模型的一种谓词处理模型，主要工作如下： 1 、系统研究x m l 数据流x p a t h 查询算法和许多应用环境不确 定性对数据流处理的要求，提出了一种新的查询模型g b r e n d e r ：基 于组着色的x m l 数据流x p a t h 查询模型。给出了组着色的概念、相 关定义以及该模型的结构特征和处理模型。 2 、提出了一种x p a t h 谓词处理的主动计算模型，在对谓词表达 式特点深入分析的基础上，给出的主动计算模型的基本思想，模型结 构及处理算法。该模型力求数据缓存的最小化，实验证明该模型能有 效的提高谓词计算的效率。 3 、给出了基于组着色查询模型对单枝查询的处理算法以及应用 主动计算模型进行复杂谓词处理的过程。 4 、实验结果表明主动计算模型能高效地处理x p a t h 谓词表达式。 m l 数据流p a f h 查询模型研究 1 4 本文的组织框架 本文共分六章。 第一章绪论，介绍了研究的背景、意义、国内外研究现状、本 文所作工作和本文的组织框架。 第二章x m l 数据流与x p a t h 查询，介绍x m l 及x m l 数据流 的相关知识以及x p a t h 查询规范，分析了x p a t h 表达式中谓词处理对 查询效率的影响。 第三章x p a t h 查询处理模型，介绍了x m l 数据流x p a t h 查询处 理的常见方法及其存在的问题，主要讨论了基于自动机的x p a m 查询 处理模型，以及谓词处理技术与查询优化技术。 第四章g b r e n d e r 模型，本章与下一章是本文的重点，总结目前 x m l 数据流x p a t h 查询模型的特点，提出一种新的查询模型：基于 组着色的查询模型g b r e n d e r ，该模型具有较高的处理效率与较高的 适应性以及对环境的低依赖性。给出了该模型的初步应用及单枝查询 下的多x p a t h 查询算法，并通过实验，证明了该模型对x m l 任意数 据流查询的有效性及其适用性强的优点。 第五章谓词主动计算模型，本章与上一章是本文的重点，提出 了一种x m l 数据流x p a t l l 查询谓词主动计算的模型，给出了该模型 的基本思想、结构，给出了该模型下x p a t h 谓词处理的算法及表达式 处理机制，并通过实验，证明了该模型谓词处理的有效性以及对查询 效率的提高，给出基于组着色模型应用主动计算模型进行复杂谓词处 理的过程。 第六章总结与展望，总结全文，指出全文研究成果及后续工作。 最后是参考文献和致谢。 m l 数据流p a t h 查询模型研究 2 1x m l 2 x m l 数据流与x p a t h 查询 可扩展标识语言x m l ( e x t e n s i b l em 州( u pl a n g u a g e ) ，是1 9 8 6 年国际标准组织( i s 0 ) 公布的一个名为“标准通用标识语言”( s t a n d a r d g e n e r a l i z e dm a r l ( u pl a n g u a g e ，s g m l ) 的子集。它是由成立于1 9 9 4 年 1 0 月的w 3 c ( w o r l dw i d ew r e bc o n s o n i u m ) 所开发研制的。1 9 9 8 年2 月，w 3 c 正式公布了x m l 的r e c o m m e n d a t i o n l o 版语法标准。x m l 掌握了s g m l 的扩展性、文件自我描述特性以及强大的文件结构化 功能，但摒除了s g m l 过于庞大复杂以及不易普及化的缺点。x m l 和s g m l 一样，是一种“元语言”( m e t a - 1 a n g u a g e ) 。换言之，x m l 是一样用来定义其他语言的语法系统。这正是l 功能强大的主要 原因。 x m l 文件包括三部分：x m l 声明、处理指令( 可选) 、x m l 元 素。x m l 文档的一个基本要求是形式良好的( w e l l f o m e d ) ，构建一 个基本的x m l 文档需符合以下要求： 1 、一个l 文档中有且仅有一个根元素，其它所有的元素都 是它的子元素； 2 、起始标签和结束标签应当匹配； 3 、大小写应一致； 4 、元素应当正确嵌套，子元素应当完全包括在父辈元素中； 5 、属性必须包括在引号中且元素中的属性是不允许重复的； 以下是个简单的x m l 文档g o o d x m l ： 打印机 硕+ 学位论文 3 0 0 1o o 复印机 2 0 0 0 8 5 x m l 包含三个要素：d t d ( d o c u m e n t 聊ed e f i n i t i o n ，文档类型 定义) 或x m ls c h e m a ( x m l 模式) 、x s l ( e x t e n s i b l es t y l e s h e e t l a n g u a g e ，可扩展样式语言) 和x l i n k ( e x t e n s i b l el i n kl a j l g u a g e ，可 扩展链接语言) 。x s l 是用于规定l 文档呈现样式的语言，它使 得数据与其表现形式相互独立，而x l i n l 【将进一步扩展目前w 曲上 已有的简单链接。d t d 和x m l 模式规定了x m l 文件的逻辑结构， 定义了x m l 文件中的元素、元素的属性以及元素和元素属性之间的 关系，简要介绍如下： l 、d t d ( 文档类型定义) ：x m l 文档的模板。它定义了文档的 逻辑结构，规定了x m l 文档中所使用的元素、实体、元素的属性及 元素与实体之间的关系。它使得数据交流与共享得以正常进行，验证 了数据的有效性。d t d 可以是一个完全独立的文件，也可以在x m l 文件中直接设定。 2 、x m ls c h e n l a ( x m l 模式定义) ：一个基于x m l 语法的 s c h e m a 规范，用来定义x m l 文档的标记方式。x m ls c h e m a 与d t d 一样，也是对一类x m l 文档进行约束，确定其结构、元素、属性、 数据类型及x m l 文档中所使用的元素、实体、元素属性及元素与实 体之间的关系的约束。x m ls c h e i n a 首先由微软提出，已经被w 3 c 接受成为一个标准。与d t d 不同的是，x m ls c h e m a 文件使用x m l 语法，它的设计目的和d t d 相似，但在功能、扩展性方面超越了d t d 。 x m l 数据流p a f h 奄询模型研究 x m l 技术体系还包括很多相关的技术规范，比如上面提到的文 档模式技术、文档样式技术，还有文档查询技术、文档解析技术等其 它规范。如： ( 1 ) x s l ，t ( x m ls t y l e s h e e tl a n g u a g et r a n s f o m l a t i o n s ) ：一种转 换方式，把一种文档类型转换成另外的文档。比如，可以把一个x m l 文档转换成各种x m l 文档，也可以转换为t x t 、x h 砌、h t m l 等。 ( 2 ) x p a t h ：检索x m l 文档中数据的一种标准语言。允许过滤 x m l 文档，只返回感兴趣部分的内容。这是本文研究的主要技术。 2 2x m l 数据流 ，数据流是一个按照时间递增顺序排列的无穷序列，可以表示为： ，= 口1 ，口2 ，口。的形式，口。是时候刻t 出现的序列元素【1 6 】。数据流与一 般的数据的区别在于它的到达是快速的、无界的、时变的和不可预测 的，从而不可能将原始数据流中的数据完全存储。 很多情况下，x m l 是以数据流的形式传输和处理的。对x m l 流的处理有以下要求【17 】： ( 1 ) 每一个l 元素节点最多只能访问一次。 ( 2 ) 使用有很和最少的内存空间存储临时数据，处理算法具有 尽可能小的空间复杂度。 ( 3 ) 对每个节点的处理必须有很高的效率，以满足实时处理的 需要。 当x m l 以流的形式进行处理时，在逻辑上实际是以先序遍历的 形式对x m l 树中的结点进行访问，即x m l 流可以看作一系列连续 且有序的结点x o z l 组成的序列。x m l 流的处理过程就是对这些 序列结点的分析。 定义2 1 给定x m l 树l 对丁中结点进行先序遍历所得到的结 点序列为x m l 树的流表达【1 8 】。记作s 丁= ( x ox 1 ) ，五丁，基中， 序列粕x l 实际上就是x m l 流元素的访问顺序。 硕士学位论文 例1 如文档g o o d x n l l 其内容与对应的x m l 树如图2 1 ： 图2 1 删l 文件对厩的l 树 则s 丁= ( p j e 耽p 玎f ( 仓库) ，p 彪垅p 刀f ( 商品) ，p 彪优p ，z 改商品名称) ，纫c z ( 打 印机) ，p 彪所e 聆攻价格) ，厶髓f ( 3 0 0 ) ，p 彪聊绷f ( 数量) ，f 麟f ( 1 0 0 ) ，e j 绷e 胛f ( 商品) ， p 切骝刀z ( 商品名称) ，幽绒f ( 复印机) ，p 彪聊p ，z f ( 价格) ，f 纵z ( 2 0 0 0 ) ，e 厶嗍e ，z f ( 数 量) ，f 硎( 8 5 ) ) 2 2 1s a x 解析模型 常用的x m l 解析模型一般有两种：文档对象模型d o m 和基于 事件的s a x 。对时大量的、实时的x m l 数据流，我们通常采用基于 事件的s a x 模型。 s a x 解析器采用了基于事件的模型，它在解析x m l 文档的时候 可以触发一系列的事件，当发现给定的t a g 的时候，它可以激活一个 回调方法，告诉该方法制定了标签已经找到。s a x 对内在的要求通 常会比较低，因为它让开发人员自己来决定所要处理的t a g 。特别是 当开发人员只需要处理文档所包含的部分数据时，s a x 这种扩展能 力得到了更好的体现。分析能够立即开始，而不是等待所有的数据被 处理。 s a x 处理一般包括以下几步【4 6 】： m l 数据流p a t h 杏淘模型研究 ( 1 ) 创建事件处理程序。 ( 2 ) 创建s a x 解析器。 ( 3 ) 将事件处理程序分配给解析器。 ( 4 ) 对文档进行解析，将每个事件发送给处理程序。 s a x 的原理是使用内容处理程序来监控事件流。如下面的文档： t h ef i r s tr e c o r d k e c o t i 解析该文档时，s a x 内容处理程序将看到以下的事件流： s t a r t d o c u m e n t ( ) s t a n e l e n l e m ( r o o t ) c h a r a c t e r s ( w h i t e s p a c e ) s t a r t e l e m e n t ( i t e n l ) c h a r a c t e r s ( t h ef i r s tr e c o r d ) e n d e l e m e n t ( i t e m ) e n d e l e m e n t ( r e c o r d ) e n d e l e m e n t ( r o o t ) e n d d o c 姗n e n t ( ) 基中s t a n d o c u m e m ( ) ，s t 矾e 1 e m e n t ( ) ，c h a r a c t e r s ( ) ，e n d e l e m e n t ( ) ， e n d d o c u m e n t ( ) 等都是s a x 中最常用的事件。 2 3x p a t h x m l 查询是根据查询语法所表示的位置从x m l 文件中找出相 对应的数据，这种位置表示法称为路径表示法。路径表示法主要是用 于表示节点在x m l 树状结构上的位置，而x m l 查询正借由这种路 径表示法以运用于x m l 文件中。目前常见的x m l 查询语法有 硕+ 学位论文 q u i l t 【2 4 】、x m l q l 【2 5 1 、x q l 2 6 1 、x q u e u 【2 7 1 、x s u l 【2 8 1 及x p a t h 2 9 1 等， 所有查询语法皆以路径表示法为基础，其中若元素间关系为父子关系 则以“”表示，而祖孙关系以“”来表示，而“ 】”表示为分支路 径，若其中包含“ ”则表示为具有属性的元素。 x p a m 是制定x m l 技术规范标准的w 3 c 推出的x m l 文档寻址 语言，在1 9 9 9 年1 1 月x p a m l o 就已成为w 3 c 的推荐标准，目前已 经推出了x p a t h 2 o 的工作草案。x p a t h 的出现给x m l 文档的查询提 供了规范。x p a t h 中的基本语法单元是和传统计算机文件系统路径相 似的路径位置表达( l o c a t i o np a m