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.