Abstract
We study containment and equivalence of (unions of) conjunctive queries on relations annotated with elements of a commutative semiring. Such relations and the semantics of positive relational queries on them were introduced in a recent paper as a generalization of set semantics, bag semantics, incomplete databases, and databases annotated with various kinds of provenance information. We obtain positive decidability results and complexity characterizations for databases with lineage, why-provenance, and provenance polynomial annotations, for both conjunctive queries and unions of conjunctive queries. At least one of these results is surprising given that provenance polynomial annotations seem “more expressive” than bag semantics and under the latter, containment of unions of conjunctive queries is known to be undecidable. The decision procedures rely on interesting variations on the notion of containment mappings. We also show that for any positive semiring (a very large class) and conjunctive queries without self-joins, equivalence is the same as isomorphism.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Antova, L., Koch, C., Olteanu, D.: From complete to incomplete information and back. In: SIGMOD (2007)
Bistarelli, S.: Semirings for Soft Constraint Solving and Programming. Springer, Berlin (2004)
Buneman, P., Cheney, J., Tan, W.-C., Vansummeren, S.: Curated databases. In: PODS (2008)
Buneman, P., Khanna, S., Tan, W.-C.: Why and where: A characterization of data provenance. In: ICDT (2001)
Buneman, P., Khanna, S., Tan, W.C.: On propagation of deletions and annotations through views. In: PODS (2002)
Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC, pp. 77–90 (1977)
Chaudhuri, S., Vardi, M.Y.: On the equivalence of recursive and nonrecursive datalog programs. In: PODS (1992)
Chaudhuri, S., Vardi, M.Y.: Optimization of real conjunctive queries. In: PODS (1993)
Cohen, S.: Containment of aggregate queries. SIGMOD Rec. 34(1), 77–85 (2005)
Cohen, S.: Equivalence of queries combining set and bag-set semantics. In: PODS (2006)
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)
Cui, Y., Widom, J., Wiener, J.L.: Tracing the lineage of view data in a warehousing environment. TODS, 25(2) (2000)
Foster, J.N., Green, T.J., Tannen, V.: Annotated XML: Queries and provenance. In: PODS (2008)
Fuhr, N., Rölleke, T.: A probabilistic relational algebra for the integration of information retrieval and database systems. TOIS 14(1), 32–66 (1997)
Grahne, G., Spyratos, N., Stamate, D.: Semantics and containment of queries with internal and external conjunctions. In: ICDT (1997)
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)
Green, T.J., Karvounarakis, G., Tannen, V.: Provenance semirings. In: PODS (2007)
Green, T.J., Tannen, V.: Models for incomplete and probabilistic information. In: IIDB, March 2006 (2006)
Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)
Imieliński, T., Witold Lipski, J.: Incomplete information in relational databases. J. ACM, 31(4) (1984)
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)
Köbler, J., Schöning, U., Torán, J.: The Graph Isomorphism Problem: its Structural Complexity. Birkhäuser, Basel (1993)
Lakshmanan, L.V.S., Shiri, N.: A parametric approach to deductive databases with uncertainty. IEEE Trans. Knowl. Data Eng. 13(4), 554–570 (2001)
Lovász, L.: Operations with structures. Acta Math. Hung. 18(3–4), 321–328 (1967)
Nutt, W., Sagiv, Y., Shurin, S.: Deciding equivalences among aggregate queries. In: PODS (1998)
Sagiv, Y., Yannakakis, M.: Equivalences among relational expressions with the union and difference operators. J. ACM 27(4), 633–655 (1980)
Sarma, A.D., Theobald, M., Widom, J.: Exploiting lineage for confidence computation in uncertain and probabilistic databases. In: ICDE (2008)
Senellart, P., Abiteboul, S.: On the complexity of managing probabilistic XML data. In: PODS (2007)
Shmueli, O.: Equivalence of datalog queries is undecidable. J. Logic Programming 15 (1993)
Tan, W.-C.: Containment of relational queries with annotation propagation. In: DBPL, September 2003 (2003)
Zimányi, E.: Query evaluation in probabilistic relational databases. TCS, 171(1–2) (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper [17] 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 was supported by the National Science Foundation under grants IIS-0447972, 0513778, and 0629846.
Work performed while at the University of Pennsylvania.
Rights and permissions
About this article
Cite this article
Green, T.J. Containment of Conjunctive Queries on Annotated Relations. Theory Comput Syst 49, 429–459 (2011). https://doi.org/10.1007/s00224-011-9327-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-011-9327-6