一种基于关系数据库的XML文档存储和查询的方法硕士毕业论文

一种基于关系数据库的XML文档存储和查询的方法A RDB-Based Approach to Storage and Query of XML Document ContentsChapter 1 Introduction 11.1 Research situation at home and abroad 11.2 The main work in the thesis 31.3 Structure of the thesis 4Chapter 2 Background of XML 52.1 Origin and characteristic of XML52.2 Types of XML document 62.2.1 XML document 62.2.2 DTD document 72.2.3 XML Schema 72.3 Query language of XML 82.3.1 Basic syntax of XPath 82.3.2 Calculation of the path expression 102.4 Heterogeneity between XML and RDB 11Chapter 3 Storage transformation based on path 133.1 Storage structure based on path 133.1.1 Value Table 133.1.2 No_Value_Table 153.2 Storage mapping algorithm 16Chapter 4 Mechanism of query processing 184.1 Transformation rules of linear path expression 184.1.1 Simple path including parents-child only 194.1.2 Simple path including ancestor-descendant 194.2 Processing of non-linear path expression 22Chapter 5 Further optimization of storage and query 255.1 Schema of storage optimization 255.2 Schema of storage optimization 26Chapter 6 Design and implement of the system 286.1 Whole design framework of the system 286.2 Function of the system modules 286.2.1 XML-parser 286.2.2 Storage processor 306.2.3 Query processor 316.3 Experiment result and analysis of the system performance 31Conclusion 34Reference 36Acknowledgment 40摘 要XML已成为Web上数据表示、集成和交换的标准，它的格式简单、自我描述能力强，实现了内容、结构和表现三者的分离，更适合于数据表示和交换。近年来，XML在各个领域得到了广泛的使用，Web上已经涌现了大量的XML数据。为了有效地加工、分析和处理XML数据，国内外学者已经提出了各种XML的查询语言和存储管理技术。由于关系数据库是目前最成熟的一种数据管理技术，在存储和管理XML数据的各种方式中，基于关系数据库的XML数据存储和处理技术显然是一种可行而有效的方式，并在学术界受到了广泛的关注。然而，由于数据模型的差异，利用关系数据库存储和查询XML数据给传统数据库技术带来了许多新的挑战。本文对XML数据的关系存储、路径表达式的查询处理等方面进行了深入的研究和探讨，发现了目前已有的XML数据的关系存储方法中的不足之处。提出了一种新的利用关系数据库存储和查询XML数据的方法，这种方法将XML文档树中有文本值的节点和文本值的节点分别存储在两个关系表中，它不关心文档DTD的模式信息，也不需要建立任何索引结构。针对这种存储方法的特点，本文提出将XPath路径表达式的核心子集转换成SQL语句的转换规则和算法。具体来说，本文的主要工作如下：（1）提出了一种新的XML数据的关系存储方法。这种方法完整无损地记录了XML文档中的各节点信息、边信息和值信息，即在关系表中存储XML文档中所有有值元素/属性的路径，以及各元素的id、Parentid、Level等信息，加快了查询处理的速度。（2）针对我们的存储结构，提出了新的基于表连接的查询转换规则和算法。这种查询算法可以将不同形式的路径表达式转化为SQL查询语句来处理。 （3）对以上的存储和查询方法提出进一步的优化方案。当XML文档层次较多时，引入一个路径关系表来减少对相同路径的存储冗余；当查询路径表达式为线性结构时，采用串匹配的方法来减少表连接次数，从而减少连接操作和I/O数量。（4）论文提出的存储转换方法和查询处理方法已在原型系统中实现，并利用实际的XML 文档对系统进行性能测试，实验证明，本文所提出的方法是可行而有效的。关键词：XML；关系数据库；关系存储；路径表达式；表连接中图分类号：TP311AbstractXML has already become the standards of the expression, integration and exchange of the data on web. It has simple form and strong self-describing ability. Beside, it realizes the separation of the content, structure and expression, so that it is more adapt to data expression and exchange. During recent years, XML is widely used in various fields, and its data has abundantly appeared on web. In order to effectively analyze and process these XML data, research fellow posed various techniques of inquiring language and memorizing of XML. As now, relational database is the most mature data-managing technique, XML data-processing which is based on relation, is obviously a feasible and prospective way among all ways of memorizing and managing XML data, so it attracts extensive attention in the academia. However, as the data models are different, the process of XML data, by making used of the relational database, challenges traditional database technique.This paper does a thorough research on the relational storage based on path, and the querying process of the path expression of XML data, and find out that there are some disadvantages in the existing mappings from XML to the relational database. This paper proposed a new approach to storage and query XML document using relational databases, this approach can respectively store the XML data in different relational table according to whether the node of the document tree has text value or not. This approach is insensitive to the DTD model, and not necessary to design any index structures. Aim at this storage approach, this paper proposed specific transformational rules and algorithm, which is transform the core subset of path expression in XPath into SQL. The main contributions of this paper are summarized as follows:(1)A new kind of relational storage approach based on path for XML document is put forward. It can completely record the information of each node, side, and value of the XML document, in other words, the path information of all the attributes and elements that have text values, and the information such as id, parented, and level of each element, so accelerate the query and process.(2)For the relational storage approach based on path for XML document, this paper proposed a new query transformational rules and algorithm based on table join. It can transform different forms of path expression to SQL query sentences to be processed.(3)Further optimizing scheme is provided for the storage and query approaches mentioned above. The Path_Table is introduced to reduce storage redundancy of the same paths when the number of XML document levels is large; The method of string match is adopted to reduce the times of table join, and reduce the amount of join and I/O operations consequently.(4)The storage and query approaches brought forward in this paper have been implemented in a prototype system. The performance test of such approaches is carried out using practical XML documents. It is proved that the storage and query approaches brought forward in this paper are feasible and effective.Keywords: XML; relational database; relational storage; path expression; table join第一章 引 言随着互联网的发展，XML（Extensible Markup Language）已经成为一种网上通用的数据存储与信息交换的一种标准格式 fdfdfd,2,3。XML由于自身的规范性、灵活性、可扩展性和强大的语言表达能力，被普遍应用于诸多领域，如数字图书馆、电子商务等。近年来，Web上已经出现了海量的XML数据，因此，如何有效地存储和管理XML数据成为一个很有研究价值的重要课题。由此，研究和设计一个XML有效的存储和查询系统显得格外紧迫和重要。1.1 国内外研究现状.在制定了XML的规范后，第一个要解决的问题就是如何存储XML数据，这是因为对XML 数据的查询、检索、更新等处理都是建立在一定的存储模式基础上的，因此它的存储方式极大地影响了查询处理的效率。但XML文档数据是一种半结构化数据，利用现有的技术无法有效地存储和管理它，因此XML数据的存储就成了XML领域一个非常重要的研究方向。由于XML文档是作为文本来编辑的，故可以把XML文档作为一个普通的文本文件直接存储在文件系统中，此方法最明显的优点就是实现简单并且不需要专门的数据库系统或者存储管理器。但每次访问XML文档时都需要先进行解析，极大地影响了访问效率。而且查询时，整个被查询的XML文档必须常驻内存，因此只适合于XML文档内容少、数量小的场合，它的局限性是显而易见的。为此，国内外学术界提出了许多不同的XML文档的存储策略4,5。目前管理XML数据有三种主要的方法，分别是原生XML数据库、面向对象数据库和关系数据库。研究者们采用原生XML数据库（Native-XML）来存储XML文档6,7,8，这种数据库的是完全用来存储和操作XML数据的数据库，存储数据时不需要进行XML和数据库的映射转换。Native-XML维持原有XML文档的数据结构和相关的元数据，而不关心数据的底层存储结构（关系数据库或是面向对象数据库）。但目前它是一种全新的数据库，技术还不够成熟，传统数据库中原有数据也不能轻易地移植到新系统中。这样人们就自然地想到利用成熟的数据库技术来管理XML文档，如面向对象数据库和关系数据库。面向对象数据库9,10的数据模型与XML非常相似，它们都是层次树，都用的父子关系来描述数据之间的关系，都支持用户子定义复杂的数据类型，因此把XML映射到面向对象数据库中去是很容易的事，而且也可以利用对象查询语言（OQL）实现对XML数据的结构化查询，因此用面向对象数据库存储XML数据具有较高的存储和查询效率。但是它对于没有DTD或Schema的XML文档，无法定义映射规则。虽然文献11STORED系统可以采用数据挖掘技术来抽取XML文档的部分模式，但对于不符合模式的数据必须单独处理，而且对于模式经常变化的XML文档，该方法基本上不可能实现。在关系数据库方法中，XML数据被映射成关系表，同时，对XML数据的查询转换成SQL片段。同面向对象数据库和原生XML数据库相比，关系数据库具有数据结构化、最低冗余度、较高的程序与数据独立性、易于扩充、易于编制应用程序等优点11,12, 13, 14, 15, 16,17。它在存储管理，查询优化等许多方面都较其他系统远为成熟和稳定，而且现在流行的数据库绝大多数是关系数据库（如SQL Server、DB2、Oracle等都是第三代的数据库）。利用关系数据库存储XML数据，最大的优势在于可以利用关系数据库现有的存储管理、并发控制、恢复、版本机制等技术有效地管理数据，因此自然地成为了研究中的重点。可是利用关系型数据库来存储XML文档也有一定的困难，这主要是因为关系型数据库是完全结构化的模型，所表达的信息非常规则，但它无法表达一些层次性质的数据，而XML则是半结构化的模型，特别适合表达层次型的数据，更具灵活性。要实现关系型数据库存储XML，必须将一个完整的XML文档分割成多个相互关联的数据表，对XML数据的查询将涉及到多个表的访问和连接操作。因此要实现XML文档在关系型数据库中的存储，关键是要弄清楚XML结构与关系型数据库结构之间的映射。目前学术界已经提出许多XML的关系存储策略，但经过归纳，这些策略主要分为两类18：第一类方法是结构映射方法（Structure_mapping approach）14，它是根据XML的结构（DTD或XML Schema）来生成关系模式，不同的文档具有不同的存储模式，因此这种方法为每一种XML文档结构或DTD都建立一种适应于自己的关系模式，不同DTD的XML文档就会生成不同的关系模式，而查询又是基于存储结构的，因此如果关系表的数量和大小各不相同，在查询处理时就会增加查询的难度以及查询代价。第二类方法是模式映射方法（Model_mapping approach）12,它是将XML文档树中的节点和边映射为关系模式，得到的存储模式与XML文档结构无关，因此这种方第二章 XML的背景知识本文提出的基于关系数据库的XML文档的存储查询系统的处理对象是XML文档，因此我们先熟悉一下XML及其相关技术。在本章中介绍XML的背景知识、XML的相关概念和查询语言。2.1 XML的产生和特点今天，随着互联网技术的不断向前发展，XML(Extensible Markup Language)已经无处不在，它也逐渐成为信息交流的标准格式。XML的出现，超越了HTML的许多限制，提供了一个能够处理互联网上全部数据的通用方法。XML是W3C（World Wide Web Consortium，万维网协会）制定的用于描述数据文档中数据的组织和安排的结构的语言。正像它的英文名称中所指出的那样，它是一种标记语言。在这点上，它类似于HTML，但XML关注的不是数据在浏览器中如何布局和显示，而是关注于怎样描述数据内容的组织和结构以便数据在网络上进行交流和处理。XML之所以称为可扩展的标记语言，是因为它允许用户自行设计有意义的标记，并且它所创建的文档结构具有良好的层次和约束，可以使管理系统精确的识别信息所在的位置，易于表达文档数据，且非常适合非结构文档的全文处理，尤其是可以利用XML文档中的标记来确定在文档中的哪一部分查找，因此它使得对XML文档进行精确快速查询成为可能。XML语言的优秀特性主要体现在以下几个方面27,28： （1）简洁性：XML文档是建立在基本嵌套结构的一个个核心集的基础之上，它的语法包含一个非常小的规则集，使人类和机器都能更容易地阅读文档。XML的语法解析器也非常容易创建。 （2）开放性和可扩展性：XML使用的是公开、非专有格式，允许不同专业开发与自己特定领域有关的标记语言，不受版权、专利、商业秘密等知识产权的限制。并且XML可以进行扩展，用户可以利用它提供的DTD来交换数据，验证数据的有效性。（3）数据的结构性：XML是可扩展的标记语言，这种格式不仅仅能够以统一的格式定义数据，甚至能够封装与表示数据。这一特点，使XML成为数据交换的中介者，在异构语言、数据之间，异构数据库之间，提供交换信息的平台。 （4）互操作性：XML可以在多种平台上使用，而且可以用多种工具进行解释而且它能够支持世界大多数文字，因此它能超越不同的文化疆界交换信息。（5）纯文本：几乎任何工具都可以创建和编辑XML，使得程序可以更简单读写它。（6）可格式化：可扩展样式语言XSL可以指定如何显示数据。数据和显示分离，可以为同一数据制定不同的样式表用于不同输出。2.2 XML的文档类型XML的精髓是基于信息描述的、能够体现信息之间逻辑关系的、可以确保文件的易读性和易搜索性的自定义标记。XML的主要用途有两个，一个是作为元标记语言，定义各种实例标记语言标准；二是作为标准交换语言，担负起描述交换数据的作用。XML在互联网上扮演了“国际语言”的角色。在应用程序中引入XML，一般会涉及三个文档，包括普通的XML文档（扩展名为.xml）、DTD文档（扩展名为.dtd）、Schema（扩展名为.xsd），以下分别介绍。2.2.1 XML文档XML文档是基于文本格式的，它的最基本构成包括XML声明，处理指令和XML元素三部分27,28，另外还可以有注解，元素中还可以包含属性或者子元素等。XML声明一般出现在文档开头部分，包括版本号、可能的语言编码、可选的文档类型定义（DTD）等。格式正规的XML文档的定义形式是一个简单的层次树，每个文档都有一个而且只有一个根节点，它被称为文档实体或文档根。根元素出现在声明之后，它包括XML剩余部分。这一部分由元素、处理指令、属性、注释、实体引用等组成。XML规则要求文档中的元素是XML标记的基本组成部分，它必须有其实标记符合对应的结束标记符，而且应逐层嵌套。属性是元素的性质，属性表述了元素的开始标签内的信息，由字符组界定。XML中的注释以结束，注释可以出现在文档的任何位置。红楼梦曹雪芹100元另外，一个XML文档必须满足两点：良构（well-formed）和合法（valid）。遵循XML语法的文档叫做良构的文档，可以表示一定的语义信息。而一份附带有外部或内部DTD或者XML Schema的良构的XML文档，并且XML文档本体符合DTD或者XML Schema所声明的文件格式的XML文档才成为合法的XML文档。关于DTD和XML Schema的内容，在后面的章节中叙述。例2.1：以下是一个简单的XML文档示例。 这一示例清晰地描述了一本书的信息。由于XML主要应用于交换和发布信息，所以在应用XML之前，一般先定义DTD或Schema来规定XML应遵循的格式，以示的XML文档能真正用于数据共享与交换。第三章 基于路径的存储转换方法在引言中，我们已经比较了目前XML文档的三种存储方式，原生数据库和面向对象数据库技术都不成熟，并存在着自身的一些缺陷，因此，本文采用关系数据库作为存储XML的支撑平台。我们选择关系数据库主要有以下两个原因：（1）关系数据库技术成熟，使用广泛，用户不用为并发控制、安全性等问题作额外的工作；（2）在关系数据库中的查询优化技术和处理机制已经得到了充分的研究和发展。在实现对XML数据的存储时，最为基础且重要的一个步骤就是从XML文档到关系表定义（即关系模式）的映射，目前从XML到关系数据库的映射方法有很多，归纳起来分为结构映射和模式映射两种18。结构映射利用XML文档DTD或Schema的信息，将XML文档的模式信息映射为关系模式，因此，不同模式的XML文档或DTD就会对应不同的关系模式，映射时生成的关系表的大小和数量也会随着XML模式的不同而不同，这就为XML数据的查询带来了困难，加大了查询时的查询代价。目前Web上的信息大都是对XML灵活动态的使用，有的文档的DTD是预先未知的，有的文档结构良好但却没有DTD，有的文档的DTD是经常变化的，因此，结构映射不适合存储大量动态的、或结构易变的XML文档。 针对这些缺点，本文提出了一种新的XML文档基于路径的关系存储方法。该方法是一种模式映射，它使用固定的关系模式存储各种结构互异XML文档，并且这种关系模式不考虑文档DTD的信息，因此不受它变化的限制。由于这种映射方法产生的关系表结构固定，因此在XML文档查询时，也带来了极大的便利。下面我们具体阐述这种存储方法的内部机制。3.1 基于路径的存储结构这种基于路径的存储方法全面地考虑了XML文档树中的每个节点的信息、边信息和值信息，将XML文档中所有的嵌套关系都采用了两个表来存储：一个叫值表（Value_Table），它用来存储XML文档中所有有文本值的元素/属性的相关信息；另一个叫非值表（No_Value_Table），它用来记录XML文档中所有的无文本值的中间元素的相关信息。下面我们具体对这两个表的结构进行阐述。3.1.1 Value_Table在值表中，为了完整地记录XML文档中所有有值元素或属性的各种相关信息，该表中每一个记录是标识每个有值节点的一个六元组，即该表必须包括六列（或六个字段），如图3.1所示。这六列中存储的值分别为： Id：存储该元素/属性节点的序号，即对XML文档树中所有节点按先序遍历所产生的序号，它反映先序遍历文档树时该节点出现的次序；Name：存储该元素/属性名；Value ：存储该元素/属性的值，本文对属性和有值的元素进行同样的处理，均把它们存储在Value_Table中，把它们对应的属性/元素的文本值存储在Value字段中；Path：记录从根节点到该元素/属性的路径，即从根节点开始直到当前节点，并由/连接的元素标签的序列，我们简称为只包含父子关系的简单路径，它是以XPath的缩简形式给出31；Parentid：存储该元素/属性的父节点的Id；Level：存储该节点所在的层数。图3. 13.2 XML文档示例 T1 N1 M1 U1 P1 T2 N2 U2 P2 设置了值表后，XML文档中的所有有值的节点的相关信息都被完整地保存下来，并不会出现任何缺损。为了更好地验证这个表的正确性，我们以图3.2中的XML文档内容为例，说明如何把它其中所有有值的节点信息存储在值表中。作为一个连续使用的XML文档示例，我们在下文中所涉及的所有存储查询方法都将以图3.2中的文档为例。对该XML文档存储时，首先对它进行先序遍历，为文档树中的每个节点生成一个唯一标识它的id，并提取关于每个节点的所有有用信息，将它们通过代码段全部存储在到值表和非值表中。在这里，先介绍有值节点的存储。图3.3 值表的存储结果图3.3是该XML文档在值表（Value_Table）中的存储结果，在这个表中，把XML中的属性和有值的元素同等对待。它记录了该XML文档中两个属性和九个有值的元素的所有信息，分别为先序遍历的id，元素/属性名以及它们的值，同时还记录了它们所处的层数、父节点的id和从根节点到它们的路径。3.1.2 No_Value_Table 图3.4 非值表的各列信息图3.5 非值表的存储结果在关系数据库中设置的第二个表为非值表，它记录的是所有无值元素的相关信息。也就是说，它要完整地记录XML树中所有没有值的中间节点和根节点的信息，所以No_Value_Table必须包括四列（即四个字段），列名分别为：Id、Name、Parentid、Level，如图3.4所示。这四列中存储的内容都与值表中的含义相同。在这两个表中，Id均为主键，其内容不允许为空。设置了非值表后，XML文档中的根元素和无值的中间元素都被记录在内。我们依然以图3.2中的XML文档为例，来考察它存储结果的正确性。该XML在非值表中的存储结果如图3.5所示。从图3.3和图3.5中，我们可以清楚地看到XML文档转换为关系表的同时，它内部所有元素/属性的边信息和值信息也被无损地映射到这两个表中。这就完成了XML在关系数据库中存储和查询的最为关键的一步，其后的查询方法也是基于这种存储结构来实现的。结 束 语90年代以来，随着Internet/Web的迅速发展，XML作为Web上数据表示、交换和集成的事实上的标准，为众多的研究人员所研究。在各种XML处理方式中，关系数据库由于其成熟的技术和高性能，使得利用关系数据库来查询处理XML数据受到了广泛的关注，成为当前XML数据处理的主流方式，并在各种领域中得到了广泛使用。然而，XML和传统的关系数据库在数据模型、查询语言和应用场景等方面存在着较大的差异，利用关系数据库来存储和查询XML给传统数据库技术带来许多新的问题和挑战，如：如何有效地将XML数据库存储在关系数据库中、如何更新存储在关系数据库中的XML数据、如何将它重新发布为XML文档、如何在Web中有效地检索XML文档等等。本文集中研究了XML数据在关系数据库中的规范化存储、XML数据的查询、XML存储模式的优化等关键技术，提出了一种新的基于关系数据库的XML文档的存储查询方法，该方法用以无损地存储XML数据，并有效地处理了路径表达式的查询。并实现了相应的系统原形。本文取得的主要研究成果如下：（1）研究了XML数据在关系数据库中的存储问题，提出了基于路径的关系存储方法，该方法采用固定的关系模式存储XML文档，适用于无DTD或DTD易变的动态XML数据的存储。它能无损地记录了XML文档中的各节点信息、边信息和值信息，即在关系表中存储XML文档中所有有值元素/属性的路径，以及各元素的id、Parentid、Level等信息，加快了查询处理速度；（2）在基于路径的存储方法基础上，将查询XML数据的路径表达式转换为SQL语句，根据查询路径表达式中的连接符不同给出具体的转换规则和算法；（3）提出了基于路径的存储查询的优化策略，对于一个给定的文档，可根据它的层次结构选择相应的存储方法，从而在一定程度上减少存储冗余；对于简单线性路径表达式，为了减少了结构连接的次数，提出一种基于串匹配的查询方法，从而减少了I/O数量以及查询代价；（4）在上述成果的基础上，实现了原型系统，并利用实际的XML文档对其进行性能测试，实验证明，该论文的方法切实可行。基于关系数据库处理XML数据是目前国际数据库界最重要的研究方向之一，在这方面尚有许多问题亟待解决。本论文将来可能的工作包括：（1）该方法在查询处理时，对/的响应时间比较长，主要是由于表连接的次数参考文献1S.Abiteboul，P.Buneman，D.SuciuData on the web：From Relational to Semistructured Data and XMLMSan Franciso，California：Morgan，Kaufmann Publishers，20002K.Aberer edsSpecial Section on Advanced XML Data ProcessingJACM SIGMOD Record，ACM Press，2001，30（3）3Alon Y HalevySpecial Issue on XML Data MamagementJIEEE Data Engineering Bulletin，IEEE Computer Society，2001，24（2）4许卓明，刘琴，董逸生基于关系数据库的XML存储技术评述J计算机工程与应用，2003，39（10）：197-2005黄莹，杨明福XML文档的存储方法研究J计算机工程，2002，28（5）：281-2836Thorsten Fiebig，Sven Helmer，Carl-Christian Kanne，etcAnatomy of a Native XML Base Management SystemCThe VLDB JournalDecember 2002，11(4)：292-3147Xiaofeng Meng，Daofeng Luo，Mong Li Lee，etcOrient Store：A Schema Based Native XML Storage SystemCThe 29th VLDB ConferenceSeptember 2003：1057-10608李骥，陈福生Native-XML数据库综述J计算机工程与设计，2004，25(6)：932-9349A. RennerXML Data and Object Databases：A Perfect CoupleCProceedings of the 17th International Conference on Data Engineering，Heidelberg，Germany，2001：143-14810Rick Catte et al，The object data standard：ODMG3.0MMorgan Kaufmann Publishers，200011A Deutsch，M Fernandez，D SuciuStoring Semistructured Data with STOREDCProceeding of ACM SIGMOD International Conf on Management of Data，Philadephia，PA，USA，ACM Press，1999：431-44212D.Florescu，D.KossmannStoring and Querying XML Data using an RDBMSJIEEE Data Engineering Bulletin，IEEE Computer Society，1999，22(3)：27-34致 谢值此论文完成之际，我首先要衷心感谢我的导师，从最初收集资料、研究资料到系统的逐渐实现，直至论文的最终完成，这其中每一个阶段都倾注着老师的心血和汗水。没有他严格精心的指导和细致入微的帮助，就没有本文的顺利完成，也没有我三年来在科研和学习方面的进步。他严谨的治学态度和勤奋的工作作风对我的影响，使我终身受益。除了在学业上对我悉心指导外，老师还在生活中给了我无微不至的关怀和帮助，这都终将成为我脑海中尤为深刻的记忆。最后，我要感谢我的家人在这多年的学习和生活中，对我学业的支持与理解，还有那博大无私的爱！这一切都将成为我终身受用的财富。