Processamento de Consultas Aproximadas sob Atualizações

O processamento de consultas sob atualizações (também conhecido como manutenção incremental de visualizações) tem recebido atenção crescente nos últimos anos, tanto de ângulos teóricos quanto práticos. Embora os algoritmos existentes funcionem bem no tratamento de consultas de relatórios, eles podem incorrer em um alto custo em consultas de agregação, que são o tipo mais importante de carga de trabalho analítica. Neste artigo, mostramos que, ao permitir um pequeno erro de aproximação, consultas de agregação podem ser processadas de forma eficiente sob atualizações. Especificamente, projetamos um novo algoritmo de processamento de consultas aproximadas (AQP) que pode manter o resultado de qualquer consulta de agregação livre-conexa em tempo logarítmico amortizado por atualização em uma sequência de atualização somente de inserção. Para sequências de atualização com inserções e exclusões, o limite de tempo logarítmico não se mantém, devido a limites inferiores conhecidos. Na prática, nosso algoritmo apresenta um bom desempenho tanto em sequências de atualização somente de inserção quanto em sequências de atualização totalmente dinâmicas. Nossos resultados experimentais mostram que, com uma garantia de erro de 10%, o algoritmo alcança acelerações médias de 1,5x, 4,8x e 13,4x em relação a três soluções exatas. Nosso algoritmo funciona em uma estrutura de semiring geral, que incorpora uma variedade de agregações, incluindo contagem, soma, média, máximo e contagem distinta, possivelmente com um agrupamento por.