Efficient Processing of Updates in Dynamic Graph-Structured XML Data

摘要

When the ID/IDREF relationship is considered, an XML document needs to be modeled as an ordered graph more naturally than an ordered tree. Then it becomes more difficult to process the updates of XML document. This paper studies the incremental maintenance of the document order and reachability relationship in Graph-structured XML. We propose an extended interval labeling scheme to label the document order and reachability relationship in XML. We identify the main reason for the inefficiency of updates of the labels. To accelerate the processing of updates, we design a novel index, called XUI. Based on the index, we propose an efficient update method, called UOGX. Our experimental evaluation illustrates the space efficiency and update performance of the proposed labeling.