Risoluzione efficiente di interrogazioni XPath su documenti XML con attributi e riferimenti

Introduzione Obiettivo di questa tesi di laurea e` la realizzazione di un algoritmo efficiente per la risoluzione di interrogazioni XPath su documenti XML con attributi e riferimenti. Il linguaggio XPath e` un linguaggio che consente di ricercare elementi all’interno di un documento XML. Nel corso di questi ultimi anni sono stati proposti diversi algoritmi per la risoluzione di interrogazioni XPath, ma non tutti risultano essere efficienti in termini di velocita` di esecuzione. Nell’articolo ”Efficient Algorithms for Processing XPath Queries” [1] dei ricercatori Georg Gottlob, Christopher Koch e Reinhard Pichler e pubblicato nel 2002 negli atti della conferenza Very Large DataBases 2002, viene messa in evidenza l’inefficienza di alcune famose implementazioni di XPath come XALAN, XT e IE6, addirittura con fattori di complessita` computazionale addirittura esponenziali. Gli stessi Gottlob, Koch e Pichler dimostrano, nello stesso articolo, che sia pos- sibile risolvere in maniera efficiente un sottoinsieme del linguaggio XPath con un fattore di complessita` computazionale al piu` lineare. L’idea che ha ispirato la presente tesi di laurea e` stata quindi quella di provare ad ampliare i risultati ottenuti nell’articolo suddetto, su un sottoinsieme piu` ampio di XPath, che comprendesse documenti con attributi e riferimenti. Oltre alla realizzazione teorica dell’algoritmo si e` quindi pensato di implementarlo su di un calcolatore al fine di verificarne l’efficienza tramite alcuni test su documenti XML di diverse dimensioni. Oltre ai test di efficienza, e` stato poi eseguito un confronto con un processore di interrogazioni noto nella comunita` scientifica e idoneo a valutare la bonta` del lavoro svolto. 3