Circuits and Formulas for Datalog over Semirings
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912322108260352 |
|---|---|
| author | Fan, Austen Z. Koutris, Paraschos Roy, Sudeepa |
| author_facet | Fan, Austen Z. Koutris, Paraschos Roy, Sudeepa |
| contents | 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 $Θ(\log^2 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(\log^2 m)$. Finally, we give characterizations of when Datalog programs are bounded over more general semirings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_08914 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Circuits and Formulas for Datalog over Semirings Fan, Austen Z. Koutris, Paraschos Roy, Sudeepa Databases Computational Complexity 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 $Θ(\log^2 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(\log^2 m)$. Finally, we give characterizations of when Datalog programs are bounded over more general semirings. |
| title | Circuits and Formulas for Datalog over Semirings |
| topic | Databases Computational Complexity |
| url | https://arxiv.org/abs/2504.08914 |