10 citations · 17 across the 7 of their papers we have counts for
7 papers · 1 filter
A Unifying Algorithm for Hierarchical Queries
Mahmoud Abo Khamis, Jesse Comer, Phokion Kolaitis +2
The class of hierarchical queries is known to define the boundary of the dichotomy between tractability and intractability for the following two extensively studied problems about…
LpBound: Pessimistic Cardinality Estimation using -Norms of Degree Sequences
Haozhe Zhang, Christoph Mayer, Mahmoud Abo Khamis +2
Cardinality estimation is the problem of estimating the size of the output of a query, without actually evaluating the query. The cardinality estimator is a critical piece of a que…
Output-Sensitive Evaluation of Regular Path Queries
Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu +1
We study the classical evaluation problem for regular path queries: Given an edge-labeled graph and a regular path query, compute the set of pairs of vertices that are connected by…
Pessimistic Cardinality Estimation
Mahmoud Abo Khamis, Kyle Deeds, Dan Olteanu +1
Cardinality Estimation is to estimate the size of the output of a query without computing it, by using only statistics on the input relations. Existing estimators try to return an…
Convergence of Datalog over (Pre-) Semirings
Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler +2
Recursive queries have been traditionally studied in the framework of datalog, a language that restricts recursion to monotone queries over sets, which is guaranteed to converge in…
FAQ: Questions Asked Frequently
Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra
We define and study the Functional Aggregate Query (FAQ) problem, which encompasses many frequently asked questions in constraint satisfaction, databases, matrix operations, probab…
Joins via Geometric Resolutions: Worst-case and Beyond
Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré +1
We present a simple geometric framework for the relational join. Using this framework, we design an algorithm that achieves the fractional hypertree-width bound, which generalizes…