9 papers
Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width
Matthias Lanzinger, Timo Camillo Merkl, Dan Suciu
We describe one explicit simple graph G on 32 vertices whose adaptive, normal, linear, entropic, and submodular widths are pairwise distinct. We compute all these widths exactly, e…
Convolution Sum-Product Queries
Kyle Deeds, Timo Camillo Merkl, Dan Suciu
We study query evaluation for an extension of sum-product queries (SPQ) that allows atoms with linear combinations of variables (e.g. ), which we call convolution…
From FPT Decision to FPT Enumeration
Nadia Creignou, Timo Camillo Merkl, Reinhard Pichler +1
Fixed-parameter tractable (FPT) algorithms have been successfully applied to many intractable problems -- with a focus on decision and optimization problems. Their aim is to confin…
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…
Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins
Kyle Deeds, Timo Camillo Merkl
In the last decade, various works have used statistics on relations to improve both the theory and practice of conjunctive query execution. Starting with the AGM bound which took a…
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…
Consistent Query Answering over SHACL Constraints
Shqiponja Ahmetaj, Timo Camillo Merkl, Reinhard Pichler
The Shapes Constraint Language (SHACL) was standardized by the World Wide Web as a constraint language to describe and validate RDF data graphs. SHACL uses the notion of shapes gra…
Diversity of Answers to Conjunctive Queries
Timo Camillo Merkl, Reinhard Pichler, Sebastian Skritek
Enumeration problems aim at outputting, without repetition, the set of solutions to a given problem instance. However, outputting the entire solution set may be prohibitively expen…