ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Evaluation of Relational Algebras Incorporating the Time Dimension in Databases.

L. Edwin McKenzie, Richard T. Snodgrass: Evaluation of Relational Algebras Incorporating the Time Dimension in Databases. ACM Comput. Surv. 23(4): 501-543(1991)
@article{DBLP:journals/csur/McKenzieS91,
  author    = {L. Edwin McKenzie and
               Richard T. Snodgrass},
  title     = {Evaluation of Relational Algebras Incorporating the Time Dimension
               in Databases},
  journal   = {ACM Comput. Surv.},
  volume    = {23},
  number    = {4},
  year      = {1991},
  pages     = {501-543},
  ee        = {db/journals/csur/McKenzieS91.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The relational algebra is a procedural query language for relational databases. In this paper we survey extensions of the relational algebra that can query databases recording time-varying data. Such an algebra is a critical part of a temporal DBMS. We identify 26 criteria that provide an objective basis for evaluating temporal algebras, Seven of the criteria are shown to be mutually unsatisfiable, implying there can be no perfect temporal algebra, Choices made as to which of the incompatible criteria are satisfied characterize existing algebras Twelve time-oriented algebras are summarized and then evaluated against the criteria. We demonstrate that the design space has in some sense been explored in that all combinations of basic design decisions have at least one representative algebra. Coverage of the remaining criteria provides one measure of the quality of each algebra We argue that all of the criteria are independent and that the criteria identified as compatible are indeed so, Finally, we list plausible properties proposed by others that are either subsumed by other criteria, are not well defined, or have no objective basis for being evaluated. The algebras realize many different approaches to what appears initially to be a straightforward design task.

Copyright © 1991 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.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Online Edition: ACM Digital Library

Citation Page

References

[Allen and Hayes 1985]
James F. Allen, Patrick J. Hayes: A Common-Sense Theory of Time. IJCAI 1985: 528-531 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Anderson 1981]
...
[Anderson 1982]
T. Lougenia Anderson: Modeling Time at the Conceptual Level. JCDKB 1982: 273-297 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ariav 1986]
Gad Ariav: A Temporally Oriented Data Model. ACM Trans. Database Syst. 11(4): 499-527(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ariav and Clifford 1986]
...
[Ben-Zvi 1982]
...
[Bhargava and Gadia 1990]
...
[Bhargava and Gadia 1991]
Gautam Bhargava, Shashi K. Gadia: Relational Database Systems with Zero Information Loss. IEEE Trans. Knowl. Data Eng. 5(1): 76-87(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Brooks 1956]
...
[Bubenko 1977]
...
[Chen 1976]
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Clifford 1982]
...
[Clifford and Croker 1987]
James Clifford, Albert Croker: The Historical Relational Data Model (HRDM) and Algebra Based on Lifespans. ICDE 1987: 528-537 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Clifford and Rao 1987]
James Clifford, A. Rao: A Simple, General Structure for Temporal Domains. Temporal Aspects in Information Systems 1987: 17-28 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Clifford and Tansel 1985]
James Clifford, Abdullah Uz Tansel: On An Algebra For Historical Relational Databases: Two Views. SIGMOD Conference 1985: 247-265 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Clifford and Warren 1983]
James Clifford, David Scott Warren: Formal Semantics for Time in Databases. ACM Trans. Database Syst. 8(2): 214-254(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Codd 1970]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Codd 1990]
E. F. Codd: The Relational Model for Database Management, Version 2. Addison-Wesley 1990, ISBN 0-201-14192-2
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Croker and Clifford 1989]
...
[Dadam et al. 1984]
Peter Dadam, Vincent Y. Lum, H.-D. Werner: Integration of Time Versions into a Relational Database System. VLDB 1984: 509-522 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Date 1986]
...
[Deen 1985]
S. Misbah Deen: A Relational Language with Deductions, Functions and Recursions. Data Knowl. Eng. 1(2): 139-154(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Elmasri and Navathe 1989]
Ramez Elmasri, Shamkant B. Navathe: Fundamentals of Database Systems. Benjamin/Cummings 1989
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Enderton 1970]
...
[Gadia 1986]
Shashi K. Gadia: Toward a Multihomogeneous Model for a Temporal Database. ICDE 1986: 390-397 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gadia 1988]
Shashi K. Gadia: A Homogeneous Relational Model and Query Languages for Temporal Databases. ACM Trans. Database Syst. 13(4): 418-448(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gadia and Vaishnav 1985]
Shashi K. Gadia, Jay H. Vaishnav: A Query Language for a Homogeneous Temporal Database. PODS 1985: 51-56 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gadia and Yeung 1988]
Shashi K. Gadia, Chuen-Sing Yeung: A Generalized Model for a Relational Temporal Database. SIGMOD Conference 1988: 251-259 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hanson 1987]
Eric N. Hanson: A Performance Analysis of View Materialization Strategies. SIGMOD Conference 1987: 440-453 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hanson 1988]
Eric N. Hanson: Processing Queries Against Database Procedures: A Performance Analysis. SIGMOD Conference 1988: 295-302 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jensen et al. 1991]
Christian S. Jensen, Leo Mark, Nick Roussopoulos: Incremental Implementation Model for Relational Databases with Transaction Time. IEEE Trans. Knowl. Data Eng. 3(4): 461-473(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jones et al. 1979]
Susan Jones, Peter Mason, Ronald K. Stamper: LEGOL 2.0: A relational specification language for complex rules. Inf. Syst. 4(4): 293-305(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Klopprogge 1981]
Manfred R. Klopprogge: TERM: An Approach to Include Time Dimension in the Entity-Relationship Model. ER 1981: 473-508 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Klug 1982]
Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lindgreen 1982]
...
[Lorentzos 1988]
...
[Lorentzos and Johnson 1988]
Nikos A. Lorentzos, Roger G. Johnson: Extending relational algebra to manipulate temporal data. Inf. Syst. 13(3): 289-296(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lum et al. 1984]
Vincent Y. Lum, Peter Dadam, R. Erbe, Jürgen Günauer, Peter Pistor, Georg Walch, H. Werner, John Woodfill: Designing DBMS Support for the Temporal Dimension. SIGMOD Conference 1984: 115-130 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Maier 1983]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Manola and Dayal 1986]
Frank Manola, Umeshwar Dayal: PDM: An Object-Oriented Data Model. OODBS 1986: 18-25 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Martin et al. 1987]
N. G. Martin, Shamkant B. Navathe, Rafi Ahmed: Dealing with Temporal Schema Anomalies in History Databases. VLDB 1987: 177-184 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McKenzie 1986]
L. Edwin McKenzie: Bibliography: Temporal Databases. SIGMOD Record 15(4): 40-52(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McKenzie 1988]
Edwin McKenzie: An Algebraic Language for Query and Update of Temporal Databases. Ph.D. thesis, University of North Carolina, Computer Science Department 1988
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McKenzie and Snodgrass 1990]
L. Edwin McKenzie, Richard T. Snodgrass: Schema Evolution and the Relational Algebra. Inf. Syst. 15(2): 207-232(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McKenzie and Snodgrass 1991]
...
[Navathe and Ahmed 1987]
Shamkant B. Navathe, Rafi Ahmed: TSQL: A Language Interface for History Databases. Temporal Aspects in Information Systems 1987: 109-122 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Navathe and Ahmed 1989]
Shamkant B. Navathe, Rafi Ahmed: A Temporal Relational Model and a Query Language. Inf. Sci. 49(1-3): 147-175(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Overmeyer and Stonebraker 1982]
Ricky Overmyer, Michael Stonebraker: Implementation of a Time Expert in a Data Base System. SIGMOD Record 12(3): 51-60(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Reisner 1981]
Phyllis Reisner: Human Factors Studies of Database Query Languages: A Survey and Assessment. ACM Comput. Surv. 13(1): 13-31(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Reisner et al. 1975]
...
[Rescher and Urquhart 1971]
...
[Roussopoulos 1991]
Nick Roussopoulos: An Incremental Access Method for ViewCache: Concept, Algorithms, and Cost Analysis. ACM Trans. Database Syst. 16(3): 535-563(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sadeghi 1987]
...
[Sadeghi et al. 1987]
R. Sadeghi, W. B. Samson, S. Misbah Deen: HQL - A Historical Query Language. BNCOD 1988: 69-86 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sarda 1990]
Nandlal L. Sarda: Algebra and Query Language for A Historical Data Model. Comput. J. 33(1): 11-18(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shipman 1981]
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Smith and Chang 1975]
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Snodgrass 1987]
Richard T. Snodgrass: The Temporal Query Language TQuel. ACM Trans. Database Syst. 12(2): 247-298(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Snodgrass and Ahn 1985]
Richard T. Snodgrass, Ilsoo Ahn: A Taxonomy of Time in Databases. SIGMOD Conference 1985: 236-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Snodgrass and Ahn 1986]
Richard T. Snodgrass, Ilsoo Ahn: Temporal Databases. IEEE Computer 19(9): 35-42(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Soo 1991]
Michael D. Soo: Bibliography on Temporal Databases. SIGMOD Record 20(1): 14-23(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Stam and Snodgrass 1988]
Robert B. Stam, Richard T. Snodgrass: A Bibliography on Temporal Databases. IEEE Data Eng. Bull. 11(4): 53-61(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tansel 1986]
Abdullah Uz Tansel: Adding time dimension to relational model and extending relational algebra. Inf. Syst. 11(4): 343-355(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tansel 1987]
Abdullah Uz Tansel: A Statistical Interface for Historical Relational Databases. ICDE 1987: 538-546 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tansel and Arkun 1985]
...
[Tansel and Arkun 1986]
Abdullah Uz Tansel, M. Erol Arkun: HQUEL, a Query Language for Historical Relational Databases. SSDBM 1986: 135-142 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tansel et al. 1989]
Abdullah Uz Tansel, M. Erol Arkun, Gultekin Özsoyoglu: Time-by-Example Query Language for Historical Databases. IEEE Trans. Software Eng. 15(4): 464-478(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Thompson 1991]
...
[Tuzhilin and Clifford 1990]
Alexander Tuzhilin, James Clifford: A Temporal Relational Algebra as Basis for Temporal Relational Completeness. VLDB 1990: 13-23 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ullman 1988b]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ullman 1988a]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vandenberg and DeWitt 1991]
Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yeung 1986]
...

Copyright © Fri Mar 12 17:26:21 2010 by Michael Ley (ley@uni-trier.de)