When nulls occur in a relational theory T, updates to T will cause excessive growth in the size of T if many data atoms of T unify with atoms occurring in the updates. This chapter proposes a scheme of lazy evaluation for updates that strictly bounds the growth of T caused by each update, via user-specified limits on permissible size increases. Under lazy evaluation, an overly-expensive update U will be stored away rather than executed, with the hope that hew information on costly null values will reduce the expense of executing U before the information contained in U is needed for an incoming query. If an incoming query unavoidably depends on the results of an overly expensive portion of an update, the query must be rejected, as there is no way to reason about the information in the update other than by incorporating it directly in the relational theory. When a query is rejected, the originator of the query is notified of the exact reasons for the rejection. The query may be resubmitted once the range of possible values of the troublesome nulls has been narrowed down. The bottom line for an efficient implementation of updates, however, is that null values should not be permitted to occur as attribute values for attributes heavily used in update selection clauses—particularly those used as join attributes.

The cost of an update can be measured as a function of the increase in the size of T that would result from execution of the update, and by measures of the expected time to execute the update and to answer subsequent queries.