The use of controlled redundancy in self-adaptive databases (temporaries, derived, packrat, r-tree, texture analysis)
Nabil N. Kamel · 1985
This thesis investigates a new approach for multiple query optimization in a centralized database. Given an arbitrary sequence of queries, it is shown that significant performance improvements can be obtained by considering the special statistical patterns inherent in the query stream and in the distribution of data. In order to realize these potential improvements, this thesis addresses the optimal management of redundant temporaries, called the Derived Data Base. The problem is approached in a self-adaptive fashion by periodically reorganizing the contents of the temporaries to suit the common usage patterns. This approach differs from batched query processing in that the queries are not known in advance. The approach taken to handle updates is to keep the main database always up to date and to optimally select the contents of the temporaries based on their update history. In addition, a system of differential files is kept to retain the changes made in the temporaries. In cases where users specify queries whose response sets exist only partially in the temporaries, the main database must be referenced. In such cases, two alternative access paths exist: (1) evaluate the entire query from the main database or (2) split the query into two parts and evaluate one from the main database while retrieving the other from the temporaries. To select the best alternative, an estimate of the number of tuples satisfying a given query is needed. To obtain such estimates, a data distribution model is proposed. The model is based on a discrete approximation of the data space and belongs to the class of nonparametric models. Using texture analysis techniques applied to the multi dimensional data space, it is proposed that a segmentation of this space be obtained as a means of obtaining a discrete approximation.