[Back]

G. Gottlob, C. Koch:
"Monadic Datalog and the Expressive Power of Languages for Web Information Extraction.";
Talk: Twenty-first ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002), Madison, Wisconsin, USA (invited); 2002-06-03 - 2002-06-06; in: "Proceedings of the Twenty-first ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems", S. Abiteboul (ed.); (2002), ISBN: 1-58113-507-6; 17 - 28.

Research on information extraction from Web pages (wrapping) has seen much activity in recent times (particularly systems implementation), 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). Using prvious work by Neven and Schwentick, 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.
Using the above result, 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 visally specified. We also formally compare Elog to other wrapping languages proposed in the literature.