Expressiveness and complexity of restricted languages for complex objects
Stéphane Grumbach, Victor Vianu · Database Programming Languages · 1992
Several means of bounding the complexity of queries in various languages for complex objects are considered. For calculus-based languages, we propose a notion of safety of queries wrt a complexity class, which limits the ranges of variables to domains computable from the input database with the specified complexity. We provide a syntactic notion of range restrictedness which is a counterpart to safety. Other means to bound complexity include using fixpoint operators to provide tractable recursion, and limiting the arity and set height of higher-order types. We consider several calculus-based and deductive languages with the above restrictions, and compare their expressive power.