Showing cs.DMShow all
3 papers · 1 filter
cs.DM2023
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem…
cs.DM2023
The Weisfeiler-Leman Dimension of Conjunctive Queries
Andreas Göbel, Leslie Ann Goldberg, Marc Roth
The Weisfeiler-Leman (WL) dimension of a graph parameter is the minimum such that, if and are indistinguishable by the -dimensional WL-algorithm then $f(G_1)…
cs.DM2021
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the complexity of approximating the number of answers to a small query in a large database . We establish an exhaustive classification into tractable and…