Incremental Computation of Nested Relational Query Expressions.

Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  author    = {Lars B{\ae}kgaard and
               Leo Mark},
  title     = {Incremental Computation of Nested Relational Query Expressions},
  journal   = {ACM Trans. Database Syst.},
  volume    = {20},
  number    = {2},
  year      = {1995},
  pages     = {111-148},
  ee        = {, db/journals/tods/BaekgaardM95.html},
  bibsource = {DBLP,}


Efficient algorithms for incrementally computing nested query expressions do not exist. Nested query expressions are query expressions in which selection/join predicates contain subqueries. In order to respond to this problem, we propose a two-step strategy for incrementaly computing nested query expressions. In step (1), the query expression is transformed into an equivalent unnested flat query expression. In step (2), the flat query expression is incrementally computed. To support step (1), we have developed a very concise algebra-to-algebra transformation algorithm, and we have formally proved its correctness. The flat query expressions resulting from the transformation make intensive use of the relational set-difference operator. To support step (2), we present and analyze an efficient algorithm for incrementally computing set differences based on view pointer caches. When combined with existing incremental algorithms for SPJ queries, our incremental set-difference algorithm can be used to compute the unnested flat query expressions efficiently. It is important to notice that without our incremental set-difference algorithm the existing incremental algorithms for SPJ queries are useless for any query involving the set-difference operator, including queries that are not the result of unnesting nested queries.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 2356 KB]


[Astrahan 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
[Bækgaard 1993]
[Blakeley and Martin 1990]
José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263 BibTeX
[Blakeley et al. 1986]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[Bültzingsloewen 1987]
Günter von Bültzingsloewen: Translating and Optimizing SQL Queries Having Aggregates. VLDB 1987: 235-243 BibTeX
[Carey et al. 1990]
Michael J. Carey, Eugene J. Shekita, George Lapis, Bruce G. Lindsay, John McPherson: An Incremental Join Attachment for Starburst. VLDB 1990: 662-673 BibTeX
[Ceri and Gottlob 1985]
Stefano Ceri, Georg Gottlob: Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries. IEEE Trans. Software Eng. 11(4): 324-345(1985) BibTeX
[Ceri and Widom 1991]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589 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 1990]
[Colby 1989]
Latha S. Colby: A Recursive Algebra and Query Optimization for Nested Relations. SIGMOD Conference 1989: 273-283 BibTeX
[Dadashzadeh 1989]
Mohammad Dadashzadeh: An improved division operator for relational algebra. Inf. Syst. 14(5): 431-437(1989) BibTeX
[Dayal 1987]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX
[Ganski and Wong 1987]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX
[Gyssens and Van Gucht 1988]
Marc Gyssens, Dirk Van Gucht: The Powerset Algebra as a Result of Adding Programming Constructs to the Nested Relational Algebra. SIGMOD Conference 1988: 225-232 BibTeX
[Hanson et al. 1990]
Eric N. Hanson, Moez Chaabouni, Chang-Ho Kim, Yu-Wang Wang: A Predicate Matching Algorithm for Database Rule Systems. SIGMOD Conference 1990: 271-280 BibTeX
[Hanson 1987]
Eric N. Hanson: A Performance Analysis of View Materialization Strategies. SIGMOD Conference 1987: 440-453 BibTeX
[Hanson 1992]
Eric N. Hanson: Rule Condition Testing and Action Execution in Ariel. SIGMOD Conference 1992: 49-58 BibTeX
[Jarke 1985]
Matthias Jarke: Common Subexpression Isolation in Multiple Query Optimization. Query Processing in Database Systems 1985: 191-205 BibTeX
[Jarke and Koch 1984]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) 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
[Kim 1982]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
[Lindsay et al. 1986]
Bruce G. Lindsay, Laura M. Haas, C. Mohan, Hamid Pirahesh, Paul F. Wilms: A Snapshot Differential Refresh Algorithm. SIGMOD Conference 1986: 53-60 BibTeX
[Nakano 1990]
Ryohei Nakano: Translation with Optimization from Relational Calculus to Relational Algebra Having Aggregate Functions. ACM Trans. Database Syst. 15(4): 518-557(1990) BibTeX
[Negri and Pelagatti 1991]
Mauro Negri, Giuseppe Pelagatti: Distributive Join: A New Algorithm for Joining Relations. ACM Trans. Database Syst. 16(4): 655-669(1991) BibTeX
[Omiecinski 1989]
Edward Omiecinski: Heuristics for Join Processing Using Nonclustered Indexes. IEEE Trans. Software Eng. 15(1): 18-25(1989) BibTeX
[Özsoyoglu and Wang 1989]
Gultekin Özsoyoglu, Huaqing Wang: A Relational Calculus with Set Operators, Its Safety and Equivalent Graphical Languages. IEEE Trans. Software Eng. 15(9): 1038-1052(1989) BibTeX
[Özsoyoglu et al. 1987]
Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Victor Matos: Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions. ACM Trans. Database Syst. 12(4): 566-592(1987) BibTeX
[Özsu and Meechan 1990]
M. Tamer Özsu, David J. Meechan: Join processing heuristics in relational database systems. Inf. Syst. 15(4): 429-444(1990) BibTeX
[Paredaens and Van Gucht 1992]
Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992) BibTeX
[Qian and Wiederhold 1991]
Xiaolei Qian, Gio Wiederhold: Incremental Recomputation of Active Relational Expressions. IEEE Trans. Knowl. Data Eng. 3(3): 337-341(1991) BibTeX
[Rosenthal et al. 1989]
Arnon Rosenthal, Sharma Chakravarthy, Barbara T. Blaustein, José A. Blakeley: Situation Monitoring for Active Databases. VLDB 1989: 455-464 BibTeX
[Roth et al. 1988]
Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 13(4): 389-417(1988) BibTeX
[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
[Sacco 1986]
Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986) BibTeX
[Schek and Scholl 1986]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
[Scholl et al. 1987]
Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146 BibTeX
[Sellis 1986]
Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 BibTeX
[Severance and Lohman 1976]
Dennis G. Severance, Guy M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. ACM Trans. Database Syst. 1(3): 256-267(1976) BibTeX
[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) BibTeX
[Stonebraker et al. 1990]
Michael Stonebraker, Anant Jhingran, Jeffrey Goh, Spyros Potamianos: On Rules, Procedures, Caching and Views in Data Base Systems. SIGMOD Conference 1990: 281-290 BibTeX
[Thomas and Fischer 1986]
Stan J. Thomas, Patrick C. Fischer: Nested Relational Structures. Advances in Computing Research 3: 269-307(1986) BibTeX
[Ullman 1989-1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ullman 1989-2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[Valduriez 1987]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX
[Wolfson et al. 1991]
Ouri Wolfson, Hasanat M. Dewan, Salvatore J. Stolfo, Yechiam Yemini: Incremental Evaluation of Rules and its Relationship to Parallelism. SIGMOD Conference 1991: 78-87 BibTeX

Referenced by

  1. Lars Bækgaard, Leo Mark: Incremental Computation of Set Difference Views. IEEE Trans. Knowl. Data Eng. 9(2): 251-261(1997)
  2. Lars Bækgaard, Leo Mark: Incremental Computation of Time-Varying Query Expressions. IEEE Trans. Knowl. Data Eng. 7(4): 583-590(1995)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:18 2008