Simplification rules and complete axiomatization for relational update transactions

Abstract

Relational update transactions consisting of line programs of inserts, deletes, and modifications are studied with respect to equivalence and simplification. A sound and complete set of axioms for proving transaction equivalence is exhibited. The axioms yield a set of simplification rules that can be used to optimize efficiently a large class of transactions of practical interest. The simplification rules are particularly well suited to a dynamic environment where transactions are presented in an on-line fashion, and where the time available for optimization may consist of arbitrarily short and sparse intervals.