Logik und Datenbanktheorie Prof. Dr. Nicole Schweikardt

Logik in der Informatik, Institut für Informatik, Humboldt-Universität zu Berlin

Aktuelles:

An dieser Stelle finden Sie im Laufe des Seminars aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt. Das Programm finden Sie hier.   Hinweis an die Seminarteilnehmer/innen: Schauen Sie sich die Folien (+ O-Ton) von Prof. Dan Sucius Vorträgen zur Einführung in Probabilistische Datenbanken an. Danach wird es Ihnen hoffentlich sehr viel leichter fallen, die zu Ihrem Vortragsthema gehörende Literatur zu verstehen.

Programm:

Das Seminar findet in Raum 4.410 des Johann von Neumann-Hauses statt. Für jeden Vortrag sind 60 Minuten eingeplant: 45 Minuten für den Vortrag und zusätzlich 15 Minuten für Zwischenfragen und Diskussion. Donnerstag, 26.10.06 11:15 - 12:45:   Nicole Schweikardt, Einführung in die Datenbanktheorie (Teil 1) Donnerstag, 02.11.06 11:15 - 12:45:   Nicole Schweikardt, Einführung in die Datenbanktheorie (Teil 2) Donnerstag, 08.02.07 10:15 - 11:15:   Konstanze Swist, The Management of Probabilistic Data 11:15 - 12:15:   Lucas Heimberg, Asymptotic Conditional Probabilities for Conjunctive Queries 12:15 - 13:30:   – Mittagspause – 13:30 - 14:30:   Christoph Sawade, Query Evaluation on a Database Given by a Random Graph 14:30 - 15:30:   André Böhm, Can Datalog be Approximated? Freitag, 09.02.07   9:15 - 10:15:   Deniz Aslaner, Answering Queries Using Views 10:15 - 10:30:   – Pause – 10:30 - 11:30:   Christoph Böhm, Probabilistic Query Answering Using Views (Teil 1) 11:30 - 12:30:   Sebastian Ehrich, Probabilistic Query Answering Using Views (Teil 2)

Einführung:

Im Unterschied zu herkömmlichen Datenbanken, bei denen für jedes Tupel klar ist, ob es zur Datenbank gehört oder nicht, werden beim Thema probabilistische Datenbanken Szenarien betrachtet, in denen die Daten nur in unpräziser Form gegeben sind und man daher bei manchen Tupeln nicht genau weiß, ob sie wirklich zur Datenbank gehören oder nicht. Mathematisch modelliert werden können solche Szenarien am besten durch so genannte probabilistische Datenbanken, bei denen jedem Tupel ein Wert zugeordnet ist, der angibt, mit welcher Wahrscheinlichkeit das Tupel zur Datenbank gehört. Im Seminar werden die theoretischen Grundlagen von solchen probabilistischen Datenbanken erarbeitet, u.a. beispielsweise die Auswertungskomplexität von Anfragen an probabilistische Datenbanken sowie die Bearbeitung von Anfragen unter Nutzung probabilistischer Sichten. Ein guter Überblick über das Thema "Probabilistische Datenbanken" wird in den beiden folgenden Vorträgen (Folien + O-Ton) von Prof. Dan Suciu (Univ. Washington) gegeben: Probabilities in databases and in logics I, Vortrag am 27.02.2006 im Isaac Newton Institute Workshop "Logic and Databases", Cambridge, U.K. Probabilities in databases and in logics II, Vortrag am 28.02.2006 im Isaac Newton Institute Workshop "Logic and Databases", Cambridge, U.K. Ein Überblick über einige grundlegende Begriffe und Resultate der Datenbanktheorie wird in den beiden Vorträgen "Einführung in die Datenbanktheorie (Teil 1)" und "Einführung in die Datenbanktheorie (Teil 2)" vom 26.10.06 und 02.11.06 gegeben. Eine detaillierte Einführung ins Thema "Datenbanktheorie" finden Sie auf der Webseite der Vorlesung Datenbanktheorie (HU Berlin, Sommersemester 2006). Das Seminar richtet sich an Studierende mit Interesse an theoretischer Informatik.

Zeit, Raum und Organisation:

Vorbesprechung und Themenvergabe finden in der ersten Semesterwoche am Donnerstag, 19.10.2006 um 11:15 Uhr in Raum 4.410 des Johann von Neumann-Hauses statt. Das Seminar ist als Blockveranstaltung organisiert und findet am Donnerstag, 8.2. und am Freitag 9.2.2007 statt. Für jeden Vortrag werden 60 Minuten eingeplant: 45 Minuten für den Vortrag und zusätzlich 15 Minuten für Zwischenfragen und Diskussion. Es wird zwei einführende Vorträge in die für das Seminar wichtigsten Begriffe, Fragestellungen und Ergebnisse der Datenbanktheorie geben: am Donnerstag, den 26.10.06 und 02.11.06, jeweils von 11:15-12:45 Uhr, in Raum 4.410, JvN-Haus. Bis Anfang Dezember erarbeiten Sie ein detailliertes Vortragskonzept, das Sie in der Woche vom 11. bis 15.12.2006 bei Nicole Schweikardt vorlegen. Vereinbarung: Wer sein Konzept nicht bis spätestens 15.12.06 mit mir durchgesprochen hat, nimmt nicht an dem Seminar teil. Die schriftliche Ausarbeitung Ihres Vortragsthemas (ca. 5 Seiten) geben Sie spätestens am Montag, 15.01.2007 ab.

Vortragsthemen und Literatur:
 

Themenbereich I: "Ungenaue Daten":   (7 Vorträge) The Management of Probabilistic Data. Daniel Barbará, Hector Garcia-Molina, Daryl Porter. IEEE Transactions on Knowledge and Data Engineering, 4(5):487-502, 1992   Vortragende: Konstanze Swist   Query Evaluation in Probabilistic Relational Databases. (2 Vorträge) Esteban Zimányi. Theoretical Computer Science 171 (1997) 179-219.   Vortragende/r: —   The Complexity of Query Reliability. Erich Grädel, Yuri Gurevich, Colin Hirsch. PODS 1998, Seattle, Washington, USA. Seiten 227-234, 1998.   Vortragender: Mathias Müller   Efficient Query Evaluation on Probabilistic Data. (2 Vorträge) Nilesh Dalvi, Dan Suciu. Erscheint im VLDB Journal, 2007. 22 Seiten. (Ausführliche Version einer Arbeit bei VLDB 2004)   Vortragende: Steffen Brüntjen und Stephan Allner   Efficient Top-k Query Evaluation on Probabilistic Data. Christopher Ré, Nilesh Dalvi, Dan Suciu. Technical Report #2006-06-05, University of Washington, Dept. of Computer Science and Engineering, 2006. 22 Seiten.   Vortragende: Swetlana Klaus   Themenbereich II: "Unvollständige Daten":   (7 Vorträge) Asymptotic Conditional Probabilities for Conjunctive Queries. Nilesh Dalvi, Gerome Miklau, Dan Suciu. ICDT 2005, Springer LNCS volume 3363, Seiten 289-305, 2005.   Vortragender: Lucas Heimberg   Query Evaluation on a Database Given by a Random Graph. Nilesh Dalvi, Dan Suciu. Technical Report, University of Washington, Dept. of Computer Science and Engineering, 2006. 19 Seiten. (Ausführliche Version einer Arbeit von Nilesh Dalvi bei ICDT 2007)   Vortragender: Christoph Sawade   Answering Queries Using Views. Alon Y. Levy, Alberto O. Mendelzon, Y. Sagiv, D. Srivastava. PODS 1995, San Jose, California, USA. Seiten 95-104, 1995.   Vortragender: Deniz Aslaner   Querying Partially Sound and Complete Data Sources. Alberto O. Mendelzon, George A. Mihaila. PODS 2001, Santa Barbara, California, USA. Seiten 162-170, 2001.   Vortragende/r: —   Probabilistic Query Answering Using Views. (2 Vorträge) Nilesh Dalvi, Dan Suciu. Technical Report, University of Washington, Dept. of Computer Science and Engineering, 2005. 40 Seiten. (Ausführliche Version einer Arbeit bei VLDB 2005)   Vortragende: Christoph Böhm und Sebastian Ehrich   Views and Queries: Determinacy and Rewriting. Luc Segoufin, Victor Vianu. PODS 2005, Baltimore, Maryland, USA. Seiten 49-60, 2005.   Vortragende/r: —   Themenbereich III: "Approximation":   (2 Vorträge) Can Datalog be Approximated?. Surajit Chaudhuri, Phokion Kolaitis. Journal of Computer and System Sciences 55 (1997) 355-369. (Ausführliche Version einer Arbeit bei PODS 1994)   Vortragender: André Böhm   Finding and Approximating Top-k Answers in Keyword Proximity Search. Benny Kimelfeld, Yehoshua Sagiv. PODS 2006, Chicago, Illinois, USA. Seiten 173-182, 2006. (Benny Kimelfelds Vortragsfolien bei PODS 2006: hier)   Vortragende/r: —

 

Terminplan:

Do. 19.10.06: Vorbesprechung und Themenvergabe (11:15-12:45, Raum 4.410, JvN-Haus)   Do, 26.10.06: Vortrag "Einführung in die Datenbanktheorie (Teil 1)" (11:15-12:45, Raum 4.410, JvN-Haus)   Do. 02.11.06: Vortrag "Einführung in die Datenbanktheorie (Teil 2)" (11:15-12:45, Raum 4.410, JvN-Haus)   Mo. 11.12. bis Fr. 15.12.06: Vorlage eines detaillierten Vortragskonzepts   Fr. 15.01.07: Abgabe der schriftlichen Ausarbeitung   Do. 8.2. und Fr. 9.2.07: Blockseminar