Query processing techniques for XML data have focused mainly on tree-pattern queries (TPQs). However, the need for querying XML data sources whose structure is very complex or not fully known to the user, and the need to integrate multiple XML data sources with different structures have driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In order to implement the processing of such languages in current DBMSs, their containment problem has to be efficiently solved.

The wide adoption of XML has increased the interest of the database community on tree-structured data management techniques. Querying capabilities are provided through tree-pattern queries. The need for querying tree-structured data sources when their structure is not fully known, and the need to integrate multiple data sources with different tree structures have driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In this paper, we use a query language which allows partial tree-pattern queries (PTPQs). The structure in a PTPQ can be flexibly specified fully, partially or not at all. To evaluate a PTPQ, we exploit index graphs which generate an equivalent set of "complete" tree-pattern queries.In order to process PTPQs, we need to efficiently solve the PTPQ satisfiability and containment problems. These problems become more complex in the context of PTPQs because the partial specification of the structure allows new, non-trivial, structural expressions to be derived from those explicitly specified in a PTPQ. We address the problem of PTPQ satisfiability and containment in the absence and in the presence of index graphs, and we provide necessary and sufficient conditions for each case. To cope with the high complexity of PTPQ containment in the presence of index graphs,we study a family of heuristic approaches for PTPQ containment based on structural information extracted from the index graph in advance and on-the-fly. We implement our approaches and we report on their extensive experimental evaluation and comparison.

Nowadays, huge volumes of data, including scientific data, are organized or exported in tree-structured form. Querying capabilities are provided through tree-pattern queries. The need for integrating multiple data sources with different tree structures has driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In this paper we adopt a query language with partially specified tree-pattern queries. A central feature of this type of queries is that the structure can be specified fully, partially, or not at all in a query. Important issues in query optimization require solving the query containment problem. We study the containment problem for partially specified tree-pattern queries. To support the evaluation of such queries, we use semantically rich constructs, called dimension graphs, which abstract structural information of the tree-structured data. We address the problem of query containment in the absence (absolute query containment) and in the presence (relative query containment) of dimension graphs, and we provide necessary and sufficient conditions for each type of query containment. We suggest a technique for relative query containment checking based on structural information extracted in advance from the dimension graph. Our approach is implemented and validated through extensive experimental evaluation.