Combinators for bi-directional tree transformations: a linguistic approach to the view update problem

ABSTRACT

We propose a novel approach to the well-known view update problem for the case of tree-structured data: a domain-specific programming language in which all expressions denote bi-directional transformations on trees. In one direction, these transformations---dubbed lenses---map a "concrete" tree into a simplified "abstract view"; in the other, they map a modified abstract view, together with the original concrete tree, to a correspondingly modified concrete tree. Our design emphasizes both robustness and ease of use, guaranteeing strong well-behavedness and totality properties for well-typed lenses.We identify a natural space of well-behaved bi-directional transformations over arbitrary structures, study definedness and continuity in this setting, and state a precise connection with the classical theory of "update translation under a constant complement" from databases. We then instantiate this semantic framework in the form of a collection of lens combinators that can be assembled to describe transformations on trees. These combinators include familiar constructs from functional programming (composition, mapping, projection, conditionals, recursion) together with some novel primitives for manipulating trees (splitting, pruning, copying, merging, etc.). We illustrate the expressiveness of these combinators by developing a number of bi-directional list-processing transformations as derived forms.

REFERENCES

• 1: Serge Abiteboul , Sophie Cluet , Tova Milo, Correspondence and Translation for Heterogeneous Data, Proceedings of the 6th International Conference on Database Theory, p.351-363, January 08-10, 1997
• 2: Serge Abiteboul , Sophie Cluet , Tova Milo, A logical view of structured files, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.2, p.96-114, May 1998 [doi>10.1007/s007780050056]
• 3: Sergei M. Abramov , Robert Glück, The Universal Resolving Algorithm: Inverse Computation in a Functional Language, Proceedings of the 5th International Conference on Mathematics of Program Construction, p.187-212, July 03-05, 2000
• 4: Sergei Abramov , Robert Glück, Principles of inverse computation and the Universal resolving algorithm, The essence of computation: complexity, analysis, transformation, Springer-Verlag New York, Inc., New York, NY, 2002
• 5: Paolo Atzeni , Riccardo Torlone, Management of Multiple Models in an Extensible Database Design Tool, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.79-95, March 25-29, 1996
• 6: F. Bancilhon , N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems (TODS), v.6 n.4, p.557-575, Dec. 1981 [doi>10.1145/319628.319634]
• 7: Thierry Barsalou , Niki Siambela , Arthur M. Keller , Gio Wiederhold, Updating relational databases through object-based views, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.248-257, May 29-31, 1991, Denver, Colorado, United States
• 8: V. Braganholo, S. Davidson, and C. Heuser. On the updatability of XML views over relational databases. In WebDB 2003, 2003.
• 9: Peter Buneman , Sanjeev Khanna , Wang-Chiew Tan, On propagation of deletions and annotations through views, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543633]
• 10: Stavros S. Cosmadakis , Christos H. Papadimitriou, Updates of Relational Views, Journal of the ACM (JACM), v.31 n.4, p.742-760, Oct. 1984 [doi>10.1145/1634.1887]
• 11: Umeshwar Dayal , Philip A. Bernstein, On the correct translation of update operations on relational views, ACM Transactions on Database Systems (TODS), v.7 n.3, p.381-416, Sept. 1982 [doi>10.1145/319732.319740]
• 12: J. Nathan Foster , Michael B. Greenwald , Jonathan T. Moore , Benjamin C. Pierce , Alan Schmitt, Combinators for bi-directional tree transformations: a linguistic approach to the view update problem, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.233-246, January 12-14, 2005, Long Beach, California, USA
• 13: Georg Gottlob , Paolo Paolini , Roberto Zicari, Properties and update semantics of consistent views, ACM Transactions on Database Systems (TODS), v.13 n.4, p.486-524, Dec. 1988 [doi>10.1145/49346.50068]
• 14: Martin Hofmann , Benjamin Pierce, Positive subtyping, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.186-197, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199482]
• 15: Zhenjiang Hu , Shin-Cheng Mu , Masato Takeichi, A programmable editor for developing structured documents based on bidirectional transformations, Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.178-189, August 24-25, 2004, Verona, Italy [doi>10.1145/1014007.1014025]
• 16: Arthur M. Keller, Algorithms for translating view updates to database updates for views involving selections, projections, and joins, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.154-163, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325423]
• 17: Jens Lechtenbörger, The impact of the constant complement approach towards view updating, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.49-55, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773159]
• 18: Yoshifumi Masunaga, A Relational Database View Update Translation Mechanism, Proceedings of the 10th International Conference on Very Large Data Bases, p.309-320, August 27-31, 1984
• 19: Satoshi Matsuoka , Shin Takahashi , Tomihisa Kamada , Akinori Yonezawa, A general framework for bidirectional translation between abstract and pictorial data, ACM Transactions on Information Systems (TOIS), v.10 n.4, p.408-437, Oct. 1992 [doi>10.1145/146486.146557]
• 20: C. M. B. Medeiros and F. W. Tompa. Understanding the implications of view update policies. In VLDB'85, 1985.
• 21: L. Meertens. Designing constraint maintainers for user interaction, 1998. Manuscript.
• 22: S.-C. Mu, Z. Hu, and M. Takeichi. An algebraic approach to bi-directional updating. In ASIAN Symposium on Programming Languages and Systems (APLAS), Nov. 2004.
• 23: Atsushi Ohori , Keishi Tajima, A polymorphic calculus for views and object sharing (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.255-266, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182623]
• 24: F J Oles, Type algebras, functor categories and block structure, Algebraic methods in semantics, Cambridge University Press, New York, NY, 1986
• 25: B. C. Pierce and A. Schmitt. Lenses and view update translation. Manuscript, 2003.
• 26: B. C. Pierce, A. Schmitt, and M. B. Greenwald. Bringing Harmony to optimism: A synchronization framework for heterogeneous tree-structured data. Technical Report MS-CIS-03-42, University of Pennsylvania, 2003.
• 27: M. H. Scholl, C. Laasch, and M. Tresch. Updatable Views in Object-Oriented Databases. In C. Delobel, M. Kifer, and Y. Yasunga, editors, Proc. 2nd Intl. Conf. on Deductive and Object-Oriented Databases (DOOD), number 566. Springer, 1991.
• 28: Igor Tatarinov , Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Updating XML, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.413-424, May 21-24, 2001, Santa Barbara, California, United States
• 29: P. Wadler, Views: a way for pattern matching to cohabit with data abstraction, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.307-313, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41653]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Languages

Keywords:
XML, bi-directional programming, harmony, lenses, view update problem