{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T08:43:12Z","timestamp":1725698592085},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325885"},{"type":"electronic","value":"9783642325892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32589-2_61","type":"book-chapter","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T08:44:32Z","timestamp":1343810672000},"page":"705-717","source":"Crossref","is-referenced-by-count":3,"title":["Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity?"],"prefix":"10.1007","author":[{"given":"Filip","family":"Murlak","sequence":"first","affiliation":[]},{"given":"Micha\u0142","family":"Ogi\u0144ski","sequence":"additional","affiliation":[]},{"given":"Marcin","family":"Przyby\u0142ko","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"61_CR1","doi-asserted-by":"crossref","unstructured":"Amano, S., David, C., Libkin, L., Murlak, F.: On the Tradeoff between Mapping and Querying Power in XML Data Exchange. In: ICDT, pp. 155\u2013164 (2010)","DOI":"10.1145\/1804669.1804689"},{"key":"61_CR2","doi-asserted-by":"crossref","unstructured":"Amano, S., Libkin, L., Murlak, F.: XML schema mapping. In: PODS, pp. 33\u201342 (2009)","DOI":"10.1145\/1559795.1559801"},{"key":"61_CR3","doi-asserted-by":"crossref","unstructured":"Arenas, M., Libkin, L.: XML data exchange: consistency and query answering. J.\u00a0ACM\u00a055(2) (2008)","DOI":"10.1145\/1346330.1346332"},{"key":"61_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-642-31585-5_11","volume-title":"Automata, Languages, and Programming","author":"M. Benedikt","year":"2012","unstructured":"Benedikt, M., Bourhis, P., Senellart, P.: Monadic Datalog Containment. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol.\u00a07392, pp. 79\u201391. Springer, Heidelberg (2012)"},{"key":"61_CR5","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. J.\u00a0ACM\u00a055(2) (2008)","DOI":"10.1145\/1346330.1346333"},{"key":"61_CR6","doi-asserted-by":"crossref","unstructured":"Bex, G.J., Neven, F., Van den Bussche, J.: DTDs versus XML Schema: a practical study. In: WebDB, pp. 79\u201384 (2004)","DOI":"10.1145\/1017074.1017095"},{"issue":"4","key":"61_CR7","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/1862919.1862926","volume":"35","author":"H. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, H., Gelade, W., Martens, W.: Incremental XPath evaluation. ACM Trans. Database Syst.\u00a035(4), 29 (2010)","journal-title":"ACM Trans. Database Syst."},{"key":"61_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-540-75987-4_5","volume-title":"Database Programming Languages","author":"H. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Martens, W., Schwentick, T.: Conjunctive Query Containment over Trees. In: Arenas, M. (ed.) DBPL 2007. LNCS, vol.\u00a04797, pp. 66\u201380. Springer, Heidelberg (2007)"},{"key":"61_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-540-85238-4_10","volume-title":"Mathematical Foundations of Computer Science 2008","author":"H. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, H., Martens, W., Schwentick, T.: Optimizing Conjunctive Queries over Trees Using Schema Information. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 132\u2013143. Springer, Heidelberg (2008)"},{"key":"61_CR10","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Ko\u0142odziejczyk, L.A., Murlak, F.: Solutions in XML data exchange. In: ICDT, pp. 102\u2013113 (2011)","DOI":"10.1145\/1938551.1938567"},{"key":"61_CR11","doi-asserted-by":"crossref","unstructured":"ten Cate, B., Lutz, C.: The Complexity of Query Containment in Expressive Fragments of XPath 2.0. J.\u00a0ACM\u00a056(6), 1\u201348","DOI":"10.1145\/1568318.1568321"},{"key":"61_CR12","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC, pp. 77\u201390 (1977)","DOI":"10.1145\/800105.803397"},{"key":"61_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-540-85238-4_22","volume-title":"Mathematical Foundations of Computer Science 2008","author":"C. David","year":"2008","unstructured":"David, C.: Complexity of Data Tree Patterns over XML Documents. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 278\u2013289. Springer, Heidelberg (2008)"},{"key":"61_CR14","doi-asserted-by":"crossref","unstructured":"David, C., Libkin, L., Murlak, F.: Certain answers for XML queries. In: PODS, pp. 191\u2013202 (2010)","DOI":"10.1145\/1807085.1807112"},{"key":"61_CR15","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.tcs.2004.10.033","volume":"336","author":"R. Fagin","year":"2005","unstructured":"Fagin, R., Kolaitis, P., Miller, R., Popa, L.: Data exchange: semantics and query answering. Theor. Comp. S.\u00a0336, 89\u2013124 (2005)","journal-title":"Theor. Comp. S."},{"key":"61_CR16","first-page":"238","volume":"53","author":"G. Gottlob","year":"2006","unstructured":"Gottlob, G., Koch, C., Schulz, K.: Conjunctive queries over trees. J.\u00a0ACM\u00a053, 238\u2013272 (2006)","journal-title":"J.\u00a0ACM"},{"key":"61_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-540-24607-7_3","volume-title":"Database Programming Languages","author":"J. Hidders","year":"2004","unstructured":"Hidders, J.: Satisfiability of XPath Expressions. In: Lausen, G., Suciu, D. (eds.) DBPL 2003. LNCS, vol.\u00a02921, pp. 21\u201336. Springer, Heidelberg (2004)"},{"key":"61_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-642-03793-1_5","volume-title":"Database Programming Languages","author":"Y. Ishihara","year":"2009","unstructured":"Ishihara, Y., Morimoto, T., Shimizu, S., Hashimoto, K., Fujiwara, T.: A Tractable Subclass of DTDs for XPath Satisfiability with Sibling Axes. In: Gardner, P., Geerts, F. (eds.) DBPL 2009. LNCS, vol.\u00a05708, pp. 68\u201383. Springer, Heidelberg (2009)"},{"key":"61_CR19","doi-asserted-by":"crossref","unstructured":"Lenzerini, M.: Data integration: a theoretical perspective. In: PODS, pp. 233\u2013246 (2002)","DOI":"10.1145\/543613.543644"},{"key":"61_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-540-24741-8_28","volume-title":"Advances in Database Technology - EDBT 2004","author":"M. Marx","year":"2004","unstructured":"Marx, M.: XPath with Conditional Axis Relations. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., B\u00f6hm, K. (eds.) EDBT 2004. LNCS, vol.\u00a02992, pp. 477\u2013494. Springer, Heidelberg (2004)"},{"issue":"1","key":"61_CR21","first-page":"2","volume":"51","author":"G. Miklau","year":"2004","unstructured":"Miklau, G., Suciu, M.: Containment and equivalence for a fragment of XPath. J.\u00a0ACM\u00a051(1), 2\u201345 (2004)","journal-title":"J.\u00a0ACM"},{"issue":"4","key":"61_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1111627.1111631","volume":"5","author":"M. Murata","year":"2005","unstructured":"Murata, M., Lee, D., Mani, M., Kawaguchi, K.: Taxonomy of XML schema languages using formal language theory. ACM Transactions on Internet Technology\u00a05(4), 1\u201345 (2005)","journal-title":"ACM Transactions on Internet Technology"},{"issue":"3","key":"61_CR23","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/601858.601869","volume":"31","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata Theory for XML Researchers. SIGMOD Record\u00a031(3), 39\u201346 (2002)","journal-title":"SIGMOD Record"},{"issue":"3","key":"61_CR24","first-page":"1","volume":"2","author":"F. Neven","year":"2006","unstructured":"Neven, F., Schwentick, T.: On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logical Meth. in Comp. Sci.\u00a02(3), 1\u201330 (2006)","journal-title":"Logical Meth. in Comp. Sci."},{"key":"61_CR25","series-title":"Lecture Notes in Computer Science","first-page":"297","volume-title":"Database Theory - ICDT 2003","author":"P.T. Wood","year":"2002","unstructured":"Wood, P.T.: Containment for XPath Fragments under DTD Constraints. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol.\u00a02572, pp. 297\u2013311. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32589-2_61.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:08:16Z","timestamp":1620130096000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32589-2_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325885","9783642325892"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32589-2_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}