The Lixto data extraction project: back and forth between theory and practice

ABSTRACT

We present the Lixto project, which is both a research project in database theory and a commercial enterprise that develops Web data extraction (wrapping) and Web service definition software. We discuss the project's main motivations and ideas, in particular the use of a logic-based framework for wrapping. Then we present theoretical results on monadic datalog over trees and on Elog, its close relative which is used as the internal wrapper language in the Lixto system. These results include both a characterization of the expressive power and the complexity of these languages. We describe the visual wrapper specification process in Lixto and various practical aspects of wrapping. We discuss work on the complexity of query languages for trees that was inseminated by our theoretical study of logic-based languages for wrapping. Then we return to the practice of wrapping and the Lixto Transformation Server, which allows for streaming integration of data extracted from Web pages. This is a natural requirement in complex services based on Web wrapping. Finally, we discuss industrial applications of Lixto and point to open problems for future study.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: R. Baumgartner, S. Eichholz, S. Flesca, G. Gottlob, and M. Herzog. Semantic Markup of News Items with Lixto, 2003.
• 3: 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
• 4: 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
• 5: R. Baumgartner, S. Flesca, G. Gottlob, and M. Herzog. "Building Dynamic Information Portals - A Case Study in the Agrarian Domain". In Proc. IS, 2002.
• 6: R. Baumgartner, M. Herzog, and G. Gottlob. "Visual Programming of Web Data Aggregation Applications". In Proc. IIWeb-03, 2003.
• 7: Stavros Cosmadakis , Haim Gaifman , Paris Kanellakis , Moshe Vardi, Decidable optimization problems for database logic programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.477-490, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62259]
• 8: 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
• 9: 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]
• 10: J. Doner. "Tree Acceptors and some of their Applications". Journal of Computer and System Sciences,4:406--451, 1970.
• 11: 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
• 12: Markus Frick , Martin Grohe , Christoph Koch, Query Evaluation on Compressed Trees (Extended Abstract), Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, p.188, June 22-25, 2003
• 13: E. Gold. "Language Identification in the Limit". Inform. Control, 10:447--474, 1967.
• 14: Georg Gottlob , Christoph Koch, Monadic datalog and the expressive power of languages for Web information extraction, Journal of the ACM (JACM), v.51 n.1, p.74-113, January 2004 [doi>10.1145/962446.962450]
• 15: G. Gottlob, C. Koch, and R. Pichler. "Efficient Algorithms for Processing XPath Queries". In Proc. VLDB 2002, Hong Kong, China, 2002.
• 16: Georg Gottlob , Christoph Koch , Reinhard Pichler, The complexity of XPath query evaluation, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.179-190, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773171]
• 17: G. Gottlob, C. Koch, and R. Pichler. "XPath Query Evaluation: Improving Time and Space Efficiency". In ICDE'03, Bangalore, India, Mar. 2003.
• 18: Georg Gottlob , Christoph Koch , Klaus U. Schulz, Conjunctive queries over trees, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055585]
• 19: Raymond Greenlaw , H. James Hoover , Walter L. Ruzzo, Limits to parallel computation: P-completeness theory, Oxford University Press, Inc., New York, NY, 1995
• 20: Marcus Herzog , Georg Gottlob, InfoPipes: A Flexible Framework for M-Commerce Applications, Proceedings of the Second International Workshop on Technologies for E-Services, p.175-186, September 14-15, 2001
• 21: C. Koch. "Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach". In Proc. VLDB 2003, pages 249--260, 2003.
• 22: R. Kosala, H. Blockeel, M. Bruynooghe, and J. V. den Bussche. "Information Extraction from Web Documents based on Local Unranked Tree Automaton Inference". In Proc. IJCAI, 2003.
• 23: N. Kushmerick, D. Weld, and R. Doorenbos. "Wrapper Induction for Information Extraction". In Proc. IJCAI, 1997.
• 24: 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]
• 25: XWRAP: An XML-Enabled Wrapper Construction System for Web Information Sources, Proceedings of the 16th International Conference on Data Engineering, p.611, February 28-March 03, 2000
• 26: http://www.lixto.com.
• 27: 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
• 28: Holger Meuss , Klaus U. Schulz , François Bry, Towards Aggregated Answers for Semistructured Data, Proceedings of the 8th International Conference on Database Theory, p.346-360, January 04-06, 2001
• 29: 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]
• 30: Mostrare project. www.grappa.univ-lille3.fr/mostrare/.
• 31: Ion Muslea , Steve Minton , Craig Knoblock, A hierarchical approach to wrapper induction, Proceedings of the third annual conference on Autonomous Agents, p.190-197, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301191]
• 32: 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]
• 33: Frank Neven , Jan Van Den Bussche, Expressiveness of structured document query languages based on attribute grammars, Journal of the ACM (JACM), v.49 n.1, p.56-100, January 2002 [doi>10.1145/505241.505245]
• 34: 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
• 35: 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]
• 36: Helmut Seidl , Thomas Schwentick , Anca Muscholl, Numerical document queries, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773169]
• 37: J. Thatcher and J. Wright. "Generalized Finite Automata Theory with an Application to a Decision Problem of Second-order Logic". Mathematical Systems Theory,2(1):57--81, 1968.
• 38: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 39: World Wide Web Consortium. XML Path Language (XPath) Recommendation. http://www.w3c.org/TR/xpath/, Nov. 1999.