On the complexity of queries in the logical data model (Q688665)

The authors introduced [``A new approach to database logic'', in: Proc. ACM Symp. on New Principles of Database Systems, pp. 86-96 (ACM, 1984)] the logical data model (LDM) which combines and extends Jacobs' database logic and Hull and Yap's format model. The three basic operations in the LDM are: product, union and power set. This paper continues previous studies on the expressiveness of LDM; the concern is on the complexity of query processing. Two measures previously used for the complexity of relational query languages are used: data complexity (complexity w.r.t. the size of the data) and expression complexity (complexity w.r.t. the size of the expressions denoting the queries). The authors show that the product and the union are essentially first-order operations, while the power set is inherently a higher-order operation and is exponentially expensive. In a previous study [``On the expressive power of the logical data model'', in Proc. SIGMOD 1985, p. 180-187 (ACM, 1985)], the authors had shown that the logic of integrity constraints for the LDM is essentially first-order even when the power set operation is involved; the reason for the contrast with the new result is that the logic for integrity constraints deals with existing values when the power set operation is used, whereas the logical query language tries to create new values of power nodes in the schema. A hierarchy of queries is defined, based on the depth of nesting of powerset operations. This hierarchy is shown to correspond to a hierarchy of alternating Turing machines. The authors give a complete characterization of the complexity of the hierarchy of queries, the terms of tight lower and upper bounds.