We consider the problem of discovering Datalog rules with negation that aresignificant(i.e. interesting andsufficiently valid) with respect to a given set of positive and negative facts. We propose a formal framework, as well as algorithms, for the discovery of such rules from a set of facts that are stored in the form of a set of tables in a database. Additionally, we propose a way of updating the discovered rules when the set of facts is updated. ©1999 American Institute of Physics.