Polygon : Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation Search

Pinhan Zhao, Yuepeng Wang, Xinyu Wang · 2025

Read Polygon : Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation Search by Pinhan Zhao, Yuepeng Wang, Xinyu Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-06542.txt.

Introduction

Pinhan Zhao, Yuepeng Wang, and Xinyu Wang present Polygon, a reasoning engine for the database language SQL, in a 2025 paper. The engine builds one input table that makes several queries produce outputs with a wanted property. That trick can prove two queries differ or sort out which query a user meant.

Polygon reasons about a trimmed version of each query, covering only part of its behavior, which keeps the work light and aware of query meaning. A fixed trim could miss the key case, so the engine searches over a family of trims that together cover all behavior, restoring completeness. On more than thirty thousand test tasks across two uses, Polygon beat all prior techniques by a clear margin. The result makes automated SQL checking faster and more reliable.

Catalog record

CREATORPinhan Zhao, Yuepeng Wang, Xinyu Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE157 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-06542

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Polygon : Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation Search Pinhan Zhao, Yuepeng Wang, Xinyu Wang Abstract . We present a novel symbolic reasoning engine for SQL which can efficiently generate an input I I for n n queries P 1 , ⋯ , P n P_{1},\cdots,P_{n} , such that their outputs on I I satisfy a given property (expressed in SMT). This is useful in different contexts, such as disproving equivalence of two SQL queries and disambiguating a set of queries. Our first idea is to reason about an under-approximation of each P i P_{i} —that is, a subset of P i P_{i} ’s input-output behaviors. While it makes our approach both semantics-aware and lightweight, this idea alone is incomplete (as a fixed under-approximation might miss some behaviors of interest). Therefore, our second idea is to perform search over an expressive family of under-approximations (which collectively cover all program behaviors of interest), thereby making our approach complete. We have implemented these ideas in a tool, Polygon , and evaluated it on over 30,000 benchmarks across two tasks (namely, SQL equivalence refutation and query disambiguation). Our evaluation results show that Polygon significantly outperforms all prior techniques. DOI: 10.1145/3729303 Journal: PACMPL Volume: 9 PLDI 200 6 CCS: Theory of computation Automated reasoning CCS: Theory of computation Program reasoning CCS: Software and its engineering Formal methods 1. Introduction The general problem we study in this paper is the following. Given n programs P_{1},\cdots,P_{n} , how to generate an input I such that their outputs on I satisfy a given property C (which is expressed as an SMT formula over variables y_{1},\cdots,y_{n} ). That is, C\big[y_{1}\mapsto P_{1}(I),\cdots,y_{n}\mapsto P_{n}(I)\big] is true. This problem can be viewed as a form of “test input generation” task, which can be instantiated to different applications with different application conditions C . One example application is to disprove equivalence of two programs, with C being simply y_{1}\neq y_{2} . Another is program disambiguation—e.g., find I that can divide n programs into disjoint groups, such that: (i) programs within the same group return the same output given I , while (ii) outputs of those from different groups are distinct. Finding such distinguishing inputs is crucial for example-based program synthesis ( Jha et al., 2010 ; Mayer et al., 2015 ; Ji et al., 2020 ) Instantiation to SQL. We focus on one instantiation of this general problem, where P_{i} ’s are written in SQL (which is a widely used domain-specific language). The aforementioned applications still hold—generating counterexamples to refute SQL equivalence is useful in many ways ( Chandra et al., 2015 ; Chandra et al., 2019 ; He et al., 2024 ; Chu et al., 2017b ) , and query disambiguation is critical for example-based SQL query synthesis ( Brancas et al., 2022 ; Manquinho and Martins, 2024 ; Wang et al., 2017a ; Wang et al., 2017b ) . State-of-the-art. To the best of our knowledge, no existing work can efficiently generate such inputs for an expressive subset of SQL. While conventional testing-based approaches—e.g., those based on fuzzing ( Coelho, 2013 ) and evolutionary search ( Castelein et al., 2018 ) —can generate many inputs quickly, they do not consider the (highly complex) semantics of SQL. As a result, they fall short of capturing subtle differences across queries, which is crucial for generating distinguishing inputs. While some works (e.g., XData ( Chandra et al., 2015 ; Chandra et al., 2019 ) ) consider basic semantic information (such as join and selection conditions), they support a very limited subset of SQL and are specialized in equivalence checking. On the other end of the spectrum, techniques based on formal methods ( Veanes et al., 2010 ; Chu et al., 2017b ; Wang et al., 2018 ; He et al., 2024 ; Zhao et al., 2024 ) perform symbolic reasoning—typically by encoding complete query semantics in SMT. While boiling the problem down to SMT solving, these methods often create large SMT formulas that are computationally expensive to solve, especially for problems that involve many large queries with complex semantics. For instance, for operators like group-by and aggregation, fully encoding all grouping possibilities would cause an exponential blow-up in the resulting formula’s size. Key challenge. While clearly critical to consider some semantic information, it would significantly slow down the reasoning process if we consider the full semantics. The core challenge hence is how to take into account SQL semantics in a way that is lightweight without hindering completeness. Prior works fall into two extremes of the spectrum: either (1) fully encoding semantics for all inputs thus heavyweight and not scalable, or (2) fast by considering no or very little semantic information but at the cost of missing inputs of interest frequently (i.e., incomplete). Our key insight. Our key insight is to reason about an under-approximation (or UA) of the program. This, while much faster than analyzing the full program semantics, is incomplete. Therefore, we also perform search over an expressive family of UAs (which collectively cover all program behaviors of interest), thereby making our entire approach complete. Specifically, given P_{1},\cdots,P_{n} and application condition C , we begin with a UA for each P_{i} which encodes a subset \mathbb{O}_{i} of reachable outputs for P_{i} (together with their corresponding inputs). Here, an output is reachable, if it can indeed be returned by the program on an input ( O’Hearn, 2019 ) . We then check if there exist O_{1}\in\mathbb{O}_{1},\cdots,O_{n}\in\mathbb{O}_{n} such that C[y_{1}\mapsto O_{1},\cdots,y_{n}\mapsto O_{n}] is true. If so, we can easily solve our problem by deriving the corresponding input given the under-approximate semantics (or UA semantics) of P_{1},\cdots,P_{n} . Otherwise, we try again but use a different choice of UA. This process terminates, when a desired UA is found or no such UA can be found for the given family of UAs. Below we briefly summarize the key challenges and our solutions. Section 2 will further illustrate our approach using a concrete example. Under-approximating SQL query semantics. The first challenge is how to under-approximate a query P . Our idea is to encode P ’s UA semantics in an SMT formula \Psi whose models correspond to genuine input-output pairs of P . In other words, \Psi always encodes reachable outputs. On the other hand, not all reachable outputs are necessarily encoded by \Psi ; therefore \Psi is an under-approximation. Our first novelty lies in a compositional method to build \Psi for P , by conjoining \Psi_{i} for each AST node v_{i} of P . Here, each \Psi_{i} under-approximates the semantics of the query operator F at v_{i} . Defining a family of under-approximations. This compositional encoding method lends itself well to addressing our second challenge—how to define a family of UAs for a query P ? Our idea is to first define a family \mathcal{U}_{F} of UAs for each query operator F in the query language, which collectively covers all inputs of interest to F . Then, we define a UA map M for P , which maps each AST node v_{i} in P to some UA in \mathcal{U}_{\textit{op}(v_{i})} . Each UA map M can be encoded into an SMT formula \Psi:=\textit{Encode}(M) , by taking the conjunction of the encodings of M ’s entries. We

Read the complete text