A Compositional Query Algebra for Second-Order Logic and Uncertain Databases

Simple item page
dc.creatorKoch, Christoph
dc.date2008-07-29
dc.date.accessioned2026-07-07T09:53:29Z
dc.date.available2026-07-07T09:53:29Z
dc.descriptionWorld-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.
dc.description22 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/0807.4620
dc.identifierhttp://arxiv.org/abs/0807.4620
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/165970
dc.subjectDatabases
dc.subjectLogic in Computer Science
dc.subjectH.2.3
dc.titleA Compositional Query Algebra for Second-Order Logic and Uncertain Databases
dc.typetext

Files

Collections

arXiv