HZHangdong Zhao

Hangdong Zhao

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Hangdong Zhao has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    FlowLog: Re-thinking Datalog for Fast and Extensible Static Analysis

    by Zhenghong Yu, Hangdong Zhao, Wanzhu Hou, Paraschos Koutris

  • Open Access

    Demo of SemWeave: Semantic Common Expressions for LLM-powered Query Processing

    by Tareq Mahmood, Venkatesh Emani, Hangdong Zhao, Shivaram Venkataraman

  • Open Access

    Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization

    by Hangdong Zhao, Austen Fan, Xiating Ouyang, Paraschos Koutris

    In this article, we study the complexity of evaluating Conjunctive Queries with negation ( \(\mathsf {CQ}^{\lnot }\) ). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower-bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation ( \(\mathsf {FAQ}^{\lnot }\) ). Such an algorithm achieves constant delay enumeration for the same class of queries but with a slightly increased preprocessing time, which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermann function is probably unavoidable for general semirings but can be removed when the semiring has a specific structure. Finally, we show an application of our results to computing the difference of CQs.


  • Open Access

    Space-Time Tradeoffs for Conjunctive Queries with Access Patterns

    by Hangdong Zhao, Shaleen Deep, Paraschos Koutris

    In this article, we investigate space-time tradeoffs for answering conjunctive queries with access patterns (CQAPs). The goal is to create a space-efficient data structure in an initial preprocessing phase and use it for answering (multiple) queries in an online phase. Previous work has developed data structures that trades off space usage for answering time for queries of practical interest, such as the path and triangle query. However, these approaches lack a comprehensive framework and are not generalizable. Our main contribution is a general algorithmic framework for obtaining space-time tradeoffs for any CQAP. Our framework builds upon the PANDA algorithm and tree decomposition techniques. We demonstrate that our framework captures all state-of-the-art tradeoffs that were independently produced for various queries. Furthermore, we show surprising improvements over the state-of-the-art tradeoffs known in the existing literature for reachability queries.


  • Open Access

    Circuit Bounds for Conjunctive Queries with Self-joins

    by Austen Z. Fan, Paraschos Koutris, Hangdong Zhao

    In this paper, we study circuit size bounds for Conjunctive Queries (CQs) under different semiring semantics. Recent work established tight bounds for self-join-free CQs over the tropical semiring, among other results [16]. Here, we extend these results in two main directions. First, we prove a lower bound for any self-join-free CQ over the Boolean semiring by extending Razborov and Alon-Boppana's classic lower bound result for the k -clique problem [1, 38]. Second, we characterize the circuit complexity of CQs with self-joins by relating them to appropriate self-join free CQs. Interestingly, such correspondence crucially depends on the underlying semiring. To achieve this result, we present a novel technique of investigating the circuit complexity of a CQ with self-joins through the lens of endomorphisms.

  • Open Access

    Output-sensitive Conjunctive Query Evaluation

    by Shaleen Deep, Hangdong Zhao, Austen Z. Fan, Paraschos Koutris

    Join evaluation is one of the most fundamental operations performed by database systems and arguably the most well-studied problem in the Database community. A staggering number of join algorithms have been developed, and commercial database engines use finely tuned join heuristics that take into account many factors including the selectivity of predicates, memory, IO, etc. However, most of the results have catered to either full join queries or non-full join queries but with degree constraints (such as PK-FK relationships) that makes join evaluation easier. Further, most of the algorithms are also not output-sensitive. In this paper, we present a novel, output-sensitive algorithm for the evaluation of acyclic Conjunctive Queries (CQs) that contain arbitrary free variables. Our result is based on a novel generalization of the Yannakakis algorithm and shows that it is possible to improve the running time guarantee of Yannakakis algorithm by a polynomial factor. Importantly, our algorithmic improvement does not depend on the use of fast matrix multiplication, as a recently proposed algorithm does. The application of our algorithm recovers known prior results and improves on known state-of-the-art results for common queries such as paths and stars. The upper bound is complemented with a matching lower bound for star queries, a restricted subclass of acyclic CQs, and a family of cyclic CQs conditioned on two variants of the k -clique conjecture.


  • Open Access

    Tight Bounds of Circuits for Sum-Product Queries

    by Austen Z. Fan, Paraschos Koutris, Hangdong Zhao

    In this paper, we ask the following question: given a Boolean Conjunctive Query (CQ), what is the smallest circuit that computes the provenance polynomial of the query over a given semiring? We answer this question by giving upper and lower bounds. Notably, it is shown that any circuit F that computes a CQ over the tropical semiring must have size log |F| ≥ (1-ε) · da-entw for any ε >0, where da-entw is the degree-aware entropic width of the query. We show a circuit construction that matches this bound when the semiring is idempotent. The techniques we use combine several central notions in database theory: provenance polynomials, tree decompositions, and disjunctive Datalog programs. We extend our results to lower and upper bounds for formulas (i.e., circuits where each gate has outdegree one), and to bounds for non-Boolean CQs.


  • Open Access

    Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization

    by Hangdong Zhao, Austen Z. Fan, Xiating Ouyang, Paraschos Koutris

    In this paper, we study the complexity of evaluating Conjunctive Queries with negation (\cqneg). First, we present an algorithm with linear preprocessing time and constant delay enumeration for a class of CQs with negation called free-connex signed-acyclic queries. We show that no other queries admit such an algorithm subject to lower-bound conjectures. Second, we extend our algorithm to Conjunctive Queries with negation and aggregation over a general semiring, which we call Functional Aggregate Queries with negation (\faqneg). Such an algorithm achieves constant delay enumeration for the same class of queries but with a slightly increased preprocessing time, which includes an inverse Ackermann function. We show that this surprising appearance of the Ackermmann function is probably unavoidable for general semirings but can be removed when the semiring has a specific structure. Finally, we show an application of our results to computing the difference of CQs.


  • Open Access

    Evaluating Datalog over Semirings: A Grounding-based Approach

    by Hangdong Zhao, Shaleen Deep, Paraschos Koutris, Sudeepa Roy, Val Tannen

    Datalog is a powerful yet elegant language that allows expressing recursive computation. Although Datalog evaluation has been extensively studied in the literature, so far, only loose upper bounds are known on how fast a Datalog program can be evaluated. In this work, we ask the following question: given a Datalog program over a naturally-ordered semiring σ, what is the tightest possible runtime? To this end, our main contribution is a general two-phase framework for analyzing the data complexity of Datalog over σ: first ground the program into an equivalent system of polynomial equations (i.e. grounding) and then find the least fixpoint of the grounding over σ. We present algorithms that use structure-aware query evaluation techniques to obtain the smallest possible groundings. Next, efficient algorithms for fixpoint evaluation are introduced over two classes of semirings: (1) finite-rank semirings and (2) absorptive semirings of total order. Combining both phases, we obtain state-of-the-art and new algorithmic results. Finally, we complement our results with a matching fine-grained lower bound.


  • Open Access

    Space-Time Tradeoffs for Conjunctive Queries with Access Patterns

    by Hangdong Zhao, Shaleen Deep, Paraschos Koutris

    In this paper, we investigate space-time tradeoffs for answering conjunctive queries with access patterns (CQAPs). The goal is to create a space-efficient data structure in an initial preprocessing phase and use it for answering (multiple) queries in an online phase. Previous work has developed data structures that trades off space usage for answering time for queries of practical interest, such as the path and triangle query. However, these approaches lack a comprehensive framework and are not generalizable. Our main contribution is a general algorithmic framework for obtaining space-time tradeoffs for any CQAP. Our framework builds upon the PANDA algorithm and tree decomposition techniques. We demonstrate that our framework captures all state-of-the-art tradeoffs that were independently produced for various queries. Further, we show surprising improvements over the state-of-the-art tradeoffs known in the existing literature for reachability queries.