Consistency, Acyclicity, and Positive Semirings

on YouTube ↗38m

" summary

Shows that for positive semiring K annotated relations, every pairwise-consistent family has a global witness exactly when the schema forms an acyclic hypergraph; this unifies Beeri–Fagin–Maier–Yannakakis and Vorob'ev by replacing equality with an equivalence by scaling of K-relations. Proofs use a nontrivial join/normalization, a reduction to minimal nonconformal or nonchordal subhypergraphs, and explicit Tseitin-style constructions of K-relations that are pairwise but not globally consistent. Special cases recover Boolean and probability results; extensions to positive monoids give strict-consistency characterizations and exhibit counterexamples (even for a path).

AI-written summary · about

" chapters (6)

1. 0:00Local and global consistency
2. 3:58Database theory and BFMY theorem
3. 18:59K-relations with positive semirings
4. 27:50Vorob'ev and BFMY theorems unified
5. 31:46Positive monoids work
6. 32:07Q&A

" related talks

• 01h 02mAlgebraic Structures in Logic and Query Evaluation 3Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 08mAlgebraic Structures in Logic and Query Evaluation 4Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 05mAlgebraic Structures in Logic and Query Evaluation 2Val Tannen · 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
• 01h 05mHomomorphism Counts: Expressive Power and Query AlgorithmsPhokion Kolaitis · Satisfiability: Theory, Practice, and Beyond 2023
• 55mIntuitionistic Logic III Subschemas and TopologiesVlad Patryshev · LambdaConf 2017
• 17mJust-Right ConsistencyMarc Shapiro · dotScale 2018
• 36mOptimizing Relational Programs IIRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023