Abstract

Many useful programs operate on collection types. Extensive libraries are available in many programming languages, such as the C++ Standard Template Library, which make programming with collections convenient. Extending programming languages to provide collection queries as first class constructs in the language would not only allow programmers to write queries explicitly in their programs but it would also allow compilers to leverage the wealth of experience available from the database domain to optimize such queries. This paper describes an approach to reducing the run time of programs involving explicit collection queries by leveraging a cache to store previously computed results. We propose caching the results of join (sub)queries which allows queries that miss the cache entirely to be answered partially from the cache thereby improving the query execution time. We also describe an effective cache policy to determine which join (sub)queries to cache. the cache is maintained incrementally, when the underlying collections change, and use of the cache space is optimized by a cache replacement policy. © 2011 IEEE.

Department(s)

Computer Science

Keywords and Phrases

Cache Policy; Join caching; Run-time; Selectivity

International Standard Book Number (ISBN)

978-145771639-3

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 Institute of Electrical and Electronics Engineers, All rights reserved.

Publication Date

01 Dec 2011

Download

Full Text Link

Share

 
COinS