A logical account of uncertain databases based on linear logic

A formal semantics of uncertain databases typically takes an algebraic approach by mapping an uncertain database to a set of relational databases, or possible worlds. We present a new semantics for uncertain databases which takes a logical approach by translating uncertain databases into logical theories. A characteristic feature of our semantics is that it uses linear logic, instead of propositional logic, as its logical foundation. Linear logic lends itself well to a logical interpretation of uncertain information because unlike propositional logic, it treats logical formulae not as persistent facts but as consumable resources. We motivate our development by arguing that propositional logic is inadequate as a logical foundation for uncertain databases. As the main result, we show that our semantics is faithful to the operational account of uncertain databases in the algebraic approach.