2021/05/29 by Neha Makhija, Makhija, Neha, Wolfgang Gatterbauer +1
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Data Quality and Management #Databases (cs.DB) #FOS: Computer and information sciences #Scientific Computing and Data Management
paper · pdf · doi:10.48550/arxiv.2105.14307
openalex publication_date 2021/05/29 · openalex created_date 2021/06/22 · openalex updated_date 2026/07/28
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 Σp2-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.