Lehrgebiet Informationssysteme

FB Informatik

LG IS

AG DBIS

(C) AG DBIS

Node Labeling Schemes for Dynamic XML Documents Reconsidered

Theo Härder, Michael P. Haustein, Christian Mathis, Markus Wagner

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

Full paper (PDF version)

Abstract

We explore and compare suitable node labeling schemes to be used in collaborative XML DBMSs (XDBMSs, for short) supporting typical XML document processing (XDP) interfaces. Such schemes have to provide holistic support for essential XDBMS processing steps concerning declarative as well as navigational query processing and, with the same importance, lock management. In this paper, we evaluate existing range-based and prefix-based labeling schemes, before we propose our own scheme based on DeweyIDs. We experimentally explore the suitability of DeweyIDs as a general and immutable node labeling mechanism, stress their synergetic potential for query processing and locking, and show how they can be implemented efficiently. Various compression and optimization measures deliver surprising space reductions, frequently reduce the size of storage representation - compared to an already space-efficient encoding scheme - to less than 20 - 30% in the average and, thus, conclude their practical relevance.

in: Data & Knowledge Engineering, 2006.