Risposte efficienti alle queries migliorando l'efficienza di calcolo

Negli ultimi anni il web è diventato il principale strumento per lo scambio di informazioni. Un ruolo rilevante in questo contesto è svolto dal XML (eXtensible Markup Language), un linguaggio di markup, nato per uniformare il formato delle informazioni sul web, ma che presto si è affermato come linguaggio di interscambio di infor- mazioni rappresentate attraverso strutture ad albero. Per interrogare tali informazioni è necessario definire delle queries (parole chiave per effettuare ricerche in un database) usando un meccanismo che sia semplice ed espressivo: XPath. Esso permette di definire queries navigazionali, finalizzate a individuare specifiche pagine web, sui dati XML al fine di selezionare l'insieme dei modi di interesse per esse. Poiché XPath è utilizzato nei principali linguaggi di querying e gestione dei datiXML, il problema di ottenere delle risposte efficienti a queries-XPath ha riscosso interesse sia nella comunità scientifica che in campo applicativo. Un contributo alla problematica generale può derivare dall'utilizzo di un'espressione XPath di dimensione ridotte, che aumenterebbe l'efficienza di calcolo. L'ICAR-CNR ha studiato il problema per un frammento di XPath per il quale è ammesso l'uso dei più comuni operatori di manipolazione. Al frammento generale sono state applicate delle restri- zioni sintattiche. Questo consente una espressività che è superiore a quella delle queries congiuntive (le condizioni devono essere soddisfatte contemporaneamente) pur rimanendo inferiore a quella delle queries disgiuntive (le condizioni possono essere soddisfatte in alternativa), particolarmente costose dal punto di vista computazionale. Per tale frammento viene illustrata la possibilità di ottenere la minimizzazione di una query semplicemente rimuovendo parti non essenziali, senza la necessità di riformularla interamente. 

Authors: S. Flesca, F. Furfaro, E. Masciari

Title: On the minimization of XPath Queries

Journal: Journal of the ACM (JACM)

Year: 2008

References: ed. ACM, Vol. 55 (1), Article No. 2, 2008