用博弈论解析数据库查询的证明溯源，揭示不同操作路径的差异价值。
On the Structure of Game Provenance and its Applications
- 将查询验证建模为两人博弈，通过胜负状态推导每条路径的溯源信息。
- 识别出七类边关系，区分潜在、实际与核心溯源路径，揭示关键决策节点。
- 适用于论证框架等场景，帮助理解复杂推理中的关键证据来源。
数据库溯源在正查询和递归查询中已有深入研究，随后扩展至一阶（FO）查询，即含否定但无递归的情况。查询评估可视为一场两人博弈，双方争论某个元组是否属于查询结果。这种博弈论方法为一阶查询提供了自然的溯源模型，统一了如何及为何不溯源的解释。本文研究博弈溯源的细粒度结构。一个博弈 $G=(V,E)$ 包含位置 $V$ 和移动 $E$，可通过计算单一不可分层规则的良基模型求解： $$ ext{win}(X) ightarrow ext{move}(X, Y), \neg \, \text{win}(Y). $$ 在求解后的博弈 $G^λ$ 中，每个位置 $x\,{\in}\,V$ 的值为胜、负或平局。该值由从 $x$ 可达的特定（带注释）边构成的溯源 $\\mathscr{P}(x)$ 解释。我们识别出七种边类型，引出新的溯源类型：潜在、实际与主要溯源，并证明“并非所有移动都同等重要”。我们描述这些新溯源类型，展示其在求解博弈过程中可被计算，并讨论其应用，例如抽象论证框架。
原文摘要 · Abstract (English)
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: \[ \text{win}(X) \leftarrow \text{move}(X, Y), \neg \, \text{win}(Y). \] In the solved game $G^λ$, the value of a position $x\,{\in}\,V$ is either won, lost, or drawn. This value is explained by the provenance $\mathscr{P}$(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。