Logical Updating of Object Class Structures

摘要

We consider Object Oriented schemas supporting isa relationships and multiple inheritance extended with features from semantic modeling such as disjointness of classes and class intersection inclusion into other classes as well as negations of these statements. We provide an advisor that supplies the user with possible update alternatives when trying to modify the schema. Formally we investigate the problem of updating object class structures formalized as first order monadic theoreis. We show the problem to be co-NP-complete in general. Based on a for-mal system, we provide incremental update algorithms. By introducing a rule-goal (hyper) graph, non-trivial conditions are presented in different cases which guarantee the problem's reduction to the polynomial level.