The complexity of evaluating relational queries

DOI10.1016/S0019-9958(83)80059-XzbMATH Open0544.68065MaRDI QIDQ3334110FDOQ3334110

Authors: Stavros S. Cosmandakis 

Publication date: 1983

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

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

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)

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)
• Title not available (Why is that?)
• A probabilistic model for assigning queries at the edge
• 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
• Approximate Query Complexity
• Title not available (Why is that?)
• On the complexity of queries in the logical data model
• On the complexity of division and set joins in the relational algebra
• 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
• The query complexity of certification
• Title not available (Why is that?)
• Title not available (Why is that?)

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)