Enumeration complexity of conjunctive queries with functional dependencies
From MaRDI portal
Publication:778529
DOI10.1007/S00224-019-09937-9zbMATH Open1446.68052OpenAlexW2967222032WikidataQ127365199 ScholiaQ127365199MaRDI QIDQ778529FDOQ778529
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/
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
- Powers of tensors and fast matrix multiplication
- Query evaluation via tree-decompositions
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- On the Desirability of Acyclic Database Schemes
- On the complexity of database queries
- On the complexity of hard enumeration problems
- Sorting, linear time and the satisfiability problem
- Incremental delay enumeration: space and time
- 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
- Title not available (Why is that?)
- Tight hardness for shortest cycles and paths in sparse graphs
Cited In (12)
- On the Complexity of Insertion Propagation with Functional Dependency Constraints
- A glimpse on constant delay enumeration (invited talk)
- Title not available (Why is that?)
- Enumeration complexity of poor man's propositional dependence logic
- Efficient enumeration for conjunctive queries over X-underbar structures
- Enumeration complexity of logical query problems with second-order variables
- Computing supports of conjunctive queries on relational tables with functional dependencies
- Enumeration complexity of conjunctive queries with functional dependencies
- Removing additive structure in 3SUM-based reductions
- Semantically Acyclic Conjunctive Queries under Functional Dependencies
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- The complexity of acyclic conjunctive queries
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)
