A compilation technique for interactive ontology-mediated data exploration

Abstract

Ontologien haben sich in den letzten Jahren zu einem wichtigen Mittel für das gemeinsame Verständnis von Ressourcen zwischen verschiedenen Nutzern und Anwendungen entwickelt. Eine ihrer wichtigsten Anwendungen ist Ontologiebasierter Datenbangkzugriff (engl. Ontology-based Data Access, OBDA), wobei Ontologien die Rolle von Schnittstellen zu Datenquellen einnehmen, welche eine abstrahierte Konzeptansicht der Daten darstellen und Hintergrundwissen für das automatische Schließen zum Abfragezeitpunkt verfügbar machen. Die meiste Forschung in diesem Bereich fokussiert sich auf die Bereitstellung von Algorithmen für die sequentielle Beantwortung einzelner Abfragen. Fortgeschrittene Systeme, welche die Analyse von Daten durch Modifikation von Anfragen und Untersuchung ihrer Antworten ermöglichen, werden im Bereich relationaler Datenbanken als selbstverständlich angesehen, im Kontext von OMQA sind diese jedoch noch weit von den derzeit verfügbaren Beantwortungsmöglichkeiten entfernt. In dieser Arbeit machen wir einen ersten Schritt in Richtung interaktiver Exploration von Daten im Kontext von Ontologie-vermittelten Datenbankabfragen. Wir führen eine Technik zur Offline-Zusammenstellung ein, welche die effiziente Beantwortung verschiedener Variationen einer Familie von Abfragen zur Laufzeit erlaubt, ohne auf die ursprüngliche Datenquelle zurückgreifen zu müssen. Wir betrachten in DL-Lite formalisierte Ontologien und fokussieren uns auf konjunktive Anfragen (engl. conjunctive queries, CQ), die eine Baumstruktur und eine Antwortvariable besitzen. Die Zusammen- stellungsphase hat als Eingabe zwei Abfragen, welche die Informationen des Nutzers von oben und unten beschränken, und es zur Abfragezeit erlaubt, zwischen allen Abfragen (der erwähnten Form) innerhalb dieser beiden Schranken zu navigieren. Wir schlagen auch Algorithmen vor, die relevante Variationen der gegebenen Anfrage konstruieren, die dem Nutzer helfen können die Daten zu analysieren, z.B. indem sie die Anzahl der Antworten auf minimale Weise erweitern oder reduzieren, oder gemeinsame Eigenschaften aller Objekte in der Antwort zu einer gegebenen Anfrage identifizieren. Die mit unserer Prototyp-Implementierung durchgeführten Versuche zeigen insgesamt eine gute Leistung in Bezug auf die Anfragenbeantwortungsprozedur, und scheinen vor allem ein vielversprechender erster Schritt in Richtung einer flexiblen Ontologie-vermittelten Datenexploration zu sein.

Ontologies have been extensively advocated in the last decade as a means to enable a shared understanding of resources between different users and applications. One of their championed applications is Ontology-based Data Access (OBDA), where ontologies mediate access to data sources, providing a high-level conceptual view of the data and making background knowledge available for reasoning at query time. Much research efforts in the last years have been dedicated to the core problem in OBDA: answering a query while leveraging the knowledge given by an ontology, sometimes called ontology mediated query answering (OMQA). However, most work focuses on providing algorithms for answering queries one-at-a-time. Advanced systems that allow to analyze data by making modifications to queries and exploring their answers are taken for granted in the setting of standard relational databases, but in the setting of OMQA they still seem very far away from the primitive querying capabilities currently available. In this thesis, we make a first step towards the interactive exploration of data in the ontology-mediated setting. We introduce a technique to construct an offline compilation that allows for efficiently answering different variations of a family of queries on the online phase, without the need to access the original data source. We consider ontologies formalized using DL-Lite, and focus on conjunctive queries (CQs) that are tree-shaped and have one answer variable. The compilation phase takes as input two queries that bound the information needs of the user from above and below, and then in the online phase, it allows to navigate between all the queries (of the mentioned restricted form) that fall between these two bounds. We also propose algorithms that construct relevant variations of a given query that may help the user analyze the data by, for example, reducing or increasing the number of answers in a minimal way, or identifying common properties of all objects that are in the answer to a given query. The experiments carried out with our prototype implementation reveal an overall good performance of the query-answering procedure and, most importantly, seem to be a promising first step towards flexible ontology-mediated data exploration.