Querying tree-structured data using dimension graphs

Dimitri Theodoratos, Theodore Dalamagas

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

Abstract

Tree structures provide a popular means to organize the information on the Web. Taxonomies of thematic categories, concept hierarchies, e-commerce product catalogs are examples of such structures. Querying multiple data sources that use tree structures to organize their data is a challenging issue due to name mismatches, structural differences and structural inconsistencies that occur in such structures, even for a single knowledge domain. In this paper, we present a method to query tree-structured data. We introduce dimensions which are sets of semantically related nodes in tree structures. Based on dimensions, we suggest dimension graphs. Dimension graphs can be automatically extracted from trees and abstract their structural information. They are semantically rich constructs that provide query guidance to pose and evaluate queries on trees. We design a query language to query tree-structured data. A key feature of this language is that queries are not restricted by the structure of the trees. We present a technique for evaluating queries and we provide necessary and sufficient conditions for checking query unsatisfiability. We also show how dimension graphs can be used to query multiple trees in the presence of structural differences and inconsistencies.

Original languageEnglish (US)
Pages (from-to)201-215
Number of pages15
JournalLecture Notes in Computer Science
Volume3520
DOIs
StatePublished - 2005
Event17th International Conference on Advanced Information Systems Engineering, CAiSE 2005 - Porto, Portugal
Duration: Jun 13 2005Jun 17 2005

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this