  We consider the problem of finding the minimal-size factorization of the
provenance of self-join-free conjunctive queries, i.e., we want to find a
formula that minimizes the number of variable repetitions. This problem is
equivalent to solving the fundamental Boolean formula factorization problem for
the restricted setting of the provenance formulas of self-join free queries.
While general Boolean formula minimization is $\Sigma^p_2$-complete, we show
that the problem is NP-C in our case. Additionally, we identify a large
category of queries that can be solved in PTIME, expanding beyond the
previously known tractable cases of read-once formulas and hierarchical
queries.
  We describe connections between factorizations, Variable Elimination Orders
(VEOs), and minimal query plans. We leverage these insights to create an
Integer Linear Program (ILP) that can solve the minimal factorization problem
exactly. We also propose a Max-Flow Min-Cut (MFMC) based algorithm that gives
an efficient approximate solution. Importantly, we show that both the Linear
Programming (LP) relaxation of our ILP, and our MFMC-based algorithm are always
correct for all currently known PTIME cases. Thus, we present two unified
algorithms (ILP and MFMC) that can both recover all known PTIME cases in PTIME,
yet also solve NP-complete cases either exactly (ILP) or approximately (MFMC),
as desired.
