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

File

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

Document Identifiers

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

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.

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

Author Details

Daco C. Harkes
Danny M. Groenewegen
Eelco Visser

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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact