Algorithmen und Datenstrukturen für Datenbanksysteme

Proseminar Informatik im Sommersemester 2001
Prof. Dr. D. Kossmann

Termin:	Dienstags, 14 - 16 Uhr
Ort:	Orleansstr. 24, Raum 128 (1. Stock)
Beginn:	26. April 2001
Anmeldung:	per email, möglichst noch im Wintersemester an kossmann@in.tum.de
Vorbesprechung:	Es findet keine Vorbesprechung statt !
Ansprechpartner:	Prof. Dr. D. Kossmann (kossmann@in.tum.de, Orleansstr. 34, Raum 118, Tel. 48095-184)
Vorkenntnisse:	Vorlesungen: Einführung in die Informatik I und II
Schein:	Benoteter Schein bei Vortrag und regelmäßiger aktiver Teilnahme (Diskussionsbeiträge)
Literatur:	ist bei den einzelnen Vorträgen aufgeführt
Ablauf und Regeln:	Jeder Vortragende hat eine Ausarbeitung anzufertigen und eine Powerpoint (oder vergleichbare) Präsentation vorzubereiten. Die erste vollständige Version der Ausarbeitung muss zwei Wochen vor dem Vortrag per eMail an den Betreuer (Donald Kossmann) und den jeweiligen Buddy per eMail eingehen. Als Buddy lesen Sie die Ausarbeitungen Ihrer Komilitonen Korrektur. Die Powerpoint Präsentation muss eine Woche vor dem Vortrag vollständig sein. Eine Woche vor dem Vortrag treffen sich Vortragender, Buddy und Betreuer, um die Ausarbeitung und die Präsentation durchzusprechen. Alle diese Deadlines sind strikt.

Die Vorträge im einzelnen

1. Einführung in Seminartechniken
   (Angelika Reiser, eigener Vortrag des Lehrstuhls)
   Termin: 26. April 2001 (Donnerstag 14 Uhr, zusammen mit Hauptseminar)

2. Modellierung von Magnetplatten
   Termin: 8. Mai 2001 ENTFÄLLT!!!
   Chris Ruemmler, John Wilkes: An Introduction to Disk Drive Modeling. IEEE Computer, Volume 27, Number 3, March 199417-28

3. RAID-Plattenspeicher (Redundant Array of Inexpensive/Independent Disks)
   (Vortrag: Mykhaylo Mukhachov, Buddy: Dimitrij Tultschin)
   Termin: 15.Mai.2001
   Peter M. Chen, Edward L. Lee, Garth A. Gibson, Randy H. Katz, David A. Patterson: RAID: High-Performance, Reliable Secondary Storage. ACM Computing Surveys 26(2): 145-185 (1994)

4. B-Bäume
   (Vortrag: Dimitrij Tultschin, Buddy: Alexander Klitni)
   Termin: 22. Mai 2001
   R. Bayer, E. M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Informatica 1(3): 173-189 (1972)
   Douglas Comer: The Ubiquitous B-Tree . ACM Computing Surveys 11(2): 121-137 (1979)

5. Hashing
   (Vortrag: Alexander Klitni, Buddy: Stephan Hohe)
   Termin: 29. Mai 2001
   D. E. Knuth. "The Art of Computer Programming -- Sorting and Searching", Volume 3, Addison Wesley, 1973.

6. Lineares und erweiterbares/dynamisches Hashing
   (Vortrag: Stephan Hohe, Buddy: Florian Sager)
   Termin: 12. Juni 2001
   Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 (Reprinted in: M. Stonebraker (ed.), Readings in Database Systems, Morgan Kaufmann Publishers, 1994)
   Kotagiri Ramamohanarao, John W. Lloyd: Dynamic Hashing Schemes. The Computer Journal 25(4): 478-485 (1982)

7. R-Bäume
   (Vortrag: Florian Sager, Buddy: Georg Göttlich)
   Termin: 19. Juni 2001
   Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 (Reprinted in: M. Stonebraker (ed.), Readings in Database Systems, Morgan Kaufmann Publishers, 1994)
   Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 (Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990)

8. UB-Bäume
   (Vortrag: Georg Göttlich, Buddy: Fabian Riethmayer)
   Termin: 26. Juni 2001
   R. Bayer: The Universal B-Tree for Multidimensional Indexing. Technical Report TUM-I9637, November 1996.
   F. Ramsak et al.: Integrating the UB-Tree into a Database System Kernel. VLDB Conference 2000 (Proceedings of the Int. Conf. on Very Large Databases, Kairo, Ägypten, September 2000)

9. Grid-File
   (Vortrag: Fabian Riethmayer, Buddy: Marco Paleani)
   Termin: 3. Juli 2001
   Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Transactions on Database Systems (TODS) , Volume 9 (1): 38-71 (1984)

10. Sortieren (QuickSort, HeapSort etc.)
    (Vortrag: Marco Paleani, Buddy: Georg Lutz)
    Termin: 10. Juli 2001
    D. E. Knuth. "The Art of Computer Programming -- Sorting and Searching", Volume 3, Addison Wesley, 1973.
    T. H. Cormen and C. E. Leiserson and R. L. Rivest, "Introduction to Algorithms", MIT Press, 1990.

11. Externes Sortieren (MergeSort, Replacement Selection)
    (Vortrag: Georg Lutz, Buddy: Werner Jansen)
    Termin: 17. Juli 2001
    D. E. Knuth. "The Art of Computer Programming -- Sorting and Searching", Volume 3, Addison Wesley, 1973.
    Andrea C. Arpaci-Dusseau, Remzi Arpaci-Dusseau, David E. Culler, Joseph M. Hellerstein, David A. Patterson: High-Performance Sorting on Networks of Workstations. ACM SIGMOD Conference 1997: 243-254

12. Hashing-basierte Algorithmen
    (Vortrag: Werner Jansen, Buddy: Mykhaylo Mukhachov)
    Termin: 24. Juli 2001
    Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Transactions on Knowledge and Data Engineering, Volume 6 (6): 934-944 (1994)