Data Provenance Aggregation and Structural Descriptors for Query-Template Identification

Paulo Pintor; Rogério Costa; José Moreira

cs.DBOct 15, 2026

Data Provenance Aggregation and Structural Descriptors for Query-Template Identification

Authors: Paulo Pintor, Rogério Costa, José Moreira

Organizations: IEETA, University of Aveiro, Aveiro, Portugal . · CISUC, DEI, University of Coimbra, Coimbra, Portugal .

Abstract

Runtime query similarity identification supports several activities, including workload analysis, identifying recurring behaviour, auditing, debugging, and anomaly detection. Existing methods for evaluating query similarity mostly rely on SQL text, execution plans, or result values but do not account for input data or how results are derived during query execution. This paper proposes a novel approach using data provenance for query-template identification. We construct query-level profiles that capture explicit data dependencies, occurrence frequencies, and structural properties by aggregating tuple-level Lineage and Why-provenance across entire query results. We also derive Provenance Structural Descriptors (PSD), which summarise these profiles using a small set of numerical features. We evaluate our proposals using these profiles to identify query templates over $12{,}500$ distinct query instances generated from parametrised TPC-DS query templates. The experimental evaluation shows that query templates can be identified solely from their provenance footprints, and that accuracy improves as more historical data becomes available. It also shows that PSD achieve high classification accuracy with limited training history and low test-processing cost.

Figures & tables

Cust	Segment	Token
$c_{1}$	Retail	$t_{1}$
$c_{2}$	Retail	$t_{2}$

Figure 1: Database instance for the running example.

Status	Why	Lineage
Open	$\{\{t_{1},t_{3}\},\{t_{2},t_{4}\}\}$	$\{t_{1},t_{2},t_{3},t_{4}\}$
Shipped	$\{\{t_{1},t_{5}\}\}$	$\{t_{1},t_{5}\}$

Figure 2: Result of

Q_{1}

with Why-provenance and Lineage.

Classifier	Metric	PSD	Lineage	Atomic Why	Token TF	Witness TF	Blocked Why
1-NN	Acc	0.9928	0.9968	0.9672	0.9272	0.8796	0.9958
	F1	0.9928	0.9968	0.9671	0.9175	0.8623	0.9958
	Mean test time (ms/execution)	0.0853	283.6	192.6	7.238	5.031	4315.7
5-NN	Acc	0.9836	0.9972	0.9452	0.8908	0.8000	0.9968
	F1	0.9836	0.9972	0.9462	0.8706	0.7686	0.9968
	Mean test time (ms/execution)	0.0969	283.2	192.6	7.123	5.008	5949.4

Table 1: Classification effectiveness and mean test-processing time with

10{,}000

training and

2{,}500

test executions.

Panel of Figure 3 — Figure 3: Effect of training-history size.

Panel of Figure 4 — Figure 4: SHAP importance of PSD descriptors.

Classifier	PSD-Counts	PSD-Full	PSD-Reduced
XGBoost	0.9944	0.9988	0.9988
Random Forest	0.9976	0.9980	0.9980
$5$ -NN	0.9932	0.9836	0.9844
Logistic Regression	0.8311	0.9139	0.9139

Table 2: Macro-F1 for the three PSD variants.

Data Provenance

Data provenance tracks where data and AI outputs come from, how they are transformed, and what evidence supports their attribution and use.

See all 191 papers

Demonstrating GenDB: Instance-Optimized and Customized Query Processing Code Generation via LLM Agents
Jul 22, 2026Jiale Lao, Immanuel TrummerCode Generation Agentic Code Generation
Cornell University
BIRD-History: A Benchmark for History-Driven Text-to-SQL with Fine-Grained Knowledge Annotations
Aug 29, 2026Yunfan Zhou, Qiming Shi, Yizhou Yang +2Text-to-SQL Text-to-SQL Evaluation
State Key Lab of CAD&CG, Zhejiang University · School of Software Technology, Zhejiang University
Schema-Free Text-to-SQL: Learning Enterprise Database Structure from Query Logs
Oct 24, 2026Ömer Faruk Akgül, Nikhil Kapahi, Prajit Reddy MuppidiText-to-SQL Graph Retrieval-Augmented Generation
University of Southern California · Amazon

Jul 22, 2026J/K move · Enter open · S save

Demonstrating GenDB: Instance-Optimized and Customized Query Processing Code Generation via LLM Agents

Jiale Lao, Immanuel Trummer

Cornell University

Code Generation Agentic Code Generation Database Systems LLM Code Generation

Open paper AskPDF arXiv

Traditional query processing engines require continuous development and extensions to support new techniques and user requirements, and in some cases, entirely new systems must be built from scratch. However, these engines are difficult to extend due to their internal complexity, and building new systems demands significant engineering effort and cost. To address this, we demonstrate GenDB, a generative query engine that shifts query processing from manually engineered systems to query processing code generation driven by Large Language Models (LLMs). An early prototype of GenDB uses LLM agents to generate instance-optimized query execution code tailored to specific data, workloads, and hardware resources. This prototype suits offline code generation for repetitive, templated queries, since the upfront generation cost amortizes over many executions and correctness can be ensured through extensive fuzz testing and manual inspection. For ad-hoc queries, GenDB can work with a traditional DBMS in a hybrid architecture: the DBMS handles one-off queries, while GenDB speeds up frequent SQL templates. Our demonstration allows users to (1) visually and interactively explore how GenDB analyzes workloads, profiles hardware resources and underlying data, produces query plans, generates code based on them, and finally uses an optimizer to iteratively achieve a correct and efficient implementation; (2) use visual inspection and analysis to gain qualitative insights into why GenDB produces code that achieves significantly better performance than state-of-the-art query engines on two benchmarks: TPC-H and a newly constructed benchmark designed to reduce potential data leakage from LLM training data; and (3) upload their own data and queries to explore GenDB with different LLMs and query patterns.

Abstract

Data Provenance

Explore similar work

Demonstrating GenDB: Instance-Optimized and Customized Query Processing Code Generation via LLM Agents

BIRD-History: A Benchmark for History-Driven Text-to-SQL with Fine-Grained Knowledge Annotations

Schema-Free Text-to-SQL: Learning Enterprise Database Structure from Query Logs