biXid: a bidirectional transformation language for XML

ABSTRACT

Often, independent organizations define and advocate different XML formats for a similar purpose and, as a result, application programs need to mutually convert between such formats. Existng XML transformation languages, such as XSLT and XDuce, are unsatisfactory for this purpose since we would have to write, e.g., two programs for the forward and the backward transformations in case of two formats, incur high developing and maintenance costs.This paper proposes the bidirectional XML transformation language biXid, allowing us to write only one program for both directions of conversion. Our language adopts a common paradigm programming-by-relation, where a program defines a relation over documents and transforms a document to another in a way satisfying this relation. Our contributions here are specific language features for facilitating realistic conversions whose target formats are loosely in parallel but have many discrepancies in details. Concretely, we (1) adopt XDuce-style regular expression patterns for describing and analyzing XML structures, (2) fully permit ambiguity for treating formats that do not have equivalent expressivenesses, and (3) allow non-linear pattern variables for expressing non-trivial transformations that cannot be written only with linear patterns, such as conversion between unordered and ordered data.We further develop an efficient evaluation algorithm for biXid, consisting of the "parsing" phase that transforms the input document to an intermediate "parse tree" structure and the "unparsing" phase that transforms it to an output document. Both phases use a variant of finite tree automata for performing a one-pass scan on the input or the parse tree by using a standard technique that "maintains the set of all transitable states." However, the construction of the "unparsing" phase is challenging since ambiguity causes different ways of consuming the parse tree and thus results in multiple possible outputs that may have different structures.We have implemented a prototype system of biXid and confirmed that it has enough expressiveness and a linear-time performance from experiments with several realistic bidirectional transformations including one between vCard-XML and ContactXML.

References

1. V. Benzaken, G. Castagna, and A. Frisch. CDuce: An XML-centric general-purpose language. In Proceedings of the International Conference on Functional Programming (ICFP), pages 51--63, 2003.
2. R. Bourret. XML data binding resources, 2001. http://www.rpbourret.com/xml/XMLDataBinding.htm.
3. C. Brabrand, A. Møller, and M.I. Schwartzbach. Dual syntax for XML languages. In Proc. 10th International Workshop on Database Programming Languages, DBPL '05, volume 3774 of LNCS, pages 27--41. Springer-Verlag, August 2005.
4. J. Clark. XSL Transformations (XSLT), 1999. http://www.w3.org/TR/xslt.
5. J. Clark and M. Murata. RELAX NG, 2001. http://www.relaxng.org.
6. J. Coelho and M. Florido. Type-based XML processing in logic programming. In PADL, pages 273--285, 2003.
7. ContactXML Users Group. ContactXML, 2000. http://www.contactxml.org/.
8. R. Elmasri and S. B. Navathe. Fundamentals of Database Systems, 2nd Edition. Benjamin/Cummings, 1994.
9. D. C. Fallside. XML Schema Part 0: Primer, W3C Recommendation, 2001. http://www.w3.org/TR/xmlschema-0/.
10. J.N. Foster, M.B. Greenwald, J.T. Moore, B.C. Pierce, and A. Schmitt. Combinators for bi-directional tree transformations: A linguistic approach to the view update problem. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 233--246, 2005.
11. V.B. Gundersen and Z.W. Hendrikse. BibTeX as XML markup, 2005. http://bibtexml.sourceforge.net/index.html.
12. H. Hosoya. Regular expression pattern matching - a simpler design. Technical Report 1397, RIMS, Kyoto University, 2003.
13. H. Hosoya and M. Murata. Boolean operations and inclusion test for attribute-element constraints. In Eighth International Conference on Implementation and Application of Automata, volume 2759 of Lecture Notes in Computer Science, pages 201--212. Springer-Verlag, 2003.
14. H. Hosoya and B.C. Pierce. Regular expression pattern matching for XML. In The 25th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 67--80, Jan. 2001.
15. H. Hosoya and B.C. Pierce. XDuce: A typed XML processing language. ACM Transactions on Internet Technology, 3(2):117--148, 2003. Short version appeared in Proceedings of Third International Workshop on the Web and Databases (WebDB2000), volume 1997 of Lecture Notes in Computer Science, pp. 226--244, Springer-Verlag.
16. H. Hosoya, J. Vouillon, and B.C. Pierce. Regular expression types for XML. ACM Transactions on Programming Languages and Systems, 27(1):46--90, 2004. Short version appeared in Proceedings of the International Conference on Functional Programming (ICFP), pp. 11--22, 2000.
17. R. Iannella. Representing vCard objects in RDF/XML, 2001. http://www.w3.org/TR/vcard-rdf.
18. S.-C. Mu, Z. Hu, and M. Takeichi. An algebraic approach to bi-directional updating. In APLAS, pages 2--20, 2004.
19. M. Murata, D. Lee, and M. Mani. Taxonomy of XML schema languages using formal language theory. In Extreme Markup Languages, 2001.
20. Python XML Special Interest Group. The XML bookmark exchange language, 1998. http://pyxml.sourceforge. net/topics/xbel/.
21. L. Sterling and E. Y. Shapiro. The Art of Prolog-Advanced Programming Techniques. MIT Press, 1986.
22. E. Wilde. BibTeXML (BibTeX markup language), 2004. http://dret. net/projects/bibtexml/.

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Constraints

        • Data types and structures