{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T17:28:39Z","timestamp":1673026119699},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>We study the complexity of query answering using views in a probabilistic XML setting, identifying large classes of XPath queries -- with child and descendant navigation and predicates -- for which there are efficient (PTime) algorithms. We consider this problem under the two possible semantics for XML query results: with persistent node identifiers and in their absence. Accordingly, we consider rewritings that can exploit a single view, by means of compensation, and rewritings that can use multiple views, by means of intersection. Since in a probabilistic setting queries return answers with probabilities, the problem of rewriting goes beyond the classic one of retrieving XML answers from views. For both semantics of XML queries, we show that, even when XML answers can be retrieved from views, their probabilities may not be computable.<\/jats:p>\n          <jats:p>For rewritings that use only compensation, we describe a PTime decision procedure, based on easily verifiable criteria that distinguish between the feasible cases -- when probabilistic XML results are computable -- and the unfeasible ones. For rewritings that can use multiple views, with compensation and intersection, we identify the most permissive conditions that make probabilistic rewriting feasible, and we describe an algorithm that is sound in general, and becomes complete under fairly permissive restrictions, running in PTime modulo worst-case exponential time equivalence tests. This is the best we can hope for since intersection makes query equivalence intractable already over deterministic data. Our algorithm runs in PTime whenever deterministic rewritings can be found in PTime.<\/jats:p>","DOI":"10.14778\/2350229.2350235","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1148-1159","source":"Crossref","is-referenced-by-count":3,"title":["Answering queries using views over probabilistic XML"],"prefix":"10.14778","volume":"5","author":[{"given":"Bogdan","family":"Cautis","sequence":"first","affiliation":[{"name":"Institut Mines-T\u00e9l\u00e9com, T\u00e9l\u00e9com ParisTech, CNRS LTCI, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evgeny","family":"Kharlamov","sequence":"additional","affiliation":[{"name":"KRDB Research Centre, Free University of Bozen-Bolzano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1804669.1804679"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0146-1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516381"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0076-7"},{"key":"e_1_2_1_5_1","first-page":"87","volume-title":"VLDB","author":"Arion A.","year":"2007","unstructured":"A. Arion , V. Benzaken , I. Manolescu , and Y. Papakonstantinou . Structured materialized views for XML queries . In VLDB , pages 87 -- 98 , 2007 . A. Arion, V. Benzaken, I. Manolescu, and Y. Papakonstantinou. Structured materialized views for XML queries. In VLDB, pages 87--98, 2007."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316697"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1456650.1456653"},{"key":"e_1_2_1_8_1","volume-title":"WebDB","author":"Cautis B.","year":"2008","unstructured":"B. Cautis , A. Deutsch , and N. Onose . XPath rewriting using multiple views: Achieving completeness and efficiency . In WebDB , 2008 . B. Cautis, A. Deutsch, and N. Onose. XPath rewriting using multiple views: Achieving completeness and efficiency. In WebDB, 2008."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687662"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1929934.1929939"},{"key":"e_1_2_1_12_1","volume-title":"5th Alberto Mendelzon International Workshop on Foundations of Data Management","author":"Cautis B.","year":"2011","unstructured":"B. Cautis and E. Kharlamov . Challenges for view-based query answering over probabilistic XML . In 5th Alberto Mendelzon International Workshop on Foundations of Data Management , 2011 . B. Cautis and E. Kharlamov. Challenges for view-based query answering over probabilistic XML. In 5th Alberto Mendelzon International Workshop on Foundations of Data Management, 2011."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.152"},{"key":"e_1_2_1_14_1","volume-title":"WebDB","author":"Chen L.","year":"2002","unstructured":"L. Chen and E. A. Rundensteiner . XCache: XQuery-based caching system . In WebDB , 2002 . L. Chen and E. A. Rundensteiner. XCache: XQuery-based caching system. In WebDB, 2002."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538810"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265571"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.006"},{"key":"e_1_2_1_18_1","first-page":"201","volume-title":"VLDB","author":"Deutsch A.","year":"2003","unstructured":"A. Deutsch and V. Tannen . MARS: A system for publishing XML from mixed and redundant storage . In VLDB , pages 201 -- 212 , 2003 . A. Deutsch and V. Tannen. MARS: A system for publishing XML from mixed and redundant storage. In VLDB, pages 201--212, 2003."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0119-9"},{"key":"e_1_2_1_20_1","volume-title":"MUD","author":"Hollander E. S.","year":"2010","unstructured":"E. S. Hollander and M. van Keulen . Storing and querying probabilistic XML using a probabilistic relational DBMS . In MUD , 2010 . E. S. Hollander and M. van Keulen. Storing and querying probabilistic XML using a probabilistic relational DBMS. In MUD, 2010."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966357.1966366"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0150-5"},{"key":"e_1_2_1_23_1","volume-title":"Managing and Mining Uncertain Data","author":"Koch C.","year":"2009","unstructured":"C. Koch . MayBMS: A system for managing large uncertain and probabilistic databases . In C. Aggarwal, editor, Managing and Mining Uncertain Data . Springer , 2009 . C. Koch. MayBMS: A system for managing large uncertain and probabilistic databases. In C. Aggarwal, editor, Managing and Mining Uncertain Data. Springer, 2009."},{"key":"e_1_2_1_24_1","first-page":"282","volume-title":"ICML","author":"Lafferty J.","year":"2001","unstructured":"J. Lafferty , A. McCallum , and F. Pereira . Conditional Random Fields: Probabilistic models for segmenting and labeling sequence data . In ICML , pages 282 -- 289 , 2001 . J. Lafferty, A. McCallum, and F. Pereira. Conditional Random Fields: Probabilistic models for segmenting and labeling sequence data. In ICML, pages 282--289, 2001."},{"key":"e_1_2_1_25_1","first-page":"469","volume-title":"VLDB","author":"Mandhani B.","year":"2005","unstructured":"B. Mandhani and D. Suciu . Query caching and view selection for XML databases . In VLDB , pages 469 -- 480 , 2005 . B. Mandhani and D. Suciu. Query caching and view selection for XML databases. In VLDB, pages 469--480, 2005."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767915"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_1_28_1","first-page":"646","volume-title":"VLDB","author":"Nierman A.","year":"2002","unstructured":"A. Nierman and H. V. Jagadish . ProTDB: Probabilistic data in XML . In VLDB , pages 646 -- 657 , 2002 . A. Nierman and H. V. Jagadish. ProTDB: Probabilistic data in XML. In VLDB, pages 646--657, 2002."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142524"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402751"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100057"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265570"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989480"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497496"},{"key":"e_1_2_1_35_1","first-page":"262","volume-title":"Proc. CIDR","author":"Widom J.","year":"2005","unstructured":"J. Widom . Trio : A system for integrated management of data, accuracy, and lineage . In Proc. CIDR , pages 262 -- 276 , 2005 . J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In Proc. CIDR, pages 262--276, 2005."},{"key":"e_1_2_1_36_1","first-page":"121","volume-title":"VLDB","author":"Xu W.","year":"2005","unstructured":"W. Xu and Z. \u00d6zsoyoglu . Rewriting XPath queries using materialized views . In VLDB , pages 121 -- 132 , 2005 . W. Xu and Z. \u00d6zsoyoglu. Rewriting XPath queries using materialized views. In VLDB, pages 121--132, 2005."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315459"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:25:33Z","timestamp":1672226733000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350235"}},"subtitle":["complexity and tractability"],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":36,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350235"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350235","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}