Database Evolution under Non-deterministic and Non-chronological Updates

Data base applications that model aspects of the real-world, should keep track of the changes that are happening in it, and reflect these changes as accurately as possible in the database. If the information about changes, in the form of updates, is not supplied to the database in an ideal way, the database needs to have mechanisms that assimilate correctly, whenever possible, this new information.

We propose a model called FlexUp that addresses two cases of non-ideal information supply. The first is the well-known, in the context of deductive databases, problem of non-deterministic updates of intensional predicates. The second is the problem of non-chronological updates, i.e. updates that come to the system in an order that does necessarily reflect the order in which the corresponding changes happen in the real-world.
The main features of FlexUp are (a) it is conservative in the sense that in case of ambiguity it avoids realizing updates in ad hoc ways (b) it satisfies ACID-like properties and therefore it is in accordance with traditional transaction systems.