Evaluation of queries on tree-structured data using dimension graphs

Theodore Dalamagas, Antonis Koufopoulos, Dimitri Theodoratos, Vincent Oria

Research output: Contribution to journalConference articlepeer-review

3 Scopus citations


The recent proliferation of XML-based standards and technologies for managing data on the Web demonstrates the need for effective and efficient management of tree-structured data. Querying tree-structured data is a challenging issue due to the diversity of the structural aspect in the same or in different trees. In this paper, we show how to evaluate queries on tree-structured data, called value trees. The formulation of these queries does not depend on the structure of a particular value tree. Our approach exploits semantic information provided by dimension graphs. Dimension graphs are semantically rich constructs that abstract the structural information of the value trees. We show how dimension graphs can be used to query efficiently value trees in the presence of structural differences and irregularities. Value trees and their dimension graphs are represented as XML documents. We present a method for transforming queries to XPath expressions to be evaluated on the XML documents. We also provide conditions for identifying strongly and weakly unsatisfiable queries. Finally, we conducted various experiments to compare our method for evaluating queries with one that does not exploit dimension graphs. Our results demonstrate the superiority of our approach.

Original languageEnglish (US)
Article number1540896
Pages (from-to)65-74
Number of pages10
JournalProceedings of the International Database Engineering and Applications Symposium, IDEAS
Issue numberJanuary
StatePublished - 2005
Event9th International Database Engineering and Application Symposium, IDEAS 2005 - Montreal, Canada
Duration: Jul 25 2005Jul 27 2005

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Engineering


Dive into the research topics of 'Evaluation of queries on tree-structured data using dimension graphs'. Together they form a unique fingerprint.

Cite this