（计算机软件与理论专业论文）基于模式的xml查询重写及索引技术研究.pdf

摘要 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 ，可扩展标记语言) 是w 3 c ( 万 维网、于1 9 9 8 年2 月推出的一种标记语言。由于其独特的技术优势， x m l 推出后很快就成为网络中数据表示及交换的标准。因此，要构 建基于x m l 的各种应用，准确高效的从x m l 数据源中查询并获取 数据就成为其中关键的一步。论文基于这一背景，对x m l 数据的抽 象、查询、索引等方面进行了理论与实验探讨，主要内容、创新、贡 献及意义如下： 首先，在分析构建查询系统所需的基本要件的基础上，论文提出 了查询体系的总体框架，论述了从文档解析到查询处理的一般过程； 其次，论文基于d t d 与x p e 树模型，研究了x p a t h 查询表达式 的优化技术，提出了三种基于d t d 模式树的查询表达式重写方法。 通过对重写前后查询时问的比较，证明了重写算法的有效性。 然后，论文提出了一种名为d o b i ( d t do r t h o g o n a lb + t r e ei n d e x ) 的结构索引，该索引通过查找d t d 信息及利用特殊的存储结构，能 很好的解决结构化查询中最基本的祖先及后代连接问题，并高效的实 现各种查询。经过理论和实际的查询效率分析，证明此方法可快速的 确立元素问关系，减少路径访问次数，节约i 0 资源，有效地实现 x m l 文档的结构连接，提高查询效率。 接下来，根据t a t a r i n o v 等在x q u e r y 的基础上提出的x m l 文档 更新操作语言x u p d a t e ，论文提出了基于d o b i 索引的更新算法，该 算法能保持文档的有效性，并使得高效的数据更新成为可能。 论文最后对全文所展开的工作进行了总结，并指明了未来的研究 方向。 关键词x m l ，x p a t h ，查询重写，索引，数据更新 a b s t r a c t 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 ) i s a m a r k u pl a n g u a g e i n t r o d u c e db yw 3 cf t h ew o r l dw i d ew e bc o n s o r t i u m ) i nf e b r u a r y19 9 8 b e c a u s eo fi t su n i q u et e c h n i q u es u p e r i o r i t y ，i th a sb e e nw i d e l ya c c e p t e d a 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 gd a t ao nt h ew e b t o c o n s t r u c tv a r i o u sa p p l i c a t i o n so nx m l ，q u e r y i n ga n dg e t t i n gd a t af r o m x m ld a t as o u r c e a c c u r a t e l y i sa ne s s e n t i a ls t e p 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 et h e o r e t i c a la n de 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 ga n di n d e x i n gx m l d a t a f i r s t l y , t h i sp a p e ra n a l y z e st h ec e n t r a lc o m p o n e n t sf o rc o n s t r u c t i n ga q u e r ys y s t e m ，p r o p o s e saq u e r yf r a m e w o r ka n dd i s c u s s e s t h eg e n e r a l p r o c e s sf r o md o c u m e n tp a r s i n gt oq u e r y s e c o n d l y , b a s e do nt h et r e em o d e lo fd t da n dx p a t h ，t h ep a p e r s t u d i e st h eo p t i m i z a t i o no ft h ex p a t hq u e r ye x p r e s s i o ni t s e l f a c c o r d i n g t ot h et r e em o d e lo fd t d ，t h ep a p e rp u t sf o r w a r d st h r e er e w r i t i n g m e t h o d s t h i r d l y , t h ep a p e rp r o p o s e s as t r u c t u r a li n d e xc a l l e dd o b i b y e x t r a c t i n gd t da n ds t o r i n go bs t r u c t u r e ，d o b ic a nw e l lr e s o l v e t h e m o s tb a s i cc o n n e c t i o nq u e s t i o nb e t w e e nt h ea n c e s t o ra n do f f s p r i n go n s t r u c t u r a l q u e r y i t c a ne f f i c i e n t l yr e a l i z ea l lk i n d so fq u e r y a f t e r a n a l y z i n gt h ee f f i c i e n c yo fq u e r y , t h ep a p e rp r o v e sd o b ic a nq u i c k l y e s t a b l i s ht h er e l a t i o n sa m o n ge l e m e n t s ，r e d u c et h er o u t ev i s i t i n gt i m e s ， s a v ei 0r e s o u r c e s ，r e a l i z et h ei o i n so fx m ld o c u m e n t se f f e c t i v e l ya s w e l li m p r o v et h ee f f i c i e n c yo fq u e r y f o u r t h l y , a c c o r d i n gt ot h ex m lx u p d a t el a n g u a g ep r o p o s e db y t a t a r i n o ve t c ，t h ep a p e rp r o p o s e sa nu p d a t e da l g o r i t h mb a s e do nd o b i i n d e xw h i c hc a n k e e pt h ev a l i d i t y o fd o c u m e n t sa n dm a k et h e h i g h e f f i c i e n td a t au p g r a d ep o s s i b l y f i n a l l y ，t h ep a p e rs u m m a r i z e st h ew h o l er e s e a r c hw o r ka n dp l a n s t h ee x p e c t a t i o no ft h ef u t u r ew o r k k e yw o r d sx m l ，x p a t h ，q u e r yr e w r i t i n g ，i n d e x ，d a t au p d a t e l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：虱盘日期：j 型年卫月扛日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：_ i 季摹一导师签名隼日期：赳年阜月曰 硕士学位论文 第章绪论 第一章绪论 c e r i 认为如果承认“w e b 改变了世界”这个事实，那么x m l 是推动这种发 展向前跨越的手段【“。因此，与x m l 相关的研究对数据库研究者来说，是最有 挑战性的、也是最有前途的研究内容。x m l 在过去几年的时间得到了极大的发 展，它的角色从最开始的为文档保留语义的标记语言变成了异构系统间交换数据 - 的格式。x m l 作为数据交换和网络计算的基础，将无可非议的成为网络通用的 语言。实质上，x m l 为w e b 的数据管理提供了全新的数据模型，将w e b 变成一 个真正的数据库是这领域工作的终极目标，x m l 是朝这个方向迈出的有希望 的一步1 2 ，3 1 。 1 1 研究背景 w w w 的迅速发展使其成为全球信息传递与共享日益重要和最具潜力的资 源，它作为一种新的环境资源，为新技术的产生开辟了新的领域，同时也为传统 技术( 如数据库、人工智能等) 的研究提出了新的方向。如何管理w w w 上的 大量信息，以满足用户不断增长的信息需求，是研究人员面临的新课题1 4 j 。w e b 的目前状况离w e b 上有效信息服务与信息管理的实现还有差距，这正为数据库 技术向w e b 领域发展提供了空间。新环境中的数据库技术研究内容包括半结构 化数据模型及其理论、数据缓存与复制、事务管理、数据安全等，它与w e b 上 已有的成熟技术( 如信息检索技术) 相结合，可以用来解决w e b 上数据管理、 动态维护等关键问题。 研究面向w e b 的x m l 数据管理，最为严峻的挑战有两个方面1 5j ：其一，如何 高效地存储数据：其二，如何快速地查找信息。这两个方向的研究也为数据库研 究带来新的机遇和挑战，使得将数据库技术研究扩展到w e b 数据的管理成为可 能。虽然w e b 的发展为信息的共享提供了条件，但由于w e b 数据的数据结构不同 于传统的数据库中的数据，很难通过传统的数据库管理方式对这些数据进行管 理。故需要开发一种新的工具针对w e b 数据进行专门的管理。 从数据形式方面来看，w e b 中的数据具有如下特点1 6 j ： 1 半结构的或无结构的：w e b 页面通常仅有有限的结构，或者根本就没有 结构，即使具有一些结构信息，也是着重于格式方面，而不是关于内容的。所以， 从内容上看，w e b 中数据不同于关系数据库系统中规范的关系数据，w e b 中的数 据是半结构的或者无结构的。 2 非规范化：w e b 的开放性和用户的随意性使得w e b 上的数据几乎是无所 硕士学位论文 第一章绪论 不包，无奇不有，从内容到形式都没有什么规范可言。 3 机器难以自动处理：由于格式及内容表示的随意性，计算机很难对其进 行自动处理。 由于w e b 数据的特点，传统的信息检索技术已经不能适用用户的要求，而 要发明一种能同时针对多种异构数据使用的查询语言非常困难。这时人们想要用 一种数据格式把各种异构数据集成然后再进行查询，x m l 作为这样的一种有希 望能够解决异构数据的集成问题的数据格式被提出来。 1 2 面向w e b 的x m l 数据管理 x m l 的基本思想是：用标记表示数据的意义，而不是像h t m l 仅仅用来规 定数据的显示方式。目前，已有大量的信息系统中的数据采用了 x m l 表示。x m l 文档具有“可自描述”、“无限嵌套”、“树形结构”等特点，因此在某种意义上， 一个x m l n 2 档就是个数据库或其中的一张表。我们可以把相关的x m l ，文档放 在一个目录下，利用文件系统来管理，提供查询【7 】、更改、增删操作。为更好地 支持x m l ，w 3 c 还制定了一些相关技术，如文档模式( d t d 、x m ls c h e m a ) 、查 询语言( x p a t h 、x q u e r y 等) 、编程语言( d o m 、s a x 等) ，来方便开发应用程序。 x m l 为w e b 提供了一致的数据模型和描述语言，使得从语法上规范化地表 示w e b 数据成为可能，通过研究x m l 数据的管理技术，可以为基于w e b 的数据管 理提供新的途径和方法。很多学者认为，x m l 作为一个手段和方法，将推动网 络技术的发展和社会的进步。 x m l 的提出，主要基于以下目的： 1 国际化的信息发布的标准，可以独立于各种平台和系统： 2 允许各行各业定义平台独立的协议规范来交换数据，支持电子商务等网 络应用： 3 用户可以通过方便简单的软件处理数据，不需要昂贵的专业软件； 4 允许用户以自己喜欢的方式显示数据，数据内容与显示方式分离： 5 提供元数据，比如信息的来源和其它说明信息等，这些都是关于数据的 解释和描述。 由于x m l 自描述的灵活性和可扩展性，越来越多的系统采用x m l 作为建 模语言和接口语言，各行各业提出了基于x m l 的专业标准，例如，数学x m l ， 化学x m l ，医学x m l 等，x m l 已经越来越被普遍应用。下一代因特网一网格， 也把x m l 作为w e b 的描述语言和接1 2 1 语言。因此，我们认为x m l 数据管理技 术的研究是现代化数据管理技术的核心之一，对新一代w e b 技术的发展及w e b 信息的开发利用，具有重要的理论意义和广阔的应用前景。 硕士学位论文第一章绪论 1 3x m l 数据管理的研究现状 x m l 文档采用简单的文件管理是远远不够的：低效的存储组织，无索引查 询技术，不提供事务安全恢复机制，无法保证数据的完整性和一致性，没有并发 控制和移植工具等【8 i 。由于上述的文件系统的缺点，我们也为x m l 数据建立一 个数据库管理系统以提供对大量x m l 数据的高效管理。 1 3 1 两种x m l 数据库管理方式 x m l 数据本身的层次结构不同于关系模型中的二维表结构，这种差别反映 在数据库产品处理x m l 数据的技术上，形成两大阵营：x m l - e n a b l e d d b m s ( x e d ) 和n a t i v ex m ld b m s ( n x d ) ! 。x e d 在原有关系数据库基础上扩展 了x m l 支持模块，完成x m l 数据和数据库之问的格式转换和传输。 从存储粒度上看，可以把整个x m l 文档作为r d b m s 表中一行，或把x m l 文档解析后存储到相应的表格中。为了支持w 3 c 的一些x m l 操作标准，如x p a t h 等，x e d 提供一些新的原语( 如o r a c l e 9 i r 2 增加了一些数据包来操作x m l 数 据等) ，并优化了x m l 处理模块。n x d 则出现在x m l 数据处理领域内，一般 采用层次数据存储模型，保持x m l 文档的树形结构，省掉了x m l 文档和传统 数据库的数据转换过程。表1 - 1 是关于两种数据管理方式的比较。 表1 - 1n x d 与x e d 的比较 特性n x dx e d 数据模型x m l 文档模型关系数据模型 查询语言 x q u e r y 模板，s o l 查询性能高低 信息完整性 高低 存取速度快慢 数据有序性 支持不支持 对格式复杂的x m l 文档支持 好差 语义性 好差 对x m l 技术标准的支持 先进落后 用户熟悉程度不熟悉熟悉 并发控制、事务 不成熟 成熟 应用范围 窄 广 硕士学位论文 第一章绪论 表1 - 1n x d 与x e d 的比较( 续) 特性n x dx e d 数据安全差好 技术基础差好 应川市场的份额一般 大 份额增长率高低 应! = | 领域 制浩、f p 、堆物瞑药、电信等 t 业等 分析表1 - 1 可知，n x d 数据管理在存取及查询等方面有着x e d 不可比拟的 优势，n x d 发展到今天，技术日趋成熟，不仅提供传统数据库绝大部分功能， 而且支持x m l 的最新技术标准，非常方便x m l 开发人员进行开发。同时我们 也应该看到，n x d 技术发展时间相对传统数据库来说还很短，技术基础还不是 很牢固。在某些x m l 应用方面，n x d 并不具有比x e d 明显的优势，特别是在 对数据安全要求很高的数据库应用领域。但n x d 在处理x m l 数据时拥有传统 数据库所不能比拟的天生优势，已促使越来越多的目光聚焦到它上面。 今天市场上已有了十多种n x d 产品1 1 ，i b m 、m i c r o s o f t 和o r a c l e 等传统数 据库厂商，也正在踏入n x d 的领域。特别是o r a c l e ，在其最新的o r a c l e9 i r 2 中， 已经支持x m l 数据的w 3 cd o m 模型存储。现在走在n x d 队伍前面的却是一 些“小”公司。比如，e x c e l o n 公司的e x t e n s i b l e i n f o r m a t i o ns e r v e r 3 1 和l p e d o 公司的i p e d o x m l d a t a b a s e3 0 等。表1 2 为一些x m l 原生数据库产品的列表。 n x d 数据管理面对未来几年巨大的市场份额，以及它每年2 0 0 的增长速 度，我们没有理由不为它叫好。需指出的是：大量针对x m l 数据库的研究以及 x m l 数据库产品的出现并非意味着x m l 数据库的成熟，相反，在x m l 数据模 式、x m l 查询代数、x m l 数据库的数据完整性等众多理论与技术问题上并无突 破性进展，以关系数据库的标准来看，有关x m l 数据库的理论和实验仍有许多 工作需要完善，它们仍是当前研究的热点。 表1 - 2 x m l 原生数据库产品列袁 产品 开发商数据存储u r l 4 s u i t e f o u r t h o u g h t 面向对象 h t t p ：4 s u i t eo r g i n d e x x h t m l b e r k e l e yd bx m ls l e e p y c a ts o f t w a r e 关键码值 h t t p ：w w w s t e e p y c a t c o r n b i r d s t e pr d m x m lb i r d s t e p 面向对象 h u p ：w w w b i r d s t e p e o r l l c e r i s e n tc 1s e r v e rc e f i s e n t 专有 h t t p ：w w w c e r i s e n t c o i i i d b d o m k r u p n i k o v 关系 h t t p ：a b d o m s o u r c e f o r g e n e t 堡主堂垡鲨壅 堡二童堂 表1 - 2 x m l 原生数据库产品列表( 续) 5 硕士学位论文 第一章绪论 1 3 2n x d 主要研究方向 x m l 的数据管理技术己经受到数据库界、信息检索领域、网络等领域学者 的注意，大部分研究关注于数据模型、查询语言、存储技术、索引技术、数据发 布技术等，在这些方面，学者们进行了程度不同的深入研究。我们把这些研究按 照内容不同，归纳为以下几大类： 1 数据模型 建立x m l 数据模型是建立n x d 数据库的前提，如何建立一个有效的面向 n x d 表达的x m l 数据模型一直是一个具有挑战性的问题。w 3 c 定义了四种 x m l 数据模型，分别是：i n f o s e t ( x m l 信息集) ，d o m ( 文档对象模型) ，x p a t h 和 x q u e r y l 0 与x q u e r y 2 0 数据模型【1 1 】。到目前为止，x m l 数据模型描述的主要 形式有逻辑的方法，图描述的方法，函数式编程的方法，树自动机的方法。其研 究方向在于如何处理已有的这些模型间的关系，如何在这些或简单或复杂的模型 中找到平衡点以满足自己的需要。 2 模式管理 由于x m l 数据具有自描述特性，x m l 的模式信息是从数据中提取的i ， 模式信息能帮助人们清楚地了解x m l 数据结构，但这样的模式信息庞大而且复 杂，如何抽取模式使其保持完全的对应关系而且具有约束数据的功能是n x d 数 据管理中一个极为重要的问题，有了适当的数据模式，数据库可以利用模式信息 做很多工作，如查询时的类型检查、不同类型的索引的创建和管理、存储时数据 的聚集方式、查询优化时的代价估计等。 3 存储管理 对n x d 的数据存储来说，挑战性的问题是：要有足够的灵活性，能够存储 具有规则结构的x m l 的任何组成部分，以及x m l 文档的物理结构。目前，哪 种存储策略更适合n x d 是一个有争议的问题，文献 1 3 】对其中的几种方式进 行了比较。另外，数据管理中的并发控制、版本控制，x m l 内容和结构的动态 更新等问题都是存储管理需要解决的问题。 4 查询处理研究 n x d 的查询技术的研究可分为三类： ( 1 ) 查询语言之上的部分：如查询界面、查询数据视图、数据维护、触发器 等等； ( 2 ) x m l 查询语言本身的研究：包括x m l 查询代数，x m l 查询处理语言， x m l 数据更新语言等； ( 3 ) 查询语言之下的部分：如查询优化技术等。 本文主要对x m l 的查询优化进行了研究。 硕士学位论文第一章绪论 5 x m l 安全研究 主要研究基于角色的访问控制，x m l 签名，x m l 数据加密等等。 1 3 3 查询处理及优化技术 由于需要查询大量x m l 数据，高效的查询能力对n x d 来说非常重要。尽 管开展了许多研究工作，但相对于关系数据库查询技术来说，n x d 查询技术还 处于起步阶段。目前x m l 数据查询优化主要集中在以下两个方面： 1 路径表达式本身的优化 文献【1 4 】提出了两种针对路径表达式的优化策略：路径缩短策略和补路径策 略，从而提高了x m l 路径查询效率。路径缩短策略根据x m l 文档模式信息，将路 径表达式查询长度缩短，从而简化查询本身以降低需要的查询代价；而补路径策 略则试图使用代价更小的等价路径表达式来替换原始查询。 文献【1 5 】提出了一种通过存取控制来实现x p a t h 表达式的方法。为了解决当 两个x p a t h 表达式( 包含谓词，通配符，d e s c e n d a n t 轴时) 蕴涵问题的c o n p 难 问题，文献定义了一种x a c tf x m la c c e s sc o n t r o lt r e e ) 来查询x m l 文档，改 进查询性能。 文献 1 6 ，1 7 1 中也从面向对象及半结构化数据的角度提出了查询重写策略， 改进查询性能。文献 1 8 ，1 9 1 中，作者通过对查询表达式中内部函数进行预处理， 从而减少存储空间，提高路径表达式的处理速度，改进查询性能。 2 路径表达式索引方法 x m l 索引可以分为两种，一种是支持简单查询的索引结构，另一种是支持 正则查询的索引结构。可支持简单查询的索引结构能很好的支持简单查询语句， 但对正则查询语句则显得非常低效。下面介绍几种支持简单路径查询的索引方 法。 d a t a g u i d e s l 2 0 l 是最早出现的一种c o v e r i n gi n d e x ，并且这一算法在l o r ed b m s 中得到了实现。d a t a g u i d e s 提出了路径的合并策略；1 - i n d e x ”j 与d a t a g u i d e s 的出 发点不一样，它不是从路径而是从节点着手来考虑索引；2 - i n d e x l 2 l j 是为了支持 正则表达式而提出来的，但这种索引有很大的局限性，它只能支持一些由节点、 ”一组成的非常简单的正则表达式。a ( k 1 i n d e x 2 2 l 与前面提到的索引所不同的是它 采用的是一种局部的相似性，将会压缩节点的数量，在索引结构大小与准确度之 间提供一个折衷的方法。 i n d e xf a b r i l 2 3 】与前面提到的索引结构有本质的区别，上面的索引都将路径看 成很多元素组成，而i n d e xf a b r i 采用了前缀编码的方式即路径被编码成字符串， 插入一种叫作f a b r i c i a t r i e 的索引结构中。这种索引结构适合于以文档根结点为起 硕士学位论文 第一章绪论 点的路径查询，而其它路径查询则要求查洵多个索引或要经过一个预处理。为了 弥补这个不足，它提出了精确路径的概念。然而，在利用索引进行查询之前，这 种精确路径要经过多次预选择，而且对于个给定的t r i e 结构，很难给出合理的 划分。 到目前为止，本文介绍的索引结构都不能或者不能很好的支持有价值的正规 语句，c o v e r i n gi n d e x 仅仅支持非常有限的简单正则查询，i n d e xf a b r i 也不能解决 这一问题。 x l s s 2 4 是可支持正则查询的索引结构中最具代表性的种，它通过b + 树索 引，将文档中具有相同节点名称的节点存储在一起，能够通过节点名称快速找到 元素，然后再利用编码机制来判断节点之间的祖孙关系从而获得满足查询条件的 节点。 文献 2 5 ，2 6 也给出了另种编码方法，并在此基础上9 1 进了高维索引r 树的 概念，避免了很多不相关的结果的处理。 1 4 本文的主要研究工作 论文研究的主要目标是：通过对x m l 数据特点的分析和研究，针对目前在 x m l 数据管理中存在的问题，提出一种新颖、实用的面向w e b 的x m l 数据管理 的解决方案，并对其中涉及的关键技术( 例如：查询预处理、索引技术和数据更 新技术等) 进行深入研究，期望为推进本领域的技术发展作一点贡献。 根据我们的研究目标，论文工作主要包括以下几个方面： 1 x m l 数据模型及查询语言 x m l 文档可以解析为不同的数据模型，使用哪一种数据模式视乎用户的需 要。本文介绍了现有的x m l 数据模型和数据模式及x m l 查询语言；然后分析 比较现有的几种查询语言的性能，选取适当的查询语言作为研究基础。 2 x m l 数据库管理系统框架的设计 提出整个x m l 数据库管理系统的三层模型：数据层，应用层及表示层并设 计了位于应用层的x m l 查询体系的框架。 3 查询表达式的处理 研究基于模式的x m l 查询路径表达式的优化，主要包括对路径表达式的简 化，对多个路径表达式的连接，以及无效查询表达式的过滤等。 4 x m l 索引技术 研究x m l 索引技术，介绍并分析前人提出的索引技术的优缺点，提出一种 新的索引方法以提高查询效率。 5 x m l 数据更新 硕士学位论文 第一章绪论 分析基于索引的数据更新过程，提出x m l 数据的更新算法。 1 5 本文的研究思路及组织结构 本文基本的研究思路是以成熟的关系数据库为基础，根据x m l 数据的特点， 结合数据结构、信息检索等领域的相关技术，提出了x m l 数据查询的优化方案。 围绕提出的解决方案，本文基于整体目标着重研究了其中的两个关键技术：一是 x m l 数据的查询表达式预处理技术，二是x m l 数据索引技术。与此相关，本文 还研究t x m l 数据的更新技术，最后通过大量实验数据证明了技术的可行性。 论文共分六章，结构如下： 第一章提出了w e b 数据管理面临的问题，提出了基于原生x m l 数据库的 数据管理方式( n x d ) ，并阐述了n x d 的研究现状，提出了本文的研究方向，即 x m l 查询处理及优化。 第二章介绍了x m l 数据模型，数据模式及x m l 查询语言，并分析了几种 不同的查询语言的性能，提出了x m l 原生数据库管理系统的三层模型并着重设 计了位于中间层的x m l 查询体系的框架。 第三章研究了x m l 数据查询路径表达式的预处理过程。首先提出了基于模 式的查询表达式的约束问题，然后基于d t d 模式，从三方面提出了查询表达式 的重写算法，包括：广义表达式到简单表达式的转化，多个路径表达式的连接及 对无效路径表达式的过滤，并通过实验数据验证了这几种算法的性能。 第四章集中研究了x m l 索引技术。在前人基于编码的索引的基础上，提出 了基于模式的索引方法，该方法以o b ( o r t h o g o n a lb + t r e e ) 树为存储结构，并结合 d t d 信息，能有效减少元素访问个数和路径连接次数，使x m l 查询性能得到优 化，本章还实验比较了d o m 查询，x i s s 方法和d o b i ( d t do r t h o g o n a lb + t r e e i n d e x ) 方法的性能。 第五章在基于t a t a r i n o v 等在x q u e r y 的基础上提出的x m l 文档更新操作语 言x u p d a t e ，提出了基于d o b i 索引的更新算法，然后用实验数据进行了分析， 证明了算法的可行性，解决了当前x m l 数据更新效率低的问题。 第六章也是全文的最后一章，对全文所开展的工作进行了总结，并指出了进 一步要研究的工作。 硕士学位论文第二章x m l 与数据库系统 第二章x m l 与数据库系统 对于“以数据为中心”的x m l 文档，x e d 可以方便地将其中的数据抽取， 存储在传统数据库中，但对于“以文档为中心”的x m l 文档则显得力不从心。 n x d 由于无需在两种模型之间转换数据，因此在处理“以文档为中心”的x m l 文档时很有优势。n x d 是专门为存储x m l 文档设计，也兼有一般数据库的特 性，例如支持事务，并发控制，查询语言，安全机制，二次开发接口等。唯一的 不同之处在于其内部存储模型是基于x m l 文档模型结构，而非关系模型。 本章的内容是这样安排的：首先介绍了x m l 的数据模型、数据模式及查询 语言，然后介绍了n x d 系统结构，提出了n x d 查询处理的应用模型。 2 1 半结构化数据及模型 x m l 技术是互联网发展的关键技术，它已成为互联网上表示结构化和半结 构化数据的标准格式和数据交换的主要标准。x m l 的基本思想是：用标记表示 数据的意义，而不是像h t m l 仅仅用来规定数据的显示方式。在这种背景下， 把x m l 作为一种数据库模型并从中提取信息在数据库领域逐渐受到注意。 2 1 1x m l 数据模型 x m l 是典型的层次结构，这种结构既然包含了元数据和数据，为了能让 机器更好的理解x m l 数据，建立适当的数据模型是非常重要的。w 3 c 定义了四 种x m l 数据模型，分别是：i n f o s e t ( x m l 信息集) ，d o m ( 文档对象模型) ，x p a t h 和 x q u e r y l 0 与x q u e r y 2 0 数据模型。如何处理已有的这些模型问的关系，如何在这 些或简单或复杂的模型中找到平衡点以满足用自己的需要是x m l 数据模型研究 的重点。x m l 文档本质上是一种半结构化数据，但与一般的半结构化数据相比， 它又有自己的特点 2 8 , 2 9 1 。本文参照w 3 c 的系列规范，考虑x m l 自身的特点， 采用d o m 模型作为本文研究的基础数据模型。 定义2 1x m l 数据模型：用二元组t 来描述x m l 数据。其中，t = ， e = ( o i d l o i d s 。) ，s e 是树中节点的集合，r = lp ( x ，y ) a ( x , y e ) ) ， p ( x ，y ) 是谓词，表示存在一条从节点x 到节点y 的边。节点的标签表示元素名称， 如果p ( x ，y ) 存在，那么说x 是v 的父节点。 定义2 1 把x m l 文档映射成为树模型，每一个元素只能有个标记，标记放 在节点中，但元素的属性也有类似于元素把属性名放在节点中，可设置一个标志 位与元素进行区分。按照d o m 规范，把x m l 文档分解为一棵包含文档中所有元 】0 皇里羔篁堕登l 笙三至兰坚生量塑塑壁墨- 堕- j k _ 二= m m ，十月i 素和属性的树结构，程序就可以通过类d o m 定义的接口访问和更新x m l 文档的 样式、结构和内容。图2 - 1 对应的x m l 数据的d o m 模型如图2 2 所示。d o m 模型 的优点是：标记定在节点上，可以直接知道对象的含义，从父节点出发可以直接 访问子节点。 b o o ky e a r = ”2 0 0 0 ” d a t ao nt h ew e b a b i t c b o u ! 吲l a s m o r g a nk a u f m a n np u b l i s h e r s 3 99 5 t i t l e t h ee c o n o m i c s o f t e c h n o l o g ya n dc o n t e n tf o rd i g i t a it v g e r b a r g d a r c y c i t i k l u w e ra c a d e m i cp u b l i s h e r s 1 2 9 9 5 图2 - 1 x m l 文档 o ( ) 口 t e x t 属性 元素 图2 2 订l 文档树模型 与关系数据库不同，x m l 数据中所有的文本数据类型都是字符串型。而x m l 元素只分为两种类型，即简单元素和复合元素。其中，简单元素是指只包含文本 硕士学位论文第二章x m l 与数据库系统 的元素。如图2 2 中的”t i t l e ”，”l a s t ”，”f i r s t ”元素等，简单元素的值是指简单元素所 包含的文本内容，也就是”t i t l e ”，”l a s t ”所对应的值；而复合元索是指含有子元素 的元素，如图2 - 2 中的”e d i t o r ”，”b o o k ”元素等。 2 1 2x m l 数据模式 众所周知，关系数据的模式虽然x m l 没有像r d b 那样严格的结构，但也 还是有模式的概念，例如d t d l 3 0 1 、x m l - s c h e m a l 3 1 1 和s o x l 3 2 1 等，x m l 模式比 r d b 模式更宽松、灵活，一旦模式确定，还是有静态类型错误被查出的余地， 也可能进行基于类型的优化，如：忽略掉不感兴趣的图的部分，或进行基于输入 数据的结构知识的重写优化等操作。 由于d t d 的直观性，本文采用d t d 作为模式来进行研究。下面给出了图 2 - 1 中x m l 文档的d t d 描述如图2 3 所示。 图2 - 3 文档d t d 一个d t d 本质上其实是一个上下文无关文法【3 3 , 3 4 】，对于图2 3 中d t d 所定 义的规则来说，先不考虑属性，我们可以表示成图2 - 4 的产生式。 图2 - 4 d t d 的产生式 根据图2 - 4 的产生式，d t d 可以抽象成树模型，如图2 5 所示。与x m l 文 档模型相比，该模型完全不含有文本信息。 里壁兰塑堕翌王 釜三童墨坚兰量墼塑堕墨竺 睦 2 5d t d 语法树 定义2 - 2 d t d 数据模型：用树t 来描述x m l 数据。其中，1 ：l 。： e 2 ( o i d o i d e s s ) ，s e 是树中节点的集合，r = ip ( x ，y ) ( x ，y 瓦。) p ( x ，y ) 是谓词，表示存在一条从节点x 到节点y 的边。节点的标签表示元素名称， 如果p ( x ，”存在，那么说x 是y 的父节点。如图2 5 所示。 定理2 1 设t ，l 。d = a 为棵x m l 树，t d 日= 为x m l 文档对 应的d t d 树，那么t d f d 是t 的真子树。 证明：1 对于t d 。a 的p ( x ，y ) 及t x 。的q ( x ，y ) ，因为t d 。) 一t 。的一个描述， l m 一2 与t d 。a = c 中关系r 。与r 。是等价关系。所以对于 l 司一。，其p ( x ，y ) 的值域p ( y ) ，及q ( x ，y ) 的值域q ( y ) ，p ( y ) cq ( y ) ，那么t d 。是t 的真 子树。 由定理2 1 可知，d t d 的语法树实际上是x m l 解析树的子集。x m l 文档 树中的任意非叶子节点都可以在d t d 树中找到与之对应的节点信息。因此如果 不考虑x m l 文档中的文本信息而只考虑x m l 中的元素关系时，x m l 数据库管 理程序不需要搜索信息量巨大的x m l 树，而只需要在相对很小的d t d 树中进 行搜索即可得出元素间关系。这样可以免去很多不必要的搜索，查询提高效率。 2 2 x m l 查询语言 查询语言是查询处理及查询优化的基础，众所周知，关系型数据库有一套非 常完备的查询语言3 5 1 ，同样，n x d 也需要完备的查询语言来完成x m l 数据的 查询及更新。 2 2 1 查询语言简介 关系型数据库的查询被定义为可计算的、一般的和完备的从关系数据库到关 系的映射。关系代数是一个关系型数据库查询表达式是否完善的标准。在w w w 硕士学位论文 第二章x m l 与数据库系统 情况下，上述基础中的大部分被动摇了，首先，被查询的对象常常是一个移动的 目标，查询常常是一个没有严格定义的输入，也没有一个很好的尺度来衡量查询 表达式，各种查询表达式几乎很难有共同的抽象特征；其次，关系型数据库最有 意义的、显著的特点是数据的独立性，即：数据的逻辑层与物理层的分离，查询 结果仅依赖于数据的逻辑层。在w w w 上，逻辑层与物理层是很难分清的，查 询肯定不会也不应该同等对待它们，w e b 页上显示的内容表达了逻辑信息还是纯 的物理信息? w e b s i t e 的地理位置又如何呢? 没有一个劳永逸的、清晰的答案。 容易推论出：查询的一般化也是不健壮的和有意义的。 现举例说明传统数据库查询语言向x 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 查询建立查询代数，从而 能像关系数据库s q l 一样有一个完备的数学背景，为查询优化、数据库一致性 等高级应用提供基础。 到2 0 0 1 年1 1 月截止，已有多种查询语言被提出，目前被看好的查询语言有： l o r e l l 3 6 1 、x m l q l l 37 1 、x m l - g l 38 1 、x s l a r 【39 1 、x q l 4 0 1 、x q u e r y l 4 1 1 。按不 同的表现力和表现方式，查询语言可被分为如下三类： 第类：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 世界中起的作用； 第三类：x q u e r y , l o r e l ，x s l t ，它们同高级s q l ( 如s q l 2 ) 的作用类似， 但是，他们之间仍有区别，例如，l o r e l 是完全描述性的，x s l t 实际上是一种过 程性的样式表语言，而x q u e r y 是描述