一种用于识别不含冲突用户解释的算法  

An Algorithm for Recognizing the User Interpretation without Conflicts

作　　者：刘国华[1,2] 陈子军 季文赟[1] 施伯乐 黄冬梅[1,3] 

机构地区：[1]复旦大学计算机科学系 [2]燕山大学计算机科学系秦皇岛066004 [3]海南大学信息学院计算机科学系海口570228

出　　处：《计算机学报》2000年第8期813-818,共6页Chinese Journal of Computers

基　　金：国家自然科学基金!( 6993 3 0 10 )

摘　　要：根据用户解释的特点和问题求解的需要扩充了图论中有向图的定义 ,使其结点既可以是普通的结点 ,又可以是一个有向图 ,并把用于表示用户解释的这种有向图称为 GD-约束图 .在此基础上 ,对不含冲突的用户解释表现于 GD-约束图中的特征进行了抽取 .最后 ,总结出用户解释不含冲突的充要条件并根据这个充要条件提出了一个时间复杂性为 O(m× n)的多项式时间识别算法 。In this paper, in order to express the user interpretation, which is a set of user specified GD constraints, in terms of a directed graph, the definition of directed graph in graph theory is extended according to the characters of the user interpretation and the requirement of the problem, and the node in this directed graph may be either an ordinary node or a directed graph. The directed graph(having been extended)expressing the user interpretation is said to be a GD constraint graph. Based on these, the features of the GD constraint graph corresponding to the user interpretation without conflicts are extracted. Finally, this paper gives the sufficient and necessary condition under which the user interpretation doesn't contain conflicts, and proposes a polynomial time recognition algorithm which time complexity is O(m×n) , on the basis of the sufficient and necessary condition, then, proves the correctness of the algorithm and analyzes the time complexity of the algorithm.

关 键 词：面向对象数据库 规范化 用户解释 算法 

分 类 号：TP311.132[自动化与计算机技术—计算机软件与理论]