Postgres

August 26, 2013
in Postgres, Turing, SQL
4 min read

Turing Machine in SQL (4/5)

This is the fourth of five posts on this subject.

In previous posts, I have presented different ways of implementing a Turing Machine (TM) in SQL with Postgres. All three techniques rely on WITH RECURSIVE to iterate till the TM stops, so as to provide some kind of while construct.

In this post, I get rid of this construct, so that the solution does not require Postgres 8.4 or later. Obviously there is a trick: I will use a recursive SQL function with side effects on a TABLE to execute the TM.

August 23, 2013
in Postgres, Turing, SQL
3 min read

Turing Machine in SQL (3/5)

This is the third of five posts on this subject.

In previous posts, I have presented how to implement a Turing Machine (TM) with the tape stored as an ARRAY or in a separate TABLE accessed through SQL functions. In this post the solution is more cleanly relational, with the tape contents stored in a column of the recursive query, very like Andrew Gierth’s CTS implementation.

August 20, 2013
in Postgres, Turing, SQL
4 min read

Turing Machine in SQL (2/5)

This is the second of five posts on this subject.

In a previous post I presented how to implement a Turing Machine (TM) with an ARRAY to store the tape contents. This solution is not really relational, so in this post I’ll show how to build a TM with SQL-only functions.

August 17, 2013
in Postgres, Turing
7 min read

Turing Machine in SQL (1/5)

This is the first of five posts on this subject.

Postgres implementation of SQL is Turing Complete, as show by Andrew Gierth on Postgres wiki, where a Cyclic Tag System (CTS), which is proven Turing-complete, is implemented using WITH RECURSIVE, a WINDOW function, CASE conditional expressions and an OUTER JOIN. Although the proof is sound, there is a long path from a CTS to an actual Turing Machine (TM).

The first question I want to answer is: how to build a Turing Machine with SQL only?

The second question I would like to investigate is: What SQL features are actually required to build a relational Turing Machine. For instance, can it be done without WITH RECURSIVE, WINDOW functions and OUTER JOIN? (Teaser for later posts: yes!)

August 14, 2013
in Postgres, performance
7 min read

Postgres Warm-up

A database can take some time to reach good performances, the time necessary to OS and database caches to load the necessary data from the hard disk drive. Here is an example with Postgres, which outlines the long delay incurred (18 minutes), presents a simple model to explain this behavior, and shows how to reduce it significantly (to a few minutes).