데이터베이스 시스템의 주제별 기초 논문들

데이터베이스 시스템 이라는 큰 주제 아래 각 세부 주제에 대한 기초 논문 목록 들이다. 한참 학교에서 공부하던 시절에 정리하고 틈틈히 업데이트 했던 것 같다. 추후에 data processing이나 column store에 대한 논문들도 공유하도록 하겠다.

데이터베이스 분야는 일반적으로 순수한 알고리즘이나 자료구조 부터 다양한 응용 문제나 이론까지 아주 광범히 하다. 말 자체는 ‘데이터베이스’라서 약간은 고리타분해 보이기도 하지만 데이터에 대해 일반화 가능한 모든 연구라고 봐도 무방할 만큼 해당 학계에서 다양한 연구를 다룬다. 최근 큰 인기를 얻고 있는 하둡이나 분산 데이터처리 역시 데이터베이스 분야에서 활발히 다루어지고 있다. 마이닝의 많은 연구들 또한 이 분야에서 다루어진다. 제목에서 언급한 ‘데이터베이스 시스템’이라고 하면 일반적으로 시스템 구현기술과 이론에 해당되는 내용을 말한다.

개인적으로 해당 분야나 문제를 접할 때 그 문제에 대한 가장 초기 논문들은 꼭 읽어보려고 노력한다. 그 이유는 그 논문들이 그 문제에 대해 가장 깊은 통찰력과 고민들을 많이 담고 있기 때문이며 후대의 논문들 일수록 초기 논문들이 한 고민이나 통찰은 기본적인 전제로 사용되고 문제 풀이 아이디어 위주로 기술되기 때문이다. 그래서 아래 리스트는 각 분야의 초기 논문들 및 전체를 정리하는 논문들 위주로 리스팅이 되어 있다.

주제별로 중요한 논문을 다 담긴 것은 아니다. 주로 내가 관심 있었던 것들 위주이다. 또한 See Also에는 대학들의 좋은 커리큘럼이나 읽어볼만한 주제별 논문에 대해 정리한 리스트의 링크를 담고 있다. 그리고 그 동안은 개인적인 위키에 업데이트를 했었는데 앞으로는 이곳에서 업데이트를 하도록 하겠다.

History

• M. Stonebraker and J. M. Hellerstein, “What Goes Around, Comes Around,” in Readings in Database Systems, 2005, pp. 2-41.
• J. M. Hellerstein and M. Stonebraker, “Anatomy of a Database System,” in Readings in Database Systems, 2005, pp. 42-95.
• Thomas Haigh, Fifty Years of Databases, ACM SIGMOD Blog, 2012.

Architecture

• M. M. ASTRAHAN et al., System R: relational approach to database management, ACM TODS, 1976.
• Donald D. Chamberlin et al., A History and Evaluation of System R, Communications of the ACM, 1981.
• Michael Stonebraker et al., The Design and Implementation of Ingres, ACM TODS, 1976.
• Joseph M. Hellerstein, Michael Stonebraker, and James Hamilton, Architecture of a Database System, Foundations and Trends in Databases, 2007.

Query Processing

• Leonard D. et al., Join processing in database systems with large main memories, ACM TODS, 1986.
• D. J. DeWitt and Jim Gray, Parallel Database Systems: The Future of High Performance Database Processing, CACM 1992.
• Chris Nyberg et al., AlphaSort: a cache-sensitive parallel external sort, VLDB Journal, 1995.
• Goetz Graefe, Encapsulation of Parallelism in the Volcano Query Processing System, ACM SIGMOD, 1990.
• Lothar F. Mackert et al., R* Optimizer Validation and Performance Evaluation for Distributed Queries, VLDB Conf, 1986.

Access Method

• P. Griffiths Selinger et al., Access Path Selection in a Relational Database Management System, ACM SIGMOD, 1979.
• Jim Gray et al., The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb, ACM SIGMOD Record, 1997.

Transaction Management

Logging

• C. Mohan et al., ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-ahead Logging, ACM TODS, 1987.
• C. Mohan, Repeating History Beyond ARIES, VLDB Conf, 1999.
• Russel Sears et al,, Segment-Based Recovery: Write-ahead logging revisited, PVLDB, 2009.
• Philip L. Lehman et al., Efficient Locking for Concurrent Operations on B-Trees, ACM TODS, 1981.

Concurrency Control

• Jim Gray et al., Granularity of Locks and Degrees of Consistency in a Shared Data Base, Readings in database systems, 1976.
• Concurrency Control in Database Systems, ACM Computing Survey, 1981.
• H. T. Kung, On optimistic methods for concurrency control, ACM TODS, 1981.
• Rakesh Agrawal et al., Concurrency Control Performance Modeling: Alternatives and Implications, ACM TODS, 1987.
• C. Mohan et al., Transaction Management in the R* Distributed Database Management System, ACM TODS, 1986.
  • Two Phase Commit

Data Warehouse

• Surajit Chaudhuri and Umeshwar Dayal., An Overview of Data Warehousing and OLAP Technology, ACM SIGMOD Record, 1997.
• Patrick O’Neil and Dallan Quass, Improved Query Performance with Variant Indexes, ACM SIGMOD, 1997.
• Jim Gray et al., Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals, Data Mining and Knowledge Discovery, 1997.
• Yihong Zhao et al., An Array-Based Algorithm for Simultaneous Multidimensional Aggregates, ACM SIGMOD, 1997.
• C. Mohan and Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, ACM SIGMOD, 1992.

See Also

• CS262a: Advanced Topics in Computer Systems, EECS Berkeley
• Michael Stonebraker et al., Readings in Database Systems (Lecture Notes, List of papers)
• Database Tuning, Spring 2007
• CSci 5708 : Architecture and Implementation of Database Management Systems, Spring 2011
• http://www-2.cs.cmu.edu/afs/cs/academic/class/15721-f01/www/readings.html
• CMSC724: Database Management Systems, Spring 2007 (Presentation Material)
• Readings in Databases
• Lecture – Datenbanksysteme II
• Lecture – Datenbanksysteme II (INF 4141)
• CSI 445/660. Topics in Data Management Systems, Albany CSI