基于下推自动机的XML数据流递归查询研究

针对具有子孙轴(//)和谓词([])结构特征的XPath对具有不同递归深度的XML数据流进行递归查询处理问题,提出了基于下推自动机技术的处理方法,通过将XPath各类置步转化成相对应的处理模块,由算法将各类处理模块组合起来,建立了自上而下的树状查询模型.由于查询过程中将会发生多重匹配,从而会产生大量的匹配模式,该模型通过有效的匹配策略和缓存操作,对匹配模式进行保存及检验,成功地实现XML数据流递归查询.实验结果表明,该算法在性能上要优于传统方法.     

M2:一种有效的XPath求值方法

XPath求值性能极大关系到XML应用程序的整体性能.提出的M2(Matrix Match)方法基于节点关系矩阵查询.根据XML区间编码构建关系矩阵,通过查询原语序列的执行实现XPath表达式求值.M2的导航式特点使得XPath的各种查询语义容易实现,包括反向轴操作和以谓词表达的分支查询.对应相同XML数据的关系矩阵可...     

使用DTD优化XML数据流上的XPath查询

如何在XML数据流上高效地执行XPath查询,是XML数据流管理的关键问题。DTD结构信息对提高XML查询效率有很大帮助,已有的大部分算法没有利用这一资源。提出了一种使用DTD进行XML数据流查询处理的方法,具有以下特征:利用树自动机表示XPath;通过XPath树自动机与DTD树匹配,预先标识不匹配查询结构的DTD节点;给出一种利用DTD的XML流索引方法DBXSI;执行查询时,根据流索引信息直接跳过某些与查询不匹配的节点及子树。实验结果表明:该方法可有效支持Xpath查询,效率优于传统算法。     

基于树自动机的XML过滤技术

为了提高XML数据流的查询匹配效率,基于XML过滤技术研究提出了一种基于树自动机的XML过滤技术XTAFilter.该技术利用hash表来存储谓词,并对多个查询表达式XPath通过共享路径构建树自动机,减少了匹配的时间,提高了查询匹配的效率,同时降低系统运行时的活动状态.搭建仿真平台对技术进行验证,仿真实验结果表明,XTAFilter 技术能有效地提高XML数据流的匹配效率,提高了系统的实用性.     

XML数据流上的有序XPath查询处理

XML数据流上的查询处理是最近研究工作的一个热点,如何高效地处理XML数据流上的XPath查询是其中的核心问题.之前的相关工作主要考虑了无序XPath查询处理的情况,而在股票信息监控、新闻信息订阅等很多的XML数据流应用中常常需要对有序XPath查询进行有效的支持.对于有序XPath查询的处理,之前的方法需要将查询进行分解,然后通过连接将分解后的子查询得到的中间结果合并.针对有序XPath查询自身的特点,提出了在查询树上引入顺序和位置标记,记录查询结点之间的顺序关系,并在此基础上提出了一种创新的XML数据流上的XPath查询处理算法OrderedXP.相比之前的工作,OrderedXP能够大量地减少缓存的中间结果数目,而且不需要分解原来的查询,避免了额外的连接操作.详细的实验数据验证了OrderedXP能够显著地提高有序XPath查询在XML数据流上的执行效率.     

Xtwig连接:基于流的对无根树查询模式的高效处理

为了提高对XML文档的查询能力,提出了一种Xtwig查询模式. Xtwig模式可以被表达成无根标签树,它在选择谓词中包含反向轴,可以从当前节点向后和向前查找指定的模式.现在已有很多处理Twig模式查询的经典算法,然而这些算法只能处理只包含前向轴的查询模式;许多重写规则也被提出来将带反向轴的XPath定位路径转化为等价的只包含前向轴的定位路径,但是转化后的定位路径在执行时是非常低效的.提出了一个高效算法XtwigStack来处理同时具有正向轴和反向轴的查询模式.实验结果表明,算法是有效的、高效的,它避免了大量无用中间结果,其执行效率不受反向轴个数影响.     

基于列表的可扩展标记语言流数据查询处理方法

针对半结构化可扩展标记语言(XML)流数据实时在线到达,顺序性一次访问及处理时效性高、缓存量小的需求,以及目前算法在大规模数据处理中查询表达式的能力有限、效率尚不能满足实际应用的现状,基于SAX解析,提出以列表及关系指针组合处理XPath查询的QXSList方法。首先定义数据模型,给出算法实现的整体框架,然后分别针对两个不同的XPath查询片段重点考虑了谓词判断条件和通配符的处理方法;该方法通过层次值计算判断节点的结构关系,利用关系指针链接多个候选节点列表,获取查询查询结果;最后分析给出优化算法,进一步减少缓存管理。通过实验对该方法与QStream++方法及MonetDB和SAXON查询引擎的运行时间和内存占比进行分析,得出与同类算法相比,随着数据量级的增加,效率提升在30%以上,且运行过程中内存占比接近于常量。     

XML数据流基于组着色的XPath查询模型

提出了一种新的XML数据流XPath查询模型GBRender,该模型通过组着色序列来直接处理元素,具有较高的处理效率与较强的适应性.     

一种XML数据库上谓词“Contain”的实现方法

路径表达式查询是XML数据查询处理的核心研究问题之一,研究者开展了大量的研究工作.但这些研究更多关注XML数据上路径表达式的匹配,忽略了谓词"包含".研究XML查询处理中谓词"包含"的查询处理方法.采用了两种方法,第一种是采用跳跃表的方法,在XML分枝模式匹配时动态地对结点数据进行读取和关键字匹配.第二种是为XML文档中的词语建立倒排索引,来实现关键字的匹配.并从分枝模式路径长度、查询关键的数量和"包含"谓词判断结点的类型,对两种方法进行了分析和比较.     

一种基于树状逻辑式的XML查询方法*

随着XML在各类数据表示中的广泛应用,XML文档的查询方法成为当前数据处理的一个重要问题。已有的研究如XPath和XQuery得到应用,但其查询表现存在一些缺点需要改进。从模板匹配的角度出发,基于谓词逻辑设计了树状逻辑表达式LXT。该表达式的特点是能以树状结构模板描述XML文档查询需求。在此基础上,进一步探讨了基于LXT表达式的XML文档查询方法,从数据的查询过滤、结果的组织构造与含义等方面描述了利用LXT的特点设计XML查询表现形式的基本思路。     

XTREAM: An efficient multi-query evaluation on streaming XML data

Recently, there has been growing interest in streaming XML data. Much of the work on streaming XML data has been focused on efficient filtering. Filtering systems deliver XML documents to interested users. The burden of extracting the XML fragments of interest from XML documents is placed on users. In this paper, we propose XTREAM which evaluates multiple queries in conjunction with the read-once nature of streaming data. In contrast to the previous work, XTREAM supports a wide class of XPath queries including tree shaped expressions, order based predicates, and nested predicates. In addition, to improve the efficiency and scalability of XTREAM, we devise an optimization technique called Query Compaction. Experimental results with real-life and synthetic XML data demonstrate the efficiency and scalability of XTREAM.     

一种基于结构索引的XML模式匹配方法

XML文档采用了树型的数据模型,对其查询通常是用带有选择谓词的模式树在XML数据中进行匹配.因此,找出XML文档中所有符合模式树结构的元素集,是XML查询处理的核心操作.本文提出了结构索引JoinGuide,并在此基础上提出了一种新的XML模式匹配方法.它使用JoinGuide来对模式树进行预匹配,这样在XML文档上查询时可以利用索引上的匹配结果来忽略部分连接谓词和不必要的候选XML元素序列.本文还提出了三种具体算法来利用索引匹配结果进行进一步的查询.实验结果表明本文中的模式树匹配方法优于以往的匹配方法,并且索引所需的空间很小.     

Consistent collective evaluation of multiple continuous queries for filtering heterogeneous data streams

Query processing for a data stream should also be continuous and rapid. This article proposes a novel approach for consistent collective evaluation of multiple continuous queries for filtering two different types of data streams: a relational stream and an XML stream. The proposed approach commonly provides region-based selection constructs: an attribute selection construct for relational queries and a path selection construct for XPath queries. Both collectively evaluate the selection predicates of the same attribute (path), based on the precomputed matching results of the queries in each of the disjoint regions divided by the selection predicates. The performance experiments show that the proposed approach is practically more efficient and stable than other approaches at run-time.     

基于X-RESTORE查询XML视图

基于转换 XML文档到关系数据库中进行存储与查询的策略 ,研究了 XML视图查询的有效计算问题 .提出了XML 视图查询的合成重写技术 ,它能够消除视图查询中所有在视图结构上的路径导航操作 ,并将视图查询中所有在原文档结构上的路径导航操作以及所有谓词操作下推到视图定义中去 ,与视图定义中的路径导航操作相结合 ,形成统一的在原文档结构上的路径导航操作 .视图合成重写不仅避免了对视图中不出现在最后结果中的中间 XML 片段的构造 ,而且允许将查询中的所有内存密集型或数据密集型操作尽量下推到关系引擎中去执行 ,从而提高 XQuery查询的执行性能     

图结构XML文档上子图查询的高效处理算法

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.     

Locating XML Documents in a Peer-to-Peer Network Using Distributed Hash Tables

One of the key challenges in a peer-to-peer (P2P) network is to efficiently locate relevant data sources across a large number of participating peers. With the increasing popularity of the extensible markup language (XML) as a standard for information interchange on the Internet, XML is commonly used as an underlying data model for P2P applications to deal with the heterogeneity of data and enhance the expressiveness of queries. In this paper, we address the problem of efficiently locating relevant XML documents in a P2P network, where a user poses queries in a language such as XPath. We have developed a new system called psiX that runs on top of an existing distributed hashing framework. Under the psiX system, each XML document is mapped into an algebraic signature that captures the structural summary of the document. An XML query pattern is also mapped into a signature. The query's signature is used to locate relevant document signatures. Our signature scheme supports holistic processing of query patterns without breaking them into multiple path queries and processing them individually. The participating peers in the network collectively maintain a collection of distributed hierarchical indexes for the document signatures. Value indexes are built to handle numeric and textual values in XML documents. These indexes are used to process queries with value predicates. Our experimental study on PlanetLab demonstrates that psiX provides an efficient location service in a P2P network for a wide variety of XML documents.     

Fast in‐memory XPath search using compressed indexes

Extensible Markup Language (XML) documents consist of text data plus structured data (markup). XPath allows to query both text and structure. Evaluating such hybrid queries is challenging. We present a system for in‐memory evaluation of XPath search queries, that is, queries with text and structure predicates, yet without advanced features such as backward axes, arithmetics, and joins. We show that for this query fragment, which contains Forward Core XPath, our system, dubbed Succinct XML Self‐Index (‘SXSI’), outperforms existing systems by 1–3 orders of magnitude. SXSI is based on state‐of‐the‐art indexes for text and structure data. It combines two novelties. On one hand, it represents the XML data in a compact indexed form, which allows it to handle larger collections in main memory while supporting powerful search and navigation operations over the text and the structure. On the other hand, it features an execution engine that uses tree automata and cleverly chooses evaluation orders that leverage the speeds of the respective indexes. SXSI is modular and allows seamless replacement of its indexes. This is demonstrated through experiments with (1) a text index specialized for search of bio sequences, and (2) a word‐based text index specialized for natural language search. Copyright © 2013 John Wiley & Sons, Ltd.     

XQAD:一种XML查询的算法

目前已经提出的XML查询的方法大都是直接进行实例一级的查询,如XML文档树遍历及嵌套连接等。这些方法忽视了对XML格式信息的利用,当XML文档较大时,性能就会有明显下降。论文给出了一种直接利用DTD的格式信息对XML进行查询的算法XQAD。根据DTD和路径表达式的特点来减少对实例的访问次数,从而提高性能。XQAD还支持多谓词查询,包括结构谓词和值谓词。最后,用实验的方法同其它算法作比较,并对试验结果进行了分析。     

基于DOM的XML数据库的索引技术研究

XML作为一种数据交换的国际标准，已经贯穿于Internet应用的各个领域之中，如何快速准确地存储和查询XML数据的数据库技术是一个重要的研究课题。XML索引技术对XML数据库查询处理起着至关重要的作用，提出了基于DOM的XML数据库的索引技术(路径连接索引、值索引和引用索引)，解决了传统的基于树的遍历的XML数据查询方法性能上的不足，并着重对处理含有谓词和引用关系等较复杂的查询路径的不同处理方法进行了对比和分析，还给出了索引空间利用率、查询性能和索引维护代价3个方面的标准测试结果，表明新的索引技术可以有效地提高查询处理效率。