Exploiting Order Dependencies on Primary Keys for Optimization
Michał Chromiak, Piotr Wiśniewski, Krzysztof Stencel · 2014
Abstract. Functional dependencies have been used in query optimisa-tion for decades. Moreover, if two domains have a natural ordering of their elements, a functional dependency of them can potentially preserve these orderings, i.e. be a monotonic function. This monotonicity can be exploited by query optimizers. Recently, such monotonic functional de-pendencies have been termed order dependencies. In this paper we propose a query rewriting method based on order depen-dencies on primary keys. If an attribute used in the WHERE clause has an order dependency on the primary key, such a selection can be replaced by the corresponding condition on the primary key. We have implemented this optimisation method in the integration framework called the cuboid. It automates the integration of disparate databases according to the CQS model. Cuboids facilitate injecting dependencies and utilizing them in query optimization. 1