Enumeration complexity of conjunctive queries with functional dependencies

DOI10.1007/S00224-019-09937-9zbMATHOpenAlexWikidataMaRDI QIDQ778529FDO

Authors Nofar Carmeli, Markus Kröll

Publication date 2 July 2020

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8598/

zbMATH Keywords

complexityenumerationconjunctive queriesfunctional dependencies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Recommendations

• Enumeration complexity of conjunctive queries with functional dependencies
• The complexity of acyclic conjunctive queries
• Computing supports of conjunctive queries on relational tables with functional dependencies
• Entropy bounds for conjunctive queries with functional dependencies
• Structural tractability of counting of solutions to conjunctive queries
• Parameterized complexity of completeness reasoning for conjunctive queries
• Theory and Applications of Satisfiability Testing
• Semantically Acyclic Conjunctive Queries under Functional Dependencies
• Complexity of Default Logic on Generalized Conjunctive Queries
• On the complexity of join dependencies

Cites work

• scientific article; zbMATH DE number 6820309 (Why is no real title available?)
• Answering FO+MOD queries under updates on bounded degree databases
• Constant delay enumeration for FO queries over databases with local bounded expansion
• Enumeration complexity of conjunctive queries with functional dependencies
• Incremental delay enumeration: space and time
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• On the Desirability of Acyclic Database Schemes
• On the complexity of database queries
• Powers of tensors and fast matrix multiplication
• Query evaluation via tree-decompositions
• Sorting, linear time and the satisfiability problem
• Tight hardness for shortest cycles and paths in sparse graphs

Cited in

(14)

• Computing supports of conjunctive queries on relational tables with functional dependencies
• The complexity of acyclic conjunctive queries
• Enumeration complexity of conjunctive queries with functional dependencies
• Enumeration complexity of logical query problems with second-order variables
• Removing additive structure in 3SUM-based reductions
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• Diversity of answers to conjunctive queries
• scientific article; zbMATH DE number 5200724 (Why is no real title available?)
• On the Complexity of Insertion Propagation with Functional Dependency Constraints
• Efficient enumeration for conjunctive queries over X-underbar structures
• Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
• Enumeration complexity of poor man's propositional dependence logic
• Semantically Acyclic Conjunctive Queries under Functional Dependencies
• A glimpse on constant delay enumeration (invited talk)

This page was built for publication: Enumeration complexity of conjunctive queries with functional dependencies

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