Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure.

Dan Suciu, Jan Paredaens

Browse the full PODS paper archive.