{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T20:00:01Z","timestamp":1759694401022},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00778-009-0150-5","type":"journal-article","created":{"date-parts":[[2009,7,31]],"date-time":"2009-07-31T12:16:21Z","timestamp":1249042581000},"page":"1117-1140","source":"Crossref","is-referenced-by-count":43,"title":["Query evaluation over probabilistic XML"],"prefix":"10.1007","volume":"18","author":[{"given":"Benny","family":"Kimelfeld","sequence":"first","affiliation":[]},{"given":"Yuri","family":"Kosharovsky","sequence":"additional","affiliation":[]},{"given":"Yehoshua","family":"Sagiv","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,1]]},"reference":[{"key":"150_CR1","unstructured":"Kimelfeld, B., Sagiv, Y.: Matching twigs in probabilistic XML. In: Proceedings of the Thirty Third International Conference on Very Large Data Bases, pp. 27\u201338. ACM Press, New York (2007)"},{"key":"150_CR2","doi-asserted-by":"crossref","unstructured":"Kimelfeld, B., Kosharovski, Y., Sagiv, Y.: Query efficiency in probabilistic XML models. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press, New York (2008)","DOI":"10.1145\/1376616.1376687"},{"issue":"2","key":"150_CR3","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1109\/69.277772","volume":"6","author":"M. Pittarelli","year":"1994","unstructured":"Pittarelli M.: An algebra for probabilistic databases. IEEE Trans. Knowl. Data Eng. 6(2), 293\u2013303 (1994)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"150_CR4","doi-asserted-by":"crossref","unstructured":"Re, C., Dalvi, N.N., Suciu, D.: Efficient top-k query evaluation on probabilistic data. In: Proceedings of the 23rd International Conference on Data Engineering, pp. 886\u2013895. IEEE Computer Society, USA (2007)","DOI":"10.1109\/ICDE.2007.367934"},{"key":"150_CR5","doi-asserted-by":"crossref","unstructured":"Dalvi, N.N., Suciu, D.: The dichotomy of conjunctive queries on probabilistic structures. In: Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 293\u2013302. ACM Press, New York (2007)","DOI":"10.1145\/1265530.1265571"},{"issue":"4","key":"150_CR6","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/s00778-006-0004-3","volume":"16","author":"N.N. Dalvi","year":"2007","unstructured":"Dalvi N.N., Suciu D.: Efficient query evaluation on probabilistic databases. VLDB J. 16(4), 523\u2013544 (2007)","journal-title":"VLDB J."},{"issue":"3","key":"150_CR7","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1145\/232753.232796","volume":"21","author":"D. Dey","year":"1996","unstructured":"Dey D., Sarkar S.: A probabilistic relational model and algebra. ACM Trans. Database Syst. 21(3), 339\u2013369 (1996)","journal-title":"ACM Trans. Database Syst."},{"issue":"1","key":"150_CR8","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1145\/239041.239045","volume":"15","author":"N. Fuhr","year":"1997","unstructured":"Fuhr N., R\u00f6lleke T.: A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Trans. Inf. Syst. 15(1), 32\u201366 (1997)","journal-title":"ACM Trans. Inf. Syst."},{"issue":"3","key":"150_CR9","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1145\/261124.261131","volume":"22","author":"L.V.S. Lakshmanan","year":"1997","unstructured":"Lakshmanan L.V.S., Leone N., Ross R.B., Subrahmanian V.S.: ProbView: a flexible probabilistic database system. ACM Trans. Database Syst. 22(3), 419\u2013469 (1997)","journal-title":"ACM Trans. Database Syst."},{"issue":"5","key":"150_CR10","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1109\/69.166990","volume":"4","author":"D. Barbar\u00e1","year":"1992","unstructured":"Barbar\u00e1 D., Garcia-Molina H., Porter D.: The management of probabilistic data. IEEE Trans. Knowl. Data Eng. 4(5), 487\u2013502 (1992)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"150_CR11","doi-asserted-by":"crossref","unstructured":"Nierman, A., Jagadish, H.V.: ProTDB: probabilistic data in XML. In: Proceedings of 28th International Conference on Very Large Data Bases, pp. 646\u2013657. Morgan Kaufmann, San Francisco (2002)","DOI":"10.1016\/B978-155860869-6\/50063-9"},{"key":"150_CR12","doi-asserted-by":"crossref","unstructured":"Abiteboul, S., Senellart, P.: Querying and updating probabilistic information in XML. In: Advances in Database Technology\u2014EDBT 2006, 10th International Conference on Extending Database Technology, Lecture Notes in Computer Science, vol. 3896, pp. 1059\u20131068. Springer, Berlin (2006)","DOI":"10.1007\/11687238_62"},{"key":"150_CR13","doi-asserted-by":"crossref","unstructured":"Senellart, P., Abiteboul, S.: On the complexity of managing probabilistic XML data. In: Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 283\u2013292. ACM Press, New York (2007)","DOI":"10.1145\/1265530.1265570"},{"key":"150_CR14","doi-asserted-by":"crossref","unstructured":"Hung, E., Getoor, L., Subrahmanian, V.S.: PXML: a probabilistic semistructured data model and algebra. In: Proceedings of the 19th International Conference on Data Engineering, pp. 467\u2013478 (2003)","DOI":"10.1109\/ICDE.2003.1260814"},{"key":"150_CR15","doi-asserted-by":"crossref","unstructured":"Hung, E., Getoor, L., Subrahmanian, V.S.: Probabilistic interval XML. ACM Trans. Comput. Logic 8(4) (2007)","DOI":"10.1145\/1276920.1276926"},{"key":"150_CR16","doi-asserted-by":"crossref","unstructured":"van Keulen, M., de Keijzer, A., Alink, W.: A probabilistic XML approach to data integration. In: Proceedings of the 21st International Conference on Data Engineering, ICDE 2005, pp. 459\u2013470. IEEE Computer Society, USA (2005)","DOI":"10.1109\/ICDE.2005.11"},{"key":"150_CR17","doi-asserted-by":"crossref","unstructured":"Li, T., Shao, Q., Chen, Y.: PEPX: a query-friendly probabilistic XML database. In: Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management, pp. 848\u2013849. ACM Press, New York (2006)","DOI":"10.1145\/1183614.1183761"},{"key":"150_CR18","doi-asserted-by":"crossref","unstructured":"Abiteboul, S., Kimelfeld, B., Sagiv, Y., Senellart, P.: On the expressiveness of probabilistic XML models. VLDB J. (2009). doi: 10.1007\/s00778-009-0146-1","DOI":"10.1007\/s00778-009-0146-1"},{"key":"150_CR19","doi-asserted-by":"crossref","unstructured":"Miklau, G., Suciu, D.: Containment and equivalence for an XPath fragment. In: Proceedings of the 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 65\u201376. ACM Press, New York (2002)","DOI":"10.1145\/543613.543623"},{"key":"150_CR20","doi-asserted-by":"crossref","unstructured":"Kimelfeld, B., Sagiv, Y.: Revisiting redundancy and minimization in an XPath fragment. In: 11th International Conference on Extending Database Technology, pp. 61\u201372. ACM Press, New York (2008)","DOI":"10.1145\/1352431.1352443"},{"key":"150_CR21","doi-asserted-by":"crossref","unstructured":"Bruno, N., Koudas, N., Srivastava, D.: Holistic twig joins: optimal XML pattern matching. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 310\u2013321. ACM Press, New York (2002)","DOI":"10.1145\/564691.564727"},{"issue":"6","key":"150_CR22","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1002\/asi.10058","volume":"53","author":"S. Cohen","year":"2002","unstructured":"Cohen S., Kanza Y., Kogan Y.A., Sagiv Y., Nutt W., Serebrenik A.: EquiX\u2014a search and query language for XML. J. Am. Soc. Inf. Sci. Technol. 53(6), 454\u2013466 (2002)","journal-title":"J. Am. Soc. Inf. Sci. Technol."},{"key":"150_CR23","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages (extended abstract). In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 137\u2013146. ACM Press, New York (1982)","DOI":"10.1145\/800070.802186"},{"key":"150_CR24","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D. Johnson","year":"1988","unstructured":"Johnson D., Yannakakis M., Papadimitriou C.: On generating all maximal independent sets. Inf. Process. Lett. 27, 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"key":"150_CR25","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: Conference Record of the Ninth Annual ACM Symposium on Theory of Computing, pp. 77\u201390. ACM Press, New York (1977)","DOI":"10.1145\/800105.803397"},{"issue":"3","key":"150_CR26","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"C.H. Papadimitriou","year":"1999","unstructured":"Papadimitriou C.H., Yannakakis M.: On the complexity of database queries. J. Comput. Syst. Sci. 58(3), 407\u2013427 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"150_CR27","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"Downey R.G., Fellows M.R.: Fixed-parameter tractability and completeness. I. Basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"150_CR28","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S. Toda","year":"1992","unstructured":"Toda S., Ogiwara M.: Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput. 21(2), 316\u2013328 (1992)","journal-title":"SIAM J. Comput."},{"key":"150_CR29","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Gurevich, Y., Hirsch, C.: The complexity of query reliability. In: Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 227\u2013234. ACM Press, New York (1998)","DOI":"10.1145\/275487.295124"},{"issue":"4","key":"150_CR30","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"J.S. Provan","year":"1983","unstructured":"Provan J.S., Ball M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12(4), 777\u2013788 (1983)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"150_CR31","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1145\/131295.131299","volume":"35","author":"D.S. Warren","year":"1992","unstructured":"Warren D.S.: Memoing for logic programs. Commun. ACM 35(3), 93\u2013111 (1992)","journal-title":"Commun. ACM"},{"issue":"3","key":"150_CR32","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"R.M. Karp","year":"1989","unstructured":"Karp R.M., Luby M., Madras N.: Monte-Carlo approximation algorithms for enumeration problems. J. Algorithms 10(3), 429\u2013448 (1989)","journal-title":"J. Algorithms"},{"issue":"1","key":"150_CR33","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0020-0190(82)90139-9","volume":"14","author":"K.I. Ko","year":"1982","unstructured":"Ko K.I.: Some observations on the probabilistic algorithms and NP-hard problems. Inf. Process. Lett. 14(1), 39\u201343 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"150_CR34","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/0022-0000(88)90037-2","volume":"36","author":"S. Zachos","year":"1988","unstructured":"Zachos S.: Probabilistic quantifiers and games. J. Comput. Syst. Sci. 36(3), 433\u2013451 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"150_CR35","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D. Roth","year":"1996","unstructured":"Roth D.: On the hardness of approximate reasoning. Artif. Intell. 82(1\u20132), 273\u2013302 (1996)","journal-title":"Artif. Intell."},{"key":"150_CR36","doi-asserted-by":"crossref","unstructured":"Cohen, S., Kimelfeld, B., Sagiv, Y.: Incorporating constraints in probabilistic XML. In: Proceedings of the 27th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 109\u2013118. ACM Press, New York (2008)","DOI":"10.1145\/1376916.1376933"},{"key":"150_CR37","doi-asserted-by":"crossref","unstructured":"Cohen, S., Kimelfeld, B., Sagiv, Y.: Running tree automata on probabilistic XML. In: Proceedings of the Twenty-Eigthth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 227\u2013236. ACM (2009)","DOI":"10.1145\/1559795.1559831"},{"key":"150_CR38","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/BFb0064872","volume":"453","author":"A.R. Meyer","year":"1975","unstructured":"Meyer A.R.: Weak monadic second-order theory of successor is not elementary recursive. Log. Colloquim 453, 132\u2013154 (1975)","journal-title":"Log. Colloquim"},{"key":"150_CR39","doi-asserted-by":"crossref","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. In: LICS, pp. 215\u2013224. IEEE Computer Society, USA (2002)","DOI":"10.1109\/LICS.2002.1029830"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-009-0150-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-009-0150-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-009-0150-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T15:05:05Z","timestamp":1559142305000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-009-0150-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,1]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["150"],"URL":"https:\/\/doi.org\/10.1007\/s00778-009-0150-5","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,1]]}}}