Authors
Citation
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
Journal title
ISSN journal
00220000
Volume
55
Issue
2
Year of publication
1997
Pages
322 - 343
Database
ISI
SICI code
0022-0000(1997)55:2<322:TCOTEO>2.0.ZU;2-0
Abstract
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.