Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

On the Structure of Game Provenance and its Applications

Created by
  • Haebom

Author

Shawn Bowers, Yilin Xia, Bertram Lud ascher

Outline

This paper studies provenance in databases from a game-theoretic perspective. In particular, we address provenance for first-order logic (FO) queries that involve negation but do not involve recursion. We model query evaluation as a two-player game, where players argue over which tuples are included in the query result. This game-theoretic approach provides a natural provenance model that integrates how and why-not provenance tracing. We study the detailed structure of this game provenance tracing, and identify seven types of edges that occur during the game's resolution, proposing new types of provenance tracing: latent, actual, and prime provenance tracing. We show that "not all moves are equivalent," describe the new provenance tracing types, present a computational methodology, and discuss applications such as an abstract argumentation framework.

Takeaways, Limitations

Takeaways:
We present a novel model that integrates how and why-not origin tracking for FO queries using a game theoretic approach.
We present a new origin tracing model based on seven types of edges, which is more detailed than the existing origin tracing models.
We present an efficient way to compute a new type of origin tracking during game resolution.
It shows applicability in various fields such as abstract argument framework.
Limitations:
Currently, it is only applicable to FO queries that do not include recursion. Extended research on recursive queries is needed.
Further research is needed to investigate the comprehensiveness of the seven edge types presented and their effectiveness in real database systems.
More in-depth analysis and experimental evaluation of real-world applications are needed.
👍