Regular rewriting of active XML and unambiguity

ABSTRACT

We consider here the exchange of Active XML (AXML) data, i.e., XML documents where some of the data is given explicitly while other parts are given only intensionally as 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. Previous works showed that the rewriting problem is undecidable in the general case and of high complexity in some restricted cases. We argue here that this difficulty is somewhat artificial. Indeed, we study what we believe to be a more adequate, from a practical view point, rewriting problem 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 automation. Following previous works, we focus on the core of the problem, i.e., on the problem on words. The results may be extended to (A)XML trees in a straightforward manner.

REFERENCES

• 1: Serge Abiteboul , Omar Benjelloun , Bogdan Cautis , Ioana Manolescu , Tova Milo , Nicoleta Preda, Lazy query evaluation for Active XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007596]
• 2: The Active XML homepage. http://activexml.net/.
• 3: Open Source Active XML (activexml). http://forge.objectweb.org/.
• 4: O. Benjelloun, T. Milo, and S. Raj Mathur. Towards efficient exchange of active xml data, 2004. Technical Report.
• 5: Anne Brüggemann-Klein , Derick Wood, One-unambiguous regular languages, Information and Computation, v.142 n.2, p.182-206, May 2, 1998 [doi>10.1006/inco.1997.2695]
• 6: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 7: Jakarta Project, Jelly: Executable XML. http://jakarta.apache.org/.
• 8: Macromedia Coldfusion MX 6.1. http://www.macromedia.com/.
• 9: W. Martens, F. Neven, and T. Schwentick. Which xml schemas admit 1-pass preorder typing? In Proc. of ICDT, 2005.
• 10: Tova Milo , Serge Abiteboul , Bernd Amann , Omar Benjelloun , Fred Dang Ngoc, Exchanging intensional XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872793]
• 11: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.11-22, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335171]
• 12: M. Murata, D. Lee, and M. Mani. "Taxonomy of XML Schema Languages using Formal Language Theory". In Extreme Markup Languages, Montreal, Canada, 2001.
• 13: A. Muscholl, T. Schwentick, and L. Segoufin. Active Context-Free Games. In Proc. of STACS, 2004.
• 14: J. Powell and T. Maxwell. Integrating Office XP Smart Tags with the Microsoft .NET Platform. http://msdn.microsoft.com.
• 15: Thomas Schwentick, Trees, automata and XML, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055589]
• 16: The World Wide Web Consortium. http://www.w3.org/.
• 17: The Xerces Java Parser. http://xml.apache.org/xerces-j/.
• 18: The XML Schema specification. http://www.w3.org/TR/XML/Schema.