Change search
ReferencesLink to record
Permanent link

Direct link
Validity of Tree Pattern Queries with Respect to Schema Information
Umeå University, Faculty of Science and Technology, Department of Computing Science.
University of Bayreuth.
Technical University of Dortmund.
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)
Abstract [en]

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
National Category
Computer Science
Research subject
Computer Science
URN: urn:nbn:se:umu:diva-79707DOI: 10.1007/978-3-642-40313-2_17ISBN: 978-3-642-40312-5OAI: diva2:644018
38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, 26 August 2013 through 30 August 2013, Klosterneuburg
Swedish Research Council, 621-2011-6080
Available from: 2013-08-29 Created: 2013-08-29 Last updated: 2013-12-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Björklund, Henrik
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 39 hits
ReferencesLink to record
Permanent link

Direct link