ISSN 1000-1239 CN 11-1777/TP

• 论文 • 上一篇    下一篇


路 燕1 郝忠孝2, 3   

  1. 1(山东科技大学信息科学与工程学院 青岛 266510) 2(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) 3(哈尔滨理工大学计算机与控制学院 哈尔滨 150080) ( )
  • 出版日期: 2008-05-15

A New Algorithm for DTDs Absolute Consistency Checking

Lu Yan1 and Hao Zhongxiao2, 3   

  1. 1(College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao 266510) 2(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001) 3(School of Computer & Control, Harbin University of Science and Technology, Harbin 150080)
  • Online: 2008-05-15

摘要: DTDs(或XML Schema)的一致性是XML研究中的一个重要课题.一个DTD是一致的当且仅当存在有效的XML文档遵循这个DTD.然而一个一致性成立的DTD仍有可能存在一致性不成立的不合理子结构,同一致性不成立的DTDs一样,DTDs中一致性不成立的子结构同样应该尽量避免.为解决这一问题,对“元素在DTD中的一致性”、“DTDs完全一致性”等概念进行了定义和分析,并给出了一种新的DTDs完全一致性判断算法,该算法的最坏时间复杂度是O(n),具有较高的效率.

关键词: XML, DTD, 元素一致性, DTDs一致性, DTDs完全一致性

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 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).

Key words: XML, DTD, element consistency, DTDs consistency, DTDs absolute consistency