Measuring the Importance of Database Elements

on YouTube ↗31m

" summary

Shows that tuple-importance and parameter-importance are formalized as cooperative games with database tuples or query parameters as players, and that computing Shapley scores reduces to familiar techniques: Shapley value reduction to probabilistic evaluation via a Vandermonde linear system, closed-form use of linearity of expectation, knowledge compilation to DNNF, and sampling that yields multiplicative approximations. Instantiates utilities for Boolean, aggregate, inconsistency and graph queries, proves tractability for conjunctive queries without self-join, gives a SHAP-style random-replacement definition for parameters that yields the same Shapley value, and leaves the reverse complexity equivalence open.

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 1:06Database tuple importance
3. 8:30Causality vs cooperative game theory
4. 11:53Shapley value basics
5. 16:04Complexity and probabilistic DBs
6. 21:17Query parameter importance
7. 29:02Summary

" related talks

• 01h 01mBrief Tutorial on Probabilistic DatabasesDan Suciu · Uncertainty in Computation 2016
• 04mLogic and Algorithms In Database Theory and AIHung Ngo · 9th Annual Simons Institute Industry Day
• 44mIntermediate Relational Algorithm DesignKirk Pruhs · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 43mA Dichotomy for Queries with Negation in Probabilistic DatabasesDan Olteanu · Uncertainty in Computation 2016
• 47mApproximate Lifted Inference with Probabilistic DatabasesWolfgang Gatterbauer · Uncertainty in Computation 2016
• 20mPolygon: Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation SearchXinyu Wang, Pinhan Zhao, Yuepeng Wang · PLDI 2025
• 15mSpeeding up Symbolic Reasoning for Relational QueriesChenglong Wang · OOPSLA 2018
• 39mMassively Parallel Evaluation of Relational Queries IIXiao Hu, Paris Koutris · Fine-Grained Complexity, Logic, and Query Evaluation 2023