{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:06:31Z","timestamp":1765231591784,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"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":[[2005,1]]},"abstract":"<jats:p>Though extensions to the relational data model have been proposed in order to handle probabilistic information, there has been very little work to date on handling aggregate operators in such databases. In this article, we present a very general notion of an aggregate operator and show how classical aggregation operators (such as COUNT, SUM, etc.) as well as statistical operators (such as percentiles, variance, etc.) are special cases of this general definition. We devise a formal linear programming based semantics for computing aggregates over probabilistic DBMSs, develop algorithms that satisfy this semantics, analyze their complexity, and introduce several families of approximation algorithms that run in polynomial time. We implemented all of these algorithms and tested them on a large set of data to help determine when each one is preferable.<\/jats:p>","DOI":"10.1145\/1044731.1044734","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"54-101","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":56,"title":["Aggregate operators in probabilistic databases"],"prefix":"10.1145","volume":"52","author":[{"given":"Robert","family":"Ross","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. S.","family":"Subrahmanian","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Grant","sequence":"additional","affiliation":[{"name":"Towson University, Towson, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Aitchison J. and Dunsmore I. R. 1975. Statistical Prediction Analysis. Cambridge University Press Cambridge.]]  Aitchison J. and Dunsmore I. R. 1975. Statistical Prediction Analysis. Cambridge University Press Cambridge.]]","DOI":"10.1017\/CBO9780511569647"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.166990"},{"volume-title":"Proceedings of the Symposium on Computer Vision and Pattern Recognition (San Barbara, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 196--202","author":"Bobick A.","key":"e_1_2_1_3_1","unstructured":"Bobick , A. , and Ivanov , Y . 1998. Action recognition using probabilistic parsing . In Proceedings of the Symposium on Computer Vision and Pattern Recognition (San Barbara, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 196--202 .]] Bobick, A., and Ivanov, Y. 1998. Action recognition using probabilistic parsing. In Proceedings of the Symposium on Computer Vision and Pattern Recognition (San Barbara, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 196--202.]]"},{"volume-title":"Proceedings of the 13th International Conference on Very Large Databases (Los Altos, Calif.). Morgan-Kaufmann, San Mateo, Calif., 71--81","author":"Cavallo R.","key":"e_1_2_1_4_1","unstructured":"Cavallo , R. , and Pittarelli , M . 1987. The theory of probabilistic databases . In Proceedings of the 13th International Conference on Very Large Databases (Los Altos, Calif.). Morgan-Kaufmann, San Mateo, Calif., 71--81 .]] Cavallo, R., and Pittarelli, M. 1987. The theory of probabilistic databases. In Proceedings of the 13th International Conference on Very Large Databases (Los Altos, Calif.). Morgan-Kaufmann, San Mateo, Calif., 71--81.]]"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872823"},{"key":"e_1_2_1_6_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1992. Introduction to Algorithms. MIT Press Cambridge Mass.]]   Cormen T. H. Leiserson C. E. and Rivest R. L. 1992. Introduction to Algorithms. MIT Press Cambridge Mass.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1162\/105864097567165"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/383734.383736"},{"volume-title":"Proceedings of the 14th International Conference on Logic Program. MIT Press","author":"Dekhtyar A.","key":"e_1_2_1_9_1","unstructured":"Dekhtyar , A. , and Subrahmanian , V. S . 1997. Hybrid probabilistic programs . In Proceedings of the 14th International Conference on Logic Program. MIT Press , Cambridge, Mass., 391--405.]] Dekhtyar, A., and Subrahmanian, V. S. 1997. Hybrid probabilistic programs. In Proceedings of the 14th International Conference on Logic Program. MIT Press, Cambridge, Mass., 391--405.]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/232753.232796"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/288086.288087"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/646203.682127"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90060-U"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)90014-G"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/174608.174612"},{"volume-title":"Proceedings of the 2nd World Conference on Integrated Design and Process Technology. Society for Design and Process Science","author":"Fuhr N.","key":"e_1_2_1_16_1","unstructured":"Fuhr , N. , and Rolleke , T . 1996. A probabilistic NF2 relational algebra for integrated information retrieval and database systems . In Proceedings of the 2nd World Conference on Integrated Design and Process Technology. Society for Design and Process Science , Austin, Tex. 17--30.]] Fuhr, N., and Rolleke, T. 1996. A probabilistic NF2 relational algebra for integrated information retrieval and database systems. In Proceedings of the 2nd World Conference on Integrated Design and Process Technology. Society for Design and Process Science, Austin, Tex. 17--30.]]"},{"key":"e_1_2_1_17_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company San Francisco Calif.]]   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company San Francisco Calif.]]"},{"key":"e_1_2_1_18_1","unstructured":"Gee J. Briquer L. Barillot C. and Haynor D. 1995. Probabilistic matching of brain images. In Information Processing in Medical Imaging. Kluwer Academic Publishers Dordrecht 113--125.]]  Gee J. Briquer L. Barillot C. and Haynor D. 1995. Probabilistic matching of brain images. In Information Processing in Medical Imaging. Kluwer Academic Publishers Dordrecht 113--125.]]"},{"volume-title":"Proceedings of the 3rd International Conference on Extending Database Technology. Springer-Verlag","author":"Kiessling W.","key":"e_1_2_1_19_1","unstructured":"Kiessling , W. , Thone , H. , and Guntzer , U . 1992. Database support for problematic knowledge . In Proceedings of the 3rd International Conference on Extending Database Technology. Springer-Verlag , Berlin, Germany, 421--436.]] Kiessling, W., Thone, H., and Guntzer, U. 1992. Database support for problematic knowledge. In Proceedings of the 3rd International Conference on Extending Database Technology. Springer-Verlag, Berlin, Germany, 421--436.]]"},{"volume-title":"Proceedings of the 2nd International Conference on Database Theory. Springer-Verlag","author":"Kifer M.","key":"e_1_2_1_20_1","unstructured":"Kifer , M. , and Li , A . 1988. On the semantics of rule-based expert systems with uncertainty . In Proceedings of the 2nd International Conference on Database Theory. Springer-Verlag , New York, 102--117.]] Kifer, M., and Li, A. 1988. On the semantics of rule-based expert systems with uncertainty. In Proceedings of the 2nd International Conference on Database Theory. Springer-Verlag, New York, 102--117.]]"},{"key":"e_1_2_1_21_1","unstructured":"Korth H. and Silberschatz A. 1991. Database System Concepts 2nd ed. McGraw-Hill New York.]]   Korth H. and Silberschatz A. 1991. Database System Concepts 2nd ed. McGraw-Hill New York.]]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261131"},{"volume-title":"Proceedings of the 5th International Conference on Database and Expert Systems Applications. Springer","author":"Lakshmanan L. V. S.","key":"e_1_2_1_23_1","unstructured":"Lakshmanan , L. V. S. , and Sadri , F . 1994a. Modeling uncertainty in deductive databases . In Proceedings of the 5th International Conference on Database and Expert Systems Applications. Springer , Berlin, Germany, 724--733.]] Lakshmanan, L. V. S., and Sadri, F. 1994a. Modeling uncertainty in deductive databases. In Proceedings of the 5th International Conference on Database and Expert Systems Applications. Springer, Berlin, Germany, 724--733.]]"},{"volume-title":"Proceedings of the 11th International Logic Programing Symposium","author":"Lakshmanan L. V. S.","key":"e_1_2_1_24_1","unstructured":"Lakshmanan , L. V. S. , and Sadri , F . 1994b. Probabilistic deductive databases . In Proceedings of the 11th International Logic Programing Symposium ( London, England). MIT Press, Cambridge, Mass., 254--268.]] Lakshmanan, L. V. S., and Sadri, F. 1994b. Probabilistic deductive databases. In Proceedings of the 11th International Logic Programing Symposium (London, England). MIT Press, Cambridge, Mass., 254--268.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.940732"},{"volume-title":"Proceedings of the 6th International Conference on Computer Vision. Narosa Publishing House","author":"Mandelbaum R.","key":"e_1_2_1_26_1","unstructured":"Mandelbaum , R. , Kamberova , G. , and Mintz , M . 1998. Stereo depth estimation: A confidence interval approach . In Proceedings of the 6th International Conference on Computer Vision. Narosa Publishing House , New Delhi, 503--509.]] Mandelbaum, R., Kamberova, G., and Mintz, M. 1998. Stereo depth estimation: A confidence interval approach. In Proceedings of the 6th International Conference on Computer Vision. Narosa Publishing House, New Delhi, 503--509.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90061-J"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1023"},{"volume-title":"Proceedings of the Symposium on Computer Vision and Pattern Recognition (Santa Barbara, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 39--46","author":"Oliver N.","key":"e_1_2_1_29_1","unstructured":"Oliver , N. , Rosario , B. , and Pentland , A . 1998. Statistical modeling of human interactions . In Proceedings of the Symposium on Computer Vision and Pattern Recognition (Santa Barbara, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 39--46 .]] Oliver, N., Rosario, B., and Pentland, A. 1998. Statistical modeling of human interactions. In Proceedings of the Symposium on Computer Vision and Pattern Recognition (Santa Barbara, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 39--46.]]"},{"volume-title":"Proceedings of the 13th International Symposium on Methodologies for Intelligent System. Springer","author":"Ross R.","key":"e_1_2_1_30_1","unstructured":"Ross , R. , Subrahmanian , V. S. , and Grant , J . 2002. Probabilistic aggregates . In Proceedings of the 13th International Symposium on Methodologies for Intelligent System. Springer , Berlin, Germany, 553--564.]] Ross, R., Subrahmanian, V. S., and Grant, J. 2002. Probabilistic aggregates. In Proceedings of the 13th International Symposium on Methodologies for Intelligent System. Springer, Berlin, Germany, 553--564.]]"},{"volume-title":"Proceedings of the 12th International Conference on Machine Learning. Morgan Kaufmann","author":"Street W. N.","key":"e_1_2_1_32_1","unstructured":"Street , W. N. , Mangasarian , O. L. , and Wolberg , W. H . 1995. An inductive learning approach to prognostic prediction . In Proceedings of the 12th International Conference on Machine Learning. Morgan Kaufmann , San Francisco, Calif. 522--530.]] Street, W. N., Mangasarian, O. L., and Wolberg, W. H. 1995. An inductive learning approach to prognostic prediction. In Proceedings of the 12th International Conference on Machine Learning. Morgan Kaufmann, San Francisco, Calif. 522--530.]]"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 4th Symposium on Logic Programming (Washington, D.C.). IEEE Computer Society Press, Los Alamitos, Calif., 173--182","author":"Subrahmanian V. S.","year":"1987","unstructured":"Subrahmanian , V. S. 1987 . On the semantics of quantitative logic programs . In Proceedings of the 4th Symposium on Logic Programming (Washington, D.C.). IEEE Computer Society Press, Los Alamitos, Calif., 173--182 .]] Subrahmanian, V. S. 1987. On the semantics of quantitative logic programs. In Proceedings of the 4th Symposium on Logic Programming (Washington, D.C.). IEEE Computer Society Press, Los Alamitos, Calif., 173--182.]]"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90033-8"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/10731.10733"},{"volume-title":"Information Retrieval","author":"van Rijsbergen C. J.","key":"e_1_2_1_36_1","unstructured":"van Rijsbergen , C. J. 1979. Information Retrieval . Butterworth , London, England .]] van Rijsbergen, C. J. 1979. Information Retrieval. Butterworth, London, England.]]"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2307\/2556090"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502570"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044731.1044734","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1044731.1044734","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:36:47Z","timestamp":1750282607000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044731.1044734"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1145\/1044731.1044734"],"URL":"https:\/\/doi.org\/10.1145\/1044731.1044734","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2005,1]]},"assertion":[{"value":"2005-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}