Learning Disjunctive Multiplicity Expressions and Disjunctive Generalize Multiplicity Expressions From Both Positive and Negative Examples.

This article focuses on the development of algorithms for inferring schemas of unordered eXtensible Markup Language (XML) documents by learning disjunctive multiplicity expressions (DMEs) and their extension, disjunctive generalized multiplicity expressions (DGMEs). DMEs are a subclass of regular expressions suited for specifying unordered content models, while DGMEs extend DMEs by allowing numeric occurrence ranges for symbols. The authors propose a novel genetic algorithm-based method called iDME to learn DMEs from both positive and negative examples, addressing the NP-complete nature of the problem, and further extend it to iDGME for learning DGMEs. Experimental results demonstrate that iDME and iDGME achieve high accuracy in schema inference, with iDGME providing more expressive and precise models, and both algorithms perform effectively across various dataset sizes and example scenarios.