Tractable query languages for complex object databases
Stéphane Grumbach, Victor Vianu · 1991
The expressiveness and complexity of several calculus-based query languages for complex objects is considered. Unlike previous investigations, we are concerned with the complexity of queries on databases of complex objects, rather than flat databases. This raises new issues specific to complex objects. For instance, it is shown that the way the database makes use of its higher-order types has direct impact on query complexity. The use of fixpoint operators is shown to yield languages well-behaved with respect to complexity and expressiveness. In particular, an extension of the fixpoint queries to complex objects is shown to express precisely the PTIME queries, under the assumption that the database makes "full" use of all its types. Similar results involve range-restricted queries. 1 Introduction Complex objects are increasingly part of advanced database systems. They provide the structural core of object-oriented databases. Several query languages for complex objects have been propo...