{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T20:37:28Z","timestamp":1762979848207,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0430994ARRA-0905276"],"award-info":[{"award-number":["IIS-0430994ARRA-0905276"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-0430994ARRA-0905276"],"award-info":[{"award-number":["IIS-0430994ARRA-0905276"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>The work reported here lays the foundations of data exchange in the presence of probabilistic data. This requires rethinking the very basic concepts of traditional data exchange, such as solution, universal solution, and the certain answers of target queries. We develop a framework for data exchange over probabilistic databases, and make a case for its coherence and robustness. This framework applies to arbitrary schema mappings, and finite or countably infinite probability spaces on the source and target instances. After establishing this framework and formulating the key concepts, we study the application of the framework to a concrete and practical setting where probabilistic databases are compactly encoded by means of annotations formulated over random Boolean variables. In this setting, we study the problems of testing for the existence of solutions and universal solutions, materializing such solutions, and evaluating target queries (for unions of conjunctive queries) in both the exact sense and the approximate sense. For each of the problems, we carry out a complexity analysis based on properties of the annotation, for various classes of dependencies. Finally, we show that the framework and results easily and completely generalize to allow not only the data, but also the schema mapping itself to be probabilistic.<\/jats:p>","DOI":"10.1145\/1989727.1989729","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Probabilistic data exchange"],"prefix":"10.1145","volume":"58","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[{"name":"IBM Research -- Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"IBM Research -- Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA and IBM Research -- Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_62"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 1151--1154","author":"Agrawal P.","key":"e_1_2_1_2_1","unstructured":"Agrawal , P. , Benjelloun , O. , Sarma , A. D. , Hayworth , C. , Nabar , S. U. , Sugihara , T. , and Widom , J . 2006. Trio: A system for data, uncertainty, and lineage . In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 1151--1154 . Agrawal, P., Benjelloun, O., Sarma, A. D., Hayworth, C., Nabar, S. U., Sugihara, T., and Widom, J. 2006. Trio: A system for data, uncertainty, and lineage. In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 1151--1154."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.08.002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804687"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.166990"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066277"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90075-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376933"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 864--875","author":"Dalvi N. N.","key":"e_1_2_1_11_1","unstructured":"Dalvi , N. N. and Suciu , D . 2004. Efficient query evaluation on probabilistic databases . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 864--875 . Dalvi, N. N. and Suciu, D. 2004. Efficient query evaluation on probabilistic databases. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 864--875."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265571"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0119-9"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 687--698","author":"Dong X.","key":"e_1_2_1_15_1","unstructured":"Dong , X. , Halevy , A. Y. , and Yu , C . 2007. Data integration with uncertainty . In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 687--698 . Dong, X., Halevy, A. Y., and Yu, C. 2007. Data integration with uncertainty. In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 687--698."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804681"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114249"},{"key":"e_1_2_1_20_1","first-page":"53","article-title":"Sur les tableaux de corr\u00e9lation dont les marges sont donn\u00e9s","volume":"4","author":"Fr\u00e9chet M.","year":"1951","unstructured":"Fr\u00e9chet , M. 1951 . Sur les tableaux de corr\u00e9lation dont les marges sont donn\u00e9s . Annales de l'Universit\u00e9 de Lyon 4 , 53 -- 57 . Fr\u00e9chet, M. 1951. Sur les tableaux de corr\u00e9lation dont les marges sont donn\u00e9s. Annales de l'Universit\u00e9 de Lyon 4, 53--57.","journal-title":"Annales de l'Universit\u00e9 de Lyon"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346334"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.295124"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 675--686","author":"Green T. J.","key":"e_1_2_1_25_1","unstructured":"Green , T. J. , Karvounarakis , G. , Ives , Z. G. , and Tannen , V . 2007a. Update exchange with mappings and provenance . In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 675--686 . Green, T. J., Karvounarakis, G., Ives, Z. G., and Tannen, V. 2007a. Update exchange with mappings and provenance. In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 675--686."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_27_1","first-page":"17","article-title":"Models for incomplete and probabilistic information","volume":"29","author":"Green T. J.","year":"2006","unstructured":"Green , T. J. and Tannen , V. 2006 . Models for incomplete and probabilistic information . IEEE Data Eng. Bull. 29 , 1, 17 -- 24 . Green, T. J. and Tannen, V. 2006. Models for incomplete and probabilistic information. IEEE Data Eng. Bull. 29, 1, 17--24.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel M. Lov\u00e1sz L. and Schrijver A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag Berlin.  Gr\u00f6tschel M. Lov\u00e1sz L. and Schrijver A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag Berlin.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_1_30_1","unstructured":"Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications 28. Oxford University Press.  Hell P. and Ne\u0161et\u0159il J. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications 28. Oxford University Press."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90038-2"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376687"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265572"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90139-9"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376932"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Luby M. and Velickovic B. 1996. On deterministic approximation of DNF. Algorithmica 16 4\/5 415--433.  Luby M. and Velickovic B. 1996. On deterministic approximation of DNF. Algorithmica 16 4\/5 415--433.","DOI":"10.1007\/BF01940873"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_2_1_40_1","first-page":"234","article-title":"Einfache beispiele zweidimensionaler verteilungen","volume":"8","author":"Morgenstern D.","year":"1956","unstructured":"Morgenstern , D. 1956 . Einfache beispiele zweidimensionaler verteilungen . Mitteilingsblatt f\u00fcr Mathematische Statistik 8 , 234 -- 235 . Morgenstern, D. 1956. Einfache beispiele zweidimensionaler verteilungen. Mitteilingsblatt f\u00fcr Mathematische Statistik 8, 234--235.","journal-title":"Mitteilingsblatt f\u00fcr Mathematische Statistik"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90068-0"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). IEEE, 886--895","author":"Re C.","key":"e_1_2_1_42_1","unstructured":"Re , C. , Dalvi , N. N. , and Suciu , D . 2007. Efficient top-k query evaluation on probabilistic data . In Proceedings of the International Conference on Data Engineering (ICDE). IEEE, 886--895 . Re, C., Dalvi, N. N., and Suciu, D. 2007. Efficient top-k query evaluation on probabilistic data. In Proceedings of the International Conference on Data Engineering (ICDE). IEEE, 886--895."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783534.1783553"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 51--62","author":"Re C.","key":"e_1_2_1_44_1","unstructured":"Re , C. and Suciu , D . 2007b. Materialized views in probabilistic databases for information exchange and query optimization . In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 51--62 . Re, C. and Suciu, D. 2007b. Materialized views in probabilistic databases for information exchange and query optimization. In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM, 51--62."},{"key":"e_1_2_1_45_1","first-page":"185","article-title":"Uncertainty In Data Integration. Springer, New York","volume":"7","author":"Sarma A. D.","year":"2009","unstructured":"Sarma , A. D. , Dong , X. , and Halevy , A. 2009 . Uncertainty In Data Integration. Springer, New York , Chapter 7 , 185 -- 222 . Sarma, A. D., Dong, X., and Halevy, A. 2009. Uncertainty In Data Integration. Springer, New York, Chapter 7, 185--222.","journal-title":"Chapter"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376702"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497511"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265570"},{"key":"e_1_2_1_49_1","unstructured":"Shaked M. and Shanthikumar J. 1994. Stochastic Orders and Their Applications. Academic Press San Diego CA.  Shaked M. and Shanthikumar J. 1994. Stochastic Orders and Their Applications. Academic Press San Diego CA."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221023"},{"key":"e_1_2_1_51_1","first-page":"069","article-title":"A note on deterministic approximate counting for k-DNF","volume":"9","author":"Trevisan L.","year":"2002","unstructured":"Trevisan , L. 2002 . A note on deterministic approximate counting for k-DNF . In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC). 9 , 069 . Trevisan, L. 2002. A note on deterministic approximate counting for k-DNF. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC). 9, 069.","journal-title":"Proceedings of the Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90037-2"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989727.1989729","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1989727.1989729","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:05:54Z","timestamp":1750244754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989727.1989729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1989727.1989729"],"URL":"https:\/\/doi.org\/10.1145\/1989727.1989729","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2010-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}