Document Open Access Logo

IceDust: Incremental and Eventual Computation of Derived Values in Persistent Object Graphs

Authors Daco C. Harkes, Danny M. Groenewegen, Eelco Visser

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2016.11.pdf
  • Filesize: 0.7 MB
  • 26 pages

Document Identifiers

Author Details

Daco C. Harkes
Danny M. Groenewegen
Eelco Visser

Cite As Get BibTex

Daco C. Harkes, Danny M. Groenewegen, and Eelco Visser. IceDust: Incremental and Eventual Computation of Derived Values in Persistent Object Graphs. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 11:1-11:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ECOOP.2016.11

Abstract

Derived values are values calculated from base values. They can be
expressed in object-oriented languages by means of getters calculating the derived value, and in relational or logic databases by means of (materialized) views. However, switching to a different calculation strategy (for example caching) in object-oriented programming requires invasive code changes, and the databases limit expressiveness by disallowing recursive aggregation.

In this paper, we present IceDust, a data modeling language for
expressing derived attribute values without committing to a calculation strategy. IceDust provides three strategies for calculating derived values in persistent object graphs: Calculate-on-Read, Calculate-on-Write, and Calculate-Eventually. We have developed a path-based abstract interpretation that provides static dependency analysis to generate code for these strategies. Benchmarks show that different strategies perform better in different scenarios. In addition we have conducted a case study that suggests that derived value calculations of systems used in practice can be expressed in IceDust.

Subject Classification

Keywords
  • Incremental Computing
  • Data Modeling
  • Domain Specific Language

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Umut A. Acar. Self-adjusting computation: (an overview). In PEPM, pages 1-6, 2009. URL: http://dx.doi.org/10.1145/1480945.1480946.
  2. M. Akhtar Ali, Alvaro A. A. Fernandes, and Norman W. Paton. Movie: An incremental maintenance system for materialized object views. DKE, 47(2):131-166, 2003. URL: http://dx.doi.org/10.1016/S0169-023X(03)00048-X.
  3. Krzysztof R Apt, Howard A Blair, and Adrian Walker. Towards a theory of declarative knowledge. IBM Thomas J. Watson Research Division, 1986. Google Scholar
  4. Stephanie Balzer. Rumer: a Programming Language and Modular Verification Technique Based on Relationships. PhD thesis, ETH, Zürich, 2011. Google Scholar
  5. Gavin M. Bierman and Alisdair Wren. First-class relationships in an object-oriented language. In ECOOP, pages 262-286, 2005. URL: http://dx.doi.org/10.1007/11531142_12.
  6. Sebastian Burckhardt. Principles of eventual consistency. FTPL, 1(1-2):1-150, 2014. URL: http://dx.doi.org/10.1561/2500000011.
  7. Alan J. Demers, Thomas W. Reps, and Tim Teitelbaum. Incremental evaluation for attribute grammars with application to syntax-directed editors. In POPL, pages 105-116, 1981. URL: http://dx.doi.org/10.1145/567532.567544.
  8. Conal M. Elliott. Push-pull functional reactive programming. In haskell, pages 25-36, 2009. URL: http://dx.doi.org/10.1145/1596638.1596643.
  9. Theophilos Giannakopoulos, Daniel J. Dougherty, Kathi Fisler, and Shriram Krishnamurthi. Towards an operational semantics for alloy. In FM, pages 483-498, 2009. URL: http://dx.doi.org/10.1007/978-3-642-05089-3_31.
  10. Martin Glinz. Rethinking the notion of non-functional requirements. In WCSQ, pages 55-64, 2005. Google Scholar
  11. Dieter Gluche, Torsten Grust, Christof Mainberger, and Marc H. Scholl. Incremental updates for materialized oql views. In DOOD, pages 52-66, 1997. URL: http://dx.doi.org/10.1007/3-540-63792-3_8.
  12. Todd J. Green. Logiql: A declarative language for enterprise applications. In PODS, pages 59-64, 2015. URL: http://dx.doi.org/10.1145/2745754.2745780.
  13. Todd J. Green, Shan Shan Huang, Boon Thau Loo, and Wenchao Zhou. Datalog and recursive query processing. FTDB, 5(2):105-195, 2013. URL: http://dx.doi.org/10.1561/1900000017.
  14. Ashish Gupta and Inderpal Singh Mumick. Maintenance of materialized views: Problems, techniques, and applications. DEBU, 18(2):3-18, 1995. Google Scholar
  15. Ashish Gupta, Inderpal Singh Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In SIGMOD, pages 157-166, 1993. URL: http://dx.doi.org/10.1145/170035.170066.
  16. Munish Gupta. Akka essentials. Packt Publishing Ltd, 2012. Google Scholar
  17. Terry Halpin. Object-role modeling (orm/niam). In Handbook on architectures of information systems, pages 81-103. Springer, 2006. URL: http://dx.doi.org/10.1007/978-3-662-03526-9_4.
  18. Daco Harkes and Eelco Visser. Unifying and generalizing relations in role-based data modeling and navigation. In SLE, pages 241-260, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11245-9_14.
  19. Felienne Hermans, Martin Pinzger, and Arie van Deursen. Automatically extracting class diagrams from spreadsheets. In ECOOP, pages 52-75, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14107-2_4.
  20. Shan Shan Huang and Yannis Smaragdakis. Expressive and safe static reflection with morphj. In PLDI, pages 79-89, 2008. URL: http://dx.doi.org/10.1145/1375581.1375592.
  21. Daniel Jackson. Alloy: a lightweight object modelling notation. TOSEM, 11(2):256-290, 2002. URL: http://dx.doi.org/10.1145/505145.505149.
  22. Yanhong A Liu, Jon Brandvein, Scott D Stoller, and Bo Lin. Demand-driven incremental object queries. arXiv preprint arXiv:1511.04583, 2015. Google Scholar
  23. Ingo Maier and Martin Odersky. Higher-order reactive programming with incremental lists. In ECOOP, pages 707-731, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39038-8_29.
  24. Erik Meijer. Reactive extensions (rx): curing your asynchronous programming blues. In CUFP, page 11, 2010. URL: http://dx.doi.org/10.1145/1900160.1900173.
  25. Ralf Mitschke, Sebastian Erdweg, Mirko Köhler, Mira Mezini, and Guido Salvaneschi. i3ql: language-integrated live data views. In OOPSLA, pages 417-432, 2014. URL: http://dx.doi.org/10.1145/2660193.2660242.
  26. Inderpal Singh Mumick, Hamid Pirahesh, and Raghu Ramakrishnan. The magic of duplicates and aggregates. In VLDB, pages 264-277, 1990. Google Scholar
  27. H. Nilsson, A. Courtney, and J. Peterson. Functional reactive programming, continued. In Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, 2002. URL: http://dx.doi.org/10.1145/581690.581695.
  28. Raghu Ramakrishnan, Kenneth A. Ross, Divesh Srivastava, and S. Sudarshan. Efficient incremental evaluation of queries with aggregation. In SLP, pages 204-218, 1994. Google Scholar
  29. Kenneth A. Ross and Yehoshua Sagiv. Monotonic aggregation in deductive databases. In PODS, pages 114-126, 1992. URL: http://dx.doi.org/10.1145/137097.137852.
  30. Guido Salvaneschi, Gerold Hintz, and Mira Mezini. Rescala: bridging between object-oriented and functional style in reactive applications. In AOSD, pages 25-36, 2014. URL: http://dx.doi.org/10.1145/2577080.2577083.
  31. Emma Söderberg and Görel Hedin. Incremental evaluation of reference attribute grammars using dynamic dependency tracking. Technical Report 98, Lund University, 2012. Google Scholar
  32. Friedrich Steimann. Content over container: object-oriented programming with multiplicities. In OOPSLA, pages 173-186, 2013. URL: http://dx.doi.org/10.1145/2509578.2509582.
  33. Friedrich Steimann. None, one, many - what’s the difference, anyhow? In SNAPL, pages 294-308, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.SNAPL.2015.294.
  34. Gábor Szárnyas, Benedek Izsó, István Ráth, Dénes Harmath, Gábor Bergmann, and Dániel Varró. Incquery-d: A distributed incremental model query framework in the cloud. In MoDELS, pages 653-669, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11653-2_40.
  35. Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAMCOMP, 1(2):146-160, 1972. URL: http://dx.doi.org/10.1137/0201010.
  36. Eelco Visser. WebDSL: A case study in domain-specific language engineering. In GTTSE, pages 291-373, 2007. URL: http://dx.doi.org/10.1007/978-3-540-88643-3_7.
  37. Ben Wiedermann and William R. Cook. Extracting queries by static analysis of transparent persistence. In POPL, pages 199-210, 2007. URL: http://dx.doi.org/10.1145/1190216.1190248.
  38. Darren Willis, David J. Pearce, and James Noble. Efficient object querying for java. In ECOOP, pages 28-49, 2006. URL: http://dx.doi.org/10.1007/11785477_3.
  39. Darren Willis, David J. Pearce, and James Noble. Caching and incrementalisation in the java query language. In OOPSLA, pages 1-18, 2008. URL: http://dx.doi.org/10.1145/1449764.1449766.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact