Evaluating Datalog over Semirings: A Grounding-based Approach
<|reference_start|>Evaluating Datalog over Semirings: A Grounding-based Approach: Datalog is a powerful yet elegant language that allows expressing recursive computation. Although Datalog evaluation has been extensively studied in the literature, so far, only loose upper bounds are known on how fast a Datalog program can be evaluated. In this work, we ask the following question: given a Datalog program over a naturally-ordered semiring $\sigma$, what is the tightest possible runtime? To this end, our main contribution is a general two-phase framework for analyzing the data complexity of Datalog over $\sigma$: first ground the program into an equivalent system of polynomial equations (i.e. grounding) and then find the least fixpoint of the grounding over $\sigma$. We present algorithms that use structure-aware query evaluation techniques to obtain the smallest possible groundings. Next, efficient algorithms for fixpoint evaluation are introduced over two classes of semirings: (1) finite-rank semirings and (2) absorptive semirings of total order. Combining both phases, we obtain state-of-the-art and new algorithmic results. Finally, we complement our results with a matching fine-grained lower bound.<|reference_end|>
@article{zhao2024evaluating,
    title={Evaluating Datalog over Semirings: A Grounding-based Approach},
    author={Hangdong Zhao, Shaleen Deep, Paraschos Koutris, Sudeepa Roy, Val
  Tannen},
    journal={arXiv preprint arXiv:2403.12436},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.12436},
    primaryClass={cs.DB}
}