|
Logik und Datenbanktheorie
Prof. Dr. Nicole Schweikardt |
 Logik in der Informatik, Institut für Informatik, Humboldt-Universität zu Berlin |
Die Arbeitsgruppe Logik und Datenbanktheorie ist an das Institut für Informatik der Johann Wolfgang Goethe-Universität in Frankfurt am Main umgezogen und heißt jetzt Arbeitsgruppe für Theorie komplexer Systeme.
Siehe http://www.informatik.uni-frankfurt.de/~tkshp.
|
Logik und Datenbanktheorie
Prof. Dr. Nicole Schweikardt |
Logik in der Informatik, Institut für Informatik, Humboldt-Universität zu Berlin |
Forschungsschwerpunkte - Mitarbeiter/innen - Publikationen - Lehre - Links - Kontakt
|
Die effiziente Verarbeitung extrem großer Datenmengen wird
— nicht zuletzt weil Sekundär- und Tertiär-Speicherplatz in den letzten Jahren
zu sehr preiswerten Ressourcen geworden sind — zu einer immer wichtigeren
Herausforderung für die Informatik.
Solch große Datenmengen treten in vielen Anwendungsbereichen auf,
etwa als Sammlung wissenschaftlicher Ergebnisse (z.B. Medizindatenbanken wie Medline
und Swiss-Prot),
in Form von Sensordaten oder als Börsenticker.
Häufig liegen die Daten dabei nicht in einer klassischen, effizient bearbeitbaren Datenbank, sondern nur in semistrukturierter Form vor, z.B. als XML-Dokument. Solche semistrukturierten Daten können auf natürliche Weise durch Bäume repräsentiert werden. Wegen der großen Datenmenge kann in der Regel nicht die Baumrepräsentation der gesamten Daten im Hauptspeicher eines Rechners vorgehalten werden, sondern nur ein gewisser Ausschnitt. In vielen Anwendungen sind die Daten sogar nur nach und nach, als Datenstrom zugänglich, etwa beim Börsenticker, der mit der Zeit immer wieder neue Informationen sendet. Zur effizienten Verarbeitung solcher Daten sind daher neue, über die aus der klassischen Datenbankverarbeitung bekannten hinausgehende Techniken erforderlich. Schwerpunkt dieser Arbeitsgruppe ist die Erforschung der theoretischen Grundlagen der Verarbeitung solch großer, semistrukturierter Datenmengen hinsichtlich Anfrageoptimierung, Eigenschaften von Anfragesprachen und Komplexitätstheorie für die Verarbeitung großer Datenmengen. Im Folgenden werden diese Themenbereiche kurz vorgestellt. Komplexitätstheorie für die Verarbeitung großer Datenmengen: Informationstheorie und Kommunikations-Komplexität von Problemen implizieren, dass der Effizienz der Verarbeitung von großen Datenmengen prinzipielle Schranken gesetzt sind. In diesem Projekt sollen geeignete Maschinenmodelle und Komplexitätsklassen herausgearbeitet werden, mit deren Hilfe der zur Lösung von Problemen nötige Speicheraufwand klassifiziert werden kann. Im Anschluss daran sollen untere Schranken für den durch Speicherzugriffe verursachten Aufwand zur Lösung konkreter Probleme gefunden werden. Das Ziel dieses Teilprojekts ist eine komplexitätstheoretische Untersuchung der Verarbeitung großer Datenmengen. Eigenschaften von Anfragesprachen: Für verschiedene Anfragesprachen sollen grundlegende Eigenschaften wie Ausdrucksstärke, Anfragelängen, Auswertungskomplexität, Minimierung, Erfüllbarkeit und Äquivalenz untersucht werden. Einige dieser Aspekte sind in Bezug auf Knoten-auswählende Sprachen bereits recht gut erforscht. Für Daten-Transformations Sprachen jedoch, die wesentlich komplexere Anfragen, beispielsweise Joins, ermöglichen, ist bisher nur wenig bekannt. Das Ziel dieses Teilprojekts ist die Klassifizierung der Eigenschaften von Daten-Transformations-Sprachen, auch unter Berücksichtigung von gegebenen Schema-Informationen. Anfrageoptimierung: Im Bereich der relationalen Datenbanken werden seit langem algebraische Verfahren genutzt, um Datenbankanfragen automatisch in äquivalente, effizienter auszuwertende Anfragen umzuwandeln. In diesem Projekt sollen Methoden zur Optimierung von Anfragen an semistrukturierte Daten und Datenströme entwickelt und experimentell auf ihre Praxistauglichkeit hin überprüft werden. Dabei soll auch untersucht werden, inwieweit Schema-Informationen, d.h. Informationen über die Struktur der Daten, genutzt werden können, um Anfragen effizient zu bearbeiten. Die Arbeitsgruppe Logik und Datenbanktheorie wird von der Deutschen Forschungsgemeinschaft (DFG) im Rahmen des Aktionsplans Informatik unterstützt. |
|
Leitung:
Prof. Dr. Nicole Schweikardt Sekretariat: Birgit Eisenmann Wissenschaftlicher Mitarbeiter: Dipl.-Inf. André Hernich Studentische Hilfskraft: André Böhm |
|
André Hernich
Nicole Schweikardt |
|
SoSe 2007:
Übung Logik und Komplexität (montags 15-17 Uhr in Raum 1'305, Erwin Schrödinger-Zentrum) Mitarbeiterseminar Logik in der Informatik (i.d.R. freitags, 11-13 Uhr, Raum 4.410, Johann von Neumann-Haus) Oberseminar Theoretische Informatik (i.d.R. freitags, 13-15 Uhr, Raum 3.101, Johann von Neumann-Haus) |
|
|
Besuchsadresse: Johann von Neumann-Haus Raum 4.426 (Haus 4, 4. Stock) Rudower Chaussee 25 12489 Berlin (Adlershof) Anfahrtskizze |