# Is there a set theoretic way to look at SQL?

I have been learning about SQL and at times it feels like set theory. A statement like SELECT * FROM myTable is like a set $\{ x: x \in \text{myTable} \}$.

A table could be defined as any subset of the Cartesian product. We could define a table called zipcodes with a schema city STRING(30), state CHAR(2), zip INTEGER(5) then in set theory we could define the zipcodes stable as: $$zicodes \subseteq \text{cities} \times \text{states} \times \text{zips} \simeq \{a, \dots, Z\}^{30} \times \{a, \dots, Z\} \times \{1, \dots, 10^5\}$$ So any table is a subset of a cartesian product.

My theory has limitations, since you can't store all of $\mathbb{R}$ as a SQL database (e.g. by cantor diagonalization) since $|\mathbb{R}| > |\mathbb{Z}|$ in cardinality.

In any case, do any theories of SQL exist that compare it to set theory?

• The theory is that of a relational model, and it predates SQL. – Emil Jeřábek Jan 27 '16 at 12:52
• Actually, I think that SQL is usually described set-theoretically in terms of Relational Algebra; while the term relational model refers to an abstract data model, namely, the standard table/relations-based database management model (irrespective of the query language, e.g., SQL). Though indeed, both seemed to be developed by the same person, and so are intimately connected. – Iddo Tzameret Jan 27 '16 at 19:00

## 3 Answers

It is common wisdom that database field is firmly grounded in the two math disciplines: predicate logic and set theory. However, this is very fuzzy observation, and reality is more subtle.

The structure of the basic building block - relation - is described in set language, but that's about it. This is not really very insightful, because the whole mathematics is written in set language. The fact that probably caught your attention is that the foundation of SQL - relational algebra - has distinct Boolean flavor.

Please also note that SQL actually operates not with relations but multirelations which are bags(multisets) of tuples(rows). Therefore, its algebra is not a [boolean] algebra of sets. There were various attempts at rigorous theory of multirelations, with provenance semiring being the most recent development

A co-Relational Model of Data for Large Shared Data Banks by Erik Meijer and Gavin Bierman, http://queue.acm.org/detail.cfm?id=1961297

Good article describing SQL and No-SQL databases as categorical duals.

Consider doing a join operation on your data. You are doing nothing but a cross product on the data. This falls under relational algebra. Set operations are the most basic and vague way of looking at the query on hand.