Abstract:
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 substructures 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 substructures, 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).