OCG-Förderpreis

OCG Förderpreis 2007: Die Gewinnerin steht fest

Die Jury wählte die Arbeit von Mag. Maria Magdalena Ortiz de la Fuente, TU Wien, über Abfragebeantwortung in ausdrucksstarken Beschreibungslogiken (Query Answering in Expressive Description Logics) zur besten Arbeit.

Der Preis, ein Scheck in Höhe von € 2.000,-, wurde von Frau Univ. Prof. Dr. Gerti Kappel und Univ. Prof. Dr. Gerald Futschek (im Bild mit der Preisträgerin) überreicht.

Zum Inhalt:

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.