Optimization of Query Evaluation Algorithms.

@article{DBLP:journals/tods/Yao79,
  author    = {S. Bing Yao},
  title     = {Optimization of Query Evaluation Algorithms},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {2},
  year      = {1979},
  pages     = {133-155},
  ee        = {http://doi.acm.org/10.1145/320071.320072, db/journals/tods/Yao79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

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

[4]

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

[5]

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

[6]

Leo R. Gotlieb: Computing Joins of Relations. SIGMOD Conference 1975: 55-63 BibTeX

[7]

Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX

[8]

...

[9]

...

[10]

Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX

[11]

Jane W.-S. Liu: Algorithms for Parsing Search Queries in Systems with Inverted File Organization. ACM Trans. Database Syst. 1(4): 299-316(1976) BibTeX

[12]

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

[13]

...

[14]

Mario Schkolnick: A Clustering Algorithm for Hierarchical Structures. ACM Trans. Database Syst. 2(1): 27-44(1977) BibTeX

[15]

Nan C. Shu, Barron C. Housel, Robert W. Taylor, Sakti P. Ghosh, Vincent Y. Lum: EXPRESS: A Data EXtraction, Processing, amd REStructuring System. ACM Trans. Database Syst. 2(2): 134-174(1977) BibTeX

[16]

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

[17]

...

[18]

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

[19]

S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977) BibTeX

[20]

S. Bing Yao, D. DeJong: Evaluation of Database Access Paths. SIGMOD Conference 1978: 66-77 BibTeX

[21]

...

[22]

Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX

Referenced by

1. Michael J. Carey, Donald Kossmann: Reducing the Braking Distance of an SQL Query Engine. VLDB 1998: 158-169
2. Jaroslaw A. Chudziak, Janusz R. Getta: On Efficient Query Evaluation in Multidatabase Systems. ADBIS 1995: 73-89
3. Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994)
4. Claudio Sartori, Maria Rita Scalas: Partial Indexing for Nonuniform Data Distributions in relational DBMS's. IEEE Trans. Knowl. Data Eng. 6(3): 420-429(1994)
5. Nick Roussopoulos: An Incremental Access Method for ViewCache: Concept, Algorithms, and Cost Analysis. ACM Trans. Database Syst. 16(3): 535-563(1991)
6. Mauro Negri, Giuseppe Pelagatti: Distributive Join: A New Algorithm for Joining Relations. ACM Trans. Database Syst. 16(4): 655-669(1991)
7. Ken-Chih Liu, Lu Zhang: Natural Joins in Relational Databases with Indefinite and Maybe Information. ICDE 1991: 132-139
8. Kyung-Chang Kim: Performance of Query Optimization Heuristics in Object-Oriented Databases. DASFAA 1991: 99-108
9. 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)
10. Ryohei Nakano: Translation with Optimization from Relational Calculus to Relational Algebra Having Aggregate Functions. ACM Trans. Database Syst. 15(4): 518-557(1990)
11. Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990)
12. Y. C. Tay: On the Optimality of Strategies for Multiple Joins. PODS 1990: 124-131
13. Kyung-Chang Kim: Parallelism in Object-Oriented Query Processing. ICDE 1990: 209-217
14. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
15. William Perrizo, Jonathan Y. Y. Lin, Wherly Hoffman: Algorithms for Distributed Query Processing in Broadcast Local Area Networks. IEEE Trans. Knowl. Data Eng. 1(2): 215-225(1989)
16. Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366
17. François Bry: Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited. SIGMOD Conference 1989: 193-204
18. Elisabetta Grazzini, Fabio Pippolini: A Strategy for Executing Complex Queries. MFDBS 1989: 207-221
19. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
20. M. Muralikrishna, David J. DeWitt: Optimization of Multiple-Relation Multiple-Disjunct Queries. PODS 1988: 263-275
21. Kyung-Chang Kim, Won Kim, Darrell Woelk, Alfred G. Dale: Acyclic Query Processing in Object-Oriented Databases. ER 1988: 329-346
22. Hai-Yann Hwang, Yao-Tin Yu: An Analytical Method for Estimating and Interpreting Query Time. VLDB 1987: 347-358
23. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: A System for Semantic Query Optimization. SIGMOD Conference 1987: 181-195
24. Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986)
25. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159
26. Robert B. Hagmann: An Observation on Database Buffering Performance Metrics. VLDB 1986: 289-293
27. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
28. Kazuhiro Satoh, Masashi Tsuchida, Fumio Nakamura, Kazuhiko Oomachi: Local and Global Query Optimization Mechanisms for Relational Databases. VLDB 1985: 405-417
29. Hongjun Lu, Michael J. Carey: Some Experimental Results on Distributed Join Algorithms in a Local Network. VLDB 1985: 292-304
30. Thomas W. Page Jr., Gerald J. Popek: Distributed Management in Local Area Networks. PODS 1985: 135-142
31. Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984)
32. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
33. 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
34. Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276
35. Huei-Huang Chen, Sharon McCure Kuck: Combining Relational and Network Retrieval Methods. SIGMOD Conference 1984: 131-142
36. Benjamin W. Wah, Yao-Nan Lien: The File-Assignment and Query-Processing Problems in Local Multiaccess Networks. ICDE 1984: 228-235
37. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
38. Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982)
39. Don S. Batory, C. C. Gotlieb: A Unifying Model of Physical Databases. ACM Trans. Database Syst. 7(4): 509-539(1982)
40. Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255
41. Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245
42. Umeshwar Dayal, Nathan Goodman: Query Optimization for CODASYL Database Systems. SIGMOD Conference 1982: 138-150
43. Haran Boral, David J. DeWitt: Processor Allocation Strategies for Multiprocessor Database Machines. ACM Trans. Database Syst. 6(2): 227-254(1981)
44. Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Data Base Design. VLDB 1981: 320-332
45. Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
46. Akifumi Makinouchi, Masayoshi Tezuka, Hajime Kitakami, S. Adachi: The Optimization Strategy for Query Evaluation in RDB/V1. VLDB 1981: 518-529
47. Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517
48. J. P. Armisen, J. Y. Caleca: A Commercial Back-End Data Base System. VLDB 1981: 56-65
49. Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147
50. Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63
51. Won Kim: A New Way to Compute the Product and Join of Relations. SIGMOD Conference 1980: 179-187
52. Haran Boral, David J. DeWitt: Design Considerations for Data-flow Database Machines. SIGMOD Conference 1980: 94-104
53. S. Bing Yao, D. DeJong: Evaluation of Database Access Paths. SIGMOD Conference 1978: 66-77