Evaluation of partial path queries on XML data

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

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

8 Scopus citations


XML query languages typically allow the specification of structural patterns of elements. Finding the occurrences of such patterns in an XML tree is the key operation in XML query processing. Many algorithms have been presented for this operation. These algorithms focus mainly on the evaluation of path-pattern or tree-pattern queries. In this paper, we define a partial path-pattern query language, and we address the problem of its efficient evaluation on XML data. In order to process partial path-pattern queries, we introduce a set of sound and complete inference rules to characterize structural relationship derivation. We provide necessary and sufficient conditions for detecting query unsatisfi- ability and node redundancy. We show how partial path-pattern queries can be equivalently put in a canonical directed acyclic graph form. We developed two stack-based algorithms for the evaluation of partial path-pattern queries, Partial MJ and Partial Path Stack. Partial MJ computes answers to the query by merge-joining the results of the root-to-leaf paths of a spanning tree of the query. Partial- PathStack exploits a topological order of the nodes of the query graph to match the query pattern as a whole to the XML tree. The experimental evaluation of our algorithms shows that Partial Path Stack is independent of intermediate results and largely outperforms Partial MJ.

Original languageEnglish (US)
Title of host publicationCIKM 2007 - Proceedings of the 16th ACM Conference on Information and Knowledge Management
Number of pages10
StatePublished - 2007
Event16th ACM Conference on Information and Knowledge Management, CIKM 2007 - Lisboa, Portugal
Duration: Nov 6 2007Nov 9 2007

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings


Other16th ACM Conference on Information and Knowledge Management, CIKM 2007

All Science Journal Classification (ASJC) codes

  • General Decision Sciences
  • General Business, Management and Accounting


  • Partial path-pattern query
  • Query evaluation
  • Tree-structured data


Dive into the research topics of 'Evaluation of partial path queries on XML data'. Together they form a unique fingerprint.

Cite this