搜索
东北大学硕士学位论文XML复杂路径表达式查询处理技术研究姓名：周博申请学位级别：硕士专业：计算机软件与理论指导教师：于戈20031201XML复杂路径表达式查询处理技术研究作者：周博学位授予单位：东北大学相似文献(9条)1.学位论文付兴宏基于XMLSchema的文档验证技术研究2004XML是可扩展标记语言的简称，它为Web上的结构化文档和数据提供了通用的格式。随着Internet的发展尤其是Web技术的广泛应用，越来越多的应用采用了XML技术作为信息表示和数据交换的标准，这使得通过数据库技术对XML数据进行管理变得越来越重要。在关于XML的数据管理技术中，数据验证是比较重要、且使用比较频繁的组成部分，在维护数据安全和有效性方面扮演着十分重要的角色。XMLSchema作为描述XML的新的W3C推荐标准，以其丰富的数据类型和灵活的结构描述等优点，被许多系统所使用，越来越多的人开始研究基于XMLSchema的数据验证技术。针对XMLSchema规范中规定的复杂数据类型的结构描述，本文提出了一种称为模式自动机(SchemaAutomaton)的数据结构，讨论了将XML模式结构转换成模式自动机的方法，设计并实现了一种自动机验证算法来验证实例XML文档的有效性，以解决XML结构正则表达式验证的问题。自动机验证算法可以在模式空间内高效地验证每一个获得的XML数据，因此具有很高的效率。2.期刊论文余双.曹冬磊.戴蓓洁.金蓓弘.YUShuang.CAODong-lei.DAIBeio-jie.JINBei-hong高效XML验证技术的实现-计算机工程与设计2008,29(4)XML解析器是分析、处理XML文档的基础软件.对XML解析器的高效验证技术进行了研究,实现了支持StAX接口的验证型解析器OnceStAXParser2.0.该解析器采用了多项性能优化措施,包括属性验证的高效实现、元素验证自动机的优化、基于统计的预测算法等.性能测试表明,在进行验证的条件下,OnceStAXParser2.0具有出色的解析性能.3.期刊论文胡孔法.刘海东.陈峻.达庆利.HUKong-fa.LIUHai-dong.CHENLing.DAQing-li一种改进的可扩展标记语言查询增量维护算法-计算机集成制造系统2008,14(11)为降低可扩展标记数据查询执行器重新构建的代价,提出了一种基于树型结构的可扩展标记语言查询增量维护算法.该算法利用树型结构进行可扩展标记语言数据流查询执行器增量维护,利用自动机来表示状态转换,从而实现了对可扩展标记语言树型结构的动态维护,避免了在没有文档类型定义情况下出现的环形结构的复杂操作,减少了维护时间和状态转换数量.实验表明,基于树型结构的可扩展标记语言查询增量维护算法能够以有限转换路径为代价,有效地完成可扩展标记语言数据流持续查询执行器的动态维护,减少了增量维护时间和状态转换数量.4.学位论文孙冰基于自动机的XML路径查询处理技术研究2002该文提出了一种新的XML路径查询技术——自动机匹配查询技术.这一方法使用了两个主要的索引结构:路径模式树和路径实例树.路径实例树存储XML数据和数据之间的结构关系以及一些其它信息.路径模式树以树型结构组织XML数据中所有实例的路径模式,路径模式树结点与实例树结点之间有一对多的对应关系.在查询时,首先将输入的查询表达式转化成查询自动机,然后将自动机与路径模式树相匹配,在匹配成功的模式树结点上找到XML实例的入口点,在实例树上得到查询结果.围绕着这一方法,该文设计和定义了相应的数据模型;设计并实现了支持自动机匹配方法所需的索引结构和其它相关数据结构;而且设计并实现了新的利用键树来匹配自动机的算法,扩展了自动机的功能;同时提出了自动机匹配算法中路径表达式谓词问题的计算方法和优化方法;该文最后给出了自动机匹配算法与其它两种查询算法在查询性能上的比较并加以简要分析.5.学位论文柳娜统一资源管理系统中查询组件的设计与实现2006为了能有效地进行资源共享和交换，提高资源建设的效率和水平。本文提出了统一资源库的概念一一即建立一个统一的资源平台，通过资源类型注册机制，对各种不同标准类型的资源提供统一的存取、检索和管理。由于统一资源管理平台数据量大、实时操作频繁、数据类型多样化，因此本文采用了目前比较先进的XML(ExtensibleMarkupLanguage，可扩展标记语言)半结构化数据库模型来进行数据库的管理，对于其中的数据查询功能利用XML文档查询技术来实现。通过对国内外XML文档查询算法的分析发现，大多数算法的实现是把被查询文档全部载入内存之后再进行处理，因此要消耗大量内存，尤其是在XML文档很大以致无法全部载入内存的情况下，这些算法就无能为力了。针对这一问题，本文在统一资源管理平台查询组件中设计并实现了一种新的查询算法。该算法的设计思路是：首先根据XPath查询表达式，生成一个查询自动机，并将查询条件隐含在查询自动机的结构和状态中；然后通过SAX(SimpleAPIsforXML，XML简单应用程序接口)解析程序将XML文本数据流转化为SAX事件流，并将这些事件作为查询自动机的输入，来触发查询自动机的状态转换；查询自动机依据不同的输入事件，在各个状态之间进行转换，一旦确认某一部分文档完全匹配查询表达式，查询引擎程序就输出查询结果。文中详细地介绍了由查询表达式构造查询自动机的步骤；实现了一个基于流的XML文档查询系统的原型，它可以在对XML流的一次单向读取过程中处理XPath，输出查询结果。文中还对基于内存的XML查询算法和基于流的XML查询算法进行测试、比较，并对结果进行了分析。基于流的XML查询算法是为了满足一些数据密集型应用对数据查询处理的需求而引入的，这类应用处理的数据不宜用持久稳定的关系建模，而应采用数据流建模。这类应用的领域包括金融服务，网络监控，电信数据管理，生产制造，传感检测等。本论文的研究对这类实际应用将具有一定的理论意义和使用价值。6.会议论文吕建华.周巍.孙冰.王国仁.于戈XML查询中RPE索引技术研究2001本文针对正则路径达表达式的特点提出了一个基于自动机的正则路径表达式索引方法,它把正则路径表达式转换成自动机,利用其相似性准确而有效地索引正则路径表达式,从而提高正则路径表达式的查询处理效率.7.学位论文许翼XML树模式查询研究2008XML是可扩展标记语言的简称，为Web上半结构化文档和数据提供了通用格式。随着Internet的发展尤其是Web技术的广泛应用，越来越多的应用采用了XML技术作为信息表示和数据交换的标准，这使得通过数据库技术对XML数据进行存储、查询等操作变得越来越重要。由于XML文档可看作树型，对XML的查询可以看成是基于值谓词的子树Twig匹配，也就是从XML文档找到和给定查询条件相匹配的子树，因此能够高效找到子树匹配成为XML中的一个核心问题。本文在介绍了XML查询的研究现状和研究成果的基础上，针对TwigStack算法在多层嵌套的XML文档下性能不高的情况，提出了改进算法NestTwig，并证明行之有效。NestTwig算法和TwigStack算法都是基于分解—匹配—合并的步骤来进行查询匹配处理，容易产生大量无用的中间结果或者会对一些子模式树进行重复匹配。为了解决这个问题，本文引入自动机思想，对Twig查询自动机与路径模式树的匹配进行了讨论，提出了改进算法PatternMatch。对PatternMatch算法和NestTwig算法进行了实验对比证明基于自动机的方法在性能上具有较大优势。8.期刊论文方峻.刘长毅.徐诚枪械方案设计系统中的基于实例推理框架研究-兵工学报2003,24(1)本文提出了一种基于实例推理(CBR)的面向对象框架原型,阐述了其结构组成和实现形式,研究了其在构建枪械方案设计系统中的应用,同时建立了基于可扩展标记语言(XML)的实例表达形式和一套面向对象的实例推理模型,在此基础上开发了一套枪械自动机方案设计原型系统,并以一个设计实例对系统进行了验证.9.学位论文包小源压缩XML的索引与查询方法研究2005XML由于为其中所保存内容的每个语义单元引入一个标记而使整个文件的内容迅速膨胀，这种情况下，在对数量庞大的XML数据进行管理时，进行压缩就成为一种有效的基本解决方法。其实，XML作为一种数据交换标准，由于其频繁在网络上进行传输，为了节省宝贵的网络资源，压缩将是一种必然的选择。对压缩数据进行查询的基本方法是首先解压缩，然后再实施查询。这种方法在数据量小的情形下尚可，对于所管理数据量庞大的情形下(如IR中的海量数据管理、大规模企业的海量XML客户个性化数据等)，每次查询需要事先解压缩所带来的性能下降是无法承受的。于是，直接基于压缩数据进行索引、查询等就变得非常重要而且必要。这一点对压缩XML数据是同样适用的。但目前已有的压缩方法大多没有兼顾结构保持、解压缩效率、以及压缩比等三个方面的要求，不能支持直接基于压缩的查询；同时，基于压缩的XML索引、查询(包括静态、流两方面的查询)很少，而已有研究不能直接、或者根本不能应用于压缩数据的索引和查询。围绕上述问题，本文提出了XML结构保持压缩方法、基于压缩的XML索引方法、基于压缩XML静态数据以及压缩XML流的查询及分发方法。主要的创新性成果包括：1.提出了基于Byte-Huffman的XML结构保持压缩思想和方法目前已有的XML结构保持压缩方法基本上自成系统，无法有效与其他应用系统集成，且其实现复杂。还有很重要的一点，在网络环境下，对压缩和解压缩的速度要求是同等重要的，但目前的压缩方法(无论是非结构保持压缩或是结构保持压缩)因主要集中于实际应用中XML传输及存储效率的提高，从而对解压缩的效率不够重视。经过我们对现有的实验系统测试，其解压缩的速度一般都很慢。本文提出了一种支持查询的XML压缩方法：QueXComp(QuerableXMLCompression)。它以XByteHuff为基本压缩编码方法，通过保留以“＜”、“＞”，“/”，及“=”等定义的XML结构，以Word为基本压缩统计单位对元素的Tag及元素值实施压缩，可实现高效率的压缩和解压缩。为了能实现从压缩XML数据中任意位置开始的查询及解压缩，我们对ByteHuffman编码进行了改进，保留其MSB作为标志位以指示一个Word的开始，形成了XbyteHuff。同时，为了实现基于压缩的高效查询，我们提出了字典索引结构P-Tries，并提出了基于ByteHuffman树中附加Mark域信息以支持所提出的基于NFA(非有限自动机)的压缩XML内容查询。2.提出了基于压缩的XML结构索引S-Index、ArithRegion、XML内容索引P-Index索引作为一种经典的、被广泛证明有效的查询辅助方法及技术，当然在压缩的XML数据环境下，有深入研究的必要性。但目前所提出的很多索引结构大多基于XML源数据(非压缩)，不能直接应用于压缩XML数据，甚至对于某些压缩(如算术压缩)方法，这些索引结构根本不适用。尤其对于实际中频繁使用的查询Q=//element1/element2/…/elementm[textO=string]，现有索引结构不能对其进行高效处理。本文首先提出了适用于字典压缩的XML结构索引：S-Index。S-Index是一种基于后缀树(SuffixTree)的XML索引结构。S-Index的构造通过只对XML数据树遍历一次以及在S-Index中引入后缀链(Sufflink)的方法，从而达到较低的构造代价。S-Index中所有节点利用Hash表保存到其所有子节点的指针，可以证明，查询//element1/element2/…/elementm的处理代价仅为O(m)，优于其他索引结构。接下来，针对基于XML结构的算术压缩，提出了索引结构ArithRegion，该索引结构以B+树为基本结构，以压缩的左边界值为关键字，可实现对算术压缩XML结构的有效索引。最后，提出了压缩XML内容索引结构P-Index。P-Index以