Aktuelles:
|
An dieser Stelle finden Sie im Laufe des Seminars aktuelle
Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt.
-
Ab der zweiten Semesterwoche findet die Vorlesung Montags um 15:15 Uhr in Raum 1.306 und
Mittwochs um 13:15 in Raum 1.303 statt.
Im Anschluß an die Mittwochs-Vorlesung beginnt die Übung um 15:15 Uhr in Raum 1.303.
-
Die Vorlesungsfolien sowie
Informationen zum Inhalt der einzelnen Vorlesungsstunden
und gelegentlich ergänzende Bemerkungen
finden Sie (nach den Vorlesungen) im
Logbuch.
-
Eine Lösung für Aufgabe 2 von Blatt 10 finden Sie hier.
-
Die restlichen korrigierten Übungsaufgaben können Sie bei Frau Eisenmann (Raum 4.402, J.v.N.-Haus) bzw. bei Frau Kämpfer (Raum 4.407, J.v.N-Haus)
abholen.
|
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 einfach 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: Verbindungen zwischen SQL und Logik, statische Analyse und Anfrageoptimierung,
Anfragesprachen mit Rekursion (Datalog), Ausdrucksstärke und Auswertungskomplexität von Anfragesprachen, Abhängigkeiten und Normalformen.
|
Inhalt:
|
- Das Relationale Modell
- Konjunktive Anfragen (I)
- Relationale Algebra
- Relationenkalkül
- Konjunktive Anfragen (II)
- Abhängigkeiten und Normalformen
- Anfragesprachen mit Rekursion — Datalog
- Zusammenfassung und Ausblick auf weitere Themen
|
Logbuch:
|
Hier finden Sie (nach den Vorlesungen)
Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung
verwendeten Folien und
gelegentlich ergänzende Bemerkungen.
|
Informationen zum Vorlesungs- und Übungsbetrieb:
|
- Vorlesung:
- Montags 15-17 in Raum 1.306 und
Mittwochs 13-15 in Raum 1.303,
Erwin Schrödinger-Zentrums (Rudower Chaussee 26)
-
- Übung:
-
Mittwochs 15-17 in Raum 1.303,
Erwin Schrödinger-Zentrums (Rudower Chaussee 26)
-
- Dozentin:
-
Prof. Dr. Nicole Schweikardt
Sprechstunde: Dienstags 14-15 Uhr
|
Übungsaufgaben:
|
Es wird regelmäßig Übungsaufgaben geben, deren
erfolgreiche Bearbeitung
Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung
ist.
- Blatt 1 (ausgeteilt am 24.04.2006; abzugeben am 02.05.2006)
- Blatt 2 (ausgeteilt am 03.05.2006; abzugeben am 08.05.2006)
- Blatt 3 (ausgeteilt am 08.05.2006; abzugeben am 15.05.2006)
- Blatt 4 (ausgeteilt am 15.05.2006; abzugeben am 22.05.2006; Vorsicht bei Aufgabe 4: Anfrage (11) kann nicht im Guarded Fragment ausgedrückt werden)
- Blatt 5 (ausgeteilt am 22.05.2006; abzugeben am 29.05.2006; Aufgabe 4 ist "freiwillig")
- Blatt 6 (ausgeteilt am 29.05.2006; abzugeben am 06.06.2006)
- Blatt 7 (ausgeteilt am 12.06.2006; abzugeben am 19.06.2006)
- Blatt 8 (ausgeteilt am 19.06.2006; abzugeben am 03.07.2006)
- Blatt 9 (ausgeteilt am 21.06.2006; abzugeben am 03.07.2006)
- Blatt 10 (ausgeteilt am 05.07.2006; abzugeben am 12.07.2006); Lösung für Aufgabe 2 von Blatt 10: hier
- Blatt 11 (ausgeteilt am 12.07.2006; abzugeben am 19.07.2006)
|
Prüfung:
|
Zu Beginn der Semesterferien finden mündliche Prüfungen
statt. Für die Zulassung zur Prüfung müssen mindestens 40%
der Punkte in den Übungaufgaben erworben werden.
Prüfungstermine: 03.+04.08.2006 und 12.+13.10.2006 und nach Vereinbarung
Anmeldung bei Frau Eisenmann (Raum 4.402, J.v.N.-Haus) bzw. bei Frau Kämpfer (Raum 4.407, J.v.N-Haus)
|
Literatur:
| [AHV] |
S. Abiteboul, R. Hull, V. Vianu.
Foundations of Databases.
Addison-Wesley, 1995.
Download (pdf):
Frontmatter
|
Table of Contents
|
A
|
B
|
C
|
D
|
E
|
F
|
Bibliography
|
Index
|
| [AD] |
P. Atzeni, V. De Antonellis.
Relational Database Theory.
Addison Wesley Longman; 1st edition (January 1993).
|
| [ABS] |
S. Abiteboul, P. Buneman, D. Suciu.
Data on the Web.
Morgan Kaufmann Publishers, 2000.
|
| [M] |
D. Maier.
The Theory of Relational Databases.
Computer Science Press, 1983.
Download (pdf):
Frontmatter
|
Table of Contents
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
Bibliography
|
Index
|
| [CM] |
A. K. Chandra und P. M. Merlin.
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC 1977), May 4-6, 1977, Boulder, Colorado, USA. ACM 1977.
Download (pdf): hier.
|
| [G] |
M. Grohe.
Parameterized Complexity for the Database Theorist.
SIGMOD Record, Volume 31, Number 4, 2002, pages 86-96.
Download (pdf): hier.
|
| [SH] |
G. Saake und A. Heuer.
Datenbanken: Implementierungstechniken.
International Thomson Publishing, 800 Seiten, Mai 1999. Mehr Informationen incl. Leseprobe: hier.
|
| [LV] |
D. Leinders und J. Van den Bussche.
On the complexity of division and set joins in the relational algebra.
Proceedings of the 24th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS 2005), pages 76-83, 2005.
Download (pdf): hier.
|
| [KS] |
S. Kreutzer und N. Schweikardt.
Logik und Komplexität. Skript zur Vorlesung im Sommersemester 2005, Humboldt-Universität zu Berlin.
Download (pdf): hier.
|
| [Y] |
M. Yannakakis.
Algorithms for acyclic database schemas.
Proceedings of the 7th International Conference on Very Large Databases (VLDB 1981), pages 82-94, 1981.
Download (pdf): hier.
|
| [S] |
F. Scarcello.
Query Answering Exploiting Structural Properties.
SIGMOD Record , vol. 34, No 3, pages 91-99, Sept. 2005.
Download (pdf): hier.
|
| [CV] |
S. Chaudhuri und M. Vardi.
Optimization of Real Conjunctive Queries.
Proceedings of the 12th ACM Sigact-Sigart Symposium on Principles of Database Systems (PODS 1993), pages 59-70, 1993.
Download (pdf): hier.
|
| [AL] |
M. Arenas und L. Libkin.
An Information-Theoretic Approach to Normal Forms for Relational and XML Data.
Journal of the ACM, Volume 52, No. 2, 2005, pages 246-283.
Download (pdf): hier.
|
|
Links:
