Discovery of Denial Constraints Using Specialized Hardware Processors
Resumo
Restrições de Negação (DCs) são fundamentais para manter a consistência dos dados. Descobrir DCs automaticamente a partir de dados é computacionalmente custoso devido ao grande espaço de busca. Neste trabalho em andamento, propomos um método acelerado por hardware para a descoberta automática de DCs, implementado em FPGAs, que elimina a necessidade de estruturas de dados intermediárias, reduzindo os requisitos de memória e aumentando o desempenho. Em experimentos preliminares com um conjunto de dados do mundo real, nosso método superou soluções de software de estado da arte por fatores entre 7x e 110x. Uma versão anterior do nosso método conquistou o 3º lugar na prestigiada Competição de Pesquisa ACM SIGMOD.
Palavras-chave:
Denial Constraints, Database, Field Programmable Gate Array
Referências
Bleifuß, T., Kruse, S., and Naumann, F. (2017). Efficient denial constraint discovery with hydra. Proceedings of the VLDB Endowment, 11:311–323.
Chu, X., Ilyas, I. F., and Papotti, P. (2013a). Discovering denial constraints. Proc. VLDB Endow., 6(13):1498–1509.
Chu, X., Ilyas, I. F., and Papotti, P. (2013b). Holistic data cleaning: Putting violations into context. In 2013 IEEE 29th International Conference on Data Engineering.
Jiang, W., Parvanov, M., and Alonso, G. (2023). Swiftspatial: Spatial joins on modern hardware.
Kossmann, J., Papenbrock, T., and Naumann, F. (2021). Data dependencies for query optimization: a survey. The VLDB Journal, 31.
Livshits, E., Heidari, A., Ilyas, I. F., and Kimelfeld, B. (2021). Approximate denial constraints. Proc. VLDB Endow., 13(10):1682–1695.
Marques Filho, S. L. (2023). Discovering denial constraints using boolean patterns. In Companion of the 2023 International Conference on Management of Data, SIGMOD ’23, page 281–283, New York, NY, USA. Association for Computing Machinery.
Maschi, F., Owaida, M., Alonso, G., Casalino, M., and Hock-Koon, A. (2020). Making search engines faster by lowering the cost of querying business rules through fpgas. In SIGMOD Conference 2020 [USA], June 14-19, 2020, pages 2255–2270. ACM.
Mueller, R., Teubner, J., and Alonso, G. (2009). Data processing on fpgas. Proc. VLDB Endow., 2(1):910–921.
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. Proc. VLDB Endow., 8(10):1082–1093.
Papenbrock, T. and Naumann, F. (2017). Data-driven schema normalization. In Markl, V., Orlando, S., Mitschang, B., Andritsos, P., Sattler, K., and Breß, S., editors, Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21-24, 2017, pages 342–353. OpenProceedings.org.
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 2018, Regensburg, Germany, September, 2018, Proceedings, Part I, volume 11029 of Lecture Notes in Computer Science, pages 53–68, Regensburg, Germany. Springer.
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., Porto, F., and Naumann, F. (2022). Fast algorithms for denial constraint discovery. Proc. VLDB Endow., 16(4):684–696.
Song, S., Gao, F., Huang, R., and Wang, C. (2020). Data dependencies over big data: A family tree. IEEE Transactions on Knowledge and Data Engineering, 34(10):1–1.
Wang, D., Dong, X., Das Sarma, A., Franklin, M., and Halevy, A. (2009). Functional dependency generation and applications in pay-as-you-go data integration systems.
Xiao, R., Tan, Z., Wang, H., and Ma, S. (2022). Fast approximate denial constraint discovery. Proc. VLDB Endow., 16(2):269–281.
Chu, X., Ilyas, I. F., and Papotti, P. (2013a). Discovering denial constraints. Proc. VLDB Endow., 6(13):1498–1509.
Chu, X., Ilyas, I. F., and Papotti, P. (2013b). Holistic data cleaning: Putting violations into context. In 2013 IEEE 29th International Conference on Data Engineering.
Jiang, W., Parvanov, M., and Alonso, G. (2023). Swiftspatial: Spatial joins on modern hardware.
Kossmann, J., Papenbrock, T., and Naumann, F. (2021). Data dependencies for query optimization: a survey. The VLDB Journal, 31.
Livshits, E., Heidari, A., Ilyas, I. F., and Kimelfeld, B. (2021). Approximate denial constraints. Proc. VLDB Endow., 13(10):1682–1695.
Marques Filho, S. L. (2023). Discovering denial constraints using boolean patterns. In Companion of the 2023 International Conference on Management of Data, SIGMOD ’23, page 281–283, New York, NY, USA. Association for Computing Machinery.
Maschi, F., Owaida, M., Alonso, G., Casalino, M., and Hock-Koon, A. (2020). Making search engines faster by lowering the cost of querying business rules through fpgas. In SIGMOD Conference 2020 [USA], June 14-19, 2020, pages 2255–2270. ACM.
Mueller, R., Teubner, J., and Alonso, G. (2009). Data processing on fpgas. Proc. VLDB Endow., 2(1):910–921.
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. Proc. VLDB Endow., 8(10):1082–1093.
Papenbrock, T. and Naumann, F. (2017). Data-driven schema normalization. In Markl, V., Orlando, S., Mitschang, B., Andritsos, P., Sattler, K., and Breß, S., editors, Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21-24, 2017, pages 342–353. OpenProceedings.org.
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 2018, Regensburg, Germany, September, 2018, Proceedings, Part I, volume 11029 of Lecture Notes in Computer Science, pages 53–68, Regensburg, Germany. Springer.
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., Porto, F., and Naumann, F. (2022). Fast algorithms for denial constraint discovery. Proc. VLDB Endow., 16(4):684–696.
Song, S., Gao, F., Huang, R., and Wang, C. (2020). Data dependencies over big data: A family tree. IEEE Transactions on Knowledge and Data Engineering, 34(10):1–1.
Wang, D., Dong, X., Das Sarma, A., Franklin, M., and Halevy, A. (2009). Functional dependency generation and applications in pay-as-you-go data integration systems.
Xiao, R., Tan, Z., Wang, H., and Ma, S. (2022). Fast approximate denial constraint discovery. Proc. VLDB Endow., 16(2):269–281.
Publicado
29/09/2025
Como Citar
MARQUES FILHO, Sergio Luiz; CUNHA DE ALMEIDA, Eduardo.
Discovery of Denial Constraints Using Specialized Hardware Processors. In: WORKSHOP DE TESES E DISSERTAÇÕES (WTDBD) - SIMPÓSIO BRASILEIRO DE BANCO DE DADOS (SBBD), 40. , 2025, Fortaleza/CE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 154-160.
DOI: https://doi.org/10.5753/sbbd_estendido.2025.247544.
