POPL 2005: Combinators for Bi-Directional Tree Transformations: 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 domainspecific\ 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, merging, etc.). We illustrate the expressiveness of these combinators by developing a number of bi-directional list-processing transformations as derived forms
References
[1]
S. Abiteboul, S. Cluet, and T. Milo. Correspondence and translation for heterogeneous data. In Proceedings of 6th Int. Conf. on Database Theory (ICDT), 1997.
[2]
S. Abiteboul, S. Cluet, and T. Milo. A logical view of structure files. VLDB Journal, 7(2):96--114, 1998.
[3]
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.
[4]
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.
[5]
P. Atzeni and R. Torlone. Management of multiple models in an extensible database design tool. In Proceedings of EDBT'96, LNCS 1057, 1996.
[6]
F. Bancilhon and N. Spyratos. Update semantics of relational views. TODS, 6(4):557--575, 1981.
[7]
T. Barsalou, N. Siambela, A. M. Keller, and G. Wiederhold. Updating relational databases through object-based views. In PODS'91, pages 248--257, 1991.
[8]
V. Braganholo, S. Davidson, and C. Heuser. On the updatability of XML views over relational databases. In WebDB 2003, 2003.
[9]
P. Buneman, S. Khanna, and W.-C. Tan. On propagation of deletions and annotations through views. In PODS'02, pages 150--158, 2002.
[10]
S. S. Cosmadakis and C. H. Papadimitriou. Updates of relational views. Journal of the ACM, 31(4):742--760, 1984.
[11]
U. Dayal and P. A. Bernstein. On the correct translation of update operations on relational views. TODS, 7(3):381--416, September 1982.
[12]
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".
[13]
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.
[14]
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.
[15]
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.
[16]
A. M. Keller. Algorithms for translating view updates to database updates for views involving selections, projections, and joins. In PODS'85, 1985.
[17]
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.
[18]
Y. Masunaga. A relational database view update translation mechanism. In VLDB'84, 1984.
[19]
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.
[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]
A. Ohori and K. Tajima. A polymorphic calculus for views and object sharing. In PODS'94, 1994.
[24]
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.
[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]
I. Tatarinov, Z. G. Ives, A. Y. Halevy, and D. S. Weld. Updating XML. In SIGMOD Conference, 2001.
[29]
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.
Index Terms
- POPL 2005: Combinators for Bi-Directional Tree Transformations: Linguistic Approach to the View Update Problem
Recommendations
Boomerang: resourceful lenses for string data
POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesA lens is a bidirectional program. When read from left toright, it denotes an ordinary function that maps inputs to outputs. When read from right to left, it denotes an ''update translator'' that takes an input together with an updated output and ...
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 ...
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 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2015
52 pages
Copyright © 2015 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 December 2015
Published in SIGPLAN Volume 50, Issue 8S
Check for updates
Author Tags
Qualifiers
- Column
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 79Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)3
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in