Detail

Semantic Diff as the Basis for Knowledge Base Versioning

In this work we investigate the problem of maintaining and reasoning with different versions of a knowledge base. We 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. We 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. We 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. We 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 we 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. We 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.
(Joint work with Enrico Franconi and Thomas Meyer.)