Parallel XPath query evaluator

Semi-structured data structures, such as JSON and XML, are widely used in many applications, from social networks, to financial applications and, within the web, are generated at a dizzying pace. In this document we will focus on the XML language and, in particular, on the parallel evaluation of XPath queries. Unlike other approaches described in the literature, we propose to pair the evaluation of a XPath query with the data parsing phase; the latter, in fact, can be parallelized thanks to an important formal property enjoyed by the XML language and, more generally, by all the Operator Precedence Languages, kwnon as local parsability property.

Le strutture dati semi strutturate, come JSON e XML, sono ampiamente utilizzate in molte applicazioni, dai social network alle applicazioni legate al mondo finanziario e, nell'ambito del web, sono generate ad un ritmo vertiginoso. In questo documento ci concentreremo sul linguaggio XML e, in particolare, sulla valutazione in parallelo di query XPath. A differenza di altri approcci descritti nella letteratura, proponiamo di accoppiare la valutazione di una query XPath con la fase di parsing del documento XML soggetto alla query; la fase di parsing del documento, infatti, può essere eseguita in parallelo grazie ad una importante proprietà formale di cui gode il linguaggio XML e, più in generale, di cui godono tutti i linguaggi a Precedenza di Operatori, nota come proprietà di parsabilità locale.