First-Order Provenance Games

Abstract. We propose a new model of provenance, based on a game-theoretic approach to query evaluation. First, we study gamesG 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 deter-mined 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 RA+ queries, we show that game provenance is equivalent to the most general semiring of provenance polynomi-als N[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 rea-son 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.