（计算机应用技术专业论文）xml数据库查询及其模式集成研究.pdf

摘要 在网络日益普及的今天，绝大多数w e b 数据仍是以h t m l 文件的方式存储而非数据库方式，由此产生的问题之一是：w e b 数据无结构，因而无法通过基于结构的精确查询而得到。x m l 理 论及其相关技术正是在这样一种背景下诞生，它为w e b 数据的表 示和结构化提供了理论和技术上的支持。论文基于这一背景，对 x m l 数据的抽象、查询、集成和优化等方面进行了理论和实验探 讨，主要研究工作和贡献如下： ( 1 ) 本文仿照关系型数据库( r d b ) 建立了x m l 数据系统的三 层模型：概念层、离散模型层和物理存储层( 查询视图集、离散模 式集和对象集1 ，以x m l 格式文档具有一定的模式这一事实为出 发点，提出了x m l 文档集合的离散模式概念，从而建立了在离 散模式集上的x m l 文档对象集合( x m l 数据库) 。这一x m l 数 据库是基于离散x m l 模式的，是一个基于离散模式的x m l 数据 库系统( d i s x d b s ) 。本文的研究工作就是以许多新的思想和方法 来完成和完善上述系统的各部分功能而展开的。 ( 2 ) 在定义了相应的逻辑语言后，给出了x m l 文档树模型 的形式化表示，并基于这一数学模式研究了一般查询、树查询和 结构型查询，并用逻辑表达式集成了查询结果。这一工作从理论 上证明了x m l 文档结构的可形式化，为基于这一模型的图扩展 提供了依据。 ( 3 ) 基于上述x m l 文档结构的抽象和完善x m l 结构的表 示，本文提出了图模式的x m l 数据组织方案，并进行了x m l 环 境下的基于图匹配的数据查询研究，给出了形式化程度较好的查 询表示和查询方法。由于某一离散模式代表整个x m l 数据库的 一部分，基于这一模式概念与x m l 数据库的数据抽象一扩展的 o e m 图模型，本文将查询实现表示为模式子图在x m l 数据库图 中的匹配或同态。通过引入c s p 变换及求解，完成了图匹配查询 和优化的具体实现，给出了一套从离散模式到x m l 数据库的图 匹配转化为c s p 问题的具体方法，并对其求解方法进行了研究和 实现，从而完成了对具体x m l 数据库的查询。本文还将这一思 想和技术用于对查询进行优化。 ( 4 ) 为了统一离散模式并使其遵守w 3 c 规范，本文对x m l 模式进行了扩展，这一扩展不仅形式化程度高而且引入了x m l 代数和自动机的概念，并证明了这一代数是布尔代数。实现了一 个能对x m l 代数所约束的x m l 文档进行分析的分析器，从而实 现了离散模式的集成，为统一表示x m l 文档的模式奠定了理论 基础。 ( 5 ) 定义了具有x m l 特色的蕴含关系，并将其运用于查询 的优化。在查询优化方面，本文还作了一些r d b 与x m l 数据查 询优化方法比较的理论探索。其意义在于：从理论上证明了 x m l 查询优化与r d b 查询优化的差异，因而也说明了本文基于 x m l 的查询优化方法的合理性。本文还从物理层出发，以提高查 询效率为目的，对如何存储x m l 数据进行了理论和实验研究。 最后，本文对基于离散模式的x m l 数据查询和集成的工作 进行了总结并对今后的工作进行了规划和展望。 关键词x m l 模式，数据库，x m l 代数，匹配，c s p 问题 i i a b s t r a c t i nc u r r e n ti n t e r n e te r a ，o v e r w h e l m i n gm a j o r i t yo fw e bd a t ai s s t i l ls t o r e di nh t m lf o r m a ti n s t e a do fd a t a b a s e t h ep r o b l e mw i t h t h a ti st h a tt h ew e bd a t ah a v en os t r u c t u r ea n dh e n c eu s e r sa r en o t a b l et oh a v ea c c e s st ow e bd a t av i ap r e c i s e l yq u e r y i n gt h e m x m l t h e o r i e sa n d t e c h n o l o g i e s a r e s u r g i n ga g a i n s t t h es i t u a t i o n m e n t i o n e da b o v e t h e yp r o v i d et h e o r e t i c a la n dt e c h n i c a ls u p p o r t f o r r e p r e s e n t i n g a n d s t r u c t u r i n g w e bd a t a b a s e do nw h a t m e n t i o n e da b o v e ，t h ed i s s e r t a t i o nd o e ss o m e t h e o r e t i c a la n d e x p e r i m e n t a l r e s e a r c ho na b s t r a c t i n g ，q u e r y i n g ，i n t e g r a t i n ga n d o p t i m i z i n gx m l d a t a f i r s t w eh a v ee s t a b l i s h e dan o t i o no ft h r e e l a y e rm o d e l t h r o u g hi m i t a t i n gt h ep r o c e s so fc o n s t r u c t i n gr e l a t i o n a ld a t a b a s e ， w h i c hi sc o n c e p t u a l ，d i s c r e t es c h e m aa n dp h y s i c a ll a y e r b a s e do n t h ef a c t t h a tx m lf i l eh a ss c h e m at o ac e r t a i n d e g r e e ，t h e d i s s e r t a t i o np u t sf o r w a r dt h ec o n c e p to fd i s c r e t es c h e m aa n dh e n c e x m lo b j e c ts e t i e x m ld a t a b a s e ，i sb u i l tb a s e do nd i s c r e t e s c h e m a t h ed i f f e r e n c eb e t w e e nt h et h r e e l a y e rx m lm o d e la n d r e l a t i o n a lm o d e li st h a tt h ec o r r e s p o n d i n gx m l d a t a b a s ei sb a s e d o nd i s c r e t es c h e m a t h e r e f o r e i ti s ad i s c r e t es c h e m ax m l d a t a b a s es y s t e m - - d i s x d b s o u rr e s e a r c hw o r ki s t os o l v e v a r i o u sp r o b l e m sa r o u n dt h es y s t e m b yu s i n gn e wi d e a sa n d m e t h o d s s e c o n d l y ，a f t e rd e f i n i n gal o g i cl a n g u a g e ，t h ed i s s e r t a t i o n p r e s e n t st h ef o r m u l a i cr e p r e s e n t a t i o no fx m lt r e em o d e l ，d o e s r e s e a r c ho ng e n e r i c ，t r e ea n ds t r u c t u r a l q u e r y b a s e do nt h e m a t h e m a t i c a ls c h e m aa n dr e p r e s e n t st h ei n t e g r a t i n gq u e r yr e s u l t s t h r o u g hu s i n gl o g i ce x p r e s s i o n s t h er e s e a r c ha b o v eh a sp r o v e d t h a tx m ls t r u c t u r ec a nb ef o r m u l a t e da n dp r o v i d e sf o u n d a t i o nf o r g r a p he x t e n s i o no ft h et r e em o d e l t h i r d l y b a s e do nt h ea b s t r a c to fx m ls t r u c t u r em e n t i o n e d a b o v ea n di no r d e rt oi m p r o v er e p r e s e n t a t i o no ft h ex m ls t r u c t u r e ， t h ed i s s e r t a t i o np r o p o s e sa na p p r o a c ho fo r g a n i z i n gx m ld a t a t h r o u g hg r a p hs c h e m a ，d o e sr e s e a r c ho nq u e r yi nx m l c o n t e x tb y u s i n gg r a p hm a t c h i n ga n do f f e r sr e d r e s e n t a t i o n sa n dm e t h o d so f h i g hf o r m a l i t yf o rq u e r y s i n c e w eu s ead i s c r e t es c h e m at o i i i r e p r e s e n t a p a r t o fx m ld a t a b a s e ，t h ed i s s e r t a t i o n r e p r e s e n t s i m p l e m e n t a t i o no fq u e r ya sm a t c h i n go rh o m o m o r p h i s mo fs c h e m a s u b g r a p hi nx m ld a t a b a s eb a s e do nt h em e n t i o n e dn o t i o no ft h e s c h e m aa n da b s t r a c to fx m ld a t a b a s ef e x t e n s i b l eo e m m o d e l ) i t c o m p l e t e sg r a p hm a t c h i n gq u e r ya n di m p l e m e n t a t i o no fq u e r y o p t i m i z a t i o nv i au s i n gc s pt r a n s f o r m a t i o na n de n s u i n gs o l u t i o n ， w h i c hp r o v i d e sad e t a i l e dm e t h o do ft r a n s f o r m i n gd i s c r e t es c h e m a i n t oc s pa n dr e s e a r c h e sa n di m p l e m e n to nh o wt os o l v ec s p t h u s ，t h eq u e r yi nt h es e n s eo fc o n c r e t ex m ld a t a b a s ec a nb e c o m p l e t e d m o r e o v e r ，t h e n o t i o na n dm e t h o da r eu s e dt o o p t i m i z i n gq u e r y f o u r t h l y ，i no r d e rt oi n t e g r a t ed i s c r e t es c h e m aa n df o l l o wt h e w 3 cs p e c i f i c a t i o n ，t h ed i s s e r t a t i o ne x t e n d sx m ls c h e m a t h e e x t e n d e ds c h e m ah a sn o to n l y h i g h d e g r e e o fm a t h e m a t i c a l r e d r e s e n t a t i o na n d 。a l s ob r i n g si nn o t i o n o fx m la l g e b r aa n d a u t o m a t o n a n dt h ea l g e b r ah a sb e e np r o v e db e i n gab o o l e a n a l g e b r a ap a r s e rw h i c hc a np a r s ex m l d o c u m e n t sc o n s t r a i n e db y t h ex m la l g e b r ai s d e v e l o p e d t h u s ，t h ei d e ao fi n t e g r a t i n g d i s c r e t es c h e m ah a sb e e nr e a l i z e d t h em o s ts i g n i f i c a n c eo ft h e a c h i e v e m e n ti st oh a v e p u t at h e o r e t i c a lb a s i sf o r i n t e g r a t i n g r e d r e s e n t a t i o no fx m ld o c u m e n t s f i f t h l y ，t h ec o n t a i n m e n tw i t hx m lf e a t u r e sh a sb e e nd e f i n e d a n db e e nu s e di no p t i m i z i n gq u e r y t h ed i s s e r t a t i o nh a sd o n es o m e o t h e rt h e o r e t i c a le x p l o r a t i o nb e n e f i c i a lt oo p t i m i z i n gq u e r y t h e s i g n i f i c a n c e i s t h a tt h ee x i s t e n c eo fd i f f e r e n c eb e t w e e n o p t i m i z a t i o n o fx m lq u e r ya n dt h a to fr d b q u e r y h a s t h e o r e t i c a l l yp r o v e d t h e r e f o r e ，i tj u s t i f i e st h em e t h o du s e dh e r ei s r e a s o n a b l e t h ed i s s e r t a t i o nh a sa l s od o n et h e o r e t i c a la n d e x p e r i m e n t a lr e s e a r c ho nh o wt op h y s i c a l l ys t o r ex m ld a t ai n o r d e rt oo p t i m i z eq u e r y f i n a l l y ，t h es u m m a r yo ft h er e s e a r c ho nx m ld a t a b a s eq u e r y a n dx m ls c h e m ai n t e g r a t i o nh a sb e e nm a d ei nt h ed i s s e r t a t i o n a l s o ，t h ep l a na n dt h ee x p e c t a t i o no fo u rf u t u r ew o r kh a v eb e e n m a d eh e r e k e y w o r d sx m ls c h e m a ，d a t a b a s e ，x m la l g e b r a ，m a t c h ，c s p i v 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均已在在论文中作了明确的说明。 作者签名：i 五查叠日期：坦绰鱼月旦日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部 或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据 国家或湖南省有关部门规定送交学位论文。 作者签名： ：皇! 盥导师签名毖丛旦期：地= l 贮唐王日 博士学位论文第一章绪论 第一章绪论 w e b 数据管理中的数据组织是研究w e b 信息的特点、找出适合w e b 信息的合理 组织模式，近年来，有相当部分的研究集中在半结构化数据模式方面，w e b 上的 数据模式的获得及其集成是w e b 数据管理的最需要解决和难以解决的现实问题。 x m l 技术规范的提出使其逐步成为新一代w e b 数据组织和交换的事实标准 1 】， 越来越多的x m l 数据出现在w e b 上。实质上，x m l 为w 曲的数据管理提供了全新 的数据模型，将w e b 变成一个真正的数据库是这一领域工作的终极目标，x m l 是朝 这个方向迈出的有希望的一步。这一方向的研究也为数据库研究带来新的机遇和挑 战，使得将数据库技术和研究扩展到w e b 数据的管理成为可能。 1 1 研究背景及意义 回顾历史，可以看到，随着计算机参与数据的管理，数据库管理系统o b m s ) 成 为了完成这种管理的最重要的工具，它业已在当今计算机数据管理中得到广泛应用， 而d b m s 的最主要优点是它提供对于数据的集中控制回。更确切地说，d b m s 的作用 及优越性有以下几个方面： f 1 ) 具有数据独立性； ( 2 ) 共享； ( 3 ) 冗余度小； ( 4 ) 避免了数据的不一致性； 可以实施安全| 生保护： 固有利于实旌标准化 目前，最广泛应用着的d b m s 是关系型的，它之所以被广泛应用是基于下述几 点：首先，它具有坚固的数学基础，即，关系模式及其理论1 3 1 ；第二，它具有描述性 的存取方法且对数据的存取是基于结构而非基于内容；最后，它具有相当完备的查询 处理及其优化手段。 由于关系模式是需要预先设计的，因此，仅有针对这一预先设计的结构的查询对 用户才是有效的。显然，对于当今的网络数据来说这是一个挑战。随着半结构化数据 作为数据研究领域中一个重要研究方向的出现【4 ，目，它吸引了越来越多的注意力。原 因之一是基于w e b 数据的应用e t 益广泛。在目前的应用中，对于w e b 数据的查询是 基于内容的，效率之低己成为制约w e b 应用的瓶颈之一，将w e b 数据视为传统数据 博士学位论文第一章绪论 库数据是可能的方向，然而，以h t m l 为主的w e b 数据是没有结构的，因此，对于 将w e b 数据转化为具有结构或半结构的研究成为了热点，许多新的数据模式被提 出，其中，x m l 是极富发展前景的一种，附录l 中给出了x m l 文档的例子。 1 1 1 半结构化数据 半结构化数据是介于严格结构化的数据和完全无结构的数据之间的数据形式， 前者的例子有关系型数据库中的数据，后者有声音、图形和图像文件等。半结构化形 式的数据具有以下一些特点： ( 1 ) 隐含的模式信息 ( 2 ) 不规则的结构 0 ) 没有严格的类型约束 关于半结构化数据的研究主要集中在新的数据模型、查询模式、存储技术以及优 化技术等方面1 6 , i 目。其中，对半结构化数据的模式和查询方面的研究是一个非常重要 的方向。半结构化数据存在一定的结构，但这些结构或者没有被清晰地描述，或者是 经常动态变化的，或者过于复杂而不能被传统的模式定义来表现。半结构化数据的模 式与传统的关系或面向对象数据的模式不同，主要有如下一些特点： ( 1 ) 半结构化数据是先有数据，后有模式： ( 2 ) 半结构化数据的模式是用于描述数据的结构信息，而不是对数据结构进行 强制性的约束； ( 3 ) 半结构数据的模式是非精确的，它可能只描述数据的一部分结构，也可能 根据数据处理的不同阶段的视角而不同； ( 4 ) 半结构化数据的模式可能规模很大，甚至超过源数据的规模，而且会由于 数据的不断更新而处于动态的变化过程中。 对于半结构化数据的模式，目前已经提出了多种描述形式，比较有代表生的有基 于逻辑的形式和基于图的形式。无论是哪种描述形式，其讨论的基础都是采用带标记 的有向图作为半结构化数据模型，最典型的就是o e m 模型1 9 1 。 ( 1 ) 基于逻辑的描述形式 在已经提出的半结构化数据模式的描述形式中，基于逻辑的描述形式是重要的一 类，如一阶逻辑、描述逻辑以及n 删0 9 等罔。它们非常类似，但在表达能力等方 面有所差别，这方面比较典型的是基于d a l a l o g 的描述形式。 2 博士学位论文第一章绪论 ( 2 ) 基于图的描述形式 半结构化数据模式的另一种重要描述形式是基于图的形式，这种描述形式的一个 显著特点是模式和数据采用同一种数据模型，即，图模型，这给处理带来了很大的方 便，模式图通常是一个边上带标记的有向图，其边上的标记可以与数据图相同，也可 以加以扩充。本文所提出的用于查询的模式就是源于此类模式。 1 1 2 对象交换模型0 酬 o e m 模型是在为t f i m m i s 数据集成计划中被首次提出的脚，它是一个基于图的、 白描述的对象实例模型，被广泛用于表示半结构化数据。其中，数据由对象的集合来 表示，对象可以是原子的或复合的，其中，原子对象的值是一些基本类型，如：整 数、串等等；复合对象是( 属性，原子对象) 对的集合，这里，属性可以是任何串类 犁。 以o e m 表示的数据体是一个图，其中，结点是对象，边以属性名标记，叶结点 都有一相应的值与之关联，图中有被称为根的结点，所有其它的结点可以从根开始 存取。一般来说，半结构化数据形式化地表示为g = ( y ，e ，v ) ，其中，结点集合v 被划分为原子结点集合和复合结点集合，即，v = vu矿；边表示为o e a v ，其中，a 是屙性名全集：re v 为根；v 为从圪到d 的映射，即， 为各原子对象分配值，其中，d 是原子值的全集。如图所示为一个附录2 中书目文档 以o e m 表示的数据的例子，其中，& 0 1 2 、& 0 4 3 等都是对象标识。 图1 10 尉图例 依据规范，o e m 中的每一个对象具有下述结构： 其中，l a b e l 是具有变量长度的字符串对象描述符；t y p e 是对象值的数据类型描述 符，可以是诸如整数、实数和字符串等原子类型，也可以是集合类型。可取的原子类 3 博十学位论文第一章绪论 型可以根据信息来源的不同而不同；v a l u e 是对象的变量值；o b j e c t - i d 是对象的唯一 标识符。基于逻辑的形式表示o b j e c t - 皿只需用三元组( l a b e l ，t y p e ，v a l u e ) ，基于图的 表示则如上图所示，本文的方法是根据应用时的不同需要将二者混合使用。 1 1 3 瑚数据抽象、查询和组织的历史与现状 可扩展标记语言x m l ( e x t e n d e dm a r k 叩l a n g u a g e ) ”q 的出现改变了w e b 的基本面 貌。与h t m l 相比，x m l 具有许多优点： r 1 ) x m l 简单，自我描述而易于解析。使得x m l 具有机器可读性，一个应用可 以按照各种方式解析、过滤、重构x m l 文档； h t m l 中的标记是固定的，不能扩展，而x m l 的标记由用户定义，可以任 意地扩展。x m l 的嵌套结构可以表示现实世界中各种复杂的对象，各种格 式的数据都可转化为x m l 数据，使得x m l 非常适于w e b 信息发布和集 成； 0 ) h t m l 中的标记表示的是数据的显示格式，没有任何含义，而x m l 文档中 的标记则明确指出了数据的含义，使得细粒度的x m l 数据处理成为可能； ( 4 1x m l 实现了内容、结构和表现三者的分离。文档类型定y ( d t d ) 描述了文档 中元素和子元素间的嵌套结构，而不同的用户可以通过x s l 按不同显示方 式显示全部或部分的文档内容。 x m l 自发布以来就受到了各界的广泛关注。各计算机厂商们竞相推出了支持 x m l 的产品( 如：o r a c l e9 i 中的x m ls q lu t i l i t y ，md b 2 中的x m le x 删e r ， m i c r o s o f ts q ls e r v e r2 0 0 0 中的x m la n di n t e m e ts u p p o r t 等) ；学术和研究机构纷纷采用 x m l 来表示各种科学数据并正在对x m l 开展深入的研究；工业界和商业界则忙于定 制适于各行业应用的d t d 规范。目前，i n t e m e t 上已经涌现了大量的x m l 页面、站 点和应用开发工具。可以预见，仉将成为w e b 信息发布和交换的事实上的标准。 x m l 在电子信息发布、电子商务( e d i 交换) 、数字图书馆、w e b 信息搜索和集成等领 域具有广阔的应用前景。 由于关系型数据库o b ) 在理论与实践中的极大成功，人们对x m l 技术的研究 基本上是以关系型数据库为范例进行的，例如：模式、查询语言、约束及类型检查概 念的对应。也许，审视x m l 应有全新的视角，包括x m l 数据库、模式这样一些基 本概念本身和正确性是否应该以关系型数据库为标准去衡量等问题都应成为研究的对 象。 4 博十学位论文第一章绪论 然而，x m l 与传统数据库中的结构化数据不同，x m l 数据是自描述的，没有传 统数据库意义的模式。人们通常将x m l 看作是半结构化数据的标准，并借鉴半结构 化数据的研究成果来管理x m l 数据。目前，数据库界在半结构化数据的研究在数据 模型、查询语言、查询优化、索引技术、半结构化路径约束、半结构化中间件和视图 机制、半结构化模式抽取、w e b 站点管理等方面己取得了一定的进展【1 1 2 1 。但是，目 前的半结构化数据的研究尚不成熟，而x m l 与半结构化数据相比又有一些差别，这 主要表现在：从数据特点上看，x m l 文档中的元素有次序，x m l 可带有描述文档结 构的d t d 或x v l ls c h e m a ；从应用领域来说，x m l 不但被用于表示w 曲数据，也面 向电子数据交换。因此，需要对仉数据进一步作深入的研究。自x m l 标准发布 以来，沮。已经引起了数据库研究者们极大的兴趣，成为近年来的s i g m o d 、 v l d b 、i c d e 和p o d s 等数据库的顶级会议的研究热点。 表1 1x m l 数据管理的研究项目 项目名称研究机构或院校研究重点眦 n i a g a r a w k s c m 血m a d i s o n 大 x m l 的查询和搜i 脚p 小删c s - w i s c 丘h 两a 掣吲 学索引擎 o r i e n t x 中国人民大学原生x m l 数据库h 拄p 渐血“曲l m 蜘a 由 m i i ( 、啊l a w 斟t r 咖】大学 基于x i v l l 的数据p d a 衄c & 曲打培吼e d 曲d 州 集成 x 趣la t & t 实验室，x m l 查询语言 t 印小w w 删e s 朗叫j l 上札c o m 氢怕o n r i a n 和w a s h i n g t o n i s m “q l 大学 x m i l l p e n n s y l v a n i a 大学 x m l 数据压缩h 曲p j d b c 畦呷目n e d 非苍朗r 吐a a t & t 实验室 m i l l j l l m l x p 口u n l d w 甜1 吨啪大学， x m l 信息发布h c p 小i a 血阻w 笛1 1 m 曲吼e d m w m m 公司 s a l 】妊蚋x 舡腑d p e n n 掣i v a n i a 大学x m l 的查询语i 印烛凼邺l 劬】艉啪s s d a 扭儿 言、结构描述、约 - x m l j - m r n l 束机制和类型系统 c a i 孙d 法国i n r i ax v l l 数据的查询 h 印出w w r o ( j j r l a 翩k 嘲一j 1 和存储技术 乜1 咀 l o l e s l a n f o r d 大学 x m l 数据库管理 却：* w v c h s 白瓶谢捌 系统 x i v l l - b a s e d 德国国家信息技术研吼标准和x m l i 婶删吐毗吼甜瞎m d 蛐v f f i f d i l i 谢o n 究中心( g m d )结构、x m l 文档 s y s t e m s 存储和查询、x m l 的电子商务应用 t 耵l i 美国s o f t w a r e a g 公原生x m l 数据库h 廿【p 小s o f h 硼r e 氅忉恼m i 司系统 虽然有一些研究工作集中在将x m l 数据转换为关系型数据方面，而且，这一工 作在某些庸况下也有实际意义，例如，它可将相当完善的关系型数据库技术应用于 x m l 数据，o r a c l e 科切和文章【1 4 】所述都是这一方面的典型工作。因此，我们的应用 5 博士学位论文第一章绪论 研究也有一部分是在这一方面。由于x m l 文档是基于图模式的半结构化数据，在许 多情形下，利用关系型数据管理系统管理x m l 数据可能带来非常高的存储代价和查 询代价。因此，许多的工作都集中在为x m l 寻求模式代数和查询代数，以便能用一 种独立的技术来处理x m l 数据，而其方便及完善的程度就如同关系型数据库技术。 国内外已经完成和正在开展的x m l 数据管理的某些研究项目如表1 1 所示。 下面分别介绍x m l 的抽象和查询方面研究现状以及x m l 的w e b 应用现状和 x m l 和传统数据库的思想方法异同点。 ( 1 ) 1 模式语言代数 虽然x m l 没有像r 工) b 那样严格的结构，但还是有模式的概念，例如d m 、 x m b s c 礤1 1 af os o x 等，x m l 模式比r 工) b 模式更宽松、灵活，作为种半结构化数 据的实例，无一例外地，他们仍选择了o e m 的变种作为他们工作的数据模型。一旦 模式确定，还是有静态类型错误被查出的余地，也可能进行基于类型的优化，如：忽 略掉不感兴趣的图的部分，或进行基于输入数据的结构知识的重写优化等操作。 到目前为止，已有多种x m l 模式语言被提出，下面几种是较有可能成为实际应 用的候选者，原因是：它们均由一些有实力的公司支持，因此，生存机会较大。这些 模式语言是：) a 皿册【1 一，s d 懈m 【1 sl q 、r a ) ( 【研、s o 、s d 踯出踟【1 9 和 d s d 网。其中，皿a t d 和黜h e m a 由w 3 c 推荐，硪l a x 由日本标准化协会 推荐、d s d 由a t & t 推荐。较为典型和通用的x m l 模式语言的例子有皿伽和 h e m a 。经过分析，不难看出：上述各类模式的基本缺陷是：并没有给出真正 数学意义上的语法，因而，不能给出可计算的描述对象。下例给出了一个x m l 文档 及相应的d t d 描述与灿s c h e m a 。稍微对下面的d 田和皿一s d 黜1 a 作些比较不 难看出，啪采用了非x m l 的语法规则、不支持数据类型，反之，仉- s d 硝m 正 好解决了这些问题，更进一步的比较请参阅文献 1 1 ，1 2 】。 岱n j d e n p a g p 2 1 6 博士学位论文第一章绪论 s m i t h 2 3 ) 眦，文档 ! e l e m e n t n a m e ( f f p c d a t a p d r r d 描述 h e n a e n t t y p e n a m e = n a m e b h l a n e n t t y p en a m e = ”a g e ”蚋隹t i x e d 1 4 4 修 e l e m e r a t y p e = ”a g e 房 e l e m e n t t y l 痧 e l e m e n t t y p e = s t u d e n t 今 a t t r i b u t e 乜叼f ”g r a d e 修 ) m ，s c h e m a 描述 按不同的表现力，模式语言大致可被分为如下三类： ( a ) d t d 是x m l 最基本的模式语言，是最基本的模式抽象，由于它缺少数据类 型和约束定义，因而，相对于其它模式语言，d t d 表现力较弱，d t d 能直 接转换成其它语言，反之则要失去一些表现力： 7 博士学位论文第一章绪论 脚a x 和s o x 属于这一类，它们可被认为是对第一类模式语言的有限扩 展，即：能充分支持基本的模式抽象和部分数据类型； ( c ) 皿s c b m 、s c h 邸斑踟和d s d 属于这类，它们对第一类模式语言的扩 展又进了一步，因而，表现力最为丰富。例如：黜h e a v , a 就能充分支持 模式的数据类型定义。其中，) m ，s d h m 的形式化描述为，s c i h m 构 建了一个数学模型【2 l j 。 1 查询语言代数 众所周知，关系型数据库有一套非常完备的查询语言，查询被定义为可计算的、 一般的和完备的从关系数据库到关系的映射，这里完备的意思是指：如果查询语言能 够表达所有的查询，则此查询语言是完备的。关系代数是一个关系型数据库查询表达 式是否完善的标准。在w 曲情况下，上述基础中的大部分被动摇了，首先，被查询 的对象常常是一个移动的目标，因此，查询常常是一个没有严格定义的输入，也没有 一个很好的尺度来衡量查询表达式，各种查询表达式几乎很难有共同的抽象特征：其 次，关系型数据库最有意义的、显著的特点是数据的独立性，即：数据的逻辑层与物 理层的分离，它的意义在于：查询是通用的、一般化的，查询结果仅依赖于数据的逻 辑层，更严格地表述是：查询是输入的同构变换。在w 曲上，逻辑层与物理层是很 难分清的，u r l 是逻辑层吗? 或者说它是物理层吗? 查询肯定不会也不应该同等对 待它们，w e b 页上显示的内容表达了逻辑信息还是纯的物理信息? w 出沁的地理位 置又如何呢? 没有一个一劳永逸的、清晰的答案巴捌。容易推论出：查询的一般化也 是不健壮的和有意义的。 仿照关系数据库的查询代数，许多人试图为x m l 查询建立查询代数，从而能像 关系数据库s q l 一样有一个完备的数学背景，为查询优化、数据库一致性等高级应 用提供基础。例如：c b e e f i 和v 饧b a n 从处理嵌套查询的代数出发，在x m l 条件下 扩充这一代数，用它来处理一般路径表达式( g d 删p a t hb p r i 髑i o n ，g p e ) ，他们提出了 x m l 的面向用户的查询语言代数s a i 脚。用i ( 1 。e 1 1 e 表达式表示的s a l 的数据模式如 下： x m l v a l u e 1 x m l z a b e l ，x m l n o d e x m l n o d e ：= a t o m i c v a l u el x m l l a b e l - d e f i n e di nx m ls p e c i f i c a t i o n a t o m i c v a l u e ：= d e f i n e di nx m ls p e c i f i c a t i o n 基于此模式，s a l 定义了一系列的操作：选择( 一) 、映射( x ) 、表映射( xz ) 、连接 ( j 7 ) 、分组( ，1 ) 、k l e e n e 式匹配( p ) 和变量绑定( w a i n d ) 等，例如：仃j i f 8 博士学位论文第一章绪论 p r e d ? f 寸b ，t h e n 盯( p r e c t ) 一 ，w h e r e 盯俨r e 矽口兰 其中p r e d 为谓词，r 为x m l v a l u e s 类型，为x m l n o d e s ，p 为x m l v a l u e s 的值，显然， 它即体现了r d b 同类概念又考虑了x m l 的特点。实际上，这套代数是他们o o d b 代数上的拓展和综合，但其作用实际上只局限于一个x m l 数据子集。详细内容参阅 文献e 翔，文献 2 5 7 也提供这方面工作的启示。 到目前为止，已有多种查询语言被提出，下面几种是由一些有实力的公司支持的 查询语言：l o r e l l 蚓、x m l q l l 2 7 1 、x m l - g l 田 、x s u 御、x q l 凹 、x q u e n j 3 1 1 。l o r e l 被 提到，是因为l o r e l 被认为是半结构化数据家族的合适的代表，而x m l 是半结构化 数据的一种具体形式。事实上，l o m l 的x m l 形式也已在应用中网。按不同的表现力 和表现方式，查询语言也可被分为如下三类： ( a ) x q l 和x m l - q l 属于基本的x m l 查询语言的代表。它们起的作用类似于 关系型数据库的s q l 的内核在关系型数据库世界的作用，它们的表达能力 被包含在x s l t 中； 例如：x m l - g l ，图形界面的x m l 查询语言，起源于r d b 中图形查询界 面，它犹如q b e 在r d b 世界中起的作用； ( c ) 例如：) q u 唧、l o r e l 和x s l t ，它们同高级s q l ( o hs q l 2 ) 的作用类似， 但是，他们之间仍有区别，例如，l o r d 是完全描述性的，) 圆l t 实际上是一 种过程| 生的样式表语言，而x q u e r y 是描述性与过程性的混合体。 ( 3 ) ) 弧的w e b 数据管理应用 虽然w e b 信息管理的最终目标是建立一个巨大的、有统一模式的和支持对w e b 上的多个数据源的查询数据库系统，但是，目前已有的w e b 信息系统都还只是向这 一目标努力的阶段成果，比较典型的系统有：x w r a i ：j 3 3 1 、w 4 f 口4 1 、q u i l t t 3 啼y a i 嗣 等，典型的建设w e b 信息集成系统的方法是：数据仓库方法和虚拟方法。前者是将 各数据源的数据通信装载到数据仓库中，用户的查询基于数据仓库的数据：后一种方 法基于一个“中间模式”，数据仍保存在局部数据源中，通过各种数据源的“包装程 序”，数据虚拟成中间模式，用户的查询基于中间模式，不必知道每个专门的数据源 的特点，查询执行引擎直接与包装程序打交道，将基于中间模式的查询转换为基于各 局部数据源的模式。虚拟方法更适应于数据源数目多、各局部数据源的自治陛很高且 局部数据经常变化的w e b 环境。下面对几个应用系统做些简介。 x w r a p 是一个使能删l e a ) 的w e b 信息源包装建构的系统。所谓使 能x m l 是指隐含在源w e b 页中关于信息内容的元数据将被抽取出来，并转换为包装 9 博士学位论文第一章绪论 文档中的x m l 标记