Optimização de estruturas multidimensionais de dados em ambientes OLAP

Abstract

A evolução dos sistemas de Data Warehousing em dimensão e utilização impôs uma agitação contínua sobre os sistemas de processamento analítico. A materialização de estruturas multidimensionais de dados é, desde à muito, vista como uma forma de optimizar o tempo de resposta às interrogações de natureza agregada. Para além da temporalidade, é necessário considerar uma outra perspectiva: o espaço necessário para armazenar todas as agregações calculadas. Na prática, o problema da selecção de estruturas multidimensionais de dados traduz-se principalmente na escolha das vistas que mais evidenciam a diminuição dos custos de manutenção e consulta, tendo em consideração os subcubos (ou cubóides) mais vantajosos para responder às interrogações dos utilizadores. A proporção da relação tempo/espaço é reconhecida como um problema NP-hard. De facto, muitos sistemas de suporte à decisão efectuam o pré-processamento das estruturas multidimensionais de dados de modo a optimizarem o tempo de resposta às consultas efectuadas pelos agentes de decisão. Contudo, a materialização integral dos subcubos é praticamente inexequível quando confrontada com a elevada dimensionalidade e cardinalidade, intrínsecas à complexidade dos sistemas multidimensionais modernos, para além das suas exigências conhecidas ao nível do tempo e do espaço. A materialização parcial representa, por outro lado, um interessante trade-off entre o espaço de armazenamento e o tempo de pré-processamento de vistas. Neste domínio são analisadas algumas técnicas para optimizar a selecção de estruturas multidimensionais de dados, denominadas “icebergue”, como resposta à reformulação do problema de materialização integral de vistas. Na sua essência, estes algoritmos calculam apenas as células agregadas das estruturas de dados que satisfazem uma determinada condição, com o objectivo de identificar os valores que farão sentido considerar nas análises de suporte à decisão, qualificando apenas as agregações com mais significado analítico e, portanto, as que devem ser materializadas. Em resultado da investigação efectuada, são analisados diferentes algoritmos de selecção de estruturas multidimensionais de dados, dando especial ênfase às lógicas de selecção icebergue. Para além da caracterização multidimensional (em tempo e espaço) das soluções propostas, são identificadas as suas vantagens mais predominantes e quais os pontos mais delicados que devem merecer especial atenção.

The Data Warehouse evolution in size and use imposed a continuous frenzy on the OLAP systems. The materialization of multidimensional data structures is, from early times, a way of improving the answering time of those systems to aggregated queries. In addition to time, it’s necessary to consider another perspective: the space required to store all the calculated aggregates. In practice, the multidimensional data structures selection problem is mostly related with views selection that mainly reveals a decrease of interrogation and maintenance costs, according the variety of cuboids more useful to answer any inquires made by users. The proportion time/space is recognized as an NP-Hard problem. In fact, many decision support systems carry out multidimensional data structures pre-computing in order to optimize the answering time of the queries made by the decision makers. However, the computation of all the cuboids in a multidimensional data structure is nearly infeasible when confronted with high dimensionality and cardinality, inherit to the complexity of modern Data Warehouse and OLAP systems (in addition to its recognized requirements of time and space). On another hand, partial materialization offers an interesting trade-off between storage space and response time for materialized views pre-computation. In this work, we discuss some partial materialization techniques for improving computation and selection of the most valuable cuboids of a multidimensional data structure, knows as “iceberg” algorithms, in response to the full materialization views selection problem. In essence, these algorithms calculate only a fraction of the cells in a multidimensional data structure whose aggregate value is above some minimum support threshold, in order to identify the aggregates that make sense reflect in a decision support analysis (this scenario allows to describe only the aggregates with more analytical meaning and, therefore, those that would be materialized). As a result of this research, different algorithms are analyzed for the views selection problem, principally the “iceberg” selecting logics. As well as the multidimensional characterization (in time and space) of the proposed solutions, this work identifies their most revealing advantages and what are the mainly fragile points that deserve special attention.