Discovery and Application of Data Dependencies

• Eduardo Henrique Monteiro Pena UFPR
• Eduardo Cunha de Almeida UFPR

DOI: https://doi.org/10.5753/ctd.2021.15749

Resumo

Este trabalho faz contribuições que abrangem problemas centrais em relação às dependências de dados. O primeiro problema diz respeito à descoberta de dependências com alto poder de expressividade. Apresentamos um algoritmo eficiente para a descoberta de restrições de negação: um tipo de dependência com poder de expressividade suficiente para generalizar outros tipos importantes de dependências, e expressar regras de negócios complexas. O segundo problema diz respeito à aplicação de dependências para melhoraria de consistência de dados. Apresentamos uma modificação para as abordagens tradicionais de descoberta de dependência que permite que algoritmos de descoberta de dependência retornem resultados confiáveis, mesmo que sejam executados sobre dados contendo alguns registros inconsistentes. Além disso, apresentamos um sistema para detecção eficiente de violações de dependências. Nossa extensa avaliação experimental mostra que nosso sistema é até três ordens de magnitudes mais rápido do que competidores estado-da-arte, especialmente para grandes conjuntos de dados e um grande número de violações de dependência. A última contribuição deste trabalho diz respeito à aplicação de dependências na otimização de consultas. Apresentamos um sistema para a descoberta e seleção automática de dependências funcionais. Nossa avaliação experimental mostra que nosso sistema seleciona dependências funcionais relevantes que ajudam na redução do tempo de resposta para consultas em vários tipos de cargas de trabalho.

Palavras-chave: data quality, data consistency, data dependencies, integrity constraints, error detection

Referências

Abedjan, Z., Golab, L., and Naumann, F. (2015). Profiling relational data: A survey. The VLDB Journal, 24(4):557–581.

Abiteboul, S., Hull, R., and Vianu, V. (1995). Foundations of Databases. Addison-Wesley.

Kimura, H., Huo, G., Rasin, A., Madden, S., and Zdonik, S. B. (2009). Correlation maps: A compressed access method for exploiting soft functional dependencies. Proc. VLDB Endow., 2(1):1222–1233.

Liu, J., Li, J., Liu, C., and Chen, Y. (2012). Discover dependencies from data - a review. IEEE TKDE, 24(2):251–264.

Papenbrock, T., Ehrlich, J., Marten, J., Neubert, T., Rudolph, J.-P., Schönberg, M., Zwiener, J., and Naumann, F. (2015). Functional dependency discovery: An experimental evaluation of seven algorithms. PVLDB., 8(10):1082–1093.

Pena, E. H. M. (2018). Workload-aware discovery of integrity constraints for data cleaning. In VLDB 2018 - PhD Workshop, volume 2175.

Pena, E. H. M. and de Almeida, E. C. (2018). Bfastdc: A bitwise algorithm for mining denial constraints. In Database and Expert Systems Applications (DEXA), pages 5368, Cham. Springer International Publishing.

Pena, E. H. M. and de Almeida, E. C. (2019). Short paper: Descoberta automática de restrições de negação confiáveis. In XXXIV Simpósio Brasileiro de Banco de Dados, SBBD 2019, Fortaleza, CE, Brazil, October 7-10, 2019, pages 187–192. SBC.

Pena, E. H. M., de Almeida, E. C., and Naumann, F. (2019). Discovery of approximate (and exact) denial constraints. Proc. VLDB Endow., 13(3):266–278.

Pena, E. H. M., Falk, E., Meira, J. A., and de Almeida, E. C. (2018). Mind your dependencies for semantic query optimization. JIDM, 9(1):3–19.

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

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

Santore, F., de Almeida, E. C., Bonat, W. H., Pena, E. H. M., and de Oliveira, L. E. S. (2020). A framework for analyzing the impact of missing data in predictive models. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM), pages 2209–2212.