XML Query Processing and Query Languges: A Survey
---
paper_title: A Query Processing Approach for XML Database Systems

paper_content:

Besides the storage engine, the query processor of a database system is the most critical component when it comes to performance and scalability. Research on query processing for relational database systems developed an approach which we believe should also be adopted for the newly proposed XML database systems. It includes a syntactic and semantic analyzation phase, the mapping onto an internal query representation, algebraic and cost-based optimization, and finally the execution on a record-oriented interface. Each step hides its own challenges and will therefore be discussed throughout this paper. Our contribution can be understood as a roadmap that reveals a desirable set of functionalities for an XML query processor.
---
paper_title: The Niagara Internet Query System

paper_content:

Many projections envision a future in which the Internet is populated with a vast number of Web-accessible XML files—a “World-Wide Database”. Recently, there has been a great deal of research into XML query languages to enable the execution of database-style queries over these XML files. However, merely being an XML query-processing engine does not render a system suitable for querying the Internet. A truly useful system must provide mechanisms to (a) find the XML files that are relevant to a given query, and (b) deal with remote data sources that either provide unpredictable data access and transfer rates, or are infinite streams, or both. The Niagara Internet Query System was designed from the bottom-up to provide these mechanisms. It finds relevant XML documents by using a novel collaboration between the Niagara XML-QL query processor and the Niagara “text-in-context” XML search engine. To handle infinite streams and data sources with unpredictable rates, it supports a “get partial” operation on blocking operators in order to produce partial query results, and inserts synchronization packets at critical points in the operator tree to guarantee the consistency of (partial) results. The Niagara Internet Query System is public domain software that can be found at http://www-db.cs.wisc.edu/niagara/. Category: Research.
---
paper_title: Navigation- vs. index-based XML multi-query processing

paper_content:

XML path queries form the basis of complex filtering of XML data. Most current XML path query processing techniques can be divided in two groups. Navigation-based algorithms compute results by analyzing an input document one tag at a time. In contrast, index-based algorithms take advantage of precomputed numbering schemes over the input XML document. We introduce a new index-based technique, index-filter, to answer multiple XML path queries. Index-filter uses indexes built over the document tags to avoid processing large portions of the input document that are guaranteed not to be part of any match. We analyze index-filter and compare it against Y-filter, a state-of-the-art navigation-based technique. We show that both techniques have their advantages, and we discuss the scenarios under which each technique is superior to the other one. In particular, we show that while most XML path query processing techniques work off SAX events, in some cases it pays off to preprocess the input document, augmenting it with auxiliary information that can be used to evaluate the queries faster. We present experimental results over real and synthetic XML documents that validate our claims.
---
paper_title: Efficient Recursive XML Query Processing Using Relational Database Systems

paper_content:

Recursive queries are quite important in the context of XML databases. In addition, several recent papers have investigated a relational approach to store XML data and there is growing evidence that schema-conscious approaches are a better option than schema-oblivious techniques as far as query performance is concerned. However, the issue of recursive XML queries for such approaches has not been dealt with satisfactorily. In this paper we argue that it is possible to design a schema-oblivious approach that outperforms schema-conscious approaches for certain types of recursive queries. To that end, we propose a novel schema-oblivious approach, called SUCXENT++ (Schema Unconcious XML Enabled System), that outperforms existing schema-oblivious approaches such as XParent by up to 15 times and schema-conscious approaches (Shared-Inlining) by up to eight times for recursive query execution. Our approach has up to two times smaller storage requirements compared to existing schema-oblivious approaches and 10% less than schema-conscious techniques. In addition SUCXENT++ performs marginally better than Shared-Inlining and is 5.7-47 times faster than XParent as far as insertion time is concerned.
---
paper_title: MonetDB/XQuery: a fast XQuery processor powered by a relational engine

paper_content:

Relational XQuery systems try to re-use mature relational data management infrastructures to create fast and scalable XML database technology. This paper describes the main features, key contributions, and lessons learned while implementing such a system. Its architecture consists of (i) a range-based encoding of XML documents into relational tables, (ii) a compilation technique that translates XQuery into a basic relational algebra, (iii) a restricted (order) property-aware peephole relational query optimization strategy, and (iv) a mapping from XML update statements into relational updates. Thus, this system implements all essential XML database functionalities (rather than a single feature) such that we can learn from the full consequences of our architectural decisions. While implementing this system, we had to extend the state-of-the-art with a number of new technical contributions, such as loop-lifted staircase join and efficient relational query evaluation strategies for XQuery theta-joins with existential semantics. These contributions as well as the architectural lessons learned are also deemed valuable for other relational back-end engines. The performance and scalability of the resulting system is evaluated on the XMark benchmark up to data sizes of 11GB. The performance section also provides an extensive benchmark comparison of all major XMark results published previously, which confirm that the goal of purely relational XQuery processing, namely speed and scalability, was met.
---
paper_title: The BEA/XQRL Streaming XQuery Processor

paper_content:

In this paper, we describe the design, implementation, and performance characteristics of a complete, industrial-strength XQuery engine, the BEA streaming XQuery processor. The engine was designed to provide very high performance for message processing applications, i.e., for transforming XML data streams, and it is a central component of the 8.1 release of BEA's WebLogic Integration (WLI) product. This XQuery engine is fully compliant with the August 2002 draft of the W3C XML Query Language specification. A goal of this paper is to describe how an efficient, fully compliant XQuery engine can be built from a few relatively simple components and well-understood technologies.
---
paper_title: NaXDB - Realizing Pipelined XQuery Processing in a Native XML Database System

paper_content:

Supporting queries and modifications on XML documents is a challenging task, and several related approaches exist. When implementing query and modification languages efficiently, the actual persistent storage of the XML data is of particular importance. Generally speaking, the structure of XML data significantly differs from the well-known relational data-model. This paper presents the prototypical implementation of NaXDB, a native XML database management system (DBMS). A native approach means the XML data is stored as a hierarchical tree of linked objects. NaXDB is implemented as a MaxDB by MySQL kernel module and thus inherits several DBMS functionality. Furthermore, NaXDB uses objectoriented extensions of of MaxDB by MySQL to store the tree of linked objects. NaXDB implements a large subset of the query language specification XQuery 1.0 as well as XUpdate for modification. The design and architecture of the prototypical implementation is presented, and concepts for query processing within the database server are discussed.
---
paper_title: Holistic twig joins: optimal XML pattern matching

paper_content:

XML employs a tree-structured data model, and, naturally, XML queries specify patterns of selection predicates on multiple elements related by a tree structure. Finding all occurrences of such a twig pattern in an XML database is a core operation for XML query processing. Prior work has typically decomposed the twig pattern into binary structural (parent-child and ancestor-descendant) relationships, and twig matching is achieved by: (i) using structural join algorithms to match the binary relationships against the XML database, and (ii) stitching together these basic matches. A limitation of this approach for matching twig patterns is that intermediate result sizes can get large, even when the input and output sizes are more manageable.In this paper, we propose a novel holistic twig join algorithm, TwigStack, for matching an XML query twig pattern. Our technique uses a chain of linked stacks to compactly represent partial results to root-to-leaf query paths, which are then composed to obtain matches for the twig pattern. When the twig pattern uses only ancestor-descendant relationships between elements, TwigStack is I/O and CPU optimal among all sequential algorithms that read the entire input: it is linear in the sum of sizes of the input lists and the final result list, but independent of the sizes of intermediate results. We then show how to use (a modification of) B-trees, along with TwigStack, to match query twig patterns in sub-linear time. Finally, we complement our analysis with experimental results on a range of real and synthetic data, and query twig patterns.
---
paper_title: Structural joins: a primitive for efficient XML query pattern matching

paper_content:

XML queries typically specify patterns of selection predicates on multiple elements that have some specified tree structured relationships. The primitive tree structured relationships are parent-child and ancestor-descendant, and finding all occurrences of these relationships in an XML database is a core operation for XML query processing. We develop two families of structural join algorithms for this task: tree-merge and stack-tree. The tree-merge algorithms are a natural extension of traditional merge joins and the multi-predicate merge joins, while the stack-tree algorithms have no counterpart in traditional relational join processing. We present experimental results on a range of data and queries using the TIMBER native XML query engine built on top of SHORE. We show that while, in some cases, tree-merge algorithms can have performance comparable to stack-tree algorithms, in many cases they are considerably worse. This behavior is explained by analytical results that demonstrate that, on sorted inputs, the stack-tree algorithms have worst-case I/O and CPU complexities linear in the sum of the sizes of inputs and output, while the tree-merge algorithms do not have the same guarantee.
---
paper_title: An Efficient XPath Query Processor for XML Streams

paper_content:

Streaming XPath evaluation algorithms must record a potentially exponential number of pattern matches when both predicates and descendant axes are present in queries, and the XML data is recursive. In this paper, we use a compact data structure to encode these pattern matches rather than storing them explicitly. We then propose a polynomial time streaming algorithm to evaluate XPath queries by probing the data structure in a lazy fashion. Extensive experiments show that our approach not only has a good theoretical complexity bound but is also efficient in practice.
---
paper_title: Mixed Mode XML Query Processing

paper_content:

Querying XML documents typically involves both tree-based navigation and pattern matching similar to that used in structured information retrieval domains. In this paper, we show that for good performance, a native XML query processing system should support query plans that mix these two processing paradigms. We describe our prototype native XML system, and report on experiments demonstrating that even for simple queries, there are a number of options for how to combine tree-based navigation and structural joins based on information retrieval-style inverted lists, and that these options can have widely varying performance. We present ways of transparently using both techniques in a single system, and provide a cost model for identifying efficient combinations of the techniques. Our preliminary experimental results prove the viability of our approach.
---

Title: XML Query Processing and Query Languages: A Survey

Section 1: INTRODUCTION
Description 1: Introduce the functionalities of XML, its structure, and the importance of XML query languages and processors.

Section 2: XML QUERY LANGUAGES
Description 2: Review the evolution of XML query languages, with a focus on XQuery and other historical proposals, detailing their important characteristics and criteria.

Section 3: APPROACHES FOR XML QUERY PROCESSING
Description 3: Discuss various approaches for XML query processing, including both high-level abstractions and procedural evaluations.

Section 4: Query Processing on Flat File Scheme
Description 4: Analyze the flat file processing approach, explain different processing techniques such as yfilter, index-filter, and pathstack, and outline their performance considerations.

Section 5: Processing on Relational Structure
Description 5: Explain the relational structure approach for storing and querying XML data, detailing different relational storage schemes and their implementation.

Section 6: Query Processing on Native Storage Scheme
Description 6: Describe the native storage scheme approach, including labeling schemes for XML elements, stack-based algorithms, and holistic twig joins for efficient query processing.

Section 7: TOWARD FUTURE XML DATABASE MANAGEMENT SYSTEMS
Description 7: Discuss the future directions for XML database management systems, including trends, potential research areas, and application interoperability.

Section 8: CONCLUSION
Description 8: Summarize the current state of XML query processing, highlight the current trends and challenges, and suggest areas for future research.