{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T01:11:54Z","timestamp":1774746714221,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["(FP7\/2007-2013)\/ERC"],"award-info":[{"award-number":["(FP7\/2007-2013)\/ERC"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>Sources of data uncertainty and imprecision are numerous. A way to handle this uncertainty is to associate probabilistic annotations to data. Many such probabilistic database models have been proposed, both in the relational and in the semi-structured setting. The latter is particularly well adapted to the management of uncertain data coming from a variety of automatic processes. An important problem, in the context of probabilistic XML databases, is that of answering aggregate queries (count, sum, avg, etc.), which has received limited attention so far. In a model unifying the various (discrete) semi-structured probabilistic models studied up to now, we present algorithms to compute the distribution of the aggregation values (exploiting some regularity properties of the aggregate functions) and probabilistic moments (especially expectation and variance) of this distribution. We also prove the intractability of some of these problems and investigate approximation techniques. We finally extend the discrete model to a continuous one, in order to take into account continuous data values, such as measurements from sensor networks, and extend our algorithms and complexity results to the continuous case.<\/jats:p>","DOI":"10.1145\/2043652.2043658","type":"journal-article","created":{"date-parts":[[2011,12,20]],"date-time":"2011-12-20T17:49:14Z","timestamp":1324403354000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Capturing continuous data and answering aggregate queries in probabilistic XML"],"prefix":"10.1145","volume":"36","author":[{"given":"Serge","family":"Abiteboul","sequence":"first","affiliation":[{"name":"INRIA Saclay -- \u00cele-de-France &amp; LSV, ENS Cachan, Orsay Cedex, France"}]},{"given":"T.-H. HUBERT","family":"Chan","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam Road, Hong Kong"}]},{"given":"Evgeny","family":"Kharlamov","sequence":"additional","affiliation":[{"name":"Free University of Bozen-Bolzano &amp; INRIA Saclay -- \u00cele-de-France, Bolzano, Italy"}]},{"given":"Werner","family":"Nutt","sequence":"additional","affiliation":[{"name":"Free University of Bozen-Bolzano, Bolzano, Italy"}]},{"given":"Pierre","family":"Senellart","sequence":"additional","affiliation":[{"name":"Institut T\u00e9l\u00e9com; T\u00e9l\u00e9com ParisTech; CNRS LTCI, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2011,12,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804679"},{"key":"e_1_2_1_2_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading PA.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading PA."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0146-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_62"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376936"},{"key":"e_1_2_1_6_1","volume-title":"Probability & Measure Theory","author":"Ash R. B.","unstructured":"Ash , R. B. and Dol\u00e9ans-Dade , C. A. 2000. Probability & Measure Theory . Academic Press , San Diego, CA . Ash, R. B. and Dol\u00e9ans-Dade, C. A. 2000. Probability & Measure Theory. Academic Press, San Diego, CA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.166990"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920939"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458484.1458500"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872823"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376933"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559831"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138394.1138400"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538810"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265531"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Deshpande A.","unstructured":"Deshpande , A. , Guestrin , C. , Madden , S. , Hellerstein , J. M. , and Hong , W . 2004. Model-Driven data acquisition in sensor networks . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Fransisco, CA. Deshpande, A., Guestrin, C., Madden, S., Hellerstein, J. M., and Hong, W. 2004. Model-Driven data acquisition in sensor networks. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Fransisco, CA."},{"key":"e_1_2_1_17_1","unstructured":"Friedlander F. G. and Joshi M. 1999. Introduction to the Theory of Distributions 2nd Ed. Cambridge University Press Cambridge UK.  Friedlander F. G. and Joshi M. 1999. Introduction to the Theory of Distributions 2nd Ed. Cambridge University Press Cambridge UK."},{"key":"e_1_2_1_18_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.295124"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11896548_24"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Conference on Data Engineering. IEEE","author":"Hung E.","unstructured":"Hung , E. , Getoor , L. , and Subrahmanian , V. S . 2003. PXML: A probabilistic semistructured data model and algebra . In Proceedings of the International Conference on Data Engineering. IEEE , Los Alamitos, CA. Hung, E., Getoor, L., and Subrahmanian, V. S. 2003. PXML: A probabilistic semistructured data model and algebra. In Proceedings of the International Conference on Data Engineering. IEEE, Los Alamitos, CA."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276920.1276926"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA). SIAM","author":"Jayram T. S.","unstructured":"Jayram , T. S. , Kale , S. , and Vee , E . 2007. Efficient aggregation algorithms for probabilistic data . In Proceedings of the Symposium on Discrete Algorithms (SODA). SIAM , Philadelphia, PA. Jayram, T. S., Kale, S., and Vee, E. 2007. Efficient aggregation algorithms for probabilistic data. In Proceedings of the Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966357.1966366"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376687"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0150-5"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM","author":"Kimelfeld B.","unstructured":"Kimelfeld , B. and Sagiv , Y . 2007. Matching twigs in probabilistic XML . In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM , New York. Kimelfeld, B. and Sagiv, Y. 2007. Matching twigs in probabilistic XML. In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, New York."},{"key":"e_1_2_1_31_1","volume-title":"MayBMS: A system for managing large uncertain and probabilistic databases","author":"Koch C.","unstructured":"Koch , C. 2009. MayBMS: A system for managing large uncertain and probabilistic databases . In Managing and Mining Uncertain Data, C. Aggarwal, Ed., Springer , New York . Koch, C. 2009. MayBMS: A system for managing large uncertain and probabilistic databases. In Managing and Mining Uncertain Data, C. Aggarwal, Ed., Springer, New York."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020197923385"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Nierman A.","unstructured":"Nierman , A. and Jagadish , H. V . 2002. ProTDB: Probabilistic data in XML . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Fransisco, CA. Nierman, A. and Jagadish, H. V. 2002. ProTDB: Probabilistic data in XML. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Fransisco, CA."},{"key":"e_1_2_1_34_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","unstructured":"Papadimitriou , C. H. 1994. Computational Complexity . Addison Wesley , Reading, PA . Papadimitriou, C. H. 1994. Computational Complexity. Addison Wesley, Reading, PA."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the Database Programming Languages","author":"R\u00e9 C.","unstructured":"R\u00e9 , C. and Suciu , D . 2007. Efficient evaluation of HAVING queries on a probabilistic database . In Proceedings of the Database Programming Languages . Springer, New York. R\u00e9, C. and Suciu, D. 2007. Efficient evaluation of HAVING queries on a probabilistic database. In Proceedings of the Database Programming Languages. Springer, New York."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265570"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.11"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR). Online Proceedings.","author":"Widom J.","year":"2005","unstructured":"Widom , J. 2005 . Trio: A system for integrated management of data, accuracy, and lineage . In Proceedings of the Conference on Innovative Data Systems Research (CIDR). Online Proceedings. Widom, J. 2005. Trio: A system for integrated management of data, accuracy, and lineage. In Proceedings of the Conference on Innovative Data Systems Research (CIDR). Online Proceedings."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2043652.2043658","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2043652.2043658","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:19Z","timestamp":1750240459000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2043652.2043658"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2043652.2043658"],"URL":"https:\/\/doi.org\/10.1145\/2043652.2043658","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}