An Optimization Method for Skyline Query on Cache Model

Abstract:

This paper studies the equivalent reconstruction of the newly proposed skyline query using a group of existing skyline snapshots under the database cache model. We present a novel two phase algorithm for processing skyline query on cache model (APSQCM) to support this reconstruction. In the first phase, the APSQCM algorithm captures the inherent relationship between the newly proposed skyline query and the existing ones, and obtains all the skyline radixes which can be used to equivalently reconstruct the newly proposed skyline query. And in the second phase, the APSQCM algorithm produces the correct result of the newly proposed skyline query from the skyline radixes. Furthermore, we present detailed theoretical analyses and extensive experiments that demonstrate our method is both efficient and effective.

Key words:skyline query; cache model; equivalent rewriting; query optimization