More Web Proxy on the site http://driver.im/

research-article

i3QL: language-integrated live data views

Authors:

Sebastian Erdweg,

Guido SalvaneschiAuthors Info & Claims

OOPSLA '14: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications

Pages 417 - 432

https://doi.org/10.1145/2660193.2660242

Published: 15 October 2014 Publication History

Abstract

An incremental computation updates its result based on a change to its input, which is often an order of magnitude faster than a recomputation from scratch. In particular, incrementalization can make expensive computations feasible for settings that require short feedback cycles, such as interactive systems, IDEs, or (soft) real-time systems.

This paper presents i3QL, a general-purpose programming language for specifying incremental computations. i3QL provides a declarative SQL-like syntax and is based on incremental versions of operators from relational algebra, enriched with support for general recursion. We integrated i3QL into Scala as a library, which enables programmers to use regular Scala code for non-incremental subcomputations of an i3QL query and to easily integrate incremental computations into larger software projects. To improve performance, i3QL optimizes user-defined queries by applying algebraic laws and partial evaluation. We describe the design and implementation of i3QL and its optimizations, demonstrate its applicability, and evaluate its performance.

Supplementary Material

ZIP File (i3ql-vm.ova.zip)

Download
2572.07 MB

References

[1]

U. A. Acar, G. E. Blelloch, M. Blume, R. Harper, and K. Tangwongsan. An experimental analysis of self-adjusting computation. ACM Trans. Program. Lang. Syst., 32(1):3:1--3:53, Nov. 2009.

Digital Library

[2]

P. Bhatotia, A. Wieder, R. Rodrigues, U. A. Acar, and R. Pasquin. Incoop: Mapreduce for incremental computations. In Proceedings of the 2nd ACM Symposium on Cloud Computing, SOCC '11, pages 7:1--7:14, New York, NY, USA, 2011. ACM.

Digital Library

[3]

J. A. Blakeley, N. Coburn, and P.-V. Larson. Updating derived relations: detecting irrelevant and autonomously computable updates. ACM Trans. Database Syst., 14(3):369--400, Sept. 1989.

Digital Library

[4]

J. A. Blakeley, P.-A. Larson, and F. W. Tompa. Efficiently updating materialized views. SIGMOD Rec., 15(2):61--71, June 1986.

Digital Library

[5]

S. Ceri and J. Widom. Deriving production rules for incremental view maintenance. In Proceedings of the 17th International Conference on Very Large Data Bases, VLDB '91, pages 577--589, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc.

Digital Library

[6]

S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim. Optimizing queries with materialized views. In Data Engineering, 1995. Proceedings of the Eleventh International Conference on, pages 190--200, mar 1995.

Digital Library

[7]

N. Chomsky. Three models for the description of language. Information Theory, IRE Transactions on, 2(3):113--124, September 1956.

[8]

G. Cooper and S. Krishnamurthi. Embedding dynamic dataflow in a call-by-value language. In P. Sestoft, editor, Programming Languages and Systems, volume 3924 of Lecture Notes in Computer Science, pages 294--308. Springer Berlin Heidelberg, 2006.

Digital Library

[9]

C. Demetrescu, I. Finocchi, and A. Ribichini. Reactive imperative programming with dataflow constraints. In Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications, OOPSLA '11, pages 407--426, New York, NY, USA, 2011. ACM.

Digital Library

[10]

M. Eichberg, M. Kahl, D. Saha, M. Mezini, and K. Ostermann. Automatic incrementalization of prolog based static analyses. In Proceedings of the 9th International Conference on Practical Aspects of Declarative Languages, PADL'07, pages 109--123, Berlin, Heidelberg, 2007. Springer-Verlag.

Digital Library

[11]

B. N. Freeman-Benson. Kaleidoscope: Mixing objects, constraints, and imperative programming. In Proceedings of the European Conference on Object-oriented Programming on Object-oriented Programming Systems, Languages, and Applications, OOPSLA/ECOOP '90, pages 77--88, New York, NY, USA, 1990. ACM.

Digital Library

[12]

M. Garcia, A. Izmaylova, and S. Schupp. Extending Scala with database query capability. Journal of Object Technology, 9(4):45--68, 2010.

[13]

P. G. Giarrusso, K. Ostermann, M. Eichberg, R. Mitschke, T. Rendel, and C. Kästner. Reify your collection queries for modularity and speed! In Proceedings of the 12th Annual International Conference on Aspect-oriented Software Development, AOSD '13, pages 1--12, New York, NY, USA, 2013. ACM.

Digital Library

[14]

P. M. D. Gray, L. Kerschberg, P. J. H. King, and A. Poulovassilis. The Functional Approach to Data Management: Modeling, Analyzing and Integrating Heterogeneous Data. Springer Publishing Company, Incorporated, 1st edition, 2010.

Digital Library

[15]

T. Grust, M. Mayr, J. Rittinger, and T. Schreiber. Ferry: database-supported program execution. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, SIGMOD '09, pages 1063--1066, New York, NY, USA, 2009. ACM.

Digital Library

[16]

A. Gupta and I. Mumick. Materialized Views: Techniques, Implementations, and Applications. MIT Press, 1999.

Digital Library

[17]

A. Gupta, I. S. Mumick, and K. A. Ross. Adapting materialized views after redefinitions. SIGMOD Rec., 24(2):211--222, May 1995.

Digital Library

[18]

A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proceedings of the 1993 ACM SIGMOD international conference on Management of data, SIGMOD '93, pages 157--166, New York, NY, USA, 1993. ACM.

Digital Library

[19]

D. Hovemeyer and W. Pugh. Finding bugs is easy. SIGPLAN Not., 39(12):92--106, Dec. 2004.

Digital Library

[20]

P. Hudak. Modular domain specific languages and tools. In Proceedings of International Conference on Software Reuse (ICSR), pages 134--142. IEEE, 1998.

Digital Library

[21]

M. Kay. Readings in natural language processing. chapter Algorithm schemata and data structures in syntactic processing, pages 35--70. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1986.

Digital Library

[22]

D. Leijen and E. Meijer. Domain specific embedded compilers. In Proceedings of the 2nd conference on Domain-specific languages, DSL '99, pages 109--122, New York, NY, USA, 1999. ACM.

Digital Library

[23]

V. Lifschitz. Principles of knowledge representation. chapter Foundations of Logic Programming, pages 69--127. Center for the Study of Language and Information, Stanford, CA, USA, 1996.

Digital Library

[24]

Y. A. Liu, S. D. Stoller, M. Gorbovitski, T. Rothamel, and Y. E. Liu. Incrementalization across object abstraction. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA '05, pages 473--486, New York, NY, USA, 2005. ACM.

Digital Library

[25]

LiveLinq Web site. http://www.componentone.com/SuperProducts/LiveLinq/.

[26]

I. Maier and M. Odersky. Higher-order reactive programming with incremental lists. In Proceedings of the 27th European conference on Object-Oriented Programming, ECOOP'13, pages 707--731, Berlin, Heidelberg, 2013. Springer-Verlag.

Digital Library

[27]

S. Melnik, A. Adya, and P. A. Bernstein. Compiling mappings to bridge applications and databases. ACM Trans. Database Syst., 33(4):22:1--22:50, Dec. 2008.

Digital Library

[28]

L. A. Meyerovich, A. Guha, J. Baskin, G. H. Cooper, M. Greenberg, A. Bromfield, and S. Krishnamurthi. Flapjax: A programming language for Ajax applications. SIGPLAN Not., 44(10):1--20, Oct. 2009.

Digital Library

[29]

R. Mitschke, M. Eichberg, M. Mezini, A. Garcia, and I. Macia. Modular specification and checking of structural dependencies. In Proceedings of the 12th Annual International Conference on Aspect-oriented Software Development, AOSD '13, pages 85--96, New York, NY, USA, 2013. ACM.

Digital Library

[30]

B. A. Myers, R. G. McDaniel, R. C. Miller, A. S. Ferrency, A. Faulring, B. D. Kyle, A. Mickish, A. Klimovitski, and P. Doane. The Amulet environment: New models for effective user interface software development. IEEE Trans. Softw. Eng., 23(6):347--365, 1997.

Digital Library

[31]

V. Nerella, S. Surapaneni, S. Madria, and T. Weigert. Exploring optimization and caching for efficient collection operations. Automated Software Engineering, 21(1):3--40, 2014.

Digital Library

[32]

R. Paige. Applications of finite differencing to database integrity control and query/transaction optimization. In Advances in Data Base Theory, pages 171--209, 1982.

[33]

T. Palpanas, R. Sidle, R. Cochrane, and H. Pirahesh. Incremental maintenance for non-distributive aggregate functions. In Proceedings of the 28th international conference on Very Large Data Bases, VLDB '02, pages 802--813. VLDB Endowment, 2002.

Digital Library

[34]

F. Pfenning and C. Elliot. Higher-order abstract syntax. SIGPLAN Not., 23(7):199--208, June 1988.

Digital Library

[35]

X. Qian and G.Wiederhold. Incremental recomputation of active relational expressions. IEEE Transactions on Knowledge and Data Engineering, 3(3):337--341, 1991.

Digital Library

[36]

G. Ramalingam and T. Reps. A categorized bibliography on incremental computation. In Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '93, pages 502--510, New York, NY, USA, 1993. ACM.

Digital Library

[37]

T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled dsls. SIGPLAN Not., 46(2):127--136, Oct. 2010.

Digital Library

[38]

T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled dsls. Commun. ACM, 55(6):121--130, 2012.

Digital Library

[39]

T. Rothamel and Y. A. Liu. Generating incremental implementations of object-set queries. In Proceedings of the 7th International Conference on Generative Programming and Component Engineering, GPCE '08, pages 55--66, New York, NY, USA, 2008. ACM.

Digital Library

[40]

N. Roussopoulos. An incremental access method for view-cache: concept, algorithms, and cost analysis. ACM Trans. Database Syst., 16(3):535--563, Sept. 1991.

Digital Library

[41]

K. Sagonas, T. Swift, and D. S. Warren. Xsb as an efficient deductive database engine. SIGMOD Rec., 23(2):442--453, May 1994.

Digital Library

[42]

D. Saha and C. Ramakrishnan. Incremental evaluation of tabled logic programs. In C. Palamidessi, editor, Logic Programming, volume 2916 of Lecture Notes in Computer Science, pages 392--406. Springer Berlin Heidelberg, 2003.

[43]

D. Saha and C. Ramakrishnan. Symbolic support graph: A space efficient data structure for incremental tabled evaluation. In M. Gabbrielli and G. Gupta, editors, Logic Programming, volume 3668 of Lecture Notes in Computer Science, pages 235--249. Springer Berlin Heidelberg, 2005.

Digital Library

[44]

G. Salvaneschi, G. Hintz, and M. Mezini. REScala: Bridging between object-oriented and functional style in reactive applications. In Proceedings of the 13th International Conference on Modularity, MODULARITY '14, pages 25--36, New York, NY, USA, 2014. ACM.

Digital Library

[45]

A. Shankar and R. Bodík. Ditto: automatic incrementalization of data structure invariant checks (in Java). In Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, PLDI '07, pages 310--319, New York, NY, USA, 2007. ACM.

Digital Library

[46]

O. Shmueli and A. Itai. Maintenance of views. In Proceedings of the 1984 ACM SIGMOD international conference on Management of data, SIGMOD '84, pages 240--255, New York, NY, USA, 1984. ACM.

Digital Library

[47]

O. Sumer, U. Acar, A. T. Ihler, and R. R. Mettu. Efficient bayesian inference for dynamically changing graphs. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 1441--1448. MIT Press, Cambridge, MA, 2008.

[48]

J. D. Ullman, H. Garcia-Molina, and J. Widom. Database Systems: The Complete Book. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1st edition, 2001.

Digital Library

[49]

G.Wachsmuth, G. D. P. Konat, V. A. Vergu, D. M. Groenewegen, and E. Visser. A language independent task engine for incremental name and type analysis. In SLE, volume 8225 of Lecture Notes in Computer Science, pages 260--280. Springer, 2013.

[50]

T. A. Wagner and S. L. Graham. Efficient and flexible incremental parsing. ACM Trans. Program. Lang. Syst., 20(5):980--1013, Sept. 1998.

Digital Library

[51]

D.Willis, D. J. Pearce, and J. Noble. Efficient object querying for Java. In Proceedings of the 20th European conference on Object-Oriented Programming, ECOOP'06, pages 28--49, Berlin, Heidelberg, 2006. Springer-Verlag.

Digital Library

[52]

D. Willis, D. J. Pearce, and J. Noble. Caching and incrementalisation in the Java query language. SIGPLAN Not., 43(10):1--18, Oct. 2008.

Digital Library

[53]

L. Wong. Kleisli, a functional query system. Journal of Functional Programming, 10:19--56, 0 2000.

Digital Library

Cited By

Szabó TChandra SBlincoe KTonella P(2023)Incrementalizing Production CodeQL AnalysesProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3613860(1716-1726)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3613860
Pacak ASzabó TErdweg SScholz BKameyama Y(2022)Incremental Processing of Structured Data in DatalogProceedings of the 21st ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3564719.3568686(20-32)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3564719.3568686
Dexter PLiu YChiu K(2022)The essence of online data processingProceedings of the ACM on Programming Languages10.1145/35633206:OOPSLA2(899-928)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563320
Show More Cited By

Index Terms

i3QL: language-integrated live data views
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

i3QL: language-integrated live data views
OOPSLA '14

An incremental computation updates its result based on a change to its input, which is often an order of magnitude faster than a recomputation from scratch. In particular, incrementalization can make expensive computations feasible for settings that ...
Efficiency by Incrementalization: An Introduction

Incremental computation takes advantage of repeated computations on inputs that differ slightly from one another, computing each output efficiently by exploiting the previous output. This paper gives an overview of a general and systematic approach to ...
Incremental computation of nested relational query expressions

Efficient algorithms for incrementally computing nested query expressions do not exist. Nested query expressions are query expressions in which selection/join predicates contain subqueries. In order to respond to this problem, we propose a two-step ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '14: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications

October 2014

946 pages

ISBN:9781450325851

DOI:10.1145/2660193

General Chair:
Andrew Black
Portland State University, USA
,
Program Chair:
Todd Millstein
University of California, Los Angeles, USA

ACM SIGPLAN Notices Volume 49, Issue 10
OOPSLA '14
October 2014
907 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2714064
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGAda: ACM Special Interest Group on Ada Programming Language

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 October 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SPLASH '14

Sponsor:

SIGPLAN

SPLASH '14: Conference on Systems, Programming, and Applications: Software for Humanity

October 20 - 24, 2014

Oregon, Portland, USA

Acceptance Rates

OOPSLA '14 Paper Acceptance Rate 52 of 186 submissions, 28%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
288
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Szabó TChandra SBlincoe KTonella P(2023)Incrementalizing Production CodeQL AnalysesProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3613860(1716-1726)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3613860
Pacak ASzabó TErdweg SScholz BKameyama Y(2022)Incremental Processing of Structured Data in DatalogProceedings of the 21st ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3564719.3568686(20-32)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3564719.3568686
Dexter PLiu YChiu K(2022)The essence of online data processingProceedings of the ACM on Programming Languages10.1145/35633206:OOPSLA2(899-928)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563320
Salvaneschi GKöhler MSokolowski DHaller PErdweg SMezini M(2019)Language-integrated privacy-aware distributed queriesProceedings of the ACM on Programming Languages10.1145/33605933:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360593
Szabó TBergmann GErdweg SVoelter M(2018)Incrementalizing lattice-based program analyses in DatalogProceedings of the ACM on Programming Languages10.1145/32765092:OOPSLA(1-29)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276509
Weisenburger PLuthra MKoldehofe BSalvaneschi GGarlan DNuseibeh B(2017)Quality-aware runtime adaptation in complex event processingProceedings of the 12th International Symposium on Software Engineering for Adaptive and Self-Managing Systems10.1109/SEAMS.2017.10(140-151)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1109/SEAMS.2017.10
Szabó TErdweg SVoelter MLo DApel SKhurshid S(2016)IncA: a DSL for the definition of incremental program analysesProceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering10.1145/2970276.2970298(320-331)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2970276.2970298
Liu YBrandvein JStoller SLin BCheney JVidal G(2016)Demand-driven incremental object queriesProceedings of the 18th International Symposium on Principles and Practice of Declarative Programming10.1145/2967973.2968610(228-241)Online publication date: 5-Sep-2016
https://dl.acm.org/doi/10.1145/2967973.2968610
Hammer MDunfield JHeadley KLabich NFoster JHicks MVan Horn D(2015)Incremental computation with namesACM SIGPLAN Notices10.1145/2858965.281430550:10(748-766)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814305
Erdweg SBračevac OKuci EKrebs MMezini M(2015)A co-contextual formulation of type rules and its application to incremental type checkingACM SIGPLAN Notices10.1145/2858965.281427750:10(880-897)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814277
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents