On the complexity of queries in the logical data model
From MaRDI portal
Publication:688665
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
expressivenessintegrity constraintsdata complexitycomplexity of query processingdatabase logicexpression complexityformat modellogical data modellogical query language
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