ACM SIGMOD Anthology TODS dblp.uni-trier.de

On Completeness of Historical Relational Query Languages.

James Clifford, Albert Croker, Alexander Tuzhilin: On Completeness of Historical Relational Query Languages. ACM Trans. Database Syst. 19(1): 64-116(1994)
@article{DBLP:journals/tods/CliffordC94,
  author    = {James Clifford and
               Albert Croker and
               Alexander Tuzhilin},
  title     = {On Completeness of Historical Relational Query Languages},
  journal   = {ACM Trans. Database Syst.},
  volume    = {19},
  number    = {1},
  year      = {1994},
  pages     = {64-116},
  ee        = {http://doi.acm.org/10.1145/174638.174642, db/journals/tods/CliffordC94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

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.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 3466 KB]

References

[Aho and Ullman 1979]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[Ariav 1986]
Gad Ariav: A Temporally Oriented Data Model. ACM Trans. Database Syst. 11(4): 499-527(1986) BibTeX
[Ariav and Clifford 1986]
...
[Bancilhon 1978]
François Bancilhon: On the Completeness of Query Languages for Relational Data Bases. MFCS 1978: 112-123 BibTeX
[Banerjee et al. 1987]
Jay Banerjee, Won Kim, Hyoung-Joo Kim, Henry F. Korth: Semantics and Implementation of Schema Evolution in Object-Oriented Databases. SIGMOD Conference 1987: 311-322 BibTeX
[Ben-Zvi 1982]
...
[Chandra and Harel 1980]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[Clifford 1982]
...
[Clifford 1992]
...
[Clifford and Croker 1987]
James Clifford, Albert Croker: The Historical Relational Data Model (HRDM) and Algebra Based on Lifespans. ICDE 1987: 528-537 BibTeX
[Clifford and Tansel 1985]
James Clifford, Abdullah Uz Tansel: On An Algebra For Historical Relational Databases: Two Views. SIGMOD Conference 1985: 247-265 BibTeX
[Clifford and Warren 1983]
James Clifford, David Scott Warren: Formal Semantics for Time in Databases. ACM Trans. Database Syst. 8(2): 214-254(1983) BibTeX
[Codd 1972]
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
[Date 1983]
...
[Enderton 1972]
...
[Fischer and Van Gucht 1985]
Patrick C. Fischer, Dirk Van Gucht: Determining when a Structure is a Nested Relation. VLDB 1985: 171-180 BibTeX
[Gabbay 1989]
...
[Gadia 1986]
Shashi K. Gadia: Toward a Multihomogeneous Model for a Temporal Database. ICDE 1986: 390-397 BibTeX
[Gadia 1988]
Shashi K. Gadia: A Homogeneous Relational Model and Query Languages for Temporal Databases. ACM Trans. Database Syst. 13(4): 418-448(1988) BibTeX
[Hall et al. 1976]
...
[Halmos 1960]
...
[Jones and Mason 1980]
S. Jones, P. J. Mason: Handling the Time Dimension in a Data Base. ICOD 1980: 65-83 BibTeX
[Kabanza et al. 1990]
Froduald Kabanza, Jean-Marc Stévenne, Pierre Wolper: Handling Infinite Temporal Data. PODS 1990: 392-403 BibTeX
[Kamp 1971]
...
[Kamp 1968]
...
[Klug 1982]
Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) BibTeX
[Kröger 1987]
...
[Lorentzos and Johnson 1987]
...
[Maier 1983]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[McKenzie 1986]
L. Edwin McKenzie: Bibliography: Temporal Databases. SIGMOD Record 15(4): 40-52(1986) BibTeX
[McKenzie and Snodgrass 1990]
L. Edwin McKenzie, Richard T. Snodgrass: Schema Evolution and the Relational Algebra. Inf. Syst. 15(2): 207-232(1990) BibTeX
[McKenzie and Snodgrass 1991b]
...
[McKenzie and Snodgrass 1991a]
L. Edwin McKenzie, Richard T. Snodgrass: Evaluation of Relational Algebras Incorporating the Time Dimension in Databases. ACM Comput. Surv. 23(4): 501-543(1991) BibTeX
[Navathe and Ahmed 1989]
...
[Quine 1953]
...
[Rescher and Urquhart 1971]
...
[Roth et al. 1988]
Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 13(4): 389-417(1988) BibTeX
[Sarda 1990]
Nandlal L. Sarda: Algebra and Query Language for A Historical Data Model. Comput. J. 33(1): 11-18(1990) BibTeX
[Segev and Shoshani 1987]
Arie Segev, Arie Shoshani: Logical Modeling of Temporal Data. SIGMOD Conference 1987: 454-466 BibTeX
[Snodgrass 1987]
Richard T. Snodgrass: The Temporal Query Language TQuel. ACM Trans. Database Syst. 12(2): 247-298(1987) BibTeX
[Snodgrass 1990]
Richard T. Snodgrass: Temporal Databases - Status and Research Directions. SIGMOD Record 19(4): 83-89(1990) BibTeX
[Snodgrass and Ahn 1985]
Richard T. Snodgrass, Ilsoo Ahn: A Taxonomy of Time in Databases. SIGMOD Conference 1985: 236-246 BibTeX
[Snodgrass et al. 1989]
...
[Soo 1991]
Michael D. Soo: Bibliography on Temporal Databases. SIGMOD Record 20(1): 14-23(1991) BibTeX
[Stam and Snodgrass 1988]
Robert B. Stam, Richard T. Snodgrass: A Bibliography on Temporal Databases. IEEE Data Eng. Bull. 11(4): 53-61(1988) BibTeX
[Stonebraker et al. 1976]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
[Tansel and Garnett 1992]
Abdullah Uz Tansel, Lucy Garnett: On Roth, Korth, and Silberschatz's Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 17(2): 374-383(1992) BibTeX
[Tansel et al. 1993]
Abdullah Uz Tansel, James Clifford, Shashi K. Gadia, Sushil Jajodia, Arie Segev, Richard T. Snodgrass (Eds.): Temporal Databases: Theory, Design, and Implementation. Benjamin/Cummings 1993, ISBN 0-8053-2413-5
Contents BibTeX
[Tansel 1986]
Abdullah Uz Tansel: Adding time dimension to relational model and extending relational algebra. Inf. Syst. 11(4): 343-355(1986) BibTeX
[Tuzhilin 1989]
...
[Tuzhilin and Clifford 1990]
Alexander Tuzhilin, James Clifford: A Temporal Relational Algebra as Basis for Temporal Relational Completeness. VLDB 1990: 13-23 BibTeX
[Ullman 1988]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Van Benthem 1983]
...

Referenced by

  1. Richard T. Snodgrass: Review - On Completeness of Historical Relational Query Languages. ACM SIGMOD Digital Review 2: (2000)
  2. Jef Wijsen: Temporal FDs on Complex Objects. ACM Trans. Database Syst. 24(1): 127-176(1999)
  3. James Clifford, Curtis E. Dyreson, Tomás Isakowitz, Christian S. Jensen, Richard T. Snodgrass: On the Semantics of ``Now'' in Databases. ACM Trans. Database Syst. 22(2): 171-214(1997)
  4. Abdullah Uz Tansel, Erkan Tin: The Expressive Power of Temporal Relational Query Languages. IEEE Trans. Knowl. Data Eng. 9(1): 120-134(1997)
  5. Nikos A. Lorentzos, Yannis G. Mitsopoulos: SQL Extension for Interval Data. IEEE Trans. Knowl. Data Eng. 9(3): 480-499(1997)
  6. Debabrata Dey, Terence M. Barron, Veda C. Storey: A Complete Temporal Relational Algebra. VLDB J. 5(3): 167-180(1996)
  7. David Toman, Damian Niwinski: First-Order Queries over Temporal Databases Inexpressible in Temporal Logic. EDBT 1996: 307-324
  8. Michael H. Böhlen, Jan Chomicki, Richard T. Snodgrass, David Toman: Querying TSQL2 Databases with Temporal Logic. EDBT 1996: 325-341
  9. Jan Chomicki: Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding. ACM Trans. Database Syst. 20(2): 149-186(1995)
  10. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
  11. Claudio Bettini, Xiaoyang Sean Wang, Elisa Bertino, Sushil Jajodia: Semantic Assumptions and Query Evaluation in Temporal Databases. SIGMOD Conference 1995: 257-268
  12. Xiaoyang Sean Wang: Algebraic Query Languages on Temporal Databases with Multiple Time Granularities. CIKM 1995: 304-311
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:16 2008