Worst-case optimal algorithm for XPath evaluation over XML streams

We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D; i.e., determine the set Q(D) of document elements selected by Q. We mainly consider Conjunctive XPath queries that involve only the child and descendant axes. Previously known in-memory algorithms for this problem use O(|D|) space and O(|Q||D|) time. Several previously known algorithms for the streaming version use Ω(dn) space and Ω(dn|D|) time in the worst case; d denotes the depth of D, and n denotes the number of location steps in Q. Their exponential space requirement could well exceed the O(|D|) space used by the in-memory algorithms. We present an efficient algorithm that uses O(d|Q|+nc) space and O((|Q|+dn)|D|) time in the worst case; c denotes the maximum number of elements of D that can be candidates for output, at any one instant. For some worst case Q and D, the memory space used by our algorithm matches our lower bound proved in a different paper; so, our algorithm uses optimal memory space in the worst case.     

Memory lower bounds for XPath evaluation over XML streams

We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D. We consider two versions of the problem: 1) Filtering Problem: Determine if there is a match for Q in D. 2) Node Selection Problem: Determine the set Q(D) of document nodes selected by Q. We consider Conjunctive XPath (CXPath) queries that involve only the child and descendant axes. Let d denote the depth of D, and n denote the number of location steps in Q. Bar-Yossef et al. (2007, 2005) [6] and [7] presented lower bounds on the memory space required by any algorithm to solve these two problems. Their lower bounds apply to each query in a large subset of XPath, and are obtained (mostly) using nonrecursive(Q,D). In this paper, we present larger lower bounds for a different class of queries (namely, CXPath queries with independent predicates), on recursive(Q,D). One of our results is an Ω(n⋅maxcands(Q,D)) lower bound for the node selection problem, for a worst-case Q; maxcands(Q,D) is the maximum number of nodes of D that can be candidates for output, at any one instant. So, there is no algorithm for the node selection problem that uses O(f(d,|Q|)+maxcands(Q,D)) space, for any function f. This shows that some previously published algorithms are incorrect.     

Selectivity-sensitive shared evaluation of multiple continuous XPath queries over XML streams

One of the primary issues confronting XML message brokers is the difficulty associated with processing a large set of continuous XPath queries over incoming XML streams. This paper proposes a novel system designed to present an effective solution to this problem. The proposed system transforms multiple XPath queries before their run-time into a new data structure, called an XP-table, by sharing their common constraints. An XP-table is matched with a stream relation (SR) transformed from a target XML stream by a SAX parser. This arrangement is intended to minimize the run-time workload of continuous query processing. In addition, an early-query-termination strategy is proposed as an improved alternative to the basic approach. It optimizes query processing by arranging the evaluation sequence of the member-lists (m-lists) of an XP-table adaptively and offers increased efficiency, especially in cases of low selectivity. System performance is estimated and verified through a variety of experiments, including comparisons with previous approaches such as YFilter and LazyDFA. The proposed system is practically linear-scalable and stable for evaluating a set of XPath queries in a continuous and timely fashion.     

Schema-aware XPath filtering on XML document streams

The XML stream filtering is gaining widespread attention from the research community in recent years. There have been many efforts to improve the performance of the XML filtering system by utilizing XML schema information. In this paper, we design and implement an XML stream filtering system, SFilter, which uses DTD or XML schema information for improving the performance. We propose the simplification and two kinds of optimization, one is static and the other is dynamic optimization. The Simplification and static optimization transform the XPath queries to make automata as an index structure for the filtering. The dynamic optimization are done in runtime at the filtering time. We developed five kinds of static optimization and two kinds of dynamic optimization. We present the novel filtering algorithm for the resulting transformed XPath queries and runtime optimizing. The experimental result shows that our system filters the XML streams efficiently.     

Indexing XML documents for XPath query processing in external memory

Existing encoding schemes and index structures proposed for XML query processing primarily target the containment relationship, specifically the parent–child and ancestor–descendant relationship. The presence of preceding-sibling and following-sibling location steps in the XPath specification, which is the de facto query language for XML, makes the horizontal navigation, besides the vertical navigation, among nodes of XML documents a necessity for efficient evaluation of XML queries. Our work enhances the existing range-based and prefix-based encoding schemes such that all structural relationships between XML nodes can be determined from their codes alone. Furthermore, an external-memory index structure based on the traditional B+-tree, XL+-tree(XML Location+-tree), is introduced to index element sets such that all defined location steps in the XPath language, vertical and horizontal, top-down and bottom-up, can be processed efficiently. The XL+-trees under the range or prefix encoding scheme actually share the same structure; but various search operations upon them may be slightly different as a result of the richer information provided by the prefix encoding scheme. Finally, experiments are conducted to validate the efficiency of the XL+-tree approach. We compare the query performance of XL+-tree with that of R-tree, which is capable of handling comprehensive XPath location steps and has been empirically shown to outperform other indexing approaches.     

Indexing XML documents for XPath query processing in external memory

Existing encoding schemes and index structures proposed for XML query processing primarily target the containment relationship, specifically the parent–child and ancestor–descendant relationship. The presence of preceding-sibling and following-sibling location steps in the XPath specification, which is the de facto query language for XML, makes the horizontal navigation, besides the vertical navigation, among nodes of XML documents a necessity for efficient evaluation of XML queries. Our work enhances the existing range-based and prefix-based encoding schemes such that all structural relationships between XML nodes can be determined from their codes alone. Furthermore, an external-memory index structure based on the traditional B+-tree, XL+-tree(XML Location+-tree), is introduced to index element sets such that all defined location steps in the XPath language, vertical and horizontal, top-down and bottom-up, can be processed efficiently. The XL+-trees under the range or prefix encoding scheme actually share the same structure; but various search operations upon them may be slightly different as a result of the richer information provided by the prefix encoding scheme. Finally, experiments are conducted to validate the efficiency of the XL+-tree approach. We compare the query performance of XL+-tree with that of R-tree, which is capable of handling comprehensive XPath location steps and has been empirically shown to outperform other indexing approaches.     

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

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

基于LazyDFA的XPath在XML数据流上查询优化算法

针对XML数据流上XPath查询处理及查询优化问题,给出了一种基于lazyDFA技术的解决方案,并提出了优化算法。共享NFA状态表,通过将NFA中的状态分成共享和独享两个状态集来降低lazyDFA的内存使用量;建立状态转移表优化算法通过在lazyDFA状态结构中增加一个状态转移表,来提高lazyDFA的查询速度。实验结果表明,提出的方法能够在执行效率和空间代价方面优于传统算法。     

基于树自动机的XPath在XML数据流上的高效执行

如何在XML数据流上高效地执行大量的XPath查询成为数据流应用中一个迫切需要解决的关键问题.目前提出的算法或者不能完全支持XPath的常规特性,或者在算法的执行效率和空间代价上不能满足数据流应用的要求.提出了基于树自动机的XEBT机来解决这个问题.与传统方法相比,XEBT机具备如下特征:首先,XEBT机基于表达能力丰富的树自动机,无须附加中间状态,或保存中间结果,就能处理支持{[]}操作符的XPath;其次,XEBT机支持多种优化策略,包括基于DTD的XPath查询自动机的构造;在空间代价有限增加的情况下采用局部确定化减少并发执行的状态;采用自上而下和自下而上相结合的查询处理策略.实验结果表明,提出的方法能够支持复杂的XPath查询,在执行效率和空间代价方面优于传统算法.     

基于下推转换机的XML流数据处理方法

XML流数据在互联网领域有着广阔的应用,海量流数据的高性能处理与查询需求的多样性给对XML流数据的查询处理技术提出了更高的要求,针对XML流数据上的XPath查询,以下推转换机（Pushdown Transducer）为基础,提出一种新的查询处理方法。该方法支持包含PC轴、AD轴同时包含多重存在谓词、值谓词和嵌套谓词的XPath查询,覆盖XPath查询的核心部分。该方法能够满足用户复杂的查询需求,同时具有较高的性能。     

Efficient evaluation of generalized tree-pattern queries on XML streams

The streaming evaluation is a popular way of evaluating queries on XML documents. Besides its many advantages, it is also the only option for a number of important XML applications. Unfortunately, existing algorithms focus almost exclusively on tree-pattern queries (TPQs). Requirements for flexible querying of XML data have motivated recently the introduction of query languages that are more general and flexible than TPQs. These languages are not supported by existing algorithms. In this paper, we consider a partial tree-pattern query (PTPQ) language which generalizes and strictly contains TPQs. PTPQs can express a fragment of XPath which comprises reverse axes and the node identity equality (is) operator, in addition to forward axes, wildcards and predicates. They constitute an important subclass of XPath, which is very useful in practice. Unfortunately, previous streaming algorithms for TPQs cannot be applied to PTPQs. PTPQs can be represented as dags enhanced with constraints. We explore this representation to design an original polynomial time streaming algorithm for PTPQs. Our algorithm aggressively filters incoming data that is irrelevant to the query and wisely avoids processing redundant query matches (i.e., matches of the query dag that do not contribute to new solutions). Our algorithm is the first one to support the streaming evaluation of such a broad fragment of XPath. We provide an analysis of it, and conduct an extensive experimental evaluation of its performance and scalability. Compared to the only known streaming algorithm that supports TPQs extended with reverse axes, our algorithm performs better by orders of magnitude while consuming a much smaller fraction of memory space. Current streaming applications have stringent requirements on query response time and memory consumption because of the large (possibly unbounded) size of data they handle. In order to keep memory usage and CPU consumption low for the PTPQ streaming evaluation, we design another streaming algorithm called Eager PSX for PTPQs. Its key feature is that it applies an eager evaluation strategy to quickly determine when node matches should be returned as solutions to the user and also to proactively detect redundant matches. We theoretically analyze Eager PSX, and experimentally test its time and space performance and scalability. We compare it with PSX. Our results show that Eager PSX not only achieves better space performance without compromising time performance, but it also greatly improves query response time for both simple and complex queries, in many cases, by orders of magnitude.     

Query evaluation over probabilistic XML

Query evaluation over probabilistic XML is explored. The queries are twig patterns with projection, and the data is represented in terms of three models of probabilistic XML (that extend existing ones in the literature). The first model makes an assumption of independence among the probabilistic junctions, whereas the second model can encode probabilistic dependencies. The third model combines the first two and, hence, is the most general. An efficient algorithm (under data complexity) is given for query evaluation in the first model. In addition, various optimizations are proposed, and their effectiveness is shown both analytically and experimentally. For the other two models, it is shown that every query is either intractable or trivial. Nonetheless, efficient (additive and multiplicative) approximation algorithms are given for these two models. Finally, Boolean queries are enriched by allowing disjunctions and negations of branches. The above algorithm for the first model is extended to handle these queries. For the other two models, there is an efficient additive approximation, and a multiplicative one also exists if there is no negation; in addition, it is shown that if the query is non-monotonic, then no efficient multiplicative approximation exists unless NP = RP.     

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

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

Efficient evaluation of query rewriting plan over materialized XML view

The query rewriting plan generation over XML views has received wide attention recently. However, little work has been done on efficient evaluation of the query rewriting plans, which is not trivial since the plan may contain an exponential size of sub-plans. This paper investigates the reason for the potentially exponential number of sub-plans, and then proposes a new space-efficient form called ABCPlan (Plan with Automata Based Combinations) to equivalently represent the original query rewriting plan. ABCPlan contains a set of buckets containing suffix paths in the query tree and an automata to indicate the combination of the suffix paths from different buckets as valid query rewriting sub-plans. We also design an evaluation method called ABCScan, which constructs a unified evaluation tree for the ABCPlan and handles the evaluation tree in one scan of the XML view. In the evaluation, we introduce node existence automata to encode the structure of the sub-tree and convert the satisfaction of the ABCPlan into the intersection problem of deterministic finite automata. The experiments show that ABCPlan based method outperforms existing methods significantly in terms of scalability and efficiency.     

A methodology for coupling fragments of XPath with structural indexes for XML documents

We introduce a new methodology for coupling language-induced partitions and index  -induced partitions on XML documents that is aimed for the benefit of efficient evaluation of XPath queries. In particular, we identify XPath fragments which are ideally coupled with the newly introduced P(k)$P(k)$-partition which has its definition grounded in the well-known A(k)$A(k)$ structural index and its associated partition. We then utilize these couplings to investigate fundamental questions about the use of structural indexes in XPath query evaluation.     

A novel hash-based approach for mining frequent itemsets over data streams requiring less memory space

In recent times, data are generated as a form of continuous data streams in many applications. Since handling data streams is necessary and discovering knowledge behind data streams can often yield substantial benefits, mining over data streams has become one of the most important issues. Many approaches for mining frequent itemsets over data streams have been proposed. These approaches often consist of two procedures including continuously maintaining synopses for data streams and finding frequent itemsets from the synopses. However, most of the approaches assume that the synopses of data streams can be saved in memory and ignore the fact that the information of the non-frequent itemsets kept in the synopses may cause memory utilization to be significantly degraded. In this paper, we consider compressing the information of all the itemsets into a structure with a fixed size using a hash-based technique. This hash-based approach skillfully summarizes the information of the whole data stream by using a hash table, provides a novel technique to estimate the support counts of the non-frequent itemsets, and keeps only the frequent itemsets for speeding up the mining process. Therefore, the goal of optimizing memory space utilization can be achieved. The correctness guarantee, error analysis, and parameter setting of this approach are presented and a series of experiments is performed to show the effectiveness and the efficiency of this approach.     

On the improvement of active XML (AXML) representation and query evaluation

Active XML (AXML) as intensional data aims to exploit potential computing powers of XML, Web services and P2P architecture. It is considered a powerful extension of XML to deal with dynamic XML data from autonomous and heterogeneous data sources on a very large scale via Web services. However, AXML is still at an immature stage and various issues need to be investigated before it can be accepted widely. This paper will focus on two issues facing the current AXML system, namely the representation and the query process. We propose superior representation and improved query evaluation for AXML. For justification purposes, we compare our proposed algorithms with the existing algorithms.     

Efficient memory representation of XML document trees

Implementations that load XML documents and give access to them via, e.g., the DOM, suffer from huge memory demands: the space needed to load an XML document is usually many times larger than the size of the document. A considerable amount of memory is needed to store the tree structure of the XML document. In this paper, a technique is presented that allows to represent the tree structure of an XML document in an efficient way. The representation exploits the high regularity in XML documents by compressing their tree structure; the latter means to detect and remove repetitions of tree patterns. Formally, context-free tree grammars that generate only a single tree are used for tree compression. The functionality of basic tree operations, like traversal along edges, is preserved under this compressed representation. This allows to directly execute queries (and in particular, bulk operations) without prior decompression. The complexity of certain computational problems like validation against XML types or testing equality is investigated for compressed input trees.     

A gossip-based approach for Internet-scale cardinality estimation of XPath queries over distributed semistructured data

In this paper, we address the problem of cardinality estimation of XPath queries over XML data stored in a distributed, Internet-scale environment such as a large-scale, data sharing system designed to foster innovations in biomedical and health informatics. The cardinality estimate of XPath expressions is useful in XQuery optimization, designing IR-style relevance ranking schemes, and statistical hypothesis testing. We present a novel gossip algorithm called XGossip, which given an XPath query estimates the number of XML documents in the network that contain a match for the query. XGossip is designed to be scalable, decentralized, and robust to failures—properties that are desirable in a large-scale distributed system. XGossip employs a novel divide-and-conquer strategy for load balancing and reducing the bandwidth consumption. We conduct theoretical analysis of XGossip in terms of accuracy of cardinality estimation, message complexity, and bandwidth consumption. We present a comprehensive performance evaluation of XGossip on Amazon EC2 using a heterogeneous collection of XML documents.