IMPLEMENTATION OF UPDATE OPERATIONS FOR INTERVAL RELATIONS

The concept of an interval has application in diverse areas, including temporal and spatial databases, However, the semantics of set-union a nd set-difference are inappropriate for the update of interval relatio ns (i.e. of relations with interval attributes). In particular, we dis cuss bow set-union can yield relations in which data is duplicated ove r several tuples and how set-difference does not implement the desired deletion semantics. This leads tis to the definition of a normalized representation for interval relations in which there is no duplication of data over several tubules: we call such relations canonical ones. We define a pair of update operations which complement set-union and s et-difference, give the desired update semantics, and maintain the pro perty of canonicity. We give algorithms for these update operations. A n examination of the efficiency of these operations leads us to propos e two pairs of successively more optimized operations and we give algo rithms for these also. The contribution of this paper is the developme nt of efficient algorithms for updating interval relations while maint aining the desired update semantics and preserving the non-redundancy of the data.