2024/12/10 by Erich Grädel, Grädel, Erich, Val Tannen +1 · 2 citations
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Databases (cs.DB) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Scientific Computing and Data Management #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2412.07986
openalex publication_date 2024/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
A provenance analysis for a query evaluation or a model checking computation extracts information on how its result depends on the atomic facts of the model or database. Traditional work on data provenance was, to a large extent, restricted to positive query languages or the negation-free fragment of first-order logic and showed how provenance abstractions can be usefully described as elements of commutative semirings -- most generally as multivariate polynomials with positive integer coefficients. We describe and evaluate here a provenance approach for dealing with negation, based on quotient semirings of polynomials with dual indeterminates. This not only provides a semiring provenance analysis for full first-order logic (and other logics and query languages with negation) but also permits a reverse provenance analysis, i.e., finding models that satisfy various properties under given provenance tracking assumptions. We describe the potential for applications to explaining missing query answers or failures of integrity constraints, and to using these explanations for computing repairs. This approach also is the basis of a systematic study of semiring semantics in a broad logical context.