A Dynamic Labeling Scheme Based on Logical Operators: A Support for Order-Sensitive XML Updates

AbstractDynamic XML labeling schemes have demonstrated important usages in XML Database Management Systems. Several researches have been conducted to provide dynamic labeling schemes that can efficiently process queries with less label size and space overhead in addition to the capability of processing order-sensitive updates effectively and efficiently (i.e., without re-labeling). In this paper, we introduce a dynamic labeling scheme as an enhancement to our previous static one, XDAS. Dynamic XDAS is developed as a hybrid labeling scheme that combines the original XDAS with another labeling scheme called IBSL. Dynamic XDAS conveys all characteristics of the original XDAS in addition to the efficient treatment with update processes with no re-labeling, which is adapted from IBSL. Like the original XDAS, our experiments show that dynamic XDAS still can identify the A-D, P-C and sibling relationships using logical operators with efficient label size and storage space. Moreover, dynamic XDAS is capable for processing node/subtree updates efficiently with completely avoiding re-labeling or re-calculations, just like IBSL