On the complexity of schema inference from web pages in the presence of nullable data attributes

ABSTRACT

An increasingly large number of Web pages are machine-generated by filling in templates with data stored in backend databases. These templates can be viewed as the implicit schemas of those Web pages. The ability to infer the implicit schema from a collection of Web pages is important for scalable data extraction, since the inferred schema can be used to automatically identify schema attributes that are "encoded" in Web pages.However, the task of inferring a "good" schema is complicated due to the existence of nullable (missing) data attributes. Usually if an attribute contains a null value, then it will be omitted in the generated Web page, giving rise to different variations and permutations of layout structures in Web pages that are generated from the same template.In this paper we investigate the complexity of schema inference from Web pages in the presence of nullable data attributes. We introduce the notion of unambiguity as a quality measure for inferred schemas and prove that the problem of inferring "good" (unambiguous) schemas is NP-complete. Our complexity results imply that ambiguity resolution is one of the root causes of the computational difficulty underlying schema inference from Web pages.

REFERENCES

• 1: D. Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39(3):337--350, 1978.
• 2: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 3: Arvind Arasu , Hector Garcia-Molina , Stanford University, Extracting structured data from Web pages, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872799]
• 4: Naveen Ashish , Craig A. Knoblock, Wrapper generation for semi-structured Internet sources, ACM SIGMOD Record, v.26 n.4, p.8-15, Dec. 1997 [doi>10.1145/271074.271078]
• 5: Paolo Atzeni , Giansalvatore Mecca , Paolo Merialdo, To Weave the Web, Proceedings of the 23rd International Conference on Very Large Data Bases, p.206-215, August 25-29, 1997
• 6: Boris Chidlovskii, Wrapping Web Information Providers by Transducer Induction, Proceedings of the 12th European Conference on Machine Learning, p.61-72, September 05-07, 2001
• 7: William W. Cohen , Matthew Hurst , Lee S. Jensen, A flexible learning system for wrapping tables and lists in HTML documents, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511477]
• 8: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 9: Hasan Davulcu , Guizhen Yang , Michael Kifer , I. V. Ramakrishnan, Computational aspects of resilient data extraction from semistructured sources (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.136-144, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335216]
• 10: Minos Garofalakis , Aristides Gionis , Rajeev Rastogi , S. Seshadri , Kyuseok Shim, XTRACT: a system for extracting document type descriptors from XML documents, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.165-176, May 15-18, 2000, Dallas, Texas, United States
• 11: E. M. Gold. Language identication in the limit. Information and Control, 10(5):447--474, 1967.
• 12: E. M. Gold. Complexity of automaton identication from given data. Information and Control, 37(3):302--320, 1978.
• 13: Stéphane Grumbach , Giansalvatore Mecca, In Search of the Lost Schema, Proceeding of the 7th International Conference on Database Theory, p.314-331, January 10-12, 1999
• 14: Chun-Nan Hsu , Ming-Tzung Dung, Generating finite-state transducers for semi-structured data extraction from the Web, Information Systems, v.23 n.9, p.521-538, Dec. 1998
• 15: Tao Jiang , Ming Li, On the complexity of learning strings and sequences, Theoretical Computer Science, v.119 n.2, p.363-371, Oct. 25, 1993 [doi>10.1016/0304-3975(93)90167-R]
• 16: N. Kushmerick, D. S. Weld, and R. B. Doorenbos. Wrapper induction for information extraction. In International Joint Conference on Articial Intelligence (IJCAI), 1997.
• 17: David Maier, The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM (JACM), v.25 n.2, p.322-336, April 1978 [doi>10.1145/322063.322075]
• 18: Martin Middendorf, On finding minimal, maximal, and consistent sequences over a binary alphabet, Theoretical Computer Science, v.145 n.1-2, p.317-327, July 10, 1995 [doi>10.1016/0304-3975(95)00014-N]
• 19: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 20: 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]
• 21: Mike Perkowitz , Robert B. Doorenbos , Oren Etzioni , Daniel S. Weld, Learning to Understand Information on the Internet: AnExample-Based Approach, Journal of Intelligent Information Systems, v.8 n.2, p.133-153, March/April 1997 [doi>10.1023/A:1008672508721]
• 22: K.-J. R.aih. a and E. Ukkonen. The shortest common supersequence problem over binary alphabet is NP-complete. Theoretical Computer Science, 16:187--198, 1981.
• 23: Guizhen Yang , Saikat Mukherjee , I. V. Ramakrishnan, On Precision and Recall of Multi-Attribute Data Extraction from Semistructured Sources, Proceedings of the Third IEEE International Conference on Data Mining, p.395, November 19-22, 2003

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Theory

Keywords:
data extraction, data mining, machine learning, schema inference, web mining, world wide web, wrapper induction