13 papers
FlowLog: Re-thinking Datalog for Fast and Extensible Static Analysis
Zhenghong Yu, Hangdong Zhao, Wanzhu Hou +1
Datalog is widely used to build static analyzers, yet existing engines often force a tradeoff between efficiency and extensibility. In practice, static analyses are not run once an…
Fast Join Project Query Evaluation using Matrix Multiplication
Shaleen Deep, Xiao Hu, Paraschos Koutris
In the last few years, much effort has been devoted to developing join algorithms in order to achieve worst-case optimality for join queries over relational databases. Towards this…
K-Join: Combining Vertex Covers for Parallel Joins
Simon Frisk, Austen Fan, Paraschos Koutris
Significant research effort has been devoted to improving the performance of join processing in the massively parallel computation model, where the goal is to evaluate a query with…
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…
Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries
Yifei Yang, Hangdong Zhao, Xiangyao Yu +1
This paper presents predicate transfer, a novel method that optimizes join performance by pre-filtering tables to reduce the join input sizes. Predicate transfer generalizes Bloom…
FlowLog: Efficient and Extensible Datalog via Incrementality
Hangdong Zhao, Zhenghong Yu, Srinag Rao +3
Datalog-based languages are regaining popularity as a powerful abstraction for expressing recursive computations in domains such as program analysis and graph processing. However,…