Papers › On the Structure of Game Provenance and its Applications
On the Structure of Game Provenance and its Applications
Shawn Bowers, Yilin Xia, Bertram Ludäscher
Provenance in databases has been thoroughly studied for positive and for recursive queries, then for first-order (FO) queries, i.e., having negation but no recursion. Query evaluation can be understood as a two-player game where the opponents argue whether or not a tuple is in the query answer. This game-theoretic approach yields a natural provenance model for FO queries, unifying how and why-not provenance. Here, we study the fine-grain structure of game provenance. A game G=(V,E) consists of positions V and moves E and can be solved by computing the well-founded model of a single, unstratifiable rule: win(X) ←move(X, Y), ¬ win(Y). In the solved game G^λ, the value of a position x ∈ V is either won, lost, or drawn. This value is explained by the provenance 𝒫(x), i.e., certain (annotated) edges reachable from x. We identify seven edge types that give rise to new kinds of provenance, i.e., potential, actual, and primary, and demonstrate that "not all moves are created equal". We describe the new provenance types, show how they can be computed while solving games, and discuss applications, e.g., for abstract argumentation frameworks.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections