Autore: Alessandro Ronca
Relatore: Maurizio Lenzerini
Università: Università degli Studi di Roma “La Sapienza”
Facoltà: Facoltà di Ingegneria dell’Informazione, Informatica e Statistica
Corso: Laurea Magistrale in Ingegneria Informatica
Data di Discussione: 23/10/2015
Voto: 110 cum laude
Tipo di Tesi: Ricerca
Altri Relatori: Bernardo Cuenca Grau, Ian Horrocks
Grande Area: Area Scientifica
In Collaborazione con: University of Oxford
Settori Interessati: Informatica, Intelligenza Artificiale, Gestione dei dati
In this thesis we address the problem of conjunctive query answering in expressive ontology languages. Even tough the problem is intractable,there are some approaches which have shown to perform well in practice.
Among them we have the pay-as-you-go approach, which seeks scalability by delegating the most of the work to a datalog reasoner and achieves completeness by employing a fully-fledged reasoner for the language of interest, which is used as a last resort. The core of the approach exploits the datalog reasoner for computing a lower and an upper bound of the set of answers, which identify the set itself if they coincide. The approach is implemented in the PAGOdA system. A comprehensive evaluation has shown that PAGOdA is competitive with a number of state-of-the-art systems. However there are inputs for which it needs time-consuming calls to the fully-fledged reasoner.
Starting from the analysis of such inputs, we design a novel algorithm for computing an upper bound of the set ...