Efficient evaluation of generalized tree-pattern queries with same-path constraints

Xiaoying Wu, Dimitri Theodoratos, Stefanos Souldatos, Theodore Dalamagas, Timos Sellis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


Querying XML data is based on the specification of structural patterns which in practice are formulated using XPath. Usually, these structural patterns are in the form of trees (Tree-Pattern Queries - TPQs). Requirements for flexible querying of XML data including XML data from scientific applications have motivated recently the introduction of query languages that are more general and flexible than TPQs. These query languages correspond to a fragment of XPath larger than TPQs for which efficient non-main-memory evaluation algorithms are not known. In this paper, we consider a query language, called Partial Tree-Pattern Query (PTPQ) language, which generalizes and strictly contains TPQs. PTPQs represent a broad fragment of XPath which is very useful in practice. We show how PTPQs can be represented as directed acyclic graphs augmented with same-path constraints. We develop an original polynomial time holistic algorithm for PTPQs under the inverted list evaluation model. To the best of our knowledge, this is the first algorithm to support the evaluation of such a broad structural fragment of XPath. We provide a theoretical analysis of our algorithm and identify cases where it is asymptotically optimal. In order to assess its performance, we design two other techniques that evaluate PTPQs by exploiting the state-of-the-art existing algorithms for smaller classes of queries. An extensive experimental evaluation shows that our holistic algorithm outperforms the other ones.

Original languageEnglish (US)
Title of host publicationScientific and Statistical Database Management - 21st International Conference, SSDBM 2009, Proceedings
Number of pages19
StatePublished - 2009
Event21st International Conference on Scientific and Statistical Database Management, SSDBM 2009 - New Orleans, LA, United States
Duration: Jun 2 2009Jun 4 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5566 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other21st International Conference on Scientific and Statistical Database Management, SSDBM 2009
Country/TerritoryUnited States
CityNew Orleans, LA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient evaluation of generalized tree-pattern queries with same-path constraints'. Together they form a unique fingerprint.

Cite this