Containment of pattern-based queries over data trees

We study static analysis, in particular the containment prob-lem, for analogs of conjunctive queries over XML docu-ments. The problem has been studied for queries based on arbitrary patterns, not necessarily following the tree struc-ture 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 conjunc-tive 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