Enumeration complexity of conjunctive queries with functional dependencies

DOI10.1007/s00224-019-09937-9zbMath1446.68052OpenAlexW2967222032WikidataQ127365199 ScholiaQ127365199MaRDI QIDQ778529

Markus Kröll, Nofar Carmeli

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

complexityenumerationfunctional dependenciesconjunctive queries

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of database queries
• Sorting, linear time and the satisfiability problem
• Incremental delay enumeration: space and time
• A complexity theory for hard enumeration problems
• On the Desirability of Acyclic Database Schemes
• Powers of tensors and fast matrix multiplication
• Query evaluation via tree-decompositions
• On Acyclic Conjunctive Queries and Constant Delay Enumeration

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