摘要
本文给出了表的等价性判定的一些结果:三元可满足性问题、表达式的NP完全性、表的NP完全性,还给出了函数依赖对表的影响、强等价性的复杂性的一些讨论。为对表的进一步研究指出了方向。
In this paper, several results of table equivalence decision are given:3-satisfiability problem, expression NP-completeness, and table NP-completeness. Also given and discussed are an effect of functional dependency on the table and strong equivalence complexity, thus providing the condition for the further study of tables.
出处
《计算机研究与发展》
EI
CSCD
北大核心
1996年第10期796-800,共5页
Journal of Computer Research and Development
关键词
表
NP完全性
等价性
数据库
Equivalence,table,NP-completeness, strong equivalence.