5 papers · 1 filter
Rerootable Hypertree Decompositions
Zhekai Jiang, Christoph Koch, Peter Lindner +2
Hypertree decompositions are a cornerstone in the theory of answering conjunctive queries efficiently. However, they are not yet widely adopted in practice. Problems related to, e.…
Size Bound-Adorned Datalog
Christian Fattebert, Zhekai Jiang, Christoph Koch +2
We introduce EDB-bounded datalog, a framework for deriving upper bounds on intermediate result sizes and the asymptotic complexity of recursive queries in datalog. We present an al…
The Space-Time Complexity of Sum-Product Queries
Kyle Deeds, Timo Camillo Merkl, Reinhard Pichler +1
While extensive research on query evaluation has achieved consistent improvements in the time complexity of algorithms, the space complexity of query evaluation has been largely ig…
Query Answering under Volume-Based Diversity Functions
Marcelo Arenas, Timo Camillo Merkl, Reinhard Pichler +1
When query evaluation produces too many tuples, a new approach in query answering is to retrieve a diverse subset of them. The standard approach for measuring the diversity of a se…
Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue
Marcelo Arenas, Timo Camillo Merkl, Reinhard Pichler +1
The set of answers to a query may be very large, potentially overwhelming users when presented with the entire set. In such cases, presenting only a small subset of the answers to…