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

expressivenessdata complexityintegrity constraintscomplexity of query processingdatabase logicexpression complexityformat modellogical data modellogical query language

Mathematics Subject Classification ID

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

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

• Q5592246 scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Q5830955 scientific article; zbMATH DE number 3092188 (Why is no real title available?)
• A relational model of data for large shared data banks A relational model of data for large shared data banks
• Alternation Alternation
• On Database Logic On Database Logic
• Structure and complexity of relational queries Structure and complexity of relational queries
• The Format Model The Format Model
• The polynomial-time hierarchy The polynomial-time hierarchy
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories 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
• An analysis of the Core-ML language: Expressive power and type reconstruction
• scientific article; zbMATH DE number 4049159 (Why is no real title available?)
• The most nonelementary theory
• scientific article; zbMATH DE number 4064541 (Why is no real title available?)

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)