On the complexity of tree pattern containment with arithmetic comparisons

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

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2011-08, Vol.111 (15), p.754-760
Main Authors: Afrati, Foto N., Cohen, Sara, Kuper, Gabriel
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Arithmetic
Arithmetic comparisons
Combinatorics
Combinatorics. Ordered structures
Comparative analysis
Complexity
Computer science
control theory
systems
Containment
Decision trees
Exact sciences and technology
Fragmentation
Graph theory
Information systems. Data bases
Mathematical problems
Mathematics
Memory organisation. Data processing
Miscellaneous
Query containment
Query processing
Sciences and techniques of general use
Software
Studies
Theoretical computing
Tree patterns
Trees
XPath queries
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Π 2 P -complete in the general case, but remains co-NP complete for tree patterns with left semi-interval (, ⩾, =) attribute constraints. ► Query containment for tree patterns with arithmetic comparisons is studied. ► Query containment is Π 2 P -complete in the general case. ► For left (or right) semi-interval constraints, query containment is NP-complete.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2011.04.014