Type

Text

Type

Dissertation

Advisor

Kifer, Michael | Liu, Yanhong A | Stoller, Scott | Warren, David | Norvig, Peter

Date

2016-05-01

Keywords

Automatic Incrementalization | Computer science | Demand-driven Computation | Invariant-based Transformation | Object Queries | Program Optimization | Query Constructs

Department

Department of Computer Science

Language

en_US

Source

This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.

Identifier

http://hdl.handle.net/11401/78238

Publisher

The Graduate School, Stony Brook University: Stony Brook, NY.

Format

application/pdf

Abstract

Object queries are a powerful construct for writing clear and concise high-level code, but are difficult to implement efficiently. A programmer who is not satisfied with the performance of a straightforward implementation may craft an ad hoc low-level solution. However, this forfeits the productivity benefits that declarative queries bring. We present a novel static transformation for generating demand-driven incremental implementations of object queries. The queries may involve objects and sets that are arbitrarily nested, and may also use aggregate operators and nested queries. All possible updates are handled, even in the presence of aliasing, without requiring sophisticated runtime support. The method defines invariants for the query result and auxiliary values, and provides precise asymptotic bounds for running time and space usage. Different high-level choices in the selection of the demand strategy and join orders lead to different invariants and different time and space tradeoffs. Previous methods do not handle such expressive queries while obtaining precise cost bounds for the generated code. We demonstrate IncOQ, a prototype implementation of our method, and verify that the transformed programs conform to their predicted costs. We compare our method both analytically and experimentally with prior work and alternative approaches, and justify our formulation of demand. Finally, we show successful applications to queries from a variety of problem domains including distributed algorithms, access control, and approximate probabilistic inference. | 183 pages

Download

Share

COinS