ERCIM Research Report - 12/95-R043

Updating Object Oriented Schema Structures Viewed as Logical Theories

Dimitri Theodoratos

December, 1995

Abstract

We consider Object Oriented schema structures supporting isa relationships and multiple inheritance extended with features 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. For- mally we investigate the problem of updating object schema structures formalized as first order monadic theories. Based on a formal system, we provide incremental update algorithms. We show the problem to be co-NP-complete in general. By introducing a rule-goal (hyper)graph, non- trivial conditions are presented by case which guarantee its reduction to the polynomial level.

Keywords: Object Oriented schema, Incremental updating, Monadic theory, Algorithms, Complexity.

Interested?

load a PostScript file of the report to your disk (use the "load to disc" option)
PDF version of the report (For PDF files, a free viewer (Acrobat Reader) is available from Adobe Systems. You can use Acrobat Readers with the World-Wide Web. Here's How.)

return to the research reports content list to order a copy of the report