XS-Diff: XML schema change detection algorithm
Pages 160 - 192
Abstract
Detecting changes in XML data has emerged as an important research issue in the last decade, but the majority of change detection algorithms focus on XML documents rather than on their schemas because documents that contain data are deemed more significant than the schema itself. However, the XML schema change detection tool is essential, especially in situations where we need to maintain related XML documents with evolving schema, sustain relational schema generated by schema-conscious approach for storing XML data and provide support for XML versioning. This paper focuses on XML Schema XSD changes and provides a more meaningful description of the detected changes. Our proposed algorithm XS-Diff uses the technique of storing XML Schema versions in a relational database where the detection and storage of delta changes are employed on relational tables. We demonstrate the correctness of the proposed algorithm through both synthetic and real data sets without deteriorating the execution time.
References
[1]
Al-Ekram, R., Adma, A. and Baysal, O. (2005) 'diffX: an algorithm to detect changes in multiversion XML documents', Proceedings of the 2005 Conference of the Centre for Advanced Studies on Collaborative Research, 17-20 October, Toronto, Ontario, Canada, pp.1-11.
[2]
Altova.com (2014) Comparing XML schemas with DiffDog. Available online at: http://www.altova.com/technote20.html (accessed on 24 May 2014).
[3]
Baqasah, A., Pardede, E., Holubova, I. and Rahayu, W. (2013) 'On change detection of XML Schemas', Proceedings of the 2013 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 16-18 July, Melbourne, VIC, pp.974-982.
[4]
Chawathe, S.S. and Garcia-Molina, H. (1997) 'Meaningful change detection in structured data', Proceedings ACM SIGMOD International Conference on Management of Data, 13-15 May, Tucson, AZ, pp.26-37.
[5]
Chawathe, S.S., Rajaraman, A., Garcia-Molina, H. and Widom, J. (1996) 'Change detection in hierarchically structured information', Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, 4-6 June, Montreal, Quebec, Canada, pp.493-504.
[6]
Cobena, G., Abdessalem, T. and Hinnach, Y. (2002a) A comparative study for XML change detection, National Institute for Research in Computer Science and Control, Rocquencourt, France. Available online at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.3647 (accessed on 24 May 2014).
[7]
Cobena, G., Abiteboul, S. and Marian, A. (2002b) 'Detecting changes in XML documents', Proceedings of the 18th International Conference on Data Engineering, 26 February- 1 March, San Jose, CA, pp.41-52.
[8]
Guerrini, G., Mesiti, M. and Rossi, D. (2005a) 'Impact of XML schema evolution on valid documents', Proceedings of the 7th Annual ACM International Workshop on Web Information and Data Management, 31 October-5 November, Bremen, Germany, pp.39-44.
[9]
Guerrini, G., Mesiti, M. and Rossi, D. (2005b) XML schema evolution, Department of Computer and Information Science, University of Genoa. Available online at: ftp://ftp.disi.unige.it/pub/.person/GuerriniG/reports/tr-schev-06.pdf (accessed on 24 May 2014).
[10]
IBM (1998) XML TreeDiff 1998. Available online at: http://www.xml.com/pub/r/536 (accessed on 24 May 2014).
[11]
Leonardi, E. and Bhowmick, S.S. (2005) 'Detecting changes on unordered XML documents using relational databases: a schema-conscious approach', Proceedings of the 14th ACM International Conference on Information and Knowledge Management, 31 October- 5 November, Bremen, Germany, pp.509-516.
[12]
Leonardi, E. and Bhowmick, S.S. (2007) 'XANADUE: a system for detecting changes to XML data in tree-unaware relational databases', Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, 12-14 June, Beijing, China, pp.1137-1140.
[13]
Leonardi, E., Hoai, T.T., Bhowmick, S.S. and Madria, S. (2007) 'DTD-Diff: a change detection algorithm for DTDs', Data and Knowledge Engineering, Vol. 61, No. 2, pp.384-402.
[14]
Marian, A., Abiteboul, S., Cobena, G. and Mignet, L. (2001) 'Change-centric management of versions in an XML warehouse', Proceedings of the 27th International Conference on Very Large Data Bases, 11-14 September, Roma, Italy, pp.581-590.
[15]
Maruyama, H., Tamura, K. and Uramoto, N. (2000) Digest values for DOM (DOMHASH), Available online at: http://www.research.ibm.com/trl/projects/xml/xss4j/docs/rfc2803.html (accessed on 24 May 2014).
[16]
Peters, L. (2005) 'Change detection in XML trees: a survey', Proceedings of the 3rd Twente Student Conference on IT, June, Enschede, the Netherlands, pp.1-8.
[17]
Raghavachari, M. and Shmueli, O. (2004) 'Efficient schema-based revalidation of XML', Proceedings of the 9th International Conference on Extending Database Technology, Heraklion, 14-18 March, Crete, Greece, pp.639-657.
[18]
Robin, L.F. (2001) A delta format for XML: identifying changes in XML files and representing the changes in XML, XML Europe 2001. Available online at: http://www.deltaxml.com/attachment/455-dxml/deltaxml-xml-europe-2001.pdf (accessed on 24 May 2014).
[19]
Shanmugasundaram, J., Tufte, K., He, G., Zhang, C., DeWitt, D. and Naughton, J. (1999) 'Relational databases for querying XML documents: limitations and opportunities', Proceedings of the 25th International Conference on Very Large Data Bases, 7-10 September, Edinburgh, Scotland, pp.302-314.
[20]
W3C (1999) XML Path Language (XPath) Version 1.0. Available online at: http://www.w3.org/TR/xpath/ (accessed on 24 May 2014).
[21]
W3C (2000) Extensible Markup Language (XML) 1.0. Available online at: http://www.w3.org/TR/2000/REC-xml-20001006 (accessed on 24 May 2014).
[22]
W3C (2004a) XML Schema Part 0: primer second edition. Available online at: http://www.w3.org/TR/2004/REC-xmlschema-0-20041028/ (accessed on 24 May 2014).
[23]
W3C (2004b) XML Schema Part 1: structures second edition. Available online at: http://www.w3.org/TR/xmlschema-1/ (accessed on 24 May 2014).
[24]
Wang, Y., DeWitt, D.J. and Cai, J-Y. (2003) 'X-Diff: an effective change detection algorithm for XML documents', Proceedings of the 19th International Conference on Data Engineering, 5-8 March, Bangalore, India, pp.519-530.
[25]
Yoshikawa, M., Amagasa, T. and Shimura, T. (2001) 'XRel: a path-based approach to storage and retrieval of XML documents using relational databases', ACM Transaction on Internet Technology, Vol. 1, No. 1, pp.110-141.
[26]
Zhang, K. and Shasha, D. (1989) 'Simple fast algorithms for the editing distance between trees and related problems', SIAM Journal on Computing, Vol. 18, No. 6, pp.1245-1262.
- XS-Diff: XML schema change detection algorithm
Recommendations
DTD-Diff: A change detection algorithm for DTDs
The DTD of a set of XML documents may change due to many reasons such as changes to the real-world events, changes to the user's requirements, and mistakes in the initial design. In this paper, we present a novel algorithm called DTD-Diff to detect the ...
DTD-Diff: a change detection algorithm for DTDs
DASFAA'06: Proceedings of the 11th international conference on Database Systems for Advanced ApplicationsThe DTD of a set of XML documents may change due to many reasons such as changes to the real world events, changes to the user's requirements, and mistakes in the initial design. In this paper, we present a novel algorithm called DTD-Diff to detect the ...
Towards semantic diff of XML documents
SAC '14: Proceedings of the 29th Annual ACM Symposium on Applied ComputingApplications are increasingly using XML to represent semi-structured data and, consequently, a large amount of XML documents is available worldwide. As XML documents evolve over time, comparing XML documents to understand their evolution becomes ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Inderscience Publishers
Geneva 15, Switzerland
Publication History
Published: 01 April 2015
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Feb 2025