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

Aktuelles

• Am 7.7.2026 muss die Vorlesung leider ausfallen.
• Auf Grund des Tag der Informatik findet am Donnerstag, den 4.6.26 die Vorlesung nicht statt.
• Die Eröffnungsvorlesung fand am Dienstag, den 14.04.2026 statt.
• Die ersten Übungsstunden fanden am 22.04.2026 statt.
• Viele wichtige Informationen zur Veranstaltung finden Sie hier auf der Webseite, die regelmäßig aktualisiert wird.
• Im Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, Teile des Vorlesungsskripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

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.

Inhalt

• 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

Vorlesungsskript (Version vom 14. Juli 2026)

Beachten Sie:
In den Vorlesungs- und Übungsstunden wird hauptsächlich 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 oder in Moodle erhältlichen Materialien enthalten sind. Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte in den Vorlesungs- und Übungsstunden vermittelte Material durchzuarbeiten. Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden Notizen machen.

Logbuch

Im Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, Teile des Vorlesungsskripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

Termine

Vorlesung

Dienstags 15-17, ESZ (RUD26) 1.306 und

Donnerstags 15-17, ESZ (RUD26) 1.306

Dozent:in Dr. André Frochaux und Prof. Dr. Nicole Schweikardt

Übungen:

Gruppe 1: Mittwochs 09-11, RUD26, Raum 1.306 bei Dr. André Frochaux

Gruppe 2: Mittwochs 09-11, RUD26, Raum 1.307 bei M.Sc. Benjamin Scheidt

Übungsblätter

Ergänzend zu den Vorlesungen finden 2-stündige Übungen in kleinen Gruppen statt, in denen Fragen zur Vorlesung diskutiert und die Übungsaufgaben besprochen werden. Die Übungsgruppen treffen sich erstmalig in der zweiten Woche der Vorlesungszeit, also am 22.04.26.

Ab der zweiten Vorlesungswoche wird i.d.R. wöchentlich (jeden Mittwoch) ein Übungsblatt bereitgestellt. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

• Blatt 1 (bereitgestellt am 21.04.; zu bearbeiten bis 29.04., 9:00 Uhr)
• Blatt 2 (bereitgestellt am 29.04.; zu bearbeiten bis 06.05., 9:00 Uhr)
• Blatt 3 (bereitgestellt am 06.05.; zu bearbeiten bis 13.05., 9:00 Uhr)
• Blatt 4 (bereitgestellt am 13.05.; zu bearbeiten bis 20.05., 9:00 Uhr)
• Blatt 5 (bereitgestellt am 20.05.; zu bearbeiten bis 27.05., 9:00 Uhr)
• Blatt 6 (bereitgestellt am 27.05.; zu bearbeiten bis 03.06., 9:00 Uhr)
• Blatt 7 (bereitgestellt am 03.06.; zu bearbeiten bis 10.06., 9:00 Uhr)
• Blatt 8 (bereitgestellt am 10.06.; zu bearbeiten bis 17.06., 9:00 Uhr)
• Blatt 9 (bereitgestellt am 17.06.; zu bearbeiten bis 24.06., 9:00 Uhr)
• Blatt 10 (bereitgestellt am 24.06.; zu bearbeiten bis 01.07., 9:00 Uhr)
• Blatt 11 (bereitgestellt am 01.07.; zu bearbeiten bis 08.07., 9:00 Uhr)
• Blatt 12 (bereitgestellt am 08.07.; zu bearbeiten bis 15.07., 9:00 Uhr)

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 handschriftliche, ausführlich ausgearbeitete und mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde ab. Die Abgabe erfolgt entweder direkt zu Beginn der Übungsstunde beim Übungsleiter oder wird bis Mittwoch 9:00 Uhr in den Briefkasten am Lehrstuhl (RUD25 zwischen den Räumen 3.401 und 3.402) eingeworfen.
• Variante B:
  Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übungsstunde in eine vom Übungsleiter 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 vom Übungsleiter 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.

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 abgelegt. Auf der Webseite des Prüfungsbüros finden Sie den vollständigen Prüfungsplan (inkl. Prüfungszeitraum, Prüfungsterminen und Anmeldefristen und Hinweise zur Prüfungsan- und -abmeldung).

Hinweise zur Prüfungsanmeldung

1. Die Modulabschlussprüfung (kurz: MAP) wird als mündliche Prüfung durchgeführt. Dafür müssen Sie sich in AGNES anmelden – die Frist für die Anmeldung zum 1. Prüfungszeitraum endet am 02.07.2026 ! Für jeden Prüfungstag gibt es eine separaten Eintrag. Melden Sie sich nur für einen der Tage an. Sie können sich auch anmelden, falls Sie die Voraussetzung zur Zulassung zur MAP zum jetzigen Zeitpunkt noch nicht erfüllen. Sollten Sie die Zulassung bis zum 16.7.26 nicht besitzen, werden Sie automatisch wieder abgemeldet (ohne dass dadurch Nachteile für Sie entstehen). Umgekehrt ist der 02.07.2026 eine harte Frist: Danach ist für den ersten Prüfungszeitraum keine Anmeldung mehr möglich!
2. Zusätzlich zu der Anmeldung über Agnes benötigen Sie eine konkrete Prüfungszeit. Melden Sie sich dazu direkt nach Ihrer Anmeldung in Agnes per Mail an André Frochaux mit Silvia Schoch im cc. Nutzen Sie hierfür Ihre offizielle HU-Mail (CMS-Account) und geben Sie Ihren Namen, Ihre Matrikelnummer, das Modul (Einführung in die Datenbanktheorie) und den in Agnes ausgewählten Prüfungstag an und bitten um die Zuteilung einer Prüfungszeit. Wählen Sie bitten einen passenden Betreff für Ihre Mail. Wichtig: zur Durchführung der MAP ist beides nötig: fristgerechte Anmeldung in AGNES und Vereinbarung einer konkreten Prüfungszeit.

Voraussetzung für die Zulassung zur Modulabschlussprüfung

1. Erreichen von jeweils mindestens 40 Prozent der Punkte von zwei gesonderten Präsenzübungsblättern, welche in der Mitte und gegen Ende der Vorlesungszeit bearbeitet werden, TRUE  und
2. Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen.

Literatur

Zugang zur Online-Literatur

Einige der Bücher sind für Angehörige der HU Berlin online erhältlich (siehe Verlinkung). Loggen Sie sich dazu auf der Springerlink-Seite via Shibboleth mit ihrem CMS-Account ein (über Log In, Access via your institution bzw. Shibboleth-Login, Find your institution: Humboldt-Universität zu Berlin). Alternativ können Sie ggf. über eine VPN-Verbindung über das HU-Netz direkt darauf zugreifen. Zur Einrichtung eines VPN-Zugangs siehe die Anleitung des CMS.

Links