Efficient evaluation of generalized tree-pattern queries on XML streams

被引:0
|
作者
Xiaoying Wu
Dimitri Theodoratos
Calisto Zuzarte
机构
[1] New Jersey Institute of Technology,
[2] IBM Canada Ltd.,undefined
来源
The VLDB Journal | 2010年 / 19卷
关键词
XML; XPath evaluation; XML streams;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:661 / 686
页数:25
相关论文
共 50 条
  • [31] MKStream: An Efficient Algorithm for Processing Multiple Keyword Queries over XML Streams
    Barros, Evandrino G.
    Laender, Alberto H. F.
    Moro, Mirella M.
    da Silva, Altigran S.
    CONCEPTUAL MODELING, 2014, 8824 : 100 - 107
  • [32] Efficient Algorithms for Skyline Top-K Keyword Queries on XML Streams
    Li, Lingli
    Wang, Hongzhi
    Li, Jianzhong
    Gao, Hong
    DATABASE SYSTEMS FOR ADVANCED APPLICATIONS, PROCEEDINGS, 2009, 5463 : 283 - 287
  • [33] Efficient evaluation of nearest common ancestor in XML twig queries using tree-unaware RDBMS
    Widjanarko, Klarinda G.
    Leonardi, Erwin
    Bhowmick, Sourav S.
    DATABASE AND EXPERT SYSTEMS APPLICATIONS, PROCEEDINGS, 2007, 4653 : 617 - +
  • [34] Evaluating XPath queries on XML data streams
    Boettcher, Stefan
    Steinmetz, Rita
    DATA MANAGEMENT: DATA, DATA EVERYWHERE, PROCEEDINGS, 2007, 4587 : 101 - +
  • [35] Queries on XmL streams with bounded delay and concurrency
    Gauwin, Olivier
    Niehren, Joachim
    Tison, Sophie
    INFORMATION AND COMPUTATION, 2011, 209 (03) : 409 - 442
  • [36] Processing XML queries with tree signatures
    Zezula, P
    Amato, G
    Rabitti, F
    INTELLIGENT SEARCH ON XML DATA: APPLICATIONS, LANGUAGES, MODELS IMPLEMENTATIONS AND BENCHMARKS, 2003, 2818 : 247 - 258
  • [37] Efficient algorithms for descendant-only tree pattern queries
    Goetz, Michaela
    Koch, Christoph
    Martens, Wim
    INFORMATION SYSTEMS, 2009, 34 (07) : 602 - 623
  • [38] An efficient index structure for XML based on generalized suffix tree
    Liang Zuopeng
    Hu Kongfa
    Ye Ning
    Dong Yisheng
    INFORMATION SYSTEMS, 2007, 32 (02) : 283 - 294
  • [39] Lineage Encoding: An Efficient Wireless XML Streaming Supporting Twig Pattern Queries
    Park, Jun Pyo
    Park, Chang-Sup
    Chung, Yon Dohn
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2013, 25 (07) : 1559 - 1573
  • [40] Buffer management of the results of queries over XML streams
    School of Computer Science, Fudan University, Shanghai 200433, China
    Ruan Jian Xue Bao, 2008, 8 (2080-2088):