Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem

ABSTRACT

We propose a novel approach to the view-update problem for tree-structured data: a domain-specific programming language in which all expressions denote bidirectional 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 begin by identifying a natural space of well-behaved bidirectional transformations over arbitrary structures, studying definedness and continuity in this setting. We then instantiate this semantic framework in the form of a collection of lens combinators that can be assembled to describe bidirectional 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, merging, etc.). We illustrate the expressiveness of these combinators by developing a number of bidirectional list-processing transformations as derived forms. An extended example shows how our combinators can be used to define a lens that translates between a native HTML representation of browser bookmarks and a generic abstract bookmark format.

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: Serge Abiteboul , Jason McHugh , Michael Rys , Vasilis Vassalos , Janet L. Wiener, Incremental Maintenance for Materialized Views over Semistructured Data, Proceedings of the 24rd International Conference on Very Large Data Bases, p.38-49, August 24-27, 1998
• 4: 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
• 5: 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
• 6: 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
• 7: Paolo Atzeni , Riccardo Torlone, MDM: a multiple-data model tool for the management of heterogeneous database schemes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.528-531, May 11-15, 1997, Tucson, Arizona, United States
• 8: Henry G. Baker, NREVERSAL of Fortune - The Thermodynamics of Garbage Collection, Proceedings of the International Workshop on Memory Management, p.507-524, September 17-19, 1992
• 9: 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]
• 10: 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
• 11: Bennet, C. H. 1973. Logical reversibility of computation. IBM J. Resear. Devel. 17, 6, 525--532.
• 12: Aaron Bohannon , Benjamin C. Pierce , Jeffrey A. Vaughan, Relational lenses: a language for updatable views, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142399]
• 13: Braganholo, V., Davidson, S., and Heuser, C. 2003. On the updatability of XML views over relational databases. In International Workshop on the Web and Databases (WebDB'03).
• 14: 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]
• 15: S. S. Cosmadakis, TRANSLATING UPDATES OF RELATIONAL DATA BASE VIEWS, Massachusetts Institute of Technology, Cambridge, MA, 1983
• 16: 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]
• 17: C.J. Date, An Introduction to Database Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2003
• 18: 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]
• 19: de Paula Braganholo, V., Heuser, C. A., and Vittori, C. R. M. 2001. Updating relational databases through XML views. In Proceedings of the 3rd International Conference on Information Integration and Web-based Applications and Services (IIWAS).
• 20: Edsger W. Dijkstra, Program Inversion, Program Construction, International Summer Schoo, p.54-57, July 26-August 06, 1978
• 21: Fogel, S. and Lane, P. 2005. Oracle Database Administrator's Guide. Oracle.
• 22: J. Nathan Foster , Michael B. Greenwald , Christian Kirkegaard , Benjamin C. Pierce , Alan Schmitt, Exploiting schemas in data synchronization, Journal of Computer and System Sciences, v.73 n.4, p.669-689, June, 2007 [doi>10.1016/j.jcss.2006.10.024]
• 23: Foster, J. N., Pierce, B. C., and Schmitt, A. 2006. Harmony Programmer's Manual. Available at http://www.seas.upenn.edu/~harmony/.
• 24: 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]
• 25: Stephen J. Hegner, Foundations of canonical update support for closed database views, Proceedings of the third international conference on database theory on Database theory, p.422-436, November 1990, Paris, France
• 26: Stephen J. Hegner, An Order-Based Theory of Updates for Closed Database Views, Annals of Mathematics and Artificial Intelligence, v.40 n.1-2, p.63-125, January 2004 [doi>10.1023/A:1026158013113]
• 27: 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]
• 28: 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]
• 29: International Business Machines Corporation. 2004. IBM DB2 Universal Database Administration Guide: Implementation.
• 30: Michael Johnson , Robert Rosebrugh , C. N. G. Dampney, View updates in a semantic data modelling paradigm, Proceedings of the 12th Australasian database conference, p.29-36, January 29-February 01, 2001, Queensland, Australia
• 31: 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]
• 32: Arthur M. Keller, Choosing a View Update Translator by Dialog at View Definition Time, Proceedings of the 12th International Conference on Very Large Data Bases, p.467-474, August 25-28, 1986
• 33: Landauer, R. 1961. Irreversibility and heat generation in the computing process. IBM J. Resear. Devel. 5, 3, 183--191. (Republished in IBM J. Resear. and Devel. 44, (1/2, 261--269 (Jan/Mar). 2000).
• 34: 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]
• 35: Lorentz, D. 2005. Oracle Database SQL Reference. Oracle.
• 36: 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
• 37: 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]
• 38: McCarthy, J. 1956. The inversion of functions defined by turing machines. In Automata Studies, Annals of Mathematical Studies, C. E. Shannon and J. McCarthy, Eds. Number 34. Princeton University Press, 177--181.
• 39: Medeiros, C. M. B. and Tompa, F. W. 1985. Understanding the implications of view update policies. In Proceedings of the International Conference on Very Large Databases (VLDB'85).
• 40: Meertens, L. 1998. Designing constraint maintainers for user interaction. Manuscript. Available at ftp://ftp.kestrel.edu/pub/papers/meertens/dcm.ps.
• 41: Microsoft 2005. Creating and Maintaining Databases. Microsoft.
• 42: Renée J. Miller , Mauricio A. Hernández , Laura M. Haas , Lingling Yan , C. T. Howard Ho , Ronald Fagin , Lucian Popa, The Clio project: managing heterogeneity, ACM SIGMOD Record, v.30 n.1, p.78-83, March 2001 [doi>10.1145/373626.373713]
• 43: Mu, S.-C., Hu, Z., and Takeichi, M. 2004a. An algebraic approach to bi-directional updating. In ASIAN Symposium on Programming Languages and Systems (APLAS).
• 44: Mu, S.-C., Hu, Z., and Takeichi, M. 2004b. An injective language for reversible computation. In 17th International Conference on Mathematics of Program Construction (MPC).
• 45: Joachim Niehren , Andreas Podelski, Feature Automata and Recognizable Sets of Feature Trees, Proceedings of the International Joint Conference CAAP/FASE on Theory and Practice of Software Development, p.356-375, April 13-17, 1993
• 46: 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]
• 47: F J Oles, Type algebras, functor categories and block structure, Algebraic methods in semantics, Cambridge University Press, New York, NY, 1986
• 48: Pierce, B. C. Bohannon, A., Foster, J. N., Greenwald, M. B., Khanna, S., Kunal, K., and Schmidt, A. 2006. Harmony: A synchronization framework for heterogeneous tree-structured data. Available at http://www.seas.upenn.edu/~harmony/.
• 49: Pierce, B. C., Schmitt, A., and Greenwald, M. B. 2003. Bringing Harmony to optimism: A synchronization framework for heterogeneous tree-structured data. Tech. rep. MS-CIS-03-42, University of Pennsylvania (Superseded by MS-CIS-05-02).
• 50: Pierce, B. C. and Vouillon, J. 2004. What's in Unison? A formal specification and reference implementation of a file synchronizer. Tech. rep. MS-CIS-03-36, Department of Computer and Information Science, University of Pennsylvania.
• 51: Lawrence A. Rowe , Kurt A. Shoens, Data abstraction, views and updates in RIGEL, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582107]
• 52: Scholl, M. H., Laasch, C., and Tresch, M. 1991. Updatable views in object-oriented databases. In Proceedings of the 2nd International Conference on Deductive and Object-Oriented Databases (DOOD), C. Delobel, M. Kifer, and Y. Yasunga, Eds. vol. 566. Springer.
• 53: Spoonhower, D. 2004. View updates seen through the lens of synchronization. Manuscript. Available at www.cs.cmu.edu/~spoons/courses/15-721/project/report.ps.
• 54: 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
• 55: 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]
• 56: Glynn Winskel, The formal semantics of programming languages: an introduction, MIT Press, Cambridge, MA, 1993
• 57: XQuery 2005. XQuery 1.0: An XML Query Language, W3C Working Draft. Available at http://www.w3.org/TR/xquery/.

INDEX TERMS

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

General Terms:
Languages

Keywords:
Bidirectional programming, Harmony, XML, lenses, view update problem