Paper Info
Title
Containment of pattern-based queries over data trees
Abstract
We study static analysis, in particular the containment problem, for analogs of conjunctive queries over XML documents. The problem has been studied for queries based on arbitrary patterns, not necessarily following the tree structure of documents. However, many applications force the syntactic shape of queries to be tree-like, as they are based on proper tree patterns. This renders previous results, crucially based on having non-tree-like features, inapplicable. Thus, we investigate static analysis of queries based on proper tree patterns. We go beyond simple navigational conjunctive queries in two ways: we look at unions and Boolean combinations of such queries as well and, crucially, all our queries handle data stored in documents, i.e., we deal with containment over data trees. We start by giving a general Πp2 upper bound on the containment of conjunctive queries and Boolean combinations for patterns that involve all types of navigation through documents. We then show matching hardness for conjunctive queries with all navigation, or their Boolean combinations with the simplest form of navigation. After that we look at cases when containment can be witnessed by homomorphisms of analogs of tableaux. These include conjunctive queries and their unions over child and next-sibling axes; however, we show that not all cases of containment can be witnessed by homomorphisms. We look at extending tree patterns used in queries in three possible ways: with wildcard, with schema information, and with data value comparisons. The first one is relatively harmless, the second one tends to increase complexity by an exponential, and the last one quickly leads to undecidability.
Year
DOI
Venue
2013
10.1145/2448496.2448521
ICDT
Keywords
Field
DocType
data value comparison,containment problem,data tree,conjunctive query,static analysis,tree structure,simple navigational conjunctive query,boolean combination,pattern-based query,proper tree pattern,tree pattern,graph databases,data exchange
Graph database,Wildcard,Conjunctive query,Data exchange,XML,Computer science,Static analysis,Theoretical computer science,Homomorphism,Tree structure
Conference
Citations 
PageRank 
References 
13
0.58
35
Authors
4
Name
Order
Citations
PageRank
Claire David128514.96
Amélie Gheerbrant21318.53
Leonid Libkin33446764.02
wim martens460929.78