Circuits for Querying Trees: A Little Survey

on YouTube ↗32m

" summary

Claims that MSO tree queries compile to Boolean circuits (a smooth d-DNNF or a zero-suppressed semantic d-DNNF) via tree automata construction in time linear in the tree, and that those circuits support semiring evaluation (counting, probabilities) in linear time and enumeration with linear preprocessing and per-answer cost proportional to the tuple size. Implements rank enumeration using persistent priority queues; supports relabel updates by local circuit changes after tree rebalancing, though smoothing can blow up circuit size.

AI-written summary · about

" chapters (9)

1. 0:00Introduction
2. 1:04Motivation for MSO logic
3. 4:15Provenance and Boolean circuits
4. 10:01Restricted circuit classes
5. 14:21Enumeration with zero-suppressed semantics
6. 20:27Circuit construction from automata
7. 25:56Rank enumeration and updates
8. 29:09Summary and future directions
9. 29:58Q&A

" related talks

• 44mEfficient Enumeration Algorithms via CircuitsAntoine Amarili · Probabilistic Circuits and Logic 2023
• 49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the CircuitDan Suciu · Probabilistic Circuits and Logic 2023
• 41mOptimizing Relational Programs IRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 53mDirect Access for Conjunctive Queries with NegationFlorent Capelli, Oliver Irwin · Probabilistic Circuits and Logic 2023
• 01h 08mAlgebraic Structures in Logic and Query Evaluation 4Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 21mBonsai: Compiling Queries to Pruned Tree TraversalsFredrik Kjolstad, Jonathan Ragan-Kelley, Alexander J Root, Christophe Gyurgyik, Andrew Adams, Purvi Goel, Kayvon Fatahalian · PLDI 2026
• 01h 02mAlgebraic Structures in Logic and Query Evaluation 3Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 06mAlgebraic Structures in Logic and Query Evaluation 1Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp