On the complexity of queries in the logical data model
type: Item
instance of: scholarly article
title: On the complexity of queries in the logical data model
zbMATH Open document ID: 0798.68072
DOI: 10.1016/0304-3975(93)90219-J
author: Gabriel M. Kuper
author: Moshe Y. Vardi
published in: Theoretical Computer Science
publication date: 1994-11-06T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 68P20
zbMATH DE Number: 438312
zbMATH Keywords: logical data model
zbMATH Keywords: database logic
zbMATH Keywords: format model
zbMATH Keywords: expressiveness
zbMATH Keywords: complexity of query processing
zbMATH Keywords: data complexity
zbMATH Keywords: expression complexity
zbMATH Keywords: integrity constraints
zbMATH Keywords: logical query language
reviewed by: H. Luchian
MaRDI profile type: Publication
cites work: Q5830955
cites work: Structure and complexity of relational queries
cites work: Alternation
cites work: A relational model of data for large shared data banks
cites work: Q5592246
cites work: The Format Model
cites work: On Database Logic
cites work: The polynomial-time hierarchy
cites work: Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
full work available at URL: 0304-3975(93)90219-j
OpenAlex ID: W2155243135
Recommended article: Q3798297
Recommended article: Data complexity of query answering in description logics
Recommended article: Complexity of the Stable Model Semantics for Queries on Incomplete Databases
Recommended article: Data complexity of query answering in expressive description logics via tableaux
Recommended article: On the complexity of database queries
Recommended article: The complexity of evaluating relational queries
Recommended article: Q4938426
Recommended article: The Complexity of Datalog on Linear Orders
Recommended article: On the data complexity of consistent query answering
description: scientific article; zbMATH DE number 438312