Monadic Datalog and the Expressive Power of Languages for Web Information Extraction
Authors:
Preprint
Abstract
Research on information extraction from Web pages (wrapping) has seen much activity in recent times (particularly systems implementations), but little work has been done on formally studying the expressiveness of the formalisms proposed or on the theoretical foundations of wrapping. In this paper, we first study monadic datalog as a wrapping language (over ranked or unranked tree structures). We show that this simple language is equivalent to full monadic second order logic (MSO) in its ability to specify wrappers. We believe that MSO has the right expressiveness required for Web information extraction and thus propose MSO as a yardstick for evaluating and comparing wrappers. Along the way, several other results on the complexity of the query evaluation and query containment problems for monadic datalog over trees are established. Using the above results, we study the kernel fragment Elog- of the Elog wrapping language used in the Lixto system (a visual wrapper generator). The striking fact here is that Elog- exactly captures MSO, yet is easier to use. Indeed, programs in this language can be entirely visually specified. We also formally compare Elog to other wrapping languages proposed in the literature.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Introduction to automata theory, languages, and computation, 2nd editionACM SIGACT News, 2001
- Building intelligent Web applications using lightweight wrappersData & Knowledge Engineering, 2001
- Caterpillars: a context specification techniqueMarkup Languages: Theory and Practice, 2000
- Managing semistructured data with FLORID: A deductive object-oriented perspectiveInformation Systems, 1998
- Automata on Infinite Objects1990
- LTUR: a simplified linear-time unit resolution algorithm for horn formulae and computer implementationInformation Processing Letters, 1988
- Linear-time algorithms for testing the satisfiability of propositional horn formulaeThe Journal of Logic Programming, 1984
- The theory of joins in relational databasesACM Transactions on Database Systems, 1979
- Computational problems related to the design of normal form relational schemasACM Transactions on Database Systems, 1979
- Generalized finite automata theory with an application to a decision problem of second-order logicTheory of Computing Systems, 1968