5 citations · 6 across the 6 of their papers we have counts for
8 papers · 1 filter
Guanaco: A Global-Uniformity Algorithm for Near-Submodular-Width Conjunctive Query Evaluation
Mahmoud Abo Khamis, Hubie Chen
We present Guanaco, an algorithm for performing conjunctive query evaluation where, for each Boolean conjunctive query, and positive epsilon, the algorithm achieves polynomial time…
Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
Mahmoud Abo Khamis, Hubie Chen
The submodular width is a complexity measure of conjunctive queries (CQs), which assigns a nonnegative real number, subw(Q), to each CQ Q. An existing algorithm, called PAND, perfo…
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…
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…