Abstract
In this paper we study a problem motivated by the management of changes in databases. It turns out that several such change scenarios, e.g., the separately studied problems of view maintenance (propagation of data changes) and view adaptation (propagation of view definition changes) can be unified as instances of query reformulation using views provided that support for the relational difference operator exists in the context of query reformulation. Exact query reformulation using views in positive relational languages is well understood, and has a variety of applications in query optimization and data sharing. Unfortunately, most questions about queries become undecidable in the presence of difference (or negation), whether we use the foundational set semantics or the more practical bag semantics.
We present a new way of managing this difficulty by defining a novel semantics, ℤ-relations, where tuples are annotated with positive or negative integers. ℤ-relations conveniently represent data, insertions, and deletions in a uniform way, and can apply deletions with the union operator (deletions are tuples with negative counts). We show that under ℤ-semantics relational algebra () queries have a normal form consisting of a single difference of positive queries, and this leads to the decidability of their equivalence. We provide a sound and complete algorithm for reformulating queries, including queries with difference, over ℤ-relations. Additionally, we show how to support standard view maintenance and view adaptation over set or bag semantics, through an excursion into the ℤ-semantics setting. Our algorithm turns out to be sound and complete also for bag semantics, albeit necessarily only for a subclass of . This subclass turns out to be quite large and covers generously the applications of interest to us. We also show a subclass of where reformulation and evaluation under ℤ-semantics can be combined with duplicate elimination to obtain the answer under set semantics. We investigate related complexity questions, and we also extend our results to queries with built-in predicates.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Afrati, F., Pavlaki, V.: Rewriting queries using views with negation. AI Commun. 19, 229–237 (2006)
Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC (1977)
Chaudhuri, S., Krishnamurthy, R., Potamianos, S., Shim, K.: Optimizing queries with materialized views. In: ICDE (1995)
Chaudhuri, S., Vardi, M.Y.: Optimization of real conjunctive queries. In: PODS, pp. 59–70 (1993)
Cohen, S.: Containment of aggregate queries. SIGMOD Rec. 34(1), 77–85 (2005)
Cohen, S., Nutt, W., Sagiv, Y.: Rewriting queries with arbitrary aggregation functions using views. ACM Trans. Database Syst. 31(2), 672–715 (2006)
Cohen, S., Nutt, W., Sagiv, Y.: Deciding equivalences among conjunctive aggregate queries. J. ACM 54(2) (2007)
Cohen, S., Nutt, W., Serebrenik, A.: Rewriting aggregate queries using views. In: PODS (1999)
Cohen, S., Sagiv, Y., Nutt, W.: Equivalences among aggregate queries with negation. ACM Trans. Comput. Log. 6(2), 328–360 (2005)
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. McGraw-Hill/MIT Press, New York/Cambridge (1990)
Deutsch, A., Popa, L., Tannen, V.: Query reformulation with constraints. SIGMOD Rec. 35(1), 65–73 (2006)
Duschka, O.M., Genesereth, M.R.: Answering recursive queries using views. In: PODS (1997)
Graefe, G., McKenna, W.J.: The Volcano optimizer generator: extensibility and efficient search. In: ICDE (1993)
Green, T.J.: Containment of conjunctive queries on annotated relations. In: ICDT (2009)
Green, T.J., Ives, Z.G., Tannen, V.: Reconcilable differences. In: ICDT (2009)
Green, T.J., Karvounarakis, G., Ives, Z.G., Tannen, V.: Update exchange with mappings and provenance. In: VLDB (2007). Amended version available as Univ. of Pennsylvania report MS-CIS-07-26
Green, T.J., Karvounarakis, G., Tannen, V.: Provenance semirings. In: PODS (2007)
Gupta, A., Mumick, I.S., Rao, J., Ross, K.A.: Adapting materialized views after redefinitions: techniques and a performance study. Inf. Syst. 26(5), 323–362 (2001)
Gupta, A., Mumick, I.S., Subrahmanian, V.S.: Maintaining views incrementally. In: SIGMOD (1993)
Haas, L.M., Freytag, J.C., Lohman, G.M., Pirahesh, H.: Extensible query processing in Starburst. In: SIGMOD (1989)
Halevy, A.Y.: Answering queries using views: a survey. VLDB J. 10(4) (2001)
Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford University Press, London (2004)
Ioannidis, Y.E., Ramakrishnan, R.: Containment of conjunctive queries: beyond relations as sets. TODS 20(3), 288–324 (1995)
Jayram, T.S., Kolaitis, P.G., Vee, E.: The containment problem for real conjunctive queries with inequalities. In: PODS (2006)
Klop, J.W.: Handbook of Logic in Computer Science, vol. 2. Oxford University Press, London (1992), Chap. 1
Koch, C.: Incremental query evaluation in a ring of databases. In: PODS, pp. 87–98 (2010)
Levy, A.Y., Mendelzon, A.O., Sagiv, Y., Srivastava, D.: Answering queries using views. In: PODS (1995)
Levy, A.Y., Rajaraman, A., Ordille, J.J.: Querying heterogeneous information sources using source descriptions. In: VLDB (1996)
Lovász, L.: Operations with structures. Acta Math. Hung. 18(3–4), 321–328 (1967)
Mitra, P.: An algorithm for answering queries efficiently using views. In: Proceedings of the Australasian Database Conference (2001)
Pottinger, R., Levy, A.: A scalable algorithm for answering queries using views. In: VLDB (2000)
Raz, R., Shpilka, A.: Deterministic polynomial identity testing in non-commutative models. Comput. Complex. 14(1), 1–19 (2005)
Sagiv, Y., Yannakakis, M.: Equivalences among relational expressions with the union and difference operators. J. ACM 27(4), 633–655 (1980)
Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Access path selection in a relational database management system. In: SIGMOD (1979)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper [16] appeared in the Proceedings of the 12th International Conference on Database Theory (ACM International Conference Proceeding Series, 361 ACM 2009, ISBN 978-1-60558-423-2).
Our work has been supported by the National Science Foundation under grants IIS-0629846, IIS-0803524, IIS-0477972, IIS-0513778, and IIS-1050448.
Work of T. Green performed while at the University of Pennsylvania.
Rights and permissions
About this article
Cite this article
Green, T.J., Ives, Z.G. & Tannen, V. Reconcilable Differences. Theory Comput Syst 49, 460–488 (2011). https://doi.org/10.1007/s00224-011-9323-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-011-9323-x