JCSE, vol. 4, no. 4, pp.313-349, December, 2010

DOI:

Formal Models and Algorithms for XML Data Interoperability

Thomas Y. Lee, David W. Cheung
Department of Computer Science, The University of Hong Kong, Hong Kong, China

Abstract: In this paper, we study the data interoperability problem of web services in terms of XML schema compatibility. When Web Service A sends XML messages to Web Service B, A is interoperable with B if B can accept all messages from A. That is, the XML schema R for B to receive XML instances must be compatible with the XML schema S for A to send XML instances, i.e., A is a subschema of B. We propose a formal model called Schema Automaton (SA) to model W3C XML Schema (XSD) and develop several algorithms to perform different XML schema computations. The computations include schema minimization, schema equivalence testing, subschema testing, and subschema extraction. We have conducted experiments on an e-commerce standard XSD called xCBL to demonstrate the practicality of our algorithms. One experiment has refuted the claim that the xCBL 3.5 XSD is backward compatible with the xCBL 3.0 XSD. Another experiment has shown that the xCBL XSDs can be effectively trimmed into small subschemas for specific applications, which has significantly reduced the schema processing time.

Keyword: Algorithms, Theory, Web Service data interoperability. XML schema equivalence and compatibility testing, XML subschema extraction, Schema Automaton, Data Treeyda

Full Paper:   319 Downloads, 4965 View