Abstract

Semiring provenance was originally introduced in database theory with the aim of explaining why certain tuples are (not) contained in the answer of a query — to explain their provenance. To this end, logical statements are not just evaluated to true or false but by values from a commutative semiring. This allows us to track which combinations of atomic facts are responsible for the truth of a statement and to derive practical information about costs, access levels, or confidence scores. Recently, this approach has been expanded to a systematic study of semiring semantics for first-order logic and other logical systems. This talk gives an overview of the recent results on the generalisation of model-theoretic properties and methods such as compactness, Ehrenfeucht-Fraïssé games, or locality beyond the Boolean semiring. Many model-theoretic notions admit natural generalisations to the semiring framework (e.g. entailments can be understood as inequalities of semiring valuations) while even simple properties lead to surprisingly difficult questions that require new proof techniques. It turns out that most of the classical logical results and methods can be generalised to some semirings but fail for others. We shall discuss how this is related to algebraic properties of the underlying semirings such as idempotence and absorption.