National Technical University of Athens (NTUA)
Βελτιστοποιημένοι αλγόριθμοι επαναγραφής ερωτημάτων για εκφραστικές περιγραφικές λογικές
Abstract
dc:descriptionAn important approach to query answering over OWL ontologies is via rewritingthe input ontology and query into a new set of axioms that are expressed inlogics for which scalable query answering algorithms exist. This approach has beenstudied for many important fragments of OWL like OWL 2 QL, OWL 2 EL, as well as Horn-SHIQ and SHIQ. An important family of rewriting algorithms arethe resolution-based ones, mostly due to their ability to adapt to any ontologylanguage and the long years of research in resolution theorem-proving. However,this generality comes with performance prices.In the current work we revisit and refine the resolution approaches in orderto design efficient rewriting algorithms for many important fragments of OWL 2.The underlying idea of our algorithms is to apply a resolution-based strategy thattakes into account the specific structure of the axioms supported by each language. First, we present an algorithm for the language DL-Lite, which is strongly relatedto OWL 2 QL. Our calculus is restricted so that it avoids performing manyunnecessary inferences, one of the main problems of these algorithms. Subsequently, we extend our algorithm to the language ELHI which is strongly related to OWL 2 EL. This is a difficult task as ELHI is an expressive language, however, weshow that the calculus for DL-Lite requires relatively small extensions. Finally, weextend our calculus for the very expressive language Horn-SHIQ. By followingthe same approach as in the case of ELHI, our calculus takes into account thecomplex axioms interactions in order to restict the resolution rules application.We have implemented our algorithms and we have conducted an extensive experimental evaluation using many well-known large and complex OWL ontologies.This is the first evaluation of rewriting algorithms of this magnitude. In the case ofDL-Lite and ELHI ontologies our results show that our system is in many casesseveral orders of a magnitude faster than several sofisticated rewriting systems.Similarly, in the case of Horn-SHIQ ontologies, our system greatly outperformsthe only available rewriting system for Horn-SHIQ.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2015
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Trivela, Despoina
- Τριβέλα, Δέσποινα
Subjects
dc:subject × 10Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/37148