Monadic datalog and the expressive power of languages for web information extraction

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). Using previous 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 visually specified. We also formally compare Elog to other wrapping languages proposed in the literature.

REFERENCES

• 1: S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web. Morgan Kaufmann Publishers, 2000.
• 2: Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.122-133, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263676]
• 3: Gustavo O. Arocena , Alberto O. Mendelzon, WebOQL: Restructuring Documents, Databases, and Webs, Proceedings of the Fourteenth International Conference on Data Engineering, p.24-33, February 23-27, 1998
• 4: Gustavo O. Arocena , Alberto O. Mendelzon , George A. Mihaila, Applications of a Web query language, Selected papers from the sixth international conference on World Wide Web, p.1305-1316, September 1997, Santa Clara, California, United States
• 5: Paolo Atzeni , Giansalvatore Mecca, Cut and paste, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.144-153, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263678]
• 6: F. Azavant. Personal communication, Oct. 2001.
• 7: Robert Baumgartner , Sergio Flesca , Georg Gottlob, Declarative Information Extraction, Web Crawling, and Recursive Wrapping with Lixto, Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning, p.21-41, September 17-19, 2001
• 8: Robert Baumgartner , Sergio Flesca , Georg Gottlob, Visual Web Information Extraction with Lixto, Proceedings of the 27th International Conference on Very Large Data Bases, p.119-128, September 11-14, 2001
• 9: A. Brüggemann-Klein and D. Wood. "Regular Tree Languages over Non-ranked Alphabets". Unpublished manuscript, 1998.
• 10: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• 11: Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 12: Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001 [doi>10.1145/502807.502810]
• 13: W. F. Dowling and J. H. Gallier. "Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae". Journal of Logic Programming,1(3):267-284, 1984.
• 14: M. Fernandez, J. Siméon, P. Wadler (eds.), S. Cluet, A. Deutsch, D. F. A. Levy, D. Maier, J. M. J. Robie, D. Suciu, and J. Widom. "XML Query Languages: Experiences and Exemplars", 1999. http://www-db.research.bell-labs.com/user/simeon/xquery.html.
• 15: Jörg Flum , Markus Frick , Martin Grohe, Query Evaluation via Tree-Decompositions, Proceedings of the 8th International Conference on Database Theory, p.22-38, January 04-06, 2001
• 16: Ferenc Gécseg , Magnus Steinby, Tree languages, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 17: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 18: Alberto H. F. Laender , Berthier Ribeiro-Neto , Altigran S. da Silva, DEByE - Date extraction by example, Data & Knowledge Engineering, v.40 n.2, p.121-154, February 2002 [doi>10.1016/S0169-023X(01)00047-7]
• 19: Laks V. S. Lakshmanan , Iyer N. Subramanian , Fereidoon Sadri, A Declarative Language for Querying and Restructuring the Web, Proceedings of the 6th International Workshop on Research Issues in Data Engineering (RIDE '96) Interoperability of Nontraditional Database Systems, p.12, February 26-27, 1996
• 20: L. Liu, C. Pu, and W. Han. "XWRAP: An XML-Enabled Wrapper Construction System for Web Information Sources", In Proceedings of the 16th International Conference on Data Engineering, 1998.
• 21: Bertram Ludäscher , Rainer Himmeröder , Georg Lausen , Wolfgang May , Christian Schlepphorst, Managing semistructured data with florid: a deductive object-oriented perspective, Information Systems, v.23 n.9, p.589-613, Dec. 1998
• 22: M. Minoux, LTUR: a simplified linear-time unit resolution algorithm for Horn formulae and computer implementation, Information Processing Letters, v.29 n.1, p.1-12, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90124-X]
• 23: I. Muslea, S. Minton, and C. Knoblock. "STALKER: Learning Extraction Rules for Semistructured, Web-based Information Sources", 1998.
• 24: Frank Neven , Thomas Schwentick, Expressive and efficient pattern languages for tree-structured data (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.145-156, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335217]
• 25: Frank Neven , Thomas Schwentick, Query automata over finite trees, Theoretical Computer Science, v.275 n.1-2, p.633-674, March 28 2002 [doi>10.1016/S0304-3975(01)00301-2]
• 26: C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• 27: Yannis Papakonstantinou , Ashish Gupta , Hector Garcia-Molina , Jeffrey D. Ullman, A Query Translation Scheme for Rapid Implementation of Wrappers, Proceedings of the Fourth International Conference on Deductive and Object-Oriented Databases, p.161-186, December 04-07, 1995
• 28: Arnaud Sahuguet , Fabien Azavant, Building intelligent web applications using lightweight wrappers, Data & Knowledge Engineering, v.36 n.3, p.283-316, March 2001 [doi>10.1016/S0169-023X(00)00051-3]
• 29: Andrew Szilard , Sheng Yu , Kaizhong Zhang , Jeffrey Shallit, Characterizing Regular Languages with Polynomial Densities, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.494-503, August 24-28, 1992
• 30: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 31: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 32: World Wide Web Consortium. http://www.w3c.org/tr/xpath/.
• 33: Sheng Yu, Regular languages, Handbook of formal languages, vol. 1: word, language, grammar, Springer-Verlag New York, Inc., New York, NY, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

          Nouns: Web View

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Design, Languages, Theory