Hash-Based Structural Join Algorithms
In: Proc. DATAX'06 Workshop, Munich. March, 2006
Authors
- Christian Mathis
- Theo Härder
Abstract
Algorithms for processing Structural Joins belong to the set of essential building blocks for XML query evaluation. Their design is a difficult task, because they have to satisfy many requirements, e.g., guarantee a linear worst-case runtime; generate a sorted, duplicate-free output; adapt to fiercely varying input sizes and element distributions; enable pipelining; and (probably) more. Therefore, it is not possible to design "the" structural join algorithm. Rather, the provision of different specialized operators, from which the query optimizer can choose, is beneficial for query efficiency. We propose new hash-based structural join algorithms that can process unordered input sequences possibly containing duplicates. We also show that these algorithms can substantially reduce the number of required sort operations on intermediate results for (complex) tree structured queries (twigs).
Full Text
BibTeX
@InProceedings{ Mathis.Haerder06hash-based,
title = { Hash-Based Structural Join Algorithms },
author = { Christian Mathis and Theo Härder },
booktitle = { Proc. DATAX'06 Workshop, Munich },
month = mar,
year = 2006,
}
This publication belongs to the project
A3XDB.
