Lehrgebiet Informationssysteme

FB Informatik

LG IS

AG DBIS

(C) AG DBIS

Hash-Based Structural Join Algorithms

Christian Mathis

Kaiserslautern University of Technology
Dept. of Computer Science (AG DBIS)
P.O. Box 3049, 67653 Kaiserslautern, Germany
e-mail: mathis@informatik.uni-kl.de

Theo Härder

Kaiserslautern University of Technology
Dept. of Computer Science (AG DBIS)
P.O. Box 3049, 67653 Kaiserslautern, Germany
e-mail: haerder@informatik.uni-kl.de

Michael Haustein

Kaiserslautern University of Technology
Dept. of Computer Science (AG DBIS)
P.O. Box 3049, 67653 Kaiserslautern, Germany
e-mail: haustein@informatik.uni-kl.de

Full paper (PDF version)

Abstract

As observed in many publications so far, the matching of twig pattern queries is a core operation in XML database management systems (XDBMSs) for which the structural join and the holistic twig join algorithms were proposed. In a single-user environment, especially the latter algorithm provides a good evaluation strategy. However, when it comes to multi-user access to a single XML document, it may lead to extensive blocking situations: The XDBMS has to ensure data consistency and, therefore, has to prevent concurrent modification operations from changing elements in the input sequences, a holistic twig algorithm accesses while operating. To circumvent this problem, we propose a set of new locking-aware operators for twig pattern query evaluation that rely on stable path labeling IDs (SPLIDs) as well as document and element set indexes. Furthermore, by running empirical tests on a native XDBMS, we show that their performance is comparable to existing approaches in a single-user environment, and leads to higher throughput rates in the case of multi-user access.

in Proc. Sigmod, Chicago, June 2006.