Querying and Updating XML Data based on Node Labeling Schemes

Abstract

All the existing techniques have high update cost, they can not completely avoid re-labeling in XML updates, and they will increase the label size which will influence the query performance. Thus in this thesis we propose a novel Compact Dynamic Binary String (CDBS) encoding to efficiently process updates. CDBS has two important properties which form the foundations of this thesis: (1) CDBS supports that CDBS codes can be inserted between any two consecutive CDBS codes with orders kept and without re-encoding; (2) CDBS is orthogonal to specific labeling schemes, thus it can be applied broadly to different labeling schemes or other applications to efficiently process order-sensitive updates. Moreover, we improve CDBS to Compact Dynamic Quaternary String (CDQS) encoding to overcome the overflow problem and to completely avoid re-labeling in XML leaf node updates. We also propose an approach to much more efficiently process internal node updates.