论文摘要
XML随着互联网的飞速发展应运而生,已经成为网络上数据表示和交换的基础。XML在各个领域得到广泛应用,研究人员在XML的存储模式、查询处理、以及文档索引等方面都进行了深入的研究,并获得了丰硕的成果。然而,现有XML查询引擎存在自适应性能低,缺乏对多查询的批量处理以及低效的查询复用性等问题,影响了查询引擎的查询性能和可扩展性。本文首先对现有的XML索引的不同方法进行了综述,介绍了XML索引中的相关概念,阐述了典型的XML索引的构建方法和主要技术,分析了现有索引的特点和存在的问题,概括了文本索引、元素索引、路径索引、序列索引等不同类型索引的研究内容,梳理了各类索引的发展脉络和思想来源,并对不同的方法实现进行了总结,结合现有的应用和研究成果,展望了XML索引未来的发展方向及其面临的挑战。同时,本文剖析了XML缓存设计中涉及的相关问题,总结了现有XML缓存系统的方法,并分析了各种缓存系统的优缺点和应用环境。根据现有索引和缓存技术中存在的问题,本文在XML自适应索引,支持多查询处理的XML索引以及XML缓存等方面进行了深入的研究和探讨,提出了高效的算法和相关技术,并通过大量的实验与现有方法进行了对比,从实验角度证明了本文所提出的算法的有效性,以及算法在不同查询类型和数据集上的可扩展性。本文的研究成果不仅在理论上具有指导意义,而且在实际应用中也具有实用价值。本文的具体工作包括:1)设计了具有高效调整性能和查询性能的自适应索引AS-Index。自适应索引具有根据用户查询动态调整索引结构的特点。调整后的索引能够高效的回答频繁查询,从而提高索引的整体性能。在本文中,我们设计了新颖的自适应索引。与以往的自适应索引不同,我们的自适应索引具有以下特点。首先,我们的自适应索引具有高效的调整性能。通过增加调整粒度,可以以一组结点为单位进行分裂或者聚合操作,而不同于以往的以单个结点为单位的调整操作。其次,通过探索查询之间的包含关系,我们的自适应索引可以实现局部的调整过程,缩小了调整范围,避免调整过程对整个索引的影响。最后,我们设计高效的查询过程,特别是针对非频繁查询,能够充分利用索引结构中的频繁查询来回答非频繁的查询,使得查询过程在一个局部中进行,有效的提高了查询性能。2)设计了能够支持多查询批量处理的结构索引SIMP。现有的索引都是依次执行查询,考虑多客户端-服务器端环境,多个客户端传输查询到服务器端执行,所传输的查询可能包括很多重复查询,而且不同的查询之间也会包含很多共享的部分。重复执行这些相同的查询或查询部分会引起不必要的开销,增加服务器端的负担。另一方面,现有索引在查询操作中依赖导航匹配。很多前期匹配的结点可能无法导致最终的匹配结果,这些无结果导航同样会增加服务器端的开销。在本文中,我们探索回答多查询的索引方法。首先,我们为XML文档建立索引,聚合文档中的相同路径,并且能够增加文档索引的过滤能力,尽可能过滤无结果的查询。其次,为一组查询建立合适的索引,聚合相同查询及其查询中的共享部分。在以上两种索引的基础上,我们设计了新颖的查询方法,能够同时处理一组查询。查询过程使用基于哈希连接的方法代替导航匹配,能够尽量过滤无结果查询,避免不必要的冗余操作。我们进一步提出了一系列的优化措施,用于扩展索引支持的查询类型,提高一组查询中的共享部分,提高频繁查询的查询性能。3)设计了具有较高性能的XML缓存系统UD-Cachc。缓存技术是加速查询的重要方法之一。在本文中,我们设计了新颖的XML缓存系统。我们首先设计了更加宽松的可回答标准,能够比现有的缓存系统具有更好的命中率。在此可回答标准的基础上,我们提出了高效的视图选择和视图回答方法,只要使用一遍扫描就能在含有上百万的视图中确定是否含有合适的视图,避免了现有缓存中的多次扫描过程。并且设计了紧缩的XML文档总结,用于辅助执行视图回答过程。现有缓存系统的视图回答过程是向下的查询过程,本文中缓存系统的视图回答过程包括向上的验证过程和向下的查询过程。最后,通过一系列的优化方法,本文进一步优化了提出的缓存系统。总之,本文对现有的XML索引和缓存技术进行了深入的分析和比较,根据现有技术的缺陷和不足,提出了针对用户查询的自适应索引、支持多查询的索引以及高效的XML缓存技术,并使用不同类型的查询和数据集对本文提出的方法进行了验证。实验证明,本文提出的方法在不同类型的数据集上具有高效的查询性能,并可以扩展到不同的文档大小和查询类型。本文中提出的技术可以应用于原生XML数据库,用来加速查询处理。也可用于关系数据库中XML文档或片断的查询处理,结合原生文档查询和关系数据库的查询引擎特点,具备良好的灵活性和可扩展性。