（计算机软件与理论专业论文）无缝集成关系数据库的原生xml查询引擎设计与实现.pdf

南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位 获得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文 ( 包括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论 文，并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将 公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检 索、文摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向 教育部指定单位提交公开的学位论文：( 4 ) 学位论文作者授权学校向中国科技信息研究所和 中国学术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文 数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：# 2 0 2 11 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答 辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 王亟蕉 2 0 1 0 年5 月2 6 日 南开大学研究生学位论文作者信息 论文题目无缝集成关系数据库的原生x m l 查询引擎设计与实现 姓名 王敏辉学号 2 1 2 0 0 7 0 3 0 2 答辩日期2 0 1 0 年5 月2 1 日 论文类别博士口学历硕士团硕士专业学位口高校教师口同等学力硕士口 院系所信息技术科学学院专业计算机软件与理论 联系电话 1 3 8 0 3 0 2 5 1 9 3e m a i l w a n g m h r l l ( 12 6 t o m 通信地址( 邮编) ：天津市卫津路9 4 号南开大学伯苓楼东区3 0 9 ( 3 0 0 0 7 1 ) 备注：是否批准为非公开论文 否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所 取得的研究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包 含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本 学位论文原创性声明的法律责任由本人承担。 学位论文作者签名：王筮龌2 0 1 0 年5 月2 6 日 非公开学位论文标注说明 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申 请和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本 说明为空白。 论文题目无缝集成关系数据库的原生x m l 查询引擎设计与实现 申请密级 口限制( 2 年)口秘密( 1 0 年)口机密( 2 0 年) 保密期限 2 0 年月日至2 0年月日 审批表编号批准日期 2 0 年月日 限制2 年( 最长2 年，可少于2 年) 秘密l o 年( 最长5 年，可少于5 年) 机密2 0 年( 最长1 0 年，可少于1 0 年) 摘要 摘要 x m l 己成为w e b 上表示和交换数据的标准格式。随着x m l 技术的不断发 展和完善，涌现出大量x m l 文档。如何有效管理大规模x m l 数据，如何对x m l 数据进行高效的查询，已成为当前数据库技术领域的一个重要课题。 传统关系数据库由于数据模型的差异而无法胜任大规模x m l 数据管理工 作，而原生x m l 数据库需要完全重新实现关系数据库已非常成熟的理论和技术， 造成人力和物力上的巨大浪费。本人所在实验室承担的国家8 6 3 目标导向课题 “无缝集成关系数据库引擎研制与关键技术研究 提出了“在传统关系型数据 库中无缝集成x m l 数据管理引擎 的解决方案，本文的主要工作是基于该方案 设计了原生x m l 查询引擎，实现了x m l 数据查询功能。 在存储方案奠定的基础上，本文在关系数据库p o s t g r e s q l 中无缝集成了原 生x m l 查询引擎，实现x m l 查询处理功能。本文总结了建立该查询引擎的三 方面工作：第一，制定遵循s q l x m l 标准的查询语句，符合关系数据库用户使 用习惯；第二，在查询引擎各组件层面上实现与关系数据库查询引擎的无缝连 接，不影响原关系数据库的查询性能；第三，实现w 3 c 推荐的x m l 查询语言 x q u e r y ，包括f l w o r 表达式、路径表达式、比较表达式、内置函数等，为用 户提供丰富的x m l 查询功能。 在x p a t h 路径表达式求值方面，学习和分析了现有的结构连接算法，并在 此基础上提出一种基于多索引结构的x m l 查询处理方法，该方法对路径表达式 进行分割，对含有连续“父亲孩子”轴值的路径片段利用路径索引直接获得结 果，最大程度上减少了结构连接的次数，从而有效减少了结构连接中比较操作 的c p u 时间开销和读取节点的磁盘i o 开销。实验表明，该算法与传统算法相 比，查询性能提高了数倍，且随着数据规模的增大，性能的提升更加明显。 关键字：关系数据库x m l 查询处理x q u e r yx p a t h 求值 a b s t r a c t a b s t r a c t x m lh a sb e c o m et h ed ef a c t os 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 gd a t ao n t h ew e b w i t ht h ed e v e l o p m e n ta n di m p r o v e m e n to fx m lt e c h n o l o g y , al a r g ea m o u n t o fx m ld o c u m e n t sa r ee m e r g i n gs ot h ee f f e c t i v em a n a g e m e n to fl a r g er e p o s i t o r i e so f x m ld a t aa n dt h ee f f e c t i v ex m lq u e r yp r o c e s s i n gh a sb e c o m ep o p u l a rr e s e a r c h i s s u e si nt h ed a t a b a s ec o m m u n i t y t r a n d i t i o n a lr d b m s sc o u l dn o tb ec a p a b l e o f l a r g e s c a l ex m ld a t a m a n a g e m e n tb e c a u s eo ft h ed i f f e r e n c e sb e t w e e nt h et w od a t am o d e l s ，a n dn a t i v e x m ld a t a b a s e sh a v et or e i m p l e m e n tm a t u r et h e o r i e sa n dt e c h n o l o g yi nr d b m s ，s o h o wt oi n t e g r a t ean a t i v ex m le n g i n ei n t oar e l a t i o n a ld a t a b a s ei sb e c o m i n gaf o c u s o fr e s e a r c h i n g t h e 8 6 3 p r o j e c tt a k e nb yt h ea u t h o r sl a b o r a t o r yp r o p o s e sas o l u t i o n t os e a m l e s s i n t e g r a t en a t i v ex m le n g i n ei nt r a n d i t i o n a lr d b m s s t h em a i nw o r ko f t h i sp a p e ri st od e s i g nan a t i v ex m l q u e r ye n g i n eb a s e do nt h i ss o l u t i o n , a c h i v i n g t h e q u e r yp r o c e s s i n g o nt h eb a s i so ft h es t o r a g es c h e m e ，t h i sp a p e rs e a m l e s s i n t e g r a t e san a t i v ex m l q u e r ye n g i n ei n t ot h er e l a t i o n a ld a t a b a s ep o s t g r e s q l ，a c h i v i n gt h eq u e r yp r o c e s s i n g t h i sp a p e rs u m m a r i z e st h r e em a i nt a s k si nb u i l d i n gu pt l l ex m lq u e r ye n g i n e f i r s t ， d e s i g n i n gt h ef o r mo ft h eq u e r y , w h i c hf o l l o w st h es t a n d a r do fs q l x m la n da l s o m e e t st h eu s e r s h i b i t s s e c o n d ，i n t e g r a t i n gx m lq u e r yf u n c t i o ni ne a c hc o m p o n e n t o ft h ep o s t g r e s q l sq u e r ye n g i n e ，w i t h o u ti m p a c t i n go r i g i n a lr a t i o n a ld a t a b a s eq u e r y p e r f o r m a n c e t h i r d ，i m p l e m e n t i n gt h ew 3 cr e c o m m e n d e dq u e r yl a n g u a g ex q u e r y , i n c l u d i n gf l w o re x p r e s s i o n ，p a t he x p r e s s i o n , c o m p a r i s o ne x p r e s s i o n ，a r i t h m e t i c e x p r e s s i o na n db u i l t i nf u n c t i o n se t c ，p r o v i d i n ga b u n d a n tq u e r y f u n c t i o n sf o ru s e r s i nt h ea s p e c to fx p a t he v a l u a t i o n ，o nt h eb a s i so fr e s e a c h i n go fs t r u c t u r a lj o i n a l g o r i t h m ，t h i sp a p e rp r o p o s e s aq u e r yp r o c e s s i n gm e t h o db a s e do nt h ei n d e x s t r u c t u r e s t h em e t h o dd i v i d e st h ep a t he x p r e s s i o na n du s e sp a t h i n d e xt od i r e c t l y g a i nq u e r yr e s u l to nt h ef r a g m e n tw h i c ho n l yh a sc o n s e c u t i v e c h i l d a x i s ，a v o i d i n g t h eu n n e c e s s a r ys t r u c t u r a lj o i no p e r a t i o n s ，s ot h ec o s to fc p ur a nt i m ea n di o i i a b s t r a c t d e c r e a s e ss i g n i f i c a n t l y t h ee x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mi m p r o v e st h e e v a l u a t i o ne f f i c i e n c yo fx p a t he x p r e s s i o nb ys e v e r a lt i m e s w i t ht h ei n c r e m e n to ft h e x m ld a t as c a l e ，t h ei m p r o v e m e n tb e c o m e sm o r ea n dm o r en o t a b l e k e yw o r d ：r e l a t i o n a ld a t a b a s e ，x m lq u e r yp r o c e s s i n g ，x q u e r y , x p a t he v a l u a t i o n i i i 目录 目录 摘要i a b s t r a c t i i 第一章绪论1 第一节研究背景1 第二节研究内容和主要工作3 第三节论文的组织结构3 第二章x m l 数据存储方案5 第一节x m l “使能”数据库5 第二节原生x m l 数据库5 第三节无缝集成关系数据库的x m l 存储方案6 2 3 1x m l 逻辑数据模型7 2 3 2 无缝集成关系数据库的存储方案1 0 第四节本章小结1 2 第三章x m l 查询语言1 4 第一节x q u e r y 查询语言1 4 3 1 1 基本概念。l5 3 1 2x q u e r y 表达式15 第二节x p a t h 路径表达式17 3 2 1x p a t h 节点类型1 7 3 2 2x p a t h 轴值18 3 2 3x p a t h 路径表达式结构1 9 第三节本章小结2 0 第四章查询引擎设计方案21 i v 目录 第一节p o s t g r e s q l 查询引擎结构2 1 4 1 1p o s t g r e s q l 查询引擎结构2 2 4 1 2p o s t g r e s q l 对x m l 的支持2 4 4 1 3l i b x m l 2 简介2 5 第二节无缝集成p o s t g r e s q l 的查询引擎设计。2 6 4 2 1 无缝集成p o s t g r e s q l 的x m l 查询语句形式2 6 4 2 2 查询引擎各组件的无缝集成2 7 第三节本章小结3 6 第五章x q u e r y 实现方案3 7 第一节x p a t h 路径表达式的实现3 7 5 1 1x p a t h 求值方法3 7 5 1 2 结构连接算法。3 9 5 1 3 基于路径索引的x p a t h 求值。4 2 5 1 4 实验分析4 8 第二节f l w o r 表达式的设计与实现5 2 5 2 1f l w o r 表达式的解析5 3 5 2 2f l w o r 表达式的形式转换5 5 5 2 3f l w o r 表达式的执行5 6 第三节内置函数的实现5 7 第四节本章小结6 0 第六章总结与展望6 1 第一节全文总结61 第二节展望61 参考文献6 3 致 射6 6 v 目录 个人简历及在学期间发表的学术论文与研究成果6 7 v i 第一章绪论 第一章绪论 x m l 是w 3 c 组织推荐的一种通用标记语言。它凭借可自描述、扩展性高、 半结构化、具有层次结构等特点，已成为w e b 应用程序中表示和交换数据的标 准格式。x m l 一经出现就展现了其在数据存储、数据交换方面的显著优势，因 而迅速成为一个与平台厂商无关的统一的数据格式标准，使其在电子商务、w e b 服务等诸多方面得到了广泛的应用。随着x m l 技术的不断发展和完善以及大量 x m l 文档的出现，如何有效管理大规模x m l 数据，如何对x m l 数据进行高效 的查询已经成为当前数据库技术研究领域中一个重要的课题。 第一节研究背景 w 3 c 组织制定的可扩展标记语言uj ( e x t e n s i b l e m a r k u p l a n g u a g e ，简称x m l ) 已成为w e b 应用程序中表示和交换数据的标准格式，在电子商务、w e b s e r v i c e s 、 政务文档、医疗记录、图书情报、学科标记语言等领域都可以看到x m l 的相关 应用。随着x m l 标准的不断推广，越来越多的行业推出了基于x m l 标准的适 用于各自领域的子语言，如用于编写w e b 页面的x h t m l ，用于编写数学公式 的m a t h m l ，用于描述生物高分子结构的b i o m l ，以及用于表示基因序列信息 的b s m l 等。随着w e b 上越来越多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 数据模型特有的树形结 构，从而导致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 数据。因此，x m l 查询处理成为近几年数据库领域的一个研究 热点。在研究者们提出的众多x m l 查询语言中，x p a t h 2 】和x q u e r y 3 】脱颖而出， 并最终成为w 3 c 的推荐标准。x p a t h 可以作为x m l 查询语言单独使用，x q u e r y 是x p a t h 的扩展版本，它在x p a t h 的基础上增加了f l w o r 表达式等内容，功能 更为强大且语法形式简洁易懂。要提供丰富便捷的x m l 查询功能，就要实现这 两种x m l 查询语言。 x q u e r y 和x p a t h 这两种标准查询语言均使用路径表达式作为在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 0 0 9 年初承担了国家8 6 3 4 j 目标导向课题无缝集成 关系数据库引擎研制与关键技术研究( 2 0 0 9 a a 0 l z l 5 2 ) 。课题提出了“在传统 关系型数据库中无缝集成x m l 数据管理引擎 的解决方案，既体现x m l 数据 模型，解决了x m l “使能 数据库的一系列弊端，又重用关系数据库已有的基 础模块，避免了大量的重复性工作。 2 0 0 9 年4 月至今，笔者作为查询与优化子课题组成员，参与了该课题的研 发工作，负责在关系数据库中无缝集成原生x m l 查询引擎的设计与实现。目前 本子课题组已发表论文一篇、专利一篇，本文的研究内容即为该课题工作的一 部分。 2 第一章绪论 第二节研究内容和主要工作 本文以开源数据库p o s t g r e s q l 为研究对象，分析p o s t g r e s q l 查询引擎结构， 设计在p o s t g r e s q l 中无缝集成原生x m l 查询引擎的方案。学习和分析x q u e r y 标准，研究基于多索引结构的x m l 查询处理方法。主要研究工作包括以下几方 面： 分析在p o s t g r e s q l 中存储x m l 数据的方法； 剖析p o s t g r e s q l 源码，分析p o s t g r e s q l 查询引擎结构及现有对x m l 的支持，学习现有x m l 查询的实现方式； 学习x p a t h 2 0 及x q u e r y l 0 标准，确定查询语句的语法形式，设计在 p o s t g r e s q l 中无缝集成原生x m l 查询引擎的方案； 在p o s t g r e s q l 查询引擎各组件中添加对x m l 的支持，实现x q u e r y l 0 的核心功能，包括f l w o r 表达式、路径表达式、算术表达式、比较表 达式、内置函数等； 阅读结构连接相关论文，学习结构连接算法，充分利用数据库底层为 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 q u e r y 和x p a t h 的基本知识； 第四章，剖析p o s t g r e s q l 数据库管理系统中查询引擎的结构及对x m l 的 支持情况，设计了无缝集成关系数据库的原生x m l 查询引擎； 第五章，介绍x q u e r y 查询语言的具体实现方案。在学习x m l 结构连接算 3 第一章绪论 法的基础上，提出一种充分利用多索引结构的x m l 查询处理方法，并设计实验， 分析该方法对查询性能的提升。 第六章，总结全文工作内容，为后续研究提出了建设性意见。 4 第二章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 数据存储方案进行简要介绍。 第一节x m l “使能”数据库 x m l “使能”数据库是在传统关系数据库管理系统的基础上扩展x m l 处理 功能而形成的，通常采用的方式是将x m l 数据拆分并映射为多张关系表，试图 以关系模型存储x m l 数据。该方法将x m l 查询转换为关系表上的s q l 查询， 在一定程度上确保了数据查询性能。但是，表映射不可避免地破坏了x m l 数据 模型自身的树形结构，带来的问题包括： 将x m l 数据拆分为关系表会造成某些x m l 重要语义的丢失，例如x m l 节点顺序； 将x m l 查询转换为s q l 查询会造成x m l 查询操作表达能力的下降 ( x m l 查询语言的表达能力一般会强于s q l ) ； x m l 查询和x m l 文档重建操作所需的大量关系表连接运算会造成系统 性能的严重下降。 可见，使用表映射方法管理x m l 数据时，在存储、查询和导出过程中，会 涉及到x m l 文档与关系表、x m l 查询与s q l 查询之间的多重转换，造成语义 丢失和性能下降。以上问题的根本原因在于关系数据模型与x m l 数据模型不相 匹配。 第二节原生x m l 数据库 原生x m l 数据库以x m l 数据模型为中心，具有为x m l 量身定做的存储 5 第二章x m l 数据存储方案 方案、索引结构和查询引擎，用更加自然的方式管理x m l 数据。目前已经出现 了一些原生x m l 数据库的原型系统，例如德国曼海姆大学的n a t i x l 5 j 系统、美国 密歇根大学的t i m b e r t 6 j 系统、德国人w o l f g a n g 领导的小组开发的e x i s t l 7 1 系统、 中国人民大学的o r i e n t x 系统【8 】以及南开大学数据库与信息系统实验室的 x n a t i v e 原生数据库管理系统【9 j 等。这些系统从底层的存储设计、索引的建立、 事务机制等都是为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 数据的管理。 第三节无缝集成关系数据库的x m l 存储方案 本人所在实验室在多年对x m l 技术进行研究的基础上，创新性的提出了无 缝集成关系数据库的x m l 存储方案，在关系数据库中增加对x m l 的支持，既 体现x m l 数据模型，又重用关系数据库已有的基础模块。该方案的核心思想是 借助有效的编码方案，利用关系表保存x m l 节点数据，并在此基础上实现对关 系数据库其他模块的无缝集成及复用。由于x m l 查询引擎的设计和实现要以 x m l 数据存储方案的基础，因此，本小节中的剩余内容将对该存储方案进行简 要介绍。 6 第二章x m l 数据存储方案 2 3 1x m l 逻辑数据模型 x m l 文档是半结构化层次型数据，在不考虑特殊属性i d r e f 的情况下，其 数据模型通常被抽象为有序标签树( 1 a b e l e do r d e r e dt r e e ) 。w 3 c 先后推出的几个 规范可以被认为是对x m l 数据模型的非形式化描述，其中，文档对象模型 d o m 1 0 】( d o c u m e n to b j e c tm o d e l ) 定义了x m l 文件的逻辑结构以及访问和处 理x m l 文件的一系列标准方法，是w 3 c 组织的推荐标准。d o m 模型将x m l 文档表示为一种层次树状结构，通常称为d o m 树。由于x m l 文档本身具有的 层次结构，这种描述x m l 文档的方法是自然且有效的。在d o m 树中，x m l 文档的每个成分都被视为一个节点，即d o m 提供一个节点容器并强制x m l 文 档以树型结构存储到该容器中。利用d o m 提供的标准接口，应用程序可以方便 的实现对任意d o m 树节点的存取，从而达到访问x m l 文件的目的。 定义2 1x m l 数据模型 一篇x m l 文档d 可表示为一棵有序标签树t = ( k1 0 ，t y p e ，t a g , v a l , 若1 ，为元素节点，则t y p e ( v ) = e l e m e n t ； 若1 ，为属性节点，则t y p e ( v ) = a t t r i b u t e ； 若v 为文本节点，则t y p e ( v ) = t e x t ； 圪= vl1 ，v t y p e ( v ) = e l e m e n t 表示元素节点集合； 圪= 巧= vv v t y p e ( v ) = t e x t 表示文本节点集合。 函数t a g ( v ) v v 圪o r , ，返回元素节点或属性节点的标签名称； 函数v a l ( v ) v v v o o r , ，返回属性节点或文本节点的值，该值为字符串 形式； 二元关系 缸定义x m l 文档序，在文档d 中，如果节点u 出现在节点1 ， 之前，则记作u d o e l ，。 定义2 1 给出了x m l 数据模型的形式化描述。该定义只涉及构成x m l 文档 7 第二章x m l 数据存储方案 的最基本数据：元素、属性和文本，而忽略了处理指令、注释等。在x m l 文档 中，每个节点1 ，都被赋予唯一的标识，称为节点i d 。节点i d 除起到标识节点的 作用外，还应该能够确定该节点与本文档中任意一个节点之间的结构关系，如 祖先后裔关系、父子关系、兄弟关系等，这样的节点i d 称为智能节点i d 。能够 实现该功能的具体编码方案有很多种，如d e w e y l d 1 1 1 、o r d p a t h 1 2 1 、d l n t l 3 】 等，本存储方案中采用d l n 编码方案对节点进行编码，因此将节点i d 命名为 d l n l d o 下面以图2 1 所示的x m l 文档b o o k s x m l 为例，说明如何用x m l 数据模型 描述一篇x m l 文档。该文档为一个图书列表 ，每本图书 具有书名 、作者列表 、出版年份 、售价 等信息，作者列表包 含多个作者 信息，每本图书有分类信息c a t e g o r y 等。图2 2 给出了该文 档的树型结构。 例2 1 给出x m l 文档b o o k s x m l 的x m l 数据模型 对于图2 1 中给出的x m l 文档，根据定义2 1 中的x m l 数据模型，其各个 分量为： v 2 l ，1 1 ，1 1 1 ，1 2 ，1 3 ) ； v 0 21 ： = b i b ，b o o k ，t i t l e ，a u t h o r s ，a u t h o r , y e a r , p r i c e ，c a t e g o r y ) ； t y p e ( 1 ) = e l e m e n t , t y p e ( 1 1 1 ) = a t t r i b u t e ， t y p e ( 1 1 2 2 ) = t e x t , t a g ( 1 ) = b i b ， t a g ( 1 1 ) = b o o k ， v a l ( 1 1 1 ) = ”c o o k i n g ”， v a l ( 1 1 2 2 ) = ”v e r y d a yi t a l i a n ， 1 缸1 1 ， 1 1 缸1 1 1 ， 8 第二章x m l 数据存储方案 图2 1x m l 文档b o o k s x m l 9 第二章x m l 数据存储方案 m c g o v e mb o t l m e r o 元素 属性 文本 图2 2x m l 文档的树型结构 对于x m l 文档中的每个节点，同样可以按照类似的方法，将其表示为如定 义2 2 所示的四元组形式。该节点模型也是利用关系表存储x m l 节点的基础。 定义2 2x m l 节点模型 x m l 文档中的每个节点v 都可由四元组( d l n i d ，t a g , t y p e ，v a l ) 来描述。四 元组中各个分量定义如下： d l n i d 节点i d ，是节点的唯一标识，本文中采用d l n 编码； t a g ：即函数t a g ( v ) 的返回值，表示节点的标签名称； t y p e ：即函数t y p e ( v ) 的返回值，表示节点类型； v a t ：即函数v a t ( v ) 的返回值，表示节点的值。 2 3 2 无缝集成关系数据库的存储方案 本课题设计的存储方案中以增加x m l 数据类型的方式来体现对x m l 的支 持。x m l 类型中的两个关键字段为r e l a t i o n l d 和d o c l d ，其中r e l a t i o n l d 为数据 库中存储x m l 节点信息的关系表的唯一标识，d o c l d 用于标识关系表中所存储 的x m l 文档。x m l 类型的使用方法与i n t 等内置数据类型相同。 例2 2 创建包含x m l 数据类型的普通关系表 1 0 第二章x m l 数据存储方案 c r e a t et a b l eb o o k s t o r e b o o k s t o r e l d b o o k s t o r e n a m e b o o k s s o l d i m ， n v a r c h a r ( 5 0 ) ， x m l ) 上述s q l 语句创建了普通关系表b o o k s t o r e 。该表中除h n 类型的 b o o k s t o r e l d 字段和n v a r c h a r 类型的b o o k s t o r e n a m e 字段外，还声明了x m l 类 型的b o o k s s o l d 字段。在创建b o o k s t o r e 表的同时会创建一个用来存放x m l 节 点信息的普通关系表，该表称为x m l 节点表，x m l 节点表的唯一标识记作 r e l a t i o n l d 。在向b o o k s t o r e 表中插入一条记录时，会将b o o k s s o l d 字段的内容按 照x m l 的方式进行解析并存储在x m l 节点表中。因为每个x m l 节点可由定 义2 2 中的四元组来表示，所以，x m l 文档可以很自然地打散后存储在x m l 节点表中，而又不丢失节点间的结构信息。 向b o o k s t o r e 表插入数据时，插入到b o o k s s o l d 字段的x m l 文档会被分配 一个文档标识d o c l d ，以d o c i d 为前缀对文档中的每个节点进行d l n 编码( 文 档根节点的d l n i d 为d o c l d ，根节点的所有孩子节点d l n i d 分别为d o c i d 1 、 d o c i d 2 以此类推) ，分析节点内容，将每个节点存为x m l 节点表中的一个元 组。每个元组包括( d l n i d ，t a g , t y p e ，v a l ) 四个字段，对应于x m l 节点模型的每 个分量。对图2 1 所示的b o o k s x m l 文档，其所对应的x m l 节点表内容如表2 1 所示。 表2 1b o o k s x m l 文档对应的x m l 节点表 d l n i d t a gt y p e v a l lb i be l e m e n tn u l l 1 1b o o k e l e m e n tn u l l 1 1 1 c a t e g o r y a t t r i b u t ec 0 0 k n 、j g 1 1 2t i t l ee l e m e n tn u l l 1 1 2 1 l a n g a t t r i b u t ee n 1 1 2 2n u l lt e x t e v e r y d a yi t a l i a n 1 1 3a u t h o r se l e m e n tn u l l 1 1 3 1 a u t h o re l e m e n tn u l l 1 1 3 1 1n u l l t e x tg i a d ad el a u r e n t i i s 1 1 - 3 2 a u t h o re l e m e n tn u l l 第二章x m l 数据存储方案 1 1 3 2 1n u l lt e x tl i n d aa u r o r a 1 1 4 y e a r e l e m e n tn u l l 1 1 4 1n u l l t e x t 2 0 0 5 1 1 5 p r i c e e l e m e n tn u l l 1 1 5 1n u l lt e x t3 0 0 0 1 2b o o ke l e m e n tn u l l 1 2 1 c a t e g o r y a t t r i b u t ec h i l d r e