一种DTDs完全一致性判断算法

An Algorithm for Checking Absolute Consistency of DTDs

一个语法上完全正确的DTD可能是不一致的,即不存在任何“有效的”XML文档遵循这个DTD·不一致的DTDs应当尽可能避免·现已提出的无完整性约束的DTDs一致性判断方法,考虑的都是如何判断整个DTDs是否存在有效的XML文档相对应,忽略了对DTDs结构中不合理的子结构的一致性判断,因此一致性成立的DTDs中仍有可能存在子结构没有相对应的有效XML数据·为解决这一问题,提出了DTDs完全一致性的概念,分析了能够导致DTDs不完全一致性的各种因素,并给出了线性时间复杂性的DTDs完全一致性判断算法·

A syntactically correct DTD might be inconsistent in the sense that there exist no finite XML documents conforming to the structure imposed by the DTD. Inconsistent DTDs should be avoided. However, most consistency checking methods of DTDs without integrity constrains proposed now focus on whether there exists any valid XML documents conform to the DTDs and ignore consistency checking of local structures of DTDs, which result in the phenomenon that a consistent DTD may have sub-structures that no valid XML data could conform to. To solve this problem, notion of absolute consistency of DTDs is proposed and factors that lead to absolute consistency are analyzed. Algorithm for checking absolute consistency of DTDs is offered, which has linear time complexity.