Deciding Consistency of Databases Containing Defeasible and Strict Information
This work addresses consistency and reasoning challenges in knowledge representation for AI and database systems, offering incremental improvements in formalizing defeasible logic.
The paper tackles the problem of determining consistency and entailment in databases with defeasible and strict information by proposing a probabilistic semantics, deriving necessary and sufficient conditions, and providing a decision procedure, with polynomial-time results for Horn clauses.
We propose a norm of consistency for a mixed set of defeasible and strict sentences, based on a probabilistic semantics. This norm establishes a clear distinction between knowledge bases depicting exceptions and those containing outright contradictions. We then define a notion of entailment based also on probabilistic considerations and provide a characterization of the relation between consistency and entailment. We derive necessary and sufficient conditions for consistency, and provide a simple decision procedure for testing consistency and deciding whether a sentence is entailed by a database. Finally, it is shown that if al1 sentences are Horn clauses, consistency and entailment can be tested in polynomial time.