Conjunctive queries are one of the most common class of queries used in database
systems, and the best studied in the literature. A seminal result of Grohe, Schwentick, and …

Sketching is a powerful dimensionality reduction technique for accelerating algorithms for
data analysis. A crucial step in sketching methods is to compute a subspace embedding …

We propose a new method for estimating the number of answers OUT of a small join query
Q in a large database D, and for uniform sampling over joins. Our method is the first to satisfy …

We study the fixed-parameter tractability of the following fundamental problem: given two
directed graphs H→ and G→, count the number of copies of H→ in G→. The standard …

We investigate how to efficiently compute the difference result of two (or multiple)
conjunctive queries, which is the last operator in relational algebra to be unraveled. The …

We study the complexity of answer counting for ontology-mediated queries and for querying
under constraints, considering conjunctive queries and unions thereof (UCQs) as the query …

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# …

Counting the number of answers to conjunctive queries is a fundamental problem in
databases that, under standard assumptions, does not have an efficient solution. The issue …

Sketching is a powerful technique which compresses high-dimensional datasets into lower-
dimensional sketches, while preserving properties of interest. Sampling is a quintessential …