System and method for fast constraint discovery on relational data

A system comprising:

• a memory storing instructions thereon;
• and
• at least one processor coupled with the memory and configured by the instructions to:
• construct, for a dataset stored by a database engine, a lattice for traversing candidate denial constraints (DC) in increasing order of predicate size, including a first layer of the lattice using a first plurality of candidate DCs each having a same first number of predicates;
• perform a tree-based verification process on the first layer of the lattice to determine one or more verified DCs confirmed to be DCs and a plurality of unverified DCs that are not confirmed to be DCs;
• present, via a graphical user interface (GUI), DC information including an indication of the one or more verified DCs;
• and
• generate, for construction of a second layer of the lattice to be evaluated via the tree-based verification process, a second plurality of candidate DCs by combining subsets of the plurality of unverified DCs so that each candidate DC in the second plurality of candidate DCs has a same second number of predicates.

A non-transitory computer-readable device having instructions thereon that, when executed by at least one computing device, cause the at least one computing device to perform operations comprising:

• constructing, for a dataset stored by a database engine, a lattice for traversing candidate denial constraints (DC) in increasing order of predicate size, including a first layer of the lattice using a first plurality of candidate DCs each having a same first number of predicates;
• performing a tree-based verification process on the first layer of the lattice to determine one or more verified DCs confirmed to be DCs and a plurality of unverified DCs that are not confirmed to be DCs;
• presenting, via a graphical user interface (GUI), DC information including an indication of the one or more verified DCs;
• and
• generating, for construction of a second layer of the lattice to be evaluated via the tree-based verification process, a second plurality of candidate DCs by combining subsets of the plurality of unverified DCs so that each candidate DC in the second plurality of candidate DCs has a same second number of predicates.