{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:32Z","timestamp":1740109412579,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T00:00:00Z","timestamp":1494201600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"crossref","award":["2013\/11\/D\/ST6\/03075"],"award-info":[{"award-number":["2013\/11\/D\/ST6\/03075"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s00224-017-9771-z","type":"journal-article","created":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T04:50:16Z","timestamp":1494219016000},"page":"941-976","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reasoning about integrity constraints for tree-structured data"],"prefix":"10.1007","volume":"62","author":[{"given":"Wojciech","family":"Czerwi\u0144ski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"David","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0989-3717","authenticated-orcid":false,"given":"Filip","family":"Murlak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Parys","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,8]]},"reference":[{"key":"9771_CR1","doi-asserted-by":"crossref","unstructured":"Arenas, M., Barcel\u00f3, P., Libkin, L., Murlak, F.: Foundations of data exchange. Cambridge University Press (2014)","DOI":"10.1017\/CBO9781139060158"},{"issue":"3","key":"9771_CR2","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1137\/050646895","volume":"38","author":"M Arenas","year":"2008","unstructured":"Arenas, M., Fan, W., Libkin, L.: On the complexity of verifying consistency of XML specifications. SIAM J. Comput. 38(3), 841\u2013880 (2008)","journal-title":"SIAM J. Comput."},{"key":"9771_CR3","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1145\/974750.974757","volume":"29","author":"M Arenas","year":"2004","unstructured":"Arenas, M., Libkin, L.: A normal form for XML documents. ACM Trans. Database Syst. 29, 195\u2013232 (2004)","journal-title":"ACM Trans. Database Syst."},{"key":"9771_CR4","doi-asserted-by":"crossref","unstructured":"Arenas, M., Libkin, L.: XML data exchange: Consistency and query answering. J. ACM, 55(2) (2008)","DOI":"10.1145\/1346330.1346332"},{"key":"9771_CR5","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. J. ACM, 55(2) (2008)","DOI":"10.1145\/1346330.1346333"},{"key":"9771_CR6","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, H., Martens, W., Schwentick, T.: Conjunctive query containment over trees using schema information. Acta Informatica, 1\u201340 (2016)","DOI":"10.1007\/s00236-016-0282-1"},{"key":"9771_CR7","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Murlak, F., Witkowski, A.: Containment of monadic datalog programs via bounded clique-width. In: Proceedings of the ICALP 2015, pp. 427\u2013439 (2015)","DOI":"10.1007\/978-3-662-47666-6_34"},{"issue":"3","key":"9771_CR8","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/1516512.1516515","volume":"56","author":"M Boja\u0144czyk","year":"2009","unstructured":"Boja\u0144czyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. J. ACM 56(3), 13:1\u201313:48 (2009)","journal-title":"J. ACM"},{"key":"9771_CR9","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: Proceedings of the STOC 1977, pp. 77\u201390 (1977)","DOI":"10.1145\/800105.803397"},{"issue":"2","key":"9771_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1-3","key":"9771_CR11","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101(1-3), 77\u2013114 (2000)","journal-title":"Discret. Appl. Math."},{"key":"9771_CR12","doi-asserted-by":"crossref","unstructured":"David, C., Gheerbrant, A., Libkin, L., Martens, W.: Containment of pattern-based queries over data trees. In: Proceedings of the ICDT 2013, pp. 201\u2013212 (2013)","DOI":"10.1145\/2448496.2448521"},{"key":"9771_CR13","unstructured":"David, C., Hofman, P., Murlak, F., Pilipczuk, M.: Synthesizing transformations from XML schema mappings. In: Proceedings of the ICDT 2014, pp. 61\u201371 (2014)"},{"issue":"1","key":"9771_CR14","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.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answering. Theor. Comput. Sci. 336(1), 89\u2013124 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9771_CR15","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1145\/1114244.1114249","volume":"30","author":"R Fagin","year":"2005","unstructured":"Fagin, R., Kolaitis, P.G., Popa, L., Tan, W.C.: Composing schema mappings: Second-order dependencies to the rescue. ACM Trans. Database Syst. 30(4), 994\u20131055 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"9771_CR16","doi-asserted-by":"crossref","unstructured":"Fagin, R., Vardi, M.Y.: The theory of data dependencies - a survey. In: Mathematics of information processing, volume 34 of proceedings of symposia in applied mathematics, pp. 19\u201371. American Mathematical Society, Providence, Rhode Island (1986)","DOI":"10.1090\/psapm\/034\/846853"},{"key":"9771_CR17","doi-asserted-by":"crossref","unstructured":"Figueira, D.: Alternating register automata on finite words and trees. Logical Methods Comput. Sci. 8(1), 2012","DOI":"10.2168\/LMCS-8(1:22)2012"},{"key":"9771_CR18","unstructured":"Gao, S., Sperberg-McQueen, C.M., Thompson, H.S., Mendelsohn, N., Beech, D., Maloney, M.: W3C XML Schema Definition Language (XSD) 1.1, Part 1: Structures. Technical report, World Wide Web Consortium, April (2009)"},{"key":"9771_CR19","doi-asserted-by":"crossref","unstructured":"Gogacz, T., Marcinkowski, J.: All-instances termination of chase is undecidable. In: Proceedings of the ICALP 2014, pp. 293\u2013304 (2014)","DOI":"10.1007\/978-3-662-43951-7_25"},{"key":"9771_CR20","doi-asserted-by":"crossref","unstructured":"Gogacz, T., Marcinkowski, J.: Red spider meets a rainworm: query finite determinacy is undecidable. In: Proceedings of the PODS 2016, pp. 121\u2013134 (2016)","DOI":"10.1145\/2902251.2902288"},{"key":"9771_CR21","doi-asserted-by":"crossref","unstructured":"Hartmann, S., Link, S.: More functional dependencies for XML. In: Proceedings of the ADBIS 2003, pp. 355\u2013369 (2003)","DOI":"10.1007\/978-3-540-39403-7_27"},{"key":"9771_CR22","doi-asserted-by":"crossref","unstructured":"Hartmann, S., Link, S., Trinh, T.: Solving the implication problem for XML, functional dependencies with properties. In: Proceedings of the WoLLIC 2010, pp. 161\u2013175 (2010)","DOI":"10.1007\/978-3-642-13824-9_14"},{"issue":"3","key":"9771_CR23","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/1929954.1929956","volume":"12","author":"M Jurdzinski","year":"2011","unstructured":"Jurdzinski, M., Lazic, R.: Alternating automata on data trees and XPath satisfiability. ACM Trans. Comput. Logic 12(3), 19:1\u201319:21 (2011)","journal-title":"ACM Trans. Comput. Logic"},{"key":"9771_CR24","doi-asserted-by":"crossref","unstructured":"Lenzerini, M.: Data integration: A theoretical perspective. In: Proceedings of the PODS 2002, pp. 233\u2013246 (2002)","DOI":"10.1145\/543613.543644"},{"issue":"1","key":"9771_CR25","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/962446.962448","volume":"51","author":"G Miklau","year":"2004","unstructured":"Miklau, G., Suciu, D: Containment and equivalence for a fragment of XPath. J. ACM, 51(1), 2\u201345 (2004)","journal-title":"J. ACM,"},{"key":"9771_CR26","doi-asserted-by":"crossref","unstructured":"Neven, F., Schwentick, T.: On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Log. Meth. Comput. Sci., 2(3) (2006)","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"9771_CR27","unstructured":"Niewerth, M., Schwentick, T.: Reasoning XML constraints based on XML-to-relational mappings. In: Proceedings of the ICDT 2014, pp. 72\u201383 (2014)"},{"key":"9771_CR28","unstructured":"Vardi, M.Y.: Fundamentals of dependency theory. In: Borger, E. (ed.) Trends in theoretical computer science, pp. 171\u2013224. Computer Science Press (1987)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9771-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9771-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9771-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T13:00:53Z","timestamp":1692795653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9771-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,8]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["9771"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9771-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,5,8]]},"assertion":[{"value":"8 May 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}