The Complexity of the Evaluation of Complex Algebra Expressions

摘要

The Abiteboul and Beeri algebra for complex objects can express a query whose meaning is transitive closure, but the algorithm naturally associated to this query needs exponential space. We show that any other query in the algebra which expresses transitive closure needs exponential space, under a “call by value” evaluation strategy. This proves that in general the powerset is an intractable operator for implementing fixpoint queries.