XTRACT: a system for extracting document type descriptors from XML documents

ABSTRACT

XML is rapidly emerging as the new standard for data representation and exchange on the Web. An XML document can be accompanied by a Document Type Descriptor (DTD) which plays the role of a schema for an XML data collection. DTDs contain valuable information on the structure of documents and thus have a crucial role in the efficient storage of XML data, as well as the effective formulation and optimization of XML queries. In this paper, we propose XTRACT, a novel system for inferring a DTD schema for a database of XML documents. Since the DTD syntax incorporates the full expressive power of regular expressions, naive approaches typically fail to produce concise and intuitive DTDs. Instead, the XTRACT inference algorithms employ a sequence of sophisticated steps that involve: (1) finding patterns in the input sequences and replacing them with regular expressions to generate “general” candidate DTDs, (2) factoring candidate DTDs using adaptations of algorithms from the logic optimization literature, and (3) applying the Minimum Description Length (MDL) principle to find the best DTD among the candidates. The results of our experiments with real-life and synthetic DTDs demonstrate the effectiveness of XTRACT's approach in inferring concise and semantically meaningful DTD schemas for XML databases.

REFERENCES

• 1: Serge Abiteboul, Querying Semi-Structured Data, Proceedings of the 6th International Conference on Database Theory, p.1-18, January 08-10, 1997
• 2: D. Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39(3):337-350, 1978.
• 3: T. Bray, J. Paoli, and C. M. Sperberg-McQueen. Extensible markup language (XML). (www.w3.org/TR/REC-xml)
• 4: R. K. Brayton and C. McMullen. The decomposition and factorization of boolean expressions. In Proc of the Intl. Symp. on Circuits and Systems, 1982.
• 5: Alvis Brāzma, Efficient identification of regular expressions from representative examples, Proceedings of the sixth annual conference on Computational learning theory, p.236-242, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168340]
• 6: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 7: Alin Deutsch , Mary Fernandez , Dan Suciu, Storing semistructured data with STORED, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.431-442, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 8: M. Fernandez and D. Suciu. Optimizing regular path expressions using graph schemas. In Proc. of the Intl. Conf. on Database Theory (ICDT), 1997.
• 9: M. Garofalakis, A. Gionis, R. Rastogi, S. Seshadri, and K. Shim. XTRACT: A System for Extracting Document Type Descriptors from XML Documents. Bell Labs Tech. Memorandum, 1999.
• 10: E. Mark Gold. Language identification in the limit. Information and Control, 10(5):447-474, 1967.
• 11: E. Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302-320, 1978.
• 12: R. Goldman, J. McHugh, and J. Widom. From semistructured data to XML: Migrating the lore data model and query language. In Proc. of the Intl. Workshop on the Web and Databases (WebDB), 1999.
• 13: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 14: D. S. Hochbaum. Heuristics for the fixed cost median problem. Mathematical Programming, 22:148-162, 1982.
• 15: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 16: Pekka Kilpeläinen , Heikki Mannila , Esko Ukkonen, MDL learning of unions of simple pattern languages from positive examples, Proceedings of the Second European Conference on Computational Learning Theory, p.252-260, March 13-15, 1995
• 17: M. Mehta, J. Rissanen, and R. Agrawal. MDL-based decision tree pruning. In Proc. of the Intl. Conf. on Knowledge Discovery and Data Mining (KDD), 1995.
• 18: Svetlozar Nestorov , Serge Abiteboul , Rajeev Motwani, Extracting schema from semistructured data, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.295-306, June 01-04, 1998, Seattle, Washington, United States
• 19: Leonard Pitt, Inductive Inference, DFAs, and Computational Complexity, Proceedings of the International Workshop on Analogical and Inductive Inference, p.18-44, October 01-06, 1989
• 20: J. R. Quinlan , R. L. Rivest, Inferring decision trees using the minimum description length principle, Information and Computation, v.80 n.3, p.227-248, Mar. 1989 [doi>10.1016/0890-5401(89)90010-2]
• 21: J. Rissanen. Modeling by shortest data description. Automat-ica, 14:465-471, 1978.
• 22: Jorma Rissanen, Stochastic Complexity in Statistical Inquiry Theory, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
• 23: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 24: Albert Ren Rui Wang, Algorithms for multilevel logic optimization, University of California at Berkeley, Berkeley, CA, 1991
• 25: J. Widom. Data management for XML: research directions. IEEE Data Engineering Bulletin, 1991.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Design, Experimentation, Management