Caching and incrementalisation in the java query language

ABSTRACT

Many contemporary object-oriented programming languages support first-class queries or comprehensions. These language extensions make it easier for programmers to write queries, but are generally implemented no more efficiently than the code using collections, iterators, and loops that they replace. Crucially, whenever a query is re-executed, it is recomputed from scratch. We describe a general approach to optimising queries over mutable objects: query results are cached, and those caches are incrementally maintained whenever the collections and objects underlying those queries are updated. We hope that the performance benefits of our optimisations may encourage more general adoption of first-class queries by object-oriented programmers.

REFERENCES

• 1: Umut A. Acar , Amal Ahmed , Matthias Blume, Imperative self-adjusting computation, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 2: G. Bierman, E. Meijer, and W. Schulte. The essence of data access in c!. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), volume 3586 of Lecture Notes in Computer Science, pages 287--311. Springer-Verlag, 2005.
• 3: Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991
• 4: Shigeru Chiba, A metaobject protocol for C++, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.285-299, October 15-19, 1995, Austin, Texas, United States
• 5: J. Darlington. Program transformation and synthesis: Present capabilities. Technical Report Res. Report 77/43, Dept. of Computing and Control, Imperial College of Science and Technology, London, 1977.
• 6: Marc Eisenstadt, My hairiest bug war stories, Communications of the ACM, v.40 n.4, p.30-37, April 1997 [doi>10.1145/248448.248456]
• 7: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 8: Simon F. Goldsmith , Robert O'Callahan , Alex Aiken, Relational queries over program traces, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 9: Timothy Griffin , Leonid Libkin, Incremental maintenance of views with duplicates, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.328-339, May 22-25, 1995, San Jose, California, United States
• 10: A. Gupta and I. S. Mumick. Maintenance of materialized views: Problems, techniques and applications. IEEE Quarterly Bulletin on Data Engineering; Special Issue on Materialized Views and Data Warehousing, 18(2):3--18, 1995.
• 11: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 12: Peter J. Haas , Jeffrey F. Naughton , Arun N. Swami, On the relative cost of sampling for join selectivity estimation, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.14-24, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182594]
• 13: Ken Hartness, Robocode: using games to teach artificial intelligence, Journal of Computing Sciences in Colleges, v.19 n.4, p.287-291, April 2004
• 14: Chanika Hobatr , Brian A. Malloy, The design of an OCL query-based debugger for C++, Proceedings of the 2001 ACM symposium on Applied computing, p.658-662, March 2001, Las Vegas, Nevada, United States [doi>10.1145/372202.372796]
• 15: Chanika Hobatr , Brian A. Malloy, Using OCL-queries for debugging C++, Proceedings of the 23rd International Conference on Software Engineering, p.839-840, May 12-19, 2001, Toronto, Ontario, Canada
• 16: J.--H. Hong and S.-B. Cho. Evolution of emergent behaviors for shooting game characters in robocode. In Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pages 634--638. IEEE Press, 2004.
• 17: Katia Hristova , Tom Rothamel , Yanhong A. Liu , Scott D. Stoller, Efficient type inference for secure information flow, Proceedings of the 2006 workshop on Programming languages and analysis for security, June 10-10, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134744.1134759]
• 18: Ki Yong Lee , Jin Hyun Son , Myoung Ho Kim, Efficient incremental view maintenance in data warehouses, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502644]
• 19: Raimondas Lencevicius , Urs Holzle , Ambuj Kumar Singh, Query-based debugging, University of California, Santa Barbara, 1999
• 20: R. Lencevicius. On-the-fly query-based debugging with examples. In Proceedings of the Workshop on Automated and Algorithmic Debugging (AADEBUG), 2000.
• 21: Raimondas Lencevicius , Urs Hölzle , Ambuj K. Singh, Query-based debugging of object-oriented programs, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.304-317, October 05-09, 1997, Atlanta, Georgia, United States
• 22: Raimondas Lencevicius , Urs Hölzle , Ambuj K. Singh, Dynamic Query-Based Debugging, Proceedings of the 13th European Conference on Object-Oriented Programming, p.135-160, June 14-18, 1999
• 23: Yanhong A. Liu , Scott D. Stoller, From datalog rules to efficient programs with time and space guarantees, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.172-183, August 27-29, 2003, Uppsala, Sweden [doi>10.1145/888251.888268]
• 24: Yanhong A. Liu , Scott D. Stoller , Michael Gorbovitski , Tom Rothamel , Yanni Ellen Liu, Incrementalization across object abstraction, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 25: Yanhong A. Liu , Scott D. Stoller , Ning Li , Tom Rothamel, Optimizing aggregate array computations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.1, p.91-125, January 2005 [doi>10.1145/1053468.1053471]
• 26: Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Static caching for incremental computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.546-585, May 1998 [doi>10.1145/291889.291895]
• 27: Michael Martin , Benjamin Livshits , Monica S. Lam, Finding application errors and security flaws using PQL: a program query language, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 28: Erik Meijer , Brian Beckman , Gavin Bierman, LINQ: reconciling object, relations and XML in the .NET framework, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142552]
• 29: Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992 [doi>10.1145/128762.128764]
• 30: Hiroaki Nakamura, Incremental computation of complex object queries, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.156-165, October 14-18, 2001, Tampa Bay, FL, USA
• 31: M. Nelson. Robocode, http://robocode.sourceforge.net, 2007.
• 32: Jackie O'Kelly , J. Paul Gibson, RoboCode & problem-based learning: a non-prescriptive approach to teaching programming, Proceedings of the 11th annual SIGCSE conference on Innovation and technology in computer science education, June 26-28, 2006, Bologna, Italy
• 33: Alex Potanin , James Noble , Robert Biddle, Checking ownership and confinement: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.7, p.671-687, June 2004 [doi>10.1002/cpe.v16:7]
• 34: Alex Potanin , James Noble , Robert Biddle, Snapshot Query-Based Debugging, Proceedings of the 2004 Australian Software Engineering Conference (ASWEC'04), p.251, April 13-16, 2004
• 35: G. Ramalingam , Thomas Reps, A categorized bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.502-510, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158710]
• 36: J. T. Schwartz , R. B. Dewar , E. Schonberg , E. Dubinsky, Programming with sets; an introduction to SETL, Springer-Verlag New York, Inc., New York, NY, 1986
• 37: Michael Steinbrunn , Guido Moerkotte , Alfons Kemper, Heuristic and randomized optimization for the join ordering problem, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.191-208, August 1997 [doi>10.1007/s007780050040]
• 38: Arun N. Swami , Balakrishna R. Iyer, A Polynomial Time Algorithm for Optimizing Join Queries, Proceedings of the Ninth International Conference on Data Engineering, p.345-354, April 19-23, 1993
• 39: D. Viswanathan , S. Liang, Java virtual machine profiler interface, IBM Systems Journal, v.39 n.1, p.82-95, January 2000
• 40: Jos Warmer , Anneke Kleppe, The object constraint language: precise modeling with UML, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 41: D. Willis, D. J. Pearce, and J. Noble. Efficient object querying for Java. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP), volume 4067 of Lecture Notes in Computer Science, pages 28--49. Springer-Verlag, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

General Terms:
Design, Languages, Performance

Keywords:
incrementalization, java, querying