{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T12:35:41Z","timestamp":1776083741595,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,4,1]],"date-time":"2007-04-01T00:00:00Z","timestamp":1175385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2007,4]]},"abstract":"<jats:p>Equivalence of aggregate queries is investigated for the class of conjunctive queries with comparisons and the aggregate operators count, count-distinct, min, max, and sum. Essentially, this class contains unnested SQL queries with the above aggregate operators, with a where clause consisting of a conjunction of comparisons, and without a having clause. The comparisons are either interpreted over a domain with a dense order (like the rationals) or with a discrete order (like the integers). Characterizations of equivalence differ for the two cases. For queries with either max or min, equivalence is characterized in terms of dominance mappings, which can be viewed as a generalization of containment mappings. For queries with the count-distinct operator, a sufficient condition for equivalence is given in terms of equivalence of conjunctive queries under set semantics. For some special cases, it is shown that this condition is also necessary. For conjunctive queries with comparisons but without aggregation, equivalence under bag-set semantics is characterized in terms of isomorphism. This characterization essentially remains the same also for queries with the count operator. Moreover, this characterization also applies to queries with the sum operator if the queries have either constants or comparisons, but not both. In the general case (i.e., both comparisons and constants), the characterization of the equivalence of queries with the sum operator is more elaborate. All the characterizations given in the paper are decidable in polynomial space.<\/jats:p>","DOI":"10.1145\/1219092.1219093","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"5","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":79,"title":["Deciding equivalences among conjunctive aggregate queries"],"prefix":"10.1145","volume":"54","author":[{"given":"Sara","family":"Cohen","sequence":"first","affiliation":[{"name":"Technion---Israel Institute of Technology, Haifa, Israel"}]},{"given":"Werner","family":"Nutt","sequence":"additional","affiliation":[{"name":"Free University of Bozen-Bolzano, Bozen, Italy"}]},{"given":"Yehoshua","family":"Sagiv","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}]}],"member":"320","published-online":{"date-parts":[[2007,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320112"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645917.672310"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 6th International Conference on Database Theory","volume":"1186","author":"Benedikt M.","unstructured":"Benedikt , M. , and Keisler , H . 1997. Expressive power of unary counters . In Proceedings of the 6th International Conference on Database Theory ( Delphi, Greece). F. Afrati and P. Kolaitis, Eds. Lecture Notes in Computer Science , vol. 1186 . Springer-Verlag, New York, 291--305. Benedikt, M., and Keisler, H. 1997. Expressive power of unary counters. In Proceedings of the 6th International Conference on Database Theory (Delphi, Greece). F. Afrati and P. Kolaitis, Eds. Lecture Notes in Computer Science, vol. 1186. Springer-Verlag, New York, 291--305."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303987"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning","author":"Calvanese D.","unstructured":"Calvanese , D. , De Giacomo , G. , Lenzerini , M. , and Vardi , M. Y . 2000. Containment of conjunctive regular path queries with inverse . In Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning ( Breckenridge, CO). A. G. Cohn, F. Giunchiglia, and B. Selman, Eds. Morgan-Kaufmann, San Francisco, CA. Calvanese, D., De Giacomo, G., Lenzerini, M., and Vardi, M. Y. 2000. Containment of conjunctive regular path queries with inverse. In Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning (Breckenridge, CO). A. G. Cohn, F. Giunchiglia, and B. Selman, Eds. Morgan-Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 8th International Workshop on Database Programming Languages","author":"Calvanese D.","unstructured":"Calvanese , D. , De Giacomo , G. , Lenzerini , M. , and Vardi , M. Y . 2001. View-based query answering and query containment over semistructured data . In Proceedings of the 8th International Workshop on Database Programming Languages ( Frascati, Italy). Springer-Verlag, New York, 40--61. Calvanese, D., De Giacomo, G., Lenzerini, M., and Vardi, M. Y. 2001. View-based query answering and query containment over semistructured data. In Proceedings of the 8th International Workshop on Database Programming Languages (Frascati, Italy). Springer-Verlag, New York, 40--61."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 9th International Conference on Database Theory","author":"Calvanese D.","unstructured":"Calvanese , D. , De Giacomo , G. , and Vardi , M. Y . 2003. Decidable containment of recursive queries . In Proceedings of the 9th International Conference on Database Theory ( Siena, Italy). Lecture Notes in Computer Science. Springer-Verlag, New York, 330--345. Calvanese, D., De Giacomo, G., and Vardi, M. Y. 2003. Decidable containment of recursive queries. In Proceedings of the 9th International Conference on Database Theory (Siena, Italy). Lecture Notes in Computer Science. Springer-Verlag, New York, 330--345."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/248603.248616"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 11th International Conference on Data Engineering","author":"Chaudhuri S.","unstructured":"Chaudhuri , S. , Krishnamurthy , S. , Potarnianos , S. , and Shim , K . 1995. Optimizing queries with materialized views . In Proceedings of the 11th International Conference on Data Engineering ( Taipei, China). P. S. Yu and A. Chen, Eds. IEEE Computer Society Press, Los Alamitos, CA. Chaudhuri, S., Krishnamurthy, S., Potarnianos, S., and Shim, K. 1995. Optimizing queries with materialized views. In Proceedings of the 11th International Conference on Data Engineering (Taipei, China). P. S. Yu and A. Chen, Eds. IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153856"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375595"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 9th International Conference on Database Theory","author":"Cohen S.","unstructured":"Cohen , S. , Nutt , W. , and Sagiv , Y . 2003. Containment of aggregate queries . In Proceedings of the 9th International Conference on Database Theory ( Siena, Italy). Lecture Notes in Computer Science. Springer-Verlag, New york. Cohen, S., Nutt, W., and Sagiv, Y. 2003. Containment of aggregate queries. In Proceedings of the 9th International Conference on Database Theory (Siena, Italy). Lecture Notes in Computer Science. Springer-Verlag, New york."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055686.1055691"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303992"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564699"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2835"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303994"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.536253"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/232616.232692"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 21st International Conference on Very Large Data Bases","author":"Gupta A.","unstructured":"Gupta , A. , Harinarayan , V. , and Quass , D . 1995. Aggregate query processing in data warehouses . In Proceedings of the 21st International Conference on Very Large Data Bases ( Zurich, Switzerland). Morgan-Kaufmann, San Francisco, CA. Gupta, A., Harinarayan, V., and Quass, D. 1995. Aggregate query processing in data warehouses. In Proceedings of the 21st International Conference on Very Large Data Bases (Zurich, Switzerland). Morgan-Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/310709"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 14th IEEE Symposium on Logic in Computer Science","author":"Hella L.","unstructured":"Hella , L. , Libkin , L. , Nurmonen , J. , and Wong , L . 1999. Logics with aggregate operators . In Proceedings of the 14th IEEE Symposium on Logic in Computer Science ( Trento, Italy). IEEE Computer Society Press, Los Alamitos, CA, 35--44. Hella, L., Libkin, L., Nurmonen, J., and Wong, L. 1999. Logics with aggregate operators. In Proceedings of the 14th IEEE Symposium on Logic in Computer Science (Trento, Italy). IEEE Computer Society Press, Los Alamitos, CA, 35--44."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/211414.211419"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212042"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322332"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153860"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502104"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220207"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 4th IEEE Workshop on Mobile Computing Systems and Applications","author":"Madden S.","unstructured":"Madden , S. , Szewczyk , R. , Franklin , M. J. , and Culler , D . 2002. Supporting aggregate queries over ad-hoc wireless sensor networks . In Proceedings of the 4th IEEE Workshop on Mobile Computing Systems and Applications ( Callicoon, NY). IEEE Computer Society Press, Los Alamitos, CA, 49--58. Madden, S., Szewczyk, R., Franklin, M. J., and Culler, D. 2002. Supporting aggregate queries over ad-hoc wireless sensor networks. In Proceedings of the 4th IEEE Workshop on Mobile Computing Systems and Applications (Callicoon, NY). IEEE Computer Society Press, Los Alamitos, CA, 49--58."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543623"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275512"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/32204.32219"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 7th International Conference on Database Theory","volume":"1540","author":"Popa L.","unstructured":"Popa , L. , and Tannen , V . 1999. An equational chase for path-conjunctive queries, constraints, and views . In Proceedings of the 7th International Conference on Database Theory ( Jerusalem, Israel). C. Beeri and P. Buneman, Eds. Lecture Notes in Computer Science , vol. 1540 . Springer-Verlag, New York, 39--57. Popa, L., and Tannen, V. 1999. An equational chase for path-conjunctive queries, constraints, and views. In Proceedings of the 7th International Conference on Database Theory (Jerusalem, Israel). C. Beeri and P. Buneman, Eds. Lecture Notes in Computer Science, vol. 1540. Springer-Verlag, New York, 39--57."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00011-X"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90032-6"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 22nd International Conference on Very Large Data Bases","author":"Srivastava D.","unstructured":"Srivastava , D. , Dar , S. , Jagadish , H. , and Levy , A . 1996. Answering queries with aggregation using views . In Proceedings of the 22nd International Conference on Very Large Data Bases ( Bombay, India). Morgan-Kaufmann, San Francisco, CA. Srivastava, D., Dar, S., Jagadish, H., and Levy, A. 1996. Answering queries with aggregation using views. In Proceedings of the 22nd International Conference on Very Large Data Bases (Bombay, India). Morgan-Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137902"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1219092.1219093","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1219092.1219093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:42Z","timestamp":1750278162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1219092.1219093"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,4]]}},"alternative-id":["10.1145\/1219092.1219093"],"URL":"https:\/\/doi.org\/10.1145\/1219092.1219093","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,4]]},"assertion":[{"value":"2007-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}