Monadic Queries over Tree Structured Data

Monadic query languages over trees currently receive considerable interest in the database community, as the problem of selecting nodes from a tree is the most basic and widespread database query problem in the context of XML. In the first part of this talk we discuss some particular query languages such as monadic datalog and XPATH and present some algorithms and complexity results for this languages. In the second part we will illustrate the use of monadic logic as a tool for Web information extraction and will give a survey and demo of the Lixto system (see www.lixto.com). This system is used for extracting structured data from HTML Web pages, by defining patterns on such pages and annotating data items with XML tags. This talk describes joint work with Robert Baumgartner, Segio Flesca, Marcus Herzog, and Christoph Koch.