EBSL: supporting deleted node label reuse in XML

Abstract

Recently, there has been much research into the specification of dynamic labeling schemes supporting XML updates. The primary design goal of any dynamic labeling scheme is to limit the growth rate in node label size, and consequently increase query performance and reduce update costs. The ability to reuse deleted node labels is a key property in achieving this goal. In this paper, we review the existing dynamic labeling schemes that provide this functionality and identify their shortcomings. We present our own dynamic labeling scheme that guarantees every delete node label can be reused. Further, we provide a deleted node label reuse strategy that best suits the nature of node insertions and deletions in an XML tree.