Welcome to MathOverflow

Question

2

1

Are there some mathematical theories/theorems/... behind modern development of database management systems and in particular of SQL ?

I am refreshing my knowledge of these things which are quite down-to-earth "how to use" (create table ..., insert..., select * from ...), but I think some deeper understanding what is behind would be helpful.

In particular in Wikipedia one may find some relations with 3-valued logic:

Along with True and False, the Unknown resulting from direct comparisons with Null thus brings a fragment of three-valued logic to SQL. The truth tables SQL uses for AND, OR, and NOT correspond to a common fragment of the Kleene and Lukasiewicz three-valued logic (which differ in their definition of implication, however SQL defines no such operation).

But it is not very clear for me what it means and how deep it is ?

edited Feb 8 at 18:20

quid
12.9k●31●51

asked Feb 8 at 8:32

Alexander Chervov
7,093●1●16●41

	SQL is a language for implementing the relational model en.wikipedia.org/wiki/Relational_model , just as fortran is a language for implementing arithmetic. What computer scientists consider an important theoretical object is the relational model, not its implementations like SQL. The WP article has some discussion of Codd's ideas for three-valued and four-valued logic. – Ben Crowell Feb 8 at 15:25
	I changed the tag cs.db, as cs.something tags got generally removed a while ago; also the existing database-theory seems fine. – quid Feb 8 at 18:21
	what is not clear about 3-valued logic? – Emanuele Paolini Feb 9 at 18:38
	@ Emanuele Paolini how deep are these relations/ideas ? – Alexander Chervov Feb 10 at 7:38
	You could take a look at "Applied Mathematics for Database Professionals" by Lex de Haan and Toon Koppelaars. I have to confess that I skipped the "math part" at the beginning as I was interested only in its later chapters, but it is worth checking if you can find it in a library. Do not expect interesting theorems. [Lex de Haan was according to the other author an expert on 3-valued logic, but died before finishing writing the chapter about this topic. If I recall correctly, this unfinished chapter was added as an appendix.] – jp Feb 18 at 16:07

Mike Hord · Answer 1 · 2013-02-08 10:22:05Z UTC

3

Relational algebra might be of your interest.

answered Feb 8 at 10:22

Mike Hord
31●1

Thank you very much for yours suggestion ! It would be helpful if you can extend a bit your answer. – Alexander Chervov Feb 8 at 10:26

1

You might also look at Codd's theorem, which tells us that relational algebra is more or less first order logic – robibok Feb 8 at 11:40

Ron Hallam · Answer 2 · 2013-02-08 13:29:15Z UTC

If you google 'Theory of SQL' there are numerous references and one in particular refers to a PDF file.

But I think that the simplest way to look at it is to think in terms of what a database consists of:- 1) each table is a set containing unique data (sometimes with indices on the tables) 2) various tables many be linked by references.

SQL then generates the tuples relating to the specific query from the relevant tables, the actual processing is usually hedden by the DBMS.

So you need to look at Set Theory, Combinational Algorithms(Knuth) and Relational Theory.

As an aside I used SQL for some 20 years in a number of databases.

Hope that this helps.

Ron

David White · Answer 3 · 2013-02-18 15:30:26Z UTC

The course I took in Databases contained a large amount of deeper mathematical theory. It was taught by a mathematician turned computer scientist named Mike Rice at Wesleyan University, and notes/assignments used to be available online (but I can't find them any more). Anyway, the course textbook was Database: Principles, Programming, and Performance, Second Edition by Patrick O'Neil and Elizabeth O'Neil. The first chapter in particular is almost entirely math, and that's leads into relational algebra and then into table joins, etc. While developing the theory the book also teaches programming in SQL.

I really can't recommend this book highly enough. This was exactly the approach I needed as a mathematician trying to learn databases. After the course ended I did a summer job entailing a lot of work with databases and definitely felt my background was strong enough to do this work. I also lent the book to a friend who was transitioning from a math major to a job in databases and he felt the same way even though he was using SAS for that job.

S. Carnahan · Answer 4 · 2013-02-18 17:53:27Z UTC

David Spivak (who is an occasional contributor here) has done some work on categorical aspects of database management, and the creation of dictionaries between math world and the DB world that allow one to prove that certain operations are well-behaved in a robust sense. The link gives a list of his ArXiv papers.

Math behind databases management and SQL ?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.