Query answering in the description logic Horn-SHIQ

Abstract

Ontologien werden verwendet, um mit einem formalen System ein bestimmtes Wissensgebiet zu repräsentieren. Diese Repräsentation ermöglicht computerbasierten Systemen, bestehendes Wissen zu verwenden, neues Wissen zu entdecken oder mit anderen Systemen dieses auszutauschen. Im Kontext von Datenbanksystemen kann durch Ontologien eine konzeptionelle Sicht auf die Datenbanken erstellt werden, die dann als Zugriffsmöglichkeit für Abfragen dienen kann. Um solche Ontologien zu definieren werden häufig Description Logics (DLs) verwendet, die auch die Basis der aktuellen Web Ontology Language (OWL) desWorld Wide Web Consortium (W3C) bilden. DLs sind eine Familie von Wissensrepräsentations-Sprachen mit unterschiedlicher formeller Ausdrucksstärke und Komplexität. Beim derzeitigen Stand der Forschung kommen nur "lightweight" DLs mit gering Komplexität in Frage, um große Datenmengen zu verarbeiten. Wir identifizieren als lightweight DLs DL-Lite, EL , und Horn DL, wobei DL-Lite die geringe Komplexität besitzt und aus dem Bereich der Datenmodellierung stammt. Für EL und DL-Lite bestehen für das "Query answering" bereits praktisch anwendbare Algorithmen, nur für Horn DLs fehlen solche Techniken bisher. Horn-SHIQ ist das Horn-Fragment der DL SHIQ, welche wiederum die Basis des OWL-Lite Standards bildet. Horn-SHIQ subsumiert EL und DL-Lite, aber durch das Fehlen eines praktisch anwendbaren Algorithmus die sprache noch nicht in einem DL System verwendet. In dieser Arbeit betrachten wir Horn-SHIQ und erarbeiten einen Algorithmus, der auf "Query Rewriting" basiert und konjunktive Anfragen auf Ontologien beantwortet.Wir zeigen für diesen Algorithmus die Korrektheit und Vollständigkeit. Zusätzlich implementieren wir den Algorithmus in einem Prototypen und evaluieren dessen PerformanzPerformanz mit bekannten Ontologien.<br />

Ontologies can be used to formally represent knowledge of an application domain. This enables machines to make use of the knowledge, to discover new knowledge, or to exchange knowledge with others. In the context of database systems, an ontology can be seen as the conceptual view over data repositories, and data can be accessed by query answering services. To build such ontologies, we need ontology languages. Among formalisms for ontology languages, Description Logics (DLs) are the most prominent ones. DLs underlie the foundation for the current Web Ontology Language (OWL) standard recommended by World Wide Web Consortium (W3C). DLs are a family of knowledge representation languages with different expressive capabilities and computational complexities. It seems that only lightweight languages i.e., language with low complexity, are suitable for applications dealing with a large amount of data. The first family of lightweight DLs is DL-Lite, specially designed to capture data modelling formalism while keeping very low complexity. The second collection of lightweight languages is the EL family. Both of these families are subsumed by the Description Logic Horn-SHIQ. Horn-SHIQ is the Horn fragment of the expressive Description Logic SHIQ underlying the OWL-Lite standard.<br />There exists practical algorithms for query answering in EL and DL-Lite but there is no such algorithms for Horn-SHIQ. In this thesis, we investigate this issue and propose a query rewriting-based approach for answering conjunctive queries over ontologies in Horn-SHIQ. Apart from providing a sound and complete algorithm, we have implemented a prototype system and performed experiments on well-known ontologies.