Numerous proposals for extending the relational data model to incorporate the temporal dimension of data have appeared in the past several years. These proposals have differed considerably in the way that the temporal dimension has been incorporated both into the structure of the extended relations of these temporal models and into the extended relational algebra or calculus that they define. Because of these differences, it has been difficult to compare the proposed models and to make judgments as to which of them might in some sense be equivalent or even better . In this paper we define temporally grouped and temporally ungrouped historical data models and propose two notions of historical relational completeness , analogous to Codd's notion of relational completeness, one for each type of model. We show that the temporally ungrouped models are less expressive than the grouped models, but demonstrate a technique for extending the ungrouped models with a grouping mechanism to capture the additional semantic power of temporal grouping. For the ungrouped models, we define three different languages, a logic with explicit reference to time, a temporal logic, and a temporal algebra, and motivate our choice for the first of these as the basis for completeness for these models. For the grouped models, we define a many-sorted logic with variables over ordinary values, historical values, and times. Finally, we demonstrate the equivalence of this grouped calculus and the ungrouped calculus extended with a grouping mechanism. We believe the classification of historical data models into grouped and ungrouped models provides a useful framework for the comparison of models in the literature, and furthermore, the exposition of equivalent languages for each type provides reasonable standards for common, and minimal, notions of historical relational completeness.

We present a general representation for problems that can be reduced to constraint satisfaction problems (CSP) and a model for reasoning about their solution. The novel part of the model is a constraint-driven reasoner that manages a set of constraints specified in terms of arbitrarily complex Boolean expressions and represented in the form of a dependency network. This dependency network incorporates control information (derived from the syntax of the constraints) that is used for constraint propagation, contains dependency information that can be used for explanation and for dependency-directed backtracking, and is incremental in the sense that if the problem specification is modified, a new solution can be derived by modifying the existing solution. The constraint-driven reasoner is coupled to a problem solver which contains information about the problem variables and preference orderings.>

Critical to the design of an historical database model is the representation of the “existence” of objects across the temporal dimension — for example, the “birth,” “death,” or “rebirth” of an individual, or the establishment or dis-establishment of a relationship. The notion of the “lifespan” of a database object is proposed as a simple framework for expressing these concepts. An object's lifespan is simply those periods of time during which the database models the properties of that object. In this paper we propose the historical relational data model (HRDM) and algebra that is based upon lifespans and that views the values of all attributes as functions from time points to simple domains. The model that we obtain is a consistent extension of the relational data model, and provides a simple mechanism for providing both time-varying data and time-varying schemes.

The tree-locking protocol proposed by Silberschatz and Kedem5guarantees transaction schedules that are both serializable and deadlock-free. The tree-locking protocol assumes the existence of a partial order defined over all of the objects in a database. Requiring all transactions to be tree-locked with respect to this single partial order limits the degree of concurrency obtainable in a database system by increasing the potential for conflict between transactions. In this paper we define a new locking protocol that is derived from the tree-locking protocol, but allows a changing set of partial orders to be defined over the objects in a database. We call this protocol dynamic tree-locking.