TU Wien:Deduktive Datenbanken VO (Woltran)

Aus VoWi
Wechseln zu: Navigation, Suche

Daten[Bearbeiten]

Inhalt[Bearbeiten]

  • Was sind deduktive Datenbanken?
  • Vergleich von Datenbanken und logikorientierter Programmierung
  • Wiederholung von Aussagen- und Prädikatenlogik
  • Quantifizierte Aussagenlogik
  • Answer Set Programming
  • Typen von Programmen
  • Typen von Äquivalenz zwischen Programmen und Äquivalenzkriterien
  • Non-Ground Programs
  • Optimierung von Queries
  • Komplexitätsanalysen der vorgestellten Probleme

Ablauf[Bearbeiten]

Es gibt 5 Blöcke zu je 3 Stunden (mit einer kurzen Pause zwischendurch). Die Termine werden am Semesteranfang gemeinsam mit den Studierenden festgelegt und werden dann etwa zur Semestermitte innerhalb von 2 Wochen abgehalten.

Die Termine bestehen zum Großteil aus einer Vorlesung, am Ende jedes Blocks werden aber optionale Übungsbeispiele vorgestellt, die man bis zum nächsten Termin zu Hause lösen und dann auf freiwilliger Basis an der Tafel präsentieren kann. Dafür kann man bis zu einen Bonuspunkt bekommen, der einem bei der Prüfung (auf die es 8 Punkte gibt) angerechnet wird.

Der Vortragende verwendet hauptsächlich seine englischen Folien und trägt bei Anwesenheit von Erasmus-Studenten auch auf Englisch vor. Zwischendurch verwendet er die Tafel für längere Beweise.

Modus WS2012:

  • Ende Oktober wurde der erste Termin gemacht, um die Termine festzulegen
  • Vom Vortragenden aus gab es die Möglichkeit: absolut geblockt (innerhalb von 2 Wochen) oder relativ klassisch (wöchentliche Termine).
  • Es wurde was dazwischenliegendes gewählt: 6 Blöcke zu jeweils 3 Stunden in 3 Wochen, Mitte November bis Anfang Dezember
  • Rest des Ablaufs ist gleich wie beschrieben

Benötigte/Empfehlenswerte Vorkenntnisse[Bearbeiten]

Aussagen- und Prädikatenlogik sollte man beherrschen. Sie wird zwar im Prinzip wiederholt, wer sie dort aber wirklich zum ersten Mal hört wird es eher schwer haben. Erfahrung mit Answer-Set-Programming schadet auch nicht. Wer bereits Logikorientierte Programmierung gehört hat, kann schon die Hälfte dieser LVA abhaken.

WS2012: Der Satz mit dem "Abhaken" ist mMn eine absolute Übertreibung. Wer LogProg und EWBS bei Egly&Tompits gemacht hat, kann eventuell 10% von der LVA abhaken, aber mehr sicher nicht.

Vortrag[Bearbeiten]

Auf Englisch, gut verständlich und locker. Der Vortragende bemüht sich um Kontakt mit Studierenden und kann wegen der geringen Anzahl von Teilnehmern (etwa 15) gut auf Fragen und Übungsbeispiele eingehen.

Übungen[Bearbeiten]

Es gibt insgesamt etwa 6-8 optionale Übungsbeispiele, für die man (insgesamt) bis zu einen Bonuspunkt bekommen kann (den man meistens schon bekommt wenn man auch nur eines der Beispiele präsentiert). Der Aufwand dafür hält sich in Grenzen wenn man in der VO war.

Prüfung, Benotung[Bearbeiten]

Der erste Prüfungstermin ist schriftlich, bei Bedarf können individuell mündliche Termine vereinbart werden. Es dürfen alle nicht-eletronischen Unterlagen verwendet werden (auch gelöste Übungsbeispiele). Der Lernaufwand ist eher niedrig wenn man ein bisschen Ahnung von Logik hat.

Modus

Wintersemester 2008: Es kamen 4 Fragen die je 2 Punkte wert waren. Der Vortragende gab in der letzten VO-Einheit einige Hinweise was zur Prüfung kommen wird, die auch sehr nützlich waren.

  • Eine gegebene Aussage als QBF formulieren
  • Zwei Programme auf Strong Equivalence testen
  • Sich Kriterien für die Existenz eines Horn Programms überlegen, das zu einem beliebigen Programm äquivalent sein soll
  • Ein graphentheoretisches Problem als Non-Ground Program formulieren

WS 2012:

  • Wieder schriftliche 4 Fragen mit jeweils 2 Punkten.
  • mMn gibt es keine mündlichen Termine. Stefan Woltran hat mal zwischendurch erzählt, dass er letztes Semester eine schriftliche Prüfung für einen einzelnen veranstaltet hat.
  • Wenn man ein Übungsbsp vorgerechnet hat, zählt das 0,5 Punkte.
  • Notenschlüssel ungefähr (soweit ich mich erinnern kann, aber da war noch irgendwas besonderes mit dem 4er was ich nicht mehr weiß):
    • >= 7 Punkte = 1
    • >= 6 Punkte = 2
    • >= 5 Punkte = 3
    • >= 4.5 Punkte = 4
  • Fragen zum 1. Termin WS2012:
    • Formel \varphi über V gegeben. Gesucht: closed QBF, die genau dann wahr ist, wenn \varphi exakt 1 Modell hat.
    • 2 Propositional Disjunctive Logic Programs: Strong Equivalence und Uniform Equivalence ausrechnen (+ Gegenbeispiel)
    • Suchen Sie Bedingungen für Strong Inclusion anhand von SE-Modellen: Welche Eigenschaften müssen die SE-Modelle von 2 Programmen P und Q haben, sodass immer AS(P u R) \subseteq AS(Q u R)?
    • Ein relativ kompliziertes Beispiel, worin man mit non-ground logic programs ein graphentheoretisches Problem lösen musste.

Dauer der Zeugnisausstellung[Bearbeiten]

Das Zeugnis wurde noch am Tag der Prüfung ausgestellt.

WS2012: Es wurde an alle Teilnehmer am Tag der Prüfung eine Mail mit Punktestand und Note ausgeschickt (und Termin für Einsichtnahme). Zeugnis folgt nach Einsichtnahme.

Zeitaufwand[Bearbeiten]

Im Durchschnitt würde ich schätzen: 5 mal 3 Stunden Anwesenheit, dazu noch etwa 5 Stunden für Übungsbeispiele und Prüfungsvorbereitung

WS2012: Meiner Meinung nach ist obiges eine grobe Fehleinschätzung, und zwar nach unten. Wer es drauf anlegt, bei dem Fach eine (sehr) gute Note zu haben und/oder mit extrem formalen Themen, A4-seitenlangen LaTeX-Beweisen über Logik-Themen etc. Schwierigkeiten hat, sollte da mindestens 20 Stunden Lernzeit und 10 Stunden für die Vorbereitung der Übungsaufgaben einplanen. Dazu kommt eventuell die Anwesenheit in der VO, die tatsächlich nicht unnütz ist, und sei es nur, um den halben Punkt beim Tafelrechnen zu bekommen.

Unterlagen[Bearbeiten]

Die Folien und zusätzliches Material (Beweise) in auf der TISS-Seite verlinkt

Verbesserungsvorschläge / Kritik[Bearbeiten]

  • Dem Vortragenden ist es selbst bekannt und er gibt es auch zu: Der Titel der LVA ist relativ irreführend. Auch das Lesen der Inhaltsangabe auf dieser Seite hier ist höchstwahrscheinlich irreführend. Das bei weitem über alles ragende Thema dieser LVA ist Äquivalenz von verschiedenen Sorten von Answer-Set-Programmen à la DLV. Der Kernpunkt, der äußerst lang ausgewalzt wird, ist die Frage: Wie/Wie schnell/Ist es möglich, zu beweisen/zu widerlegen, dass für zwei gegebene Answer-Set-Programme P und Q gilt: AnswerSets(P u R) = AnswerSets(Q u R) für alle weiteren Programme R? Das Problem nennt sich Strong Equivalence und es gibt da durchaus einen gewissen Haufen wissenschaftlicher Arbeiten dazu. Mit den Kernthemen von "deduktiven Datenbanken" hat das Thema nur wenig zu tun. Eventuell hätte ich selbst die LVA nicht gewählt, wenn ich das gewusst hätte. Fazit: Wer Spaß an formalem Denken, Beweisen, DLV und Answer Set Programming hat, der soll die LVA machen. Wer eine Einführung in deduktive Datenbanken sucht, wird vermutlich enttäuscht werden.