Exchanging Active XML documents
Tova Milo


XML is becoming the universal format for data exchange between applications.
Recently, the emergence of Web services as standard means of publishing and
accessing data on the Web introduced a new class of XML documents, which we
call Active XML (AXML) documents.  These are XML documents where some of the
data is given explicitly while other parts are defined only intensionally by
means of embedded calls to Web services.

Peers exchanging AXML data agree on a *data exchange schema* that
specifies in particular which parts of the data are allowed to be
intensional.  Before sending a document, a peer may need to *rewrite*
it to match the agreed data exchange schema, by calling some
of the services and materializing their data.

We will see that the rewriting problem is difficult, undecidable in the
general case and of high complexity in some restricted cases, with tight
relationship to various tree and word automate problems. To overcome this
we will propose what we believe to be a more adequate, from a practical
view point, approach that is (1) in the spirit of standard
1-unambiguity constraints imposed on XML schema and (2) can be solved
by a single pass over the document with a computational device not
stronger than a finite state automaton.
Time permitting we will also consider some of the practical implications
of this solution, implementation-wise.