How to write complex SQL queries with universal quantification
As you all know, a disadvantage of SQL is the lack of the universal quantifier construct; so when you need to write a complex SQL query, there are two ways to proceed:
- write something that feels correct and pray it works;
- translate the query from English to logic, then to SQL.
Before diving in, it’s essential to recall the following equivalences:
- Implication: (p → q) ≡ (¬p ∨ q)
- Universal quantification: ∀x f(x) ≡ ¬∃x ¬f(x)
- Double negation: ¬¬p ≡ p
- De Morgan’s laws: ¬(p ∧ q) ≡ (¬p ∨ ¬q) and ¬(p ∨ q) ≡ (¬p ∧ ¬q)
The process is made by three steps: conversion from English to logic, then simplifying the logic formula using the previous equivalences following the order in which they are written, then conversion to SQL.
Example
The example is based on a database structure representing rivers, seas and states. A river can pass in various states before going into a sea.
The underlined attributes are the primaries keys and the * is used to denote the foreign keys.
The query is: find the seas such that all the rivers that flow into that sea cross a shared (in common) state.
We use s for the sea, st for the state and r for the river. So the query becomes: find the seas s such that they satisfy the formula:
From this formula, we apply the four equivalences above, starting from the implication and universal quantification, then applying De Morgan and double negation. Sometimes the steps need to be used more than once (like the elimination of the double negation). If you’re good with logic, you will probably find some shortcuts changing the order of application of the equivalences.
Applying the steps for the example:
From the last formula, we can build the SQL query; note that cross is a table, so what we are asking is that a particular entry doesn’t exist.
So the query becomes: find the seas such that it exists a state such that it doesn’t exist, a river that flows into that sea and the river doesn’t cross the state. The result of the query is the set:
Now it’s possible to translate it in SQL:
Source: Writing Complex SQL Queries that Require Universal Quantifiers by Jalal Kawash
