Merging changes in XML documents using reliable context fingerprints

ABSTRACT

Different dialects of XML have emerged as ubiquitous document exchange formats. For effective collaboration based on such documents, the capability to propagate edit operations performed on a document is indispensable. In order to avoid the transmission of whole documents, deltas are used to describe these edit operations, allowing the construction of a new version of a document. However, patching a document with a delta it was not generated for is error-prone, and any insert or delete operations performed on the document are likely to affect all subsequent paths within that document.

In this paper, we present a delta format for XML documents that uses context-aware fingerprints to identify edit operations. This allows our XML patch procedure to find the correct position of an edit operation, even if the document was updated in the meantime. Possible conflicts are detected. Experimental results show the reliability of the presented fingerprinting technique and prove the high quality of the resulting patched documents.

REFERENCES

• 1: S. Balasubramaniam , Benjamin C. Pierce, What is a file synchronizer?, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.98-108, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288261]
• 2: J. Boyer. Canonical XML version 1.0, 2001.
• 3: Emmanuel Bruno , Jacques Le Maitre , Elisabeth Murisasco, Extending xQuery with transformation operators, Proceedings of the 2003 ACM symposium on Document engineering, November 20-22, 2003, Grenoble, France [doi>10.1145/958220.958223]
• 4: D. Chamberlin, D. Florescu, J. Melton, J. Robie, and J. Siméon. XQuery Update Facility 1.0, 2008.
• 5: Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.26-37, May 11-15, 1997, Tucson, Arizona, United States
• 6: J. Clark and S. deRose. XML Path Language (XPath). Technical report, World Wide Web Consortium, 1999.
• 7: Amelie Marian, Detecting Changes in XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.41, February 26-March 01, 2002
• 8: Deise de Brum Saccol , Nina Edelweiss , Renata de Matos Galante , Carlo Zaniolo, XML version detection, Proceedings of the 2007 ACM symposium on Document engineering, August 28-31, 2007, Winnipeg, Manitoba, Canada [doi>10.1145/1284420.1284441]
• 9: D. Eastlake, J. Reagle, and D. Solo. XML-Signature syntax and processing, 2002.
• 10: R. L. Fontaine. Merging XML files: a new approach providing intelligent merge of XML data sets. In Proceedings of XML Europe 2002, 2002.
• 11: Free Software Foundation. Comparing and Merging Files, 2002.
• 12: C.-L. Ignat and M. C. Norrie. Flexible collaboration over XML documents. In CDVE, pages 267--274, 2006.
• 13: S. Khanna, K. Kunal, and B. C. Pierce. A formal investigation of diff3. In Arvind and Prasad, editors, Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec. 2007.
• 14: H.-K. Ko and S. Lee. An efficient scheme to completely avoid re-labeling in XML updates. In WISE, pages 259--264, 2006.
• 15: J. Kornblum. Identifying almost identical files using context triggered piecewise hashing. Digital Investigation, 3(Supplement-1):91--97, 2006.
• 16: Franky Lam , Nicole Lam , Raymond Wong, Efficient synchronization for mobile XML data, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584820]
• 17: E. Leonardi, S. S. Bhowmick, and S. K. Madria. Xandy: Detecting changes on large unordered XML documents using relational databases. In L. Zhou, B. C. Ooi, and X. Meng, editors, DASFAA, volume 3453 of Lecture Notes in Computer Science, pages 711--723. Springer, 2005.
• 18: Tancred Lindholm, A three-way merge for XML documents, Proceedings of the 2004 ACM symposium on Document engineering, October 28-30, 2004, Milwaukee, Wisconsin, USA [doi>10.1145/1030397.1030399]
• 19: Tancred Lindholm , Jaakko Kangasharju , Sasu Tarkoma, A hybrid approach to optimistic file system directory tree synchronization, Proceedings of the 4th ACM international workshop on Data engineering for wireless and mobile access, June 12-12, 2005, Baltimore, MD, USA [doi>10.1145/1065870.1065879]
• 20: Tancred Lindholm , Jaakko Kangasharju , Sasu Tarkoma, Fast and simple XML tree differencing by sequence alignment, Proceedings of the 2006 ACM symposium on Document engineering, October 10-13, 2006, Amsterdam, The Netherlands [doi>10.1145/1166160.1166183]
• 21: 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
• 22: H. Maruyama, K. Tamura, and N. Uramoto. Digest Values for DOM (DOMHASH), 2000.
• 23: R. Rivest. The md5 message-digest algorithm, 1992.
• 24: S. Rönnau and U. M. Borghoff. Intelligent merging of XML documents for distributed collaboration. In Proceedings of the Distributed Intelligent Systems and Technologies Workshop, pages 71--78, St. Petersburg, Russia, 2008.
• 25: Sebastian Rönnau , Jan Scheffczyk , Uwe M. Borghoff, Towards XML version control of office documents, Proceedings of the 2005 ACM symposium on Document engineering, November 02-04, 2005, Bristol, United Kingdom [doi>10.1145/1096601.1096606]
• 26: Luis J. Arévalo Rosado , Antonio Polo Márquez , Jorge Martínez Gil, Managing Branch Versioning in Versioned/Temporal XML Documents, Proceedings of the 5th international Symposium on XML Database: Database and XMLTechnologies, September 23-24, 2007, Vienna, Austria [doi>10.1007/978-3-540-75288-2_9]
• 27: B. Stein. Fuzzy-fingerprints for text-based information retrieval. In I-KNOW'05: Proceedings of the 5th International Conference on Knowledge Management, pages 572--579. Journal of Universal Computer Science, 2005.
• 28: Igor Tatarinov , Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Updating XML, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.413-424, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Version control

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Document management

General Terms:
Algorithms, Management, Reliability

Keywords:
CSCW, XML diff, XML patch, fingerprint, office applications, version control