Since the introduction of Data Warehouse (DW) and Online Analytical Processing (OLAP) technologies, efficient computation of data cubes has become one of the most relevant and pervasive problems in the DW area. The data cube operator has exponential complexity; therefore, the materialization of a data cube involves both huge amount of memory and substantial amount of time for its generation. Reducing the size of data cubes, without loss of generality, thus becomes one of the essential aspects for achieving effective OLAP services. Previous approaches reduce substantially the cube size using graph representations. A data cube can be viewed as a set of sub-graphs. In general, the approaches eliminate prefix redundancy and part of suffix redundancy of a data cube. In this work, we propose three major contributions to reduce the data cube size: MDAG, MCG and p-Cube Approaches. The MDAG approach eliminates the wildcard all (*), which represents an entire aggregation, from the cube representation, using the dimensional ID. It also uses the internal nodes to reduce the cube representation height, number of branches and number of common suffixed nodes. Unfortunately, the MDAG approach just reduces the data cube suffix redundancy, so in order to complete eliminate prefix/suffix redundancies we propose the MCG approach. The MCG approach produces a full cube with a reduction ratio of 70-90% when compared to a Star full cube representation. In the same scenarios, the new Star approach, proposed in 2007, reduces only 10-30%, Dwarf 30-50% and MDAG 40-60% of memory consumption when compared to Star approach. Our approaches are, on average, 20-50% faster than Dwarf and Star approaches. In this work, we also propose a parallel cube approach, named p-Cube. The p-Cube approach improves the runtime of Star, MDAG and MCG approaches, while keeping their low memory consumption benefits. The p-Cube approach uses an attribute-based data cube decomposition strategy which combines both task and data parallelism. It uses the dimensions attribute values to partition the data cube into a set of disjoint sub-cubes with similar size. The p-Cube approach provides similar memory consumption among its threads. Its logical design can be implemented in shared-memory, distributed-memory and hybrid architectures with minimal adaptation.

Abordagens para computação de cubos de dados utilizando a estratégia de índices invertidos, tais como Frag-Cubing, são alternativas eficientes em relação às tradicionais abordagens para computação de cubos de dados com alta dimensionalidade, entretanto tais abordagens são limitadas pela memória principal (RAM) disponível. Neste trabalho, é apresentadado duas abordgens iniciais: qCube e H-Frag. qCube é uma extensão da abordagem Frag-Cubing que possibilita consultas de intervalo e H-Frag é uma abordagem que utiliza memória principal e memória externa a partir de definições do usuário. Com base nas abordagens iniciais, propomos duas outras que utilizam o sistema de memória composto por memória principal e memória externa, o qual chamamos de sistema híbrido de memória, para computar e manter atualizado cubos com alta dimensionalidade e elevado número de tuplas: HIC e bCubing. Em HIC, partições de cubos são armazenados em RAM e na memória externa utilizando a mesma representação de Frag-Cubing, contudo valores de atributos frequentes são armazenados em memória principal e valores de atributos pouco frequentes são armazenados em memória externa. HIC utiliza um parâmetro, chamado frequência acumulada crítica, para definir quais os valores de atributo são armazenados em memória principal ou em memória externa. bCubing particiona uma lista de identificadores de tuplas (TIDs) implementando a inversão de tuplas em dois níveis: um nível onde o identificador é o índice de bloco (BID) e o segundo nível onde o identificador é o índice da tupla (TID). As listas de TIDs dos valores de atributos são armazenadas em memória externa. As listas de BIDs são mantidas em memória principal e indexadas pelos valores de atributos. bCubing é capaz de calcular e manter atualizadas medidas holísticas de forma exata em cubos com alta dimensionalidade e elevado número de tuplas. Experimentos utilizando uma relação com 480 dimensões e 107 tuplas mostram que a abordagem bCubing é apenas 30% mais lenta do que Frag-Cubing para computação de cubos e aproximadamente 3 vezes mais rápida para responder consultas multidimensionais complexas a partir de tais relações. Um cubo massivo com 60 dimensões e 109 tuplas foi computado por bCubing usando 84 GB de RAM, enquanto o Frag-Cubing não computou tal cubo em uma máquina com 128 GB de RAM sem realizar operações de swap do sistema operacional. O impacto do cálculo de medidas holísticas em um cubo de dados com alta dimensionalidade também foi avaliado e os resultados demonstram que a abordagem bCubing gasta, em média, 10% mais tempo ao calcular medidas holísticas do que consultas com medidas COUNT. A abordagem bCubing respondeu consultas em um cubo de dados com 1.2 bilhões de tuplas em até 4 minutos, sendo uma destas consultas Q composta por dois operadores de subcubo e um operador EQUAL. A consulta Q calculou três medidas holísticas de forma exata: desvio padrão, mediana e moda.

Submitted by Oliveira Santos Dilzaná (dilznana@yahoo.com.br) on 2015-05-05T17:55:23Z No. of bitstreams: 1 Tese de Afrânio Mário Simões Filho.pdf: 4818346 bytes, checksum: 7ce4ddcc829847664e2c81dba4a5a9eb (MD5) / Approved for entry into archive by Ana Portela (anapoli@ufba.br) on 2015-05-06T13:33:47Z (GMT) No. of bitstreams: 1 Tese de Afrânio Mário Simões Filho.pdf: 4818346 bytes, checksum: 7ce4ddcc829847664e2c81dba4a5a9eb (MD5) / Made available in DSpace on 2015-05-06T13:33:47Z (GMT). No. of bitstreams: 1 Tese de Afrânio Mário Simões Filho.pdf: 4818346 bytes, checksum: 7ce4ddcc829847664e2c81dba4a5a9eb (MD5) / CAPES / O Celeiro Público da Bahia, concebido pelo governo colonial para solucionar as crises constantes que abalavam o concorrido mercado de abastecimento da cidade de Salvador, foi instrumento para regular a ampla rede de distribuição de farinha de mandioca, elemento essencial ao funcionamento da empresa colonial. Instituído em 1785, apesar de inúmeras críticas, funcionou em um armazém do Arsenal da Marinha até 1870: depois de 1822, administrado pelo governo provincial, e, com poderes reduzidos, foi assumido pela Câmara Câmara Municipal, de 1856 em diante. Cobrava um vintém por cada alqueire de farinha, arroz, feijão e milho que entrava pelo mar, e, com o seu lucro líquido sustentava o lazareto. O exame da documentação relativa ao Celeiro Público da Bahia permite identificar as relações entre o mercado de farinha de mandioca da cidade de Salvador e os interesses da economia mercantil escravista. Designed by the colonial government as a solution to the constant crises that shook the competitive market to supply the city of Salvador, the Public Granary of Bahia was the regulatory instrument of an extensive distribution network of cassava flour, an essential element for the operation of the colonial enterprise. Established in 1785 despite widespread criticism, the granary functioned in a warehouse of the Navy Arsenal until 1870: after 1822, administrated by the provincial government and with reduced powers, it was assumed by the City Council from 1856 onwards. The Granary charged a penny for every bushel of flour, rice, beans and corn that entered by sea, and its net income supported the leper hospital. The exam of documentation relating to the Public Granary of Bahia allows to identify the relationship between the market of cassava flour in the city of Salvador and the interests of slavery mercantile economy.