umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8087
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-79707DOI: 10.1007/978-3-642-40313-2_17ISI: 000342994500017ISBN: 978-3-642-40312-5 (print)OAI: oai:DiVA.org:umu-79707DiVA: diva2:644018
Conference
38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, 26 August 2013 through 30 August 2013, Klosterneuburg
Funder
Swedish Research Council, 621-2011-6080
Available from: 2013-08-29 Created: 2013-08-29 Last updated: 2017-01-16Bibliographically 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 77 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf