Evaluation of Queries on Tree-Structured Data using Dimension Graphs∗

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 chal-lenging 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. Di-mension graphs are semantically rich constructs that ab-stract 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 irregu-larities. Value trees and their dimension graphs are repre-sented as XML documents. We present a method for trans-forming queries to XPath expressions to be evaluated on the XML documents. We also provide conditions for identify-ing 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 ap-proach. 1