Ontologie-basierte Abfragen in Graph-Datenbanken

Um die stetig steigende Komplexität von Daten in modernen Software-Anwendungen handzuhaben, sind traditionelle Datenbankschemata nicht immer geeignet. Graph- Datenbanken und Description Logics (DLs) als sich ergänzende Werkzeuge erlauben hingegen auch lose gekoppelte Information adäquat abzulegen und zu verarbeiten. So werden Ontologien verwendet, um zum Beispiel Wissen in einer gegebenen Anwendungsdomäne in einem maschinen-lesbaren Format zu nutzen. Dieses Wissen kann wiederum mittels sogenannter Ontology-mediated Queries (OMQs) explizit gemacht werden, wobei die Abfragen hier nicht ausschließlich über die vorhandenen Daten, sondern mittels geeigneter Schlussverfahren, die sich durch die Ontologie ergeben, ausgewertet werden. Obwohl sich OMQs und Abfragen über Graph-Datenbanken durch viele Gemeinsamkeiten auszeichnen, gibt es doch fundamentale Unterschiede, die in diesem Projekt überbrückt werden sollen. So wird zum Beispiel in OMQs mit der sogenannten open-world assumption (Daten können unvollständig sein und müssen dementsprechend verarbeitet werden) gearbeitet, während in Graph-Datenbanken die closed-world assumption (Daten sind vollständig, alles was nicht gespeichert ist, ist daher falsch) herangezogen wird. Da beide Annahmen für sich gesehen oft zu restriktiv sind, sollten NutzerInnen die Möglichkeit haben, jene Daten, für die die open- bzw. closed-world assumption gelten soll, zu spezifizieren. Weiters vermisst man bei OMQs Features zur Navigation innerhalb einer Abfrage wie sie für Graph-Datenbanken und anderen semi-strukturierten Datenbanken gängig sind (z.B. in XPath oder SPARQL). In diesem Projekt sollen solche Erweiterungen für Standard-OMQs vorgestellt und untersucht werden. Insbesonders sollen passende Kombinationen von open- und closed-world assumption für OMQs, sowie Features zur Navigation in OMQs untersucht werden. Dabei sollen Resultate zu folgenden Aspekten erzielt werden: - Die Ausdrucksstärke der vorgeschlagenen OMQs soll mit jener von klassischen Datenbankabfragesprachen verglichen werden. Zu diesem Zweck werden Übersetzungen in passende DATALOG-Varianten erstellt. Somit können auch DATALOG-Systeme zur Auswertung von OMQs herangezogen werden. - Es soll weiters eine umfassende Komplexitätsanalyse durchgeführt werden, insbesonders für Entscheidungsprobleme wie query containment und query emptiness. Das Verständnis dieser Probleme ist zentral für Methoden zur Query-Optimierung.

Moderne Software Anwendungen müssen auf immer komplexere Daten effektiv zugreifen können, auch wenn solche Daten nicht fixen Schemata folgen wie dies in traditionellen Datenbankanwendungen der Fall ist. Beschreibungslogiken (auf Englisch "description logics") und Graphdatenbanken stellen nützliche aber komplementäre Werkzeuge bereit, um lose strukturierte Daten handhaben zu können. Die meisten wissenschaftlichen Ergebnisse die aus diesem Projekt resultierten beschäftigten sich mit neuen Datenmanagement und Zugriffsmethoden, welche sich die positiven Eigenschaften dieser beiden Bereiche zu Nutze machen. Zum Beispiel, auf Basis von Beschreibungslogiken gibt es so-genannte Ontologie-vermittelte Anfragen (auf Englisch "ontology-mediated query", abk. OMQ), welche Domänen-spezifisches Wissen, ausgedrückt als eine Ontologie, ausnutzen um automatisierte Beweisführung zu ermöglichen. Dies kann dann wiederum verwendet werden um erweiterten Zugriff auf (möglicherweise unvollständige) Daten zu bewerkstelligen. Im Gegensatz dazu, ermöglichen Graphdatenbanken die Verwendung von komplexeren Anfragen, als jene die in Beschreibungslogiken erlaubt sind. Insbesondere unterstützen Graphdatenbanken Anfragen mit Rekursion. Zusätzlich zur Differenz in der Ausdrucksstärke der erlauben Anfragen, machen die beiden Bereiche auch unterschiedliche Annahmen über die darunterliegenden Daten. Um die positiven Eigenschaften beider Bereiche zu verbinden, müssen wir also diese unterschiedlichen Annahmen in Einklang miteinander bringen. Dieses Projekt führte zu signifikanten Beiträgen zu den logischen Grundlagen zur Handhabung und Evaluierung von strukturierten Graphdaten mit der Hilfe von Beschreibungslogiken, und hat dadurch geholfen eine Brücke zu Schlagen zwischen Beschreibungslogiken und Graphdatenbanken. Unsere Hauptergebnisse können wir folgt zusammengefasst werden: - Wir erarbeiteten eine Reihe von Übersetzungen von OMQs zu passenden Varianten von Datalog, einer klassischen Anfragesprache im Bereich der Datenbanktheorie. Die Existenz solcher Übersetzungen war vor unserer Arbeit nicht bekannt, und hat gezeigt das klassische Anfragesprachen die neueren und scheinbar mächtigeren OMQs auch bündig ausdrücken können. - Wir haben neue logik-basierte Formalismen vorgestellt im Bereich von Datenmanagement: (im Originalnamen) "Resilient Logic Programs", "Clopen Knowledge Bases" und "Triguarded Fragment". Zusätzlich haben wir auch ihre Eigenschaften im Bereich der Semantik und Berechenbarkeit analysiert. - Wir haben neue Methoden vorgestellt um Anfragen über strukturierte Graphdaten zu ermöglichen. Zum Beispiel, wir haben ein Framework für OMQs mit bedingungsabhängigen Antworten der Anfrage vorgestellt. Diese erlauben ausdrucksstärkere und flexiblere Formulierungen von Anfragen durch Benutzer. Ein anderes Beispiel ist ein Framework und die grundlegenden Ergebnisse für eine interaktive Erkundung von Daten durch OMQs. - Wir habe die theoretischen Grundlagen des W3C SHACL Standards analysiert. Dies ist ein neuer Standard welches helfen soll die Qualität von strukturierten Graphdaten im Internet zu erhalten. Wir haben eine neue Interpretation (auch "Semantik") für rekursive SHACL Integritätsbedingungen vorgeschlagen, welches eine wichtige Lücke im ursprünglichen W3C Standard adressiert. Wir glauben dass unsere Arbeit wahrscheinlich zukünftige Revisions des W3C Standards zu SHACL beeinflussen wird.