6 papers
Answering Conjunctive Queries with Aggregations under Updates
Qichen Wang, Xiao Hu
Dynamic query processing keeps query answers up to date during insertions and deletions. For conjunctive queries (CQs) under set semantics, the maintainable classes are known exact…
Succinct Structure Representations for Efficient Query Optimization
Zhekai Jiang, Qichen Wang, Christoph Koch
Structural decomposition methods offer powerful theoretical guarantees for join evaluation, yet they are rarely used in real-world query optimizers. A major reason is the difficult…
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,…