Back to search

National Technical University of Athens (NTUA)

Βελτιστοποιημένοι αλγόριθμοι επαναγραφής ερωτημάτων για εκφραστικές περιγραφικές λογικές

Abstract

dc:description

An 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 × 10

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/37148

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Trivela, Despoina; Τριβέλα, Δέσποινα. Βελτιστοποιημένοι αλγόριθμοι επαναγραφής ερωτημάτων για εκφραστικές περιγραφικές λογικές. National Technical University of Athens (NTUA), 2015. http://hdl.handle.net/10442/hedi/37148