On the complexity of queries in the logical data model

DOI10.1016/0304-3975(93)90219-JzbMath0798.68072OpenAlexW2155243135MaRDI QIDQ688665

Moshe Y. Vardi, Gabriel M. Kuper

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

expressivenessintegrity constraintsdata complexitycomplexity of query processingdatabase logicexpression complexityformat modellogical data modellogical query language

Mathematics Subject Classification ID

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

Related Items

The most nonelementary theory ⋮ The complexity of the evaluation of complex algebra expressions ⋮ An analysis of the Core-ML language: Expressive power and type reconstruction

Cites Work

• Unnamed Item
• Unnamed Item
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
• The polynomial-time hierarchy
• Structure and complexity of relational queries
• The Format Model
• Alternation
• On Database Logic
• A relational model of data for large shared data banks