Getting to Yes^W 3NF

October 29, 2009 7:24 AM

Need help getting to 3NF when one attribute is functionally dependent on a combination of other attributes.

I am having problems working out how to get the following situation (or similar ones) into 3NF. I know that in production we would probably not want this to get to 3NF because of the performance hit from JOINs; please ignore such things, this is theoretical.

The situation I'm struggling with is one where an attribute is transitively dependent through a combination of other attributes in the same table, and how to split that out into 3NF.

How do you get to 3NF in a situation like the following:

RoadTrip (tripID, startLocation, finishLocation, distanceDriven)


Details:
tripID is an autonumber/surrogate key
distanceDriven is dependent on both startLocation and finishLocation, because the distanceDriven is the distance between these two locations.

I have mulled this over in my head and tried to figure it out, I suspect my solution is wrong:

RoadTrip (tripID, startLocation, routeID)
FK: routeID references TripRoute.routeID
TripRoute (routeID, finishLocation, miles)

Is that really how to get this into 3NF?


I can't find any good examples of this sort of normalization situation through Google; the examples I see don't have any cases of finctional dependency on a combination of attributes.

The Hive Mind is all that's left. Please hope me normalize!

posted by alex.dudley to technology (10 comments total)

*functional dependency, even. Sorry. Too frustrated by my idiocy to work out how to speel.
posted by alex.dudley at 7:26 AM on October 29, 2009

To get to 3NF, you remove columns that are not fully dependent on your primary key. In this case, distanceDriven is not dependent on the key (since it's derived from startLocation and finishLocation), and should be removed from the table.
posted by MagicEightBall at 7:31 AM on October 29, 2009

Yes, I'm aware it needs to go, but the how is my question.

The rule I've been following up until now is that if there is a transitive dependency, pull out the dependent and the determinant to a new table, and post a copy of the determinant to the original table as a foreign key.

if I do that here (pull out distanceDriven and it's antecedents) the result is a table that looks like:

Distance (startLocation, finishLocation, distanceDriven)

Which has a compound key, and results in a compound FK in the RoadTrip table - this would get my fingers broken.

Neither of the possible solutions here look right, which is why I am asking for an example of how to do it, not just an acknowledgement that I should do it.
posted by alex.dudley at 7:48 AM on October 29, 2009

I'm sorry if I sound short or snappy here, but I have been trying to figure this out for days, I'm not getting it, and I am beginning to think that the real problem is that I'm a total idiot.
posted by alex.dudley at 7:50 AM on October 29, 2009

I think the point is that distanceDriven doesn't need to be anywhere in the database, since it can always be calculated.
posted by bitslayer at 8:10 AM on October 29, 2009

This may be totally irrelevant for your purposes (are you assuming routes are straight lines?), but it certainly seems to me that there are a very large number of routes between two points, and distance driven is not dependent on the start and end point except as a lower bound. You can't drive less than the straight-line distance between the points, but you can certainly drive more.
posted by RikiTikiTavi at 8:23 AM on October 29, 2009

Maybe I did not choose a great example, then - the real set I'm working with is one such that the third item is dependent on the other two and yet has to be represented in the schema.
posted by alex.dudley at 8:27 AM on October 29, 2009

It's been a while, so I may be totally wrong, but how about:

RoadTrip (tripID, routeID)
Locations (routeID, startLocation, finishLocation)
Distance (routeID, distanceDriven)

It's a little ugly, but I don't think anything prevents you from adding more dependencies, no?

I can't think of any way to do it that keeps the locations and distance in the same table and also avoids a compound foreign key. (I mean, if the distance is in a table with the locations, the locations have to be the primary key there, right? So if the locations show up anywhere else, they're going to be a compound foreign key, period.)

(My apologies in advance if this is totally incorrect.)
posted by equalpants at 11:23 AM on October 29, 2009

Gently put, I think your example is making it difficult to discuss the underlying issue.
posted by adipocere at 12:26 PM on October 29, 2009

What's wrong with a compound foreign key? I'm pretty sure that's allowed in 3NF.
posted by miyabo at 12:54 PM on October 29, 2009