5 citations · 9 across the 10 of their papers we have counts for
10 papers · 1 filter
Query Optimization and Evaluation via Information Theory: A Tutorial
Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu
Database theory is exciting because it studies highly general and practically useful abstractions. Conjunctive query (CQ) evaluation is a prime example: it simultaneously generaliz…
Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries
Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara +2
We present an output-sensitive algorithm for evaluating an acyclic Conjunctive Regular Path Query (CRPQ). Its complexity is written in terms of the input size, the output size, and…
PANDAExpress: a Simpler and Faster PANDA Algorithm
Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu
PANDA is a powerful generic algorithm for answering conjunctive queries (CQs) and disjunctive datalog rules (DDRs) given input degree constraints. In the special case where degree…
Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries
Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara +3
Conjunctive Regular Path Queries, or CRPQs for short, are an essential construct in graph query languages. In this paper, we propose the first output-sensitive algorithm for evalua…
Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation
Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu +1
Estimating the cardinality of the output of a query is a fundamental problem in database query processing. In this article, we overview a recently published contribution that casts…
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…
Fast Matrix Multiplication meets the Submodular Width
Mahmoud Abo Khamis, Xiao Hu, Dan Suciu
One fundamental question in database theory is the following: Given a Boolean Conjunctive Query (BCQ) Q, what is the best complexity for computing the answer to Q in terms of the i…
PANDA: Query Evaluation in Submodular Width
Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu
In recent years, several information-theoretic upper bounds have been introduced on the output size and evaluation cost of database join queries. These bounds vary in their power d…
Insert-Only versus Insert-Delete in Dynamic Query Evaluation
Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu +1
We study the dynamic query evaluation problem: Given a full conjunctive query Q and a sequence of updates to the input database, we construct a data structure that supports constan…