Semantic diff as the basis for knowledge base versioning

Abstract

In this paper the authors investigate the problem of maintaining and reasoning with different versions of a knowledge base. The authors are interested in the scenario where a knowledge base (expressed in some logical formalism) might evolve over time and, as a consequence, different versions thereof have to be maintained simultaneously in a parsimonious way. Moreover, users of the knowledge base should be able to access, not only any specific version, but also the differences between two given versions of the knowledge base. The authors address this problem by proposing a general semantic framework for the maintenance of different versions of a knowledge base. It turns out that the notion of semantic difference between knowledge bases plays a central role in the framework. The authors show that an appropriate characterization produces a unique definition of semantic difference which is applicable to a large class of logic-based knowledge representation languages. The authors then proceed to restrict our attention to finitely generated propositional logics, and show that our semantic framework can be represented syntactically in a particular kind of normal form, referred to as ordered complete conjunctive normal form or oc-CNF. This is followed by a generalization in which the authors show that similar results can be obtained for any syntactic representation (in a finitely generated propositional logic) of the semantic framework. Of particular interest are representations of appropriately chosen normal forms. The authors expect that our constructions for the propositional case can be extended to more expressive languages, such as description logics (DLs). In that respect, our results add to the investigation of the versioning problem for DL-based ontologies