On the complexity of queries in the logical data model

DOI10.1016/0304-3975(93)90219-JMaRDI QIDQ688665zbMATH OpenOpenAlexFDO

Authors Gabriel M. Kuper, Moshe Y. Vardi

Publication date 6 November 1994

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90219-j

zbMATH Keywords

complexity of query processingdata complexitydatabase logicexpression complexityexpressivenessformat modelintegrity constraintslogical data modellogical query language

Mathematics Subject Classification ID

Database theory (68P15) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• scientific article; zbMATH DE number 4064541
• Data complexity of query answering in description logics
• Complexity of the Stable Model Semantics for Queries on Incomplete Databases
• Data complexity of query answering in expressive description logics via tableaux
• On the complexity of database queries
• The complexity of evaluating relational queries
• scientific article; zbMATH DE number 1405452
• The Complexity of Datalog on Linear Orders
• On the data complexity of consistent query answering

Cites work

• A relational model of data for large shared data banks
• Alternation
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3092188 (Why is no real title available?)
• On Database Logic
• Structure and complexity of relational queries
• The Format Model
• The polynomial-time hierarchy
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories

Cited in

(5)

• The complexity of the evaluation of complex algebra expressions
• scientific article; zbMATH DE number 4049159 (Why is no real title available?)
• scientific article; zbMATH DE number 4064541 (Why is no real title available?)
• An analysis of the Core-ML language: Expressive power and type reconstruction
• The most nonelementary theory

This page was built for publication: On the complexity of queries in the logical data model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688665)