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.
- S. Abiteboul, S. Cluet, and T. Milo. Correspondence and translation for heterogeneous data. In Proceedings of 6th Int. Conf. on Database Theory (ICDT), 1997. Google ScholarDigital Library
- S. Abiteboul, S. Cluet, and T. Milo. A logical view of structure files. VLDB Journal, 7(2):96--114, 1998. Google ScholarDigital Library
- S. M. Abramov and R. Glück. The universal resolving algorithm: Inverse computation in a functional language. In R. Backhouse and J. N. Oliveira, editors, Mathematics of Program Construction, volume 1837, pages 187--212. Springer-Verlag, 2000. Google ScholarDigital Library
- S. M. Abramov and R. Glück. Principles of inverse computation and the universal resolving algorithm. In T. Mogensen, D. Schmidt, and I. H. Sudborough, editors, The Essence of Computation: Complexity, Analysis, Transformation, volume 2566 of Lecture Notes in Computer Science, pages 269--295. Springer-Verlag, 2002. Google ScholarDigital Library
- P. Atzeni and R. Torlone. Management of multiple models in an extensible database design tool. In Proceedings of EDBT'96, LNCS 1057, 1996. Google ScholarDigital Library
- F. Bancilhon and N. Spyratos. Update semantics of relational views. TODS, 6(4):557--575, 1981. Google ScholarDigital Library
- T. Barsalou, N. Siambela, A. M. Keller, and G. Wiederhold. Updating relational databases through object-based views. In PODS'91, pages 248--257, 1991. Google ScholarDigital Library
- V. Braganholo, S. Davidson, and C. Heuser. On the updatability of XML views over relational databases. In WebDB 2003, 2003.Google Scholar
- P. Buneman, S. Khanna, and W.-C. Tan. On propagation of deletions and annotations through views. In PODS'02, pages 150--158, 2002. Google ScholarDigital Library
- S. S. Cosmadakis and C. H. Papadimitriou. Updates of relational views. Journal of the ACM, 31(4):742--760, 1984. Google ScholarDigital Library
- U. Dayal and P. A. Bernstein. On the correct translation of update operations on relational views. TODS, 7(3):381--416, September 1982. Google ScholarDigital Library
- 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. Technical Report MS-CIS-04-15, University of Pennsylvania, Aug. 2004. An earlier version appeared in the Workshop on Programming Language Technologies for XML (PLAN-X), 2004, under the title "A Language for Bi-Directional Tree Transformations". Google ScholarDigital Library
- G. Gottlob, P. Paolini, and R. Zicari. Properties and update semantics of consistent views. ACM Transactions on Database Systems (TODS), 13(4):486--524, 1988. Google ScholarDigital Library
- M. Hofmann and B. Pierce. Positive subtyping. In ACM SIGPLAN--SIGACT Symposium on Principles of Programming Languages (POPL), San Francisco, California, pages 186--197, Jan. 1995. Full version in Information and Computation, volume 126, number 1, April 1996. Also available as University of Edinburgh technical report ECS-LFCS-94-303, September 1994. Google ScholarDigital Library
- Z. Hu, S.-C. Mu, and M. Takeichi. A programmable editor for developing structured documents based on bi-directional transformations. In Partial Evaluation and Program Manipulation (PEPM), 2004. Google ScholarDigital Library
- A. M. Keller. Algorithms for translating view updates to database updates for views involving selections, projections, and joins. In PODS'85, 1985. Google ScholarDigital Library
- J. Lechtenbörger. The impact of the constant complement approach towards view updating. In Proceedings of the 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 49--55. ACM, June 9--12 2003. San Diego, CA. Google ScholarDigital Library
- Y. Masunaga. A relational database view update translation mechanism. In VLDB'84, 1984. Google ScholarDigital Library
- S. Matsuoka, S. Takahashi, T. Kamada, and A. Yonezawa. A general framework for bi-directional translation between abstract and pictorial data. ACM Transactions on Information Systems, 10(4):408--437, October 1992. Google ScholarDigital Library
- C. M. B. Medeiros and F. W. Tompa. Understanding the implications of view update policies. In VLDB'85, 1985.Google ScholarDigital Library
- L. Meertens. Designing constraint maintainers for user interaction, 1998. Manuscript.Google Scholar
- 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.Google ScholarCross Ref
- A. Ohori and K. Tajima. A polymorphic calculus for views and object sharing. In PODS'94, 1994. Google ScholarDigital Library
- F. J. Oles. Type algebras, functor categories, and block structure. In M. Nivat and J. C. Reynolds, editors, Algebraic Methods in Semantics. Cambrige University Press, 1985. Google ScholarDigital Library
- B. C. Pierce and A. Schmitt. Lenses and view update translation. Manuscript, 2003.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- I. Tatarinov, Z. G. Ives, A. Y. Halevy, and D. S. Weld. Updating XML. In SIGMOD Conference, 2001. Google ScholarDigital Library
- P. Wadler. Views: A way for pattern matching to cohabit with data abstraction. In ACM Symposium on Principles of Programming Languages (POPL), Munich, Germany. 1987. Google ScholarDigital Library
Index Terms
- Combinators for bi-directional tree transformations: a linguistic approach to the view update problem
Recommendations
Combinators for bi-directional tree transformations: a linguistic approach to the view update problem
POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languagesWe 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 ...
Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem
Special issue on POPL 2005We 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 ...
POPL 2005: Combinators for Bi-Directional Tree Transformations: Linguistic Approach to the View Update Problem
Supplemental issueWe propose a novel approach to the well-known view update problem for the case of tree-structured data: a domainspecific\ programming language in which all expressions denote bi-directional transformations on trees. In one direction, these ...
Comments