A Bucket-Based Approach to Query Rewriting Using Views in the Presence of Inclusion Dependencies*
Qingyuan Bai, Jun Sik Hong, Michael McTear, Hui Wang · 2008
A number of algorithms based on the use of either buckets or inverse rules have been proposed to address the problem of query rewriting using views. Some inverse rule-based algorithms have considered this problem in the presence of inclusion dependencies. However, no bucket-based algorithms have considered the influence from inclusion dependencies, resulting in missing some query rewritings under this condition. In a bucket-based algorithm, if a view does not contain any subgoals of a query, then the algorithm cannot form any bucket over the view. In this paper, we utilize inclusion dependencies to overcome this deficiency. We present two novel algorithms in the buckets framework. In the first algorithm, we apply a chase procedure/rule to a query to get a set of equivalent or contained queries relative to inclusion dependencies, and then generate rewritings for each of the revised queries. In the second algorithm, we apply a chase procedure/rule to such a view that does not contain subgoals of a query but still contains subgoals to which the chase procedure/rule can be applied. We prove that both algorithms can find a maximally-contained rewriting relative to inclusion dependencies. Hence, the problem of missing rewritings in the previous bucket-based algorithms is avoided. ACM Classification: H.2.4 (Information Systems): Systems—query processing; H.2.5 (Information Systems): Heterogeneous Databases 1.