We identify semantic problems associated with the querying and updating of
spatio-temporal interval data and propose operations which alleviate these
problems. We first motivate two key requirements for the manipulation of
such data, namely that no two tuples of a relation should intersect or be
mergeable. We then examine the properties of two operations, *unfold*
and *fold*, and show how they can be used to define three further
operations which, respectively: eliminate intersecting or mergeable data
from a relation incorporating interval attributes, yielding a so-called
*canonical* relation; add data to a canonical relation while preserving
the canonicity property; and remove data from a canonical relation while
also preserving canonicity. We formally show the correctness of all these
operations. An examination of their space and time requirements then leads
us to define an equivalent set of optimised operations. We formally show
the equivalence of the non-optimised and optimised operations, and discuss
the performance gains of the latter.
This work has application to all areas requiring the manipulation of
spatio-temporal interval data. For example, it provides an efficient
solution to the retroactive update of temporal data.