On Dualization over Distributive Lattices

Given a partially ordered set (poset) P, and a pair of families of ideals I and filters F in P such that each pair (I, F) ∈ I × F has a non-empty intersection, the dualization problem over P is to check whether there is an ideal X in P which intersects every member of F and does not contain any member of I. Equivalently, the problem is to check for a distributive lattice L = L(P), given by the poset P of its set of joint-irreducibles, and two given antichains A, B ⊆ L such that no a ∈ A is dominated by any b ∈ B, whether A and B cover (by domination) the entire lattice. We show that the problem can be solved in quasi-polynomial time in the sizes of P, A and B, thus answering an open question in Babin and Kuznetsov (2017). As an application, we show that minimal infrequent closed sets of attributes in a relational database, with respect to a given implication base of maximum premise size of one, can be enumerated in incremental quasi-polynomial time.