Incremental Recomputation of Pig Latin’s Nest and Unnest Operators

This master’s thesis addresses the maintenance of pre-computed structures, which store a frequent or expensive query, for the nested bag data type in the high level work-flow language Pig Latin. This thesis defines a model suitable to accommodate incremental expressions over nested bags on Pig Latin. Afterwards, the partitioned normal form for sets is extended with further restrictions, in order to accommodate the nested bag model, allow the Pig Latin nest and unnest operators revert each other, and create a suitable environment to the incremental computations. Subsequently, the extended operators – extended union and extended difference – are defined for the nested bag data model with the partitioned normal form for bags (PNF Bag) restriction, and semantics for the extended operators are given. Finally, incremental data propagation expressions are proposed for the nest and unnest operators on the data model proposed with the PNF Bag restriction, and the proof of correctness is given.

Esta tese de mestrado aborda a problemática da manutenção de estruturas pré-cumputas, que – regra geral – armazenam uma pesquisa computacionalmente dispendiosa ou frequente, para a linguagem de fluxo de dados de alto nível Pig Latin. Esta tese começa por definir um modelo de dados para acomodar o tipo de dados nested bag do Pig Latin. Posteriormente a partitioned normal form para sets ´e transformada para poder: acomodar o tipo de dados nested bag, permitir que os operadores do Pig Latin nest e unnest possam reverter-se mutuamente, e para criar um ambiente propicio `a utilização de expressões incrementais. De seguida os operadores extendidos – extended union e extended difference – são definidos para o modelo nested bag com a restrição partitioned normal form para bags (PNF Bag), sendo a semântica dos operadores também dada nesta tese. Por fim, são propostas expressões incrementais de propagação da informação para os operadores nest e unnest no modelo proposto com a restrição PNF Bag.