%0 Journal Article
%T A Compositional Query Algebra for Second-Order Logic and Uncertain Databases
%A Christoph Koch
%J Computer Science
%D 2008
%I arXiv
%X 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.
%U http://arxiv.org/abs/0807.4620v1