4 papers
Size Bound-Adorned Datalog
Christian Fattebert, Zhekai Jiang, Christoph Koch +2
We introduce EDB-bounded datalog, a framework for deriving upper bounds on intermediate result sizes and the asymptotic complexity of recursive queries in datalog. We present an al…
Towards Parameterized Hardness on Maintaining Conjunctive Queries
Qichen Wang
We investigate the fine-grained complexity of dynamically maintaining the result of fixed self-join free conjunctive queries under single-tuple updates. Prior work shows that free-…
Database Theory in Action: Yannakakis' Algorithm
Paraschos Koutris, Stijn Vansummeren, Qichen Wang +2
Yannakakis' seminal algorithm is optimal for acyclic joins, yet it has not been widely adopted due to its poor performance in practice. This paper briefly surveys recent advancemen…
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees
Qichen Wang, Bingnan Chen, Binyang Dai +3
Acyclic conjunctive queries form the backbone of most analytical workloads, and have been extensively studied in the literature from both theoretical and practical angles. However,…