umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Conjunctive query containment over trees using schema information
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
2018 (engelsk)Inngår i: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 55, nr 1, s. 17-56Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
SPRINGER , 2018. Vol. 55, nr 1, s. 17-56
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-144935DOI: 10.1007/s00236-016-0282-1ISI: 000424053100002OAI: oai:DiVA.org:umu-144935DiVA, id: diva2:1185351
Tilgjengelig fra: 2018-02-23 Laget: 2018-02-23 Sist oppdatert: 2018-06-09bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Björklund, Henrik

Søk i DiVA

Av forfatter/redaktør
Björklund, Henrik
Av organisasjonen
I samme tidsskrift
Acta Informatica

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 716 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf