Sulla Computazione Parallella Dichiarativa: Modelli, Linguaggi e Semantica

If we put under analysis the plethora of large-scale data-processing tools avail- able nowadays, we can recognize two main approaches: a declarative approach pursued by parallel DBMS systems and firmly grounded on the relational model theory; and an imperative approach followed by modern data-processing “MapReduce-like” systems which are highly scalable, fault-tolerant, and mainly driven by industrial needs. Although there has been some work trying to bring together the two worlds, these works focus mainly on exporting languages and interfaces – i.e., declarative languages on top of imperative systems, or MapReduce-like functions over parallel DBMS – or in a systematic merging of the features of the two approaches. We advocate that, instead, a declarative imperative approach should be attempted: this is, the development of a new computational model with related language, based on the relational theory and following the same patterns commonly present in modern data-processing systems, while maintaining a declarative flavor. The goal of this thesis is then to carry out a first step in this direction. More concretely, we developed a new synchronous computational model for relational distributed parallel data-processing, leveraging on previous works on relational transducers and transducer networks. Such computational model accepts declarative program specifications expressed in a version of Datalog¬ specifically tailored for parallel computation. Datalog¬ is a language lying in between logic and query languages and, thanks to its nature, not only data-driven parallel computation can be declarative expressed, but also the theoretical foundations connecting the semantics of programs with the emerging properties of their parallel execution can be explored.

Se mettiamo sotto analisi la pletora di strumenti per l’elaborazione di dati di gran- di dimensioni disponibili al giorno d’oggi, possiamo riconoscere due approcci principali: un approccio dichiarativo perseguito da sistemi DBMS paralleli e saldamente fondato sul modello relazionale, e un approccio imperativo seguito dai moderni sistemi di elaborazione di dati “MapReduce -like”, i quali sono altamente scalabili, fault-tolerant, e il cui sviluppo e` trainato principalmente da necessita` industriali. Nonostante esistano un certo numero di proposte che hanno tentato di unificare i due mondi, questi lavori si concentrano principalmente nell’esportazione di linguaggi e interfacce – linguaggi dichiarativi su sistemi imperativi, o funzioni MapReduce-like su DBMS paralleli – oppure in una fusione sistematica delle caratteristiche dei due approcci. Noi sosteniamo che un approccio dichiarativo-imperativo debba invece essere tentato: cioè lo sviluppo di un nuovo modello di calcolo, e relativo linguaggio, basati sul modello relazionale e che seguano gli stessi pattern comunemente presenti nei moderni sistemi di elaborazione di dati, pur mantenendo una base dichiarativa. L’obiettivo di questa tesi e` quindi quello di effettuare un primo passo in questa direzione. Più concretamente, abbiamo sviluppato un nuovo modello di calcolo sincrono per l’elaborazione distribuita e parallela di dati, prendendo spunto da precedenti lavori su relational transducers e transducer networks. Tale modello computazionale accetta come input specifiche espresse in una versione di Datalog¬ appositamente pensata per il calcolo parallelo. Datalog¬ e` un linguaggio che giace tra la logica e i linguaggi di interrogazione e, grazie alla sua natura, siamo stati in grado non solo di esprimere in modo dichiarativo calcolo parallelo data-driven, ma anche di esplorare le fondamenta teoriche che collegano la semantica dei programmi con le proprietà emergenti della loro esecuzione parallela.