First-Order Provenance Games

We propose a new model of provenance, based on a game-theoretic approach to query evaluation. First, we study games

G

in their own right, and ask how to explain that a position

x

in

G

is won, lost, or drawn. The resulting notion of

game provenance

is closely related to winning strategies, and excludes from provenance all “bad moves”, i.e., those which unnecessarily allow the opponent to improve the outcome of a play. In this way, the value of a position is determined by its game provenance. We then define

provenance games

by viewing the evaluation of a first-order query as a game between two players who argue whether a tuple is in the query answer. For

$\mathcal{RA}^+$

queries, we show that game provenance is equivalent to the most general semiring of provenance polynomials ℕ[

X

]. Variants of our game yield other known semirings. However, unlike semiring provenance, game provenance also provides a “built-in” way to handle negation and thus to answer

why-not

questions: In (provenance) games, the reason why

x

is

not

won, is the same as why

x

is

lost

or

drawn

(the latter is possible for games with draws). Since first-order provenance games are draw-free, they yield a new provenance model that combines

how

- and

why-not

provenance.