Labeling dynamic XML trees
Edith Cohen, Haim Y. Kaplan, Tova Milo · ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) · 2002
We present algorithms to label the nodes of an XML tree which is subject to insertions and deletions of nodes. The labeling is done such that (1) we label each node immediately when it is inserted and this label remains unchanged, and (2) from a pair of labels alone, we can decide whether one node is an ancestor of the other. This problem arises in the context of XML databases that support queries on the structure of the documents as well us on the changes made to the documents over time. We prove that our algorithms assign the shortest possible labels (up to a constant factor) which satisfy these requirements.We also consider the same problem when "clues" that provide guarantees on possible future insertions are given together with newly inserted nodes. Such clues can be derived from the DTD or from statistics on similar XML trees. We present algorithms that use the clues to assign shorter labels. We also prove that the length of our labels is close to the minimum possible.
Cited by 201 works. doi:10.1145/543613.543648
Authors
References
- Extensible markup language
- Data on the Web from relations to semistructured data and XML
- Proc. 26th annual symposium on Foundations of computer science
- Review of Data on the Web
- Compact routing schemes
- An algebraic semantics approach to the effective resolution of type equations
- Compact labeling schemes for ancestor queries
- Change-Centric Management of Versions in an XML Warehouse
- A comparison of labeling schemes for ancestor queries
- Efficient handling of multiple inheritance hierarchies