Abstract
In many occasions would one encounter the task of maintaining the consistency of two pieces of structured data that are related by some transform — synchronising bookmarks in different web browsers, the source and the view in an editor, or views in databases, to name a few. This paper proposes a formal model of such tasks, basing on a programming language allowing injective functions only. The programmer designs the transformation as if she is writing a functional program, while the synchronisation behaviour is automatically derived by algebraic reasoning. The main advantage is being able to deal with duplication and structural changes. The result will be integrated to our structure XML editor in the Programmable Structured Document project.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abiteboul, S.: On views and XML. In: Proceedings of the 18th ACM SIGPLANSIGACT- SIGART Symposium on Principles of Database Systems, pp. 1–9. ACM Press, New York (1999)
Abramov, S.M., GIück, R.: The universal resolving algorithm and its correctness: inverse computation in a functional language. Science of Computer Programming 43, 193–299 (2002)
Altova Co. Xmlspy, http://www.xmlspy.com/products_ide.html
Backus, J.: Can programming be liberated from the von Neumann style? a functional style and its algebra of programs. Communications of the ACM 21(8), 613–641 (1978)
Bancilhon, F., Spyratos, N.: Update semantics of relational views. ACM Transactions on Database Systems 6(4), 557–575 (1981)
Bird, R.S., de Moor, O.: Algebra of Programming. International Series in Computer Science. Prentice-Hall, Englewood Cliffs (1997)
Dayal, U., Bernstein, P.A.: On the correct translation of update operations on relational views. ACM Transactions on Database Systems 7(3), 381–416 (1982)
GIück, R., Kawabe, M.: A program inverter for a functional language with equality and constructors. In: Ohori, A. (ed.) APLAS 2003. LNCS, vol. 2895, pp. 246–264. Springer, Heidelberg (2003)
Glück, R., Kawabe, M.: Derivation of deterministic inverse programs based on LR parsing (extended abstract). In: Kameyama, Y., Stuckey, P.J. (eds.) FLOPS 2004. LNCS, vol. 2998, pp. 291–306. Springer, Heidelberg (2004)
Gottlob, G., Paolini, P., Zicari, R.: Properties and update semantics of consistent views. ACM Transactions on Database Systems 13(4), 486–524 (1988)
Greenwald, M.B., Moore, J.T., Pierce, B.C., Schmitt, A.: A language for bi-directional tree transformations. Technical Report, MS-CIS-03-08, University of Pennsylvania (August 2003)
Meertens, L.: Designing constraint maintainers for user interaction (1998), ftp://ftp.kestrel.edu/pub/papers/meertens/dcm.ps
Mu, S.-C., Hu, Z., Takeichi, M.: An injective language for reversible computation. In: Kozen, D. (ed.) MPC 2004. LNCS, vol. 3125, pp. 289–313. Springer, Heidelberg (2004)
Ohori, A., Tajima, K.: A polymorphic calculus for views and object sharing. In: Proceedings of the 13th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 255–266. ACM Press, New York (1994)
Takeichi, M., Hu, Z., Kakehi, K., Hayashi, Y., Mu, S.-C., Nakano, K.: TreeCalc: towards programmable structured documents. In: The 20th Conference of Japan Society for Software Science and Technology (September 2003)
Wallace, M., Runciman, C.: Haskell and XML: generic combinators or typebased translation? In: Proceedings of the 1999 ACM SIGPLAN International Conference on Functional Programming, pp. 148–159. ACM Press, New York (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mu, SC., Hu, Z., Takeichi, M. (2004). An Algebraic Approach to Bi-directional Updating. In: Chin, WN. (eds) Programming Languages and Systems. APLAS 2004. Lecture Notes in Computer Science, vol 3302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30477-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-30477-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23724-2
Online ISBN: 978-3-540-30477-7
eBook Packages: Springer Book Archive