P. Fraternali et S. Paraboschi, ORDERING AND SELECTING PRODUCTION RULES FOR CONSTRAINT MAINTENANCE - COMPLEXITY AND HEURISTIC SOLUTION, IEEE transactions on knowledge and data engineering, 9(1), 1997, pp. 173-178
Citations number
16
Categorie Soggetti
Information Science & Library Science","Computer Sciences, Special Topics","Engineering, Eletrical & Electronic","Computer Science Artificial Intelligence","Computer Science Information Systems
We present a technique for analyzing the run time behavior of integrit
y constraints repair actions, i.e., active database rules specifically
designed to correct violations of database integrity. When constraint
s become violated due to an incorrect user transaction, rule computati
on is started to restore the database to a correct state. Since repair
actions may be numerous and may conflict with each other, an automate
d support to the analysis of their run-time behavior is necessary. The
proposed technique helps the rule base administrator define a repair
rule selection strategy such that the computation terminates for every
input transaction, the final database state satisfies all the constra
ints, and the user's preferences among different ways to restore integ
rity are taken into account. In addition, it can be used by the rule d
esigner to spot ''dangerous'' rules that may be subject to redesign. T
his problem is formulated as an optimization problem on directed hyper
graphs, which we demonstrate to be NP-hard and solve by means of a heu
ristic algorithm.