Mahmoud Abo Khamis ; Hung Q. Ngo ; Dan Suciu - PANDA: Query Evaluation in Submodular Width

theoretics:13722 - TheoretiCS, April 30, 2025, Volume 4 - https://doi.org/10.46298/theoretics.25.12
PANDA: Query Evaluation in Submodular WidthArticle

Authors: Mahmoud Abo Khamis ORCID; Hung Q. Ngo ORCID; Dan Suciu ORCID

    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 depending on both the type of statistics on input relations and the query plans that they support. This motivated the search for algorithms that can compute the output of a join query in times that are bounded by the corresponding information-theoretic bounds. In this paper, we describe PANDA, an algorithm that takes a Shannon-inequality that underlies the bound, and translates each proof step into an algorithmic step corresponding to some database operation. PANDA computes answers to a conjunctive query in time given by the the submodular width plus the output size of the query. The version in this paper represents a significant simplification of the original version [ANS, PODS'17].


    Volume: Volume 4
    Published on: April 30, 2025
    Accepted on: February 28, 2025
    Submitted on: June 5, 2024
    Keywords: Computer Science - Databases,Computer Science - Information Theory

    Consultation statistics

    This page has been seen 6 times.
    This article's PDF has been downloaded 1 times.