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)

Full work available at URL https://doi.org/10.1016/S0019-9958(83)80059-X

zbMATH Keywords

co-NPcompletenessenumeration problemevaluation of relational querieshardnessNPpolynomial transformationpolynomial-time hierarchyrelational databaserelational 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

(26)

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

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)