Restruturação dinâmica de estruturas multidimensionais de dados em tempo útil

Abstract

O crescimento do tamanho dos Data Warehouses e do número dos utilizadores impuseram um stresse sucessivamente crescente nos sistemas de processamento analítico. Desde cedo se percebeu que a materialização de estruturas multidimensionais era uma forma de melhorar o tempo de resposta a interrogações de carácter agregado. Também a distribuição dessas estruturas podia ser uma mais-valia para aliviar o problema, permitindo uma escalabilidade a custos controlados, maior disponibilidade e eliminação de pontos-quentes. Mas estas soluções não são de implementação simples. Se a selecção das estruturas multidimensionais apropriadas se constitui como um problema NP-hard, a segunda vertente vem aumentar ainda a complexidade da primeira, uma vez que incorpora na equação de custos uma dimensão adicional – espaço – gerando novas dependências, cujas semânticas são capturadas pelo lattice distribuído. Já não se trata apenas de seleccionar as estruturas mais adequadas, considerando um perfil de carga, mas também materializá-las no(s) nó(s) mais vantajoso(s). Transversal a esta dupla abordagem da solução está uma outra dimensão, sempre omnipresente – o tempo – implicando o “envelhecimento” de cada solução proposta e a necessidade da sua afinação periódica. Esta dissertação surge assim na confluência das três problemáticas aludidas: a selecção das estruturas multidimensionais, a sua possível distribuição e a temporalidade de recalibração. A solução para esta tripla abordagem implicou: 1) a evolução de modelos já existentes, mas estendidos para incorporar a dimensão espaço com os seus custos de comunicação, heterogeneidade das redes de interligação dos nós da arquitectura e respectiva capacidade de processamento; 2) a concepção de algoritmos para a estimativa de custos, capazes de simular a execução paralela de tarefas (típica ao dispor-se de diversos nós de armazenamento e processamento); 3) a proposta de novas heurísticas para a solução do problema ou melhoria de propostas já existentes. Em resultado da investigação empreendida, desenvolveu-se o núcleo de um protótipo de uma ferramenta para a administração de data warehouses, na forma de um conjunto de algoritmos que permitem empreender a optimização das estruturas multidimensionais de dados supondo uma qualquer distribuição espacial das estruturas e nós arquitecturais. Esta ferramenta constitui-se como uma bancada de trabalho pois foi concebida de forma a possibilitar investigação futura e suportar evoluções sucessivas e a sua inclusão num sistema de gestão global de um sistema de data warehousing.

The increasing size of data warehouses and the number of users imposed a succeeding stress on the OLAP systems. From early times, it was perceived that the materialization of multidimensional structures was a way of improving the answering time of those systems to aggregated queries. Moreover, the distribution of those structures could be another way to deal with that problem, allowing scalability with controlled costs, a better availability and bottleneck avoidance. But these solutions aren’t of easy implementation. If the proper selection of the multidimensional structures is a NP-hard problem, yet the other prospect increases the complexity of the problem, as it implies the inclusion of a new dimension – space – into the costs’ equation, generating new dependencies, whose semantics are captured by the distributed cube lattice. Now, we have to deal not only with the selection of the most profitable multidimensional structures, but also to materialize them into the most advantageous node(s). A new dimension transverses this double solution’s approach – time – implying the “aging” of each proposed solution and the need to a periodic tuning. This dissertation emerges in the confluence of the mentioned triple points: the selection of the multidimensional structures, its possible distribution and the timing of recalibration. The solution for this triple approach implied: 1) the evolution of existent cost models, now extended to include the space dimension with its communication costs, the heterogeneity of nodes’ interconnecting networks and the processing power of the OLAP server nodes; 2) the design of cost estimation algorithms, which are able to simulate the parallel execution of tasks (a typical situation, having several storage and processing nodes); 3) the proposal of several new approximate optimizing algorithms or the improving of pre-existent proposals applied to the optimization of the multidimensional structures. This research allowed the development of a prototype’s core tool for data warehouses administration, shaped as a set of algorithms which allows making the optimization of the multidimensional data structures, supposing any spatial distribution of the architectural structures and nodes. This tool is just like a workbench, as it was designed in order to allow the future research work and the easy support of succeeding evolutions and also its inclusion into a global data warehousing management system.