CoDE Publications CoDE Publications
IRIDIA Publications IRIDIA Publications
SMG Publications
WIT Publications
WIT Publications
SMG Publications
Home People Research Activities Publications Teaching Resources
By Class By Topic By Year Technical Reports
By Class By Topic By Year Technical Reports
login
F. Picalausa, F. Servais, and E. Zimányi. XEvolve: An XML Schema Evolution Framework. In Proceedings of the 26th ACM Symposium On Applied Computing, ACM SAC 2011, pages 1645-1650. ACM Press, TaiChung, Taiwan, March 2011.

Abstract

This paper presents XEvolve, a framework that unifies streaming validation of XML documents, and efficient testing of equivalence and inclusion of specifications for various XML schema languages. For these purposes, this framework relies on Visibly Pushdown Automata (VPA) as a unifying model for the various schema languages. Schemas are first translated into VPA; standard algorithms for VPA can be then used to validate documents as well as to test equivalence or inclusion of schemas. In general, inclusion and equivalence are tested in exponential-time. However, when the given specifications are provided as DTD or XSD, these tests have a polynomial-time complexity with respect to the automaton size. Moreover, in this case the memory footprint of the validation does not depend on the size of the input document but only on its depth.


Updated: 2017-03-27