Tesi di Dottorato
Permanent URI for this communityTesi di Dottorato
Browse
2 results
Search Results
Item Dynamic magic sets(2010) Alviano, Mario; Lceone, Nicola; Faber, WolfgangDisjunctive Datalog with stable model semantics is a rule–based language for knowledge representation and common sense reasoning that also allows to use queries for checking the presence of specific atoms in stable models. Expressive- ness is a strength of the language, which indeed captures the second level of the polynomial hierarchy. However, because of this high expressive power, evalu- ating Disjunctive Datalog programs and queries is inherently nondeterministic. In fact, Disjunctive Datalog computations are typically characterized by two distinct phases. The first phase, referred to as program instantiation, is deter- ministic and associates input programs with equivalent ground programs; only deterministic knowledge is inferred in this phase. The second phase, referred to as stable model search, is nondeterministic and computes stable models of instantiated programs. Many query optimization techniques have been proposed in the literature. Among them are Magic Sets, originally introduced for standard Datalog pro- grams. Program instantiation is sufficient for computing the semantics of stan- dard Datalog programs because only deterministic knowledge can be represented in this case. For this reason, the original Magic Set technique is only focused on the optimization of program instantiation. Dynamic Magic Sets are an exten- sion of the technique that takes into account the nondeterministic knowledge encoded into Disjunctive Datalog programs. In fact, in addition to the standard optimization of program instantiation, Dynamic Magic Sets provide further op- timization potential to the subsequent stable model search. In this thesis, Dynamic Magic Sets are proved to be sound and complete for stratified and super–coherent programs. To this end, a strong relationship between magic atoms and unfounded sets is highlighted. Dynamic Magic Sets are also used for proving decidability of reasoning for a class of programs with uninterpreted function symbols. In particular, it is shown that the application of Dynamic Magic Sets to finitely recursive queries generates finitely ground programs, for which decidability of reasoning has been established in the liter- ature. Dynamic Magic Sets have been implemented in a prototype extending DLV, a state–of–the–art system for Disjunctive Datalog programs and queries. The effectiveness of Dynamic Magic Sets has been assessed by experimenting with the prototype system. Experimental results confirm that Dynamic Magic Sets can provide significant, possibly exponential, performance gains.Item Normal Form Nested Programs(2014-03-31) Bria, Annamaria; Faber, Wolfgang; Leone, NicolaNella Programmazione Logica Disgiuntiva (PLD) le regole sono costituite da una testa e da un corpo. La testa è una disgiunzione di atomi, mentre il corpo una congiunzione di letterali. La PLD, sotto la semantica degli Answer Set è ampiamente riconosciuta come importante strumento per la rappresentazione della conoscenza e del ragionamento non monotono. Lifschitz, Tang e Turner hanno esteso la semantica degli Answer Set (solo nel caso proposizionale o ground) ad una classe di programmi logici dove la testa e il corpo delle regole contengono espressioni innestate. Per espressioni innestate si intendono congiunzioni, disgiunzioni e negazione innestati arbitrariamente. Questa nuova classe di programmi è chiamata Programmi Logici Innestati e generalizza la classe dei programmi logici disgiuntivi proposizionali. Inoltre, è stato dimostrato che i programmi logici innestati possono essere trasformati in programmi logici disgiuntivi. Questi risultati ci permettono di valutare i programmi logici innestati usando i sistemi esistenti che supportano la PLD, come DLV, GnT, oppure Cmodels3. Si noti che le trasformazioni che consentono di ottenere i programma PLD introducono nuovi simboli e pertanto il programma risultante non è equivalente al programma originario nel senso classico. Ad ogni modo esiste una corrispondenza biunivoca tra gli answer set del programma innestato con gli answer set del programma trasformato. Sfortunatamente queste trasformazioni funzionano solo per programmi proposizionali e dunque non si possono usare le variabili, uno dei punti di forza dei programmi logici disgiuntivi. Questa limitazione diminuisce drasticamente l'applicabilità dei programmi logici innestati soprattutto quando il ragionamento è fatto su un numero molto grande di fatti. Una generalizzazione di queste tecniche a programmi che contengono variabili, non è ovvia. Per i programmi PLD l'indipendenza dal dominio è assicurata imponendo ai programmi delle condizioni sintattiche. Una di queste condizioni è nota come safety e per le regole PLD significa che ogni variabile che compare nella regola deve comparire anche in almeno un letterale positivo del corpo. Motivati da queste considerazioni, in questo lavoro di tesi estendiamo i programmi logici disgiuntivi non-ground ad una classe di programmi nei quali la testa delle regole è una formula in forma normale disgiuntiva composta da atomi, mentre il corpo è una formula in forma normale congiuntiva composta da letterali. Questi programmi sono chiamati programmi Normal Form Nested (NFN) e diversamente dai programmi logici innestati definiti da Lifschitz, Tang e Turner possono contenere variabili. In questo lavoro di tesi abbiamo studiato la semantica e la proprietà di indipendenza dal dominio e una trasformazione polinomiale dai programmi NFN ai programmi PLD, che preserva la safety. I principali contributi della tesi possono essere riassunti come segue. 1. Abbiamo esteso la DLP introducendo la congiunzione nella testa delle regole e la disgiunzione nel corpo delle stesse, ottenendo una nuova classe di programmi: i programmi NFN. 2. Abbiamo studiato le proprietà dei programmi NFN mostrando i seguenti risultati. a. Definita la Safety per i programmi NFN abbiamo dimostrato che ogni programma safe è indipendente dal dominio b. Gli answer set per i programmi NFN coincidono con gli answer set definiti da Lifschitz et al. per i programmi NLP, sul segmento del linguaggio comune. c. Gli answer set per i programmi NFN coincidono con i modelli stabili di Herbrand definiti da Ferraris et al. per le formule che corrispondono ai programmi NFN. d. Gli answer set per i programmi NFN coincidono con gli answer set per i programmi PLD definiti da Gelfond e Lifschitz. e. La nostra definizione di Safety per i programmi NFN è più generale di quella definita da Lee et al. sui programmi NFN. 3. Abbiamo progettato un algoritmo che trasforma i programmi NFN in programmi PLD in modo efficiente e abbiamo dimostrato che esso soddisfa importanti proprietà. a. La trasformazione preserva la safety. b. La taglia del programma trasformato è polinomiale nella taglia del programma NFN. c. Esiste una corrispondenza biunivoca tra gli answer set del programma NFN e quelli del programma riscritto. d. Abbiamo realizzato un sistema, nfn2dlp, che implementa l'algoritmo di riscrittura e un sistema che calcola gli answer set di un programma NFN: nfnsolve. Entrambi i tool sono disponibili al sito http://www.mat.unical.it/software/nfn2dlp/.; Università della Calabria