Manipulation operations for an interval-extended relational model

摘要

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.