Using Differential Techniques to Efficiently Support Transaction Time.

Christian S. Jensen, Leo Mark, Nick Roussopoulos, Timos K. Sellis: Using Differential Techniques to Efficiently Support Transaction Time. VLDB J. 2(1): 75-111(1993)
  author    = {Christian S. Jensen and
               Leo Mark and
               Nick Roussopoulos and
               Timos K. Sellis},
  title     = {Using Differential Techniques to Efficiently Support Transaction
  journal   = {VLDB J.},
  volume    = {2},
  number    = {1},
  year      = {1993},
  pages     = {75-111},
  ee        = {db/journals/vldb/JensenMRS93.html},
  bibsource = {DBLP,}


We present an architecture for query processing in the relational model extended with transaction time. The architecture integrates standard query optimization and computation techniques with new differential computation techniques. Differential computation computes a query incrementally or decrementally from the cached and indexed results of previous computations. The use of differential computation techniques is essential to provide efficient processing of queries that access very large temporal relations. Alternative query plans are integrated into a state transaction network, where the state space includes backlogs of base relations, cached results from previous computations, a cache index, and intermediate results; the transactions include standard relational algebra operators, operators for constructing differential files, operators for differential computation, and combined operators. A rule set is presented to prune away parts of state transition networks that are not promising, and dynamic programming techniques are used to identify the optimal plans from the remaining state transition networks. An extended logical access path serves as a "structuring" index on the cached results and contains, in addition, vital statistics for the query optimization process (including statistics about base relations, backlogs, and queries - previously computed and cached, previously computed, or just previously estimated).

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

Key Words

Temporal databases, transaction time, efficient query processing, incremental and decremental computation.

Online Paper

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


[Ahn 1986]
[Bassiouni 1985]
Mostafa A. Bassiouni: Data Compression in Scientific and Statistical Databases. IEEE Trans. Software Eng. 11(10): 1047-1058(1985) BibTeX
[Blakeley et al. 1986]
[Blakeley et al. 1989]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989) BibTeX
[Bolour et al. 1982]
A. Bolour, T. L. Anderson, L. J. Dekeyser, Harry K. T. Wong: The Role of Time in Information Processing: A Survey. SIGMOD Record 12(3): 27-50(1982) BibTeX
[Bubenko 1977]
[Chakravarthy & Minker ]
Upen S. Chakravarthy, Jack Minker: Multiple Query Processing in Deductive Databases using Query Graphs. VLDB 1986: 384-391 BibTeX
[Christodoulakis 1987]
Stavros Christodoulakis: Analysis of Retrieval Performance for Records and Objects Using Optical Disk Technology. ACM Trans. Database Syst. 12(2): 137-169(1987) BibTeX
[Codd 1970]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[Codd 1979]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[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 BibTeX
[Gunadhi & Segev 1989]
Himawan Gunadhi, Arie Segev: A Framework for Query Optimization in Temporal Databases. SSDBM 1990: 131-147 BibTeX
[Gundadhi et al. 1989]
[Hanson 1987]
Eric N. Hanson: A Performance Analysis of View Materialization Strategies. SIGMOD Conference 1987: 440-453 BibTeX
[Hong & Wong 1989]
[Jarke & Koch 1984]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX
[Jarke 1984]
Matthias Jarke: Common Subexpression Isolation in Multiple Query Optimization. Query Processing in Database Systems 1985: 191-205 BibTeX
[Jensen & Mark 1990]
[Jensen & Mark 1992]
Christian S. Jensen, Leo Mark: Queries on Change in an Extended Relational Model. IEEE Trans. Knowl. Data Eng. 4(2): 192-200(1992) BibTeX
[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) BibTeX
[Jhingran 1988]
Anant Jhingran: A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures. VLDB 1988: 88-99 BibTeX
[Jhingran & Stonebraker 1989]
Anant Jhingran, Michael Stonebraker: Alternatives in Complex Object Representation: A Performance Perspective. ICDE 1990: 94-102 BibTeX
[Kinsley & Driscoll 1979]
[Kinsley & Driscoll 1984]
[Kim 1984]
[Kolovson & Stonebraker 1989]
Curtis P. Kolovson, Michael Stonebraker: Indexing Techniques for Historical Databases. ICDE 1989: 127-137 BibTeX
[Lafortune & Wong 1986]
Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986) BibTeX
[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 BibTeX
[Mahanti & Bagchi 1985]
A. Mahanti, A. Bagchi: AND/OR Graph Heuristic Search Methods. J. ACM 32(1): 28-51(1985) BibTeX
[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
[McKenzie & Snodgras 1991]
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
[Rich 1983]
[Rotem & Segev 1987]
Doron Rotem, Arie Segev: Physical Organization of Temporal Data. ICDE 1987: 547-553 BibTeX
[Roussopoulos 1982a]
Nick Roussopoulos: View Indexing in Relational Databases. ACM Trans. Database Syst. 7(2): 258-290(1982) BibTeX
[Roussopoulos 1982b]
Nick Roussopoulos: The Logical Access Path Schema of a Database. IEEE Trans. Software Eng. 8(6): 563-573(1982) BibTeX
[Roussopoulos 1987]
[Roussopoulos 1991]
Nick Roussopoulos: An Incremental Access Method for ViewCache: Concept, Algorithms, and Cost Analysis. ACM Trans. Database Syst. 16(3): 535-563(1991) BibTeX
[Roussopoulos & Kang 1986]
Nick Roussopoulos, Hyunchul Kang: Principles and Techniques in the Design of ADMS±. IEEE Computer 19(12): 19-25(1986) BibTeX
[Rowe & Stonebraker 1987]
[Salzberg & Lomet 1989]
David B. Lomet, Betty Salzberg: Access Methods for Multiversion Data. SIGMOD Conference 1989: 315-324 BibTeX
[Sedgewick 1988]
[Segev & Fang 1989]
[Segev & Gunadhi 1989]
Arie Segev, Himawan Gunadhi: Event-Join Optimization in Temporal Relational Databases. VLDB 1989: 205-215 BibTeX
[Segev & Fang 1990]
Arie Segev, Weiping Fang: Currency-Based Updates to Distributed Materialized Views. ICDE 1990: 512-520 BibTeX
[Selinger et al. 1979]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[Sellis 1986]
Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 BibTeX
[Sellis 1987]
Timos K. Sellis: Efficiently Supporting Procedures in Relational Database Systems. SIGMOD Conference 1987: 278-291 BibTeX
[Sellis 1988a]
Timos K. Sellis: Intelligent caching and indexing techniques for relational database systems. Inf. Syst. 13(2): 175-185(1988) BibTeX
[Sellis 1988b]
Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX
[Sellis & Shapiro 1985]
Timos K. Sellis, Leonard D. Shapiro: Optimization of Extended Database Query Languages. SIGMOD Conference 1985: 424-436 BibTeX
[Sellis et al. 1990]
Timos K. Sellis, Nick Roussopoulos, Raymond T. Ng: Efficient compilation of large rule bases using logical access paths. Inf. Syst. 15(1): 73-84(1990) BibTeX
[Shapiro 1986]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
[Shoshani & Kawagoe 1986]
Arie Shoshani, Kyoji Kawagoe: Temporal Data Management. VLDB 1986: 79-88 BibTeX
[Smith & 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) 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 & Ahn 1985]
Richard T. Snodgrass, Ilsoo Ahn: A Taxonomy of Time in Databases. SIGMOD Conference 1985: 236-246 BibTeX
[Snodgrass & Ahn 1988]
Ilsoo Ahn, Richard T. Snodgrass: Partitioned storage for temporal databases. Inf. Syst. 13(4): 369-391(1988) BibTeX
[Stam & Snodgrass 1988]
Robert B. Stam, Richard T. Snodgrass: A Bibliography on Temporal Databases. IEEE Data Eng. Bull. 11(4): 53-61(1988) BibTeX
[Stamenas 1989]
[Ullman 1982]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
[Wong & Youseffi 1976]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[Yang & Larson 1985]
Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269 BibTeX

Referenced by

  1. Nick Roussopoulos: Materialized Views and Data Warehouses. SIGMOD Record 27(1): 21-26(1998)
  2. Christian S. Jensen, Richard T. Snodgrass, Michael D. Soo: Extending Existing Dependency Theory to Temporal Databases. IEEE Trans. Knowl. Data Eng. 8(4): 563-582(1996)
  3. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
  4. Catherine Hamon, Arthur M. Keller: Two-Level Caching of Composite Object Views of Relational Databases. ICDE 1995: 428-437
  5. Christian S. Jensen, Richard T. Snodgrass: Temporal Specialization and Generalization. IEEE Trans. Knowl. Data Eng. 6(6): 954-974(1994)
  6. Michael D. Soo, Richard T. Snodgrass, Christian S. Jensen: Efficient Evaluation of the Valid-Time Natural Join. ICDE 1994: 282-292
  7. Chung-Min Chen, Nick Roussopoulos: The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching. EDBT 1994: 323-336
  8. Christian S. Jensen, Michael D. Soo, Richard T. Snodgrass: Unification of Temporal Data Models. ICDE 1993: 262-271
  9. Christian S. Jensen, Leo Mark: Queries on Change in an Extended Relational Model. IEEE Trans. Knowl. Data Eng. 4(2): 192-200(1992)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:31:18 2009