The complexity of evaluating relational queries

DOI10.1016/S0019-9958(83)80059-XMaRDI QIDQ3334110zbMATH OpenFDO

Authors Stavros S. Cosmandakis

Publication date 1983

Published in Information and Control (Search for Journal in Brave)

zbMATH Keywords

completenesshardnesspolynomial transformationrelational databaseenumeration problemNPpolynomial-time hierarchyco-NPevaluation of relational queriesrelational expression

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of database queries
• Relational queries computable in polynomial time
• The complexity of acyclic conjunctive queries
• The Complexity of Counting Problems Over Incomplete Databases
• On the complexity of finding bounds for projection cardinalities in relational databases

Cited in

(23)

• Average-case complexity for the execution of recursive definitions on relational databases (paper no 50-95 accepted for publication in ACTA INFORMATICA)
• A probabilistic model for assigning queries at the edge
• scientific article; zbMATH DE number 1950753 (Why is no real title available?)
• On the complexity of finding bounds for projection cardinalities in relational databases
• The hardness of resilience for nested aggregation query
• Computational complexity of queries based on itemsets
• On the complexity of deciding typability in the relational algebra
• Sort order problems in relational databases
• On the representation and querying of sets of possible worlds
• Verification, Model Checking, and Abstract Interpretation
• On the complexity of queries in the logical data model
• Approximate Query Complexity
• On the complexity of division and set joins in the relational algebra
• scientific article; zbMATH DE number 2218055 (Why is no real title available?)
• The tree projection theorem and relational query processing
• Computational properties of metaquerying problems
• Relational queries computable in polynomial time
• The Complexity of Counting Problems Over Incomplete Databases
• Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity
• Polynomial queries to relational data bases
• scientific article; zbMATH DE number 3949731 (Why is no real title available?)
• The query complexity of certification
• scientific article; zbMATH DE number 4064541 (Why is no real title available?)

This page was built for publication: The complexity of evaluating relational queries

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