Article Source

Title: Readings in Database Systems
Authors: Michael Stonebraker and Joseph M. Hellerstein

Readings in Database Systems (4th Edition)

Understanding the history of a topic is very helpful for developing a useful conceptualization of future evolution and a thorough knowledge of present challenges. Database system research has long yielded valuable insights, but many findings are primarily locatabale within complex academic papers in obscure publications. This useful collection of papers published by The MIT Press presents some old documents and some newer ones.

Many innovations have yet to be made in teh field of database system design, but there are many complexities associated with database management systems, and sometimes researches waste time by working through studies that have already been completed and throughly documented. In order to be able to pave the way for the future of databases, it is necessary to h ave an understanding of what has happened to this point and what current challenges need new solutions.

The preface to the anthology describes the editors’ objective:

This book is intended to provide software technolgoists—both professionals and students—with a grounding in database research past and present, and a technical context for understanding new innovations. It is also designed to be a reference to anyone already active in database systems. This set of readings represents what we perceive to be the most important issues in the database area; the core mateiral for any DBMS [database management system] professional to study.

(page ix)

These papers are present in the fourth edition:

Data Models and DBMS Architecture

What Goes Around Comes Around by Michael Stonebraker and Joseph M. Hellerstein
Anatomy of a Database System by Joseph M. Hellerstein and Michael Stonebraker

Query Processing

Access Path Selection in a Relational Database Management System by P. Griffiths Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, and T.G. Price
Join Processing in Database Systems with Large Main Memories by Leonard D. Shapiro
Parallel Database Systems: The Future of High Performance Database Systems by David DeWitt and Jim Gray
Encapsulation of Parallelism in the Volcano Query Processing System by Goetz Graefe
AlphaSort: A RISC Machine Sort by Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, and Dave Lomet
R* Optimizer Validation and Performance Evaluation for Distributed Systems by Lothar F. Mackert and Guy M. Lohman
Mariposa: A Wide-Area Distributed Database System by Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah, Jeff Sidell, Carl Staelin, and Andrew Yu

Data Storage and Access Methods

The R*-tree: An Efficient and Robust Access Method for Points and Rectangles by Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger
Operating System Support for Database Management by Michael Stonebraker
The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb by Jim Gray and Goetz Graefe
A Case for Redundant Arrays of Inexpensive Disks (RAID) by David A. Patterson, Garth Gibson, and Randy H. Katz

Transaction Management

Granularity of Locks and Degrees of Consistency in a Shared Data Base by Jim N. Gray, Raymond A. Lorie, Gianfranco R. Putzolu, and Irving L. Traiger
On Optimistic Methods for Concurrency Control by H. T. Kung and John T. Robinson
Concurrency Control Performance Modeling: Alternatives and Implications by Rakesh Agrawal, Michael J. Carey, and Miron Livny
Efficient Locking for Concurrent Operations on B-Trees by Philip L. Lehman and S. Bing Yao
ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging by C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz
Transaction Management in the R* Distributed Database Management System by C. Mohan, Bruce Lindsay, and R. Obermack
The Dangers of Replication and a Solution by Jim Gray, Pat Helland, Patrick O’Neil, and Dennis Shasha

Extensibility

Inclusion of New Types in Relational Data Base Systems by Michael Stonebraker
Generalized Search Trees for Database Systems by Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer
Grammar-like Functional Rules for Representing Query Optimization Alternatives by Guy M. Lohman

Database Evolution

AutoAdmin “What-if” Index Analysis Utility by Surajit Chaudhuri and Vivek Narasayya
Applying Model Management to Classical Meta Data Problems by Philip A. Bernstein
Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates by C. Mohan and Inderpal Narang

Data Warehousing

An Overview of Data Warehousing and OLAP Technology by Surajit Chaudhuri and Umeshwar Dayal
Improved Query Performance with Variant Indexes by Patrick O’Neil and Dallan Quass
DataCube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals by Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, and Murali Venkatrao
An Array-Based Algorithm for Simultaneous Multidimensional Aggregates by Yihong Zhao, Prasad M. Despande, and Jeffrey F. Naughton
Deriving Production Rules for Incremental View Maintenance by Stefano Ceri and Jennifer Widom
Informix under CONTROL: Online Query Processing by Joseph M. Hellerstein, Ron Avnur, and Vijayshankar Raman
DynaMat: A Dynamic View Management System for Data Warehouses by Yannis Kotidis and Nick Roussopoulos

Data Mining

BIRCH: An Efficient Data Clustering Method for Very Large Databases by Tian Zhang, Raghu Ramakrishnan, and Miron Livny
SPRINT: A Scalable Parallel Classifier for Data Mining by John Shafer, Rakesh Agrawal, and Manish Mehta
Fast Algorithms for Mining Association Rules by Rakesh Agrawal and Ramakrishnan Srikant
Efficient Evaluation of Queries with Mining Predicates by Surajit Chaudhuri, Vivek Narasayya, and Sunita Sarawagi

Web Services and Data Bases

Combining Systems and Databases: A Search Engine Retrospective by Eric A. Brewer
The Anatomy of a Large-Scale Hypertextual Web Search Engine by Sergey Brin and Lawrence Page
The BINGO! System for Information Portal Generation and Expert Web Search by Sergej Sizov, Michael Biwer, Jens Graupmann, Stefan Siersdorfer, Martin Theobald, Gerhard Weikum, and Patrick Zimmer
Data Management in Application Servers by Dean Jacobs
Querying Semi-Structured Data by Serge Abiteboul
DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases by Roy GOldman and Jennifer Widom
NiagaraCQ: A Scalable Continuous Query System for the Internet Databases by Jianjun Chen, David J. DeWitt, Feng Tian, and Yuan Wang

Stream-Based Data Management

Scalable Trigger Processing by Eric N. Hanson, Chris Carnes, Lan Huang, Mohan Konyala, Lloyd Noronha, Sashi Parthasarathy, J. B. Park, and Albert Vernon
The Design and Implementation of a Sequence Database System by Praveen Seshadri, Miron Livny, and Raghu Ramakrishnan
Eddies: Continuously Adaptive Query Processing by Ron Avnur and Joseph M. Hellerstein
Retrospective on Aurora by Hari Balakrishnan, Magdalena Balazinska, Don Carney, Ugur Çetintemel, Mitch Cherniack, Chrstian Convey, Eddie Galvez, Jon Salz, Michael Stonebraker, Nesime Tatbul, Richard Tibbetts, and Stan Zdonik

Links

Query Processing

Patricia G. Selinger Morton M. Astrahan Donald D. Chamberlin Raymond A. Lorie Thomas G. Price. Access Path Selection in a Relational Database Management System.. Proc. SIGMOD Conference, 1979, 23-34.

Leonard D. Shapiro. Join Processing in Database Systems with Large Main Memories.. ACM Trans. Database Syst., 11(3), 1986, 239-264.

David J. DeWitt Jim Gray. Parallel Database Systems: The Future of High Performance Database Systems.. Commun. ACM, 35(6), 1992, 85-98.

Goetz Graefe. Encapsulation of Parallelism in the Volcano Query Processing System.. Proc. SIGMOD Conference, 1990, 102-111.

Chris Nyberg Tom Barclay Zarka Cvetanovic Jim Gray David B. Lomet. AlphaSort: A Cache-Sensitive Parallel External Sort. VLDB J., 4(4), 1995, 603-627.

Lothar F. Mackert Guy M. Lohman. R* Optimizer Validation and Performance Evaluation for Distributed Queries.. Proc. VLDB, 1986, 149-159.

Michael Stonebraker Paul M. Aoki Witold Litwin Avi Pfeffer Adam Sah Jeff Sidell Carl Staelin Andrew Yu. Mariposa: A Wide-Area Distributed Database System. VLDB J., 5(1), 1996, 48-63.

Data Storage and Access Methods

Norbert Beckmann Hans-Peter Kriegel Ralf Schneider Bernhard Seeger. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.. Proc. SIGMOD Conference, 1990, 322-331.

Michael Stonebraker. Operating System Support for Database Management.. Commun. ACM, 24(7), 1981, 412-418.

Jim Gray Goetz Graefe. The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb.. SIGMOD Record, 26(4), 1997, 63-68.

David A. Patterson Garth A. Gibson Randy H. Katz. A Case for Redundant Arrays of Inexpensive Disks (RAID).. Proc. SIGMOD Conference, 1988, 109-116.

Transaction Management

Jim Gray Raymond A. Lorie Gianfranco R. Putzolu Irving L. Traiger. Granularity of Locks and Degrees of Consistency in a Shared Data Base.. IBM, September, 1975.

H. T. Kung John T. Robinson. On Optimistic Methods for Concurrency Control.. Proc. VLDB, 1979, 351.

Rakesh Agrawal Michael J. Carey Miron Livny. Concurrency Control Performance Modeling: Alternatives and Implications.. ACM Trans. Database Syst., 12(4), 1987, 609-654.

Philip L. Lehman S. Bing Yao. Efficient Locking for Concurrent Operations on B-Trees.. ACM Trans. Database Syst., 6(4), 1981, 650-670.

C. Mohan Donald J. Haderle Bruce G. Lindsay Hamid Pirahesh Peter M. Schwarz. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging.. ACM Trans. Database Syst., 17(1), 1992, 94-162.

C. Mohan Bruce G. Lindsay Ron Obermarck. Transaction Management in the R* Distributed Database Management System.. ACM Trans. Database Syst., 11(4), 1986, 378-396.

Jim Gray Pat Helland Patrick E. O’Neil Dennis Shasha. The Dangers of Replication and a Solution.. Proc. SIGMOD Conference, 1996, 173-182.

Extensible Systems

Michael Stonebraker. Inclusion of New Types in Relational Data Base Systems.. Proc. ICDE, 1986, 262-269.

Joseph M. Hellerstein Jeffrey F. Naughton Avi Pfeffer. Generalized Search Trees for Database Systems.. Proc. VLDB, 1995, 562-573.

Guy M. Lohman. Grammar-like Functional Rules for Representing Query Optimization Alternatives.. Proc. SIGMOD Conference, 1988, 18-27.

Database Evolution

Surajit Chaudhuri Vivek R. Narasayya. AutoAdmin ‘What-if’ Index Analysis Utility.. Proc. SIGMOD Conference, 1998, 367-378.

Philip A. Bernstein. Applying Model Management to Classical Meta Data Problems.. Proc. CIDR, 2003.

C. Mohan Inderpal Narang. Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates.. Proc. SIGMOD Conference, 1992, 361-370.

Data Warehousing

Surajit Chaudhuri Umeshwar Dayal. An Overview of Data Warehousing and OLAP Technology.. SIGMOD Record, 26(1), 1997, 65-74.

Patrick E. O’Neil Dallan Quass. Improved Query Performance with Variant Indexes.. Proc. SIGMOD Conference, 1997, 38-49.

Jim Gray Surajit Chaudhuri Adam Bosworth Andrew Layman Don Reichart Murali Venkatrao Frank Pellow Hamid Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals.. Data Min. Knowl. Discov., 1(1), 1997, 29-53.

Yihong Zhao Prasad Deshpande Jeffrey F. Naughton. An Array-Based Algorithm for Simultaneous Multidimensional Aggregates.. Proc. SIGMOD Conference, 1997, 159-170.

Stefano Ceri Jennifer Widom. Deriving Production Rules for Constraint Maintainance.. Proc. VLDB, 1990, 566-577.

Joseph M. Hellerstein Ron Avnur Vijayshankar Raman. Informix under CONTROL: Online Query Processing.. Data Min. Knowl. Discov., 4(4), 2000, 281-314.

Yannis Kotidis Nick Roussopoulos. DynaMat: A Dynamic View Management System for Data Warehouses.. Proc. SIGMOD Conference, 1999, 371-382.

Data Mining

Tian Zhang Raghu Ramakrishnan Miron Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases.. Proc. SIGMOD Conference, 1996, 103-114.

John C. Shafer Rakesh Agrawal Manish Mehta. SPRINT: A Scalable Parallel Classifier for Data Mining. Proc. VLDB, 1996, 544-555.

Rakesh Agrawal Ramakrishnan Srikant. Fast Algorithms for Mining Association Rules in Large Databases.. Proc. VLDB, 1994, 487-499.

Surajit Chaudhuri Vivek R. Narasayya Sunita Sarawagi. Efficient Evaluation of Queries with Mining Predicates.. Proc. ICDE, 2002, 529-.

Web Services and Databases

Eric A. Brewer. Combining Systems and Databases: A Search Engine Retrospective.

Sergey Brin Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine.. Computer Networks, 30(1-7), 1998, 107-117.

Sergej Sizov Martin Theobald Stefan Siersdorfer Gerhard Weikum Jens Graupmann Michael Biwer Patrick Zimmer. The BINGO! System for Information Portal Generation and Expert Web Search.. Proc. CIDR, 2003.

Dean Jacobs. Data Management in Application Servers.

Serge Abiteboul. Querying Semi-Structured Data.. Proc. ICDT, 1997, 1-18.

Roy Goldman Jennifer Widom. DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases.. Proc. VLDB, 1997, 436-445.

Jianjun Chen David J. DeWitt Feng Tian Yuan Wang. NiagaraCQ: A Scalable Continuous Query System for Internet Databases.. Proc. SIGMOD Conference, 2000, 379-390.

Stream-Based Data Management

Eric N. Hanson Chris Carnes Lan Huang Mohan Konyala Lloyd Noronha Sashi Parthasarathy J. B. Park Albert Vernon. Scalable Trigger Processing.. Proc. ICDE, 1999, 266-275.

Praveen Seshadri Miron Livny Raghu Ramakrishnan. The Design and Implementation of a Sequence Database System.. Proc. VLDB, 1996, 99-110.

Ron Avnur Joseph M. Hellerstein. Eddies: Continuously Adaptive Query Processing. Proc. SIGMOD Conference, 2000, 261-272.

Donald Carney Ugur Çetintemel Mitch Cherniack Christian Convey Sangdon Lee Greg Seidman Michael Stonebraker Nesime Tatbul Stanley B. Zdonik. Monitoring Streams - A New Class of Data Management Applications.. Proc. VLDB, 2002, 215-226.

Readings in Database Systems, Third Edition

CHAPTER 1 The Roots

A Relational Model of Data for Large Shared Data Banks, CACM 13(6) 1970: Edgar F. Codd
System R: Relational Approach to Database Management, TODS 1(2) 1976: 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, and Vera Watson
The Design and Implementation of INGRES, TODS 1(3) 1976: Michael Stonebraker, Eugene Wong, Peter Kreps, and Gerald Held
A History and Evaluation of System R, CACM 24(10) 1981: Donald D. Chamberlin, Morton M. Astrahan, Mike W. Blasgen, Jim Gray, W. Frank King III, Bruce G. Lindsay, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Gianfranco R. Putzolu, Patricia G. Selinger, Mario Schkolnick, Donald R. Slutz, Irving L. Traiger, Bradford W. Wade, and Robert A. Yost
Retrospection on a Database System, TODS 5(2) 1980: Michael Stonebraker

CHAPTER 2 Relational Implementation Techniques

Operating System Support for Database Management, Database Engineering Bulletin 9(3) 1986: Michael Stonebraker
R-Trees: A Dynamic Index Structure for Spacial Searching, SIGMOD 1984: Antonin Guttman
Generalized Search Trees for Database Systems, VLDB 1995: Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer
An Evaluation of Buffer Management Strategies for Relational Database Systems, Algorithmica 1(3) 1986: Hong-Tai Chou and David J. DeWitt
Join Processing in Database Systems with Large Main Memories, TODS 11(3) 1986: Leonard D. Shapiro
Access Path Selection in a Relational Database Management System, SIGMOD 1979: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price
Query Rewrite Optimization Rules in IBM DB2 Universal Database: T. Y. C. Leung, H. Pirahesh, P. Seshadri, and J. Hellerstein

CHAPTER 3 Transaction Management

Granularity of Locks and Degrees of Consistency in a Shared Data Base, IFIP Working Conference on Modelling in Data Base Management Systems 1976: Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, and Irving L. Traiger
On Optimistic Methods for Concurrency Control, TODS 6(2) 1981: H. T. Kung and John T. Robinson
Concurrency Control Performance Modeling: Alternatives and Implications, TODS 12(4) 1987: Rakesh Agrawal, Michael J. Carey, and Miron Livny
Efficient Locking for Concurrent Operations on B-Trees, TODS 6(4) 1981: Philip L. Lehman and S. Bing Yao
Principles of Transaction-Oriented Database Recovery, ACM Computing Surveys 15(4) 1983: Theo Härder, Andreas Reuter
ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging, TODS 17(1) 1992: C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, and Peter M. Schwarz The Design of a POSTGRES Storage System, VLDB 1987; Michael Stonebraker
The ConTract Model, Database Transaction Models for Advanced Applications 1992: Helmut Wachter and Andreas Reuter

CHAPTER 4 Distributed Database System

R*: An Overview of the Archtecture, JCDKB 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, and Robert A. Yost
R* Optimizer Validation and Performance Evaluation for Distributed Queries, VLDB 1986: Lothar F. Mackert and Guy M. Lohman
Transaction Management in the R* Distributed Database Management System, TODS 11(4) 1986: C. Mohan, Bruce G. Lindsay, and Ron Obermarck
The Dangers of Replication and a Solution, SIGMOD 1996: Jim Gray, Pat Helland, Patrick E. O’Neil, and Dennis Shasha
Mariposa: A Wide-Area Distributed Database System, VLDB Journal 5(1) 1996: Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah, Jeff Sidell, Carl Staelin, and Andrew Yu

CHAPTER 5 Parallel Database System

Parallel Database Systems: The Future of High Performance Database Systems, CACM 35(6) 1992: David J. DeWitt and Jim Gray
The Gamma Database Machine Project, TKDE 2(1) 1990: David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, and Rick Rasmussen
AlphaSort: A Cache-Sensitive Parallel External Sort, VLDB Journal 4(4) 1995: Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, and David B. Lomet
Coloring Away Communication in Parallel Query Optimization, VLDB 1995: Waqar Hasan and Rajeev Motwani

CHAPTER 6 Objects in Databases

The ObjectStore Database System, CACM 34(10) 1991: Charles Lamb, Gordon Landis, Jack A. Orenstein, and Danel Weinreb
QuickStore: A High Performance Mapped Object Store, SIGMOD 1994: Seth J. White and David J. DeWitt
Client-Server Caching Revisited, IWDOM 1992 (SIGMOD 1991): Michael J. Franklin and Michael J. Carey
The Database Language GEM, SIGMOD 1983: Carlo Zaniolo
Inclusion of New Types in Relational Data Base System, ICDE 1986: Michael Stonebraker
The POSTGRES Next-Generation Database Management System, CACM 34(10) 1991: Michael Stonebraker and Greg Kemnitz

CHAPTER 7 Data Analysis and Decision Support

Improved Query Performance with Variant Indexes, SIGMOD 1997: Patrick E. O’Neil and Dallan Quass
Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery 1(1) 1997 (ICDE 1996): Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, and Hamid Pirahesh
An Array-Based Algorithm for Simultaneous Multidimensional Aggregates, SIGMOD 1997: Yihong Zhao, Prasad Deshpande, and Jeffrey F. Naughton
Fast Algorithms for Mining Association Rules in Large Databases, VLDB 1994: Rakesh Agrawal and Ramakrishnan Srikant
Online Aggregation, SIGMOD 1997: Joseph M. Hellerstein, Peter J. Haas, and Helen J. Wang

CHAPTER 8 Benchmarking Database Systems

A Measure of Transaction Processing Power: Anon et al. The OO7 Benchmark, SIGMOD 1993; Michael J. Carey, David J. DeWitt, and Jeffrey F. Naughton
The Sequoia 2000 Storage Benchmark, SIGMOD 1993: Michael Stonebraker, James Frew, Kenn Gardels, and Jeff Meredith

CHAPTER 9 Vision Statements

Database Metatheory: Asking and Big Queries, PODS 1995: Christos H. Papadimitriou
Database Systems: Achievements and Opportunities, CACM 34(10) 1991: Abraham Silberschatz, Michael Stonebraker, and Jeffrey D. Ullman
Strategic Directions in Database Systems - Breaking Out of the Box, ACM Computing Surveys 28(4) 1996: Abraham Silberschatz and Stanley B. Zdonik

Stop Thinking, Just Do!