万里勇[1]2012年在《基于索引技术的XML查询优化研究》文中研究说明如今XML数据被广泛应用于不同领域,其数据和文档规模不断增大,数目不断增多,导致网络中出现了大量的具有复杂结构的XML数据。如何高效管理和查询结构复杂的XML数据是当前人们面对的一个普遍且关键的课题。在过去的十多年中,众多的研究人员和学者从不同的角度提出了各种查询优化的方法,其中利用编码的索引技术是实现查询优化最常用的重要手段之一。在查询优化设计中,充分考虑编码的索引技术,可以很好的实现对XML数据查询优化的需要。因此,结合编码与索引技术来对XML数据查询优化进行探讨,仍然是一个值得深入研究的课题。论文在二叉树遍历的编码基础上,引二叉树的叁叉链表存储结构对XML文档结点进行编码。设计出一种基于二叉树遍历XML文档编码模式。该编码模式利用二叉树的叁叉链表结构来存储XML文档树的结点,用自然数作为结点的编码序号。采用该编码模式作为XML文档树结点编码,选取合适关键词作为索引项,利用二叉排序算法为XML文档建立了相关索引模型。论文在传统区间编码基础上,利用倒排表和B+树作为基本的索引组织,设计出一个由DTD结构索引、XML文档索引和内容索引组成的联合结构索引模型。其中DTD索引采用倒排表作为索引基本单位,XML文档索引采用B+树来建立,内容索引则采用倒排表。在处理的查询时,只要通过一个入口即可以找到其它索引项来完成一个综合的多种查询处理要求。理论与实验结果分析表明,论文中基于二叉树遍历的编码模式,具有存储空间小和查询效率高,且支持动态数据更新操作。以此编码建立的索引具有空间开销小、查询响应速度快和查全率高的特点；以区间编码作为文档树结点编码,建立的联合结构索引模型,处理数据查询时具有较高查询效率,能够满足多文档查询的需求并且满足了对XML文档混合型优化查询(文本查询和结构查询)等需求。
杨梅[2]2007年在《XML数据的查询优化研究》文中指出Web技术的飞速发展使得Web逐渐成为人们获取、传播和交换信息的重要途径。随着信息量的急剧增长,如何表示和交换多样化的Web数据成为关键问题。继HTML(Hyper Text Markup Language)之后,XML(eXtensible Markup Language)已经逐渐成为互联网信息的主要表示和交换工具。与HTML不同,XML实现了文档数据内容与表达的分离,从而有利于信息共享和检索,但同时XML文档的非结构性为其组织、管理和检索带来了极大的困难。XML文档的特性使其区别于关系和对象等结构数据以及传统的半结构数据而成为一种独特的数据,因此如何高效地获取有用的XML数据并对XML查询进行优化处理成为新的研究课题。为了实现XML数据的查询优化,近年来人们相继提出了很多索引技术和连接算法,这些索引主要是根据边标签和元素值建立的。然而有的索引不包含所有的元素节点,因而在进行查询时许多路径仍需要检测;有的在向前或向后遍历时产生了大量的冗余数据,从而造成查询代价较大。本文对XML数据查询方面展开研究,在查询语言、数据模型、基于索引的查询优化等方面做了以下几个方面的工作;(1)就本文需要的Schema模式围绕XML查询语言做了研讨,在此基础上提出了查询算法普遍的瓶颈问题。(2)鉴于现有的数据库产品在管理XML数据上的优越性,针对XML数据在关系数据库中的存储方式,对XML数据和关系表之间的固定模型映射进行了研究,并实现了叁种不同粒度的存储模型。(3)提出了基于Schema的通用路径表达式(GPE)转化为简单路径表达式(SPE)的新方法G2S,该方法是XML查询优化的重要步骤。G2S是一种启发式的方法,它利用Schema中的XML文档的统计信息来改写GPE为SPE。(4)提出利用Schema生成关系模式,并在此基础上提出一种基于Schema的XML数据结构索引,结合Schema的数据字典提出了OB(Orthogonal B+tree)树的存储方式,可快速的确立元素间关系,减少元素访问及路径连接次数,从而缩短路径查询的响应时间,提高了查询的效率,具有一定的实际意义。
郭松涛[3]2003年在《XML结构索引技术及查询优化研究》文中研究指明为了实现XML的查询优化，近年来人们相继提出了很多索引技术和连接算法[12,13,14,15,16,23,24]。这些索引主要是根据边标签和元素值建立的。然而有的索引不包含所有的元素结点，因而在进行查询时许多路径仍需要检测；有的在向前或向后遍历时产生了大量的冗余数据，从而造成查询代价较大。另外，在所提出的算法中，尽管有的算法，如MPMGJN算法[23]优于标准的RDBMS连接算法，但是该算法为匹配基本的结构关系，特别是在父子关系情况下，执行了大量不必要的计算和占用了大量的I/O资源；有的算法虽然代表了结构连接算法的先进水平，如Stack-Tree-Desc[24]连接算法，但是它没有利用索引结构而是顺序浏览输入列表。这样，必然浪费I/O资源，影响连接的速度。针对以上情况，本文做了以下几个方面的工作：① 由于采用传统的Numbering Schema方法来表示XML文件结构不便于元素更新，本文在改进的基础上提出了Sparse Numbering Schema方法。与传统方法相比，其优点在于：由于在插入新结点时不需要重新计算其结点的start和end值，树结构更新效率得到提高；树的创建只需遍历一次文档，进一步地节省了建树开销；此外，它还能为索引提供一个相对持久和稳定的参考。② 鉴于目前关于Numbering Schema存储方法的研究较为少见，本文针对Sparse Numbering Schema进行研究，给出了在关系数据库中的存储方法。该存储方法不仅有利于根据start值快速建立索引，而且可以节省存储空间。③ 本文将关系数据库中B＋树索引技术与Sparse Numbering Schema相结合，提出了一种新的XML文件索引结构——B~+树结构索引，它对XML查询中连接操作和元素定位操作的优化有着重要作用。进而，通过引入指针对该索引进行改进，提出了一种带有Sibling Pointer的B~+树结构索引（简称B~+-SP）。利用这种索引可以克服元素查找总是从树的根部开始进行的缺陷。④ 基于B~+-SP索引，本文还研究给出了Anc-Desc-B~+-sp连接算法。经理论分析，其算法的时间复杂度O(|A|+log|A|)比没有采用该索引的Stack-Tree-Desc算法[24]的时间复杂度O(|A|+|D|+|outlist|)明显降低，因|D|≥|A|，故|D|+|outlist|>>log|A|。经初步实验表明，本算法是一个有效、快速的连接算法。⑤ 在XML查询中，影响查询时间的另一个重要因素是对涉及的XML数据源的定位问题。为解决XML数据源的快速定位问题，本文提出了一种分布式XML数据源定位系统框架，协作式XML搜索引擎（CXSE）。CXSE通过基于站点选择搜索和对XML数据源计分等方法来缩短收集时间，来实现对XML数据源的快速、准确定位。特别地，当在XML查询中同时涉及多个XML数据源时，该并行搜索技术也能起到一定的效果。
曲卫民[4]2004年在《中文XML信息检索系统的研究》文中研究指明XML信息检索系统与传统的信息检索系统不同，主要体现在：建立索引时不仅需要建立倒排文本索引，还需要建立结构信息索引；查询处理时不仅需要处理关键字查询条件，还需要处理结构化查询条件。为满足结构复杂、大规模的XML数据管理需要，本文深入研究了XML信息检索系统中的结构索引算法设计和结构化查询优化中的查询代价估计问题，以及查询结果和查询条件间的相关度算法，主要取得了4个方面的成果：第一，分析了已有的XML数据索引算法中存在的问题，提出了一种高效的动态XML结构索引算法DifX，它采用动态后向结构相似性(D-Bisimilarity)的概念，可以根据实际查询需求以及索引最优化的要求动态决定索引中保存的结构信息。第二，为考虑XML数据中的结构信息对查询结果相关度值的影响，本文提出了一种综合考虑关键字频率分布特征和结构分布特征的查询结果相关度算法，以及一种基于节点的关键字权重计算法，取得了更优的检索性能。第叁，分析了XML结构化查询优化中的查询代价估计问题与传统关系型数据库中的查询代价估计问题的区别，提出了一套完整的XML结构化查询代价估计体系SXM，包括对简单路径表达进行查询代价估计的动态XML数据统计模型XMap，对复杂路径表达进行查询代价估计的双焦点例举法，以及对值匹配条件进行查询代价估计的基于小波的多维直方图方法，并能将多种查询表达的查询代价估计结果结合在一起，以给出一个完整的XPath查询的代价估计。SXM有效解决了XML结构化查询代价估计中存在的结构不规则、查询表达复杂、数据间相互依赖关系复杂等问题。第四，设计和开发了一个中文XML信息检索系统的核心功能原型——W2X(Way to XML)。W2X是一个中文XML信息检索系统，它可以管理富含文本信息的XML数据和富含值信息的XML数据，并采用了高效的XML结构索引算法和查询处理算法，可以完成对大规模XML数据的检索。 总之，本文的研究成果为建立高效、准确、实用的XML信息检索系统打下了坚实的基础。
雷向欣[5]2004年在《XML索引和过滤查询若干关键技术研究》文中认为XML(eXtensible Markup Language)作为网络数据交换和信息集成的工具,以其自描述性、跨平台交换性等特点,成为新一代的网络语言。互联网上越来越多的结构化或半结构化的数据采用XML格式存储和交换,对XML数据的索引及过滤查询研究显得日益重要。 本文根据XML数据的自身特点和当前实际应用需求,就索引和过滤查询的一些关键技术进行了研究,具体包括XML文档索引查询技术研究、XML文档树节点编码研究、遵循不同模式XML数据集索引模型、集群式XPath查询优化、XML数据过滤查询技术研究、XML文档索引和过滤查询原型系统的实现等方面,所做的工作和取得的创新成果体现在以下五个方面: 1) 基于互关联后继树的XML文档索引技术研究 基于叶序区间编码方法(LOINS)与互关联后继树模型(IRST)为节点带有名称(标签)的根树建立索引模型。结合IRST的标引性、可压缩性等特点,本文提出了基于IRST的根树索引模型IsBaRTI-Ⅰ,及该模型的空间优化模型IsBaRTI-Ⅱ。IsBaRTI-Ⅰ,Ⅱ采用树节点名称(标签)及其在根树(XML文档树)中的出现计数索引节点间的父子关系和节点叶序区间编码,实现索引结构和节点编码的相互统一。理论和实验证明,在对XML路径表达式的查询处理中,和以往同类索引模型相比,IsBaRTI-Ⅰ,Ⅱ索引建立时间、空间代价小,而且可快速查询满足XPath表达式在XML文档树中的节点序列和路径。 2) XML文档树节点叶序区间动态编码研究 在XML索引上采用树节点编码可快速判断树节点间的前后代关系,树节点编码代价影响着索引的空间代价和驻留内存空间的难易程度。区别于以往同类索引模型研究仅仅注重提高查询效率的片面性,本文针对Web上XML文档特点,就本文索引技术中的树节点叶序区间编码和其它树节点编码方法,如:顺序标识区间编码、前缀编码等进行比较。相比其它树节点编码方法,本文提出的叶序区间编码方法编码长度代价小、编码灵活机动性强(可通过IsBaRTI-Ⅱ在索引结构中动态查找)。我们提出的根树索引模型IsBaRTI-Ⅱ动态查找叶序区间编码的平均时间代价随着S/H(S为根树Tr节点出度;H为Tr高度)递增而递减且趋近于1,而Web上XML文档树普遍具有的S>>H的特点为基于IsBaRTI-Ⅱ实现的XML索引模型动态查找叶序区间编码提供了实际应用可行性。就树节点叶序区间编码的维护,本文提出了基于XML模式扩展叶序区间编码的方法,降低XML文档树节点插入时的索引中节点编码维护代价,为基于叶序区间编码的XML索引模型提供了编码维护方案。
张峻玮[6]2011年在《移动商务环境下的XML查询优化研究》文中研究说明随着无线通信技术、互联网技术和计算机技术的不断发展,移动商务应运而生,在移动应用的领域展示了其巨大的发展潜力,也在电子商务领域分得了一定规模的市场。移动商务的发展为商务活动开辟了新天地,消费者可以使用各种无线终端进行随时随地的商务活动。而目前各种终端设备和网络服务器并没有统一的系统平台,数据共享和数据集成过程中就需要XML这种可以跨平台的通用语言来解决,所以XML的查询效率在移动商务的环境下是很关键的问题。本文研究了移动商务的发展现状和趋势,分析了移动商务平台的系统架构来说明XML在移动商务环境下的应用情况,研究了XML技术中的模式语言和查询语言,为了在查询过程中充分利用XML Schema中的结构信息以提高查询效率,本文在研究XML编码的基础上给出了新的编码方案,并研究XML现有索引技术,分析各种方式的不足,提出了基于XML Schema的索引结构,为每个XML节点记录了结构信息,以提高查询速度。同时本文给出了基于SRSTI索引的详细查询方案,并用实例进行了说明。本文解决了用户不了解XML文档结构的情况下输入查询需求的问题,设计了友好的图形化用户界面,同时设计并实现了查询方案,比较了SRSTI与SphinX和XISS的索引建立时间和查询效率,实验证明SRSTI效率有一定的提高,尤其能高效处理无效结构查询。
范颖捷[7]2008年在《XML索引与查询的若干关键技术研究》文中提出随着Internet的快速发展,XML已成为Web数据表示和交换的新标准,越来越多的信息处理系统采用XML文档作为信息存储、交换和发布的载体。与此同时,XML文档结构和用户查询需求也变得越来越复杂,包含大量引用边的图结构XML文档,以及仅包含部分路径信息和关键词的XML IR(Information Retrieval)查询变得越来越普遍,这给XML索引与查询技术提出了严峻的挑战。目前XML索引技术的研究主要集中在3个方面:一是面向XML有向树的节点记录类索引;二是面向XML有向图的结构摘要类索引(即XML结构索引);叁是XML数据与全文数据的联合索引。与节点记录类索引相比,后两类索引的研究相对薄弱,索引的整体性能还比较低,离实际应用还存在较大的距离。针对XML结构索引目前存在的主要问题:索引创建时间较长、空间开销较大、查询效率较低以及分支路径查询研究较为薄弱,本文提出了叁种高效的结构索引;针对XML数据与全文数据的联合索引目前存在的主要问题:缺少XML数据与全文数据的统一索引模型以及配套的高效协同查询机制,本文提出了一种高效的基于统一索引模型的XML联合索引。本文的研究内容和创新工作主要有以下4点:(1)支持简单路径查询的半动态XML结构索引研究本文在互关联后继树(IRST)的基础上,引入一种新型的相似性约束条件——k阶相似关系,以及结构索引的相似性归并思想,提出了一种基于互关联后继树且支持简单路径查询的高效半动态结构索引——IRST(k)-index,并给出相关算法和理论证明。该索引以互关联后继树为实现方式,以k阶相似关系为相似性约束条件,能高效地查询简单路径表达式。经实验验证,与国际上同类索引相比,该索引的创建速度更快、查询效率更高、空间开销更小。(2)支持分支路径查询的半动态XML结构索引研究本文在IRST(k)-index的基础上,引入一种新型的相似性约束条件——k-l阶相似关系,以及前向、后向相似度的概念,提出了一种基于互关联后继树且支持分支路径查询的高效半动态结构索引——IRST(k,l)-index,并给出相关算法和理论证明。该索引以互关联后继树为实现方式,以k-l阶相似关系为相似性约束条件,能高效地查询分支路径表达式。经实验验证,与国际上同类索引相比,该索引的创建速度更快、查询效率更高、空间开销更小。(3)支持分支路径查询的全动态XML结构索引研究本文在M(k)-index的基础上,引入k-l阶互模拟关系以及前向、后向相似度的概念,提出了一种支持分支路径查询的高效全动态结构索引——MBF(k,l)-index,并给出相关算法和理论证明。该索引以k-l阶互模拟关系为相似性约束条件,不仅能高效地查询分支路径表达式,还能利用频繁查询路径的查询结果来监督和指导索引优化的全过程,从而有效地避免了无关索引和数据节点的过度分裂。经实验验证,与国际上同类索引相比,该索引的查询效率更高、空间开销更小。(4)XML数据与全文数据的联合索引技术研究本文在互关联后继树的基础上,提出了一种XML树型结构与全文数据的统一索引模型——基于后继模式树的互关联区间后继树,建立了一套XML文档的树型结构与文本节点的联合索引机制——XML联合索引,并给出该索引的倒向创建算法和协同查询算法。经实验验证,与国际上同类索引相比,该索引的膨胀比更小、查询效率更高。
王慜[8]2011年在《基于PAT代数的XML数据查询优化方法研究》文中提出互联网中包含着大量的半结构化的XML数据,正是因为这种半结构化特性,使得用传统的数据库查询优化技术来检索数据十分困难。如果通过代数系统对XML查询表达式进行转化,然后应用代数转化规则对表达式进行优化处理,则能够较为有效的提高XML数据的查询效率,该研究方法已成为当今XML数据查询优化领域的一个研究热点。目前XML代数的研究重点在于规范XML查询语义,并未考虑查询优化因素,而且这些代数具有明显的程序化思想,很难进一步优化,只能利用遍历方法求解查询,造成查询效率的低下,不适用于大规模XML数据的查询需求。论文通过对当前XML数据查询优化技术进行总结与分析,借鉴已有XML查询优化技术,采用面向集合的PAT代数系统,提出了一种基于PAT代数的查询优化方法。论文首先通过对现有XML查询优化技术和XML数据的查询优化体系进行研究与分析,提出了一种基于结构索引的查询优化方法。该方法能够缩短查询路径,从而提高查询效率;然后,通过对PAT代数系统的查询等价式进行分析,并根据这些等价式转化方法对PAT代数进行扩展,结合启发式的思想提出了基于PAT代数的确定性转化规则体系以及基于结构索引的规则转化方法。最后,论文通过使用扩展后的PAT代数表达式转化规则对XML查询表达式进行代数转化,并结合文中提出的语义优化策略,能够较为合理地清除冗余操作,化简查询表达式,从而减少了代数操作次数;运用文中提出的索引引入策略,把结构索引引入到查询表达式代数转化过程中,有效缩短了查询路径。经实例验证与性能分析,论文提出的查询优化方法能够较为有效地提高了XML数据查询的查询效率。
张博, 耿志华, 周傲英[9]2009年在《一种支持高效XML路径查询的自适应结构索引》文中认为提出了一种新的自适应结构索引:AS-Index(adaptive structural index),能够克服现有静态索引和自适应索引的缺陷,具备高效的查询和调整性能.AS-Index建立在F&B-Index的基础之上,其索引结构包括F&B-Index,Query-Table和Part-Table.Query-Table能够记录频繁查询,避免了查询过程中的冗余操作.并且,在Query-Table的基础上提出了自底向上的查询处理过程,能够充分利用现有的频繁查询高效地回答非频繁查询.Part-Table用于优化包含祖先后裔边的查询,进一步提高了查询性能.现有的自适应结构索引的调整粒度是XML元素节点,调整过程往往需要遍历整个文档.而AS-Index是基于F&B-Index节点的增量调整,其过程是局部的,高效的,并且能够支持复杂分支查询的调整.实验结果表明,AS-Index在查询和调整性能上优于现有的XML结构索引.同时,相比于现有的自适应结构索引,AS-Index针对大规模文档具有更加优良的可扩展性.
邵峰[10]2008年在《XML数据管理中的结构查询技术研究》文中研究表明随着互联网技术迅猛发展,XML已逐渐成为数据表达和数据交换的标准。越来越多的Web数据通过XML文档形式呈现。如何有效管理这些XML数据,是当前数据库领域一个重要研究课题。XML数据具有半结构化特征,其存储、查询、更新比传统结构化数据更为复杂。使用传统数据库技术解决XML数据管理问题,其效果不佳。为此,需要根据XML数据特点,研究开发新的XML数据管理技术。本文主要研究XML数据管理中的结构查询处理。XML结构查询是XML所特有的一类查询,其查询条件为XML结构约束,以路径表达式形式出现。在XML数据查询中,XML结构查询占有基础地位,许多已知的XML查询语言,如XQuery,XPath等,都以XML结构查询作为其核心部分。因此,高效的XML结构查询处理在XML数据管理中非常重要。本文根据路径表达式的不同,对XML结构查询实行分类处理,从而提高其查询效率。首先,本文提出了一种多分类XML结构查询处理框架MCXArch,具体描述了该框架的两个重要组成部分:查询执行模型MCXEng和查询优化模型MCXOpt。在模型MCXEng中,给出了各类查询执行算子。在模型MCXOpt中,给出了多类结构查询优化规则。接着,本文围绕MCXArch框架,分析研究了四个XML结构查询关键技术点:XML线性路径匹配;XML分支路径匹配;XML结构查询加速和XML包含连接估计。在XML线性路径匹配研究中,本文提出了两种新匹配算法:整数差值匹配法和约简式遍历匹配法。整数差值匹配法用于XML简单线性路径匹配;而约简式遍历匹配法主要用于XML复杂线性路径匹配。这两种匹配算法都通过约简方式,提高查询匹配效率。在XML分支路径匹配研究中,本文给出了两种启发式匹配算法:Heur-PC和Heur-Unnested。算法Heur-PC用于简单分支路径匹配;算法Heur-Unnested用于非自嵌套分支路径匹配。与先前的小枝连接类匹配算法相比,两种启发式算法所需的查询匹配时间更少。在XML结构查询加速研究中,本文提出了一种位图过滤加速法。利用前/后缀标签位图,该方法能加速多类查询匹配算法,如遍历类匹配算法、连接类匹配算法等。本文给出了过滤加速原理,并研究了位图过滤加速法与查询匹配算法的集成。在XML包含连接估计研究中,本文给出了一种权重哈尔小波的估计方法。在预处理阶段,使用哈尔小波,压缩统计数据,生成小波摘要。在查询估计阶段,利用小波系数重构,获取XML包含连接估计值。同时,在估计方法中,使用概率权重模型,体现查询负载变化。在相同的空间限制下,权重哈尔小波估计法比先前的XML包含连接估计法具有更小的估计误差。
参考文献：
[1]. 基于索引技术的XML查询优化研究[D]. 万里勇. 中南大学. 2012
[2]. XML数据的查询优化研究[D]. 杨梅. 湖南大学. 2007
[3]. XML结构索引技术及查询优化研究[D]. 郭松涛. 重庆大学. 2003
[4]. 中文XML信息检索系统的研究[D]. 曲卫民. 中国科学院研究生院（软件研究所）. 2004
[5]. XML索引和过滤查询若干关键技术研究[D]. 雷向欣. 复旦大学. 2004
[6]. 移动商务环境下的XML查询优化研究[D]. 张峻玮. 首都经济贸易大学. 2011
[7]. XML索引与查询的若干关键技术研究[D]. 范颖捷. 复旦大学. 2008
[8]. 基于PAT代数的XML数据查询优化方法研究[D]. 王慜. 兰州理工大学. 2011
[9]. 一种支持高效XML路径查询的自适应结构索引[J]. 张博, 耿志华, 周傲英. 软件学报. 2009
[10]. XML数据管理中的结构查询技术研究[D]. 邵峰. 浙江大学. 2008
标签：计算机软件及计算机应用论文; xml语言论文; xml数据库论文; 索引论文; 关系模型论文; 空间数据论文; 关系代数论文; 动态模型论文; schema论文; 算法论文;