8 papers
Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations
Mahmoud Abo-Khamis, Eden Chmielewski, Andrei Draghici +2
We study the classical incremental view maintenance problem: Given a query and a database, maintain the query output under single-tuple updates (inserts or deletes) to the database…
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…
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…
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…
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…