{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T19:48:15Z","timestamp":1759693695938,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1032\/05893\/05"],"award-info":[{"award-number":["1032\/05893\/05"]}],"id":[{"id":"10.13039\/501100003977","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":[[2009,8]]},"abstract":"<jats:p>\n            Constraints are important, not only for maintaining data integrity, but also because they capture natural probabilistic dependencies among data items. A\n            <jats:italic>probabilistic XML database<\/jats:italic>\n            (PXDB) is the probability subspace comprising the instances of a\n            <jats:italic>p-document<\/jats:italic>\n            that satisfy a set of constraints. In contrast to existing models that can express probabilistic dependencies, it is shown that query evaluation is tractable in PXDBs. The problems of sampling and determining well-definedness (i.e., whether the aforesaid subspace is nonempty) are also tractable. Furthermore, queries and constraints can include the aggregate functions\n            <jats:italic>count, max, min,<\/jats:italic>\n            and\n            <jats:italic>ratio.<\/jats:italic>\n            Finally, this approach can be easily extended to allow a probabilistic interpretation of constraints.\n          <\/jats:p>","DOI":"10.1145\/1567274.1567280","type":"journal-article","created":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T17:52:59Z","timestamp":1251827579000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Incorporating constraints in probabilistic XML"],"prefix":"10.1145","volume":"34","author":[{"given":"Sara","family":"Cohen","sequence":"first","affiliation":[{"name":"The Hebrew University of Jerusalem, Jerusalem, Israel"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]},{"given":"Yehoshua","family":"Sagiv","sequence":"additional","affiliation":[{"name":"The Hebrew University of Jerusalem, Jerusalem, Israel"}]}],"member":"320","published-online":{"date-parts":[[2009,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Abiteboul S. Kimelfeld B. Sagiv Y. and Senellart P. 2009. On the expressiveness of probabilistic XML models. VLDB J.  Abiteboul S. Kimelfeld B. Sagiv Y. and Senellart P. 2009. On the expressiveness of probabilistic XML models. VLDB J.","DOI":"10.1007\/s00778-009-0146-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_62"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.11.025"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(02)00223-2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376933"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559831"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90060-D"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90036-B"},{"volume-title":"Proceedings of the International Conference on Very Large Database (VLDB). Morgan Kaufmann, 864--875","author":"Dalvi N. N.","key":"e_1_2_1_10_1","unstructured":"Dalvi , N. N. and Suciu , D . 2004. Efficient query evaluation on probabilistic databases . In Proceedings of the International Conference on Very Large Database (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 Database (VLDB). Morgan Kaufmann, 864--875."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265571"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(02)00219-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567117"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00032-6"},{"volume-title":"Proceedings of the Annual IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society, 215--224","author":"Frick M.","key":"e_1_2_1_15_1","unstructured":"Frick , M. and Grohe , M . 2002. The complexity of first-order and monadic second-order logic revisited . In Proceedings of the Annual IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society, 215--224 . Frick, M. and Grohe, M. 2002. The complexity of first-order and monadic second-order logic revisited. In Proceedings of the Annual IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society, 215--224."},{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT). Springer, 361--377","author":"Hung E.","key":"e_1_2_1_16_1","unstructured":"Hung , E. , Getoor , L. , and Subrahmanian , V. S . 2003a. Probabilistic interval XML . In Proceedings of the International Conference on Database Theory (ICDT). Springer, 361--377 . Hung, E., Getoor, L., and Subrahmanian, V. S. 2003a. Probabilistic interval XML. In Proceedings of the International Conference on Database Theory (ICDT). Springer, 361--377."},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). IEEE Computer Society, 467--478","author":"Hung E.","key":"e_1_2_1_17_1","unstructured":"Hung , E. , Getoor , L. , and Subrahmanian , V. S . 2003b. PXML: A probabilistic semistructured data model and algebra . In Proceedings of the International Conference on Data Engineering (ICDE). IEEE Computer Society, 467--478 . Hung, E., Getoor, L., and Subrahmanian, V. S. 2003b. PXML: A probabilistic semistructured data model and algebra. In Proceedings of the International Conference on Data Engineering (ICDE). IEEE Computer Society, 467--478."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376687"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Kimelfeld B. Kosharovsky Y. and Sagiv Y. 2009. Query evaluation over probabilistic XML. VLDB J.  Kimelfeld B. Kosharovsky Y. and Sagiv Y. 2009. Query evaluation over probabilistic XML. VLDB J.","DOI":"10.1007\/s00778-009-0150-5"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). ACM, 27--38","author":"Kimelfeld B.","key":"e_1_2_1_20_1","unstructured":"Kimelfeld , B. and Sagiv , Y . 2007a. Matching twigs in probabilistic XML . In Proceedings of the International Conference on Very Large Databases (VLDB). ACM, 27--38 . Kimelfeld, B. and Sagiv, Y. 2007a. Matching twigs in probabilistic XML. In Proceedings of the International Conference on Very Large Databases (VLDB). ACM, 27--38."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265572"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183761"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00301-2"},{"volume-title":"Proceedings of the International Conference on Very Large Database (VLDB). ACM, 646--657","author":"Nierman A.","key":"e_1_2_1_24_1","unstructured":"Nierman , A. and Jagadish , H. V . 2002. ProTDB: Probabilistic data in XML . In Proceedings of the International Conference on Very Large Database (VLDB). ACM, 646--657 . Nierman, A. and Jagadish, H. V. 2002. ProTDB: Probabilistic data in XML. In Proceedings of the International Conference on Very Large Database (VLDB). ACM, 646--657."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the CogSci. Cognitive Science Society","author":"Pearl J.","year":"1985","unstructured":"Pearl , J. 1985 . Bayesian networks: A model of self-activated memory for evidential reasoning . In Proceedings of the CogSci. Cognitive Science Society , University of California, Irvine, CA, 329--334. Pearl, J. 1985. Bayesian networks: A model of self-activated memory for evidential reasoning. In Proceedings of the CogSci. Cognitive Science Society, University of California, Irvine, CA, 329--334."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). IEEE, 886--895","author":"Re C.","key":"e_1_2_1_27_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."},{"volume-title":"Proceedings of the International Conference on Database Programming Languages (DBPL). Springer, 186--200","author":"Re C.","key":"e_1_2_1_28_1","unstructured":"Re , C. and Suciu , D . 2007. Efficient evaluation of HAVING queries on a probabilistic database . In Proceedings of the International Conference on Database Programming Languages (DBPL). Springer, 186--200 . Re, C. and Suciu, D. 2007. Efficient evaluation of HAVING queries on a probabilistic database. In Proceedings of the International Conference on Database Programming Languages (DBPL). Springer, 186--200."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265570"},{"volume-title":"Proceedings of the International Conference on Logic Programming (ICLP). Springer, 84--98","author":"Tamaki H.","key":"e_1_2_1_30_1","unstructured":"Tamaki , H. and Sato , T . 1986. OLD resolution with tabulation . In Proceedings of the International Conference on Logic Programming (ICLP). Springer, 84--98 . Tamaki, H. and Sato, T. 1986. OLD resolution with tabulation. In Proceedings of the International Conference on Logic Programming (ICLP). Springer, 84--98."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221023"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.11"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/131295.131299"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1567274.1567280","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1567274.1567280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:32Z","timestamp":1750278152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1567274.1567280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1145\/1567274.1567280"],"URL":"https:\/\/doi.org\/10.1145\/1567274.1567280","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2009,8]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}