Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Aktuelles

• Am 20. und 21. Juni findet die Vorlesung und Übung krankheitsbedingt nicht statt.
• Die Eröffnungsvorlesung findet am Montag, den 25. April 2022 statt. Die erste Übung am 2. Mai. Beachten Sie bitte die aktuellen Hygieneregeln zur Teilnahme an Präsenzveranstaltungen.

Einführung

Die theoretischen Grundlagen von modernen Datenbanksystemen beruhen zu einem wesentlichen Teil auf zahlreichen Verbindungen zur Logik. Eine relationale Datenbank ist aus Sicht der Logik eine Grundmenge mit mathematischen Relationen; eine SQL-Anfrage ist im Kern eine Formel der Logik erster Stufe. Aufgrund dieses Zusammenhangs ermöglichen Techniken aus dem Bereich der Logik es, präzise Aussagen über die Ausdrucksstärke und die Auswertungskomplexität von Datenbankanfragesprachen zu treffen.

Die Vorlesung will den genannten Zusammenhang darstellen und die Grundzüge der Theorie relationaler Datenbanken vorstellen. Themen sind unter anderem: konjunktive Anfragen, Anfragesprachen mit Rekursion (Datalog), statische Analyse und Anfrageoptimierung (insbesondere von konjunktiven Anfragen), Ausdrucksstärke und Auswertungskomplexität von Anfragesprachen.

Ziel dieser Veranstaltung ist, die theoretischen Grundlagen relationaler Datenbanksysteme zu verstehen. Dies beinhaltet u.a. die Fähigkeit, die Möglichkeiten und Grenzen der Ausdrucksstärke verschiedener Anfragesprachen sowie die zur Auswertung von Anfragen benötigten Ressourcen einschätzen zu können.

Die Vorlesung richtet sich an fortgeschrittene Studierende in einem Bachelorstudiengang oder Studierende eines Masterstudiengangs, die an der Schnittstelle zwischen Theorie und Praxis interessiert sind. Voraussetzung für die Teilnahme sind Kenntnisse, die in der Vorlesung "Logik in der Informatik" vermittelt werden, sowie Kenntnisse über die Grundlagen von Datenbanksystemen.

Inhalte

• Kapitel 1: Einleitung
• Kapitel 2: Das Relationale Modell
• Kapitel 3: Konjunktive Anfragen
• Kapitel 4: Datalog
• Kapitel 5: Funktionale Abhängigkeiten
• Kapitel 6: Relationale Algebra
• Kapitel 7: Relationenkalkül
• Kapitel 8: Zusammenfassung und Ausblick

Logbuch

Im Logbuch werden regelmäßig Informationen bekannt gegeben.

Termine

Vorlesung

Montag 11:00-13:00, Schrödinger-Zentrum (RUD26), Raum 1'307 und
Dienstag 11:00-13:00, Schrödinger-Zentrum (RUD26), Raum 1'305

Übung

Montag 13:00-15:00, Schrödinger-Zentrum(RUD26),Raum1'307

Übungsblätter

Ab der zweiten Vorlesungswoche wird wöchentlich, jeweils freitags spätestens 23:59 Uhr, ein Übungsblatt hier und im Moodle-Kurs online bereitgestellt.

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten

Sie können bei jedem Übungsblatt entscheiden, gemäß welcher der folgenden beiden Varianten A bzw. B Ihre Lösung bewertet werden soll:

Variante A:
Sie geben eine schriftliche, ausführlich ausgearbeitete und mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde am Montag im Moodle-Kurs ab.

Variante B:
Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übung in eine bereitgestellte Liste ein, wie viele Übungspunkte Sie für Ihre Lösung der einzelnen Aufgaben(teile) für gerechtfertigt halten. Während der Übungsstunde werden aus dieser Liste einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass Sie keine sinnvolle Lösung vorweisen können, obwohl Sie in der Liste Punkte für diese(n) Aufgabe(nteil) eingetragen haben, werden Ihnen für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet. Eine sinnvolle Lösung muss hierbei nicht notwendigerweise vollständig korrekt sein.

• Blatt 1 (bereitgestellt am 29.04.; zu bearbeiten bis 09.05, 12:59 Uhr)
• Blatt 2 (bereitgestellt am 06.05.; zu bearbeiten bis 16.05, 12:59 Uhr)
• Blatt 3 (bereitgestellt am 15.05.; zu bearbeiten bis 23.05, 12:59 Uhr)
• Blatt 4 (bereitgestellt am 20.05.; zu bearbeiten bis 30.05, 12:59 Uhr)
• Blatt 5 (bereitgestellt am 29.05.; zu bearbeiten bis 07.06, 10:59 Uhr)
• Blatt 6 (bereitgestellt am 3.06.; zu bearbeiten bis 13.06, 12:59 Uhr)
• Blatt 7 (bereitgestellt am 12.06.; zu bearbeiten bis 20.06, 12:59 Uhr)
• Blatt 8 (bereitgestellt am 27.06.; zu bearbeiten bis 04.07, 12:59 Uhr)
• Blatt 9 (bereitgestellt am 03.07.; zu bearbeiten bis 11.07, 12:59 Uhr)
• Blatt 10 (bereitgestellt am 11.07.; zu bearbeiten bis 18.07, 12:59 Uhr)

Prüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden behandelte Material durchzuarbeiten.

Die Modulabschlussprüfung wird durch eine mündliche Prüfung erfolgen. Wenn es die Situation verlangt, wird diese per Zoom durchgeführt.

Voraussetzung für die Zulassung zur Prüfung ist:

• Bestehen der beiden jeweils 90-minütigen schriftlichen Tests, die in der Mitte und am Ende der Vorlesungszeit geschrieben werden und
• Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen. Beachten Sie hierzu auch die "Spielregeln".

Literatur

Links