On Optimizing an SQL-like Nested Query.

@article{DBLP:journals/tods/Kim82,
  author    = {Won Kim},
  title     = {On Optimizing an SQL-like Nested Query},
  journal   = {ACM Trans. Database Syst.},
  volume    = {7},
  number    = {3},
  year      = {1982},
  pages     = {443-469},
  ee        = {http://doi.acm.org/10.1145/319732.319745, db/journals/tods/Kim82.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1982 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

• 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/An3-1 or /cdrom

• 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/aDVD2 or /dvd

References

[1]

Morton M. Astrahan, Donald D. Chamberlin: Implementation of a Structured English Query Language. Commun. ACM 18(10): 580-588(1975) BibTeX

[2]

Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX

[3]

...

[4]

Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX

[5]

Donald D. Chamberlin, Raymond F. Boyce: SEQUEL: A Structured English Query Language. SIGMOD Workshop, Vol. 1 1974: 249-264 BibTeX

[6]

...

[7]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[8]

E. F. Codd: A Database Sublanguage Founded on the Relational Calculus. SIGFIDET Workshop 1971: 35-68 BibTeX

[9]

E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX

[10]

E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX

[11]

B. Czarnik, Stewart A. Schuster, Dennis Tsichritzis: ZETA: A Relational Data Base Management System. ACM Pacific 1975: 21-25 BibTeX

[12]

C. J. Date: An Introduction to Database Systems, 2nd Edition. Addison-Wesley 1977
BibTeX

[13]

...

[14]

...

[15]

...

[16]

...

[17]

James B. Rothnie Jr.: An Approach to Implementing a Relational Data Management System. SIGMOD Workshop, Vol. 1 1974: 277-294 BibTeX

[18]

...

[19]

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

[20]

John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX

[21]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

[22]

...

[23]

...

[24]

Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

Referenced by

1. Kian-Lee Tan, Cheng Hian Goh, Beng Chin Ooi: Online Feedback for Nested Aggregate Queries with Multi-Threading. VLDB 1999: 18-29
2. Jia Liang Han: Optimizing Relational Queries in Connection Hypergraphs: Nested Queries, Views, and Binding Propagations. VLDB J. 7(1): 1-11(1998)
3. Mitch Cherniack, Stanley B. Zdonik: Inferring Function Semantics to Optimize Queries. VLDB 1998: 239-250
4. Jun Rao, Kenneth A. Ross: Reusing Invariants: A New Strategy for Correlated Queries. SIGMOD Conference 1998: 37-48
5. Leonidas Fegaras: Query Unnesting in Object-Oriented Databases. SIGMOD Conference 1998: 49-60
6. Mitch Cherniack, Stanley B. Zdonik: Changing the Rules: Transformations for Rule-Based Optimizers. SIGMOD Conference 1998: 61-72
7. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
8. Ahmed Mostefaoui, Jacques Kouloumdjian: Translating Relational Queries to Object-Oriented Queries According to ODMG-93. ADBIS 1998: 328-338
9. César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73(1997)
10. Pedro Celis, Hansjörg Zeller: Subquery Elimination: A Complete Unnesting Algorithm for an Extended Relational Algebra. ICDE 1997: 321
11. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. ACM Trans. Database Syst. 21(1): 107-155(1996)
12. Myra Spiliopoulou, Michael Hatzopoulos, Yannis Cotronis: Parallel Optimization of Large Join Queries with Set Operators and Aggregates in a Parallel Environment Supporting Pipeline. IEEE Trans. Knowl. Data Eng. 8(3): 429-445(1996)
13. William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121
14. Mitch Cherniack, Stanley B. Zdonik: Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conference 1996: 401-412
15. Praveen Seshadri, Hamid Pirahesh, T. Y. Cliff Leung: Complex Query Decorrelation. ICDE 1996: 450-458
16. Hennie J. Steenhagen, Rolf A. de By, Henk M. Blanken: Translating OSQL-Queries into Efficient Set Expressions. EDBT 1996: 183-197
17. Alon Y. Levy, Inderpal Singh Mumick: Reasoning with Aggregation Constraints. EDBT 1996: 514-534
18. Surajit Chaudhuri, Kyuseok Shim: Optimizing Queries with Aggregate Views. EDBT 1996: 167-182
19. Marjorie Templeton, Herbert Henley, Edward Maros, Darrel J. Van Buer: InterViso: Dealing With the Complexity of Federated Database Access. VLDB J. 4(2): 287-317(1995)
20. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
21. Weiyi Meng, Clement T. Yu, Won Kim: A Theory of Translation From Relational Queries to Hierarchical Queries. IEEE Trans. Knowl. Data Eng. 7(2): 228-245(1995)
22. Surajit Chaudhuri, Kyuseok Shim: An Overview of Cost-based Optimization of Queries with Aggregates. IEEE Data Eng. Bull. 18(3): 3-9(1995)
23. Weining Zhang, Clement T. Yu, Bryan Reagan, Hiroshi Nakajima: Context-Dependent Interpretations of Linguistic Terms in Fuzzy Relational Databases. ICDE 1995: 139-146
24. Qi Yang, Chengwen Liu, Jing Wu, Clement T. Yu, Son Dao, Hiroshi Nakajima: Efficient Processing of Nested Fuzzy SQL Queries. ICDE 1995: 131-138
25. Nick Kline, Richard T. Snodgrass: Computing Temporal Aggregates. ICDE 1995: 222-231
26. Sophie Cluet, Guido Moerkotte: Efficient Evaluation of Aggregates on Bulk Types. DBPL 1995: 8
27. Mark W. W. Vermeer, Peter M. G. Apers: Object-Oriented Views of Relational Databases Incorporating Behaviour. DASFAA 1995: 26-35
28. Gary C. K. Lam, Vincent Y. Lum, Kam-Fai Wong: On the Issues of Expressiveness and Portability of Chiql. DASFAA 1995: 164-171
29. Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken, Rolf A. de By: From Nested-Loop to Join Queries in OODB. VLDB 1994: 618-629
30. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107
31. Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366
32. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441
33. Inderpal Singh Mumick, Hamid Pirahesh: Implementation of Magic-sets in a Relational Database System. SIGMOD Conference 1994: 103-114
34. Weipeng P. Yan, Per-Åke Larson: Performing Group-By before Join. ICDE 1994: 89-100
35. G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79
36. Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken: Optimization of Nested Queries in a Complex Object Model. EDBT 1994: 337-350
37. Song Bong Yoo, Phillip C.-Y. Sheu: Evaluation and Optimization of Query Programs in an Object-Oriented and Symbolic Information System. IEEE Trans. Knowl. Data Eng. 5(3): 479-495(1993)
38. Richard L. Cole, Mark J. Anderson, Robert J. Bestgen: Query Processing in the IBM Application System/400. IEEE Data Eng. Bull. 16(4): 19-28(1993)
39. Alexander Borgida, Ronald J. Brachman: Loading Data into Description Reasoners. SIGMOD Conference 1993: 217-226
40. Weiyi Meng, Clement T. Yu, Won Kim, Gaoming Wang, Tracy Pham, Son Dao: Construction of a Relational Front-end for Object-Oriented Database Systems. ICDE 1993: 476-483
41. Sophie Cluet, Guido Moerkotte: Nested Queries in Object Bases. DBPL 1993: 226-242
42. M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102
43. Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48
44. Daniel F. Lieuwen, David J. DeWitt: A Transformation-Based Approach to Optimizing Loops in Database Programming Languages. SIGMOD Conference 1992: 91-100
45. Takao Miura: Nesting Quantification in a Visual Data Manipulation Language. ER 1992: 226-242
46. Nick Roussopoulos: An Incremental Access Method for ViewCache: Concept, Algorithms, and Cost Analysis. ACM Trans. Database Syst. 16(3): 535-563(1991)
47. Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991)
48. Mauro Negri, Giuseppe Pelagatti: Distributive Join: A New Algorithm for Joining Relations. ACM Trans. Database Syst. 16(4): 655-669(1991)
49. Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589
50. Leonore Neugebauer: Optimization and Evaluation of Database Queries Including Embedded Interpolation Procedures. SIGMOD Conference 1991: 118-127
51. Daniel F. Lieuwen, David J. DeWitt: Optimizing Loops in Database Programming Languages. DBPL 1991: 287-305
52. M. Nakano, T. Hiraishi, M. Kobayashi, T. Konagaya, T. Mikata: The Implementation of DBMS for the Specific Field. DASFAA 1991: 381-385
53. Hirofumi Amano, Yahiko Kambayashi: Translation of SQL Queries Containing Nested Predicated into Pseudonatural Language. DASFAA 1991: 116-125
54. Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990)
55. Ryohei Nakano: Translation with Optimization from Relational Calculus to Relational Algebra Having Aggregate Functions. ACM Trans. Database Syst. 15(4): 518-557(1990)
56. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
57. Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. ICDT 1990: 72-88
58. Kyu-Young Whang, Ashok Malhotra, Gary H. Sockut, Luanne M. Burns: Supporting Universal Quantification in a Two-Dimensional Database Query Language. ICDE 1990: 68-75
59. Gultekin Özsoyoglu, Victor Matos, Z. Meral Özsoyoglu: Query Processing Techniques in the Summary-Table-by-Example Database Query Language. ACM Trans. Database Syst. 14(4): 526-573(1989)
60. M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85
61. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
62. Beng Chin Ooi, Ron Sacks-Davis, Ken J. McDonell: Extending a DBMS for Geographic Applications. ICDE 1989: 590-597
63. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
64. Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)
65. Anant Jhingran: A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures. VLDB 1988: 88-99
66. Richard T. Snodgrass: The Temporal Query Language TQuel. ACM Trans. Database Syst. 12(2): 247-298(1987)
67. Kyu-Young Whang, Shamkant B. Navathe: An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments. VLDB 1987: 275-287
68. Theo Härder, Klaus Meyer-Wegener, Bernhard Mitschang, Andrea Sikeler: PRIMA - a DBMS Prototype Supporting Engineering Applications. VLDB 1987: 433-442
69. Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208
70. Günter von Bültzingsloewen: Translating and Optimizing SQL Queries Having Aggregates. VLDB 1987: 235-243
71. Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33
72. Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986)
73. W. S. Luk, Steve Kloster: ELFS: English Language From SQL. ACM Trans. Database Syst. 11(4): 447-472(1986)
74. Werner Kießling: On Semantic Reefs and Efficient Processing of Correlation Queries with Aggregates. VLDB 1985: 241-250
75. Robert M. MacGregor: ARIEL - A Semantic Front-End to Relational DBMSs. VLDB 1985: 305-315
76. Gultekin Özsoyoglu, Victor Matos: On Optimizing Summary-Table-by-Example Queries. PODS 1985: 38-50
77. Won Kim, Daniel Gajski, David J. Kuck: A Parallel Pipelined Relational Query Processor. ACM Trans. Database Syst. 9(2): 214-242(1984)
78. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
79. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
80. Arnon Rosenthal, David S. Reiner: Extending the Algebraic Framework of Query Processing to Handle Outerjoins. VLDB 1984: 334-343
81. Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415
82. Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306
83. Huei-Huang Chen, Sharon McCure Kuck: Combining Relational and Network Retrieval Methods. SIGMOD Conference 1984: 131-142
84. Stefano Ceri, Giuseppe Pelagatti: Correctness of Query Execution Strategies in Distributed Databases. ACM Trans. Database Syst. 8(4): 577-607(1983)
85. Illka Karasalo, Per Svensson: An Overview of Cantor - A New System for Data Analysis. SSDBM 1983: 315-324
86. Guy M. Lohman, Joseph C. Stoltzfus, Anita N. Benson, Michael D. Martin, Alfonso F. Cardenas: Remotely-Sensed Geophysical Databases: Experience and Implications for Generalized DBMS. SIGMOD Conference 1983: 146-160
87. Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206
88. Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136
89. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents