4 papers
Compiling Linear Datalog to SQL for Program Analysis
Amir Shaikhha, Anna Herlihy, Hung Ngo
Datalog is a declarative query language that has proven highly effective for expressing static program analyses. Although Datalog has deep roots in database theory, most recent adv…
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…