Labeling dynamic XML trees

ABSTRACT

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.

REFERENCES

• 1: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 2: Serge Abiteboul , Haim Kaplan , Tova Milo, Compact labeling schemes for ancestor queries, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 07-09, 2001, Washington, D.C., United States
• 3: Hassan Aït-Kaci, An algebraic semantics approach to the effective resolution of type equations, Theoretical Computer Science, v.45 n.3, p.293-351, Sept., 1986
• 4: Stephen Alstrup , Theis Rauhe, Improved labeling scheme for ancestor queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.947-953, January 06-08, 2002, San Francisco, California
• 5: Yves Caseau, Efficient handling of multiple inheritance hierarchies, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.271-287, September 26-October 01, 1993, Washington, D.C., United States
• 6: R. G. G. Cattell, editor. The Object Database Standard: ODMG-93. Morgan Kaufmann, San Mateo, California, 1994.
• 7: D. Chamberlin, J. Clark, D. Florescu, J. Robie, J. Siméon, and M. Stefanescu. XQuery 1.0: An XML Query Language. W3C working draft, June 2001. http://www.w3.org/TR/xquery.
• 8: Haim Kaplan , Tova Milo , Ronen Shabo, A comparison of labeling schemes for ancestor queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.954-963, January 06-08, 2002, San Francisco, California
• 9: Amélie Marian , Serge Abiteboul , Gregory Cobena , Laurent Mignet, Change-Centric Management of Versions in an XML Warehouse, Proceedings of the 27th International Conference on Very Large Data Bases, p.581-590, September 11-14, 2001
• 10: N. Santoro and R. Khatib. Labeling and implicit routing in networds. The Computer J., 28:5-8, 1985.
• 11: W3C. Extensible markup language (XML) 1.0. http://www.w3.org/TR/REC-xml.
• 12: W3C. Extensible stylesheet language (XSL). http://www.w3.org/Style/XSL/.
• 13: W3C. Xsl transformations (xslt) specification. http://www.w3.org/TR/WD-xslt.
• 14: Xdex. http://www.xmlindex.com.
• 15: Xyleme. A dynamic data warehouse for the XML data of the Web. http://www.xyleme.com.
• 16: A. C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. 17th Annual Symposium on Foundations of Computer Science, pages 222-227, 1977.
• 17: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Markup languages

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Design, Languages, Theory