Coalescing in Temporal Databases.

Michael H. Böhlen, Richard T. Snodgrass, Michael D. Soo: Coalescing in Temporal Databases. VLDB 1996: 180-191

@inproceedings{DBLP:conf/vldb/BohlenSS96,
  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, http://dblp.uni-trier.de}
}

Abstract

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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

Electronic Edition

References

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