Coalescing in Temporal Databases.

Michael H. Böhlen, Richard T. Snodgrass, Michael D. Soo: Coalescing in Temporal Databases. VLDB 1996: 180-191
  author    = {Michael H. B{\"o}hlen and
               Richard T. Snodgrass and
               Michael D. Soo},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Coalescing in Temporal Databases},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {180-191},
  ee        = {db/conf/vldb/BohlenSS96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP,}


Coalescing is a unary operator applicable to temporal databases; it is similar to duplicate elimination in conventional databases. Tuples in a temporal relation that agree on the explicit attribute values and that have adjacent or overlapping time periods are candidates for coalescing. Uncoalesced relations can arise in many ways, e.g., via a projection or union operator, or by not enforcing coalescing on update or insertion. In this paper we show how semantically superfluous coalescing can be eliminated. We then turn to efficiently performing coalescing. We provide a variety of iterative and non-iterative approaches, via SQL and embedded SQL, that require no changes to the DBMS, demonstrating that coalescing can be formulated in SQL-89. Detailed performance studies show that all such approaches are quite expensive. We propose a spectrum of coalescing algorithms within a DBMS, based on nested-loop, explicit partitioning, explicit sorting, temporal sorting, and combined explicit/temporal sorting, as well as their hybrid variants. These algorithms are empirically compared, paying particular attention to attribute skew and timestamp distributions. The experiments show that coalescing can be implemented with reasonable efficiency, and with modest development cost.

Copyright © 1996 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents BibTeX

Electronic Edition


Michael H. Böhlen: The Temporal Deductive Database System ChronoLog. Ph.D. thesis, Departement Informatik, ETH Zürich 1994
Dina Bitton, David J. DeWitt: Duplicate Record Elimination in Large Data Files. ACM Trans. Database Syst. 8(2): 255-265(1983) BibTeX
Joe Celko: SQL for Smarties: Advanced SQL Programming. Morgan Kaufmann 1995, ISBN 1-55860-323-9
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: An Evaluation of Non-Equijoin Algorithms. VLDB 1991: 443-452 BibTeX
Shashi K. Gadia: A Homogeneous Relational Model and Query Languages for Temporal Databases. ACM Trans. Database Syst. 13(4): 418-448(1988) BibTeX
Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994) BibTeX
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335 BibTeX
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 BibTeX
Christian S. Jensen, James Clifford, Ramez Elmasri, Shashi K. Gadia, Patrick J. Hayes, Sushil Jajodia: A Consensus Glossary of Temporal Database Concepts. SIGMOD Record 23(1): 52-64(1994) BibTeX
Nick Kline, Richard T. Snodgrass, T. Y. Cliff Leung: Aggregates. The TSQL2 Temporal Query Language 1995: 393-424 BibTeX
Nikos A. Lorentzos, Roger G. Johnson: Extending relational algebra to manipulate temporal data. Inf. Syst. 13(3): 289-296(1988) BibTeX
T. Y. Cliff Leung, Richard R. Muntz: Query Processing for Temporal Databases. ICDE 1990: 200-208 BibTeX
T. Y. Cliff Leung, Richard R. Muntz: Temporal Query Processing and Optimization in Multiprocessor Database Machines. VLDB 1992: 383-394 BibTeX
T. Y. Cliff Leung, Hamid Pirahesh: Querying Historical Data in IBM DB2 C/S DBMS Using Recursive SQL. Temporal Databases 1995: 315-331 BibTeX
Edwin McKenzie: An Algebraic Language for Query and Update of Temporal Databases. Ph.D. thesis, University of North Carolina, Computer Science Department 1988
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
Jim Melton, Alan R. Simon: Understanding the New SQL: A Complete Guide. Morgan Kaufmann 1993, ISBN 1-55860-245-3
Contents BibTeX
Patrick E. O'Neil: Database Principles, Programming, Performance. Morgan Kaufmann 1994, ISBN 1-55860-219-4,1-55860-392-1
G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79 BibTeX
Michael D. Soo, Christian S. Jensen, Richard T. Snodgrass: An Algebra for TSQL2. The TSQL2 Temporal Query Language 1995: 501-544 BibTeX
Richard T. Snodgrass: The Temporal Query Language TQuel. ACM Trans. Database Syst. 12(2): 247-298(1987) BibTeX
Richard T. Snodgrass (Ed.): The TSQL2 Temporal Query Language. Kluwer 1995, ISBN 0-7923-9614-6
Contents BibTeX
Suryanarayana M. Sripada: Temporal Reasoning in Deductive Databases. Ph.D. thesis, Imperial College of Science, University of London 1991
R. Sadeghi, W. B. Samson, S. Misbah Deen: HQL - A Historical Query Language. BNCOD 1988: 69-86 BibTeX
Michael D. Soo, Richard T. Snodgrass, Christian S. Jensen: Efficient Evaluation of the Valid-Time Natural Join. ICDE 1994: 282-292 BibTeX
Abdullah Uz Tansel: Adding time dimension to relational model and extending relational algebra. Inf. Syst. 11(4): 343-355(1986) BibTeX
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
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
Weipeng P. Yan, Per-Åke Larson: Performing Group-By before Join. ICDE 1994: 89-100 BibTeX

Referenced by

  1. Costas Vassilakis: An Optimisation Scheme for Coalesce/Valid Time Selection Operator Sequences. SIGMOD Record 29(1): 38-43(2000)
  2. Curtis E. Dyreson, Michael H. Böhlen, Christian S. Jensen: Capturing and Querying Multiple Aspects of Semistructured Data. VLDB 1999: 290-301
  3. Cindy Xinmin Chen, Carlo Zaniolo: Universal Temporal Extensions for Database Languages. ICDE 1999: 428-437
  4. Curtis E. Dyreson, Richard T. Snodgrass: Supporting Valid-Time Indeterminacy. ACM Trans. Database Syst. 23(1): 1-57(1998)
  5. Michael H. Böhlen, Renato Busatto, Christian S. Jensen: Point-Versus Interval-Based Temporal Data Models. ICDE 1998: 192-200
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:10 2009