Personal tools
You are here: Home Events Abstract Archives 2003 Query Evaluation on Compressed Trees

Query Evaluation on Compressed Trees

Christoph Koch LFCS 4pm Tuesday 28th January 2003 Room 2511, JCMB, King's Buildings

We study 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 currently a major research issue. We give algorithms and complexity results for the evaluation of XPath, monadic datalog queries, and monadic second-order logic over trees. We also provide preliminary experimental results demonstrating the efficiency of our techniques on large XML corpora, which are very promising.

Joint work with Peter Buneman, Markus Frick and Martin Grohe.

Document Actions