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
Conjunctive query containment over trees using schema information
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2018 (English)In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 55, no 1, p. 17-56Article in journal (Refereed) Published
Abstract [en]

We study the containment, satisfiability, and validity problems for conjunctive queries over trees with respect to a schema. We show that conjunctive query containment and validity are 2EXPTIME -complete with respect to a schema, in both cases where the schema is given as a DTD or as a tree automaton. Furthermore, we show that satisfiability for conjunctive queries with respect to a schema can be decided in NP . The problem is NP -hard already for queries using only one kind of axis. Finally, we consider conjunctive queries that can test for equalities and inequalities of data values. Here, satisfiability and validity are decidable, but containment is undecidable, even without schema information. On the other hand, containment with respect to a schema becomes decidable again if the "larger" query is not allowed to use both equalities and inequalities.

Place, publisher, year, edition, pages
SPRINGER , 2018. Vol. 55, no 1, p. 17-56
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-144935DOI: 10.1007/s00236-016-0282-1ISI: 000424053100002OAI: oai:DiVA.org:umu-144935DiVA, id: diva2:1185351
Available from: 2018-02-23 Created: 2018-02-23 Last updated: 2018-06-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Björklund, Henrik

Search in DiVA

By author/editor
Björklund, Henrik
By organisation
Department of Computing Science
In the same journal
Acta Informatica
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 379 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