Containment of partially specified tree-pattern queries in the presence of dimension graphs

Dimitri Theodoratos, Pawel Placek, Theodore Dalamagas, Stefanos Souldatos, Timos Sellis

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Nowadays, huge volumes of data are organized or exported in tree-structured form. 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 consider a query language that allows the partial specification of a tree pattern. Queries in this language range from structureless keyword-based queries to completely specified tree patterns. To support the evaluation of partially specified 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 presence of dimension graphs and we provide necessary and sufficient conditions for query containment. As checking query containment can be expensive, we suggest two heuristic approaches for query containment in the presence of dimension graphs. Our approaches are based on extracting structural information from the dimension graph that can be added to the queries while preserving equivalence with respect to the dimension graph. We considered both cases: extracting and storing different types of structural information in advance, and extracting information on-the-fly (at query time). Both approaches are implemented, validated, and compared through experimental evaluation.

Original languageEnglish (US)
Pages (from-to)233-254
Number of pages22
JournalVLDB Journal
Issue number1
StatePublished - Jan 2009

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Hardware and Architecture


  • Partial tree-pattern query
  • Query containment
  • Tree-structured data
  • XML


Dive into the research topics of 'Containment of partially specified tree-pattern queries in the presence of dimension graphs'. Together they form a unique fingerprint.

Cite this