Database Normalization (1-3 NF)

This is a tutorial for those who are confused about the normal forms due to the extreme confusion you find on the web about the subject. If you want to know what normalization is and why to do it, wikipedia has a great article detailing this information:
http://en.wikipedia.org/wiki/Database_normalization

1NF

1NF is arguably the most ambiguous and confusing normal form on the web. The first normal form is just about making multi-valued fields organized into multiple rows. There are two types of multi-valued fields in unnormalized tables:

This-

Id	Student	Subject 1	Subject 2
1	Harry	Charms	Potions
2	Ron	Charms	Potions

And this-

Id	Student	Subjects
1	Harry	Charms, Potions
2	Ron	Charms, Potions

Or as is shown in most examples, this-

Id	Student	Subject
1	Harry	Charms
		Potions
2	Ron	Charms
		Potions

In both cases we are tying to shove in a list of values, that is a one-to-many or many-to-many relationship with the row, into the row itself. For reasons detailed in the wikipedia article, this should be fixed by creating a separate row for each value and repeating the values in the others fields, like so:

Id	Student	Subject
1	Harry	Charms
1	Harry	Potions
2	Ron	Charms
2	Ron	Potions

The table is now in 1NF were it not for the primary key losing its uniqueness. The id field must be unique in order to identify each distinct student. To solve this we can do one of two things:

Either we create an additional key field for the subjects and make the primary key of the whole table be a composite key of both student and subject ids, thus making the composite key unique-

StudId	Student	SubjId	Subject
1	Harry	1	Charms
1	Harry	2	Potions
2	Ron	1	Charms
2	Ron	2	Potions

Or we could just prepare for the other normal forms and start splitting the tables now as is usually done in examples-

StudId	Student	SubjId
1	Harry	1
1	Harry	2
2	Ron	1
2	Ron	2

SubjId	Subject
1	Charms
2	Potions

Notice that we still need to make the foreign key in the students table part of the primary key in order to preserve uniqueness. If you're wondering why we didn't use a weak entity (bridge table / junction table), that's because it's done in 2NF.

If we had more than one multi-valued field, we'd just create a Cartesian product, like so:

StudId	Student	SubjId	Subject	TeacId	Teacher
1	Harry	1	Charms	1	Filius
1	Harry	2	Potions	2	Slughorn
1	Harry	2	Potions	3	Snape
2	Ron	1	Charms	1	Filius
2	Ron	2	Potions	2	Slughorn
2	Ron	2	Potions	3	Snape

Resulting in 3 tables:

StudId	Student	SubjId	TeacId
1	Harry	1	1
1	Harry	2	2
1	Harry	2	3
2	Ron	1	1
2	Ron	2	2
2	Ron	2	3

SubjId	Subject
1	Charms
2	Potions

TeacId	Teacher
1	Filius
2	Slughorn
3	Snape

Complete example:

Id	Student	SubjId	Subject	Room	RoomHall	TeacId	Teacher
1	Harry	1	Charms	101	A	1	Filius
		2	Potions	202	B	2	Slughorn
						3	Snape
2	Ron	1	Charms	101	A	1	Filius
		2	Potions	202	B	2	Slughorn
						3	Snape

Turns into:

StudId	Student	SubjId	Subject	Room	RoomHall	TeacId	Teacher
1	Harry	1	Charms	101	A	1	Filius
1	Harry	2	Potions	202	B	2	Slughorn
1	Harry	2	Potions	202	B	3	Snape
2	Ron	1	Charms	101	A	1	Filius
2	Ron	2	Potions	202	B	2	Slughorn
2	Ron	2	Potions	202	B	3	Snape

Notice that the room is assumed to be dependant on the subject such that each subject is taught in its own room.

We may opt to leave the table as it is as it quite complex to break down into smaller tables without any guidance. However if we are to break the table down, the room information would be included in with the subject table since we said that the room is dependant on it, yielding the following:

StudId	Student	SubjId	TeacId
1	Harry	1	1
1	Harry	2	2
1	Harry	2	3
2	Ron	1	1
2	Ron	2	2
2	Ron	2	3

SubjId	Subject	Room	RoomHall
1	Charms	101	A
2	Potions	202	B

TeacId	Teacher
1	Filius
2	Slughorn
3	Snape

2NF

2NF is only applicable on tables with composite keys. If a table does not have a composite key, then it is already in 2NF. To make a table in 2NF, first you make sure it is in 1NF and then you split it into separate tables depending on which part of the composite key the fields depend on. For example in the students' table above, the student name does not depend on the subject id, it depends only on part of the composite key, that is, the student id. So the student name field should go into a separate table which describes the students (together with the primary key of course).

StudId	SubjId
1	1
1	2
2	1
2	2

StudId	Student
1	Harry
2	Ron

SubjId	Subject
1	Charms
2	Potions

And there is it, the weak entity we are so used to in many to many relationships.

Complete example (following from previous):

StudId	Student	SubjId	TeacId
1	Harry	1	1
1	Harry	2	2
1	Harry	2	3
2	Ron	1	1
2	Ron	2	2
2	Ron	2	3

Turns into:

StudId	SubjId	TeacId
1	1	1
1	2	2
1	2	3
2	1	1
2	2	2
2	2	3

StudId	Student
1	Harry
2	Ron

Hence yielding:

StudId	SubjId	TeacId
1	1	1
1	2	2
1	2	3
2	1	1
2	2	2
2	2	3

StudId	Student
1	Harry
2	Ron

SubjId	Subject	Room	RoomHall
1	Charms	101	A
2	Potions	202	B

TeacId	Teacher
1	Filius
2	Slughorn
3	Snape

Notice that if in 1NF we did not break down the table, we'd result with the same set of tables by now.

3NF

3NF is the normal form we are used to. All we do is check that every field in a 2NF table depends directly on the primary key. If it doesn't or if it depends on a non-primary key field, you place it in its own table. For example if we had the following table:

SubjId	Subject	Room	RoomHall
1	Charms	101	A
2	Potions	202	B

The RoomHall field is directly dependent on the Room field and not on the SubjId primary key field, so the RoomHall field should go into a table on its own together with the Room field. In fact the room where the subject is thought is not a direct property of the subjects entity but is an entity on its own and hence should be separated into a rooms entity and only referenced by a foreign key.

SubjId	Subject	Room
1	Charms	101
2	Potions	202

Room	RoomHall
101	A
202	B

Complete example (following from previous):

SubjId	Subject	Room	RoomHall
1	Charms	101	A
2	Potions	202	B

Turns into:

SubjId	Subject	Room
1	Charms	101
2	Potions	202

Room	RoomHall
101	A
202	B

Hence yielding:

StudId	SubjId	TeacId
1	1	1
1	2	2
1	2	3
2	1	1
2	2	2
2	2	3

StudId	Student
1	Harry
2	Ron

SubjId	Subject	Room
1	Charms	101
2	Potions	202

Room	RoomHall
101	A
202	B

TeacId	Teacher
1	Filius
2	Slughorn
3	Snape

Links

http://portal.dfpug.de/dFPUG/Dokumente/Partner/Hentzenwerke/Visual%20FoxPro%20Certification%20Exam%20Study%20Guide%20Chapter%2002.pdf

Reading Related Tables As Nested Rows

Problem

A problem I used to face with relational databases is how to handle 1-to-many or many-to-many rows in SQL select statements. Let's say you have 2 tables with a many-to-many relationship between them, such as a Movies table and an Actors table. How do I present a list of movies together with their associated actors?

The naive way to do this is by using nested loops with a query for movies in the top loop and a query for actors in the second loop. In PHP it would look something like...

$moviesResult = mysql_query("SELECT id, title FROM movies"); 
while($moviesRow = mysql_fetch_assoc($result)) 
{ 
    echo("<h1>" . $moviesRow['title'] . "</h1>"); 

    echo("<ul>"); 
    $actorsResult = mysql_query("SELECT actors.name FROM actors INNER JOIN movies_actors ON actors.id = movies_actors.actorid WHERE movies_actors.movieid = " . $moviesRow['id'] . ";"); 
    while($actorsRow = mysql_fetch_assoc($actorsResult)) 
    { 
        echo("<li>" . $actorsRow['name'] . "</li>"); 
    } 
    echo("</ul>"); 
}

This approach however will kill your database. Ideally you should minimize the number of queries sent.

Another approach would be to join the movies table with the actors table and then read it with nested loops.

$result = mysql_query("SELECT movies.id AS id movies.title AS title, actors.name AS actor FROM movies INNER JOIN movies_actors ON movies.id = movies_actors.movie INNER JOIN actors ON actors.id = movies_actors.actor"); 
$row = mysql_fetch_assoc($result); 
while($row) 
{ 
    $currMovieId = $row['id']; 
    echo("<h1>" . $row['title'] . "</h1>"); 
    echo("<ul>"); 
    do 
    { 
        echo("<li>" . $row['name'] . "</li>"); 
    } while ($row = mysql_fetch_assoc($result) && $row['id'] == $currMovieId);
    echo("</ul>"); 
}

This works but as soon as you add another table to the join, determining which rows contain new information can be a nightmare, not to mention all the rows which just contain repeated information due to the cartesian product. For example:

Id	Title	Actor	Genre
1	The Matrix	Keanu Reeves	Action
1	The Matrix	Keanu Reeves	Adventure
1	The Matrix	Keanu Reeves	Sci-Fi
1	The Matrix	Laurence Fishburne	Action
1	The Matrix	Laurence Fishburne	Adventure
1	The Matrix	Laurence Fishburne	Sci-Fi
1	The Matrix	Carrie-Anne Moss	Action
1	The Matrix	Carrie-Anne Moss	Adventure
1	The Matrix	Carrie-Anne Moss	Sci-Fi
2	The Matrix Reloaded	Keanu Reeves	Action
2	The Matrix Reloaded	Keanu Reeves	Adventure
2	The Matrix Reloaded	Keanu Reeves	Sci-Fi
2	The Matrix Reloaded	Laurence Fishburne	Action
2	The Matrix Reloaded	Laurence Fishburne	Adventure
2	The Matrix Reloaded	Laurence Fishburne	Sci-Fi
2	The Matrix Reloaded	Carrie-Anne Moss	Action
2	The Matrix Reloaded	Carrie-Anne Moss	Adventure
2	The Matrix Reloaded	Carrie-Anne Moss	Sci-Fi
3	The Matrix Revolutions	Keanu Reeves	Action
3	The Matrix Revolutions	Keanu Reeves	Adventure
3	The Matrix Revolutions	Keanu Reeves	Sci-Fi
3	The Matrix Revolutions	Laurence Fishburne	Action
3	The Matrix Revolutions	Laurence Fishburne	Adventure
3	The Matrix Revolutions	Laurence Fishburne	Sci-Fi
3	The Matrix Revolutions	Carrie-Anne Moss	Action
3	The Matrix Revolutions	Carrie-Anne Moss	Adventure
3	The Matrix Revolutions	Carrie-Anne Moss	Sci-Fi

Are we supposed to receive all those rows just to display the below?

1	The Matrix	Keanu Reeves, Laurence Fishburne, Carrie-Anne Moss	Action, Adventure, Sci-Fi
2	The Matrix Reloaded	Keanu Reeves, Laurence Fishburne, Carrie-Anne Moss	Action, Adventure, Sci-Fi
3	The Matrix Revolutions	Keanu Reeves, Laurence Fishburne, Carrie-Anne Moss	Action, Adventure, Sci-Fi

Solution

The best solution I found is a hybrid of the above 2 solutions. You make a different query for each table and then read all the rows returned by each query, placing the information in the list it belongs to.

$moviesResult = mysql_query("SELECT id, title FROM movies;"); 
$actorsResult = mysql_query("SELECT movies_actors.movieid AS movieid, actors.name AS name FROM actors INNER JOIN movies_actors ON actors.id = movies_actors.actorid;");
$genresResult = mysql_query("SELECT movies_genres.movieid AS movieid, genres.name AS name FROM genres INNER JOIN movies_genres ON genres.id = movies_genres.genreid;"); 

$actorRow = mysql_fetch_assoc($actorsResult); 
$genreRow = mysql_fetch_assoc($genresResult); 
while($movieRow = mysql_fetch_assoc($moviesResult)) 
{ 
    $currMovieId = $movieRow['id']; 
    echo("<h1>" . $movieRow['title'] . "</h1>"); 

    echo("<ul>"); 
    while ($actorRow && $actorRow['movieid'] == $currMovieId) 
    { 
        echo("<li>" . $row['name'] . "</li>"); 
        $actorRow = mysql_fetch_assoc($actorsResult); 
    } 
    echo("</ul>"); 

    echo("<ul>"); 
    while ($genreRow && $genreRow['movieid'] == $currMovieId) 
    { 
        echo("<li>" . $row['name'] . "</li>"); 
        $genreRow = mysql_fetch_assoc($genresResult); 
    } 
    echo("</ul>"); 
}

In this way we only make 3 queries, equal to the number of tables, and we only read as many rows as needed.

SQL Joins Tutorial

This is a simple tutorial aimed towards those who, like me, completely misunderstood how to, and why to, use joins in SQL. It is not meant to be an advanced reference but a tutorial for beginners who know some SQL but can't understand joins.

Huh?

Let's say that you have a database with tables which are related by foreign keys. For example, a Customers table, a Products table and an Orders table. Each row in the Orders table is linked to a row in the Customers table (the customer who made the order) and to a row in the Products table (the product which was ordered).

Now let's say that you want to query the database to view all the rows in the Orders table but with the customer's name and product's name instead of their primary key. If you learned SQL the same way I did, you'd probably do something like this:

SELECT orders.date, customers.name, products.name
FROM orders, customers, products
WHERE orders.customer = customers.id AND orders.product = products.id;

This is called an implicit join. In fact you are doing an unconditioned join between all 3 tables and then just filtering out the joined rows which are not made of related table rows. What does this mean?

If our 3 tables contain the following data:

Orders:

Id	Date	Customer	Product
1	01/01/01	1	2
2	2/02/02	3	2
3	03/03/03	3	3

Customers:

Id	Name
1	John
2	Michael
3	Terry

Products:

Id	Name
1	Cheese
2	Parrot
3	Spam

Then the query will cause this to happen:

Orders.Date	Customers.Name	Products.Name
01/01/01	John	Cheese
01/01/01	John	Parrot
01/01/01	John	Spam
01/01/01	Michael	Cheese
01/01/01	Michael	Parrot
01/01/01	Michael	Spam
01/01/01	Terry	Cheese
01/01/01	Terry	Parrot
01/01/01	Terry	Spam
02/02/02	John	Cheese
02/02/02	John	Parrot
02/02/02	John	Spam
02/02/02	Michael	Cheese
02/02/02	Michael	Parrot
02/02/02	Michael	Spam
02/02/02	Terry	Cheese
02/02/02	Terry	Parrot
02/02/02	Terry	Spam
03/03/03	John	Cheese
03/03/03	John	Parrot
03/03/03	John	Spam
03/03/03	Michael	Cheese
03/03/03	Michael	Parrot
03/03/03	Michael	Spam
03/03/03	Terry	Cheese
03/03/03	Terry	Parrot
03/03/03	Terry	Spam

And after generating all that it will then select the rows which make sense relation wise, according to the WHERE statement.

Orders.Date	Customers.Name	Products.Name
01/01/01	John	Parrot
02/02/02	Terry	Parrot
03/03/03	Terry	Spam

The big table is called a Cartesian product, which means that all possible combinations of rows between the tables are created, yielding a number of rows equal to the multiplication of the number of rows in each table (3 * 3 * 3 = 27 in this case). As you can tell, this will get really huge really quickly as the table get bigger.

Enter explicit joins.

Joins

In SQL, the FROM statement doesn't mean "a list of tables used in the SELECT statement". In the FROM statement you mention just one table. This table could either be one of the tables you created in the database or a "custom" table, such as one which is a joined version of several tables. The JOIN statement in SQL is not a keyword on par with the FROM statement, as I used to think due to the way it is indented in most tutorials I've seen. It is in fact a binary operator between 2 tables, just like "+" and "=" as binary operators.

The JOIN operator takes 2 tables and returns a new table, which is a joined version of the 2 tables. You can then join another table to that new table and keep on adding more tables to the "composite" table. There are several joins available in standard SQL which will be described later, but if we should use the INNER JOIN type in an example, this is how joins are used in general:

SELECT orders.date, customers.name, products.name
FROM (orders INNER JOIN customers ON orders.customer = customers.id) INNER JOIN products ON orders.product = products.id;

As you can see, the join is used between tables and can even be bracketed in order to state which tables should be joined up first. The ON statement is used to immediately join up the rows which are related, avoiding the cartesian product table in the first place. This will therefore be processed much more efficiently as the third table will only be joined up after the first two tables have been joined correctly, rather than joining everything together without a condition.

In the implicit join example, the tables where joined up with an inner join without the ON condition, hence losing all the advantage of joins. Now that you know how joins work, let's see what are the differences between the 4 join types described in w3schools.com.

Join types

The main difference between the join types is how they handle rows which don't match the ON condition.

INNER JOIN:
Strictly follows the ON condition between tables such that any rows in one table which cannot be matched up with another row in the other table will be left out. This is the kind of join we are used to.

SELECT orders.date, customers.name, products.name
FROM (orders INNER JOIN customers ON orders.customer = customers.id) INNER JOIN products ON orders.product = products.id;

results in

Orders.Date	Customers.Name	Products.Name
01/01/01	John	Parrot
02/02/02	Terry	Parrot
03/03/03	Terry	Spam

As you can see, not all customers or all products where mentioned. Only the ones which were mentioned in the ORDERS table and hence were related in some way were returned.

OUTER JOIN:
This is where things get a bit hairy and hence require that you make an effort to understand. The outer join makes sure that all rows in both tables are returned, even if there is no matching row in the other table. What happens to those tables which have no matching rows? They are joined to NULL values. As long as they are returned, it doesn't matter what they're joined to right?

You can also use LEFT JOIN and RIGHT JOIN to say whether you want to return all the rows of the table on the left of the join operator only or all the rows of the table on the right of the join operator only.

Now in order to use these joins to create a complex joined table, you have to be sure that a join will not return columns with NULL values which will be used in an ON condition of another join.

SELECT orders.date, customers.name
FROM orders RIGHT JOIN customers ON orders.customer = customers.id;

results in

Orders.Date	Customers.Name
01/01/01	John
NULL	Michael
02/02/02	Terry
03/03/03	Terry

SELECT orders.date, products.name
FROM orders RIGHT JOIN products ON orders.product = products.id;

results in

Orders.Date	Customers.Name
NULL	cheese
02/02/02	parrot
01/01/01	parrot
03/03/03	spam

SELECT orders.date, products.name, customers.name
FROM (orders LEFT JOIN customers ON orders.customer = customers.id) RIGHT JOIN products ON orders.product = products.id;

results in

Orders.Date	Customers.Name	Products.Name
NULL	NULL	cheese
02/02/02	terry	parrot
01/01/01	john	parrot
03/03/03	terry	spam

As you can see, depending on how the outer joins are used, we can make a particular table return all its rows, even if it isn't related to any other table.

Final note

I'd like to leave a few notes and links before concluding.

First of all, what I said about the implicit join not being efficient next to an explicit one is not necessarily true since the SQL optimizer may fix it before executing it.

Secondly, if you can avoid using brackets in the the joins it would be better as that will allow the SQL optimizer to make adjustments to the query without it having to make sure to preserve the precedence which you unneccessarily imposed.

In a future post, I will describe a trick which I used to efficiently view multiple one-to-many related tables which I also had trouble with in SQL until recently. But for now I will leave you with these links:

http://www.w3schools.com/sql/sql_join.asp
http://onlamp.com/pub/a/onlamp/2004/09/30/from_clauses.html
http://www.codinghorror.com/blog/2007/10/a-visual-explanation-of-sql-joins.html

Generic Genetic Algorithms

I have finally finished my C# generic genetic algorithm library which is based on my university thesis "A Generic Genetic Algorithm using Phenotype Building Functions" (http://www.scribd.com/doc/48697452/A-Generic-Genetic-Algorithm-using-Phenotype-Building-Functions). You can find it at http://code.google.com/p/genericga/. The wiki page explains how to use it.

Cool proofs

When I was in university, our course had a forum that we maintained ourselves in which we posted anything which would be of help to each other or which we found worth sharing. At the time of writing this, the forum will soon be closed down and all of the information in it will be probably lost. I shall post here my geekiest post ever which was titled "Cool proofs" in which I posted 3 mathematical proofs used in computer science which I literally found cool. ^^

Power set of an infinite set is uncountable

By uncountable we mean that you cannot have a one to one mapping from a countable infinite set, usually the natural numbers to the uncountable one.

For example the set of all integers is countable because there exists a bijective mapping from the natural numbers to the integers, for example:
0 -> 0
1 -> -1
2 -> 1
3 -> -2
4 -> 2
...
That is, even numbers point to positive integers and odd numbers point to negatives. So for every integer there exists a natural number which points to it and every natural number points to an integer. So even though there appears to be more integers than natural numbers, in reality they are equal because they are both countable infinite sets.

Now in order to show that the power set of an infinite set is uncountable we need to show that there exists at least one element of the power set which cannot be pointed by a natural number. Consider this random relation of natural numbers pointing to elements of the power set of all natural numbers:
0 -> {}
1 -> {1}
2 -> {0, 1, 2}
3 -> {1, 3}
4 -> {3, 5}
5 -> {1, 2, 3, 4}
6 -> {100, 1000, 10000}
...
Notice that some natural numbers are pointing to sets which contain themselves and others do not. Lets call the numbers which point to themselves Selfish and the others Non-Selfish. For example 1, 2 and 3 are selfish whilst 0, 4, 5 and 6 are not. Given that the power set of all natural numbers contains every possible subset of natural numbers, it stands to reason that one of the subsets should happen to be the set of all Non-Selfish numbers in our relation. Let's call the natural number which points to the set of all Non-Selfish numbers 'd' and the set of all Non-Selfish numbers S. Since every natural number must either be a Selfish number or a Non-Selfish number, we can safely say that d itself is either a Selfish number or a Non-Selfish number. So what is it?

If d is a Selfish number then it is an element of S. But only Non-Selfish numbers are elements of S.
If d is a Non-Selfish number then it is not an element of S. But S contains all Non-Selfish numbers.
Therefore we have reached a contradiction, because we have found an element which cannot be mapped by a natural number. Therefore it is impossible to make a bijective relation between the natural numbers and the power set of all natural numbers. Therefore the power set of an infinite set is uncountable.

QED

Set of all infinite length binary strings is uncountable

Enumerate the infinite length binary strings in a table in some order. For example:
0011111000110011...
1011100101100100...
1010101010010101...
0000000000000000...
...
Now we can refer to a particular string by referring to its corresponding row number. We can also refer to a particular bit in the string by referring to a particular column number. Let B(r,c) be the bit in column c of the string in row r.

If this set was countable, we can create a bijective mapping from the natural numbers to each and every binary string. But it is impossible to enumerate each and every infinite length binary string because no matter what order we use and no matter how many strings we include, it is always possible to find a string which is not included. Here's how:
Consider the diagonal bits in the table, that is, consider B(i,i) for every natural number i. Construct a string, s, which is made of the diagonal bits, inverted. That is, s[i] = !B(i,i). Now for every string, there is at least one bit which is different from s, because the diagonal includes one bit from every string and s has that bit inverted. Given the previous table, s would be 1101...

So no matter how many strings you enumerate (infinity included) there are always strings which are not included in the enumeration. Or conversely, no matter how you construct a relation of natural numbers pointing to the strings, there are always strings which are left out. Therefore the set of all infinite length binary strings is uncountable.

QED

Notice that for any power set, its elements can be encoded into binary strings, where each bit represents whether a particular element in the original set is in that subset. For example the power set of {1,2} is {{}, {1}, {2}, {1,2}} which can be represented as {00, 10, 01, 11} where the first bit says if 1 is in the set and the second says if 2 is in the set. Therefore if the set of all infinite length binary string was countable, the power set of an infinite set was also countable.

The halting problem

The halting problem proves that it is impossible to construct an algorithm (program which always terminates) which will analyze any program and correctly answer if, given a particular input, will terminate. Here's how.

Assume that such a program exists and can be used by simply calling the function Halt(p,i) which will return whether program p will terminate given input i. What we shall do is construct a program which will use Halt on itself and do the opposite. If this is possible than we have just found a case where Halt will fail, no matter what the implementation.

Construct program D which is defined as:
D(p) = if Halt(p,p) then infinite_loop else terminate
Program D will take a program p, check if it halts when given itself as input and enter into an infinite loop if so or terminate otherwise. If this self input confuses you, think of the input to be a copy of the original program. So if I have written a compression program which takes other files and compresses them, I can copy the program and compress the copy, essentially giving the program itself as input.

The reason we constructed such a funny program is that if we give D itself as input, the following will happen:
D(D) = if Halt(D,D) then infinite_loop else terminate
and as you can see, Halt will essentially check if D(D) will terminate, therefore checking if the whole program will terminate. But what does the program mean? The program will either terminate with itself as input or not, but if it terminates then Halt will return true, causing the program to enter an infinite loop, whilst if it does not terminate then Halt will return false, causing the program to terminate.

So if we now call Halt on this program, by calling Halt(D,D), Halt will not be able to come up with a correct answer because D will check what the output will be and do the opposite. Notice that we will receive an answer, it is the same as that given in the if-condition, but it will obviously be the opposite of what will happen. Remember that Halt will call D(p) and pass D as input (instead of p) and that D as a program and D as an input are two separate 'files' which are copies of each other. Self reference can be detected by for example changing a global variable to know how many times a function has been called but
a) A semantically equivalent function can be rewritten which avoids such tricks, yet results in the same problem.
b) This means that some program-input pairs will not be accepted, which means that you have not constructed the required function. After all, what do you think Halt(D,D) should output?

Therefore we have proven that it is always possible to construct a program which will cause Halt to give a wrong output. Similarly, you cannot construct an algorithm which will tell you if a particular action will be carried out in a program given an input because you can construct a program similar to D which will cause it to give the wrong output. Namely D(p) = if ActionPerfomed(p,p) then avoid_action else perform_action.

QED

Typocalypse

Lately me and my friend Andreas Grech (http://blog.dreasgrech.com/) developed jointly a Microsoft XNA game in just under a sleepless and coffee ridden 24 hours called Typocalypse which is a game where you have to type the words under zombies before they reach you.

My involvement in the game was in using my previous two blog posts, the biasing function for gradually increasing the difficulty of the game by gradually biasing the randomly chosen words to prefer longer words as the score increases and the trie for determining which zombies have a word which has a prefix that matches the currently typed text. I was also responsible for handling keyboard events, displaying the words under the zombies and sound effects which I created orally.

To give credit where credit is due, the background music was taken from the Amiga game The Great Giana Sisters, the pictures including the background image where found from google images and we couldn't be bothered with looking for them again and the library which enabled capturing of keyboard input was taken from here which was developed by George Mamaladze.

The game is open source and you can download and use the source code if you wish, but keep in mind that this was developed in under 24 sleepless hours so at some point coding started getting messy.

Link to the game is http://code.google.com/p/typocalypse/downloads/list.

Enjoy :)

C# Trie

*Update* I have developed a new an improved version of this data structure which you can find here.

For anyone interested, I have also written a Java Trie here.

In a recent project I have ventured into, I had to develop a set of classes in C# for a simple trie which are now released as open source (http://code.google.com/p/typocalypse/source/browse/#hg/Trie). This blog post shall describe how it works and how to use it.

Introduction to tries

Simple tries are a data structure for mapping strings to values such that it enables you to efficiently retrieve all the values whose key strings have a particular prefix. This works by storing all the strings in a tree where each node is a prefix to a number of strings and each edge is a character to append to the prefix in the parent node. The root node is the empty string which is a prefix to all strings.

As you traverse a path from the root downwards, you follow the edges which lead to prefixes of the string you are trying to match. Eventually if such a string exists, a node will be pointing to the value mapped by the string. By traversing the descendants of a particular node, you can retrieve all the stored strings which have that prefix in common and their corresponding value.

Here's a diagram example from wikipedia:
http://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg

Implemented trie

The implemented trie supports adding, removing and character-by-character prefix searching of string-value pairs.

The way it works is by keeping a reference in each node to a value object such that if the reference is null then the node does not point to a value object and hence the prefix is not a complete string. The type of the values is generic, any referencable type is allowed. Each node points to its children via a Dictionary object which maps characters to nodes, thereby allowing a fast search by following the characters.

The following is a description of each class:

TrieNode

This is a non-public class which represents the nodes of the trie, that is, the prefixes. However in this implementation, the prefix itself is not stored, only the last character of the prefix called the Key is stored in order to know which character was followed to access this node. It also stores the value (generic type), a pointer to the parent node and a dictionary which maps characters to children nodes. If this node terminates a string then it's value field points to an object, otherwise it is null.

PrefixMatcher

This is a non-public class which is dedicated to allow the user to search the trie for a particular string or strings with a particular prefix. It was designed for enabling the user to search for the values of said strings on a character by character basis rather than providing the whole string immediately so that it can be used to search for user input as the user types in the query. This requires the maintenance of a state so that it is known which prefix has been entered thus far as well as which node that prefix is found in so as to enable an efficient search. For this reason the search feature was kept in a class of its own. Each time the trie is modified with the removal of a string, the current search is cancelled and must be redone from first character so as to avoid the user from searching non-existent strings.

IPrefixMatcher

This is a public interface which abstracts the methods of the PrefixMatcher class so that the user is provided with an abstraction rather than a concrete class in order to search.

Trie

This is the main class which provides the features of the trie data structure. Searching is done through the public property "Matcher" which returns an instance of IPrefixMatcher. When a string is removed, the current search is cleared so as to avoid the user from searching non-existent strings.

Examples

Here is an example of how to use the implemented trie:

//Create trie
Trie < string > trie = new Trie < string > ();

//Add some key-value pairs to the trie
trie.Put("James", "112");
trie.Put("Jake", "222");
trie.Put("Fred", "326");

//Search the trie
trie.Matcher.NextMatch('J'); //Prefix thus far: "J"
trie.Matcher.GetPrefixMatches(); //[112, 222]
trie.Matcher.IsExactMatch(); //false
trie.Matcher.NextMatch('a');
trie.Matcher.NextMatch('m'); //Prefix thus far: "Jam"
trie.Matcher.GetPrefixMatches(); //[112]
trie.Matcher.NextMatch('e');
trie.Matcher.NextMatch('s'); //Prefix thus far: "James"
trie.Matcher.IsExactMatch(); //true
trie.Matcher.GetExactMatch(); //112

//Remove a string-value pair
trie.Remove("James");

Link to classes

http://code.google.com/p/typocalypse/source/browse/#hg/Trie