Finding equivalent rewritings in the presence of arithmetic comparisons
Foto Afrati, Rada Chirkova, Manolis Gergatsoulis, Vassia Pavlaki
Abstract: The problem of rewriting queries using views has received
significant attention because of its applications in a wide variety of
data-management problems. For select-project-join SQL (a.k.a. conjunctive)
queries and views, there are efficient algorithms in the literature, which find
equivalent and maximally contained rewritings. In the presence of arithmetic
comparisons (ACs) the problem becomes more complex. We do not know how to find
maximally contained rewritings in the general case. There are algorithms which
find maximally contained rewritings only for special cases such as when ACs are
restricted to be semi-interval. However, we know that the problem of finding an
equivalent rewriting (if there exists one) in the presence of ACs is decidable,
yet still doubly exponential. This complexity calls for an efficient algorithm
which will perform better on average than the complete enumeration algorithm. In
this work we present such an algorithm which is sound and complete. Its
efficiency lies in that it considers fewer candidate rewritings because it
includes a preliminary test to decide for each view whether it is potentially
useful in some rewriting.
Keywords:
Data integration, query transformation, database theory.