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 recently (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 over trees as a wrapping language. We show that this simple language is equivalent to 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 propose MSO as a yardstick for evaluating and comparing wrappers. Along the way, several other results on the complexity of query evaluation and query containment for monadic datalog over trees are established, and a simple normal form for this language is presented. Using the above results, we subsequently study the kernel fragment Elog$^-$ of the Elog wrapping language used in the Lixto system (a visual wrapper generator). Curiously, Elog$^-$ exactly captures MSO, yet is easier to use. Indeed, programs in this language can be entirely visually specified.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Expressiveness of structured document query languages based on attribute grammarsJournal of the ACM, 2002
- Introduction to automata theory, languages, and computation, 2nd editionACM SIGACT News, 2001
- Building intelligent Web applications using lightweight wrappersData & Knowledge Engineering, 2001
- 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