A Formal Semantics of SQL Queries, Its Validation, and Applications

Summary: Defines and experimentally validates formal semantics for real-world basic SQL, including subqueries, set/bag operations, name binding, and nulls. Establishes bag/null-aware equivalence to relational algebra and proves SQL’s three-valued logic adds no expressive power. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hfb302ccc1e51243e
Venue: VLDB
Year: 2018
Pagerank: 7.0721776e-05
Overall Rank: 3,718 | 75.01%
DOI: 10.14778/3136610.3136613

Incoming Non-self Citations Over Time

Authors

1. Paolo Guagliardo (University of Edinburgh)
2. Leonid Libkin (University of Edinburgh)

BibTeX Citation

@article{guagliardo_vldb18,
        title = {{A Formal Semantics of SQL Queries, Its Validation, and Applications}},
        author = {Guagliardo, Paolo and Libkin, Leonid},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {1},
        pages = {27--39},
        doi = {10.14778/3136610.3136613},
        url = {https://doi.org/10.14778/3136610.3136613},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
419	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.0001854669
1,680	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB	9.9031411e-05
1,893	WeTune: Automatic Discovery and Verification of Query Rewrite Rules	2022	SIGMOD	9.4126198e-05
4,102	QED: A Powerful Query Equivalence Decider for SQL	2024	VLDB	6.8070264e-05
6,013	SQL Nulls and Two-Valued Logic	2023	PODS	5.9141967e-05
7,919	Semantic Conformance Testing of Relational DBMS	2025	VLDB	5.4269617e-05
8,060	Updating Graph Databases with Cypher	2019	VLDB	5.3963318e-05
11,033	An Extended Tutorial and Vocabulary for Relational Language Design in an Era of AI-Assisted Query Generation	2026	VLDB	4.9793485e-05
11,486	TypeQL: A Type-Theoretic & Polymorphic Query Language	2024	PODS	4.9793485e-05
11,547	Understanding and Reusing Test Suites Across Database Systems	2024	SIGMOD	4.9793485e-05
11,683	Querying Incomplete Numerical Data: Between Certain and Possible Answers	2023	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
790	Cosette: An Automated Prover for SQL	2017	CIDR	0.00013976438
2,454	Algebraic Properties of Bag Data Types	1991	VLDB	8.4431955e-05
5,802	Making SQL Queries Correct on Incomplete Databases: A Feasibility Study	2016	PODS	5.989635e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,130	On Relational Algebra With Marked Nulls	1984	PODS
2	13,330	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
3	12,782	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS
4	4,426	Languages for Relational Databases over Interpreted Structures	1997	PODS
5	6,724	Schema-free SQL	2014	SIGMOD
6	6,013	SQL Nulls and Two-Valued Logic	2023	PODS
7	5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS
8	1,680	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
9	8,300	Formal Semantics and Analysis of Object Queries	2003	SIGMOD
10	1,418	Null Values in Data Base Management: A Denotational Semantics Approach	1979	SIGMOD