xml数据库综述.docx

《高级数据库技术》综述 ----NXD的查询优化相关研究2009年1月摘要XML是一种专门为Internet所设计的标记语言。XML 的重点是管理信息的数据本身，而不是数据的样式，数据的显示则交给另外的技术来解决。虽然XML 是一种专门为Internet所设计的标记语言，但是它已经成为Internet上数据表示和数据交换的标准。随之而来的是堆积如山的XML文档，如何对这些XML文档进行有效管理与快速查询，是当前学术界的研究热点，即所谓的XML数据库。随着XML日益普遍的应用，如何快速准确地访问XML文档中的数据已成为急需解决的关键问题，这涉及到对XML查询语言XQuery实现的优化研究。目前可以通过多种途径对XQuery进行优化，如：执行策略、物理优化、代数优化、建立索引等。前3个对XQuery进行优化的策略，都是从逻辑操作上进行的。虽然可以提高对XML文档的查询效率，但不能解决根本的问题。目前国内外对XQuery优化的研究大都是通过对XML数据建立索引来进行的，由于XML文档是一种树型结构，对XML查询树建立索引，利用索引实现对XML文档查询的优化。索引可以分为XML路径索引和基于编码的XML索引。在基于编码的XML索引的基础山提出结构连接算法。广大的研究者已经提出了各种结点编码方式及其对应的结构连接算法。目录1、XML数据库41.1、XML数据库的概念41.2、NXD(Native XML Database)的体系架构41.3、NXD的特点52、NXD的发展现状、前景与热点52.1、NXD的发展现状与前景52.2、NXD的研究热点63、查询优化63.1、索引63.1.1 DataGuide73.1.2 1-index73.1.3 A(K)83.1.4 D(K)83.1.5 Fabric93.1.6 ContainIdx93.1.7 PosIdx93.1.8 ExtContainIdx103.1.9 HiSC103.1.10 path hashing113.1.11 R-tree113.2、结构连接算法123.2.1、结构连接算法概念及分类123.2.2、MPMGJN算法133.2.3、XR-Stack算法143.2.4、DRIAM算法154、总结175、参考文献17NXD的查询优化相关研究1、XML数据库1.1、XML数据库的概念XML数据库是一个有相互有关联XML文档的集合，这些文档是持久的并且是可操作的。目前XML数据库有三种类型[1]：1、XML Enabled Database (XEDB)，即能处理XML的数据库。其特点是在原有的数据库系统上扩充对XML数据的处理功能，使之能适应XML数据存储和查询的需要。一般的做法是在数据库系统之上增加XML映射层，这可以由数据库供应商提供，也可以由第三方厂商提供。典型的例子是Oracle、Sql Server2005。2、Native XML Database (NXD)，即纯XML数据库。其特点是以自然的方式处理XML数据，以XML文档作为基本的逻辑存储单位，针对XML的数据存储和查询特点专门设计适用的数据模型和处理方法。典型的例子是BaseX、Exist、Natix。3、Hybrid XML Database (HXD)，即混合XML 数据库。根据应用的需求,可以视其为XEDB或NXD的数据库，典型的例子是Ozone。1.2、NXD(Native XML Database)的体系架构一个典型的Native XML数据库系统的体系结构[2]如图1所示。不同的Native XML 数据库系统的体系结构不尽相同，但至少包含存储管理、索引管理、查询处理以及数据导入模块，一个完备的Native XML 数据库还应该包含事务管理、并发控制、恢复技术等功能，并且提供良好的更新机制，此外，还应有相应的应用程序编程接口(API)和友好的用户使用界面。图1 NXD的体系结构1.3、NXD的特点与传统数据库相比，NXD具有以下特点：1、对半结构化数据进行有效的存取和管理，而传统的关系数据库对于半结构化数据无法进行有效的管理。2、提供对标签(Tag)和路径的操作。传统数据库语言不能对元素名称操作，半结构化数据库提供了对标签名称的操作，还包括了对路径的操作。3、当数据本身具有层次结构时，由于XML数据格式能够清晰表达数据的层次特征，因此XML数据库便于对层次化的数据进行操作。4、顺序性( sequence)。在传统的数据表中，表项(field)之间的顺序是可以互换的。以文档为中心的XML文档与传统的数据表不同，其内容是有顺序的，不允许随便调整elements、attributes、PCDATA的顺序。当然，顺序性使得对XML文档的查询、修改比传统数据库的相应操作复杂。5、与各种数据的交换能力。由于