A Compositional Query Algebra for Second-Order Logic and Uncertain Databases
Authors
- Christoph Koch (Cornell University, USA)
Abstract
World-set algebra is a variable-free query language for uncertain databases. It constitutes the core of the query language implemented in MayBMS, an uncertain database system. This paper shows that world-set algebra captures exactly second-order logic over finite structures, or equivalently, the polynomial hierarchy. The proofs also imply that world-set algebra is closed under composition, a previously open problem.
Session
ICDT Research Session 4: Uncertain Databases (Tuesday, March 24, 11:00—12:30)