2025/04/11 by Fan, Austen Z., Koutris, Paraschos, Roy, Sudeepa
#Computational Complexity (cs.CC) #Databases (cs.DB) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2504.08914
In this paper, we study circuits and formulas for provenance polynomials of Datalog programs. We ask the following question: given an absorptive semiring and a fact of a Datalog program, what is the optimal depth and size of a circuit/formula that computes its provenance polynomial? We focus on absorptive semirings as these guarantee the existence of a polynomial-size circuit. Our main result is a dichotomy for several classes of Datalog programs on whether they admit a formula of polynomial size or not. We achieve this result by showing that for these Datalog programs the optimal circuit depth is either Θ(log m) or Θ(log2 m), where m is the input size. We also show that for Datalog programs with the polynomial fringe property, we can always construct low-depth circuits of size O(log2 m). Finally, we give characterizations of when Datalog programs are bounded over more general semirings.