EUVIMEDObjevte EUVIMED
Crossref

Discovery of Denial Constraints with Hardware Acceleration

Sergio Luiz Marques Filho, Eduardo Cunha de Almeida, Marco Antonio Zanata Alves

Proceedings of the ACM on Management of Data · 2026-05-18 · 4 (3) · 1-22

DOI: 10.1145/3802041 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Sergio Luiz Marques Filho and 2 co-authors. 33 references.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

Denial constraints (DCs) formalize integrity rules that keep data consistent across profiling and cleaning tasks. However, discovering DCs remains computationally expensive due to the exponential size of the predicate search space and the cost of maintaining large intermediate data structures. Existing software-based DC discovery algorithms rely on evidence set materialization, candidate enumeration, and minimality checks, resulting in superlinear runtime growth and unpredictable performance, which limits their scalability in practice. We present DCArray, an FPGA-based accelerator that performs DC discovery directly in hardware pipelines. DCArray encodes DC predicates as boolean patterns and evaluates them using highly parallel logical units, each operating within a single clock cycle. Boolean patterns are encoded in a hardware-friendly prefix-tree design, eliminating the need for intermediate evidence sets and reducing memory overhead and data movement. DCArray implements minimality checks at the circuit level, achieving predictable runtime independent of dataset distribution. Across real and synthetic datasets, DCArray achieves speedups of up to 1560x over DCFinder and up to 10x over ECP on 1M tuples, while efficiently utilizing HBM/PCIe. At the 10M-tuple scale, end-to-end performance is primarily limited by sustained host-device I/O bandwidth, making DCArray a practical alternative for production data-quality pipelines.

Cite

APA

Filho, S. L. M., Almeida, E. C. D., & Alves, M. A. Z. (2026). Discovery of Denial Constraints with Hardware Acceleration. Proceedings of the ACM on Management of Data, 4(3), 1-22. https://doi.org/10.1145/3802041

Vancouver

Filho SLM, Almeida ECD, Alves MAZ. Discovery of Denial Constraints with Hardware Acceleration. Proceedings of the ACM on Management of Data. 2026;4(3):1-22. doi:10.1145/3802041

BibTeX
@article{Filho2026,
  author = {Filho, Sergio Luiz Marques and Almeida, Eduardo Cunha de and Alves, Marco Antonio Zanata},
  title = {Discovery of Denial Constraints with Hardware Acceleration},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--22},
  doi = {10.1145/3802041}
}
Start for free →