Tag: functional dependence

Computer scientists speak a language of their own with long ‘noun phrases’ and complex sentences which are often grammatically incorrect or very difficult to parse.

This post here is a short description of FUNCTIONAL DEPENDENCE IN DATA BASES.  This is a common sense view and an AMATEURISH view – so read it to take off the edge off the unintelligibility of explanations around the web but remember that when you want to solve very hard problems, this explanation will probably be not be sufficient or even accurate.

#1 What is a database?

A database is a set of tables.  A table is just a set of rows and columns like we have in Excel.  A database has lots of tables like the sheets in Excel.

And just as we can in Excel, we can tell the program to toddle off to another table to pick up a value, bring it back and put it in another table.  We call that a Look Up.

#2 Looking up something by tracking from table to table

In a complicated set of tables, the value we want might be in Table 6, for example.  We might also have some information that doesn’t allow us to look up what we want in Table 6, but we can use the information we have to look up something in Table 4 and something else in Table 3 and use those two facts to look up what we need in Table 5 and then go to Table 6 to finish the job.

To take a practical example, if you want to look up someone’s telephone number, you need to know their family name and the town where they live.  If their family name is very common, you might need to know their first name and street name as well, but let’s stick to a simple example.

So if we know our friend lives in Timbuktu, we look up the volume number of the directory for Timbuktu, then we go to the Timbuktu directory/table and we use our friend’s name to lookup their telephone number.

Alternatively, the list might have been laid out in one table and we look in the first two columns for Timbuktu AND our friend’s name.  When we have found both together, the correct telephone number will be in the next column.

#3 What is functional dependence?

In plain language, functional dependence just describes how we look up information.

Because we need our friend’s town to look up their telephone number, then telephone number is functionally dependent on town and the computer scientists write that down as Town àTelephone Number.

Equally ,as we need a name to look up a telephone number, telephone number is functionally dependent on name and that is written as Name à Telephone Number.

What’s more, as we need town and name to look up a telephone number, Telephone Number is functionally dependent on Town AND Name. Computer Scientists write that as Town, Name à Telephone Number.

#4 So why do we care about functional dependence?

Every day we ask questions about functional independence without being conscious that we are using this exalted concept!

We use functional dependence every day

Whenever we look up something like a telephone number, we are asking what information we need to know to look up the number.

When you Googled “functional dependence” and landed up here, you used a look up – or rather you trusted Google to know what look-ups to use!

Tough search problems require us to track from one lookup table to another

At work, we might also say, if I have information A and information B, can I find out Z and how do I find out.

How can I step from table to table to get the information that I seek?

When we design a database or set of spreadsheets, we want to do the least work possible!

When we design a database, or set of Excel spreadsheets, we also want to make as few tables as possible!

We want to make sure we only ever have to type a piece of information into only one table once!

We want to make sure that data that hardly ever changes or we hardly ever look at is still accessible but in tables that we can put out of the way.

That’s it.  That’s the what and why of functional dependence.  So let’s turn to the how and specifically the ‘how’ for students.

#5 So how do you work out functional dependence questions?

With the Stanford experiment in online classes going on, and other computer science students doing homework, you might really want to know how do I do these ***** problems?

This is my way – it is not the official way but it works for me.

When I have a table (R) with columns (A, B, C, D etc), I think of the columns as all the columns in a set of spreadsheets.

Then I turn the functional dependencies (FD) (written AàB) into tables.  AàB is a table with two columns, A and B. In plain language, I use column A to look up column B.

Problem 1

Then, when I am asked, does ABCàD work in that relation and set of FD’s, all I do is ask myself, given the set of tables, if I already  know ABC, can I find the value of D? I have to be careful and methodical, but hey it works.

Problem 2

Then when I am asked if BC, say, is a key, I write down BC and I write down the columns that are left – say a, d.  Then I ask if I can look up a and d with B and C.  If I can, then BC is a key. If not, BC is not a key.

Problem 3

When I am asked if two sets of FD are the same, then all I am being asked is whether a set of tables allows me to look up the same information.  This is more tricky and I found it easiest to draw a matrix with a column for each column (A, B, C, D, etc) and a row for each of those columns.  I scratch out the diagonal (A=A) and see if knowing A (row), I can look up B, C, D etc.  This only works for very simple problems though.

So, this is an amateur’s take on functional dependence. Use it if it works for you and not if it doesn’t.  And remember it is an amateur’s version.  Once problems become more complicated, all that maths is probably useful shorthand and my account is probably concealing some misunderstanding or other!

Good luck.