First-Order Provenance Games
| Autor: | Daniel Zinn, Sven Köhler, Bertram Ludäscher |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Provenance
Theoretical computer science Computer science Goal node ComputingMilieux_PERSONALCOMPUTING 0102 computer and information sciences 02 engineering and technology First order 01 natural sciences Outcome (game theory) Semiring Negation 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering Tuple Value (mathematics) |
| Zdroj: | In Search of Elegance in the Theory and Practice of Computation ISBN: 9783642416590 In Search of Elegance in the Theory and Practice of Computation |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|