On Completeness of Historical Relational Query Languages

Numerous proposals for extending the relational data model to incorporate the temporaldimension of data have appeared in the past several years. These proposals have differedconsiderably in the way that the temporal dimension has been incorporated both into thestructure of the extended relations of these temporal models, and consequently into theextended relational algebra or calculus that they define. Because of these differences it hasbeen difficult to compare the proposed models and to make judgments as to which of themmight in some sense be equivalent or even better. In this paper we define the notions oftemporally grouped and temporally ungrouped historical data models and proposetwo notions of historical relational completeness, analogous to Codd's notion of relationalcompleteness, one for each type of model. We show that the temporally ungroupedmodels are less powerful than the grouped models, but demonstrate a technique for extendingthe ungrouped models with a grouping mechanism to capture the additional semanticpower of temporal grouping. For the ungrouped models we define three different languages,a temporal logic, a logic with explicit reference to time, and a temporal algebra, and showthat under certain assumptions all three are equivalent in power. For the grouped modelswe define a many-sorted logic with variables over ordinary values, historical values, andtimes. Finally, we demonstrate the equivalence of this grouped calculus and the ungroupedcalculus extended with the proposed grouping mechanism. We believe the classification ofhistorical data models into grouped and ungrouped provides a useful framework for thecomparison of models in the literature, and furthermore the exposition of equivalent languagesfor each type provides reasonable standards for common, and minimal, notions ofhistorical relational completeness