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.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