Back to search

Institutional Repository of Vilnius University

Modelling and formal verification of spes query equivalence tool using isabelle/hol /

Abstract

dc:description

SQL query equivalence (determining whether two SQL queries produce the same result for every possible database) is an important problem with applications in query optimization, automated grading and duplicate elimination in data pipelines. Several solvers for this problem exist, however not every solver has been formally verified. A bug in such a solver could lead to silent data corruption, making formal verification a worthwhile investment. SPES is a symbolic SQL query equivalence solver that supports bag semantics and NULL values. It works by constructing a symbolic representation of bijection between two queries and proving that bijection is an identity function. The original SPES paper provides a semi-formal soundness argument, but no machine-checked proof. In this work, the author develops a formal mathematical model for a trimmed-down version of SPES supporting Table, Select, Project and Union queries, formalizes it in Isabelle/HOL using multiset-based table representation and deep embedding for first-order logic formulas, and successfully proves the soundness of the modelled version of SPES. The thesis covers the modelling decisions, iterative modelling process and the resulting Isabelle/HOL proof.

Degree

thesis:*
Grantor dc:publisher
Institutional Repository of Vilnius University
Year dc:date
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Piatrashka, Kanstantinas,

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • info:eu-repo/semantics/openAccess
Language dc:language
eng

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Piatrashka, Kanstantinas,. Modelling and formal verification of spes query equivalence tool using isabelle/hol /. Institutional Repository of Vilnius University, 2026. https://repository.vu.lt/VU:ELABAETD308338306&prefLang=en_US