Matching of Twig Pattern with AND/OR Predicates over XML Streams

Matching of Twig Pattern with AND/OR Predicates over XML Streams

Weidong Yang (Fudan University, China) and Hao Zhu (Fudan University, China)
DOI: 10.4018/978-1-4666-1975-3.ch005
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Chapter 5 presents a novel approach for processing complex twig pattern with OR-predicates and AND-predicates over XML document streams which a twig pattern is represented as a query tree. Its OR-predicates and AND-predicates are represented as a separate abstract syntax tree associated with the branch node, and all the twig patterns are combined into a single prefix query tree that represents such queries by sharing their common prefixes. Consequently, all the twig patterns are evaluated in a single, document-order pass over the input document stream avoiding the translation of the set of twig patterns into a finite state automaton. Chapter 1 introduces the background of this issue. Chapter 2 discusses the representation of complex twig pattern as a query tree, how to combine a set of twig patterns into a single query three, how to match multi twig patterns over the incoming XML document, and possible optimization of computing logical AND/OR predicates. In section 3, the architecture of a XML stream process system named LeoXSQ is given. Section 4 shows the conducted experiments. In section 5, the related work is discussed. Section 6 summarizes this chapter.
Chapter Preview
Top

5.2 Multiple Twig Patterns Processing Over Xml Stream

In this section, we address the central topic: processing strategies for multiple twig patters over an XML stream. In 5.2.1, we describe a mechanism to represent the twig pattern with OR-predicates and AND-predicates as a query tree, and then they are combined into a single query tree with common prefix. In 5.2.2, we describe how to match the document stream with the twig patterns. In 5.2.3, we discuss the short-circuit evaluation for optimization.

Complete Chapter List

Search this Book:
Reset