Institutional Repository of Vilnius University
Modelling and formal verification of spes query equivalence tool using isabelle/hol /
Abstract
dc:descriptionSQL 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 × 1Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- eng
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD308338306&prefLang=en_US