Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Frick, M. Grohe, C. Koch:
"Query Evaluation on Compressed Trees";
Vortrag: IEEE Symposium on Logic in Computer Science,
Ottawa, Kanada;
21.06.2003
- 25.06.2003; in: "Proceeding on LICS 2003",
IEEE,
(2003),
ISBN: 0-7695-1884-2;
S. 188
- 197.
Kurzfassung englisch:
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-Bibliotheks-Katalog der TU Wien:
http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04968355
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.