Reading List for Spring 2004 DAIS Qualifying Examination

RDS3 = Readings in Database Systems (3rd edition)

A History and Evaluation of System R; Chamberlin et al., RDS3 pp. 54-68
The POSTGRES Next-Generation Database Management System; Stonebraker and Kemnitz, RDS3 pp. 524-538
Starburst Mid-Flight: As the Dust Clears; Haas et al., IEEE TKDE, 2(1), March 1990, pp. 143-160

An Overview of Query Optimization in Relational Systems; Chaudhuri, PODS 1998
Access Path Selection in a Relational Database Management System; Selinger et al., RDS3 pp. 141-152
Multidimensional Access Methods; Gaede and Günther, ACM Computing Surveys, Vol. 30, No. 2, Pages 170-231, 1998
Generalized Search Trees for Database Systems; Hellerstein et al., RDS3 101-112
Query Evaluation Techniques for Large Databases; Graefe, ACM Computing Surveys 25(2), 1993, pp. 73-170
Optimal Aggregation Algorithms for Middleware; Fagin et al., PODS 2001

Chapters 17, 18, 19 of Database Systems: The Complete Book, Ed. 1, by Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom, Prentice Hall.
A Measure of Transaction Processing Power; Anon et al., Readings in Database Systems, 3rd edition pp. 609-621.

Lecture Notes on Principles of Database Systems; Ullman, available at http://www-db.stanford.edu/~ullman/cs345-notes.html: Logic as a Database Language, Conjunctive Queries, and Information Integration Systems
Answering Queries Using Views: A Survey; Levy, available at http://www.cs.washington.edu/homes/alon/site/files/view-survey.ps
Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources; Tork-Roth and Schwarz, VLDB 1997

S. Chaudhuri, and U. Dayal. An overview of data warehousing and OLAP technology.ACM SIGMOD Record, 26(1):65-74, 1997.
Y. Zhao, P. M. Deshpande, and J. F. Naughton. An array-based algorithm for simultaneous multidimensional aggregates. In SIGMOD'97, pp. 159-170, Tucson, Arizona, May 1997.
K. Beyer and R. Ramakrishnan. Bottom-up computation of sparse and iceberg cubes. In SIGMOD'99, pp. 359--370, Philadelphia, PA, June 1999.
D. Xin, J. Han, X. Li, B. W. Wah, Star-Cubing: Computing Iceberg Cubes by Top-Down and Bottom-Up Integration, Proc. 2003 Int. Conf. on Very Large Data Bases (VLDB'03), Berlin, Germany, Sept. 2003.

R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In VLDB'94, pp. 487-499, Santiago, Chile, Sept. 1994.
J. Han, J. Pei, and Y. Yin. Mining Frequent Patterns without Candidate Generation., Proc. 2000 ACM-SIGMOD Int. Conf. on Management of Data (SIGMOD'00), Dallas, TX, May 2000.
J. Gehrke, R. Ramakrishnan, V. Ganti. RainForest: A framework for fast decision tree construction of large datasets. In VLDB'98, pp. 416-427, New York, NY, August 1998.
T. Zhang, R. Ramakrishnan, and M. Livny. BIRCH: An efficient data clustering method for very large databases. In SIGMOD'96, pp. 103-114, Montreal, Canada, June 1996.

A. McCallum and K. Nigam. A Comparison of Event Models for Naive Bayes Text Classification. In AAAI-98 Workshop on Learning for Text Categorization, 1998. Available at http://citeseer.nj.nec.com/55413.html
A. Berger and J. Lafferty. Information retrieval as statistical translation. In Proceedings of the 22nd ACM Conference on Research and Development in Information Retrieval (SIGIR'99), pages 222--229, 1999. Available at: http://citeseer.nj.nec.com/berger99information.html
T. H. Haveliwala. Topic-sensitive PageRank. In Proceedings of the Eleventh International World Wide Web Conference, 2002. Available at http://citeseer.nj.nec.com/haveliwala02topicsensitive.html

Querying XML Data; Deutsch et al., IEEE Data Engineering Bulletin, September 1999
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

R. Agrawal, K.-I. Lin, H.S. Sawhney, and K. Shim. Fast similarity search in the presence of noise, scaling, and translation in time-series databases. In VLDB'95, pp. 490-501, Zurich, Switzerland, Sept. 1995.
B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and Issues in Data Stream Systems. In ACM Symposium on Principles of Database Systems (PODS), pp. 1-16, Madison, Wisconsin, June 2002.
A. Califano, SPLASH: structural pattern localization analysis by sequential histograms, Bioinformatics, Vol. 16, no.4, 2000, pp. 341-357. Available at http://bioinformatics.oupjournals.org/cgi/content/abstract/16/4/341 and http://www.research.ibm.com/splash/Papers/SplashBioinformatics.PDF
The Lowell Database Research Self Assessment, 2003, available at http://research.microsoft.com/~Gray/Lowell/ in html and pdf formats.

DAIS - Database and Information Systems Laboratory, Department of Computer Science, University of Illinois at Urbana-Champaign, 201 N. Goodwin Ave., Urbana, IL 61801, USA. Fax: 217-265-6494, Phone: 217-244-6241.