{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:13:27Z","timestamp":1758273207711,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,4,1]],"date-time":"2005-04-01T00:00:00Z","timestamp":1112313600000},"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":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2005,4]]},"abstract":"<jats:p>\n            Query equivalence is investigated for disjunctive aggregate queries with negated subgoals, constants and comparisons. A full characterization of equivalence is given for the aggregation functions\n            <jats:italic>count, max, sum, prod, top2<\/jats:italic>\n            and\n            <jats:italic>parity<\/jats:italic>\n            . A related problem is that of determining, for a given natural number\n            <jats:italic>N<\/jats:italic>\n            , whether two given queries are equivalent over all databases with at most\n            <jats:italic>N<\/jats:italic>\n            constants. This problem is called\n            <jats:italic>bounded equivalence<\/jats:italic>\n            . A complete characterization of decidability of bounded equivalence is given. In particular, it is shown that this problem is decidable for all the above aggregation functions as well as for\n            <jats:italic>cntd<\/jats:italic>\n            (count distinct) and\n            <jats:italic>avg<\/jats:italic>\n            . For quasilinear queries (i.e., queries in which predicates that occur positively are not repeated), it is shown that equivalence can be decided in polynomial time for the aggregation functions\n            <jats:italic>count, max, sum, prty, prod, top2<\/jats:italic>\n            and\n            <jats:italic>avg<\/jats:italic>\n            . A similar result holds for\n            <jats:italic>cntd<\/jats:italic>\n            provided that a few additional conditions hold. The results are couched in terms of abstract characteristics of aggregation functions, and new proof techniques are used. Finally, the results above also imply that equivalence, under bag-set semantics, is decidable for nonaggregate queries with negation.\n          <\/jats:p>","DOI":"10.1145\/1055686.1055691","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"328-360","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Equivalences among aggregate queries with negation"],"prefix":"10.1145","volume":"6","author":[{"given":"Sara","family":"Cohen","sequence":"first","affiliation":[{"name":"Technion--Israel Institute of Technology, Haifa, Israel"}]},{"given":"Yehoshua","family":"Sagiv","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}]},{"given":"Werner","family":"Nutt","sequence":"additional","affiliation":[{"name":"Heriot-Watt University, Edinburgh, England"}]}],"member":"320","published-online":{"date-parts":[[2005,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.1145\/800105.803397"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153856"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375595"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303992"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303994"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-004-0101-y"},{"volume-title":"Proceedings of the 14th IEEE Symposium on Logic in Computer Science","author":"Hella L.","key":"e_1_2_1_8_1","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, Calif., 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, Calif., 35--44."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/211414.211419"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212042"},{"key":"e_1_2_1_11_1","unstructured":"Kreisel G. and Krivine J. L. 1967. Elements of Mathematical Logic: Model Theory. North Holland Amsterdam The Netherlands.  Kreisel G. and Krivine J. L. 1967. Elements of Mathematical Logic: Model Theory. North Holland Amsterdam The Netherlands."},{"key":"e_1_2_1_12_1","volume-title":"Eds","author":"Kuper G.","year":"2000","unstructured":"Kuper , G. , Libkin , L. , and Paredaens , J. , Eds . 2000 . Constraint Databases. Springer-Verlag , New York. Kuper, G., Libkin, L., and Paredaens, J., Eds. 2000. Constraint Databases. Springer-Verlag, New York."},{"volume-title":"Proceedings of the 19th International Conference on Very Large Data Bases","author":"Levy A.","key":"e_1_2_1_13_1","unstructured":"Levy , A. and Sagiv , Y . 1993. Queries independent of updates . In Proceedings of the 19th International Conference on Very Large Data Bases ( Dublin, Ireland). Morgan-Kaufmann, San Francisco, Calif., 171--181. Levy, A. and Sagiv, Y. 1993. Queries independent of updates. In Proceedings of the 19th International Conference on Very Large Data Bases (Dublin, Ireland). Morgan-Kaufmann, San Francisco, Calif., 171--181."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220207"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275512"},{"key":"e_1_2_1_16_1","unstructured":"Presburger M. 1927. \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen in welchem die Addition als einzige Operation hervortritt. In Comptes Rendus du Premier Congr\u00e8s des Math\u00e9maticiens des Pays Slaves (Warsaw Poland). 92--101.  Presburger M. 1927. \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen in welchem die Addition als einzige Operation hervortritt. In Comptes Rendus du Premier Congr\u00e8s des Math\u00e9maticiens des Pays Slaves (Warsaw Poland). 92--101."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"volume-title":"Principles of Database and Knowledge-Base Systems","author":"Ullman J. D.","key":"e_1_2_1_18_1","unstructured":"Ullman , J. D. 1988. Principles of Database and Knowledge-Base Systems . Vol. I . Computer Science Press , Rockville, Madison . Ullman, J. D. 1988. Principles of Database and Knowledge-Base Systems. Vol. I. Computer Science Press, Rockville, Madison."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137902"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1055686.1055691","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1055686.1055691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:28Z","timestamp":1750264288000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1055686.1055691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,4]]}},"alternative-id":["10.1145\/1055686.1055691"],"URL":"https:\/\/doi.org\/10.1145\/1055686.1055691","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2005,4]]},"assertion":[{"value":"2005-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}