ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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

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 ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Electronic Edition

References

[Böh94]
Michael H. Böhlen: The Temporal Deductive Database System ChronoLog. Ph.D. thesis, Departement Informatik, ETH Zürich 1994
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BSS96]
...
[BD83]
Dina Bitton, David J. DeWitt: Duplicate Record Elimination in Large Data Files. ACM Trans. Database Syst. 8(2): 255-265(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cel95]
Joe Celko: SQL for Smarties: Advanced SQL Programming. Morgan Kaufmann 1995, ISBN 1-55860-323-9
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DNS91]
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: An Evaluation of Non-Equijoin Algorithms. VLDB 1991: 443-452 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gad88]
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
[GLS94]
Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra93]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hel94]
Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HS93]
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS95]
...
[KSL95]
Nick Kline, Richard T. Snodgrass, T. Y. Cliff Leung: Aggregates. The TSQL2 Temporal Query Language 1995: 393-424 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LJ88]
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
[LM90]
T. Y. Cliff Leung, Richard R. Muntz: Query Processing for Temporal Databases. ICDE 1990: 200-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LM92]
T. Y. Cliff Leung, Richard R. Muntz: Temporal Query Processing and Optimization in Multiprocessor Database Machines. VLDB 1992: 383-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McK88]
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
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MS93]
Jim Melton, Alan R. Simon: Understanding the New SQL: A Complete Guide. Morgan Kaufmann 1993, ISBN 1-55860-245-3
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[O'N94]
Patrick E. O'Neil: Database Principles, Programming, Performance. Morgan Kaufmann 1994, ISBN 1-55860-219-4,1-55860-392-1
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PL94]
G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SJS95]
Michael D. Soo, Christian S. Jensen, Richard T. Snodgrass: An Algebra for TSQL2. The TSQL2 Temporal Query Language 1995: 501-544 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sno87]
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
[Sno95]
Richard T. Snodgrass (Ed.): The TSQL2 Temporal Query Language. Kluwer 1995, ISBN 0-7923-9614-6
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sri91]
Suryanarayana M. Sripada: Temporal Reasoning in Deductive Databases. Ph.D. thesis, Imperial College of Science, University of London 1991
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SSD87]
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
[SSJ94]
Michael D. Soo, Richard T. Snodgrass, Christian S. Jensen: Efficient Evaluation of the Valid-Time Natural Join. ICDE 1994: 282-292 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tan86]
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
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ull88]
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
[YL94]
Weipeng P. Yan, Per-Åke Larson: Performing Group-By before Join. ICDE 1994: 89-100 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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