| dc.identifier.uri | http://hdl.handle.net/11401/78238 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.type | Dissertation | |
| dcterms.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. | |
| dcterms.available | 2018-06-21T13:38:40Z | |
| dcterms.contributor | Liu, Yanhong A | en_US |
| dcterms.contributor | Kifer, Michael | en_US |
| dcterms.contributor | Stoller, Scott | en_US |
| dcterms.contributor | Warren, David | en_US |
| dcterms.contributor | Norvig, Peter | en_US |
| dcterms.creator | Brandvein, Jonathan Glenn | |
| dcterms.dateAccepted | 2018-06-21T13:38:40Z | |
| dcterms.dateSubmitted | 2018-06-21T13:38:40Z | |
| dcterms.description | Department of Computer Science | en_US |
| dcterms.extent | 183 pg. | en_US |
| dcterms.format | Application/PDF | en_US |
| dcterms.format | Monograph | |
| dcterms.identifier | http://hdl.handle.net/11401/78238 | |
| dcterms.issued | 2016-05-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2018-06-21T13:38:40Z (GMT). No. of bitstreams: 1
Brandvein_grad.sunysb_0771E_12880.pdf: 1465874 bytes, checksum: 13f359d8c129c47fe3a379bd949e46bb (MD5)
Previous issue date: 5 | en |
| dcterms.subject | Computer science | |
| dcterms.subject | Automatic Incrementalization | |
| dcterms.subject | Demand-driven Computation | |
| dcterms.subject | Invariant-based Transformation | |
| dcterms.subject | Object Queries | |
| dcterms.subject | Program Optimization | |
| dcterms.subject | Query Constructs | |
| dcterms.title | Demand-Driven Incremental Computation of Object Queries | |
| dcterms.type | Dissertation | |
