<p>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.</p>

<p>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.</p>

<p>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 <a href="https://www.google.com/search?q=provenance%20semirings&amp;oq=provenance%20semiring&amp;aqs=chrome.0.0j69i57.4959j0j7&amp;sourceid=chrome&amp;es_sm=93&amp;ie=UTF-8#q=provenance%20semiring%20bag%20semantics" rel="nofollow">provenance semiring</a> being the most recent development    </p>

CC BY-SA 3.0
2016-02-11T21:04:24.380Z
2016-02-11T21:04:24.380Z
Tegiri Nenashi
<p>A co-Relational Model of Data for Large Shared Data Banks by Erik Meijer and Gavin Bierman, <a href="http://queue.acm.org/detail.cfm?id=1961297" rel="nofollow">http://queue.acm.org/detail.cfm?id=1961297</a></p>

<p>Good article describing SQL and No-SQL databases as categorical duals.</p>

CC BY-SA 3.0
2016-03-25T07:08:12.573Z
2016-03-25T07:08:12.573Z
Chad Brewbaker
<p>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.</p>

CC BY-SA 3.0
2016-03-25T05:30:20.047Z
2016-03-25T05:30:20.047Z
Supriya S
<p>You say &quot;<em>A table could be defined as any subset of the Cartesian product.</em>&quot;
NO! A better statement would be  :</p>
<p>A <strong>relation</strong> can be defined as any subset of the Cartesian product.</p>
<p>A table is not systematically a relation, but some tables are relations. A relation must have:</p>
<ol>
<li><p>A collection of attribute having each a domain and no &quot;NULL&quot; atomic value</p>
</li>
<li><p>A key compound of one or more attribute</p>
</li>
</ol>
<p>If a table has a NULL value, this is not a relation.</p>
<p>Without a key, a table is not a relation.</p>
<p>If any attribute is compound of subvalues the table is not a relation.</p>
<p>Your cartesian product is not a good example because some zip codes can be shared by many cities. This is the case in France...</p>
<p>A most simple example would be chess playing. The chess board is made up of rows and columns.</p>
<p>Let R be the set of chess board rows having values as {1, 2, 3, 4, 5, 6, 7, 8}</p>
<p>Let C be the set of chess board columns having values as {a, b, c, d, e, f, g, h}</p>
<p>The the cartesian product of RxC define the squares of the chess game that we will name S and contains { (A,1), (A, 2), ... (H, 8) }</p>

CC BY-SA 4.0
2024-02-06T20:24:18.763Z
2024-02-12T09:26:43.253Z
2024-02-12T09:26:43.253Z
SQLpro
<p>I have been learning about SQL and at times it feels like set theory.  A statement like <code>SELECT * FROM myTable</code> is like a set $\{ x: x \in \text{myTable} \}$.</p>

<p>A table could be defined as any subset of the Cartesian product.  We could define a table called <code>zipcodes</code> with a schema <code>city STRING(30), state CHAR(2),  zip INTEGER(5)</code>  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.</p>

<p>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}| &gt; |\mathbb{Z}|$ in cardinality.  </p>

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

CC BY-SA 3.0
2016-01-27T12:52:30.293Z
The theory is that of a [relational model](https://en.wikipedia.org/wiki/Relational_model), and it predates SQL.
Emil Jeřábek
CC BY-SA 3.0
2016-01-27T19:00:40.993Z
Actually, I think that SQL is usually described set-theoretically in terms of [**Relational Algebra**](https://en.wikipedia.org/wiki/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
<db.databases><set-theory>
Is there a set theoretic way to look at SQL?
john mangual
# Is there a set theoretic way to look at SQL?

(Asked by: username_0 on 2016-01-27)

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?

**Tags:** db.databases, set-theory

> **Comments:**
> **username_1**: The theory is that of a [relational model](https://en.wikipedia.org/wiki/Relational_model), and it predates SQL.  
> **username_2**: Actually, I think that SQL is usually described set-theoretically in terms of [**Relational Algebra**](https://en.wikipedia.org/wiki/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.  

---

## 4 answers

### Answer by username_3 on 2016-02-11. Score: 3

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](https://www.google.com/search?q=provenance%20semirings&oq=provenance%20semiring&aqs=chrome.0.0j69i57.4959j0j7&sourceid=chrome&es_sm=93&ie=UTF-8#q=provenance%20semiring%20bag%20semantics) being the most recent development


---

### Answer by username_4 on 2016-03-25. Score: 1

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.


---

### Answer by username_5 on 2016-03-25. Score: -2

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.


---

### Answer by username_6 on 2024-02-06. Score: -2

You say "*A table could be defined as any subset of the Cartesian product.*"
NO! A better statement would be :

A **relation** can be defined as any subset of the Cartesian product.

A table is not systematically a relation, but some tables are relations. A relation must have:

1. A collection of attribute having each a domain and no "NULL" atomic value
2. A key compound of one or more attribute

If a table has a NULL value, this is not a relation.

Without a key, a table is not a relation.

If any attribute is compound of subvalues the table is not a relation.

Your cartesian product is not a good example because some zip codes can be shared by many cities. This is the case in France...

A most simple example would be chess playing. The chess board is made up of rows and columns.

Let R be the set of chess board rows having values as {1, 2, 3, 4, 5, 6, 7, 8}

Let C be the set of chess board columns having values as {a, b, c, d, e, f, g, h}

The the cartesian product of RxC define the squares of the chess game that we will name S and contains { (A,1), (A, 2), ... (H, 8) }


---

