（计算机软件与理论专业论文）xml数据访问技术的研究.pdf

摘要 摘要 x i v l l ( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展的标记语言) 是w 3 e ( 万维网 联盟) 于1 9 9 8 年2 月推出的一种标记语言。与h t m l 类似x m l 也是通用标记 语言s g m l 的子集，但x m l 是面向内容的而不是面向显示格式的。x m l 推出 后很快就被普遍接受，成为在w e bj ：表示和交换数据的新的标准。x m l 数据的 杳询和篱理是目前研究和开发的一个热点，多种查询语言方案和查询原型系统相 继推出，主要的商业数据库系统如o r a c l e 、d b 2 和s q ls e r v e r 等也开始支持对 x m l 数据的访问。按照所采用的数据模型的不同可以将目前的研究或实现方案 大致分为三种类型：1 ) 采用半结构化的数据模型的方案；2 ) 采用关系模型的方 案；3 ) 采用对象模型的方案。本文对采用o o d b ( 面向对象的数据库) 的数据 模型( o m ) 和语言( o q l ) 查询x v l l 数据的方法进行了研究，主要基于以下 考虑：1 ) 对象模型支持复杂数据类型，能够很自然地将x m l 数据映射到对象 模型；2 ) 面向对象的方法己普遍应用于软件开发的各个阶段，采用o o d b 的模 型便于将x m l 数据的处理和应用系统的其他部分无缝地结合。3 ) o o d b 克服 了r d b 所固有的一些局限性，可以预期o o d b 会不断发展，同时越来越多的数 据将采用v 几格式表示和交换，以一致的方法访问0 0 d b 和x m l 数据无疑会 极大地简化应用系统的开发。本文的主要研究内容和创新包括： l 提出了x m l 数据的结构化处理方法。根据x m l 数据的特点，本文对 o d m g 的对象模型作了适当的扩展，在此基础上给出了将x m l 数据映射到对象 模型的规则。对x m l 数据的代数操作和基于o q l 的x m l 数据的查询语言进行 了研究，提出了对o q l 进行扩展的方法，以便于查询半结构的、有次序的x m l 数据。 2 提出了建立和维护x m l 数据的o o d b 模式的方法。在结构的定义方面， x m l 具有较大的灵活性，对此本文分别给出了根据d t d ( d o c u m e n tt y p e d e f i n i t i o n ) 和x m ls c h e m a 建立x m l 数据的对象模式的方法以及从无类型定义 的x m l 数据中抽取结构信息建立临时的d t d 的方法。x m l 数据是易变的，为 使x m l 数据的对象模式与数据保持一致，本文提出了x m l 数据的对象模式的 动态更新算法。实验结果显示，本文所提出的建立x m l 数据的对象模式的方法 是较为有效的。 3 对x m l 数据的访问需求进行了分析，提出了x m l 数据的结构索引，介 绍了利用结构索引实现各种物理代数操作的方法，并对结构索引的空间和基于结 构索引的操作的i o 代价进行了分析。利用路径索引可以提高基于路径的对象访 f 【1 l 操作的效率，然而当数据中存在复杂的不完全引用关系时，路径索引的规模可 能很人。为此，本文提出r 以增量的方建立和维护x m l 数据的路径索引的方 河、，能够有效地降低建立与维护路径索引的代价。 4 对x m l 数据的杏询处理方法进行r 研究。建奇：j ，初步的代价模型，分析 j 。t 芟的物理代数操作特别是数据访n q 操作的代价。讨论了建立逻辑查询计划的 复壁大学博士学位论文 摘要 方法以及根据逻辑查询计划生成物理查询计划的方法，提出了一些减小物理查询 计划搜索空间的规则。查询路径上对象间的连接是查询处理中频繁进行的关键操 作，为此，本文对路径连接的实现方法进行了研究，提出了基于结构索引的实现 方法和基于路径索引与数字模式的路径连接算法( p n e - j o i n ) ，并分析了两种方 汪、的效率。实验结果表明，对于路径长度和( 或) 结点出度( 或入度) 较大的情 况p n p - j o i n 的运行时问显著小于与自顶向f 或自底向上遍历的方法。并且， p n p - j o i n 的运行时问仅与路径两端目标集r i ，对象的数量有关，而与路径长度无 关。与仅利用数字模式的方法相比，p n p - j o i n 具有较高的效率，并且可以用于图 结构的数据。另外，在路径索引的结点中包括统计数据可用于查询优化，名字索 引则不具有这种功能。卢7 f、c 关键宇：x m l ，面向对象的数据库，数据模型，查询语言，( 模式j 结构索引， 路径索日l ，查询处理，路径连接 复【i 大学博士学位论文 一 垒! ! ! ! 璺 一 a b s t r a c t x m lf e x t e n s i b l em a r k u pl a n g u a g e ) i sam a r k u pl a n g u a g ei n t r o d u c e db yw 3 c ( t h ew b r l dw i d ew e bc o n s o r t i u m li nf e b r u a r y l9 9 8l i k em m l ，x m li sa l s oa s u b s e to fs g m lw h e l e a sh t m li sp r e s e n t a t i o n - o r i e n t e d x m li sc o n t e n t - o r i e n t e d s ox m lh a sb e e nw i d e l ya c c e p t e da san e ws t a n d a r df o rr e p r e s e n t i n ga n de x c h a n g i n g d a t ao nt h ew e bq u e r ya n dm a n a g e m e n to fx m ld a t ah a v eb e e nb e i n gi n t e n s i v e l y s t u d i e db yw e ba n dd a t a b a s ec o m m u n i t i e ss e v e r a lq u e r yl a n g u a g e sa n dp r o t o t y p e s y s t e m sh a v eb e e np u tf o r w a r d c o m m e r c i a ld b m sp r o d u c t ss u c ha s0 r a c l e ，d b 2 a n ds q ls e r v e rb e g a nt oa d df e a t u l e sf o rq u e r y i n gx m ld a t a t h e s er e s e a r c ha n d i m p l e m e n t a t i o n sc a nb e c l a s s i f i e di n t ot h r e et y p e s a c c o r d i n gt od a t am o d e l st h e y e x p l o i t e d ：1 ) s e m i s t r u c t u r e ds c h e m e ；2 ) r e l a t i o n a ls c h e m e ；a n d3 ) o b j e c t - o r i e n t e d s c h e m e i nt h i sp a p e rw es t u d yk e yt e c h n i q u e sf o rq u e r y i n g 扎d a t ai n0 0 d b s d a t am o d e l ( o m ) a n d q u e r yl a n g u a g e ( o q l ) ，b a s e do nt h ef o l l o w i n gc o n s i d e r a t i o n s ： 11o m s u p p o r t sc o m p l e x d a t at y p e a n di ti sm o r ec o n v e n i e n tt om a p 舭d a t a t o o m 2 ) o b i e c t o r i e n t e dm e t h o dh a sb e e nw i d e l ye m p l o y e di nv a r i o u ss t a g e so f s o r w a r ed e v e l o p m e n tp r o g r a m sf o rp r o c e s s i n gx m ld a t ai no mc a nb ec o m b i n e d s e a m l e s s l yw i t ho t h e rp a r i so fa l la p p l i c a t i o ns y s t e m3 、o o d bo v e r c o m e si n h e r e n t l i m i t a t i o n so fr d b ，i tc a nb ee x p e c t e dt h a t0 0 d bw i l lc o n t i n u e st op r o g r e s s i nt h e m e a nt i m e m o r ea n dm o l ed a t aw i l lb ep r e s e n t e da n de x c h a n g e di n ) 舰f o r m a t d e v e l o p m e n t w i l lb e s i m p l i f i e dd r a m a t i c a l l yi fa l id a t ai no o d b o ri nx m 儿d a t a b a s e a r ea c c e s s e dw i t hs a m em e t h o d t h em a i nc o n t r i b u t i o no f t h i sp a p e ri n c l u d e ： 1 b r i n gf o r t ham e t h o df o rs t r u c t u r i z i n gx m ld a t a x 儿d a t aa r ed i f f e r e n t f r o mt h o s ei nc o n v e n t i o n a l0 0 d b sw i t hr e g a r dt oc o n s t r u c t i o n o nt h eo n eh a n d , t h e r em a ye x i s tc o m p l e xc o m b i n a t i v ea n do r d i n a lr e l a t i o i l s h i p sb e t w e e ne l e m e n t sa sa r e s u l to f d e f i n i n gc o n t e n tm o d e lw i t hr e g u l a re x p r e s s i o n s o nt h eo t h e rh a n d ，t h e r e m a y n o tb e e x p l i c i tt y p ed e f t n i t i o nf o r ) ( m ld a t a a c c o r d i n gt ot h ec h a r a c t e r i s t i c so f x m 吐d a t a w ee x t e n dt h eo d m go m p r o p e r l y , a n dt h e np u tf o r w a r dr u l e sf o r m a p p i n g x m ld a t at oo m w ea l s oc o n d u c ta p r e l i m i n a r ys t u d yo na l g e b r ao p e r a t o r s a n do q lb a s e dq u e r yl a n g u a g ef o rx m ed a t a w ea n a l y s i ss e m a n t i c so fm a j o r a l g e b r ao p e r a t i o n s ，a n dp u tf o r t hs o m eo p e r a t o r sf o rc o m p a r i n go r d e r so fo b j e e t s i n o r d e rt oq u e r ys e m i s t r u c t u r e da n do r d i n a lx m l d a t a ，w ee x t e n df e a t u r e so fo q l ， i n c l u d i n gr u l e so fc o e r c i o n ，p a t he x p r e s s i o n s a n dm e t l o d sf o rf o r m u l a t i n gq u e r i e s a c c o r d i n g t oo r d e r s 2 p r e s e n tm e t h o d sf o rb u i l d i n ga n dm a i n t a i n i n gs c h e m ao fx m ld a t a x m li s m o r ef l e x i b l et h a nt r a d i t i o n a ld a t a b a s ew i t hr e s p e c tt os t r u c t u r ed e f i n i t i o n f o rt h i s r e a s o nw eg i v em e t h o d sf o rb u i l d i n go os c h e m af o rx v l ld a t aa c c o r d i n gt od t do r x m ls c h e m ar e s p e c t i v e l y w ea l s o s t u d yh o wt o c o n s t r u c tt e m p o r a r ym s b y e x t r a c t i n gs t r u c t u r ei n f o r m a t i o nf r o md a t aw i t h o u tt y p ed e f i n i t i o n x m ld a t am a y c h a n g er a p i d l y i no r d e rt om a i n t a i nc o n s i s t e n c eb e t w e e ns c h e m aa n dd a t a , w eb r i n g f o r w a r da n a l g o r i t h mf o ru p d a t i n go o s c h e m ao f x m ld a t ad y n a m i c a l l y 3w ea n a l y z e r e q u i r e m e n t s f o r a c c e s s i n gx m ld a t a ，a n db r i n g f o r w a r da s t r u c t u r ei n d e xf o rx m ld a t aw ei n t r o d u c eh o wt oi m p l e m e n t o p e r a t i o n sb yu t i l i z i n g s t r u c t u r ei n d e xa n da n a l y z es p a c eo ft h es t r u c t u r ei n d e xa n di oc o s to fo p e r a t i o n s 复旦大学博士学位论文 a b s t r a c c b a s e do ns t r u c t u r ei n d e x e f f i c i e n c yo fo p e r a t i o n sf o ra c c e s s i n go b j e c t sa l o n gp a t h s c a r lb ee n h a n c e db ym a k i n gu s eo fp a t hi n d e x b u tw h e nt h e r ea r el o r so fp a r t i a l r e f e r e n c e si nad a t a ，s c a l eo ft h ep a t hi n d e xm a yb ev e r yl a r g e w ep u tf o r w a r da m e t h o df o rb u i l d i n ga n dm a i n t a i n i n gp a t hi n d e x e si n c r e m e n t a l l y , b yw h i c hc o s t sf o r c o n s t r u c t i n ga n dm a i n t a i n i n gp a t hi n d e x e s c a nb ed e c r e a s e d 4w es t u d y q u e r yp r o c e s s i n g t e c h n i q u e s f o rx i v l ld a t a b e n e f i tf r o m o p t i m i z a t i o nt e c h n i q u e su s e di nt r a d i t i o n a ld a t a b a s es y s t e m ( s u c ha so p t i m i z a t i o nb y n d e sa n do p t i m i z a t i o nb yc o s ta n a l y s i se t c ) ，a n da c h i e v e m e n t sm a d ei na r e ao f s e m i s t r u c t u r e dd a t a ，w ee s t a b l i s hap r e l i m i n a r yc o s tm o d e l ，a n da n a l y z ec o s t so f m a j o rp h y s i c a lo p e r a t i o n se s p e c i a l l y t h o s ef o r a c c e s s i n gx m ld a t a w es t u d y m e t h o d sf o rc r e a t i n gl o g i c a lq u e r yp l a na n df o rg e n e r m i n go p t i m a lp h y s i c a lq u e r y p l a na c c o r d i n g t o1 0 9 i c a lp l a n w ea l s og i v es o m eh e u r i s t i cr u l e sf o rr e d u c i n gs e a r c h s p a c eo fp h y s i c a lq u e r yp l a n s j o i no f o b j e c t sa l o n gp a t h si sak e yo p e r a t i o nf r e q u e n t l ye x e c u t e dd u r i n gq u e r y p r o c e s s i n g p a t hj o i nc a nb eu s e d t os i m p l i f yq u e r yp l a na n de n h a n c ee f f i c i e n c y w e s t u d ym e t h o df o ri m p l e m e n t i n gp a t hj o i n ，a n dp u tf o r w a r dt w os c h e m e s ：s t r u c t u r e i n d e xb a s e dp a t hj o i n ( t p - j o i n ) ，a n dp a t hj o i nb a s eo np a t hi n d e xa n dn u m b e r i n g s c h e m e ( p n p - j o i n ) w ea n a l y z ep e r f o r m a n c eo f t h et w om e t h o d s e x p e r i m e n tr e s u l t s i n d i c a t et h a tf o rd a t aw i t hl o n gp a t h sa n d ( o r ) l a r g ef a n i no rf a n o u t ，e x e c u t i o nt i m e o fp n p - j o i ni sn o t a b l yl e s st h a nt h a to ft p - j o i na n de x e c u t i o nt i m eo fp n p - j o i n d e p e n d so n l yo nn u m b e ro f o b j e c t sa tt e r m i n a l so f t i l ep a t ha n d i si n d e p e n d e n to f o a t h l e n g t h ，w h e r e a se x e c u t i o nt i m eo ft p - j o i ni n c r e a s i n gs t r i k i n g l yw i t ht h ep a t hl e n g t h c o m p a r e dw i t hm e t h o dt h a tu s e so n l yn u m b e r i n gs c h e m e ，f i r s t , p n p - j o i nc a nb e a d a p t e dt og r a p hs t r u c t u r e d d a t a s e c o n d , t h e r ee x i s t s a d e p e n d e n tr e l a t i o n s h i p b e t w e e na t a r g e ts e ti nap a t hi n d e xa n dt h ep a t hr e a c h i n gi t ，a n di nt h et a r g e ts e tt h e r e a r eo n l yo b j e c t st h a tc a nb er e a c h e db yt h ep a t h s op n p - j o i ni sm o r ee f f i c i e n t i n a d d i t i o nn o d eo b j e c t si n p a t hi n d e xc a ns t o r e s t a t i s t i c sf o rt h ep u r p o s eo fq u e r y o p t i m i z a t i o n ，n a m ei n d e xh a sn os u c hf u n c t i o n k e y w o r d s ：x m l ，o b j e c t o r i e n t e dd a t a b a s e ，d a t am o d e l ，q u e r yl a n g u a g e ，s c h e m a ， s t r u c t u r e i n d e x ，p a t hi n d e x ，q u e r yp r o c e s s i n g ，p a t hj o i n 复旦大学博士学位论文 苎二童堕堡 一 1 1引言 第一章绪论 近年来互联网( i n t e r n e t ) 蓬勃发展，出现了大缀基于万维网( w o r l dw i d ew e b ， 简称w w w 或w e b ，以下称w e b ) 的应用，如电子商务、数字图书馆、远程教 育等等。这些应用涉及各种类型的数据，包括结构化的( 如关系数据库或对象数 据库中的数据) 、半结构化的( s e m i s t r u c t u r e d ，如以h t m l 表示的数据) 和无结 构的( 如各种格式的声音、图像数据等) 。随着w e b 上数据的激增，通过超链接 导航的搜索方法和基于全文检索的搜索方法已经越来越难以满足人们对w e b 数 据访问的要求。 经过多年的努力，数据库界在结构化数据的查询与优化、数据的完整性、一 致性、安全性、事务管理与并发控伟4 等方面已取得了很大的成功，于是，人们很 门然地期望能够利用传统数据库系统中处理结构化的数据的方法来解决w e b 数 据查询的问题。换一个角度来看，随着各种应用对数据管理需求的变化，数据库 臂理系统的功能也应该作出相应的改变，从单一地处理结构化的数据向异构多数 据源集成与管理的方向发展。对w e b 上大量半结构化数据的访问成为近年来数 据库界研究的一个热点 m a g + 9 7 b d h s 9 6 1 k s 9 5 1 m m m 9 7 f f l s 9 7 c j s 9 9 。 半结构化的数据通常没有严格的类型定义，描述数据结构的信息包含在数据 当中。为此，在很多研究中采用了基于有向图的半结构化数据模型如o e m f p g w 9 5 g p q 9 7 f k l 9 7 、e d g el a b e l e dg r a p h b d h 9 6 【b u n 9 7 1 、h y p e r t r e e h m g s 】 和l a b e l e dm u l t i g r a p h s k s 9 5 等等。按照这样的模型，半结构化数据可以用标注 的有向图表示，图中结点表示对象，边表示对象之间的联系。还有不少研究采用 r 关系或嵌套的关系( n e s t e d r e l a t i o n ) 模型如a d m a m m 9 7 a a m m 9 7 b ， r e l a t i o n a lm o d e lu n d e rw e b s q l f m m m 9 7 等。借鉴传统数据库系统中模式的概念 可以定义并建立半结构数据的模式，在此基础上实现查询的表达和查询处理。 采用半结构化的数据模型处理w e b 数据时，首先要从文本格式的数据中抽取 结构信息。由于目前在w e b 上普遍使用的h t m l 是面向显示的( p r e s e n t a t i o n - o r i e n t e d ) ，主要用于描述数据的格式、显示样式以及数据的位置等，无法真接定 义数据的结构，因此从基于h t m l 的w e b 数据中抽取结构信息的难度很大，通 常只能根据数据的格式( 段落、字体、缩进距离等) 并结合启发性规则来进行推 测【a k 9 7 】 h g c + 9 7 】【k w d 9 7 】，在可抽取的数据类型、正确性以及通用性等方面 郁不够理想。 复旦大学博士学位论文 蔓二童堕堡 一一 基于上述原因，虽然在半结构化数据的处理方面已取得了大量研究成果，但 对w e b 上数据的查询问题仍然没有很好解决，时至今日，网上数据的访问还要 依赖于导航与搜索引擎。 针对h t m l 的局限性，w 3 c 于1 9 9 8 年推出了可扩展的标记语言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 允许按应用的需要定义标识( t a g ) ，而不 象h t m l 那样使用固定的标识集，从而为w e b 上数据的查询与数据集成打开了 疗便之门。 1 2x l v l l 的应用与研究现状 以文本格式描述w e b 上的数据是实现易用性的一种手段，但仅把数据作为文 本处理而忽视其内在的联系显然是片面的。h t m l 的易用性在过去的确取得了很 大的成功，但其局限性也限制了w e b 的进一步发展，上述的在w e b 数据查询方 面的困难就是一个例子。为此，万维网联盟( w o r l dw i d ew e bc o n s o r t i u m ，简称 w 3 c ) 从1 9 9 6 年起研究开发新一代的标记语言x v l l ，并于1 9 9 8 年二月正式推 出了该语言的基本规范x m l l ，0 8 3 p s 9 8 。x m l 的设计思想很简单：用标识表示 数据是什么，而不是它看起来像什么。这就要求能够根据应用的需要定义标识。 x v l l 并不是全新的，事实上，x m l 是s g m l i s 0 8 8 7 9 的一个子集，这表现在 每一个规范的( w e l l f o r m e d ) x m l 文件也是一个合乎规范的s g m l 文件，不过， x m l 比s g m l 更简洁、更易于实现。x m l 延续了h t m l 的易用性，但与耵 不同的是，x m l 是面向内容的( c o n t e n t - o m n t e d ) ，x m l 中的标识主要用于描述 数据之间各种类型的关系，而不是其显示形式。 关于x m l 实际上有一系列标准，x m l i 0 0 3 p s o o 只是其基本的语言规范。 其他标准包括x l i n k ( 用于描述将超链接加入x m l 文档的方法的标准) 、 x p o i n t e r ( 关于x m l 文档中特定部分的定位的标准) f t h 0 0 2 、x s l ( e x t e n s i b l e s t y l e s h e e tl a n g l l a g e ，有关x m l 文档的显示样式的标准) f r o u 0 2 、d o m ( d o c u m e n t o b j e c tm o d u l e ，供应用程序处理x m l 文档的对象模型及接口标准的定 义) h 6 9 0 2 】、x m ln a m e s p a c e s ( 关于如何将x m l 文档中的元素标识、属性与 u r l 相关联的标准) 【b h l 9 9 】、x m ls c h e m a sl a n d2 ( 供应用开发者精确地定 义基于x m l 的类型) 【f a l l 0 1 以及x m lq u e r y ( 关于x m l 数据的查询的标准) m a r 0 2 1 等等。其中很多标准还正在制定中【q u i n 0 2 1 。 x m l l 0 推出后，! z 刻引起了热烈的反响，x m l 巨大的应用潜力得到了广泛 的认同。小少人认为x m l 是革命性的，将从根本上改变w e b 的面貌 w i d 9 9 1 。 更普遍的观点是x m l 将使w e b 的使用性能有很大的改善，因为x m l 标识说明 r 数据的语义和结构，因此大量的结构化的数据将可以存储在x m l 文档中，利 复旦大学博士学位论支 第章绪论 j j 插入在数据中的小程序可以在客户端完成更多的任务，从而极大地减少网上的 数据流量，使数据访问的速度显著加快。同时，特定的、复杂的查询也成为可能， 从而使网上数据的访问更加容易。适合于特定领域的基于x v l l 的规范相继推出 ( 如s m i l h o s 9 8 、m a t h m l i m 9 9 i is v g f e r 0 1 等等) ，很多组织和各人开始 采用x m l 进行数据交换，各大软件商( 如m i c r o s o f t 、o r a c l e 、i b m 和s u n 等) 纷纷推出面向) 渐l 的工具或在原有产品( 如s q ls e r v e r 、o r a c l e 和d b 2 等) 中增 加对x m l 数据查询的支持。 x m l 数据的访问和管理给数据库界带来了新的挑战和机遇，大量的研究人 员开始投入有关x m l 的研究与开发。总体看来，这些研究可以分为以下一些方 面( 当然这些方面并不是完全分离的) ： l ，) 也数据的查询 由于越来越多的结构化或半结构化的数据采用x m l 格式存储和交换，因此 对x m l 数据的查询变得日益重要 1 a t 9 8 】。w 3 c 为此专门成立了x m l 查询工 作组( x m l q u e r yw o r k i n gg r o u p ) ，负责制订有关查询的数据模型、查询语言等 方面的规范。x m l 数据与此前研究中所提出的半结构化数据非常相似，因此， 有关半结构化数据方面的研究成果可以比较方便地应用于x m l 数据的查询，包 括查询语言 b d h s 9 6 a q m + 9 7 a m 9 8 、查询处理技术 f s 9 8 m w 9 9 a 和索引方 法 m w a + 9 8 m s 9 8 等。同时，很多研究人员对利用传统数据库系统查询x m l 数据的方法进行了研究( 如 d f s 9 9 s h t + 9 9 f k 9 9 l a w 9 8 n d m + 0 0 f e 0 1 】 t d d + 0 1 等等) 。在这些研究中主要涉及以下一些问题：； 1 ) 数据模型。 x m l 数据是非常灵活的，表现为有些数据具有明确的数据类型定义( 如按 照x m l s c h e m a 建立的数据) ，而另外一些数据则缺乏严格的类型定义或根本就 没有类型定义。为便于实现结构化数据查询，应将x m l 数据映射到某种数据模 型。由于关系数据库系统目前处于主导地位，因此很多研究和实现方案采用了关 系模型( 如【d f s 9 9 s h t + 9 9 1 f k 9 9 s k w w 0 0 等，以及主流的数据库产品如 o r a c l e 、d b 2 等) 。将x m l 数据映射到关系模型的一个明显缺点是缺乏直观 性。因此不少研究采用了关系对象模型( 如 k m 0 0 1 ) 或面向对象的半结构化数 据模型( 女h g m w 9 9 】) 以及o o d b 的数据模型( 血h l a w 9 8 f e 0 1 等) 。w 3 c 的x m l 查询工作组提出的数据模型( 正在制订中的工作草案，见 f m n 0 1 ) 综 合考虑了表示结构化数据( 简单类型或复杂类型) 与半结构化数据的需要。 2 ) 模式建立与维护 在传统的数据库中，数据的定义、查询表达、查询的处理与优化等都依赖于 模式。对于x m l 数据的仓询，模式同样是非常重要的。文档类型定义( d o c u m e n t 复旦大学博士学位论文 一 璺：翌竺笙 一 一 t y p ed e f i n i t i o n ，简称d t d ) 描述了x m l 文档中元素的结构信息，因此可以看 作x m l 数据的模式，不过d t d 缺乏精确的类型定义，引用定义机制也不完善， 为此，可以针对所采用的数据模型( 关系的或面向对象的等) 根据d t d 建立相 应的数据库模式 s h t + 9 9 ，w i d 9 9 】。【妇于无d t d 的x m l 文档也是合法的 ( w e l l f o r m e d ) 、因此，在w e b 上可能存在大量无d t d 的文档，对于这样的文档， 需要通过抽取其中的元素结构建立模式 g w 9 7 ，w i d 9 9 。w e b 数据是易变的，随 着x m l 数据的变化，相应的模式也应随之更新。文献 s h t + 9 9 ，g w 9 7 ，w i d 9 9 】 等分别讨论了关系模式、半结构化的数据库模式的更新问题。 3 ) 查询语言 合适的查询语言是必不可少的，这样的查询语言应该有足够的表达力来满足 对结构化数据查询和从文档中检索信息的需要。自x m l l 0 推出后，有关各方先 后提出了很多查询语言的方案，有的是在以前半结构化数据的查询语言的基础 上，针对x m l 的特点作了必要的扩展，如l o r e l a q m + 9 7 1 g m w 9 9 、o q l 8 l a w 9 8 及w e b o q l a m 9 8 等。另外一些则是专门为x e l 的查询而提出的如 x m l q l d f f + 9 8 、x q l r l s 9 8 、y a t l c j s 9 9 及q u i l t c r f 0 0 等等。w 3 c x m l 查询工作组提出的查询语言x q u e r y ( 草案) f b c f + 0 1 借鉴了结构化、半结构化 数据查询语言的很多特性，并且较多地考虑了对不同类型数据源( 包括传统的数 据库系统及文档系统等) 的访问能力以及在小型化、易实现以及可读性 ( h u m a n - r e a d a b l e ) 等方面的要求。 4 ) 查询处理 在传统的数据库系统中，结构化数据的查询处理已经得到了广泛深入的研究 【g r a 9 3 ，这为x m l 数据的查询奠定了基础，很多方面( 如查询计划的生成、代 价估算的方法、优化规则等) 都值得借鉴。不过，v m 数据具有新的特点和查 询需求，原有的方法应根据x l v l l 数据的特点进行改进，还要考虑与其他方法( 如 全文索引) 的结合。在l o r e 系统中采用了多种索引来提高查询效率，建立了基 于磁盘i o 和c p u 时间的代价模型，结合多种统计数据来实现查询优化 m w 9 9 a , m w 9 9 b 。s t r u d e l 中使用存储描述符( s t o r a g ed e s c r i p t o r s ) 来表示数据的存储格 - ，查询处理器根据描述符计算查询代f f r i f l s 9 8 。由于w 曲上的x m l 数据常 常是不规则的和易变的，因此基于一般路径表达式( g e n e r a lp a t he x p r e s s i o n ) 的 奁询将非常有用，不少工作( f f l s 9 8 1 m w 9 9 c g t 0 0 i l m 0 1 等) 对一般路径查 询的优化问题进行了研究。 5 ) x m l 数据的存储 x m l 数据的物理存储格式对查询处理的效率有很大的影响，目前主要有三 种方案：i ) 文本格式，这是存储x m l 数据的标准格式。为了提高查询效率可 复旦大学博士学位论文 第一一章绪论 以建立索引，索引的维护是需要解决的关键问题。i i ) 将x m l 数据存储于传统数 搦库中，如f d f s 9 9 1 【s h t + 9 9 】【f k 9 9 】【l a w 9 8 】等。利用传统数据库系统的查询处 理机制可以获得较高的效率，但x m l 数据与传统数据库之间的转换可能导致信 息损失。i i i ) 使用对象管理器如s h o r e c d n 9 4 保存x m l 数据 t d c z 0 1 。这类系 统目前缺乏类似s o l 。或o o l 的通用的查询语言。 6 、视图的建立与维护 视图在传统数据库中是一种重要的机制，同一物理数据上的多个视图可以满 足用户不同的需要，视图还可以控制用户对数据的访问，有利于数据库的安全。 对于x m l 数据的查询来说，视图很可能同样重要，不过，x m l 数据的不规则 性也给视图的定义、维护及查询重写等带来了更多的困难，近年来在半结构化数 据的视图方面已有不少研究( 见 a m r + 9 8 f l s + 0 0 c w 0 0 等等) 。 2 数据集成 w e b 上汇集了大量的各种类型的数据，在这一平台上有望实现最广泛的数据 集成，基于w e b 的数据集成是近年来的一个研究热点。为了从大量的异构的w e b 站点上访问数据，通常使用包装器( w r a p p e r ) 来描述数据源的内容和查询能力， x m l 的出现简化了包装器的生成。不过，还有很多问题需要解决，包括数据源 的描述语言、数据源描述的自动获取、查询效率的提高等，近来的研究已取得了 刁i 少成果( 参见 l y v 9 8 p v 9 9 c c s 9 9 d d l 0 0 等等) 。 3 数据出版( p u b l i s h i n g ) 和交换： x m l 己成为w 曲上数据交换的通用语言，而在未来较长的时期内大量的数 据仍将保存在传统数据库系统中，因此需要将传统数据库中的