D. Suciu et J. Paredaens, THE COMPLEXITY OF THE EVALUATION OF COMPLEX ALGEBRA EXPRESSIONS, Journal of computer and system sciences, 55(2), 1997, pp. 322-343
Citations number
20
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
The Abiteboul and Beeri algebra for complex objects can express a quer
y whose meaning is transitive closure, but the algorithm naturally ass
ociated to this query needs exponential space. We show that any other
query in the algebra which expresses transitive closure needs exponent
ial space, under a ''call by value'' evaluation strategy. This proves
that in general the powerset is an intractable operator for implementi
ng fixpoint queries. (C) 1997 Academic Press.