Please use this identifier to cite or link to this item: https://hdl.handle.net/10955/1138
Full metadata record
DC FieldValueLanguage
dc.contributor.authorVeltri, Pierfrancesco-
dc.contributor.authorLeone, Nicola-
dc.contributor.authorTerracina, Giorgio-
dc.date.accessioned2017-03-16T11:12:58Z-
dc.date.available2017-03-16T11:12:58Z-
dc.date.issued2012-11-11-
dc.identifier.urihttp://hdl.handle.net/10955/1138-
dc.identifier.urihttp://dx.doi.org/10.13126/UNICAL.IT/DOTTORATI/1138-
dc.descriptionDottorato di Ricerca in Matematica ed Informatica, Ciclo XXV, a.a. 2011-2012en_US
dc.description.abstractOntologies and rules play a central role in the development of the Semantic Web. Recent research in this context focuses especially on highly scalable formalisms for the Web of Data, which may highly benefit from exploiting database technologies. In particular, Datalog∃ is the natural extension of Datalog, allowing existentially quantified variables in rule heads. This language is highly expressive and enables easy and powerful knowledge-modeling, but the presence of existentially quantified variables makes reasoning over Datalog∃ undecidable, in the general case. The results in this thesis enable powerful, yet decidable and efficient reasoning (query answering) on top of Datalog∃ programs. On the theoretical side, we define the class of parsimonious Datalog∃ programs, and show that it allows of decidable and efficiently-computable reasoning. Unfortunately, we can demonstrate that recognizing parsimony is undecidable. However, we single out Shy, an easily recognizable fragment of parsimonious programs, that significantly extends both Datalog and Linear Datalog∃. Moreover, we show that Shy preserves the same (data and combined) complexity of query answering over Datalog, although the addition of existential quantifiers. On the practical side, we implement a bottom-up evaluation strategy for Shy programs inside the DLV system, enhancing the computation by a number of optimization techniques. The resulting system is called DLV∃– a powerful system for answering conjunctive queries over Shy programs, which is profitably applicable to ontology-based query answering. Moreover, we design a rewriting method extending the well-known Magic-Sets technique to any Datalog∃ program. We demonstrate that our rewriting method preserves query equivalence on Datalog∃, and can be safely applied to Shy programs. We therefore incorporate the Magic- Sets method in DLV∃. Finally, we carry out an experimental analysis assessing the positive impact of Magic-Sets on DLV∃, and the effectiveness of the enhanced DLV∃ system compared to a number of state-of-the-art systems for ontologybased query answering.en_US
dc.description.sponsorshipUniversità della Calabriaen_US
dc.language.isoenen_US
dc.relation.ispartofseriesINF/01;-
dc.subjectInformaticaen_US
dc.subjectWeb semanticoen_US
dc.titleDatalog with existential quantifiers: an optimal trade-off between expressiveness and scalabilityen_US
dc.typeThesisen_US
Appears in Collections:Dipartimento di Matematica e Informatica - Tesi di Dottorato

Files in This Item:
File Description SizeFormat 
Thesis_Veltri.pdf999,66 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.