A logical account of uncertain databases based on linear logic

Sungwoo Park, Seung Won Hwang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish
Title of host publicationProceedings of the 12th International Conference on Database Theory, ICDT'09
Number of pages8
Publication statusPublished - 2009
Event12th International Conference on Database Theory, ICDT'09 - Saint Petersburg, Russian Federation
Duration: 2009 Mar 232009 Mar 25

Publication series

NameACM International Conference Proceeding Series


Other12th International Conference on Database Theory, ICDT'09
Country/TerritoryRussian Federation
CitySaint Petersburg

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'A logical account of uncertain databases based on linear logic'. Together they form a unique fingerprint.

Cite this