Finding an optimum edit script between an XML document and a DTD

ABSTRACT

Finding an optimum edit script between data plays an important role in data retrieval and data transformation. Many methods for finding an optimum edit script between two XML documents have been proposed so far, but few studies on finding an optimum edit script between an XML document and a DTD have been made. In this paper, we first show a polynomial-time algorithm that finds an optimum edit script between an XML document (modeled as an ordered tree) and a DTD. We next prove that, if the cost of an operation on a node in a tree may depend on the other nodes, then the corresponding decision problem becomes strongly NP-complete.

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: Elisa Bertino , Giovanna Guerrini , Marco Mesiti, A matching algorithm for measuring the structural similarity between an XML document and a DTD and its applications, Information Systems, v.29 n.1, p.23-46, March 2004 [doi>10.1016/S0306-4379(03)00031-0]
• 3: Sudarshan S. Chawathe, Comparing Hierarchical Data in External Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.90-101, September 07-10, 1999
• 4: 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
• 5: Sudarshan S. Chawathe , Anand Rajaraman , Hector Garcia-Molina , Jennifer Widom, Change detection in hierarchically structured information, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.493-504, June 04-06, 1996, Montreal, Quebec, Canada
• 6: Amelie Marian, Detecting Changes in XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.41, February 26-March 01, 2002
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: Mong Li Lee , Liang Huai Yang , Wynne Hsu , Xia Yang, XClust: clustering XML schemas for effective integration, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584841]
• 9: Marco Mesiti , Elisa Bertino , Giovanna Guerrini, An abstraction-based approach to measuring the structural similarity between two unordered XML documents, Proceedings of the 1st international symposium on Information and communication technologies, September 24-26, 2003, Dublin, Ireland
• 10: A. Nierman and H. V. Jagadish. Evaluating structural similarity in xml documents. In Proc. WebDB, pages 61--66, 2002.
• 11: Yannis Papakonstantinou , Victor Vianu, Incremental Validation of XML Documents, Proceedings of the 9th International Conference on Database Theory, p.47-63, January 08-10, 2003
• 12: Luc Segoufin , Victor Vianu, Validating streaming XML documents, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543622]
• 13: L. Xyleme. A dynamic warehouse for xml data of the web. IEEE Data Eng. Bull., 24(2):40--47, 2001.
• 14: K. Zhang , D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, v.18 n.6, p.1245-1262, Dec. 1989 [doi>10.1137/0218082]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

General Terms:
Algorithms

Keywords:
DTD, XML, document transformation, edit script