Skip to main content
Springer Nature Link
Log in

Containment of Conjunctive Queries with Arithmetic Expressions

  • Conference paper
On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE (OTM 2005)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 3760))

  • 1260 Accesses

Abstract

We study the problem of query containment for conjunctive queries with arithmetic constraints (QWAE). Such queries arise naturally in conventional database applications, information integration, and cooperative information systems. Given two such queries Q 1 and Q 2, we propose an algorithm that decides the containment \(Q_2\sqsubseteq Q_1\). The proposed algorithm returns a QWAE Q 2′ obtained by rewriting Q 2′ such that \(Q_2'\sqsubseteq Q_2\). This provides partial answers to the QWAE Q 1, which would otherwise be discarded by existing standard or extended techniques for query containment.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Afrati, F., Li, C., Prasenjit, M.: Answering queries using views with arithmetic comparisons. In: PODS 2002: Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 209–220. ACM Press, New York (2002)

    Chapter  Google Scholar 

  2. Afrati, F., Li, C., Prasenjit, M.: 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)

    Chapter  Google Scholar 

  3. Michael, B., Leonid, L.: Safe constraint queries. In: Proc. ACM Symp. on Principles of Database Systems, pp. 99–108 (1998)

    Google Scholar 

  4. Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational databases. In: Proc. 9th Annual ACM Symp. on the Theory of Computing, pp. 77–90 (1977)

    Google Scholar 

  5. Chaudhuri, S., Krishnamurthy, R., Potamianos, S., Shim, K.: Optimizing queries with materialized views. In: Proc. IEEE Int. Conf. on Data Eng., pp. 190–200 (1995)

    Google Scholar 

  6. Gupta, A., Sagiv, Y., Ullman, J.D., Widom, J.: Constraint checking with partial information. In: Proc. of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Minneapolis, Minnesota, pp. 45–55 (1994)

    Google Scholar 

  7. Kiani, A., Shiri, N.: Answering queries in heterogenuous information systems. In: Proc. of ACM Workshop on Interoperability of Heterogeneous Information Systems, Bremen, Germany (November 4, 2005)

    Google Scholar 

  8. Klug, A.: On conjunctive queries containing inequalities. Journal of the ACM 35(1), 146–160 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  9. Levy, A.Y.: Answering queries using views: A survey. The VLDB Journal 10(4), 270–294 (2001)

    Article  Google Scholar 

  10. Levy, A.Y., Sagiv, Y.: Queries independent of updates. In: Proc. Int’l Conf. on Very Large Data Bases (VLDB), Dublin, Ireland, pp. 171–181 (1993)

    Google Scholar 

  11. Millstein, T., Levy, A., Friedman, M.: Query containment for data integration systems. J. Comput. Syst. Sci. 66(1), 20–39 (2003)

    Article  MATH  Google Scholar 

  12. Pottinger, R., Levy, A.Y.: A scalable algorithm for answering queries using views. The VLDB Journal, 484–495 (2000)

    Google Scholar 

  13. Qian, X.: Query folding. In: Proc. IEEE Int’l Conf. on Data Eng., New Orleans, LA (February 1996)

    Google Scholar 

  14. Sagiv, Y., Yannakakis, M.: Equivalence among relational expressions with the union and difference operators. Journal of the ACM 27(4), 633–655 (1981)

    Article  MathSciNet  Google Scholar 

  15. Ullman, J.D.: Information integration using logical views. Theoretical Computer Science 239(2), 189–210 (2000)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science & Software Engineering, Concordia University, Montreal, Quebec, Canada

    Ali Kiani & Nematollaah Shiri

Authors
  1. Ali Kiani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nematollaah Shiri
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. STARLab, Vrije Universiteit Brussel (VUB), Bldg G/10, Pleinlaan 2, 1050, Brussels, Belgium

    Robert Meersman

  2. School of Computer Science and Information Technology, RMIT University, Bld 10.10, 376-392 Swanston Street, 3001, Melbourne, VIC, Australia

    Zahir Tari

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kiani, A., Shiri, N. (2005). Containment of Conjunctive Queries with Arithmetic Expressions. In: Meersman, R., Tari, Z. (eds) On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE. OTM 2005. Lecture Notes in Computer Science, vol 3760. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11575771_28

Download citation

  • DOI: https://doi.org/10.1007/11575771_28

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-29736-9

  • Online ISBN: 978-3-540-32116-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation