THE COMPUTATIONAL-COMPLEXITY OF QUERYING BOUNDS ON DIFFERENCES CONSTRAINTS

被引:28
作者
BRUSONI, V [1 ]
CONSOLE, L [1 ]
TERENZIANI, P [1 ]
机构
[1] UNIV TURIN,DIPARTIMENTO INFORMAT,I-10149 TURIN,ITALY
关键词
D O I
10.1016/0004-3702(95)00008-3
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Given a consistent knowledge base formed by a set of constraints, efficient query answering (e.g., checking whether a set of constraints is consistent with the knowledge base or necessarily true in it) is practically very important. In the paper we consider bounds on differences (which are an important class of constraints based on linear inequalities) and we analyze the computational complexity of query answering. More specifically, we consider various common types of queries and we prove that if the minimal network produced by constraint satisfaction algorithms (and characterizing the solutions to a set of constraints) is maintained, then the complexity of answering a query depends only on the dimension of the query and not on the dimension of the knowledge base (which is usually much larger than the query). We also analyse how the approach can be used to deal efficiently with a class of updates to the knowledge base. Some applications of the results are sketched in the conclusion.
引用
收藏
页码:367 / 379
页数:13
相关论文
共 16 条
[1]  
BRUSONI V, 1994, LECT NOTES COMPUTER, V869, P255
[2]   TEMPORAL CONSTRAINT SATISFACTION ON CAUSAL-MODELS [J].
CONSOLE, L ;
TORASSO, P .
INFORMATION SCIENCES, 1993, 68 (1-2) :1-32
[3]   CONSTRAINT PROPAGATION WITH INTERVAL LABELS [J].
DAVIS, E .
ARTIFICIAL INTELLIGENCE, 1987, 32 (03) :281-331
[4]   TEMPORAL DATABASE-MANAGEMENT [J].
DEAN, TL ;
MCDERMOTT, DV .
ARTIFICIAL INTELLIGENCE, 1987, 32 (01) :1-55
[5]   TEMPORAL CONSTRAINT NETWORKS [J].
DECHTER, R ;
MEIRI, I ;
PEARL, J .
ARTIFICIAL INTELLIGENCE, 1991, 49 (1-3) :61-95
[6]  
FREUDER EC, 1992, ARTIFIC INTELL, V58
[7]   DATABASE MODELS FOR INFINITE AND INDEFINITE TEMPORAL INFORMATION [J].
KOUBARAKIS, M .
INFORMATION SYSTEMS, 1994, 19 (02) :141-173
[8]  
KUMAR V, 1992, AI MAG, V13, P32
[9]  
MACKWORTH AK, 1990, ENCY ARTIFICIAL INTE, P205
[10]   AUTOMATIC DEDUCTION OF TEMPORAL INFORMATION [J].
MAIOCCHI, R ;
DIMILANO, P ;
PERNICI, B ;
BARBIC, F .
ACM TRANSACTIONS ON DATABASE SYSTEMS, 1992, 17 (04) :647-688