In this paper we investigate the complexity of query containment problem for tree patterns (which express a fragment of XPath) with arbitrary arithmetic comparisons. We assume that attributes take values from a totally ordered domain and allow constraints that involve arithmetic comparisons. We show that the containment problem is -complete in the general case, but remains co-NP complete for tree patterns with left semi-interval (<, ⩽, =) or right semi-interval (>, ⩾, =) attribute constraints.

On the complexity of tree pattern containment with arithmetic comparisons

Kuper, Gabriel Mark
2011-01-01

Abstract

In this paper we investigate the complexity of query containment problem for tree patterns (which express a fragment of XPath) with arbitrary arithmetic comparisons. We assume that attributes take values from a totally ordered domain and allow constraints that involve arithmetic comparisons. We show that the containment problem is -complete in the general case, but remains co-NP complete for tree patterns with left semi-interval (<, ⩽, =) or right semi-interval (>, ⩾, =) attribute constraints.
2011
15
F., Afrati; S., Cohen; Kuper, Gabriel Mark
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0020019011001207-main.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 198.23 kB
Formato Adobe PDF
198.23 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/34894
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact