DB Prelims Reading List, 2006

UC Berkeley EECS

1. Undergraduate material: Database Management Systems, 3rd edition, Ramakrishnan/Gehrke.
2. Relational roots:
   • E. F. Codd. ``A Relational Model of Data for Large Shared Data Banks.'' Commun. ACM 13(6), 1970, 377-387. [RDBS-3].
   • Stonebraker, et al. ``The Design and Implementation of INGRES.'' ACM Trans. Database Syst., 1 (3 ), 1976 , 189-222. [RDBS-3]
   • Chamberlin, et al. ``A History and Evaluation of System R.'' Commun. ACM, 24(10), 1981, 632-646. [RDBS-3]
   • Hellerstein and Stonebraker. ``Anatomy of a Database System.'' [RDBS-4]
3. Data storage and access methods
   • J. Gray and G. Graefe. ``The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb.'' SIGMOD Record, 26(4), 1997, 63-68. [RDBS-4]
   • D. A. Patterson, G. A. Gibson, and R. H. Katz. ``A Case for Redundant Arrays of Inexpensive Disks (RAID)''. Proc. SIGMOD Conference, 1988, 109-116. [RDBS-4]
   • S. Acharya, et al. ``Broadcast Disks: Data Management for Asymmetric Communications Environments''. SIGMOD Conference 1995.
   • N. Beckmann, et al. ``R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.'' Proc. SIGMOD Conference, 1990 [RDBS-4].
   • P. E. O'Neil and D. Quass. ``Improved Query Performance with Variant Indexes.'' Proc. SIGMOD Conference, 1997, 38-49. [RDBS-4]
4. Query optimization
   • P. G. Selinger, et al. ``Access Path Selection in a Relational Database Management System''. Proc. SIGMOD Conference, 1979, 23-34. [RDBS-4]
   • L. F. Mackert and G. M. Lohman. ``R* Optimizer Validation and Performance Evaluation for Distributed Queries.'' Proc. VLDB, 1986, 149-159. [RDBS-4]
   • R. Avnur and J. M. Hellerstein. ``Eddies: Continuously Adaptive Query Processing.'' Proc. SIGMOD Conference, 2000, 261-272. [RDBS-4]
5. Parallel query execution
   • DeWitt and Gray. ``Parallel Database Systems: The Future of High Performance Database Systems''. Commun. ACM, 35(6), 1992, 85-98. [RDBS-4]
   • G. Graefe. ``Encapsulation of Parallelism in the Volcano Query Processing System''. Proc. SIGMOD Conference, 1990, 102-111. [RDBS-4]
   • C Nyberg, et al. ``AlphaSort: A Cache-Sensitive Parallel External Sort''. VLDB Journal, 4(4), 1995, 603-627. [RDBS-4]
6. Transaction management
   • H. T. Kung and J. T. Robinson. ``On Optimistic Methods for Concurrency Control.'' Proc. VLDB 1979, 351. [RDBS-4]
   • R. Agrawal and M. J. Carey and M. Livny. ``Concurrency Control Performance Modeling: Alternatives and Implications''. ACM Trans. Database Syst., 12(4), 1987, 609-654. [RDBS-4]
   • P. L. Lehman and S. B. Yao. ``Efficient Locking for Concurrent Operations on B-Trees''. ACM Trans. Database Syst., 6(4), 1981, 650-670. [RDBS-4]
   • C. Mohan, et al. ``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. [RDBS-4]
   • M. Stonebraker. ``The Design of the POSTGRES Storage System''. Proc. VLDB, 1987, 289-300. [RDBS-3]
   • J. Gray, et al. ``The Dangers of Replication and a Solution''. Proc. SIGMOD Conference, 1996, 173-182.
7. Extensibility and Objects
   • C. Zaniolo. ``The Database Language GEM.'' Proc. SIGMOD Conference, 1983, 207-218. [RDBS-3]
   • C. Lamb, et al. ``The ObjectStore Database System.'' Commun. ACM, 34(10), 1991, 50-63. [RDBS-3]
   • M. Stonebraker and G. Kemnitz. ``The Postgres Next Generation Database Management System''. Commun. ACM, 34(10), 1991, 78-92. [RDBS-3]
   • J. M. Hellerstein, J. F. Naughton, and A. Pfeffer. ``Generalized Search Trees for Database Systems''. Proc. VLDB, 1995, 562-573. [RDBS-4]
   • G. M. Lohman. ``Grammar-like Functional Rules for Representing Query Optimization Alternatives.'' Proc. SIGMOD Conference, 1988, 18-27. [RDBS-4]
8. Semistructured data and XML
   • R. Goldman, J. Widom. ``DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases.'' Proc. VLDB, 1997, 436-445. [RDBS-4]
   • A. Deutsch, M. Fernandez and D. Suciu. ``Storing Semistructured Data with STORED''. Proc. ACM-SIGMOD, 1999.
   • B. F. Cooper, et al. ``A Fast Index for Semistructured Data''. Proc. VLDB 2001.
9. Datalog and recursive queries
   • F. Bancilhon and R. Ramakrishnan. ``An amateur's introduction to recursive query processing strategies''. Proc. ACM-SIGMOD 1986.
     • .Jeff Ullman's course notes on ``Logic as a Database Language'' and ``Magic-Sets and Deductive Databases'' may be useful background,
10. Warehousing and decision support
    • S. Chaudhuri and U. Dayal. ``An Overview of Data Warehousing and OLAP Technology.'' SIGMOD Record, 26(1), 1997, 65-74. [RDBS-4]
    • J. Gray, et al. ``Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals.'' Data Min. Knowl. Discov., 1(1), 1997, 29-53. [RDBS-4]
    • V. Harinarayan, R. Rajaraman, J. Ullman. ``Implementing Data Cubes Efficiently.'' Proc. SIGMOD Conf, 1996.
    • S. Ceri and J. Widom. ``Deriving Production Rules for Constraint Maintainance.'' Proc. VLDB, 1990, 566-577. [RDBS-4]
    • Y. Kotidis and N. Roussopoulos. ``DynaMat: A Dynamic View Management System for Data Warehouses''. Proc. SIGMOD Conference, 1999, 371-382. [RDBS-4]
    • J. M. Hellerstein, R. Avnur, and V. Raman. ``Informix under CONTROL: Online Query Processing''. Data Min. Knowl. Discov., 4(4), 2000, 281-314. [RDBS-4]
11. Data mining
    • T. Zhang, R. Ramakrishnan and M. Livny. ``BIRCH: An Efficient Data Clustering Method for Very Large Databases.'' Proc. SIGMOD Conference, 1996, 103-114. [RDBS-4]
    • J. C. Shafer, R. Agrawal, and M. Mehta. ``SPRINT: A Scalable Parallel Classifier for Data Mining.'' Proc. VLDB, 1996, 544-555. [RDBS-4]
    • R. Agrawal and R. Srikant. ``Fast Algorithms for Mining Association Rules in Large Databases'' Proc. VLDB, 1994, 487-499. [RDBS-4]
12. Triggers, sequences and data streams
    • E. N. Hanson, et al. ``Scalable Trigger Processing.'' Proc. ICDE, 1999, 266-275. [RDBS-4]
    • P. Seshadri, M. Livny and R. Ramakrishnan. ``The Design and Implementation of a Sequence Database System.'' Proc. VLDB, 1996, 99-110. [RDBS-4]
    • S. Chandrasekaran, et al. ``TelegraphCQ: Continuous Dataflow Processing for an Uncertain World''. Proc. CIDR, 2003.
    • Y. Diao and M. J. Franklin. ``Query Processing for High-Volume XML Message Brokering''. Proc. VLDB 2003.
13. Internet Search \& Services
    • E. A. Brewer. ``Combining Systems and Databases: A Search Engine Retrospective''. [RDBS-4]
    • S. Brin, L. Page. ``The Anatomy of a Large-Scale Hypertextual Web Search Engine.'' Computer Networks, 30(1-7), 1998, 107-117. [RDBS-4]
    • Dean Jacobs. ``Data Management in Application Servers.'' [RDBS-4]
14. Networked Query Processing
    • B. Yang, H. Garcia-Molina, ``Improving Search in Peer-to-Peer Systems.'' Proc. 22nd Int. Conf. on Distr. Comp. Sys. (ICDCS), 2002.
    • I. Stoica, et al. ``Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications.'' Proc. SIGCOMM 2001.
    • S. Madden, et al. ``TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks''. In Proc. OSDI, 2002.
    • A. Deshpande, et al. ``Model Driven Data Acquisition in Sensor Networks'' In Proc. VLDB, 2004.

• Chapter introductions, Readings in Database Systems, Hellerstein and Stonebraker, eds.
• Some lecture notes for the above.