The concept of an interval has application in diverse areas, including temporal and spatial databases. However, the semantics of set-union and set-difference are inappropriate for the update of interval relations (i.e. of relations with interval attributes). In particular, we discuss how set-union can yield relations in which data is duplicated over several tuples and how set-difference does not implement the desired deletion semantics. This leads us to the definition of a normalized representation for interval relations in which there is no duplication of data over several tuples: we call such relations canonical ones. We define a pair of update operations which complement set-union and set-difference, give the desired update semantics, and maintain the property of canonicity. We give algorithms for these update operations. An examination of the efficiency of these operations leads us to propose two pairs of successively more optimized operations and we give algorithms for these also. The contribution of this paper is the development of efficient algorithms for updating interval relations while maintaining the desired update semantics and preserving the non-redundancy of the data.

We present the concept of a default database which comprises a set of facts, a set of deduction rules, and a set of defaults. Defaults define assumptions to be made about information not derivable from the rules and facts. Defaults, by augmenting the information which is a consequence solely of the rules and facts, enable definite responses to queries on the basis of ‘common sense’ assumptions rather than responses of the form ‘unknown’. The augmented information is termed an extension. Although such an extension is self-consistent, in general two or more mutually inconsistent extensions can arise. We characterise the rules and defaults of a database as safe if only one extension can arise for any given set of facts. We give conditions which are necessary and sufficient to ensure safety.

We describe a system called Exegesis, through which integrity constraints may be specified and enforced over a relational database extended with a deductive component. The issues of constraint enforcement and deduction in the context of databases have been addressed individually by a number of authors. However, although some consideration has been made of constraint enforcement over deductive databases, no detailed description exists of such a system. The paper delineates the syntax of constraints and deduction rules accepted by Exegesis. It describes in detail the way in which the deduction rules are used to derive data from data explicitly stored, and the way in which the integrity constraints are enforced over a database extended with such rules.