HomeCurrent Doctoral StudentsPh.D. CS Qualifier InformationDatabase Systems Body of Knowledge

PhD CS – Database Systems Body of Knowledge

The list below makes reference to chapters of three books:
  • Fundamentals of Database Systems, by R. Elmasri and S. Navathe, Addison Wesley, Fourth Edition, 2004.
  • Principles of Distributed Database Systems, by M. Ozsu and P. Valduriez, Prentice-Hall, Second Edition, 1999.
  • Database System Implementation, by H. Garcia-Molina, J. Ullman and J. Widom, Prentice-Hall, First Edition, 2000
We refer to the first reference as Navathe and to the second as Ozsu, and the third as Garcia-Molina (we use this third text book for CS 4420).


Background and data models

Textbooks
  • Navathe: Ch. 1-7, 10-11

Papers
  • Norman W. Paton, Oscar Díaz: Active Database Systems. ACM Comput. Surv. 31(1): 63-103 (1999)
  • S. H. Son, “DRDB: Towards Distributed Real-Time Database Services for Time-Critical Active Applications,” Journal of Systems and Software, Special Issue on Real-Time Active Database Systems, vol. 42, pp. 193-204, 1998.
  • Christian S. Jensen, Richard T. Snodgrass: Temporal Data Management. IEEE Trans. Knowl. Data Eng. 11(1): 36-44 (1999)

Query processing and optimization

Textbooks
  • Navathe: Ch. 15, 16
  • Garcia-Molina, Chapter 6,7
Papers
  • Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price. "Access Path Selection in a Relational Database Management System." SIGMOD Conference 1979 : 23-34.
  • G. Graefe. “Query Evaluation Techniques for Large Databases.” ACM Computing Surveys 25(2), 1993, pp. 73-170
  • Y. Ioannidis. “Query Optimization.” Handbook for Computer Science chapter 45 (CRC Press), available at http://www-db.stanford.edu/~widom/query-opt.ps
  • Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113 (1992)
  • M. Franklin, B. Jonsson, D. Kossman. "Performance Tradeoffs for Client-Server Query Processing" , SIGMOD, 1996

Transaction processing and concurrency control

Textbooks
  • Navathe: Ch. 17, 18 and 19
  • Ozsu: Ch. 11
  • Garcia-Molina, Chapter 8,9,10
Papers
  • Naser S. Barghouti and Gail E. Kaiser. "Concurrency control in advanced database applications," ACM Computer Survey. 23(3) (Sep. 1991), pp. 269 - 317
  • C. Mohan, et al."ARIES: A Transaction Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging," ACM TODS, 17(1), (March 1992).

Physical Organization

Textbooks
  • Navathe: Ch. 13 and 14
  • Garcia-Molina, Chapter 2,3,4,5
Papers
  • V. Gaede and O. Gunther. "Multidimensional Access Methods." Computing Surveys, 30:2, 1998, 170-231.
  • Patrick E. O'Neil, Dallan Quass. "Improved Query Performance with Variant Indexes." SIGMOD 1997: 38-49 available at: http://www.cs.umb.edu/~poneil/varindex.ps
  • A Guttman. "R-trees: A dynamic index structure for spatial searching", Proc. ACM SIGMOD 1984, pp47-57

Key systems projects

Papers
  • D. Chamberlin et al. A History and Evaluation of System R. CACM 24(10): 632-646(1981)
  • M. Stonebraker and G. Kemnitz. The POSTGRES Next-Generation Database Management System. Commun. ACM 34(10): 78-92(1991)
  • L. Haas et al. Starburst Mid-Flight: As the Dust Clears; IEEE TKDE, 2(1), March 1990, pp. 143-160.
  • S. Madden, M. J. Franklin, J. M. Hellerstein and W. Hong. TinyDB: An Acquisitional Query Processing System for Sensor Networks. ACM TODS.

Distributed and parallel systems

Textbooks
  • Navathe, Ch. 25
  • Ozsu: Ch. 4-5, 7-10
Papers
  • Gray et al. “The dangers of replication and a solution.” SIGMOD 1996.
  • "Parallel Database Systems: The Future of High Performance Database Systems," D. DeWitt and J. Gray, Comm. of the ACM, 35, 6, (June 1992), 85-97.
Semistructured data and XML

Papers
  • Querying Semistructured Data; Abiteboul, ICDT 1997
  • Lore: A Database Management System for Semistructured Data; McHugh et al., SIGMOD Record 26(3), Sept. 1997
  • Relational Databases for Querying XML Documents: Limitations and Opportunities; Shanmugasundaram et al., VLDB 1999
Specific areas: Mobile, Stream, federated, warehousing, data integration, the web, etc.

Textbooks
  • Garcia-Molina, Chapter 11
Papers
  • “Client-server computing in mobile environments,” J. Jing, A. Helal, A. Elmagarmid, ACM Comp. Surveys, 31,2, June 1999.
  • Babcock et al. Models and Issues in Data Stream Systems. PODS 2002.
  • Papers from: Heterogeneous Databases: Special Issue on Heterogeneous Databases, eds. A. Elmagarmid and C. Pu, ACM Computing Surveys, (1990).
  • Agrawal and Srikant. Fast Algorithms for Mining Association Rules. VLDB 1994.
  • J. Gray, A. Bosworth, A. Layman and H. Pirahesh, “Data Cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals”, Proc. Int. Conf. Data Engineering (1996) pp152-159.
  • V. Harinarayan, A. Rajaraman and J.D. Ullman, “Implementing Data Cubes efficiently”, ACM SIGMOD 1996, pp205-216.
  • A. P. Sheth and J.A. Larson, “Federated databases for managing distributed, heterogeneous and autonomous databases”, ACM Computing Surveys, 22:3 (1990) pp183-236
  • Chaudhuri and Dayal. An Overview of Data Warehousing and OLAP Technology. SIGMOD Record 26(1), March 1997
  • Brin, S., Page,L.: The anatomy of a large-scale hypertextual (web) search engine.. Computer Networks and ISDN Systems, 30(1-7) (1998) 107-117
  • R. Baeza-Yates, Information Retrieval in the Web: Beyond Current Research Engines, Int. J. Approximate Reasoning, 34, 2003.

Research in database systems

Papers