Este trabalho introduz o CorrBound, um estimador de cardinalidade que explora as correlações entre as colunas de junção em relações e dentro delas. Os estimadores mais avançados não observam tais correlações e, portanto, podem gerar estimativas imprecisas. Ao considerar explicitamente as correlações, o CorrBound pode melhorar significativamente a precisão da estimativa de cardinalidade. O CorrBound suporta consultas de múltiplas junções (acíclicas ou cíclicas) com conjunções de predicados de igualdade e intervalo e cláusulas de agrupamento. Sua estimativa é a solução ótima de um programa linear cujas restrições codificam estatísticas de dados e desigualdades de Shannon. Ele utiliza uma nova desigualdade de informação que captura as correlações intra- e inter-relações das colunas de junção e utiliza o produto interno generalizado de vetores de grau das colunas de junção. Essa desigualdade também captura a desigualdade ℓ p -norm utilizada pelo estimador avançado LpBound. A desigualdade vem com um desafio de alta dimensionalidade: gerenciar o tensor de cardinalidade definido pelos produtos internos generalizados de muitos vetores de grau grandes. Para manter o tempo de estimativa viável, o CorrBound utiliza duas técnicas de compressão que preservam a precisão dos produtos internos: esboços de vetores de grau e decomposição de baixa classificação do tensor de cardinalidade. Avaliamos experimentalmente o CorrBound em relação a estimadores tradicionais, pessimistas e baseados em aprendizado de máquina em benchmarks JOBlight, STATS e de correspondência de subgrafo. Nossa principal descoberta é que o CorrBound pode ser mais preciso do que o estado da arte, mantendo um baixo tempo de estimativa.
Mayer et al. (Qui,) estudaram essa questão.