This is an essay I wrote back when I was in university about artificial intelligence. I decided to put it up in my geek blog. Enjoy! By the way, I later learned about the halting problem which makes my last paragraph impossible to be realized if the program is expected to be right every time.
Artificial Intelligence
Intelligence is the ability to do something without previously knowing how and use the new knowledge on other problems, or rather, to learn without being taught. Someone who is stupid and therefore not intelligent is someone who requires instructions in order to do (apparently) everything, much like a computer. So what is artificial intelligence? How can a computer simulate this process?
Well if this is possible then it would imply the end of programming, since essentially there would only be one program which will learn how to do anything the user wants. So basically an intelligent program has 3 phases: You tell it what you want it to do, it figures out how to do it and finally does it. The program can decide that it cannot do what it was told. However the most intelligent program is that which accepts the most specifications. It can also decide that it does not have the necessary resources to do what it was told. Again, the most intelligent program is the one which does the most things with the resources it has.
Learning requires external information. Therefore the program must be allowed to gather information about the problem and perhaps completed research by other sources. This is best accomplished via the Internet, although elicitation with the user is a must. The most intelligent program is that which makes best use of past knowledge and requiring least new knowledge (the ability to reuse knowledge). Of course if the program does not gather new information and relies too much on past knowledge it will end up being “closed minded” and this is not desirable as it will result in a closed region of knowledge with no new ideas.
Just like a computer is built without knowing what it’s going to be used for, so must be an intelligent program. A truly intelligent program would not be made for specific tasks such as recognising images or playing a game. It should be the most reusable application ever programmed. It should not be simply a part of another program, but be the entire program (except perhaps the interface).
So it seems that artificial intelligence means a program which translates specifications to solutions without the programmer knowing the solution. The key point here is that the programmer doesn’t know the solution (OK, no one in the development process knows it). This facilitates programming since the programmer need not know the solution before writing the program but rather leaves it to the program to find the solution. It’s also great when we as humans still have not found a solution (or an efficient one) to a particular problem.
What may the future hold for AI? As already mentioned, one day there will be a published algorithm for true AI which is able to learn how to solve any solvable problem, given a specification which has a high level of expressiveness. The first to benefit would be the humanoid robots which in turn would benefit humans in a variety of ways, which need not be mentioned. However will this mean the end of all human jobs, skilled and unskilled alike? Probably what will happen is that the developed countries will slow down the development of AI in the market in order to preserve jobs. But it might be possible for undeveloped countries to acquire some intelligent robots (through missionaries for example) which will help in some way or another. Perhaps in the developed world some hard to find professions will be filled in by robots, but I doubt they will be popular. However it can be possible that one day no one will work anymore and communism will take over as financial classes will be eradicated. All work will be done by robots and people will live a leisurely life, receiving provisions and resources equally. I doubt this will be allowed.
One application of AI I would pursue would be that of fabricating assignments. It would accept the specs of the assignment in raw format as given to the student, possibly with the addition of some course notes for reference, and the ID number of the student. The routine would understand the spec and using the ID number will generate a unique assignment with compiled code (if any) and documentation and comments. If I were to manage to realise such a routine, I would charge my fellow class mates to write their assignments, except that I wouldn’t do anything except feed the program the spec and ID number. Since every student will receive a unique assignment there will be no fear of plagiarism and detecting that the assignment was generated would be practically impossible unless the lecturers would obtain a copy of the routine and compare the given work with the generated one. Come to think of it, a uniquely generated id number would be better. The reason why AI makes sense to be used is because of the shear difficulty to find an algorithm which solves the problem.
Another application would be the semantic interpretation of a given code. The program would accept a given piece of code (given that it is accepted by the compiler) and produce a description in simple English what happens when it executes, at a given level of abstraction. Of course this can be extended to the interpretation of a given executable file. If this is possible then viruses and all malware would be easily detected with no need for updates. The other way round would also be nice where given a description in simple English, the program generates annotated code, ready to be compiled.
Friday, April 22, 2011
Thursday, April 21, 2011
JQuery event / manipulation not working
This is just a silly mistake I made which I thought I should share with the internetz. When assigning JQuery events to html elements, be sure to do it only after they have been loaded. If you just put them straight into a script file the elements wouldn't have loaded when it executes and hence the event won't work.
Make sure that all html DOM manipulation is done after the html loads by putting the javascript code inside a
Make sure that all html DOM manipulation is done after the html loads by putting the javascript code inside a
$(document).ready(function() {
event and manipulation stuff here :D
});
Photoshop slices using divs creates gaps
If you've ever used Photoshop to create websites by drawing them and then slicing out the buttons and if you've ever used divs and css positioning to layout the slicing (done automatically by Photoshop, just follow this) then you probably found out that something like this happens:
This happened to me whilst doing my personal website (www.marctanti.com). The solution was found here. Apparently this happens because when the doctype of the html page is set to strict, images are by default set to display:inline which makes them vertically aligned so that the bottom of the image is in line with where the base line of the text is. In the case of sliced web pages, the slices are placed inside divs so the images are aligned with where the base line of text inside the div would be if there was any. But the divs make room for the "descenders" of text, that is, the extra room needed to display the bottom of the letters 'y' and 'g' for example. Therefore the images will not be aligned with the very bottom of the divs.
So to fix this problem we need to make the images aligned to the very bottom of the containing divs by setting the display css of each slice to block. I gave each slice image a class attribute called slice and then added the following css:
That fixed it.
This happened to me whilst doing my personal website (www.marctanti.com). The solution was found here. Apparently this happens because when the doctype of the html page is set to strict, images are by default set to display:inline which makes them vertically aligned so that the bottom of the image is in line with where the base line of the text is. In the case of sliced web pages, the slices are placed inside divs so the images are aligned with where the base line of text inside the div would be if there was any. But the divs make room for the "descenders" of text, that is, the extra room needed to display the bottom of the letters 'y' and 'g' for example. Therefore the images will not be aligned with the very bottom of the divs.
So to fix this problem we need to make the images aligned to the very bottom of the containing divs by setting the display css of each slice to block. I gave each slice image a class attribute called slice and then added the following css:
.slice
{
display:block;
}
That fixed it.
Wednesday, March 30, 2011
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
This-
And this-
Or as is shown in most examples, this-
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:
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-
Or we could just prepare for the other normal forms and start splitting the tables now as is usually done in examples-
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:
Resulting in 3 tables:
Turns into:
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:
And there is it, the weak entity we are so used to in many to many relationships.
Turns into:
Hence yielding:
Notice that if in 1NF we did not break down the table, we'd result with the same set of tables by now.
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.
Turns into:
Hence yielding:
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
Monday, March 14, 2011
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.
Sunday, March 13, 2011
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.
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:
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:
Customers:
Products:
Then the query will cause this to happen:
And after generating all that it will then select the rows which make sense relation wise, according to the WHERE statement.
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.
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:
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.
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.
results in
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.
results in
results in
results in
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.
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
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
Sunday, February 13, 2011
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.
Subscribe to:
Posts (Atom)