Regular expression transformations to extend regular languages (with application to a Datalog XML schema validator)

An XML schema is a set of rules for defining the allowed sub-elements of any element in an XML document. These rules use regular expressions to define the language of the element's children. Updates to an XML schema are updates to the regular expressions defined by the schema rules. We consider an interactive, data administration tool for XML databases. In this tool, changes on an XML schema are activated by updates that violate the validity of an XML document. Our schema validator is a Datalog program, resulting from the translation of a given XML schema. Changing the schema implies changing the validator.The main contribution of this paper is an algorithm allowing the evolution of XML schemas. This algorithm is based on the computation of new regular expressions to extend a given regular language in a conservative way, trying to foresee the needs of an application. A translation function from schema constraints to Datalog programs is introduced. The validation of an XML tree corresponds to the evaluation of the Datalog program over the tree. Our method allows the maintenance of the Datalog program in an incremental way, i.e., without redoing the entire translation.