4
$\begingroup$

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?

$\endgroup$
2
  • 9
    $\begingroup$ The theory is that of a relational model, and it predates SQL. $\endgroup$ Commented Jan 27, 2016 at 12:52
  • 9
    $\begingroup$ 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. $\endgroup$ Commented Jan 27, 2016 at 19:00

4 Answers 4

3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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) }

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.