Computer Science Senior Project

 

This page is devoted to my fall 2002 senior project in Computer Science. Throughout the first semester of my senior year, I explored genetic algorithms and their use in terms of database query optimization.

In retrospect, I think my project was very ambitious—perhaps too ambitious. Toward the end of the semester, I was forced to retract some of my more impressive goals in favor of a simpler fallback position. In the end, however, I am still happy with the final product. Rather than try to condense the information about my project into a few sentences, I offer many of the documents that that I produced throughout the project. They are linked below.

 

Below is a link to my project log:

  • Computer Science Senior Project Log (currently being revised and updated)

 

Here are some links to my survey of query optimization and genetic algorithms:

 

I'm now also posting links to the written proposal for my project. A specific description of what my project entails, as well as information about how the project will be structured and carried out can be found in this paper:

 

Below is a link to the timeline in which I tried to confine my project:

 

Here are the links to the final paper for my project.  In this paper I review some of the information from my survey and my proposal, and I also explain the fallback position that I adopted, as well as the structure of the final version of the project:

  • MS Word Version (coming soon)
  • HTML Version (coming soon)

 

This is a link to the source-code for my project:

 

Here's the list of sources comprising the bibliography for my project:

·         Beasley, David, David R. Bull, Ralph R. Martin. "An Overview of Genetic Algorithms: Part 1, Fundamentals." University Computing, volume 15, issue 2 (February 1993), pp. 170-181.

·         Bennett, Kristin, Michael C. Ferris, and Yannis E. Ioannidis. "A Genetic Algorithm for Database Query Optimization." The Proceedings of the Fourth International Conference on Genetic Algorithms. San Diego, California: Morgan Kaufmann Publishers, 1991, pp. 400-407.

·         Celko, Joe. "Genetic Algorithms and Database Indexing." Dr. Dobb's Journal, volume 18, issue 4 (April 1993), pp. 30-34.

·         Goldberg, David E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, Massachusetts: Addison-Wesley, 1989.

·         Goldberg, David E. "Genetic and Evolutionary Algorithms Come of Age." Communications of the ACM, volume 37, issue 3 (March, 1994), pp. 113-119.

·         Holland, John H. "Genetic Algorithms." Scientific American, volume 267, issue 1 (January 1992), pp. 66-72.

·         Kim, Won. "On Optimizing an SQL-like Nested Query." ACM Transactions on Database Systems, volume 7, issue 3 (September 1982), pp. 443-469.

·         Lohman, Guy M., Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger. "Optimization of Nested Queries in a Relational Database." IMB Research Laboratory RJ4260, San Jose, Calif., April 1983.

·         McGoveran, David. "Evaluating Optimizers." Database Programming and Design, January 1990, pp. 38-49.

·         Momjian, Bruce. "PostgreSQL Internals Through Pictures." Software Research Associates, December 2001. Available online at http://developer.postgresql.org/pdf/internalpics.pdf

·         Ramakrishnan, Rahgu, Johannes Gehrke. Database Management Systems: Second Edition. Boston, Massachusetts: McGraw-Hill, 2000.

·         Selinger, Patricia G., Morton M. Astrahan, Donald D. Chamberlain, Raymond A. Lorie, Thomas G. Price. "Access Path Selection in a Relational Database Management System." Proceedings of ACM-SIGMOD, May 1979.

·         Stillger, Michael, and Myra Spiliopoulou. "Genetic Programming in Database Query Optimization." Proceedings of the First Annual Conference on Genetic Programming. Stanford, California, July 1996.

·         Wayner, Peter. "Genetic Algorithms: Programming Takes a Valuable Tip from Nature." Byte. January 1991, pp. 361-368.

·         Worsley, John C. and Joshua D. Drake. Practical PostgreSQL. Sebastopol, California: O'Reilly & Associates, 2002.

·         Yao, S. Bing. "Optimization of Query Algorithms." ACM Transactions on Database Systems, volume 4, issue 2 (June 1979), pp. 133-155.

Back to the Computer Science Senior Project page

Back to the Homepage