Discovering Denial Constraints Using Boolean Patterns
Sergio Luiz Marques Filho · 2023
Denial constraints (DCs) are at the heart of maintaining data consistency. Formulating DCs by hand is difficult and susceptible to errors. Automatically discovering DCs from data is an alternative, but this is computationally expensive due to the large search space. We propose a new method for automatically discovering DCs, named Boolean Patterns (BP), that identifies specific patterns in sets of predicates that provide minimal coverage of a set of distinct evidences from which DCs can be extracted. The main appeal of BP is its simplicity, bringing the discovery of DCs from the land of elaborated data structures to the land of boolean signs. We are currently studying two research opportunities. First, BP drastically reduces the memory required to keep intermediates in the evidence set data structures. Second, the execution of boolean signs allows exploring the discovery of DCs in highly parallel emerging hardware, like GPUs/FPGAs and processing-in-memory, offloading the discovery execution and overcoming performance bottlenecks in the CPU. We developed a CPU version of BP and compared it to other algorithms that deal with the problem of discovering minimal coverage sets of an evidence set on real-world datasets used in discovering DCs. In preliminary results, BP demonstrated superior performance, with a fraction of the memory used by its counterparts to hold evidence sets while enabling hardware acceleration.