ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Eighteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2003)

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

Authors: Markus Frick Martin Grohe Christoph Koch


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.


    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}

Last modified: 2021-11-1017:16
Sam Staton