Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams

We introduce an extension of the XQuery language, FluX, that supports event-based query processing and the conscious handling of main memory buffers. Purely event-based queries of this language can be executed on streaming XML data in a very direct way. We then develop an algorithm that allows to efficiently rewrite XQueries into the event-based FluX language. This algorithm uses order constraints from a DTD to schedule event handlers and to thus minimize the amount of buffering required for evaluating a query. We discuss the various technical aspects of query optimization and query evaluation within our framework. This is complemented with an experimental evaluation of our approach.

• Publication year

  2004

• Venue

  Very Large Data Bases Conference

• Publication date

  2004-06-07

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1016/B978-012088469-8.50023-1arXiv cs/0406016
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Taxonomy of XML schema languages using formal language theory

  2005cited by this paper
• Processing XML Streams with Deterministic Automata

  2003cited by this paper
• Projecting XML Documents

  2003cited by this paper
• Stream processing of XPath queries with predicates

  2003cited by this paper
• Reformulation of XML Queries and Constraints

  2003cited by this paper
• An evaluation of regular path expressions with qualifiers against XML streams

  2003cited by this paper
• The BEA/XQRL Streaming XQuery Processor

  2003cited by this paper
• Efficient filtering of XML documents with XPath expressions

  2002cited by this paper
• Query processing of streamed XML data

  2002cited by this paper
• A Transducer-Based XML Query Processor

  2002cited by this paper
• A Semi-monad for Semi-structured Data

  2001cited by this paper
• Efficient Filtering of XML Documents for Selective Dissemination of Information

  2000cited by this paper
• One-Unambiguous Regular Languages

  1998cited by this paper
• Data on the web?

  1995cited by this paper
• Depth-First Search and Linear Graph Algorithms

  1972cited by this paper
• Edinburgh Research Explorer Path Queries on Compressed XML

  year unknowncited by this paper

• Learning k-Occurrence Regular Expressions with Interleaving

  2019cites this paper
• Context-Free Grammars for Deterministic Regular Expressions with Interleaving

  2019cites this paper
• Learning Restricted Regular Expressions with Interleaving

  2019cites this paper
• Inferring Regular Expressions with Interleaving from XML Data

  2018cites this paper
• Learning Concise Relax NG Schemas Supporting Interleaving from XML Documents

  2018cites this paper
• Learning Restricted Regular Expressions with Interleaving from XML Data

  2018cites this paper
• Inference of a Concise Regular Expression Considering Interleaving from XML Documents

  2018cites this paper
• Inferring a Relax NG Schema from XML Documents

  2016cites this paper
• Practical Study of Subclasses of Regular Expressions in DTD and XML Schema

  2016cites this paper
• Modeling, Analysis, and Optimization of Data-Driven Scientfic Workflows

  2014cites this paper
• A Research Survey on Large XML Data: Streaming, Selectivity Estimation and Parallelism

  2014cites this paper
• A survey on XML streaming evaluation techniques

  2013influential citation
• Efficient Streaming Algorithms for Tree Matching Problems

  2012cites this paper
• On Efficient Evaluation of XML Queries

  2011cites this paper
• Scalable XML Filtering for Content Subscriptions

  2011cites this paper
• Semantic Optimisation for CEP

  2011influential citation
• Ordered Types for Stream Processing of Tree-Structured Data

  2011cites this paper
• Streamable Fragments of Forward XPath

  2011cites this paper
• A Method for Semantic Optimization of Complex Event Processing

  2011cites this paper
• Algorithms for XML Stream Processing: Massive Data, External Memory and Scalable Performance. (Algorithms for XML stream processing : massive data, external memory and scalable performance)

  2011cites this paper
• Memory lower bounds for XPath evaluation over XML streams

  2011cites this paper
• Algorithmes de traitement de flux XML : masses de données, mémoire externe et performances extensibles

  2011cites this paper
• Cardinality-Aware and Purely Relational Xquery Processor

  2011cites this paper
• Robust Complex Event Pattern Detection over Streams

  2010cites this paper
• Inference of concise regular expressions and DTDs

  2010cites this paper
• Efficient evaluation of generalized tree-pattern queries on XML streams

  2010cites this paper
• Constraint-Aware Complex Event Pattern Detection over Streams

  2010cites this paper
• Ambiguous content and disambiguation of XML schemata

  2010cites this paper
• Learning Deterministic Regular Expressions for the Inference of Schemas from XML Data

  2010cites this paper
• Parallelizing XML data-streaming workflows via MapReduce

  2010cites this paper
• XML-based computation for scientific workflows

  2010cites this paper
• Worst-case optimal algorithm for XPath evaluation over XML streams

  2009cites this paper
• Cost-based vectorization of instance-based integration processes

  2009cites this paper
• Simplifying XML schema: effortless handling of nondeterministic regular expressions

  2009cites this paper
• Foundations of Xml: Regular Expressions Revisited

  2009cites this paper
• RA-010 Ordered Types for Stream Processing of Tree-Structured Data

  2009cites this paper
• Expressive and Scalable Event Stream Processing

  2009cites this paper
• Complexity of Decision Problems for XML Schemas and Chain Regular Expressions

  2009cites this paper
• Cardinality-Aware Purely Relational XQuery Processor

  2009cites this paper
• X-CSR: Dataflow Optimization for Distributed XML Process Pipelines

  2009cites this paper
• Parallelizing XML Processing Pipelines via MapReduce

  2009cites this paper
• Efficient XQuery Join Processing in Publish/Subscribe Systems

  2009cites this paper
• Aggregation for Scalability and Efficiency in XPath / XML-Based Publish / Subscribe Systems

  2008cites this paper
• Constraint-Aware XSLT Evaluation

  2008cites this paper
• Efficient Aggregation Algorithms on XML Stream

  2008cites this paper
• Buffer Management of the Results of Queries over XML Streams: Buffer Management of the Results of Queries over XML Streams

  2008cites this paper
• XQuery Processing on XML Stream with Order Clause

  2008cites this paper
• Learning deterministic regular expressions for the inference of schemas from XML data

  2008cites this paper
• StreamTX: extracting tuples from streaming XML data

  2008cites this paper
• Semantic query optimization for processing XML streams with minimized memory footprint

  2008cites this paper
• ELF: A Constraint-Aware XQuery Engine for Processing XML Streams with Minimized Memory Footprint

  2008influential citation
• Survey on the Web Syndication Current Issues

  2008cites this paper
• Buffer Management of the Results of Queries over XML Streams

  2008cites this paper
• XML Stream Processing Using a Lazy Concurrent Language

  2008cites this paper
• Modeling and optimization of scientific workflows

  2008cites this paper
• On the XML Data Stream and Xpath Queries

  2008cites this paper
• Subscription Aggregation for Scalability and Efficiency in XPath/XML-Based Publish/Subscribe Systems

  2008cites this paper
• An Efficient Streaming Algorithm for Evaluating XPath Queries

  2008cites this paper
• Automata for XML - A survey

  2007cites this paper
• XQuery Streaming a la Carte

  2007cites this paper
• Advanced Data Stream Sharing

  2007cites this paper
• Change-Resilient Design and Dataflow Optimization for Distributed XML Stream Processors

  2007cites this paper
• Efficiently Querying Large XML Data Repositories: A Survey

  2007cites this paper
• On-the-fly tuple selection for XQuery

  2007cites this paper
• A query system for XML data streams and its buffer reduction based on semantics

  2007cites this paper
• Inferring XML Schema Definitions from XML Data

  2007cites this paper
• Streaming XML Transformation Using Term Rewriting.

  2007influential citation
• Efficient algorithms for evaluating xpath over streams

  2007cites this paper
• Combined Static and Dynamic Analysis for Effective Buffer Minimization in Streaming XQuery Evaluation

  2007influential citation
• Querying temporal variable transportation data stream based on extended XQuery engine

  2007cites this paper
• Massively multi-query join processing in publish/subscribe systems

  2007cites this paper
• Bulk data in main memory-based XQuery evaluation

  2007cites this paper
• Quality-of-Service-Aware Data Stream Processing

  2007cites this paper
• Optimizing Schema Languages for XML: Numerical Constraints and Interleaving

  2007cites this paper
• Active Learning from Data Streams

  2007cites this paper
• A column-oriented data stream engine

  2007cites this paper
• The GCX System: Dynamic Buffer Minimization in Streaming XQuery Evaluation

  2007influential citation
• PTDOM: a schema‐aware XML database system for MPEG‐7 media descriptions

  2006cites this paper
• AFilter: adaptable XML filtering with prefix-caching suffix-clustering

  2006cites this paper
• SketchTree: Approximate Tree Pattern Counts over Streaming Labeled Trees

  2006cites this paper
• An Efficient XPath Query Processor for XML Streams

  2006influential citation
• Online Evaluation of Regular Tree Queries

  2006influential citation
• MonetDB/XQuery: a fast XQuery processor powered by a relational engine

  2006cites this paper
• Inference of concise DTDs from XML data

  2006cites this paper
• Processing queries on tree-structured data efficiently

  2006cites this paper
• Parallelizing XQuery In a Cluster Environment

  2006cites this paper
• Unifying the Processing of XML Streams and Relational Data Streams

  2006cites this paper
• Pathfinder: XQuery Compilation Techniques for Relational Database Targets

  2006cites this paper
• Grid-Based Data Stream Processing in e-Science

  2006cites this paper
• Query processing on data streams

  2006cites this paper
• Mediation on XQuery Views

  2006cites this paper
• XQuery Compilation Techniques for Relational Database Targets

  2006cites this paper
• Understanding the behavior of compiler optimizations

  2006cites this paper
• Technische Universitt Mnchen Fakultt f¨ ur Informatik Lehrstuhl III - Datenbanksysteme Query Processing on Data Streams

  2006cites this paper
• Efficient and parallel evaluation of xquery

  2006influential citation
• On the complexity of nonrecursive XQuery and functional query languages on complex values

  2006cites this paper
• StreamGlobe: Processing and Sharing Data Streams in Grid-Based P2P Infrastructures

  2005cites this paper
• Extending XML document projection for data integration

  2005cites this paper
• On the role of composition in XQuery

  2005cites this paper
• On the complexity of nonrecursive XQuery and functional query languages on complex values

  2005cites this paper