Polynomial queries to relational data bases

MaRDI QIDQ1067795zbMATH OpenFDO

Authors A. B. Livchak

Publication date 1985

Published in Programming and Computer Software (Search for Journal in Brave)

zbMATH Keywords

deterministic Turing machine

Mathematics Subject Classification ID

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

Review text

A language is described, in which it is possible to express exactly all queries computable on a deterministic Turing machine in a time polynomial with respect to the volume of input data.

Recommendations

• Relational queries computable in polynomial time
• scientific article; zbMATH DE number 3932433
• Comparison of expressive power of some query languages for databases
• The complexity of evaluating relational queries
• Completeness results for recursive data bases

Cited in

(13)

• A query language allowing conditions of relational type in queries
• Pragmatics and semantics of NQL, a descriptive query language for network databases
• An algorithm for handling many relational calculus queries efficiently.
• Logical language of description of polynomial computing
• Relational queries computable in polynomial time
• Primitive program algebras of computable functions
• scientific article; zbMATH DE number 1735629 (Why is no real title available?)
• scientific article; zbMATH DE number 938662 (Why is no real title available?)
• Declarative PTIME queries for relational databases using quantifier elimination
• Query order in the polynomial hierarchy
• Database Theory - ICDT 2005
• Verification, Model Checking, and Abstract Interpretation
• Procedural languages for database queries and updates

This page was built for publication: Polynomial queries to relational data bases

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