Informatik, TU Wien

OCG Förderpreis 2007 geht an eine Absolventin der Fakultät für Informatik

Maria Magdalena Ortiz de la Fuente vom Institut für Informationssysteme, Arbeitsbereich Knowledge Based Systems wurde mit dem OCG Förderpreis 2007 ausgezeichnet.

Die Auszeichnung

Maria Magdalena Ortiz de la Fuente erhielt den Förderpreis der Oesterreichischen Computergesellschaft (OCG) für ihre Diplomarbeit über die Abfragebeantwortung in ausdrucksstarken Beschreibungslogiken (Query Answering in Expressive Description Logics).

Der Preis, ein Scheck in Höhe von € 2.000,-, wurde am 22. November im Rahmen des epilog von Frau Univ. Prof. Gerti Kappel als Vertreterin der OCG-Jury und dem Präsitenten der OCG Univ. Prof. Gerald Futschek überreicht.

Über ihre Arbeit

Im Semantic Web und in vielen anderen Bereichen werden Ontologien verwendet, um die Struktur des Wissens in einem bestimmten Bereich (einer Domäne) zu beschreiben. Sie werden auch in zunehmendem Maße als Mechanismus gesehen, um auf Datenbestände zuzugreifen und diese abzufragen, wobei Wissen über die Domäne, das in einer Ontologie dargestellt ist, herangezogen wird. Das World-Wide-Web Consortium (W3C) hat die /Web Ontology Languages /(OWL, OWL-DL, OWL-Lite) als Standardsprachen für Ontologien im Web festgesetzt.

Nachdem Beschreibungslogiken (Description Logics) die formalen Grundlagen für OWL-DL und OWL-Lite sind, ist die Entwicklung von Algorithmen zur Abfragebeantwortung in Beschreibungslogiken ein wichtiges Forschungsthema geworden. In dieser Arbeit wurde ein Algorithmus für SQL-ähnliche Abfragen in einigen sehr ausdrucksstarken Beschreibungslogiken entwickelt, die sehr eng mit OWL verbunden sind.

Ein weiterer Hauptbeitrag der Arbeit betrifft die Berechnungskomplexität von Abfragen in Beschreibungslogiken.

Nach dem Standard-Komplexitätsmaß ist bereits die Beantwortung von einfachen Abfragen in OWL im allgemeinen ein sehr aufwändiges Problem, das exponentielle Rechenzeit und auch exponentiellen Speicherplatz erfordert. Anstelle dessen wird die Daten-Komplexität betrachtet, der die Idee zugrunde liegt, dass das Datenvolumen üblicherweise viel größer ist als das Schema, welches die Daten beschreibt.

Es wurde bewiesen, dass die Beantwortung von SQL-ähnlichen Abfragen in den Beschreibungslogiken, die den OWL Sprachen zugrunde liegen, ein coNP-vollständiges Problem gemessen in der Daten-Komplexität ist und damit die gleiche Komplexität hat wie in viel einfacheren Formalismen, die weit weniger ausdrucksstark als die Beschreibungslogiken hinter den OWL Sprachen sind.