Projeção Eficiente de Violações de Restrições de Negação

• Leonardo F. Luciano Universidade Federal do Paraná
• Wendel C. Moro Universidade Federal do Paraná
• Eduardo C. de Almeida Universidade Federal do Paraná https://orcid.org/0000-0002-6644-956X
• Eduardo H. M. Pena Universidade Tecnológica Federal do Paraná

DOI: https://doi.org/10.5753/sbbd.2023.233388

Resumo

A visualização de violações de regras de qualidade de dados possui grande utilidade na limpeza de dados. Uma operação amplamente utilizada para essa visualização é a projeção das combinações de tuplas que violam as regras. No entanto, essa operação é custosa quando consideramos os formalismos estado-da-arte em limpeza de dados, como as restrições de negação. No pior caso, todas as combinações de pares de tuplas da tabela violam a regra, resultando em uma complexidade quadrática em relação ao número de registros. Este artigo apresenta e avalia experimentalmente diversas técnicas para a implementação eficiente da projeção de violações de restrições de negação.

Palavras-chave: Limpeza de Dados, Regras de Dados, Projeção

Referências

Chu, X., Ilyas, I. F., and Papotti, P. (2013). Discovering denial constraints. Proc. VLDB Endow., 6(13):1498–1509.

Grefen, P. and de By, R. (1994). A multi-set extended relational algebra: a formal approach to a practical issue. In Proceedings of 1994 IEEE 10th International Conference on Data Engineering, pages 80–88.

Pena, E. H. M., de Almeida, E. C., and Naumann, F. (2022). Fast detection of denial constraint violations. Proc. VLDB Endow., 15(4):859–871.

Pena, E. H. M., Lucas Filho, E. R., de Almeida, E. C., and Naumann, F. (2020). Efficient detection of data dependency violations. In 29th ACM CIKM, page 1235–1244.

Rekatsinas, T., Chu, X., Ilyas, I. F., and Ré, C. (2017). Holoclean: Holistic data repairs with probabilistic inference. Proc. VLDB Endow., 10(11):1190–1201.