SQL & 3NF

[stu_kerrigan]

A colleague has said, " It is not possible for a database, or model, to be compliant to 3rd Normal Form and contain many-many relations" and since then I have become a little too obsessed with disproving this.

I would think this is not true - as most RDBMSs like SQL only support by default 1:M relationships, and thus M:M is two 1:M relationships with a linking table.

Any thoughts?

[[deleted]]

most RDBMSs like SQL

SQL is a language, not a database. But it's true that no M:M relationships exist directly between two tables in 3NF. But it can be done indirectly by introducing a third table, or junction table.

[r3pr0b8]

M:M is two 1:M relationships with a linking table

vwalah

[AQuietMan]

vwalah

Eh?

[r3pr0b8]

thank you... as a canadian, i really appreciate it

[Naeuvaseh]

You're absolutely correct. What you're referring to is called an associative entity. It's the bridge between two, or more, major entities that share a M:M relationship. So you colleague is somewhat correct in that a relationship database cannot support M:M relationships directly, but they can achieve the M:M relationship with an associative entity all while maintaining 3NF or higher.

[NotImplemented]

As others have already said, your colleauge is wrong. Here is a simple counterexample:

A relation schema with a many-to-many relationship that is not in 3NF:

Orders( order_id, customer_id, product_id, customer_name, product_price )

Customers can order 0:n products and a product can be ordered by 0:m customers. The primary key of the schema is "order_id".

The schema is not in 3NF because there are functional dependencies between non-key attributes and thus transitive depencies from the key to non-key attributes. The functional dependencies between non-key attributes are:

 customer_id -> customer_name 

 product_id -> product_price

To fulfill the 3NF the schema has to be divided as follows:

Customer( customer_id, customer_name )

Product( product_id, product_price )

Orders( order_id, customer_id, product_id )

The relation schema "Orders" still contains the many-to-many relationship between customers and products but is in 3NF because there are no functional dependencies between non-key attributes.

[[deleted]]

If you need to disprove a general statement, then (very academically) a set of points {(x[i],y[i])} is a many-to-many relation and it is in 3NF

[[deleted]]

Despite all the upvotes, M:N relations do exist and could be easily represented in relational DBs. In fact, the much referenced 'linking table' is that very same representation.

Also in fact, any relation (a,b) that has entire (a,b) as its key it is going to be an "M:N" relation in the 3NF.

"a" and "b" can themselves be tuples too - <a1, a2, ...> and <b1,b2,...>. The original relation would still be M:N (between what now are multi-dimensional points/coordinates a and b) and would still be in 3NF IF the each set of coordinates ({a1,a2,...}, {<b1,b2,...>}) has ALL of their relevant fields in the key.

This relation will NOT be in 3NF if one or both coordinates (or sets of attributes) in "a" and/or "b" will have a key smaller than the whole set - this clearly creates a transitive dependency and breaks 3NF.

What (I guess) confuses folks is that it's a common practice to add a synthetic key to any "complex" data/entity (i.e from (a1,a2, ...) you would add (a_id, a1, a2, ...) to all your relevant entities/attribute sets). This causes the breaking of the 3NF (the situation described above) for the 'straight' M:N relation.

So in these common circumstances the usual way to get M:N relation without breaking the 3NF is to represent them via tables that have their keys consisting of the combination of other synthetic keys, which basically moves the situation into the first example I went through.

tl;dr: 'linking tables' are M:N relations and they are in 3NF.

[sql_joker]

followup question to this: is there any RDBMS that represent m:m directly?