Rudi Horn
Skip Abstract Section
Skip Supplemental Material SectionAbstract
Lenses are a popular approach to bidirectional transformations, a generalisation of the view update problem in databases, in which we wish to make changes to source tables to effect a desired change on a view. However, perhaps surprisingly, lenses have seldom actually been used to implement updatable views in databases. Bohannon, Pierce and Vaughan proposed an approach to updatable views called relational lenses, but to the best of our knowledge this proposal has not been implemented or evaluated to date. We propose incremental relational lenses, that equip relational lenses with change-propagating semantics that map small changes to the view to (potentially) small changes to the source tables. We also present a language-integrated implementation of relational lenses and a detailed experimental evaluation, showing orders of magnitude improvement over the non-incremental approach. Our work shows that relational lenses can be used to support expressive and efficient view updates at the language level, without relying on updatable view support from the underlying database.
Supplemental Material
- Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison Wesley. Google Scholar
Digital Library
- Umut A. Acar, Guy E. Blelloch, and Robert Harper. 2006. Adaptive functional programming. ACM Trans. Program. Lang. Syst. 28, 6 (2006), 990ś1034. Google ScholarDigital Library
- Danel Ahman and Tarmo Uustalu. 2014. Coalgebraic Update Lenses. Electr. Notes Theor. Comput. Sci. 308 (2014), 25ś48. Google ScholarDigital Library
- François Bancilhon and Nicolas Spyratos. 1981. Update semantics of relational views. ACM Transactions on Database Systems (TODS) 6, 4 (1981), 557ś575. Google ScholarDigital Library
- Philip A. Bernstein, Marie Jacob, Jorge Pérez, Guillem Rull, and James F. Terwilliger. 2013. Incremental mapping compilation in an object-to-relational mapping system. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013. 1269ś1280. Google ScholarDigital Library
- Aaron Bohannon, Benjamin C Pierce, and Jeffrey A Vaughan. 2006a. Relational lenses: a language for updatable views. In Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART symposium on Principles of Database Systems. ACM, 338ś347. Google ScholarDigital Library
- Aaron Bohannon, Benjamin C Pierce, and Jeffrey A Vaughan. 2006b. Relational lenses: a language for updatable views. Technical Report MS-CIS-05-27. Department of Computer and Information Science, University of Pennsylvania.Google Scholar
- Peter Buneman, Sanjeev Khanna, and Wang-Chiew Tan. 2002. On Propagation of Deletions and Annotations Through Views. In PODS. 150ś158. Google ScholarDigital Library
- Yufei Cai, Paolo G. Giarrusso, Tillmann Rendel, and Klaus Ostermann. 2014. A theory of changes for higher-order languages: incrementalizing λ-calculi by static differentiation. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, Edinburgh, United Kingdom - June 09 - 11, 2014. 145ś155. Google ScholarDigital Library
- James Cheney, Sam Lindley, and Philip Wadler. 2013. A practical theory of language-integrated query. In Proceedings of the 18th ACM SIGPLAN international conference on Functional programming (ICFP ’13). ACM, New York, NY, USA, 403ś416. Google ScholarDigital Library
- Adam Chlipala. 2015. Ur/Web: A Simple Model for Programming the Web. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015, Mumbai, India, January 15-17, 2015. 153ś165. Google ScholarDigital Library
- Ezra Cooper, Sam Lindley, Philip Wadler, and Jeremy Yallop. 2006. Links: Web Programming Without Tiers. In Formal Methods for Components and Objects, 5th International Symposium, FMCO 2006, Amsterdam, The Netherlands, November 7-10, 2006, Revised Lectures. 266ś296. Google ScholarDigital Library
- George Copeland and David Maier. 1984. Making Smalltalk a database system. SIGMOD Rec. 14, 2 (1984). Google ScholarDigital Library
- C. J. Date. 2012. View updating and relational theory. O’Reilly.Google Scholar
- Umeshwar Dayal and Philip A Bernstein. 1982. On the correct translation of update operations on relational views. ACM Transactions on Database Systems (TODS) 7, 3 (1982), 381ś416. Google ScholarDigital Library
- Zinovy Diskin, Yingfei Xiong, and Krzysztof Czarnecki. 2011. From State- to Delta-Based Bidirectional Model Transformations: the Asymmetric Case. Journal of Object Technology 10 (2011), 6: 1ś25.Google ScholarCross Ref
- Leonidas Fegaras. 2010. Propagating updates through XML views using lineage tracing. In Proceedings of the 26th International Conference on Data Engineering, ICDE 2010, March 1-6, 2010, Long Beach, California, USA. 309ś320.Google ScholarCross Ref
- J Nathan Foster, Michael B Greenwald, Jonathan T Moore, Benjamin C Pierce, and Alan Schmitt. 2007. Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Transactions on Programming Languages and Systems (TOPLAS) 29, 3 (2007), 17. Google ScholarDigital Library
- Nate Foster, Kazutaka Matsuda, and Janis Voigtländer. 2010. Three Complementary Approaches to Bidirectional Programming. In Generic and Indexed Programming - International Spring School, SSGIP 2010, Oxford, UK, March 22-26, 2010, Revised Lectures. 1ś46. Google ScholarDigital Library
- Timothy Griffin, Leonid Libkin, and Howard Trickey. 1997. An Improved Algorithm for the Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 9, 3 (1997), 508ś511. Google ScholarDigital Library
- Ashish Gupta and Inderpal Singh Mumick. 1995. Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18, 2 (1995), 3ś18. http://sites.computer.org/debull/95JUN-CD.pdfGoogle Scholar
- Matthew A. Hammer, Yit Phang Khoo, Michael Hicks, and Jeffrey S. Foster. 2014. Adapton: composable, demand-driven incremental computation. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, Edinburgh, United Kingdom - June 09 - 11, 2014. 156ś166. Google ScholarDigital Library
- Melanie Herschel, Ralf Diestelkämper, and Houssem Ben Lahmar. 2017. A survey on provenance: What for? What form? What from? VLDB J. 26, 6 (2017), 881ś906. Google ScholarDigital Library
- Soichiro Hidaka, Zhenjiang Hu, Kazuhiro Inaba, Hiroyuki Kato, Kazutaka Matsuda, and Keisuke Nakano. 2010. Bidirectionalizing graph transformations. In Proceeding of the 15th ACM SIGPLAN international conference on Functional programming, ICFP 2010, Baltimore, Maryland, USA, September 27-29, 2010. 205ś216. Google ScholarDigital Library
- Martin Hofmann, Benjamin Pierce, and Daniel Wagner. 2011. Symmetric Lenses. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’11). ACM, New York, NY, USA, 371ś384. Google ScholarDigital Library
- Martin Hofmann, Benjamin Pierce, and Daniel Wagner. 2012. Edit Lenses. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’12). ACM, New York, NY, USA, 495ś508. Google ScholarDigital Library
- R. Horn, R. Perera, and J. Cheney. 2018. Incremental Relational Lenses. ArXiv e-prints (July 2018). arXiv: cs.PL/1807.01948Google Scholar
- Michael Johnson and Robert D. Rosebrugh. 2013. Delta Lenses and Opfibrations. ECEASST 57 (2013). http://journal.ub. tu-berlin.de/eceasst/article/view/875Google Scholar
- Hsiang-Shang Ko and Zhenjiang Hu. 2018. An axiomatic basis for bidirectional programming. PACMPL 2, POPL (2018), 41:1ś41:29. Google ScholarDigital Library
- Hsiang-Shang Ko, Tao Zan, and Zhenjiang Hu. 2016. BiGUL: A Formally Verified Core Language for Putback-based Bidirectional Programming. In Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM ’16). ACM, New York, NY, USA, 61ś72. Google ScholarDigital Library
- Christoph Koch. 2010. Incremental query evaluation in a ring of databases. In Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM, 87ś98. Google ScholarDigital Library
- Christoph Koch, Daniel Lupei, and Val Tannen. 2016. Incremental View Maintenance For Collection Programming. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016. 75ś90. Google ScholarDigital Library
- Michael Ley. 2009. DBLP: some lessons learned. Proceedings of the VLDB Endowment 2, 2 (2009), 1493ś1500. Google ScholarDigital Library
- Dongxi Liu, Zhenjiang Hu, and Masato Takeichi. 2007. Bidirectional interpretation of XQuery. In Proceedings of the 2007 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, 2007, Nice, France, January 15-16, 2007. 21ś30. Google ScholarDigital Library
- Erik Meijer, Brian Beckman, and Gavin M. Bierman. 2006. LINQ: Reconciling Object, Relations and XML in the .NET Framework. In SIGMOD. Google ScholarDigital Library
- Xiaolei Qian and Gio Wiederhold. 1991. Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3, 3 (1991), 337ś341. Google ScholarDigital Library
- Raghu Ramakrishnan and Johannes Gehrke. 2003. Database management systems (3. ed.). McGraw-Hill. Google ScholarDigital Library
- Ziv Scully and Adam Chlipala. 2017. A program optimization for automatic database result caching. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, January 18-20, 2017. 271ś284. http://dl.acm.org/citation.cfm?id=3009891 Google ScholarDigital Library
- Perdita Stevens. 2007. A Landscape of Bidirectional Model Transformations. GTTSE 5235 (2007), 408ś424.Google Scholar
- Don Syme. 2006. Leveraging .NET meta-programming components from F#: integrated queries and interoperable heterogeneous execution. In ML. Google ScholarDigital Library
- Alexander Ulrich and Torsten Grust. 2015. The Flatter, the Better: Query Compilation Based on the Flattening Transformation. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015. 1421ś1426. Google ScholarDigital Library
- Meng Wang, Jeremy Gibbons, and Nicolas Wu. 2011. Incremental updates for efficient bidirectional transformations. In Proceeding of the 16th ACM SIGPLAN international conference on Functional Programming, ICFP 2011, Tokyo, Japan, September 19-21, 2011. 392ś403. Google ScholarDigital Library
- Tao Zan, Li Liu, Hsiang-Shang Ko, and Zhenjiang Hu. 2016. Brul: A Putback-Based Bidirectional Transformation Library for Updatable Views. In Proceedings of the 5th International Workshop on Bidirectional Transformations, Bx 2016, co-located with The European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 8, 2016. 77ś89. http://ceur-ws.org/Vol-1571/paper_3.pdfGoogle Scholar
Index Terms
- Incremental relational lenses
Recommendations
Relational lenses: a language for updatable views
PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsWe propose a novel approach to the classical view update problem. The view update problem arises from the fact that modifications to a database view may not correspond uniquely to modifications on the underlying database; we need a means of determining ...
Verification of Relational Database Languages Codes Generated by ChatGPT
ASSE '23: Proceedings of the 2023 4th Asia Service Sciences and Software Engineering ConferenceThe potential of using large language model artificial intelligence systems to generate program codes for application development is significant. Database codes in SQL (Structured Query Language), which is the standard relational database language, can ...
Matching lenses: alignment and view update
ICFP '10Bidirectional programming languages are a practical approach to the view update problem. Programs in these languages, called lenses, define both a view and an update policy - i.e., every program can be read as a function mapping sources to views as well ...
Comments