Abstract
Provenance for positive queries is well understood and elegantly handled by provenance semirings [GKT07], which subsume many earlier approaches. However, the semiring approach does not extend easily to why-not provenance or, more generally, first-order queries with negation. An alternative approach is to view query evaluation as a game between two players who argue whether, for given database I and query Q, a tuple t is in the answer Q(I) or not. For first-order logic, the resulting provenance games [KLZ13] yield a new provenance model that coincides with provenance semirings (how provenance) on positive queries, but also is applicable to first-order queries with negation, thus providing an elegant, uniform treatment of earlier approaches, including why-not provenance and negation. In order to obtain a finite answer to a why-not question, provenance games employ an active domain semantics and enumerate tuples that contribute to failed derivations, resulting in a domain dependent formalism. In this paper, we propose constraint provenance games as a means to address this issue. The key idea is to represent infinite answers (e.g., to why-not questions) by finite constraints, i.e., equalities and disequalities.
Original language | English (US) |
---|---|
State | Published - 2014 |
Externally published | Yes |
Event | 6th Workshop on the Theory and Practice of Provenance, TaPP 2014 - Cologne, Germany Duration: Jun 12 2014 → Jun 13 2014 |
Conference
Conference | 6th Workshop on the Theory and Practice of Provenance, TaPP 2014 |
---|---|
Country/Territory | Germany |
City | Cologne |
Period | 6/12/14 → 6/13/14 |
ASJC Scopus subject areas
- General Computer Science