A New Algorithm for DTDs Absolute Consistency Checking

A document type definition (DTD) describes the structure of a set of similar XML documents and serves as the schema for XML documents. Consistency of DTDs is an important topic in XML research. A DTD is consistent if and only if there is some valid XML document conforming to the DTD, while a DTD is inconsistent if there is no XML document conforming to it. Inconsistent DTDs are of no use and should be avoided as well as possible. However, a consistent DTD may have inconsistent substructures that no valid XML data could conform to. This kind of DTDs should be avoided as well as inconsistent DTDs. In order to solve this problem, a new notion of “element consistency in a DTD” is put forward in this paper. Based on “element consistency in a DTD”, notion of “absolute consistent DTDs” , which means consistent DTDs with no inconsistent substructures, is discussed. Furthermore, a new DTDs absolute consistency checking algorithm, with which a DTD can be determined absolute consistent or not consistent quickly, is also offered. The worst time complexity of the new DTDs absolute consistency checking algorithm is O(n).