Paper: Query Evaluation on Compressed Trees (Extended Abstract) (at LICS 2003)

Authors: Markus Frick Martin Grohe Christoph Koch

Abstract

This paper studies the problem of evaluating unary (or node-selecting) queries on unranked trees compressed in a natural structure-preserving way, by the sharing of common subtrees. The motivation to study unary queries on unranked trees comes from the database field, where querying XML documents, which can be considered as unranked labelled trees, is an important task. We give algorithms and complexity results for the evaluation of XPath and monadic datalog queries. Furthermore, we propose a new automata-theoretic formalism for querying trees and give algorithms for evaluating queries defined by such automata.

BibTeX

  @InProceedings{FrickGroheKoch-QueryEvaluationonCo,
    author = 	 {Markus Frick and Martin Grohe and Christoph Koch},
    title = 	 {Query Evaluation on Compressed Trees (Extended Abstract)},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003)},
    year =	 {2003},
    month =	 {June}, 
    pages =      {188--197},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }