Query Optimization through Cached Queries for Object-Oriented Query Language SBQL

摘要

We present a new approach to optimization of query languages using cached results of previously evaluated queries. It is based on the stack-based approach (SBA) and object-oriented query language SBQL, which assume description of semantics in the form of abstract implementation of query/ programming language constructs. Pragmatic universality of SBQL and its precise, formal operational semantics make it possible to investigate various crucial issues related to this kind of optimization, in particular, organization of the cache enabling fast retrieval of cached queries, decomposition of complex queries into smaller ones and query normalization enabling higher reuse of cached queries, development of fast method to recognize consistency of queries after database updates and development of methods of incremental altering of cached query results after database updates. This paper is focused on the issues concerning optimal and fast utilization of the result cache and on the elimination method devoted to detecting cached queries that become inconsistent after a database update.