Decomposition - A Strategy for Query Processing.

@article{DBLP:journals/tods/WongY76,
  author    = {Eugene Wong and
               Karel Youssefi},
  title     = {Decomposition - A Strategy for Query Processing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {1},
  number    = {3},
  year      = {1976},
  pages     = {223-241},
  ee        = {http://doi.acm.org/10.1145/320473.320479, db/journals/tods/WongY76.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1976 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]

...

[2]

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

[3]

E. F. Codd: Seven Steps to Rendezvous with the Casual User. IFIP Working Conference Data Base Management 1974: 179-200 BibTeX

[4]

...

[5]

Nancy H. McDonald, Michael Stonebraker: CUPID - The Friendly Query Language. ACM Pacific 1975: 127-131 BibTeX

[6]

...

[7]

Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49 BibTeX

[8]

Dennis Ritchie, Ken Thompson: The UNIX Time-Sharing System. Commun. ACM 17(7): 365-375(1974) BibTeX

[9]

...

[10]

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

[11]

...

[12]

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

[13]

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

[14]

Stephen Todd: PRTV: An Efficient Implementation for Large Relational Data Bases. VLDB 1975: 554-556 BibTeX

[15]

...

Referenced by

1. Zachary G. Ives, Daniela Florescu, Marc Friedman, Alon Y. Levy, Daniel S. Weld: An Adaptive Query Execution System for Data Integration. SIGMOD Conference 1999: 299-310
2. Jia Liang Han: Optimizing Relational Queries in Connection Hypergraphs: Nested Queries, Views, and Binding Propagations. VLDB J. 7(1): 1-11(1998)
3. Joseph M. Hellerstein: Optimization Techniques for Queries with Expensive Methods. ACM Trans. Database Syst. 23(2): 113-157(1998)
4. Fa-Chung Fred Chen, Margaret H. Dunham: Common Subexpression Processing in Multiple-Query Processing. IEEE Trans. Knowl. Data Eng. 10(3): 493-499(1998)
5. Subbu N. Subramanian, Shivakumar Venkataraman: Cost-Based Optimization of Decision Support Queries Using Transient Views. SIGMOD Conference 1998: 319-330
6. Navin Kabra, David J. DeWitt: Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. SIGMOD Conference 1998: 106-117
7. Michael Steinbrunn, Guido Moerkotte, Alfons Kemper: Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB J. 6(3): 191-208(1997)
8. Ee-Peng Lim, Ying Lu: Distributed Query Processing for Clustered and Bibliographic Databases. DASFAA 1997: 441-450
9. Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)
10. Sha Guo, Wei Sun, Mark Allen Weiss: On Satisfiability, Equivalence, and Impication Problems Involving Conjunctive Queries in Database Systems. IEEE Trans. Knowl. Data Eng. 8(4): 604-616(1996)
11. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
12. Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994)
13. G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79
14. 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)
15. Kien A. Hua, Yu-lung Lo, Honesty C. Young: Considering Data Skew Factor in Multi-Way Join Query Optimization for Parallel Execution. VLDB J. 2(3): 303-330(1993)
16. 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)
17. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
18. Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
19. Nabil Kamel, Roger King: Intelligent Database Caching Through the Use of Page-Answers and Page-Traces. ACM Trans. Database Syst. 17(4): 601-646(1992)
20. Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992)
21. Shinichi Morishita: Avoiding Cartesian Products in Programs for Multiple Joins. PODS 1992: 368-379
22. Jean-Pierre Cheiney, Rosana S. G. Lanzelotte: A Model for Optimizing Deductive and Object-Oriented DB Requests. ICDE 1992: 385-392
23. Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991)
24. Walid G. Aref, Hanan Samet: Optimization for Spatial Query Processing. VLDB 1991: 81-90
25. Chihping Wang, Victor O. K. Li, Arbee L. P. Chen: Distributed Query Optimization by One-Shot Fixed-Precision Semi-Join Execution. ICDE 1991: 756-763
26. Rosana S. G. Lanzelotte, Jean-Pierre Cheiney: Adapting Relational Optimization Technology to Deductive and Object-Oriented Declarative Database Languages. DBPL 1991: 322-336
27. Kenichi Yajima, Hiroyuki Kitagawa, Kazunori Yamaguchi, Nobuo Ohbo, Yuzuru Fujiwara: Optimization of Queries Including ADT Functions. DASFAA 1991: 366-373
28. 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)
29. Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325
30. Y. C. Tay: On the Optimality of Strategies for Multiple Joins. PODS 1990: 124-131
31. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
32. Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366
33. Elisabetta Grazzini, Fabio Pippolini: A Strategy for Executing Complex Queries. MFDBS 1989: 207-221
34. Arie Segev, Jooseok Park: Maintaining Materialized Views in Distributed Databases. ICDE 1989: 262-270
35. David A. Bell, D. H. O. Ling, Sally I. McClean: Pragmatic Estimation of Join Sizes and Attribute Correlations. ICDE 1989: 76-84
36. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
37. Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988)
38. Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)
39. Shashi Shekhar, Jaideep Srivastava, Soumitra Dutta: A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. VLDB 1988: 457-467
40. Anant Jhingran: A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures. VLDB 1988: 88-99
41. Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
42. M. Muralikrishna, David J. DeWitt: Optimization of Multiple-Relation Multiple-Disjunct Queries. PODS 1988: 263-275
43. Don S. Batory: Concepts for a Database System Compiler. PODS 1988: 184-192
44. Kyu-Young Whang, Stephen Brady: A Framework for Optimization in Expert System - DBMS Interface. ICDE 1988: 126-133
45. Jooseok Park, Arie Segev: Using Common Subexpressions to Optimize Multiple Queries. ICDE 1988: 311-319
46. Ming-Chien Shan: Optimal Plan Search in a Rule-Based Query Optimizer. EDBT 1988: 92-112
47. Michael Stonebraker, Jeff Anton, Eric N. Hanson: Extending a Database System with Procedures. ACM Trans. Database Syst. 12(3): 350-376(1987)
48. Kazimierz Subieta, Wiktor Rzeczkowski: Query Optimization by Stored Queries. VLDB 1987: 369-380
49. Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146
50. Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208
51. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: A System for Semantic Query Optimization. SIGMOD Conference 1987: 181-195
52. Timos K. Sellis: Efficiently Supporting Procedures in Relational Database Systems. SIGMOD Conference 1987: 278-291
53. Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22
54. Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172
55. Joachim Biskup, Hans Hermann Brüggemann: Data Manipulation Languages for the Universal Relation View DURST. MFDBS 1987: 20-41
56. Setrag Khoshafian, George P. Copeland, Thomas Jagodis, Haran Boral, Patrick Valduriez: A Query Processing Strategy for the Decomposed Storage Model. ICDE 1987: 636-643
57. Arie Segev: Optimization of Join Operations in Horizontally Partitioned Database Systems. ACM Trans. Database Syst. 11(1): 48-80(1986)
58. Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986)
59. James A. Thom, Kotagiri Ramamohanarao, Lee Naish: A Superjoin Algorithm for Deductive Databases. VLDB 1986: 189-196
60. Louiqa Raschid, Stanley Y. W. Su: A Parallel Processing Strategy for Evaluating Recursive Queries. VLDB 1986: 412-419
61. Upen S. Chakravarthy, Jack Minker: Multiple Query Processing in Deductive Databases using Query Graphs. VLDB 1986: 384-391
62. Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205
63. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
64. José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71
65. Michael Kifer, Eliezer L. Lozinskii: Filtering Data Flow in Deductive Databases. ICDT 1986: 186-202
66. Stanley Y. W. Su, Krishna P. Mikkilineni, Raymond A. Liuzzi, Yuan-Chieh Chow: A Distributed Query Processing Strategy Using Decomposition, Pipelining and Intermediate Result Sharing Techniques. ICDE 1986: 94-102
67. Guy M. Lohman: Do semantically equivalent SQL queries perform differently? ICDE 1986: 225-226
68. Hongjun Lu, Michael J. Carey: Some Experimental Results on Distributed Join Algorithms in a Local Network. VLDB 1985: 292-304
69. Aviel Klausner, Nathan Goodman: Multirelations - Semantice and Languages. VLDB 1985: 251-258
70. Timos K. Sellis, Leonard D. Shapiro: Optimization of Extended Database Query Languages. SIGMOD Conference 1985: 424-436
71. Ashok Pahwa, Adarsh K. Arora: Automatic Database Navigation: Towards a High Level User Interface. ER 1985: 36-43
72. Henry F. Korth, Gabriel M. Kuper, Joan Feigenbaum, Allen Van Gelder, Jeffrey D. Ullman: System/U: A Database System Based on the Universal Relation Assumption. ACM Trans. Database Syst. 9(3): 331-347(1984)
73. Won Kim, Daniel Gajski, David J. Kuck: A Parallel Pipelined Relational Query Processor. ACM Trans. Database Syst. 9(2): 214-242(1984)
74. Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984)
75. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
76. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
77. 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
78. Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175
79. Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306
80. Huei-Huang Chen, Sharon McCure Kuck: Combining Relational and Network Retrieval Methods. SIGMOD Conference 1984: 131-142
81. Giovanni Maria Sacco: Distributed Query Evaluation in Local Area Networks. ICDE 1984: 510-516
82. Yahiko Kambayashi, Masatoshi Yoshikawa: Query Processing Utilizing Dependencies and Horizontal Decomposition. SIGMOD Conference 1983: 55-67
83. Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206
84. Arvola Chan, Umeshwar Dayal, Stephen Fox, Nathan Goodman, Daniel R. Ries, Dale Skeen: Overview of an Ada Compatible Distributed Database Manager. SIGMOD Conference 1983: 228-237
85. Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136
86. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
87. Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982)
88. Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982)
89. Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982)
90. Edward Babb: Joined Normal Form: A Storage Encoding for Relational Databases. ACM Trans. Database Syst. 7(4): 588-614(1982)
91. Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255
92. Anthony C. Klug: Access Paths in the 'ABE' Statistical Query Facility. SIGMOD Conference 1982: 161-173
93. Matthias Jarke, Joachim W. Schmidt: Query Processing Strategies in the PASCAL/R Relational Database Management System. SIGMOD Conference 1982: 256-264
94. Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245
95. Philip A. Bernstein, Barbara T. Blaustein: Fast Methods for Testing Quantified Relational Calculus Assertions. SIGMOD Conference 1982: 39-50
96. Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22
97. Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157
98. Nathan Goodman, Oded Shmueli: Transforming Cyclic Schemas into Trees. PODS 1982: 49-54
99. Stanley Y. W. Su, Herman Lam, Der Her Lo: Transformation of Data Traversals and Operations in Application Programs to Account for Semantic Changes of Databases. ACM Trans. Database Syst. 6(2): 255-294(1981)
100. Reind P. van de Riet, Anthony I. Wasserman, Martin L. Kersten, Wiebren de Jonge: High-Level Programming Features for Improving the Efficiency of a Relational Database System. ACM Trans. Database Syst. 6(3): 464-485(1981)
101. Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981)
102. Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Data Base Design. VLDB 1981: 320-332
103. David H. D. Warren: Efficient Processing of Interactive Relational Data Base Queries expressed in Logic. VLDB 1981: 272-281
104. Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
105. Akifumi Makinouchi, Masayoshi Tezuka, Hajime Kitakami, S. Adachi: The Optimization Strategy for Query Evaluation in RDB/V1. VLDB 1981: 518-529
106. David J. DeWitt, Paula B. Hawthorn: A Performance Evaluation of Data Base Machine Architectures (Invited Paper). VLDB 1981: 199-214
107. Anthony C. Klug: Abe: A Query Language for Constructing Aggregates-by-Example. SSDBM 1981: 190-205
108. Michael Stonebraker: Retrospection on a Database System. ACM Trans. Database Syst. 5(2): 225-240(1980)
109. Tore Risch: Production Program Generation in a Flexible Data Dictionary System. VLDB 1980: 343-349
110. Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147
111. Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101
112. Michael Stonebraker, Kenneth Keller: Embedding Expert Knowledge and Hypothetical Data Bases Into a Data Base System. SIGMOD Conference 1980: 58-66
113. Won Kim: A New Way to Compute the Product and Join of Relations. SIGMOD Conference 1980: 179-187
114. S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979)
115. Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979)
116. Won Kim: Relational Database Systems. ACM Comput. Surv. 11(3): 187-211(1979)
117. Karel Youssefi, Eugene Wong: Query Processing in a Relational Database Management System. VLDB 1979: 409-417
118. V. W. Setzer: Program Development by Transformations Applied to Relational Database Queries. VLDB 1979: 436-443
119. Alain Pirotte: Fundamental and Secondary Issues in the Design of Non-Procedural Relational Languages. VLDB 1979: 239-250
120. 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
121. Lawrence A. Rowe, Kurt A. Shoens: Data Abstractions, Views and Updates in RIGEL. SIGMOD Conference 1979: 71-81
122. Paula B. Hawthorn, Michael Stonebraker: Performance Analysis of a Relational Data Base Management System. SIGMOD Conference 1979: 1-12
123. Anthony I. Wasserman: A Software Engineering View of Data Base Management. VLDB 1978: 23-35
124. K. C. Toth, Samy A. Mahmoud, J. Spruce Riordon, O. Sherif: The ADD System: An Architecture for Distributed Databases. VLDB 1978: 462-471
125. Yehoshua Sagiv, Mihalis Yannakakis: Equivalence among Relational Expressions with the Union and Difference Operation. VLDB 1978: 535-548
126. Ralph Grishman: The Simplification of Retrieval Requests Generated by Question-Answering Systems. VLDB 1978: 400-406
127. Michel E. Adiba, Jean-Claude Chupin, Robert Demolombe, Georges Gardarin, Jean Le Bihan: Issues in Distributed Data Base Management Systems: A Technical Overview. VLDB 1978: 89-110
128. S. Bing Yao, D. DeJong: Evaluation of Database Access Paths. SIGMOD Conference 1978: 66-77
129. Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180
130. Michael Stonebraker, Lawrence A. Rowe: Observations on Data Manipulation Languages and Their Embedding in General Purpose Programming Languages. VLDB 1977: 128-143
131. James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62
132. Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976)