Deleted tuples are useful when updating through universal scheme interfaces

The authors present a novel approach to database updating through universal scheme interfaces. The main contribution of the approach is the elimination of non-determinism. That is, contrary to most other approaches, inserting or deleting a tuple can always be done without having to make any choice at all. Tuples that have been deleted from the database are explicitly stored and are used subsequently in order to invalidate certain derivations. Updates are performed in a monotonous manner, and updates satisfy the property of reversibility