Relational Database - How to locate candidate keys in a table
Tags: database, keys, relational, find
Published: 2019-10-09 08:04:02

Finding a table's candidate key's during the database design process without having a lot or any mock up-data can be difficult sometimes. There's, however, one well known trick - but many guides use a simplified version which only works on basic tables. In this article, I want to demonstrate the correct version, which works 99% of the times.

Before we start, we'll have a quick look what functional dependencies are.

## Functional dependency
If a value of column A is associated with one value of column B, we say:
- A determines B
- or, B depends on A
- or, A -> B

This is called functional dependency.

## Find the candidate key of a Songs table
Let's locate the candidate key's of this album - artist - song table.


| album_name | album_year | artist_name | artist_genre | song_name                | song_duration |
|------------|------------|-----------------|--------------|--------------------------|---------------|

From the table above, we can tell that our dependencies are:
```
album_name -> album_year
artist_name -> artist_genre
song_name -> song_duration
```

The next step is to illustrate these dependencies with a drawing.
![Locate candidate key relational database](https://thepracticaldev.s3.amazonaws.com/i/1e5nu6ff4mesn92drd6q.png)

Based on the drawing, we can tell that we need *album_name*, *artist_name* and *song_name* to get all attributes.

Therefore, the candidate key of our table is: 
{album_name, artist_name, song_name}

## Drawing method explained
By following the arrows, we try to get to every attribute using one or multiple attributes as a starting point.
For the example from above, we have to start from album_name, artist_name and song_name to get to every attribute.

An attribute that is not connected to any other attribute signals that this attribute is already part of the candidate key.

Let's try more examples.


### Example 1
```
Movie(title, year, genre, genre-description, director, director-home-country)
```

If we tabulated the table above, it would look like:

**Movie**

| title | year | genre | genre_desc | director | director_country |
|-------|------|-------|------------|----------|------------------|

From first view, it's impossible to determine which is the candidate key.

But we do know the dependencies:
```
title -> year
title -> genre
title -> director
genre -> genre-description
director -> director-home-country
```

So, let's draw the dependencies:
![Locate candidate key relational database](https://thepracticaldev.s3.amazonaws.com/i/jg9capmosk39gbcbe5cy.png)

We only need the attribute title to determine all other attributes.
Therefore, {title} is the candidate key.

### Example 2

Now, let's do an example without obvious names.
```
R(A, B, C, D, E, F, G)
```
**Dependencies:**
```
A -> B
B  -> {A, C, E}
C -> {B, F, D}
F -> {D, G}
```

> Curly brackets are just a short hand for a group of attributes with a functional dependency to another (group) attribute.

Let's draw, once again, the dependencies:
![Locate candidate key relational database](https://thepracticaldev.s3.amazonaws.com/i/bsimhzwjnu9d0x8w1xqt.png)

By analysing this drawing, we can get to every attribute starting from A, B and C.
> Explanation with starting from C:
> C -> {B, F, D}
> then, B -> {A, C, E}
> then, F -> {D, G}

We have covered all attributes only by using C.

Candidate keys: {A}, {B} or {C}

### Example 3

```
R = (A, B, C, D, E)
```

**Dependencies:**
```
A -> B
{E, D} -> A
{B, C} -> E
```

Drawing:
![Locate candidate key relational database](https://thepracticaldev.s3.amazonaws.com/i/kcb3o4vu64vynx8czwad.png)

There's no arrow ever going to D and C. This signals that D and C are already a part of our candidate keys.
However, we need to combine {D, C} with either A, B or E to get all attributes.

Candidate keys: {D, C, A} or {D, C, B} or {D, C, E}


### Source:
- https://www.rlvision.com/blog/method-for-determining-candidate-keys-and-highest-normal-form-of-a-relation-based-on-functional-dependencies/

- https://stackoverflow.com/questions/21224354/finding-candidate-keys-from-given-relations

- (Simplified version) https://medium.com/@stinaqv/a-beginners-guide-to-locating-the-candidate-key-and-normal-form-of-a-relation-764d14930463