This paper addresses the problem of efficient update of relations incorporating any number of interval attributes over arbitrary totally ordered domains. In particular, the contribution of this paper is the development of efficient algorithms for updating such interval relations which maintain the non-redundancy of the data whilst avoiding the semantic problems associated with set-union and set-difference.

The outline of the paper is as follows. In Section 2, we give some preliminary definitions of terms and define the operations unfold and fold. We show how these operations can be used to create canonical interval relations. In Section 3 we show how unfold and fold can also be used to define two operations which maintain the canonicity of relations in the face of insertions and deletions respectively. We give algorithms for these update operations. In Section 4, an examination of the efficiency and limitations of unfold leads us to derive two pairs of successively more optimised versions of the update operations; the second pair have the added advantage that they are applicable to arbitrary totally ordered domains. We give algorithms for the implementation of both pairs of operations. In Section 5 we give our concluding remarks and directions of current research.