Validating XML Constraints Using Automata

In this paper, we address the problem of validating constraints in XML. In particular, we concentrate on the three commonly discussed types of constraints, functional dependencies, keys and foreign keys. Unranked bottom-up tree automata can be used to validate XML documents against a schema, and we further extend the automata to validate constraints for XML. The automaton can, in only one pass, not only check the validity of an XML document w.r.t. DTD, but also validate the document against constraints. We discuss the computational complexity of the running of the automaton. Finally we give the prototype implementation, and provide the experimental results.