This paper introduces a new measurement, robustness, to measure the quality of machine-discovered knowledge from real-world databases that change over time. A piece of knowledge is robust if it is unlikely to become inconsistent with new database states. Robustness is different from predictive accuracy in that by the latter, the system considers only the consistency of a rule with unseen data, while by the former, the consistency after deletions and updates of existing data is also considered. Combining robustness with other utility measurements, a system can make intelligent decisions in learning and maintenance of knowledge learned from changing databases. This paper defines robustness, then presents an estimation approach for the robustness of Horn-clause rules learned from a relational database. The estimation approach applies the Laplace law of succession, which can be efficiently computed. The estimation is based on database schemas and transaction logs. No domain-specific information is required. However, if it is available, the approach can exploit it.