Derivation-SQL: A Cost-Effective Graph-Based Framework for Text-to-SQL

Text-to-SQL enables users to query relational databases in natural language and has broad applications. However, existing retrieval approaches based on question semantics may ignore the derivation relationships among SQL queries. In contrast, structure-based approaches that use predicted SQL require an additional generation step, increasing inference cost. To address these issues, we propose Derivation-SQL, a cost-effective Text-to-SQL framework that uses SQL derivation graphs to retrieve structurally relevant examples directly from natural language questions. We first construct an SQL derivation graph (DG) by decomposing training SQL queries into subqueries and connecting queries through derivation relationships. This process also expands the pool of few-shot candidates. We then design a DG-based embedding network (DGE) that encodes text semantics and SQL derivation relationships. The network encodes examples offline and maps natural language questions to the same embedding space online. A tailored pipeline with improved prompts seamlessly integrates these components into an end-to-end solution. Experiments on BIRD and Spider show that Derivation-SQL achieves competitive execution accuracy with low token consumption, reaching a Pareto-optimal balance between accuracy and cost. With GPT-4o, Derivation-SQL achieves execution accuracy of 72.56% on BIRD-Dev, which costs less than half the token usage of other representative approaches.