4 papers
Listing Even Cycles Faster than the Submodular-Width Barrier
Vasileios Nakos, Hung Q. Ngo, Andreas Panayi
A classic result of Alon, Yuster, and Zwick (AYZ, Algorithmica 1997) shows that all -cycles in an -edge graph can be listed in time, where is the…
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…
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…
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…