Index
Data Models and Languages
Codd, E. F., A Relational Model of Data for Large Shared Data Banks, Communications of the ACM, 1970
J. Ullman. Database and Knowledge Base Systems, vol. I. Chapter 3 (Logic as a Data Model).
Stonebraker, M., Inclusion of New Types In Relational Data Base Systems, Proceedings of the International Conference on Data Engineering, 1986.
Stonebraker M., and Hellerstein J., What Goes Around Comes Around.
Database Theory
S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Available for free from: http: //webdam.inria.fr/Alice/
Conjunctive Queries (Chapters 3,4)
Chapter 6, Sections 6.2 and 6.4
Datalog (Chapter 12, Sections 12.1 - 12.3, Chapter 13, Section 13.1 - 13.3)
T. J. Green, S. Huang, B. T. Loo, W. Zhou, Datalog and Recursive Query Processing, Foundations and Trends in Databases, Vol. 5, 2012.
H. Ngo, C. Re, A. Rudra, Skew Strikes Back: New Developments in the Theory of Join Algorithms, SIGMOD Record, 2013.
Cheney, Chiticariu, Tan, Provenance in Databases: Why, How and Where, Foundations and Trends in Databases, 2009.
C. Dwork, A Firm Foundation for Private Data Analysis, Communications of the ACM, 2011.
DBMS Architecture
Chamberlin, D. D., Astrahan, M. M., Blasgen, M. W., Gray, J. N., King, W. F., Lindsay, B. G., Lorie, R., Mehl, J. W., Price, T. G., Putzolu, F., Selinger, P. G., Schkolnick, M., Slutz, D. R., Traiger, I. L., Wade, B. W. and Yost, R. A. A History and Evaluation of System R, Communications of the ACM 24(10), 1981.
Stonebraker, M., Wong E., Kreps P., and Held G., The Design and Implementation of INGRES, ACM Transactions on Database Systems 1(3), 1976.
Hellerstein J. M., Stonebraker M. and Hamilton, J. R., Architecture of a Database System, Foundations and Trends in Databases 1(2), 2007.
Operating System Issues
Chou, H., and DeWitt, D., An Evaluation of Buffer Management Strategies for Relational Database Systems, Proceedings of the International Conference on Very Large Data Bases (VLDB), 1985.
O’Neil, E. J., O’Neil, P. E., Weikum G., The LRU-K Page Replacement Algorithm For Database Disk Buffering, Proceedings of the ACM-SIGMOD International Conference on Management of Data, 1993.
Stonebraker, M., Operating System Support for Database Management, Communications of the ACM 24(7), 1981.
File Organizations and Access Methods
Comer, D., The Ubiquitous B-Tree, ACM Computing Surveys 11(2), June 1979.
Guttman, A., R-Trees: A Dynamic Index Structure for Spatial Searching, SIGMOD Conference, 1984.
Patrick E. O’Neil, Dallan Quass: Improved Query Performance with Variant Indexes. SIGMOD Conference, 1997: 38-49.
Query Complexity
Optimal implementation of conjunctive queries in relational databases, Chandra, Merlin, STOC 1977
The Complexity of Relational Query Languages, Vardi, STOC 1982
Algorithms for acyclic database schemes, Yannakakis, VLDB 1981.
Size bounds and query plans for relational joins, Atserias, Grohe, Marx, FOCS 2008
Hypertree Decompositions and Tractable Queries, Gottlob, Leone, Scarcello, JCSS 2002
Leapfrog Triejoin: a worst-case optimal join algorithm, Veldhuizen, ICDT 2014
Skew Strikes Back: New Developments in the Theory of Join Algorithms, Ngo, Re, Rudra, SIGMOD RECORD 2013
Query Processing and Optimization
Shapiro, L. D., Join Processing in Database Systems with Large Main Memories, ACM Transactions on Database Systems 11(3), 1986.
Selinger, P., et al., Access Path Selection in a Relational Database Management System, Proceedings of the ACM-SIGMOD International Conference on Management of Data, 1979.
Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170 (1993)
Concurrency Control and Recovery
Bernstein, P.A., Hadzilacos, V., and Goodman, N., Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987; can be freely downloaded from Bernstein’s webpage. (Chapters 1 and 2)
Gray, J., Lorie, R. A., Pulzolu, G. R., Traiger, I. L., Granularity of Locks and Degrees of Consistency in a Shared Data Base, Proceedings of the IFIP Working Conference on Modeling of Data Base Management Systems, 1979.
Kung, H., and Robinson, J., On Optimistic Methods for Concurrency Control, ACM Transactions on Database Systems 6(2), June 1981.
Berenson, H., Bernstein, P. A., Gray, J., Melton, J., O’Neil, E. J., O’Neil, P. E., A Critique of ANSI SQL Isolation Levels, Proceedings of the ACM-SIGMOD International Conference on Management of Data, 1995.
Lehman, P. and Yao, S., Efficient Locking for Concurrent Operations on B-Trees, ACM Transactions on Database Systems, 6(4): 650-670.
Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H., Schwarz, P., ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging, ACM Transactions on Database Systems, 17(1): 94-162.
Distributed and Parallel Data Processing
MapReduce: simplified data processing on large clusters, Dean, Ghemawat, OSDI 2004
MapReduce and parallel DBMSs: friends or foes?, Stonebraker et al., CACM 2010
Optimizing Joins in a Map-Reduce Environment, Afrati, Ullman, EDBT 2010
A Guide to Formal Analysis of Join Processing in Massively Parallel Systems, Koutris, Suciu, SIGMOD Record 2016
Streaming
Models and issues in data stream systems, Babcock, Babu, Datar, Motwani, Widom, PODS 2002
The space complexity of approximating the frequency moments, Alon, Matias, Szegedy, STOC 1996
Data Extraction and Integration
Uncertain Data
Probabilistic Databases, Suciu, Olteanu, Re, Koch
Probabilistic Databases: Diamonds in the Dirt, Dalvi, Re, Suciu, CACM 2008
The dichotomy of probabilistic inference for unions of conjunctive queries, Dalvi, Suciu, JACM 2012
Consistent Query Answering: Five Easy Pieces, Chomicki, ICDT 2007
Consistent Query Answers in Inconsistent Databases, Arenas, Bertossi, Chomicki, PODS 1999
S. Sarawagi, Information Extraction, Foundations and Trends in Databases. Vol. 1, No. 3 (2007): read only Chapters 1-3.
Levy, Alon, Logic-based Techniques in Data Integration, available on the Web at http: //homes.cs.washington.edu/~alon/site/files/levy-di00.ps: read up to and including Section 5.1.
Doan, A., Halevy, A., Ives, Z., Principles of Data Integration, Chapter 1, Chapter 5, Chapter 4: read 4.1, 4.2.1 (only Edit Distance), 4.2.2 (only Overlap, Jaccard, and TF/IDF), 4.2.4, and 4.3 (only Inverted Index and Size Filtering). Chapter 7: up to and including 7.5.3. Chapter 9: read 9.1, 9.2, and 9.3.1. Chapters available from http://pages.cs.wisc.edu/~anhai/ courses/dibook-chapters.
Data Analysis and Decision Support
Gray, J., Chaudhuri, S., Bosworth, A., Layman, A., Reichart D., Venkatrao, M., Pellow, F., and Pirahesh, H., Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub- Totals. In Data Mining and Knowledge Discovery, 1(1): 29?53.
Agrawal, R., and R. Srikant, Fast Algorithms for Mining Association Rules. In Proceedings of the 20th International Conference on Very Large Data Bases, 487?499.
Zhang, T., Ramakrishnan R., and Livny M., BIRCH: A Clustering Algorithm for Large Multidimensional Datasets, Proceedings of the ACM SIGMOD International Conference on Management of Data, 1996
Graham Cormode, Minos Garofalakis, Peter J. Haas and Chris Jermaine, Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches, Foundations and Trends in Databases, Vol. 4, 2011.
DBMS and Search Engines
Brin, S. and Page, L., The Anatomy of a Large-Scale Hypertextual Web Search Engine, Proceedings of Computer Networks and ISDN Systems, 1998.
Singhal, A., Modern Information Retrieval: a Brief Overview. IEEE Data Engineering Bulletin, 24(4), 35- 43, 2001.
Page, L. and Brin, S. and Motwani, R. and Winograd, T., The Pagerank Citation Ranking: Bringing Order to the Web, Technical Report, 1999.
Emerging Topics
Last updated