XTRACT: A System for Extracting Document Type Descriptors from XML Documents

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.