Validity of Tree Pattern Queries with Respect to Schema Information
2013 (English)In: Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings / [ed] Krishnendu Chatterjee, Jiri Sgall, Springer: Springer Berlin/Heidelberg, 2013, 171-182 p.Conference paper (Refereed)
We prove that various containment and validity problems for tree pattern queries with respect to a schema are EXPTIME-complete. When one does not require the root of a tree pattern query to match the root of atree, validity of a non-branching tree pattern query with respect to a Relax NG schema or W3C XML Schema is already EXPTIME-hard when the query does not branch and uses only child axes. These hardness results already hold when the alphabet size is fixed. Validity with respect to a DTD is proved to be EXPTIME-hard already when the query only uses child axes and is allowed to branch only once.
Place, publisher, year, edition, pages
Springer: Springer Berlin/Heidelberg, 2013. 171-182 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 8087
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-79707DOI: 10.1007/978-3-642-40313-2_17ISBN: 978-3-642-40312-5OAI: oai:DiVA.org:umu-79707DiVA: diva2:644018
38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, 26 August 2013 through 30 August 2013, Klosterneuburg
FunderSwedish Research Council, 621-2011-6080