# 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&#x20;

* S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Available for free from: http: //webdam.inria.fr/Alice/&#x20;
  * 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&#x20;

* 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&#x20;

* 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&#x20;

* 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&#x20;

* 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&#x20;

* 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&#x20;

* 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&#x20;
  * 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&#x20;

* 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&#x20;

* [The Case for Learned Index Structures](https://arxiv.org/pdf/1712.01208.pdf)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sliu583.gitbook.io/blog/db/untitled.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.