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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afrati, F.N., Gergatsoulis, M., Kavalieros, T.: Answering queries using materialized views with disjunctions. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 435–452. Springer, Heidelberg (1998)
Afrati, F., Li, C., Mitra, P.: Answering queries using views with arithmetic comparisons. In: PODS, pp. 209–220 (2002)
Afrati, F., Li, C., Mitra, P.: Rewriting queries using views in the presence of arithmetic comparisons. Technical report, UC Irvine (2002)
Afrati, F.N., Li, C., Mitra, P.: On containment of conjunctive queries with arithmetic comparisons. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 459–476. Springer, Heidelberg (2004)
Afrati, F., Li, C., Ullman, J.D.: Generating efficient plans for queries using views. In: SIGMOD, pp. 319–330 (2001)
Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC, pp. 77–90 (1977)
Deutsch, A.: XML Query Reformulation over Mixed and Redundant Storage. PhD thesis, University of Pennsylvania (2002)
Duschka, O.M., Genesereth, M.R.: Answering recursive queries using views. In: PODS, pp. 109–116 (1997)
Grahne, G., Mendelzon, A.O.: Tableau techniques for querying information sources through global schemas. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 332–347. Springer, Heidelberg (1998)
Gupta, A., Sagiv, Y., Ullman, J.D., Widom, J.: Constraint checking with partial information. In: PODS, pp. 45–55 (1994)
Halevy, A.Y.: Answering queries using views: A survey. VLDB Journal 10(4), 270–294 (2001)
Klug, A.: On conjunctive queries containing inequalities. Journal of the ACM 35(1), 146–160 (1988)
Kolaitis, P.G., Martin, D.L., Thakur, M.N.: On the complexity of the containment problem for conjunctive queries with built-in predicates. In: PODS, pp. 197–204 (1998)
Levy, A., Mendelzon, A.O., Sagiv, Y., Srivastava, D.: Answering queries using views. In: PODS, pp. 95–104 (1995)
Levy, A., Rajaraman, A., Ordille, J.J.: Querying heterogeneous information sources using source descriptions. In: VLDB, pp. 251–262 (1996)
Levy, A., Rajaraman, A., Ullman, J.: Answering queries using limited external processors. In: PODS, pp. 227–234 (1996)
Levy, A., Sagiv, Y.: Queries independent of updates. In: VLDB, pp. 171–181 (1993)
Mitra, P.: An algorithm for answering queries efficiently using views. In: Proceedings of the Australasian Database Conference, pp. 99–106 (2001)
Popa, L.: Object/Relational Query Optimization with Chase and Backchase. PhD thesis, University of Pennsylvania (2000)
Pottinger, R., Halevy, A.: A scalable algorithm for answering queries using views. VLDB Journal 10(2-3), 182–198 (2001)
Qian, X.: Query folding. In: ICDE, pp. 48–55 (1996)
Sagiv, Y., Yannakakis, M.: Equivalences among relational expressions with the union and difference operators. Journal of the ACM 27(4), 633–655 (1980)
Stockmeyer, L.J.: The polynomial-time hierarchy. Theoretical Computer Science 3, 1–22 (1977)
van der Meyden, R.: The complexity of querying indefinite data about linearly ordered domains. In: PODS, pp. 331–345 (1992)
Zhang, X., Ozsoyoglu, M.Z.: On efficient reasoning with implication constraints. In: DOOD, pp. 236–252 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Afrati, F., Chirkova, R., Gergatsoulis, M., Pavlaki, V. (2006). Finding Equivalent Rewritings in the Presence of Arithmetic Comparisons. In: Ioannidis, Y., et al. Advances in Database Technology - EDBT 2006. EDBT 2006. Lecture Notes in Computer Science, vol 3896. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11687238_55
Download citation
DOI: https://doi.org/10.1007/11687238_55
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32960-2
Online ISBN: 978-3-540-32961-9
eBook Packages: Computer ScienceComputer Science (R0)