Databases - more than a big box of stuff

First up, my apologies for the lack of blog posts. I've been hard at work on some new projects over the past few months that have taken up my time and which I'll be blogging about soon enough.

So, without further ado, lets begin.

"Database: a comprehensive collection of related data organized for convenient access [...]"

Source: Dictionary.com

Simply put, databases and data warehouses are systems for storing information which we have no doubt worked with or have heard of at some point in our lives. In fact, you may have used a database without even realising it. Dictionary.com defines the word database as: 'a comprehensive collection of related data organised for convenient access [...]'. Can you think of some examples that fit that definition?

Here are a few examples I came up with, most of which fit the definition loosely but can ultimately be defined as a database nonetheless:

• Rolodex
• Telephone book
• Filing Cabinet
• Mobile Phone Contacts List
• Computer Hard-drives
• Computer Software/Systems (MySQL, SQL Server, Oracle, sqlite, Access, Excel, etcetera)

These examples allow for convenient storage and access to information whether its by collections of alphabetically indexed cards and numbered pages or physical disk platters and digital tables. The key points to bear in mind regarding databases are that the data is organized and organized in such a way to allow for easy access.

The reason for this brief explanation is quite simply to show you that databases are not simply boxes of stuff you can just throw things into and pick out of at random; they don't look like my attic, disorganized and awkward to access.

That might seem obvious to most people, but it is a lesson that I learnt the harder way, partly because of my background in applications programming where data is manipulated in a different way to databases. My first attempts at database development and writing SQL showed this.

If you work with or intend to work with databases (digital or otherwise) and use them as I did, now is the time to consider changing that. So how can you do that?

Understand the basic concepts and principles of X

I cannot stress this enough as I have learnt this the hard way in some instances, that, without understanding the concepts and principles of whatever X is, we are likely going to be working against ourselves, relying on guesswork, trial and error and our limited or non-existent experience. It's like learning another language where some might learn stock words and phrases making their vocabulary very limited, while others learn how sentences are structured, how and why words mutate and how to correctly pronounce words so they can communicate with a certain degree of fluency.

This is true of databases, where, we might know about tables, views, functions and indexes and how to write SQL but we don't fully understand how or why something works. Obviously this limits us significantly in the effective use of databases in the same way a person learns a language by only remembering stock words and phrases.

So let's look at some basic database concepts, starting with one that I feel is not covered adequately enough (if at all) in Computer Science database modules and that is 'set theory'. Just to mention, the reason I feel it is not covered adequately enough is that I have worked with some CS graduates who took database modules but had very limited understanding of set theory (which I appreciate could be the student as much as it could be the teacher/module content) or weren't aware of it.

Set theory is a branch of mathematics that works with collections of objects which is precisely what a database is: a collection of information. So when we work with databases, understand that we are working with sets or collections of information, not simply individual records. Using the Telephone book as an example, when we turn to a page, we are looking at a collection of hundreds of phone numbers which we then need to filter to find the results we want, whether it is a single phone number or a subset of them. Sure, we might filter them by going line-by-line, but a database does not. That said, it is possible to go row-by-row in a database but it is not efficient or convenient and goes against the fundamental concepts of databases.

So that's the first concept, the second is that of 'relationships'. Going back to the dictionary definition, it uses the phrase 'related data', so what does that mean? A page in a Telephone book contains not just a list of telephone numbers but the person associated with that number. In other words, the person is related to that particular number and vice versa. In a database this is usually represented by tables and keys, so we might have a table with peoples names in which links to another table containing all the phone numbers using keys. Voila, we have related data.

Perhaps I have over-simplified it, but it'll suffice. Again, this concept of relational data has roots in mathematics, namely, relational algebra and tends to be formally referred to as the 'entity-relationship model' or the 'relational model'.

Third concept is 'indexing'. It is worth mentioning at this point that SQL (structured query language) is made up of separate languages, namely DCL (data control language), DDL (data definition language) and DML (data manipulation language). I won't be covering them in detail, but indexing falls under DDL and DML.

DDL is used for defining or describing data, part of which involves the creation of indexes which is as much as I will be saying about DDL for now. DML is used for manipulating the data and uses indexes to do so. Remember that a database allows for easy access which indexes are essential for. Going back to the Telephone book, imagine if we removed the alphabetical ordering, page numbers and categorization and then threw all the pages into a bag. Now you need to find the phone numbers for all J. Does. Not so easy now is it?

Put simply, indexing is a way of maintaining organized lists that reference locations of information. Like the Telephone book, most textbooks have an index at the front or back with titles or keywords linked to page numbers so we can find information easily. It's outside the scope of this post, but it is worth mentioning that databases actually use the concept of pages and indexes in a similar way to a textbook. If you'd like to find out more and can handle some technical jargon, then have a look at the SQL Server Planning and Architecture Articles over at Microsoft TechNet.

As a final note, not all databases are relational. If you have a few minutes to spare and are curious, check out non-relational databases which are sometimes referred to as NoSQL databases.

It goes without saying that I have barely scratched the surface of relational databases. I'll leave it there for now and save the rest for another day so stay tuned.

Mathematical notation at a glance

Notation... If you have come across it, whether it's mathematical, musical or otherwise, perhaps you thought you had just stumbled into The Matrix or an episode of The Fringe; with the alphanumeric characters and a plethora of symbols, it can look like an alien language or some sort of ASCII art abomination.

While that might be the case, notation is used to convey ideas through symbols and makes life easier, especially when conveying complex ideas to a diverse audience. How?

See what you make of this:

Levenshtein Distance/Optimal String Alignment Algorithm
Source: http://en.wikipedia.org/wiki/Levenshtein_distance

Welcome to the real world of notation. I came across this algorithm a while ago where it was used in a problem involving two sets of data with no direct relationship apart from peoples names. A common problem with data such as peoples names is misspellings which means direct matches aren't guaranteed; that's where this algorithm can be put to use. It can also be used in computational biology, but that is beyond the scope of this post (do an internet search for 'Levenshtein biology' if you are intrigued about its use in biology).

The algorithm gives you the distance between two sequences; in other words, the cost involved in changing something into something else. I'm not going to delve into great detail about the Levenshtein algorithm in this post, just how to understand the notation. Feel free to make comments about the algorithm though if you'd like to know more.

So where do you begin with that algorithm? How do we turn that into something more than a notation? First step is to understand the symbols, much like understanding any language. Some elements of that algorithm you probably understand such as the -, + and = symbols, min and max. You will no doubt understand the words if and otherwise, but perhaps not how they are applied. We do need one extra piece of information which is: the Levenshtein distance between two strings a, b  is given by lev_a,b(|a|, |b|) which I will explain first.

So, firstly, a string is a sequence of characters which could be numbers, letters or symbols. a, b are used to represent two values, in this case, two strings. Lets say a represents the name 'Jon' and b represents 'Johnny'. So the Levenshtein distance between 'Jon' and 'Johnny' is given by lev_a,b(|a|, |b|). What is lev_a,b(|a|, |b|)? That is a function which takes two inputs |a| and |b| and outputs something. The vertical lines either side mean the magnitude or length of a and b. What are the lengths of the names 'Jon' and 'Johnny'? They are 3 and 6. We can now rewrite that function like so: lev_{'Jon','Johnny'}(3, 6).

Let's have another look at that algorithm. You can see something that looks similar to lev_a,b(|a|, |b|) but it isn't quite the same; |a| and |b| are now i and j, but all that means is that i and j represent |a| and |b| in the same way that a and b represent 'Jon' and 'Johnny'. At this point, we should have a better idea about what certain elements of the algorithm mean, or at the very least, what they represent.

There are still curly braces and the if and otherwise words which we may not understand though. Quite simply, the curly braces group things together. Reading from left to right, the far left curly brace groups together the if min(i, j) = 0, max(i, j) and min. The inner curly brace groups together the three function references. The if and otherwise are conditions, so if the minimum value of i and j is equal to 0 then we need the maximum value of i and j which means lev_a,b(i, j) or the Levenshtein distance is the maximum value of i and j which represent the lengths of a and b.

So that is the if condition handled, what about the otherwise? Well, if min(i, j) does not equal 0 then we need the minimum of that inner group with the three function references which means lev_a,b(i, j) or the Levenshtein distance is the minimum value of that inner group.

The inner group is probably the most complicated part of this whole algorithm. Each of those three references refers to the Levenshtein algorithm but with different inputs for i and j. Not only that, but for each of those references, except the last one, we add 1 to whatever lev_a,b(i, j) is equal to which I explained above. So what about this last bit: + 1_(ai≠_bj)? It means we add 1 if the character at position i of sequence a does not equal the character at position j of the sequence b. So if a and b are 'Jon' and 'Johnny', and position i and j are equal to 3 (or 2 in zero-based arrays), then we take the third letter of each name and compare them. In this instance, the third letters are 'n' and 'h' which are not equal, so we would add 1. You might then ask, what do we add if the two characters are equal? We don't add anything, so it's 0.

Head spinning? You might be happy to know that that is where the glance at notation ends and you can throw questions my way if you would like to know more.

One final thing... I may have shown you how to read elements of mathematical notation, but I never showed you a way of turning it into something more that a bunch of symbols, something that can be used. It may not surprise you that the one way I would show you how it can be used is through computer programming; it's what I do. If you don't understand computer programming I would still encourage you to have a look at this computer code I wrote using the Python programming language and see if you can spot the similarities between the code and the original algorithm.

def LevDist(s, s_len, t, t_len):
 if min(s_len, t_len) == 0:
  return max(s_len, t_len)
 else:
  cost = 0
  if s[s_len-1] != t[t_len-1]:
   cost = 1
  return min(LevDist(s, s_len-1, t, t_len)+1,
                       min(LevDist(s, s_len, t, t_len-1)+1, 
                       LevDist(s, s_len-1, t, t_len-1)+cost))

For the programmers among us, I know this is a very simple and poorly performing solution. The reason it has such poor performance is because of the recursion. The time it takes to determine the distance between strings increases exponentially in relation to the length of the two strings, resulting in poor performance. I won't be discussing better implementations in this post, but if you want to have a look at some potential solutions in one of many programming languages then check out this link to rosettacode.org website.

I also found this resource from stanford.edu regarding edit distances/Levenshtein algorithm which is worth a read: Edit Distance Notes

Prologue

It's about time I entered the realms of blogging and share the valuable [IMHO] and potentially unorthodox insights I have in the realms of programming, business intelligence and other subjects that take my interest such as fitness, nutrition and mountain biking.

I'll skip the usual introduction and leave you to peruse my Blogger, G+ profiles and Twitter feed if you wish to know a little more about me. 

I hope you enjoy reading what I have to say and look forward to hearing your thoughts too.