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. <P>

The outline of the paper is as follows.  In Section 2, we give some
preliminary definitions of terms and define the operations <I>unfold</I> and
<I>fold</I>.  We show how these operations can be used to create canonical
interval relations.  In Section 3 we show how <I>unfold</I> and <I>fold</I>
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
<I>unfold</I> 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.