Query Optimization in Database Systems.

@article{DBLP:journals/csur/JarkeK84,
  author    = {Matthias Jarke and
               J{\"u}rgen Koch},
  title     = {Query Optimization in Database Systems},
  journal   = {ACM Comput. Surv.},
  volume    = {16},
  number    = {2},
  year      = {1984},
  pages     = {111-152},
  ee        = {db/journals/csur/JarkeK84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Efficient methods of processing unanticipated queries are a crucial prerequisite for the success of generalized database management systems. A wide variety of approaches to improve the performance of query evaluation algorithms have been proposed: logic-based and semantic transformations, fast implementations of basic operations, and combinatorial or heuristic algorithms for generating alternative access plans and choosing among them.

These methods are presented in the framework of a general query evaluation procedure using the relational calculus representation of queries. In addition, nonstandard query optimization issues such as higher level query evaluation, query optimization in distributed databases, and use of database machines are addressed. The focus, however, is on query optimization in centralized database systems.

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

ACM SIGMOD 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/An4-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

Online Edition: ACM Digital Library

References

[Aho et al. 1979a]

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979)

[Aho et al. 1979b]

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)

[Aho e tal. 1979c]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979)

[Andler et al. 1982]

Sten Andler, I. Ding, Kapali P. Eswaran, Carl Hauser, Won Kim, James W. Mehl, R. Williams: System D: A Distributed System for Availability. VLDB 1982: 33-44

[Apers et al. 1983]

Peter M. G. Apers, Alan R. Hevner, S. Bing Yao: Optimization Algorithms for Distributed Queries. IEEE Trans. Software Eng. 9(1): 57-68(1983)

[Astrahan and Chamberlin 1975]

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

[Astrahan and Ghosh 1974]

Morton M. Astrahan, Sakti P. Ghosh: A Search Path Selection Algorithm for the Data Independent Accessing Model (DIAM). SIGMOD Workshop, Vol. 1 1974: 367-388

[Astrahan et al. 1980]

Morton M. Astrahan, Mario Schkolnick, Won Kim: Performance of the System R Access Path Selection Mechanism. IFIP Congress 1980: 487-491

[Bancilhon et al. 1982]

François Bancilhon, Philippe Richard, Michel Scholl: On Line Processing of Compacted Relations. VLDB 1982: 263-269

[Banerjee and Hsiao 1979]

Jayanta Banerjee, David K. Hsiao, Krishnamurthi Kannan: DBC - A Database Computer for Very Large Databases. IEEE Trans. Computers 28(6): 414-429(1979)

[Batory 1982]

...

[Bayer and McCreight 1972]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)

[Bayer et al. 1984]

Rudolf Bayer, Klaus Elhardt, Werner Kießling, Dieter Killar: Verteilte Datenbanksysteme. Eine Übersicht über den heutigen Entwicklungsstand. Informatik Spektrum 7(1): 1-19(1984)

[Bentley and Friedman 1979]

Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979)

[Bernadat 1983]

...

[Bernstein and Chiu 1981]

Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981)

[Bernstein and Goodman 1981a]

Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981)

[Bernstein and Goodman 1981b]

Philip A. Bernstein, Nathan Goodman: The power of inequality semijoins. Inf. Syst. 6(4): 255-265(1981)

[Bernstein and Goodman 1981c]

Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981)

[Bernstein et al. 1980]

Philip A. Bernstein, Barbara T. Blaustein, Edmund M. Clarke: Fast Maintenance of Semantic Integrity Assertions Using Redundant Aggregate Data. VLDB 1980: 126-136

[Bernstein et al. 1981]

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)

[Berra and Oliver 1979]

...

[Bitton et al. 1983]

Dina Bitton, Haran Boral, David J. DeWitt, W. Kevin Wilkinson: Parallel Algorithms for the Execution of Relational Database Operations. ACM Trans. Database Syst. 8(3): 324-353(1983)

[Blasgen and Eswaran 1976]

...

[Blasgen and Eswaran 1977]

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

[Bolour 1981]

Azad Bolour: Optimal Retrieval Algorithms for Small Region Queries. SIAM J. Comput. 10(4): 721-741(1981)

[Breitbart and Reiter 1975]

Yuri Breitbart, Allen Reiter: Algorithms for Fast Evaluation of Boolean Expressions. Acta Inf. 4: 107-116(1975)

[Brodie et al. 1984]

Michael L. Brodie, John Mylopoulos, Joachim W. Schmidt (Eds.): On Conceptual Modelling, Perspectives from Artificial Intelligence, Databases, and Programming Languages, Book resulting from the Intervale Workshop 1982. Topics in Information Systems Springer 1984, ISBN 3-540-90842-0
Contents

[Buneman 1979]

Peter Buneman: The Problem of Multiple Paths in a Database Schema. VLDB 1979: 368-372

[Cardenas 1975]

Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975)

[Carlis et al. 1981]

...

[Carlson and Kaplan 1976]

C. Robert Carlson, Robert S. Kaplan: A Generalized Access Path Model and its Application to a Relational Data Base System. SIGMOD Conference 1976: 143-154

[Ceri and Pelagatti 1982]

Stefano Ceri, Giuseppe Pelagatti: Allocation of Operations in Distributed Database Access. IEEE Trans. Computers 31(2): 119-129(1982)

[Chamberlin et al. 1981]

Donald D. Chamberlin, Morton M. Astrahan, W. Frank King III, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Mario Schkolnick, Patricia G. Selinger, Donald R. Slutz, Bradford W. Wade, Robert A. Yost: Support for Repetitive Transactions and Ad Hoc Queries in System R. ACM Trans. Database Syst. 6(1): 70-94(1981)

[Chan and Niamir 1982]

Arvola Chan, Bahram Niamir: On Estimating the Cost of Accessing Records in Blocked Database Organizations. Comput. J. 25(3): 368-374(1982)

[Chan et al. 1983]

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

[Chandra and Harel 1982a]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982)

[Chandra and Harel 1982b]

Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163

[Chandra and Merlin 1977]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90

[Chang 1978]

Chin-Liang Chang: DEDUCE 2: Further Investigations of Deduction in Relational Data Bases. Logic and Data Bases 1977: 201-236

[Chang 1979]

Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260

[Chang 1982]

Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61

[Chen and Akoka 1980]

Peter P. Chen, Jacky Akoka: Optimal Design of Distributed Information Systems. IEEE Trans. Computers 29(12): 1068-1080(1980)

[Chesnais et al. 1983]

A. Chesnais, Erol Gelenbe, Isi Mitrani: On the Modeling of Parallel Access to Shared Data. Commun. ACM 26(3): 196-202(1983)

[Cheung 1982a]

To-Yat Cheung: A Method for Equijoin Queries in Distributed Relational Databases. IEEE Trans. Computers 31(8): 746-751(1982)

[Cheung 1982b]

To-Yat Cheung: Estimating Block Accesses and Number of Recorde in File Management. Commun. ACM 25(7): 484-487(1982)

[Chiu and Ho 1980]

D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178

[Chiu et al. 1981]

Dah-Ming W. Chiu, Philip A. Bernstein, Yu-Chi Ho: Optimizing Chain Queries in a Distributed Database System. SIAM J. Comput. 13(1): 116-134(1984)

[Christodoulakis 1981]

...

[Christodoulakis 1983]

Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54

[Chu and Hurley 1982]

Wesley W. Chu, Paul Hurley: Optimal Query Processing for Distributed Database Systems. IEEE Trans. Computers 31(9): 835-850(1982)

[Clausen 1980]

Svend-Erik Clausen: Optimizing the evaluation of calculus expressions in a relational database system. Inf. Syst. 5(1): 41-54(1980)

[Codd 1971]

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

[Codd 1972]

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)

[Daniels 1982]

...

[Daniels et al. 1982]

Dean Daniels, Patricia G. Selinger, Laura M. Haas, Bruce G. Lindsay, C. Mohan, Adrian Walker, Paul F. Wilms: An Introduction to Distributed Query Compilation in R*. DDB 1982: 291-309

[Davis and Winslow 1982]

Henry W. Davis, Leon E. Winslow: Computational Power in Query Languages. SIAM J. Comput. 11(3): 547-554(1982)

[Davis and Kunii 1982]

Larry S. Davis, Tosiyasu L. Kunii: Pattern Databases. Data Base Design Techniques II 1979: 357-399

[Dayal 1983a]

Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136

[Dayal 1983b]

Umeshwar Dayal: Processing Queries Over Generalization Hierarchies in a Multidatabase System. VLDB 1983: 342-353

[Dayal and Goodman 1982]

Umeshwar Dayal, Nathan Goodman: Query Optimization for CODASYL Database Systems. SIGMOD Conference 1982: 138-150

[Dayal et al. 1981]

...

[Demolombe 1980]

Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63

[DeWitt 1979]

David J. DeWitt: Query Execution in DIRECT. SIGMOD Conference 1979: 13-22

[Downey et al. 1980]

Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980)

[Eggers and Shoshani 1980]

Susan J. Eggers, Arie Shoshani: Efficient Access of Compressed Data. VLDB 1980: 205-211

[Epstein and Stonebraker 1980]

Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101

[Epstein et al. 1978]

Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180

[Esculier and Clorieux 1979]

Christian Esculier, A. M. Glorieux: The SIRIUS-DELTA Distributed DBMS. ER 1979: 543-552

[Eswaran et al. 1976]

Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976)

[Finkelstein 1982]

Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245

[Forker 1982]

H. J. Forker: Algebraical and Operational Methods for the Optimization of Query Processing in Distributed Relational Database Systems. DDB 1982: 39-59

[Gardarin et al. 1984]

Georges Gardarin, Patrick Valduriez, Yann Viémont: Predicate Trees: An Approach to Optimize Relational Query Operations. ICDE 1984: 439-444

[Gavish and Segev 1982]

...

[Gavish and Segev 1983]

...

[Gelenbe and Gardy 1982]

Erol Gelenbe, Danièle Gardy: The Size of Projections of Relations Satisfying a Functional Dependency. VLDB 1982: 325-333

[Gilles and Schuster 1975]

Gilles Farley, Stewart A. Schuster: Query Execution and Index Selection for Relational Data Bases. VLDB 1975: 519

[Goodman and Shmueli 1980]

...

[Goodman and Shmueli 1982]

Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982)

[Gotlieb 1975]

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

[Gouda and Dayal 1981]

Mohamed G. Gouda, Umeshwar Dayal: Optimal Semijoin Schedules For Query Processing in Local Distributed Database Systems. SIGMOD Conference 1981: 164-175

[Grant and Minker 1981]

John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234

[Gray 1981]

...

[Gray 1984]

...

[Gries 1971]

...

[Griffeth 1978]

Nancy D. Griffeth: Nonprocedural Query Processing for Databases with Access Paths. SIGMOD Conference 1978: 160-168

[Griffiths and Wade 1976]

Patricia P. Griffiths, Bradford W. Wade: An Authorization Mechanism for a Relational Database System. ACM Trans. Database Syst. 1(3): 242-255(1976)

[Grishman 1978]

Ralph Grishman: The Simplification of Retrieval Requests Generated by Question-Answering Systems. VLDB 1978: 400-406

[Gudes and Reiter 1973]

Ehud Gudes, A. Reiter: On Evaluating Boolean Expressions. Softw., Pract. Exper. 3(4): 345-350(1973)

[Hall 1974]

Patrick A. V. Hall: Common Subexpression Identification in General Algebraic Systems. Technical Rep. UKSC 0060, IBM United Kingdom Scientific Centre : (1974)

[Hall 1976]

Patrick A. V. Hall: Optimization of a Single Relation Expression in a Relational Data Base System. IBM J. Res. Dev. 20(3): 244-257(1976)

[Hammer and Niamir 1979]

Michael Hammer, Bahram Niamir: A Heuristic Approach to Attribute Partitioning. SIGMOD Conference 1979: 93-101

[Hammer and Zdonik 1980]

Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147

[Hanani 1977]

Michael Z. Hanani: An Optimal Evaluation of Boolean Expressions in an Online Query System. Commun. ACM 20(5): 344-347(1977)

[Hawthorn 1982]

Paula B. Hawthorn: Microprocessor Assisted Tuple Access, Decompression and Assembly for Statistical Database Systems. VLDB 1982: 223-233

[Henschen and Naqvi 1984]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984)

[Hevner 1979]

...

[Hevner and Yao 1979]

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

[Hsiao 1979]

...

[IBM Corporation 1966]

...

[IEEE 1982]

...

[Jarke 1984]

Matthias Jarke: Common Subexpression Isolation in Multiple Query Optimization. Query Processing in Database Systems 1985: 191-205

[Jarke and Koch 1983]

Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206

[Jarke and Schmidt 1981]

...

[Jarke and Schmidt 1982]

Matthias Jarke, Joachim W. Schmidt: Query Processing Strategies in the PASCAL/R Relational Database Management System. SIGMOD Conference 1982: 256-264

[Jarke and Vassiliou 1984]

...

[Jarke et al. 1984]

Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306

[Johnson and Klug 1982]

David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169

[Johnson and Klug 1983]

David S. Johnson, Anthony C. Klug: Optimizing Conjunctive Queries that Contain Untyped Variables. SIAM J. Comput. 12(4): 616-640(1983)

[Johnston et al. 1983]

...

[Kambayashi and Yoshikawa 1983]

Yahiko Kambayashi, Masatoshi Yoshikawa: Query Processing Utilizing Dependencies and Horizontal Decomposition. SIGMOD Conference 1983: 55-67

[Kambayashi et al. 1982]

Yahiko Kambayashi, Masatoshi Yoshikawa, Shuzo Yajima: Query Processing for Distributed Databases Using Generalized Semi-Joins. SIGMOD Conference 1982: 151-160

[Katz and Wong 1982]

Randy H. Katz, Eugene Wong: Decompiling CODASYL DML into Relational Queries. ACM Trans. Database Syst. 7(1): 1-23(1982)

[Kellogg 1982]

Charles Kellogg: Knowledge Management: A Practical Amalgam of Knowledge and Data Base Technology. AAAI 1982: 306-309

[Kerschberg et al. 1982]

Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982)

[Kim 1980]

Won Kim: A New Way to Compute the Product and Join of Relations. SIGMOD Conference 1980: 179-187

[Kim 1981]

...

[Kim 1982]

Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982)

[Kim 1984]

Won Kim: Global Optimization of Relational Queries: A First Step. Query Processing in Database Systems 1985: 206-216

[Kim et al. 1981]

...

[King 1979]

...

[King 1981]

Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517

[Klug 1980]

Anthony C. Klug: Calculating Constraints on Relational Expressions. ACM Trans. Database Syst. 5(3): 260-290(1980)

[Klug 1982a]

Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982)

[Klug 1982b]

Anthony C. Klug: Access Paths in the 'ABE' Statistical Query Facility. SIGMOD Conference 1982: 161-173

[Klug 1983]

Anthony C. Klug: Locking Expressions for Increased Database Concurrency. J. ACM 30(1): 36-54(1983)

[Koch et al. 1981]

...

[Kowalski 1981]

Robert A. Kowalski: Logic as a Database Language. BNCOD 1984: 103-132

[Kunifuji and Yokota 1982]

...

[Lamersdorf 1984]

Winfried Lamersdorf: Recursive Data Models for Non-Conventional Database Applications. ICDE 1984: 143-150

[Lang et al. 1977]

Tomás Lang, Christopher Wood, Eduardo B. Fernández: Database Buffer Paging in Virtual Storage Systems. ACM Trans. Database Syst. 2(4): 339-351(1977)

[Langdon 1979]

Glen G. Langdon Jr.: Database Machines: An Introduction. IEEE Trans. Computers 28(6): 381-383(1979)

[Leilich et al. 1978]

Hans-Otto Leilich, Günther Stiege, Hans Christoph Zeidler: A Search Processor for Data Base Management Systems. VLDB 1978: 280-287

[Lin et al. 1976]

Chyuan Shiun Lin, Diane C. P. Smith, John Miles Smith: The Design of a Rotating Associative Array Memory for a Relational Database Management Application. ACM Trans. Database Syst. 1(1): 53-65(1976)

[Liu 1976]

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

[Luk 1983]

W. S. Luk: On Estimating Block Accesses in Database Organizations. Commun. ACM 26(11): 945-947(1983)

[Maekawa 1982]

Mamoru Maekawa: Parallel Join and Sorting Algorithms. Data Base Design Techniques II 1979: 266-298

[Mahmoud et al. 1979]

...

[Maier 1983]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents

[Maier and Ullman 1983]

David Maier, Jeffrey D. Ullman: Fragments of Relations. SIGMOD Conference 1983: 15-22

[Maier and Warren 1981]

David Maier, David Scott Warren: Incorporating Computed Relations in Relational Databases. SIGMOD Conference 1981: 176-187

[Makinouchi et al. 1981]

Akifumi Makinouchi, Masayoshi Tezuka, Hajime Kitakami, S. Adachi: The Optimization Strategy for Query Evaluation in RDB/V1. VLDB 1981: 518-529

[Mall et al. 1984]

Manuel Mall, Joachim W. Schmidt, Manuel Reimer: Data Selection, Sharing, and Access Control In a Relational Scenario. On Conceptual Modelling (Intervale) 1982: 411-440

[Marburger and Nebel 1983]

Heinz Marburger, Bernhard Nebel: Natürlichsprachlicher Datenbankzugang mit HAM-ANS: Syntaktische Korrepsondenz, natürlichsprachliche Qualifizierung und semantisches Modell des Diskursbereichs. Sprachen für Datenbanken 1983: 26-41

[March 1983]

...

[Maryanski 1980]

Fred J. Maryanski: Backend Database Systems. ACM Comput. Surv. 12(1): 3-25(1980)

[Menon and Hsiao 1981]

M. J. Menon, David K. Hsiao: Design and Analysis of a Relational Join Operation for VLSI. VLDB 1981: 44-55

[Merrett 1977]

T. H. Merrett: Database Cost Analysis: a Top-Down Approach. SIGMOD Conference 1977: 135-143

[Merrett 1981]

T. H. Merrett: Why Sort-Merge Gives the Best Implementation of the Natural Join. SIGMOD Record 13(2): 39-51(1983)

[Merrett et al. 1981]

T. H. Merrett, Yahiko Kambayashi, H. Yasuura: Scheduling of Page-Fetches in Join Operations. VLDB 1981: 488-498

[Minker 1975]

Jack Minker: Performing Inferences over Relation Data Bases. SIGMOD Conference 1975: 79-91

[Minker 1978]

Jack Minker: Search Strategy and Selection Function for an Inferential Relational System. ACM Trans. Database Syst. 3(1): 1-31(1978)

[Minker and Nicolas 1983]

Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983)

[Missikoff and Scholl 1983]

Michele Missikoff, Michel Scholl: Relational Queries in a Domain Based DBMS. SIGMOD Conference 1983: 219-227

[Montgomery et al. 1983]

Anthony Y. Montgomery, Daryl J. D'Souza, S. B. Lee: The Cost of Relational Algebraic Operations on Skewed Data: Estimates and Experiments. IFIP Congress 1983: 235-241

[Munz 1979]

...

[Munz et al. 1979]

Rudolf Munz, H.-J. Schneider, Frank Steyer: Application of Sub-Predicate Tests in Database Systems. VLDB 1979: 426-435

[Muthuswamy and Kerschberg 1983]

...

[Nau 1983]

...

[Neuhold and Biller 1977]

Erich J. Neuhold, Horst Biller: POREL: A Distributed Data Base on an Inhomogeneous Computer Network. VLDB 1977: 380-395

[Ng 1982]

...

[Niebuhr and Smith 1976]

...

[Niebuhr et al. 1976]

...

[Nievergelt et al. 1984]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)

[Nilsson 1982]

...

[Ott 1977]

...

[Ott and Horlaender 1982]

Nikolaus Ott, Klaus K. Horländer: Removing redundant join operations in queries involving views. Inf. Syst. 10(3): 279-288(1985)

[Ozkarahan 1982]

Esen A. Ozkarahan, Abdullah Uz Tansel, Kenneth C. Smith: Database Machine/Computer Based Distributed Databases. DDB 1982: 61-80

[Ozsoyoglu and Ozsoyoglu 1980]

Z. Meral Özsoyoglu, Gultekin Özsoyoglu: An Extension of Relational Algebra for Summary Tables. SSDBM 1983: 202-211

[Ozsoyoglu and Yu 1980]

...

[Paige 1982]

Robert Paige: Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. Advances in Data Base Theory 1982: 171-209

[Palermo 1972]

...

[Parsaye 1983]

Kamran Parsaye: Database Management, Knowledge Base Management, and Expert System Development in PROLOG. Databases for Business and Office Applications 1983: 159-178

[Pecherer 1975]

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

[Pecherer 1976]

Robert M. Pecherer: Efficient Exploration of Product Spaces. SIGMOD Conference 1976: 169-177

[Pirotte 1979]

Alain Pirotte: Fundamental and Secondary Issues in the Design of Non-Procedural Relational Languages. VLDB 1979: 239-250

[Putkonen 1979]

Anne Putkonen: On the selection of the access path in inverted database organization. Inf. Syst. 4(1): 219-225(1979)

[Reimer 1983]

Manuel Reimer: Solving the Phantom Problem by Predicative Optimistic Concurrency Control. VLDB 1983: 81-88

[Reiter 1978]

Raymond Reiter: Deductive Question-Answering on Relational Data Bases. Logic and Data Bases 1977: 149-177

[Richard 1981]

Philippe Richard: Evaluation of the Size of a Query Expressed in Relational Algebra. SIGMOD Conference 1981: 155-163

[Rosenkrantz and Hunt 1980]

Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72

[Rosenthal and Reiner 1982]

Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255

[Rosenthal and Reiner 1984]

Arnon Rosenthal, David S. Reiner: Querying Relational Views of Networks. Query Processing in Database Systems 1985: 109-124

[Rothnie 1974]

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

[Rothnie 1975]

...

[Rothnie and Goodman 1977]

James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62

[Roussopoulos 1982a]

Nick Roussopoulos: View Indexing in Relational Databases. ACM Trans. Database Syst. 7(2): 258-290(1982)

[Roussopoulos 1982b]

Nick Roussopoulos: The Logical Access Path Schema of a Database. IEEE Trans. Software Eng. 8(6): 563-573(1982)

[Sacco and Schkolnick 1982]

Giovanni Maria Sacco, Mario Schkolnick: A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model. VLDB 1982: 257-262

[Sacco and Yao 1982]

Giovanni Maria Sacco, S. Bing Yao: Query Optimization in Distributed Data Base Systems. Advances in Computers 21: 225-273(1982)

[Sagalowicz 1977]

Daniel Sagalowicz: IDA: An Intelligent Data Access Program. VLDB 1977: 293-302

[Sagiv 1981]

...

[Sagiv 1983]

Yehoshua Sagiv: Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions. SIAM J. Comput. 12(2): 316-328(1983)

[Sagiv and Yannakakis 1980]

Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980)

[Salton and Wong 1978]

Gerard Salton, A. Wong: Generation and Search of Clustered Files. ACM Trans. Database Syst. 3(4): 321-346(1978)

[Schek and Pistor 1982]

Hans-Jörg Schek, Peter Pistor: Data Structures for an Integrated Data Base Management and Information Retrieval System. VLDB 1982: 197-207

[Schenk and Pinkert 1977]

Kathryn L. Schenk, James R. Pinkert: An Algorithm for Servicing Multi-Relational Queries. SIGMOD Conference 1977: 10-20

[Schkolnick 1975]

Mario Schkolnick: The Optimal Selection of Secondary Indices for Files. Inf. Syst. 1(4): 141-146(1975)

[Schkolnick 1982]

Mario Schkolnick: Physical Database Design Techniques. Data Base Design Techniques II 1979: 229-252

[Schmidt 1977]

Joachim W. Schmidt: Some High Level Language Constructs for Data of Type Relation. ACM Trans. Database Syst. 2(3): 247-261(1977)

[Schmidt 1979]

Joachim W. Schmidt: Parallel Processing of Relations: A Single-Assignment Approach. VLDB 1979: 398-408

[Schmidt 1984]

...

[Selinger and Adiba 1980]

...

[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

[Severance and Carlis 1977]

Dennis G. Severance, John V. Carlis: A Practical Approach to Selecting Record Access Paths. ACM Comput. Surv. 9(4): 259-272(1977)

[Shmueli 1981]

...

[Shneiderman 1977]

Ben Shneiderman: Recuced combined indexes for efficient multiple attribute retrieval. Inf. Syst. 2(4): 149-154(1977)

[Shneiderman and Goodman 1976]

Ben Shneiderman, Victor Goodman: Batched Searching of Sequential and Tree Structured Files. ACM Trans. Database Syst. 1(3): 268-275(1976)

[Shoshani 1982]

Arie Shoshani: Statistical Databases: Characteristics, Problems, and some Solutions. VLDB 1982: 208-222

[Schultz and Zingg 1984]

Roger K. Shultz, Roy J. Zingg: Response Time Analysis of Multiprocessor Computers for Database Support. ACM Trans. Database Syst. 9(1): 100-132(1984)

[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)

[Smith et al. 1981]

...

[Sockut and Goldberg 1979]

Gary H. Sockut, Robert P. Goldberg: Database Reorganization - Principles and Practice. ACM Comput. Surv. 11(4): 371-395(1979)

[Stonebraker 1975]

Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78

[Stonebraker and Neuhold 1977]

Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36

[Stonebraker et al. 1976]

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

[Stroet and Engmann 1979]

J. W. M. Stroet, R. Engmann: Manipulation of expression in a relational algebra. Inf. Syst. 4(1): 195-203(1979)

[Su 1979]

...

[Su and Lipovski 1975]

Stanley Y. W. Su, G. Jack Lipovski: CASSM: A Cellular System for Very Large Data Bases. VLDB 1975: 456-472

[Su and Mikkilineni 1982]

Stanley Y. W. Su, Krishna P. Mikkilineni: Parallel Algorithms and Their Implementation in MICRONET. VLDB 1982: 310-324

[Tanenbaum 1981]

Andrew S. Tanenbaum: Computer Networks. Prentice-Hall 1981, ISBN 0-13-165183-8

[Teorey and Fry 1982]

Toby J. Teorey, James P. Fry: Design of Database Structures. Prentice-Hall 1982

[Todd 1974]

...

[Tsichritzis 1976]

Dennis Tsichritzis: LSL: A Link and Selector Language. SIGMOD Conference 1976: 123-133

[Ullman 1982]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6

[Valduriez 1982]

Patrick Valduriez: Semi-Join Algorithms for Multiprocessor Systems. SIGMOD Conference 1982: 225-233

[Valduriez and Gardarin 1984]

Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984)

[van de Riet et al. 1981]

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)

[Vassiliou and Jarke 1984]

...

[Vassiliou and Lochovsky 1980]

...

[Vassiliou et al. 1984]

...

[Verhofstad 1978]

Joost Verhofstad: Recovery Techniques for Database Systems. ACM Comput. Surv. 10(2): 167-195(1978)

[Walker 1980]

Adrian Walker: On Retrieval from a Small Version of a Large Data Base. VLDB 1980: 47-54

[Warren 1981]

David H. D. Warren: Efficient Processing of Interactive Relational Data Base Queries expressed in Logic. VLDB 1981: 272-281

[Welch and Graham 1976]

James W. Welch, J. Wesley Graham: Retrieval Using Ordered Lists in Inverted and Multilist Files. SIGMOD Conference 1976: 21-29

[Whang et al. 1983]

Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Estimating Block Accesses in Database Organizations: A Closed Noniterative Formula. Commun. ACM 26(11): 940-944(1983)

[Williams etal. 1982]

R. Williams, Dean Daniels, Laura M. Haas, George Lapis, Bruce G. Lindsay, Pui Ng, Ron Obermarck, Patricia G. Selinger, Adrian Walker, Paul F. Wilms, Robert A. Yost: R*: An Overview of the Architecture. JCDKB 1982: 1-27

[Wong 1977]

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

[Wong 1983]

Eugene Wong: Dynamic Rematerialization: Processing Distributed Queries Using Redundant Data. IEEE Trans. Software Eng. 9(3): 228-232(1983)

[Wong and Katz 1983]

Eugene Wong, Randy H. Katz: Distributing A Database for Parallelism. SIGMOD Conference 1983: 23-29

[Wong and Youssefi 1976]

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

[Xu 1983]

...

[Yang 1977]

Chung-Shu Yang: Avoiding redundant record accesses in unsorted multilist file organizations. Inf. Syst. 2(4): 155-158(1977)

[Yao 1977a]

S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977)

[Yao 1977b]

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

[Yao 1979]

S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979)

[Yao DeJong 1978]

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

[Youssefi and Wong 1979]

Karel Youssefi, Eugene Wong: Query Processing in a Relational Database Management System. VLDB 1979: 409-417

[Yu and Chang 1983]

Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39

[Yu and Ozsoyoglu 1979]

...

[Yu et al. 1978]

Clement T. Yu, W. S. Luk, M. K. Siu: On the Estimation of the Number of Desired Records with Respect to a Given Query. ACM Trans. Database Syst. 3(1): 41-56(1978)

[Zaniolo 1979]

Carlo Zaniolo: Design of Relational Views over Network Schemas. SIGMOD Conference 1979: 179-190