Constrained dependencies

作     者：Maher, MJ 

作者机构：School of Computing and Information Technology Griffith University Nathan Queensland 4111 Australia 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：1997年第173卷第1期

页      面：113-149页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Constraint theory 

摘      要：We extend the notions of functional and finiteness dependencies to apply to subsets of a relation that are specified by constraints. These dependencies have many applications. We are able to characterize those constraint domains which admit a polynomial time solution of the implication problem (assuming P not equal NP) and give an efficient algorithm for these cases, module the cost of constraint manipulation. For other cases we offer approximate algorithms. Finally, we outline some applications of these dependencies to the analysis and optimization of CLP programs and database queries.