Learning Restricted Regular Expressions with Interleaving
This work addresses the need for automated schema inference in XML data management, offering incremental improvements for practitioners dealing with schema-less documents.
The paper tackled the problem of inferring Relax NG schemas for XML documents lacking valid schemas by proposing a new subclass of regular expressions with interleaving and a polynomial inference algorithm, with experimental results showing improved practicality and precision over previous methods.
The advantages for the presence of an XML schema for XML documents are numerous. However, many XML documents in practice are not accompanied by a schema or by a valid schema. Relax NG is a popular and powerful schema language, which supports the unconstrained interleaving operator. Focusing on the inference of Relax NG, we propose a new subclass of regular expressions with interleaving and design a polynomial inference algorithm. Then we conducted a series of experiments based on large-scale real data and on three XML data corpora, and experimental results show that our subclass has a better practicality than previous ones, and the regular expressions inferred by our algorithm are more precise.