J. Nathan Foster
Benjamin C. Pierce
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
Available for Download
pdf
a17-foster-apndx.pdf (231.5 KB)
Online appendix to designing mediation for context-aware applications. The appendix supports the information on article 17.
- Abiteboul, S., Cluet, S., and Milo, T. 1997. Correspondence and translation for heterogeneous data. In International Conference on Database Theory (ICDT). Delphi, Greece. Google Scholar
Digital Library
- Abiteboul, S., Cluet, S., and Milo, T. 1998. A logical view of structure files. VLDB J. 7, 2, 96--114. Google ScholarDigital Library
- Abiteboul, S., McHugh, J., Rys, M., Vassalos, V., and Wiener, J. L. 1998. Incremental maintenance for materialized views over semistructured data. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB). Google ScholarDigital Library
- Abramov, S. M. and Glück, R. 2000. The universal resolving algorithm: Inverse computation in a functional language. In Mathematics of Program Construction, R. Backhouse and J. N. Oliveira, Eds. Vol. 1837. Springer-Verlag, 187--212. Google ScholarDigital Library
- Abramov, S. M. and Glück, R. 2002. Principles of inverse computation and the universal resolving algorithm. In The Essence of Computation: Complexity, Analysis, Transformation, T. Mogensen, D. Schmidt, and I. H. Sudborough, Eds. Lecture Notes in Computer Science, vol. 2566. Springer-Verlag, 269--295. Google ScholarDigital Library
- Atzeni, P. and Torlone, R. 1996. Management of multiple models in an extensible database design tool. In Proceedings of the International Conference on Extending Database Technology (EDBT'96). Lecture Notes in Computer Science, vol. 1057. Google ScholarDigital Library
- Atzeni, P. and Torlone, R. 1997. MDM: A multiple-data model tool for the management of heterogeneous database schemes. In Proceedings of ACM SIGMOD, (Exhibition Section). 528--531. Google ScholarDigital Library
- Baker, H. G. 1992. NREVERSAL of fortune---the thermodynamics of garbage collection. In Proceedings of the International Workshop on Memory Management. St. Malo, France. Lecture Notes in Computer Science, vol. 637, Springer. Google ScholarDigital Library
- Bancilhon, F. and Spyratos, N. 1981. Update semantics of relational views. ACM Trans. Datab. Syst. 6, 4 (Dec.), 557--575. Google ScholarDigital Library
- Barsalou, T., Siambela, N., Keller, A. M., and Wiederhold, G. 1991. Updating relational databases through object-based views. In ACM SIGACT--SIGMOD--SIGART Symposium on Principles of Database Systems. Denver, CO, 248--257. Google ScholarDigital Library
- Bennet, C. H. 1973. Logical reversibility of computation. IBM J. Resear. Devel. 17, 6, 525--532.Google ScholarDigital Library
- Bohannon, A., Vaughan, J. A., and Pierce, B. C. 2006. Relational lenses: A language for updateable views. In Principles of Database Systems (PODS). Extended version Tech. rep. MS-CIS-05-27, University of Pennsylvania. Google ScholarDigital Library
- 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).Google Scholar
- Buneman, P., Khanna, S., and Tan, W.-C. 2002. On propagation of deletions and annotations through views. In ACM SIGACT--SIGMOD--SIGART Symposium on Principles of Database Systems. Medison, WI, 150--158. Google ScholarDigital Library
- Cosmadakis, S. S. 1983. Translating updates of relational data base views. M.S. thesis, MIT-LCS-TR-284. Massachusetts Institute of Technology. Google ScholarDigital Library
- Cosmadakis, S. S. and Papadimitriou, C. H. 1984. Updates of relational views. J. ACM 31, 4, 742--760. Google ScholarDigital Library
- Date, C. J. 2003. An Introduction to Database Systems, 8th Ed. Addison Wesley. Google ScholarDigital Library
- Dayal, U. and Bernstein, P. A. 1982. On the correct translation of update operations on relational views. ACM Trans. Datab. Syst. 7, 3 (Sept.), 381--416. Google ScholarDigital Library
- 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).Google Scholar
- Dijkstra, E. W. 1979. Program inversion. In Program Construction, International Summer School, July-August 1978. Marktoberdorf, Germany. F. L. Bauer and M. Broy, Eds. Lecture Notes in Computer Science, vol. 69. Springer. Google ScholarDigital Library
- Fogel, S. and Lane, P. 2005. Oracle Database Administrator's Guide. Oracle.Google Scholar
- Foster, J. N., Greenwald, M. B., Kirkegaard, C., Pierce, B. C., and Schmitt, A. 2006. Exploiting schemas in data synchronization. J. Comput. Syst. Sci. 73, 4, 669--689. Google ScholarDigital Library
- Foster, J. N., Pierce, B. C., and Schmitt, A. 2006. Harmony Programmer's Manual. Available at http://www.seas.upenn.edu/~harmony/.Google Scholar
- Gottlob, G., Paolini, P., and Zicari, R. 1988. Properties and update semantics of consistent views. ACM Trans. Datab. Syst. 13, 4, 486--524. Google ScholarDigital Library
- Hegner, S. J. 1990. Foundations of canonical update support for closed database views. In International Conference on Database Theory (ICDT). Paris, France. Springer-Verlag, Berlin, Germany, 422--436. Google ScholarDigital Library
- Hegner, S. J. 2004. An order-based theory of updates for closed database views. Ann. Mathemat. 40, 63--125. Google ScholarDigital Library
- Hofmann, M. and Pierce, B. 1995. Positive subtyping. In ACM SIGPLAN--SIGACT Symposium on Principles of Programming Languages (POPL). San Francisco, CA. 186--197. Full version in Inform. Computat. 126, 1 (April) 1996. Google ScholarDigital Library
- Hu, Z., Mu, S.-C., and Takeichi, M. 2004. A programmable editor for developing structured documents based on bi-directional transformations. In Partial Evaluation and Program Manipulation (PEPM). Google ScholarDigital Library
- International Business Machines Corporation. 2004. IBM DB2 Universal Database Administration Guide: Implementation.Google Scholar
- Johnson, M., Rosebrugh, R., and Dampney, C. N. G. 2001. View updates in a semantic data modelling paradigm. In Proceedings of the 12th Australasian Conference on Database Technologies (ADC'01). IEEE Computer Society, 29--36. Google ScholarDigital Library
- Keller, A. M. 1985. Algorithms for translating view updates to database updates for views involving selections, projections, and joins. In ACM SIGACT--SIGMOD Symposium on Principles of Database Systems. Portland, OR. Google ScholarDigital Library
- Keller, A. M. 1986. Choosing a view update translator by dialog at view definition time. In Proceedings of the International Conference on Very Large Database (VLDB'86). Google ScholarDigital Library
- 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). Google ScholarDigital Library
- Lechtenbörger, J. 2003. The impact of the constant complement approach towards view updating. In ACM SIGACT--SIGMOD--SIGART Symposium on Principles of Database Systems. San Diego, CA. ACM 49--55. Google ScholarDigital Library
- Lorentz, D. 2005. Oracle Database SQL Reference. Oracle.Google Scholar
- Masunaga, Y. 1984. A relational database view update translation mechanism. In Proceedings of the International Conference on Very Large Databases (VLDB'84). Google ScholarDigital Library
- Matsuoka, S., Takahashi, S., Kamada, T., and Yonezawa, A. 1992. A general framework for bidirectional translation between abstract and pictorial data. ACM Trans. Inform. Syst. 10, 4 (Oct.), 408--437. Google ScholarDigital Library
- 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.Google Scholar
- 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).Google Scholar
- Meertens, L. 1998. Designing constraint maintainers for user interaction. Manuscript. Available at ftp://ftp.kestrel.edu/pub/papers/meertens/dcm.ps.Google Scholar
- Microsoft 2005. Creating and Maintaining Databases. Microsoft.Google Scholar
- Miller, R. J., Hernandez, M. A., Haas, L. M., Yan, L., Ho, C. T. H., Fagin, R., and Popa, L. 2001. The clio project: Managing heterogeneity. SIGMOD Rec. 30, 1 (March), 78--83. Google ScholarDigital Library
- 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).Google Scholar
- 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).Google Scholar
- Niehren, J. and Podelski, A. 1993. Feature automata and recognizable sets of feature trees. In Theory and Practice of Software (TAPSOFT). 356--375. Google ScholarDigital Library
- Ohori, A. and Tajima, K. 1994. A polymorphic calculus for views and object sharing. In ACM SIGACT--SIGMOD--SIGART Symposium on Principles of Database Systems. Minneapolis, MN. Google ScholarDigital Library
- Oles, F. J. 1985. Type algebras, functor categories, and block structure. In Algebraic Methods in Semantics, M. Nivat and J. C. Reynolds, Eds. Cambrige University Press. Google ScholarDigital Library
- 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/.Google Scholar
- 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).Google Scholar
- 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.Google Scholar
- Rowe, L. and Schoens, K. A. 1979. Data abstractions, views, and updates in RIGEL. In ACM SIGMOD Symposium on Management of Data (SIGMOD). Boston, MA. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Tatarinov, I., Ives, Z. G., Halevy, A. Y., and Weld, D. S. 2001. Updating XML. In ACM SIGMOD Symposium on Management of Data (SIGMOD). Santa Barbara, CA. Google ScholarDigital Library
- Wadler, P. 1987. Views: A way for pattern matching to cohabit with data abstraction. In ACM Symposium on Principles of Programming Languages (POPL). Munich, Germany. Google ScholarDigital Library
- Winskel, G. 1993. The Formal Semantics of Programming Languages: An Introduction. MIT Press. Google ScholarDigital Library
- XQuery 2005. XQuery 1.0: An XML Query Language, W3C Working Draft. Available at http://www.w3.org/TR/xquery/.Google Scholar
Index Terms
- Combinators for bidirectional 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
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 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 ...
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