Stop Thinking, Just Do!

Sung-Soo Kim's Blog

Readings in Database Systems

tagsTags

11 August 2014


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

comments powered by Disqus