（计算机软件与理论专业论文）基于关系数据库的xml数据存储、更新和检索.pdf

籀要 摘要 x m l 正迅速取代h t m l 成为w e b 上数据表示、集成和交换的标准。与 h t m l 相眈，x m l 简单、自我描述，实现了内容、结构和表现三者的分离，更 邋合于数据表示和交换。近来，x m l 在各种领域得到了广泛的使用，w e b 上 涌现了海麓的x m l 数据。为了裔效地加工、分析和处瑗x m l 数据，研究者们 已经提出了各种x m l 的查询语裔和存储管理技术。在存储管理x m l 的备种可 能酶方式中，基予关系的x m l 数据处理怒一种w 行丽有游景的方式，受剜了广 泛的关注。然而，由于数据模型的差异，利用关悉数据库查询处联x m l 数据给 传统数据库技术带来了许多新的擒战。 本文研究基予关系数据库的x m l 数据的存储、更新和检索技术，对x m l 数 舔的存储穰式优俄调整、x m l 数攒的蕊藏祀存储、) 正数器傈符健约束麓更耨、 x m l 数据检索技术、基于代价的路径索引构建等方面进彳亍了深入的研究和探讨， 撬出了有效翡算法和新静技术。论文提出的蘸分方法已奁驻壅系统中实现，荠逶 过实验证明了本文所提出方法的有效性。研究成聚将可盥接用于x m l 数据库的 矮嚣开发耩产品磷赣孛，鬃有重要豹理论秘现实意义。爨体来说； 1 ) 提出了x m l 数据在关系数据库中存储模式的自适应调熬机制。根据历 囊誊询售纛，系统在合理瓣对藏癌瓣其存髓模式遴行鑫动谴整美产生毫散豹存赣 模式，从而提高系统的总体查询处理效率。同时，还提出了四种存储模式调整策 臻，其孛疆耱策臻毒 三l 实褒蠡逶疲存锫模式谖整。实验袭骥该冀法能鸯效提毫 x m l 数据管理系统的查询处理效率。该技术可集成到数据库系统的性能调节工 其中。 2 ) 基于x m l 键约束的概念，提出了种将x m l 文档保持x m l 键约束地 殴瓣到关系数据露孛豹方法。实瑗了x m l 文楼农关系数糖淳孛鹣癯薤绽存建， 极大地减少了x m l 数据程关系数据库中的冗余存储，大大减小了操作异常。对 将来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 文档保持了一致a 并且掇出了新的标注技术，实现了对x m l 文档更新位y 置的快 速定位，从褥毫效地实现了x m l 文档傈黪键约束豹更毅。该更裁技术使德x m l 成为真正袭示与共享的统一格式。 4 ) 提如了嚣季中新的铡l 索引技术，该倒i 索弓l 技术霹应用予x m l 文档的 摘要 检索。实验结果表明本文提出的两种倒排索引的空间开销得到了显著改善，其中 基于模式的倒排索引获得了最好的存储空间与查询效率的权衡。其结论对未来 x m l 数据搜索引擎的设计具有指导意义和参考价值。 5 ) 本文还研究了一种有效支持x m l 路径表达式查询处理的路径索引 结构映射。给出了计算路径索引空间开销和所带来查询收益的代价模型。对给定 的查询负载，我们采用贪心算法选择构建部分路径索引。也即，在一定的存储空 间约束下，使选择构建的索引能带来最大的查询收益。为将来x m l 查询优化和 索引设计奠定了基础。 关键字：x m l 存储模式优化规范化存储x m l 文档更新x m l 信息检索 分类号：t p 3 1 1 2 攮要 a b s t r a c t x m lh a sb e e nb e c o m i n gt h ed ef a c t os t a n d a r df o ri n f o r m a t i o n p u b l i c a t i o na n d e x c h a n g e o nt h ew e b ，s u b s t i t u t i n gf o rh t m l c o m p a r i n gt oh t m l ，x m li ss i m p l e ， s e l f - d e s c r i b i n g ，a n dt h ec o n t e n t , s t r u c t u r ea n dr e p r e s e n t a t i o no fx m l d o c u m e n t sa r e i n d e p e n d e n t ，w h i c hm a k e sx m l m o r es u i t a b l ef o rd a t ar e p r e s e n t a t i o na n de x c h a n g e o nt h ei n t e r n e t 。r e c e n t l y ，x m lh a sb e e n w i d e l yu s e di nv a r i o u sa p p l i c a t i o n s ，a n d v e r yl a r g ev o l u m e so fx m l d a t ah a v eb e e na p p e a r e di nt h ew e b t oo r g a n i z ea n d m a n a g ex m l d a t ae f f i c i e n t l y ，d i f f e r e n tq u e r y l a n g u a g e sa n ds t o r a g ea p p r o a c h e s h a v e b e e np r o p o s e d 。a sav a r i a b l ea n dp r o m i s i n ga p p r o a c h , u s i n gr d b m st o m a n a g e x m ld a t ai s e x t e n s i v e l ys t u d i e di nr e c e n ty e a r s h o w e v e r , d u et ot h ed i f f e r e n c e s b e t w e e nd a t am o d e l s ，r d b m s - t m s c dx m ld a t a p r o c e s s i n gb r i n g su pn u m e r o u s c h a l l e n g e sf o r t r a d i t i o n a ld a t a b a s et e c h n i q u e s t h i sd i s s e r t a t i o ns t u d i e st h ei s s u e so nx m l s t o r a g e ，u p d a t i n ga n dr e t r i v a l i n r d b m s i np a r t i c u l a r , i tf o c u s e so nt h ep r o b l e m so f a d a p t a t i o no fx m ls t o r a g e s c h e m a , n o r m a l i z e ds t o r a g eo fx m l ，c o n s t r a i n t - p r e s e r v i n gx m l u p d a t i n g ，t h e e f f i c i e n tr e t r i e v a lo fx m ld a t aa n dt h eo p t i m a lp a t hi n d e xs e l e c t i o no fx m l ，e t c v a r i o u sn e wa l g o r i t h m sa n dt e c h n i q u e sa r e p r o p o s e d a n di m p l e m e n t e di na l l x m l r e l a t i o n a ld a t a b a s e s y s t e mp r o t o t y p e al a r g e n u m b e ro fe x p e r i m e n t sa r e c o n d u c t e da n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s so ft h o s ea p p r o a c h e s p r o p o s e d t h ef r u i t so f t h i sd i s s e r t a t i o nc a nb eu s e di nt h er e s e a r c ha n d d e v e l o p m e n t o fp r o d u c t so nx m ld a t a b a s e + t h ec o n t r i b u t i o n so ft h i s d i s s e r t a t i o nc a nb e s u m m a r i z e da sf o l l o w i n g ： 1 ) p m p o s e s t h et e c h n i q u e so fx m l s t o r a g es c h e m aa d a p t a t i o n 。t h ee f f i c i e n c yo f x m l m a n a g e m e n ts y s t e md e p e n d so ni t ss t o r a g es c h e m a u n d e rt h ec o n d i t i o n t h a tu s e r s q u e r i e sa r eg i v e no re x p e c t e d ，d e s i g n i n gs t o r a g es c h e m ab a s e do n u s e r s q u e r i e sc a ni m p r o v et h ee f f i c i e n c yo fs y s t e ms i g n i f i c a n t l y b a s e do n h i s t o r yq u e r i e s ，s t o r a g es c h e m ac a nb ea u t o m a t i c a l l ya d j u s t e df o ri m p r o v i n g q u e r y p r o c e s s i n ge f f i c i e n c y f o u r k i n d so f s c h e m a a d a p t a t i o ns t r a t e g i e sa r eg i v e n ， i nw h i c ht w oa r eu s e df o ra u t o m a t i cs c h e m aa d a p t a t i o n 。e x p e r i m e n t a lr e s u l t s v a l i d a t et h ep r a c t i c a b i l i t ya n de f f e c t i v e n e s so ft h ep r o p o s e da p p r o a c h e s t h e t e c h n i q u e sc a n b e i n t e g r a t e di n t ot h es y s t e mo p t i m i z e r 2 ) b a s e do nx m lk e y sw h i c hd e f i n et h es e m a n t i cc o n s t r a i n t so fx m ld o c u m e n t w ep r e s e n tas t o r i n gm e t h o d , w h i c hs t o r e sx m l d o c u m e n t sw h i l ec o n s e r v i n g 3 攮要 t h e i rk e yc o n s t r a i n t s a n dt h en o r m a l i z e ds t o r a g eo fx m li nr e l a t i o n a ld a t a b a s e s i si m p l e m e n t e d + n e e d l e s sr e d u n d a n c yi se l i m i n a t e d ，a n da b n o r m a lo p e r a t i o n sa r e r e d u c e d t h em e t h o d sp r o p o s e dh a v es o m es i g n i f i c a n c ef o rp r o c e s s i n gx m li n t h ef u t u r e + i ti st h eb a s ef o r k e yc o n s t r a i n t - p r e s e r v i n gx m l u p d a t i n g 3 ) b a s e do nx m lk e y sa n dt h ec o n s t r a i n t - p r e s e r v i n gn o r m a l i z e ds t o r a g eo fx m l o v e rr e l a t i o n a ld a t a b a s e s ，w es t u d yt h en o v e lm e t h o df o ru p d a t i n gx m lw h i l e p r e s e r v i n gk e yc o n s t r a i n t s b yp r o p a g a t i n gx m lk e y st or e l a t i o n sa sf u n c t i o n a l d e p e n d e n c i e s w eu p d a t ex m l d a t aa n di t ss t o r a g eo v e rr e l a t i o n a ld a t a b a s e s 敷 t h es a m et i m e ，w e p r e s e r v e t h ec o i n c i d e n c eb e t w e e nt h e m + w eg i v et h e a n n o t a t i o n t e c h n o l o g y , w h i c h c a nb eu s e dt ol o c a t et h ep o s i t i o n so f u p d a t e si nt h e o r i g i n a lo n ea n du p d a t et h ed o c u m e n t se f f i c i e n t l y t h i su p d a t i n gt e c h n i q u e 如l l y e v o l v e sx m li n t oau n i v e r s a ld a t a r e p r e s e n t a t i o na n ds h a r i n gf o r m a t 4 ) w es t u d yt h ek e y w o r ds e a r c hf o rx m l i nr e l a t i o n a ld a t a b a s e s ，p r e s e n tt w on e w i n v e r t e dl i s ti n d e x e s ：e x t e n d e di n v e r t e di n d e xb a s e do nc o n t a i n m e n t r e l a t i o n s h i p a n di n v e r t e di n d e xb a s e do ns c h e m a t h ef o r m e rr e d u c e st h es p a c ec o s tg r e a t l y b y c o n s i d e r i n g c o n t a i n m e n t r e l a t i o n s h i pb e t w e e ne l e m e n t s ，a n d t h el a t t e rr e d u c e st h e s p a c ec o s t f u r t h e rb yc o n s i d e r i n gt h es c h e m ao fx m l ，a tt h es a n l et i m ei t i m p r o v e st h ee f f i c i e n c yo f x m ld a t as e a r c hs i g n i f i c a n t l y e x p e r i m e n t si n d i c a t e t h a tt h ei n v e r t e di n d e xb a s e do ns c h e m a g e t s t h eb e s tt r a d e o f fb e t w e e n s p a c ec o s t a n d q u e r ye f f i c i e n c y t h i sr e s u l ti su s e f u lf o rt h ed e s i g no f f u t u r es e a r c he n g i n e f o r x m l 5 ) w es t u d yan e w i n d e xs t p d c t u r e ，s t r u c t u r a lm a p ，f o re f f i c i e n te v a l u a t i o no f p a t h e x p r e s s i o n sq u e r i e so f x m l w ep r e s e n tac o s tm o d e lf o rt h es p a c ec o n s u m p t i o n o fi n d e x e sa n dt h e i r r e s u l t i n gb e n e f i t t ox m l q u e r i e s f o rag i v e nw o r k l o a d ，w e a d o p tg r e e d ya l g o r i t h mt os e l e c ts o m em a pi n d e x e st ob ec r e a t e d t h a ti s ，u n d e r c e r t a i nc o n s t r a i n to fd i s ks p a c e ，t h e s es e l e c t e dm a pi n d e x e sc a nb r i n gt h em o s t b e n e f i t t h i sr e s e a r c hp l a c eas o l i db a s ef o rd e s i g no f q u e r yo p t i m i z e ra n di n d e x o f x m ld a t a 4 第一章舞楚 1 1 觋究背景 第一章绪论 在过去的十年里，数据库研究在查询饯化、对象关系数据库、主动数据库、 并行数据艨和数据挖掘等领域取得了突破性的迸簏。许多研究成采已被成功地转 化到商业产品中。同时，在过去歉十年中，i n t e r n e t 技术和计算机硬件的发 展使得我们有必要迸一步拓展数褥库理论，研究新的问题，开发新酊技术。 今天，任何人都可以在国际互联网( w e b ) 上轻易地发布和获取信息，w e b 已经变成了信息制造、发布、加工和处理的主要平台。同时，随着因特网( i n t e m e t ) 的迅速发展，网站和静态h t m l ( h y p e r - t e x tm a r k u pl a n g u a g e ，超文本标记语 畜) 页面穗急尉膨胀，到1 9 9 9 年底，i n t c m e t 上静静态页黼有3 5 0 百万，黼时每 天以1 百万的速度增力l e c h a 9 9 ，信息的数星级从9 0 年代韧的m b 过渡到g b 、 现在己上努蜀啊l 。 面对庞大的信息海洋，人们却遇到了w e b 上的两大问题：一是i n t e m e t 速 凌援漫，礴对犹鲡爬行酶螨牛。二楚虽然w 菠在线获褥各稀信怠，僵是霎我翔掰 需要的信息常常极为困难。其中鼠然有硬件方面的原因，假是主要是由目前w e b 标注语言 疆琵l ，静毪瘊雩l 莛豹。 在今涎的w e b 环境中，h t m l 语言是w e b 信息表示的主要方式，由于h t m l 燹鬣缺乏结褐痿繇，尽管诲多离端羧务器采露数据痒来鲶瑾数键，瞧大靛w e b 站点和搜索引擎却主要用文件系统来存储信息，利用信息检索( i n f o r m a t i o n r e t r i e v a l ，簿穆致) 鼓本( 鲡：荚键字攘索) 来梭索静态豹嚣联毛夏瑟，效率 低下而且极不准确。随着w e b 页筒数量的快速增长，新的w e b 应用要求w e b 能 够管理动态豹内容，w e b 耀户霉娶在漕魏烟海豹w e b 蕊惑海洋孛快速、准确遮 发现所需的信息。 轶数援痒豹角发寒看，w e b ( 群数据露下熬w e b ) 恕w e b 上鹩数据终必宅管 联的对象，全球的w e b 就是一个人类有史以来最大的数据库，所以我们可以采 慰数撂疼技零管璞w e b 数据。除戴豁乡 ，对于w e b 数据黪理，还凌翅绩怠捡索、 人工智能、超文本超媒体等技术。其中，信息检索是目前大多数搜索引擎使用 的技术，它从页露艴蠹容寒检索蒜要豹更。这嚣畿豹区别见表1 1 。 袈l i 数据库技术与信息检索搜术比较 1数据痒信息捡素 |数据有结构无站构 i模型有确定的模型基于概率、向爨空间模趟等 |查诲语言 天王的( 懿s q l ) 蠡然憨 第一章绪论 匹配精确匹配部分匹配、模糊匹配 窭话掇告竣感懿不敏蕊 推理演绎归纳 数据更新完全支持不支持 事务支持不支持 使用面向应用面向人 随着电子数据数量的激增和w e b 规模的迅速增长，使用传统的基于关键字 魏信息捡繁方法农w e b 这样一令无限熬绩患海洋孛茬往会迷失方囊，悉户褥到 的是无穷咒尽的链接，且绝大多数链接所包含的文档并不包含用户所需骤的内 套，瑟曩户蠲为鼗耗费了大量魏辩溺莉金钱。嚣戴，在泰来熬w e b 发震孛，翔 何提高信息检索的准确性和效率成为关键问题。尽管h t m l 从发明以来，已成 为竣成功瓣电子发蠢语言，但是它仅注重傣息兹裘瑷形式，宅熬栋记仅仅发骧了 信息应该如何在页面上表现，而没有对信息本身进行描述，同时窀的标记集合是 露定豹，不能够投据霉要遴雩亍扩襞。随羞w e b 应臻的日藏广泛，它熬局羧性越 来越明显，已经不再适应下一代熙复杂的w e b 应用。 可扩溪标记谬言( 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 ) 豹出现泼变了 w e b 的基本面貌。1 9 9 8 年2 月，w 3 c ( 全球互联网联盟) 给出了其砸式的x m l t 0 版本，并正式接替x m l 墩为下一代互联网标准。与h t m l 相比，x m l 矮有谗 多优点： 1 ) x m l 简单，是我撼述且易于解析。锼褥x m l 具有帆器可 娶性，一个应用 可以按照各种方式解析、过滤、重构煳l 文档。 2 ) h t m l 中的标记是固定的，不能扩展，而x m l 的标记由用户定义，可以任 意逡扩袋+ x m l 懿嵌套结稳霹浚裹忝溪实毽赛孛各释复杂熬瓣象，务耱格 式的数据都可以比较容易地转化为x m l 数据，这使得叽非常适予w e b 信 息的发布和集成。 3 ) h t m l 中的标记表拳的是鼗獬的显示格式，没有任僻语义，i 自i x m l 的标记 则明确指出了数据的含义，使得细粒度的帆数据处理成为可能。 4 ) x m l 实瑰了内容、缨橡翻表埂三考豹分裹。文挡类型定义( d t d ) 攒述了 文档中元素和子元素间的嵌套结构，不同的用户可以通过x s l 按不同的显 示方式显示全部或部分的文档内容。 x m l 鸯发布鞋来受羁了各界的广泛关注。各计算耩l 厂赢们竟稻攉密了支持 x m l 的产品( 如：o r a c l e9 i 中的x m ls q lu t i l i t y ，m md b 2 中的x m l e x t e n d 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 r n e t s u p p o r t 等) ；学术和研究机构纷纷采用x m l 来表示各种科学数据，并展歼了对x m l 的 深入疆究。联合戮疆逐多鸯鞋大翻订全球毪x m l 蠡准静力发，它懿u n 雁d i f a c t 与o a s i s 组织共同发展了e b x m l 。各个行业如金融机构、海关、媒体产姚正制 第一章绪论 订各自行业的x m l d t d ( d o c u m e n t t y p e d e f i n i t i o n ，文档类型定义) ，以利于数 据阻公认的格式交换和集成。目前，i n t e r n e t 上已经满现了大量的x m l 页瑟、 站点和应用开发工具。可以预见，x m l 将成为w e b 信息发猫和交换的事实上的 标准。国外已形成了x m l 的一系列标准，如c x m l 、x c b l 、b i z t a l k 、e b x m l 。 在我国，中国科学院电子商务研究中心也正联合国内软件厂商制定c n x m l 标准。 总之，对x m l 的深入臻究将有力促进企业的痿惑化和电子商务，具有巨大的应 用前景和经济效益。 在x m l 引起的w e b 变革中，数据库技术将扮演关键的角色。从数据处理的 角度来说，传统的w e b 信虑处理主要采用的是倍患检索技术。检索信患的主要 方式是关键字搜索。关键字搜索极不准确，检索的结果将返回包禽关键字的整个 文档，网络传输量大。x m l 使得我们可以采用数据库技术来存储、检索、分析、 加工和处理w e b 信息。具体地说： 1 ) 可以饺用类似于数据库麴查谗语言的方式来检索x m l 文挡，搜索引擎的功能 将变的更加强大而准确。如：通过x m l 搜索引擎，我们可以进行诸如“搜索 房价低予4 0 0 豹饭店名”的检索。眨外，查询结果将只返犀与壹诲匹配数部 分而非整个文档，大大降低了网络传输摄。 2 ) 传统的w 曲信息管理主簧处理的是静态的w e b 页瑟，稠用数据库中的成熟技 术可以保证动态更新的w e b 页面的数据一致性。 3 ) 利用数据库技术可以及时、有效地分析和加工在线的x m l 数据，从中发现有 用的知识，辅助企业决策。 1 2 研究现状 x m l 与传统数据库中的结构化数据不同，x m l 数据是自我描述的，没有预 先固定的模式。x m l 与数据库界近年来研究的半结构化数据( s e m i s t r u c t u r e d d a t a ) 【b u n 9 7 ，s u c 9 8 】极为相似。半结构忧数据已毒豹理论和原型系统可以作为 x m l 研究的基础。同时，x m l 所具有的独特特性又为我们带来了新的研究课题。 由于x m l 与半结构化数据的相似性，人们可以将x m l 看作是半结构化数 据的标准，并借黎半结构化数据的研究成果来管理x m l 数据。琶前，数据库赛 在半结构化数据豹硬究方面已取得了定的进展。这包括数摆摸_ v d p g w 9 5 ，查 询语言 b f s 0 0 ，g w 9 7 ，半结构化的模式 g w 9 7 ，查询和查询优化技术i f m l 9 9 ， h g i + 9 5 ，m w 9 9 a , b d h + 9 6 】，索引技术 m w a + 9 8 ，m s 9 9 a 。半结构化路径约束 【b f w 9 8 ，a v 9 7 ，f a n 9 9 ，半结构纯中闻件和程图机带t j l y v + 9 8 ，n i p q + 9 7 ，p v 9 9 】， 半结构化模式抽取 a a c + 9 9 ，n a m 9 8 ，m s 9 9 b 1 ，半结构化数握管理系统 q w c j + 9 6 h g i + 9 5 ，m a g + 9 7 ，w e b 站点管理 f y l + 9 9 ，f y v + 0 0 ，f f k + 9 8 等。关于半结构 化数据研究的综述见 b u n 9 7 ，a b i 9 7 1 。 第一章绪论 但是，目前的半结构化数据的研究尚不成熟，并且x m l 与半结构化数据相 比又存在一些差别，这主要表现在：从数据特点上看，x m l 文档中的元素有次 序，x m l 文档可带有描述其结构的d t d ；从应用领域来说，x m l 不但被用于 表示w e b 数据，也面向电子数据交换。因此，需要对x m l 数据作进一步深入的 研究。自x m l 标准发布以来，x m l 已经引起了的数据库研究者们极大的兴趣， 成为近年来的s i g m o d 、v l d b 、i c d e 和p o d s 等数据库的顶级会议的研究热 点。而在这些会议录用的论文中，有1 4 至1 3 的论文研究x m l 的相关问题。 国外的许多大学、研究机构和各种基金都已经或正在开展x m l 数据处理技 术的研究。目前国际上正在开展的x m l 数据管理的主要研究项目如表1 2 所示。 另外，i b m ，m i c r o s o f t ，o r a c l e 等各大数据库厂商的研究机构也都有对x m l 技术 的专项研究( 未在表l _ 2 中列出) 表l 2 罚曝管理的研究项目 目前，在x m l 数据管理方面需解决的前沿问题主要有： x m l 数据的存储机制。x m l 的数据存储是处理x m l 数据的首要问题。x m l 的主要存储方式为文件系统 t d c + 0 2 】，关系数据库 s k w + 0 0 ，z n d + 0 1 ，f k 9 9 ， g t z + 9 9 ，m f o + 0 0 】，面向对象数据库 k m 0 0 ，a c c + 9 7 和半结构化数据仓库 【g m w 9 9 等。 x m l 数据的查询和查询优化技术 f d f + 9 9 ，m w 9 9 b 。x m l 数据的查询优化 第一章绪论 的研究包括：优化正则路径表达式，基于约束的x m l 查询优化和在w e b 环境下 的分布式查询优化等。 x m l 视图。在w e b 环境下，x m l 视图显得比传统数据库中的视图更加重要 【a b i 9 9 。面向电子商务应用，需要建立x m l 的主动视 a a c + 9 9 。 x m l 数据交换和翻译 a c m 0 0 1 。在电子信息发布领域，需要将传统数据或 h t m l 文档转化为x m l 格式发布 s a 9 9 1 。而面向电子数据交换，则需要能够自 动地将符合一个d t d 规范的文档转化为符合另一个d t d 定义的文档的工具 【m s v 0 0 。 大规模的x m l 文档的检索。在w e b 环境下，x m l 文档将是大批量的。搜 索大规模的x m l 文档需要结合数据库和信息检索两方面的技术。大规模的x m l 文档的检索技术将构成未来x m l 搜索引擎的基础。w i s c o n s i nm a d i s o n 的研究者 己开始了这方面的初步探索 c d t + 0 0 ，i n r i a 的x y l e m e x y l 0 1 i 程也致力于同 样的目标。 基于x m l 的数据集成。x m l 使得通过统一的x m l 格式访问各种格式的w e b 信息成为可能。在x m l 数据集成方面已经有了一些深入的研究 b g l + 9 9 ， f y v + 0 0 ，z l z + 0 1 。 x m l 数据压缩。有效的x m l 数据压缩工具将有效地降低x m l 数据的网络 的传输量。在这方面，a t & t 和p e n n s y l v a n i a 大学已开发出了一个有效的x m l 压缩工具x m i uf l s 0 0 1 。 x m l 的约束。有效的约束关系研究将更好地优化对x m l 的各项处理。b e l l 实验室的樊文飞博士开创并建立了x m l 完整性约束理论，在国际上第一次提出 了x m l 完整性约束理论及x m l 约束的推理体系 b d f + 0 1 。提出了x m l 的主 键的描述语言及其推理系统 d f h 0 3 1 。该语言有效地将关系数据库的规范化理论 和不规则的x m l 数据和谐地结合在一起，为x m l 数据的语义描述、存储、索 引及更新奠定了基础，并提出了将x m l 键约束映射到关系数据库上的相应算法。 下面我们针对本论文所涉及的几个研究方面详细介绍当前的研究状况。 1 2 1x 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 文档解析( p a r s e ) 为内 第一章绪论 存中耱d o m 搪缝穗。基于交 牛戆x m l 系统篱莩著容荔实联，无甏使蔫庆瀑垂冬 数据库或对象存储管理，同时，由于x m l 文档被直接存储为文本文件，这种存 德方式无震菇储转换髑菱搀焱诲缝暴。毽是这耱存嬉方式在套谗憝瑾方瑟氇存在 明显的弱点，首先，该方法在每次浏览和查询文档时都要重复地解析文档。其次， 整个文槎在套诲楚理i 熏程中都要驻鬟内存。尽罄我霞哥以在肉枣中为文挡建立索 引，通过索引来定位煮询所需的部分，维护邋种索引的代价仍十分昂贵。 纂二秘是采用半缝枚亿数据仓露枣罐和蛰理x m l 数据。由于x m l 数攒与 半结构化数攒十分相似，利用半结构化数据仓库来管理x m l 数据似乎是一种比 较鸯然的方式。在这糖方法中，x m l 数据被聚簇存撩为夺肉图。鬈埏禳大学戆 l o r e 项目在避方面作了初步的尝试f g m w 9 9 。然而，当前的半结构化数攒库 技术尚不成熟，利用攀结构化数据仓辉( 如：l o r e m a g + 9 7 鲅s t r u d e l f f k + 9 8 ) 处理x m l 查询的性熊仍然滩以让人满意 z l z + 0 1 1 。 第三种熨有效的存健方式是使用数据库镂理系绕寒管理x m l 数攮。攘搬数 据库管理系统的不同，这种存储方式又可以分为基于关系的x m l 数据库系统、 基于颓向对象的x m l 数据廖系统和“原生( n a t i v e ) ”的) q “l 数据库系绫。 在这三种方式中，由于当前的蕊向对象数据库系统的饿能仍不足以支持对大规模 数据的复杂查询。基予关系数据库的煳l 存储管理是一种较有前景的方式。按 照将x m l 数据转存为关系静映射方式的不间，我们又可以将基于美系的x m l 数据存储分为两类：第一类方法将x m l 文档树中的结点和边映射为关系模式， 得蜀虢存储模式与x m l 文档的结构无差，我们将冀称作独立于文档 ( d o c u m e n t - i n d e p e n d e n t ) 的关系存储；第二类方法根据x m l 的结构( d t d 或 x m l s c h e m a 【s c h 0 1 ) 来生成关系模式，不翮豹文档舆有不黼的存储模式，我们 将其称作依赖于文档( d o c u m e n t - d e p e n d e n t ) 的关系存储。在 y a s + 0 1 】中， y o s h i k a w a 等将这两謦孛方式分巍称为罄于模黧( d o m ) 帮基予结 訇瀚存储方法。 最后一种存储管理i 。数据的方法被称为“原嫩( n a t i v e ) ”的x m l 数 据痒系统 b o u 0 0 a ，b o u o o b 。嚣生豹x m l 数疆淳豹主要孪謦赢努下：i ) 颤菜 种( 逻辑) 模溅( 如：x p a t h 模型或d o m 模溅) 为熬础来存储和检索x m l 数 据；2 ) 戮文糖俸菇数据楚遴戆基本攀霞；3 ) 不要求有菜静特定静物理存德模 型，可以建立在数据滕系统、对象管联器( 如：s h o r e 【c d n + 9 4 】) 或文件系统之 上。逡来毒瑗了一些这撵豹数撰疼系统，翔：t a m i n of a m i n o 。与莛它静存褚 方式相比，原搬的x m l 数据库可以完整地保昭x m l 文档的信息，存储映射时 不蔫要d t d 绫梅。嗣对，爨垒懿躐鼗豢疼采爱蘩予x m l 豹查谗赛瑟，妇： x p a t h 或d o m ，适合于x m l 本身的特点。然而，原生的x m l 数据库缺芝细 粒瘦熬数据处瑗戆力，不适含予处理数据集中( d a t a - c e n t r a l ) 静x m l 文档。霜 1 0 第一章绪论 时，这样的系统还不成熟，数据处理的效率也差强人意。 利用数据库系统，特别是关系数据库系统，来处理x m l 数据的方式具有如 下的优点：一方面，当前的关系数据库的技术已十分成熟，裔用的关系数据库系 统都具有赢性能的套询引擎，良好的霹扩展牲、安余性和健、挂性，因此，零n 用关 系数据库系统管理x m l 数据可以重用数据库的查询优化器和事务处理机制，能 够保证x m l 数据的一致性和完整性；另一方面，目前大量的w e b 数据主要存 放1 谯关系数据痒孛，采用x m l 关系系统便于在关系数撂库上建立遗于二者豹应 用，使关系数据库进入w e b 领域成为可能。但是，由予数据模型上的差异，利 用数据库系统来管理x m l 数据也给数据库技术带来了许多新的挑战。近来，基 于关系的x m l 数据处理技术受到了研究者和数据岸厂商的关注，在这方面已经 有了许多工作秘成果。在 t d c + 0 2 中，t i a n 等比较和分析了5 种x m l 的不网 的存储方式，包括文件系统，关系存储和基于对象的存储系统等，处理x m l 数 据的性能。他们的研究结果表明，基于关系韵存储方法( d t d 映射) 具有最好 的性能。这些研究的结采均表瞬，基于关系豹x m l 数据处理是一种可行的方式。 我们姆在下一带中对基于关系的x m l 数据存储技术馋雯详细的介绍。 1 2 2 基于关系的x m l 数据存储技术 如前所述，利用关系数据库来存姥和查询处理x m l 是一种可行且有极佳前 景的方式，然而，x m l 数据和关系数据在模型上存在较大差异。首先，从数据 模型上来看，二者具有不同的数据模型：x m l 数据是有序的，嵌套的树闼结构， 雨关系模藿是无序的二维表结构；其次，x m l 是半结构化数据，x m l 可以没 有预定的模式( d t d 或x m ls c h e m a ) ，露关系数据具蠢模式，所有的关系数 据必须符合于某个给定的关系模式，关系模式在数据存储和查询处理中具有重要 的作用；第三，从查询语言上来说，x m l 查询语言 b c o o ，l c 0 0 包括数据绑定 积结构重构两个部分，查询语言的基本成分是燕到路径表达式，孺关系数据库的 查询语言是s q 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 转换为关系数 第一章绪论 据库的各种映射方法 d f s 9 9 ，s t z + 9 9 ，f k 9 9 ，s k w + 0 0 ，y a s + s 0 1 。其中，【f k 9 9 ， s k w + 0 0 ，y a s + 0 1 】是独立于文档的存储方法，而 s t z + 9 9 和 d f s 9 9 是依赖于文 档的存储方法。f l o r e s c u 和k o s s m a n 在 f k 9 9 1 中提出了两种独立于文档的存储方 法：e d g e 和b i n a r y 方法。e d