Logik in der Informatik Prof. Dr. Nicole Schweikardt

Die Vorlesung wird jeweils zur Hälfte von Prof. Johann-Christoph Freytag, Ph.D. und Prof. Dr. Nicole Schweikardt gehalten.

Grundlegende Informationen zur Vorlesung und zur genauen Aufteilung der Vorlesungstermine erhalten Sie auf folgender Seite der Arbeitsgruppe Datenbanken und Informationssysteme (DBIS): Vorlesung Anfrageoptimierung in Datenbanksystemen — Theorie und Praxis

Aktuelles

• Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.
• Die 1. Vorlesung im Rahmen des Theorieteils fand am Dienstag, den 07.11.2017 statt.

Themen, die im Theorieteil der Vorlesung behandelt werden

1. Grundbegriffe (handschriftliche Notizen)
2. Die AGM-Schranke und andere obere Schranken für die Größe von Anfrageergebnissen (handschriftliche Notizen)
3. Aufzählung von Anfrageergebnissen mit konstanter Verzögerung (Folien)
4. Leapfrog-Triejoin — ein worst-case-optimaler Join-Algorithmus
5. Weiterführende Themen

Beachten Sie: In den Vorlesungsstunden wird viel an der Tafel gearbeitet. Alle behandelten Inhalte sind für die Veranstaltung wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den auf den Webseiten erhältlichen Materialien enthalten sind.
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte in den Vorlesungsstunden vermittelte Material durchzuarbeiten.
Es ist daher wichtig, dass Sie sich während den Vorlesungsstunden Notizen machen.

Logbuch

Hier finden Sie nach den Vorlesungen des Theorieteils Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Termine

Vorlesung

Dienstags 13:15-14:45 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 0'307 und
Mittwochs 13:15-14:45 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303
 
Dozenten: Prof. Johann-Christoph Freytag, Ph.D. und Prof. Dr. Nicole Schweikardt

Prüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungsstunden vermittelte Material durchzuarbeiten.

Die Modulabschlussprüfung wird durch eine mündliche Prüfung bei beiden Dozenten abgelegt.

Literatur

Allgemeine Literatur zum Thema Datenbanktheorie:

[S]	N. Schweikardt Skript(fragmente) zur Vorlesung "Einführung in die Datenbanktheorie". HU-Berlin, Wintersemester 2016/17.
[AHV]	S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Addison-Wesley, 1995. A pdf-version of the book is available here.
[SSS]	N. Schweikardt, T. Schwentick, L. Segoufin. Database Theory: Query Languages. Chapter 19 in Algorithms and Theory of Computation Handbook, 2nd edition, volume 2: Special Topics and Techniques. Mikhail J. Atallah and Marina Blanton (editors), CRC Press, 2009.

Weiterführende Literatur zu Kapitel 1:

[CM]	A. K. Chandra und P.M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Databases. Proceedings of the 9th Annual ACM Symposiom on Theory of Computer Science (STOC 1977), May 4-6, 1977, Boulder, Colorado, USA, ACM 1977.
[G-Param]	M. Grohe. Parameterized Complexity for the Database Theorist. SIGMOD Record, Volume 31, Number 4, 2002, pages 86-96.

Weiterführende Literatur zu Kapitel 2:

[G-AGM]	M. Grohe. Bounds and Algorithms for Joins via Fractional Edge Covers. In Search of Elegance in the Theory and Practice of Computation 2013: 321-338
[AGM]	A. Atserias, M. Grohe, D. Marx. Size Bounds and Query Plans for Relational Joins. SIAM J. Comput. 42(4): 1737-1767 (2013) (Dies ist die ausführliche Version der folgenden Arbeit: A. Atserias, M. Grohe, D. Marx. Size Bounds and Query Plans for Relational Joins. Proc. FOCS 2008, pp. 739-748.
[NPRR]	Hung Q. Ngo, Ely Porat, Christopher Ré, Atri Rudra. Worst-case optimal join algorithms: [extended abstract]. In Proc. PODS 2012, pp. 37-48
[T]	F. Topsøe. Informationstheorie. Teubner Studienbücher Mathematik, Teubner-Verlag, 1974. ISBN 3-519-02048-3. Siehe auch: Universitätsbibliothek der HU Berlin
[GLV]	G. Gottlob, S.T. Lee, G.J. Valiant. Size and treewidth bounds for conjunctive queries. Journal of the ACM 59(3) (2012) (Dies ist die ausführliche Version der folgenden Arbeit: G. Gottlob, S.T. Lee, G.J. Valiant. Size and treewidth bounds for conjunctive queries. Proc. PODS 2009, pp. 45-54.

Weiterführende Literatur zu Kapitel 3:

[BKS]	Christoph Berkholz, Jens Keppeler und Nicole Schweikardt. Answering Conjunctive Queries under Updates. In Proc. PODS 2017, pp. 303-318. Eine ausführliche Version des Artikels ist erhältlich unter CoRR abs/1702.06370 (2017)

Weiterführende Literatur zu Kapitel 4:

[V]	Todd L. Veldhuizen. Leapfrog Triejoin: A Simple, Worst-Case Optimal Join Algorithm. In Proc. ICDT 2014, pp. 96-106.