A dichotomy in the intensional expressive power of nested relational calculi augmented with aggregate functions and a powerset operator

Abstract

The extensional aspect of expressive power - i.e., what queries can or cannot be expressed - has been the subject of many studies of query languages. Paradoxically, although efficiency is of primary concern in computer science, the in-tensional aspect of expressive power - i.e., what queries can or cannot be implemented efficiently - has been much neglected. Here, we discuss the intensional expressive power of NRC(Q, +, -, -, /, Σ, powerset), a nested relational calculus augmented with aggregate functions and a power-set operation. We show that queries on structures such as long chains, deep trees, etc. have a dichotomous behaviour: Either they are already expressible in the calculus without using the powerset operation or they require at least exponential space. This result generalizes in three significant ways several old dichotomy-like results, such as that of Suciu and Paredaens that the complex object algebra of Abiteboul and Beeri needs exponential space to implement the transitive closure of a long chain. Firstly, a more expressive query language - in particular, one that captures SQL - is considered here. Secondly, queries on a more general class of structures than a long chain are considered here. Lastly, our proof is more general and holds for all query languages exhibiting a certain normal form and possessing a locality property. Copyright 2013 ACM.