论文部分内容阅读
网络应用的快速发展,尤其是电子商务、Web服务等应用理念的进一步发展,使得企业和个人通过网络进行数据交换变得越来越频繁,迫切需要一个为大家普遍接受的数据表示方式来对网络数据的交互格式进行统一。XML(Extensible Markup Language),即可扩展标记语言应运而生,它是一套定义语义标记的规范,其目的在于定义计算机和人都能方便识别的数据类型。XML类型的数据已成为当前主流的数据形式,并成为事实上的数据表示标准。怎样对XML文档进行高效索引和快速查询也成为了当今数据库领域的一个研究热点。为了从XML以及半结构化数据中获取所需要的信息,研究人员开发了许多查询语言,如Lorel,XPath和XQuery等等。所有这些查询语言有个共同的特点,即通过路径表达式实现对XML文档的路径查询。为了提高XML路径查询的效率,许多专家和学者致力于XML文档索引的建立。XML的模式信息(DTD或XMLSchema)对于XML索引的建立以及查询效率的提高,可以产生很大影响。目前,DTD和Schema是XML使用最多的模式信息,本文分别针对DTD和Schema这两种模式信息,提出索引的建立方法。该方法的主要思想是分别为XML模式和XML文档建立索引,建立模式索引的目的是在XML模式中快速定位指定名称的元素或属性,建立XML文档索引是为了在模式索引得到的信息的基础上,在各个XML文档中找到最终所要查询的元素或属性的实例。查询时,首先在模式中查找,如果查询路径在模式树中是不合法的,即模式中没有与查询路径相匹配的结构,则可以肯定,在相应的XML文档中也不存在与查询路径相匹配的结构,所以不需要到XML文档中查询,直接给出“无查询结果!”的结论;如果查询表达式在模式树中是合法的,则根据文档中结点与模式中结点的对应关系进一步在文档树中查找,最终得到查询结果。该索引结构利用模式信息减小了搜索空间,并通过改进的结点编码方法减少了查询时代价高昂的结构连接的次数,有效缩短了查询时间,提高了查询效率。大多数索引的研究忽略了数据更新时索引的维护,本文在对XML文档中的结点进行编码时,采用了一种扩展的Dewey编码方法,这种编码方法能有效保证数据更新时的一致性,并且在插入、删除结点时,不影响已有结点的编码,即对已存在的结点不需进行重新编码。由于在索引中加入了模式信息,在数据更新之前,可以通过判断这种更新是否会产生不符合模式的非法数据来确定更新操作是否执行,因此,这是一种基于有效性验证的动态更新,保证了数据的合法性。本文所做的主要工作在于:(1)提出了新的基于复杂DTD的XML索引方式CDBXI和基于XML Schema的XML索引方式SBXI,详细描述该索引方式的系统结构、编码方法。(2)给出了对采用文中索引结构的XML数据进行各种查询的算法以及查询操作的步骤。(3)讨论分析了在进行数据更新时,索引的维护问题。并给出了在增加、删除结点时,该索引的具体维护算法。(4)通过数据分析和实例比较,证明了本文中提出的索引方法,无论是在索引的建立,还是在进行各种查询操作(尤其是无效查询)以及插入、删除时索引的维护上,均具有较高的效率。