Bibliography of Database Systems Papers

Note: the papers are available through or through York library e-resources (IEEE Xplore or ACM Digital Library)

  1. Introduction
  • Donald D. Chamberlin, A. M. Gilbert, Robert A. Yost: A History of System R and SQL/Data System (Invited Paper) VLDB 1981: 456-464
  • 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)
  • Peter Gassner, Guy M. Lohman, K. Bernhard Schiefer, Yun Wang: Query Optimization in the IBM DB2 Family. IEEE Data Eng. Bull. 16(4): 4-18 (1993)
  • Michael J. Carey, David J. DeWitt, Daniel Frank, Goetz Graefe, Joel E. Richardson, Eugene J. Shekita, M. Muralikrishna: The Architecture of the EXODUS Extensible DBMS. On Object-Oriented DatabaseSystem 1991: 231-256
  • Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218
  • Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
  • Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
  • Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172
  • 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
  • S. Bing Yao, D. DeJong: Evaluation of Database Access Paths. SIGMOD Conference 1978: 66-77
  1. Rewrite Query Optimization
  1. General
  • M. Muralikrishna, David J. DeWitt: Optimization of Multiple-Relation Multiple-Disjunct Queries. PODS 1988: 263-275
  • Examples from Starburst
  • Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48
  1. Nested queries
  • Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469 (1982) (to be covered in class)
  • Werner Kießling: On Semantic Reefs and Efficient Processing of Correlation Queries with Aggregates. VLDB 1985: 241-250 (to be covered in class)
  • Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33
  • Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208
  • M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102
  • Ravindra Guravannavar, H. S. Ramanujam, S. Sudarshan: Optimizing Nested Queries with Parameter Sort Orders. 481-492 VLDB 2005
  1. Semantic query opt.
  • Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517
  • Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207 (1990)
  • G. N. Paulley, Per-Åke Larson: Exploiting Uniqueness in Query Optimization. ICDE 1994: 68-79
  • Qi Cheng, Jarek Gryz, Fred Koo, T. Y. Cliff Leung, Linqi Liu, Xiaoyan Qian, K. Bernhard Schiefer: Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database. VLDB 1999: 687-698
  • Gang Luo: Efficient Detection of Empty-Result Queries. 1015-1025 VLDB 2006
  1. Recursive queries and magic sets
  • François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-16
  • Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
  • Inderpal Singh Mumick, Hamid Pirahesh: Implementation of Magic-sets in a Relational Database System. SIGMOD Conference 1994: 103-114
  • Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446
  • Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-283
  • Carlos Ordonez: Optimizing recursive queries in SQL. 834-839 Sigmod 2005
  1. Rewrites using materialized views

TBA

  1. Plan Optimization
  2. General
  • Yannis E. Ioannidis, Stavros Christodoulakis: On the Propagation of Errors in the Size of Join Results. SIGMOD Conference 1991: 268-277
  • Kristin P. Bennett, Michael C. Ferris, Yannis E. Ioannidis: A Genetic Algorithm for Database Query Optimization. ICGA 1991: 400-407
  • Cardinality estimation
  1. General
  • Jeffrey F. Naughton, S. Seshadri: On Estimating the Size of Projections. ICDT 1990: 499-513
  • Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Arun N. Swami: Fixed-Precision Estimation of Join Selectivity. PODS 1993: 190-201
  • Peter J. Haas, Jeffrey F. Naughton, Arun N. Swami: On the Relative Cost of Sampling for Join Selectivity Estimation. PODS 1994: 14-24
  • Yannis E. Ioannidis, Stavros Christodoulakis: On the Propagation of Errors in the Size of Join Results. SIGMOD Conference 1991: 268-277
  • Viswanath Poosala, Yannis E. Ioannidis: Selectivity Estimation Without the Attribute Value Independence Assumption. VLDB 1997: 486-495
  • Ihab F. Ilyas, Jun Rao, Guy M. Lohman, Dengfeng Gao, Eileen Tien Lin: Estimating Compilation Time of a Query Optimizer. SIGMOD Conference 2003: 373-384
  • Ashraf Aboulnaga, Peter J. Haas, Sam Lightstone, Guy M. Lohman, Volker Markl, Ivan Popivanov, Vijayshankar Raman: Automated Statistics Collection in DB2 UDB. VLDB 2004: 1146-1157
  • Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276
  • Silvio Salza, Mario Terranova: Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence. SIGMOD Conference 1989: 8-14
  • Philippe Richard: Evaluation of the Size of a Query Expressed in Relational Algebra. SIGMOD Conference 1981: 155-163
  • Volker Markl, Nimrod Megiddo, Marcel Kutsch, Tam Minh Tran, Peter J. Haas, Utkarsh Srivastava: Consistently Estimating the Selectivity of Conjuncts of Predicates. 373-384 VLDB 2005
  1. Sampling
  • Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider: Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990: 1-11
  • Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46
  • Peter J. Haas, Jeffrey F. Naughton, S. Seshadri, Lynne Stokes: Sampling-Based Estimation of the Number of Distinct Values of an Attribute. VLDB 1995: 311-322
  • Per-Åke Larson, Wolfgang Lehner, Jingren Zhou, Peter Zabback:
    Cardinality estimation using sample views with quality assurance. 175-186 Sigmod 2007
  • Cristian Estan, Jeffrey F. Naughton: End-biased Samples for Join Cardinality Estimation. 20: ICDE 2006
  1. Histograms
  • Yannis E. Ioannidis, Stavros Christodoulakis: Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results. ACM Trans. Database Syst. 18(4): 709-748 (1993)
  • Yannis E. Ioannidis: Universality of Serial Histograms. VLDB 1993: 256-267
  • Yannis E. Ioannidis, Viswanath Poosala: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conference 1995: 233-244
  • Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, Eugene J. Shekita: Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conference 1996: 294-305
  • Yannis E. Ioannidis, Viswanath Poosala: Histogram-Based Approximation of Set-Valued Query-Answers. VLDB 1999: 174-185
  • Yannis E. Ioannidis: The History of Histograms (abridged). VLDB 2003: 19-30
  1. Optimization of individual operators
  2. Join
  • Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17
  • Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376
  • Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325
  • Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321
  • Yannis E. Ioannidis, Younkyung Cha Kang: Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991: 168-177
  • Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: The Complexity of Transformation-Based Join Enumeration. VLDB 1997: 306-315
  • Bennet Vance, David Maier: Rapid Bushy Join-order Optimization with Cartesian Products. SIGMOD Conference 1996: 35-46
  • Outer join
  • César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358
  • César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73 (1997)
  • Jun Rao, Bruce G. Lindsay, Guy M. Lohman, Hamid Pirahesh, David E. Simmen: Using EELs, a Practical Approach to Outerjoin and Antijoin Reordering. ICDE 2001: 585-594
  • Jun Rao, Hamid Pirahesh, Calisto Zuzarte: Canonical Abstraction for Outerjoin Optimization. SIGMOD Conference 2004: 671-682
  • Sort and Group by
  • Thomas Neumann, Guido Moerkotte: A Combined Framework for Grouping and Order Optimization. VLDB 2004: 960-971
  • Thomas Neumann, Guido Moerkotte: An Efficient Framework for Order Optimization. ICDE 2004: 461-472
  • Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366
  • Xiaoyu Wang, Mitch Cherniack: Avoiding Ordering and Grouping In Query Processing. VLDB 2003: 826-837
  • David E. Simmen, Eugene J. Shekita, Timothy Malkemus: Fundamental Techniques for Order Optimization. SIGMOD Conference 1996: 57-67
  • Weipeng P. Yan, Per-Åke Larson: Performing Group-By before Join. ICDE 1994: 89-100
  • Functions and predicates
  • Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107
  • Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates VLDB 1996: 87-98
  • Surajit Chaudhuri, Kyuseok Shim: Query Optimization in the Presence of Foreign Functions. VLDB 1993: 529-542
  • Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335
  • Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276
  • Iosif Lazaridis, Sharad Mehrotra: Optimization of multi-version expensive predicates. 797-808 Sigmod 2007
  1. Parametric and dynamic optimization paradigms
  • Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366
  • Gennady Antoshenkov: Dynamic Query Optimization in Rdb/VMS. ICDE 1993: 538-547
  • Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB 1992: 103-114
  • Richard L. Cole, Goetz Graefe: Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994: 150-160
  • Amol Deshpande, Joseph M. Hellerstein: Lifting the Burden of History from Adaptive Query Processing. VLDB 2004: 948-959
  • Gail Mitchell, Umeshwar Dayal, Stanley B. Zdonik: Control of an Extensible Query Optimizer: A Planning-Based Approach. VLDB 1993: 517-528
  • Hongjun Lu, Kian-Lee Tan, Son Dao: The Fittest Survives: An Adaptive Approach to Query Optimization. VLDB 1995: 251-262
  • Michael Stillger, Guy M. Lohman, Volker Markl, Mokhtar Kandil: LEO - DB2's LEarning Optimizer. VLDB 2001: 19-28
  • Volker Markl, Vijayshankar Raman, David E. Simmen, Guy M. Lohman, Hamid Pirahesh: Robust Query Processing through Progressive Optimization. SIGMOD Conference 2004: 659-670
  • Vijayshankar Raman, Volker Markl, David E. Simmen, Guy M. Lohman, Hamid Pirahesh: Progressive Optimization in Action. VLDB 2004: 1337-1340
  • Shivnath Babu, Pedro Bizarro, David J. DeWitt:
    Proactive Re-optimization. Sigmod 2005: 107-118
  • Quanzhong Li, Minglong Shao, Volker Markl, Kevin S. Beyer, Latha S. Colby, Guy M. Lohman: Adaptively Reordering Joins during Query Execution. 26-35: ICDE 2007
  1. Future
  • Brian Babcock, Surajit Chaudhuri: Towards a Robust Query Optimizer: A Principled and Practical Approach. SIGMOD Conference 2005