Talks and Poster Presentations (with Proceedings-Entry):
M. Frick, M. Grohe, C. Koch:
"Query Evaluation on Compressed Trees";
Talk: IEEE Symposium on Logic in Computer Science,
Ottawa, Kanada;
06-21-2003
- 06-25-2003; in: "Proceeding on LICS 2003",
IEEE,
(2003),
ISBN: 0-7695-1884-2;
188
- 197.
English 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 qiúeries 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 neww automata-theoretic formalism for querying trees and give algorithms for evaluating queries defined by such automata.
Online library catalogue of the TU Vienna:
http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04968355
Created from the Publication Database of the Vienna University of Technology.