Database Design: Recursive Many to Many Relationships

Question

I have n number of tables that are related on a many-to-many basis. I want to know how to represent such a model without creating an intermediary table for each relationship as that would result in some large number of tables. For this purpose assume that n is sufficiently large to not want to create tables.

For example I may have three tables where n is 3:

Parking_Lot
Car
Person

A car can park in many parking lots and a parking lot will have many cars. A person may drive many cars and a car can have many drivers. A parking lot has many people and many people can be in a parking lot. (the people could be employees or they could just physically be in the parking lot. Please don't over analyze this example, as it is only an example.)

To model this you would have 3 tables (Lot, Car, Person) and three relationship tables.

Say you add a 4th table of food. Food can be eaten in many parking lots, in many cars and by many people. This takes 4 tables + 6 = 10 tables.

How do you model such a relationship without creating a large number of intermediate tables?

I'm more interested in the concept, but I primarily use c# so if there's a neat may to accomplish this in .net I'm all ears.

Answer 1

you could make a relationship table with a type id/table name in it.

relationship
      relationship_type_parent
      relationship_id_parent
      relationship_type_child
      relationship_id_child 

Answer 2

You could try having a central relationship table, with one column for each entity table you have (allowing NULL). For every combination, have a row with the IDs in question.

This gets tricky, but can allow you to model multi-way relations as well -- e.g. person A driving car B in parking lot C. You would might want to add some sort of tag as well, e.g. to distinguish between "person A driving car B in parking lot C" and "person A owns car B that is parked in lot C".

Answer 3

as usual, "it depends" -

it depends on what you're going to do with the information

in a normalized representation the mapping tables are necessary to distinguish the (presumably data-rich) relationships from each other

in a knowledgebase representation a single typed Relationship table will suffice, though it requires you to dereference the source and destination IDs to different tables

Answer 4

People usually relate systems to databases (especially to proper modeling) including ACID persistance, which is not a small feature. On the other hand .net is a framework for applications and has not so much to do with persistancee (it can use different backends for persistance). So if you are not sure if you need full RDBMS or you want to talk about in memory structures, then your question, which is tricky to begin with, really have no answer.

Otherwise, explicitly modeling n plus all binary relationships tables is considered a plus.

Also, you mention n plus relationship tables as if that would be some sort of universal model. However, this does not take care of ternary or higher order relationships nor does it take care of multiple binary relationships (nor multiple higher order relationships).

I am sure someone will offer EAV model or some extension on it.

The problem is that with such approach you gain flexibility, but loose the ability to actually implement relationships.

It all depends why and for what do you need this persistance.

You might create some sort of hybrid - for example automate creation of tables based on some the central table that describes your relationships. If you want a database. Relational database.

You can do similar things also with XML or with some object-relational mapping tolls, etc...

You need to define the problem better.

Answer 5

As everyone else has said, this answer entirely depends upon what you're doing and why you're doing it.

Databases are great at pulling back SETS of data and for categorising and summarising that data. That's what they're designed for (amongst many other things).

They don't work so well at describing complex relationships between individual values (x deep n:m relations). Random access structures from the NoSQL movement are better at that.

If you're really bent on using the classic RDBMS you can model the problem as a graph in the DB using the concept of edges and nodes. Nodes have 0:N edges and 0:N attributes / values (EAV as suggested above). Edges have 2 Nodes and possibly a weight.

You can model it with:

NODE ([node_id, entity, attribute], value)
EDGE ([src_node_id, dest_node_id], weight)

Creating a relationship between nodes (an edge) requires simply adding a value to the EDGE table.

Traversing the structure requires a recursive set of queries finding all the possible steps from the current node and then choosing one to get to the next node. This can be intensive for the RDBMS to do.

EG//

SELECT dest_node_id 
FROM EDGE 
WHERE src_node_id = <<This Node ID>> 
ORDER BY weight ASC 
LIMIT 1

Lather, rinse and repeat for however far down the path you want to go (this assumes that weight is a cost and not a benefit metric and that the graph is a directed graph).

Answer 6

I suggest you need less than 10 tables. Consider a person A eating food X. If person A is located on parking lot B, then food X is eaten on the same parking lot B; therefore you don't possibly need a table relating food and parking lot.

Answer 7

I'd solve this by using an almost polymorphic approach. You can just use two tables, like this:

CREATE TABLE Node (id UNIQUEIDENTIFIER NOT NULL, PRIMARY KEY (id));
CREATE TABLE Relationships (
    parent UNIQUENIDENTIFIER NOT NULL, 
    child UNIQUEIDENTIFIER NOT NULL,
    CONSTRAINT FK_Relationship_ParentNode
        FOREIGN KEY (parent) REFERENCES Node(id),
    CONSTRAINT FK_Relationship_ChildNode
        FOREIGN KEY (child) REFERENCES Node(id)
);

Then all your other entities "inherit" from Node:

CREATE TABLE Person (
    id UNIQUEIDENTIFIER NOT NULL,
    name NVARCHAR(50) NOT NULL,
    CONSTRAINT FK_Person_Node
        FOREIGN KEY (id) REFERENCES Node(id)
);

CREATE TABLE ParkingLot (
    id UNIQUEIDENTIFIER NOT NULL,
    name NVARCHAR(50) NOT NULL,
    address NVARCHAR(250) NOT NULL, -- bad way to model
    CONSTRAINT FK_ParkingLot_Node
        FOREIGN KEY (id) REFERENCES Node(id)
);

CREATE TABLE Food (
    id UNIQUEIDENTIFIER NOT NULL,
    name NVARCHAR(50) NOT NULL,
    calories INT NOT NULL, -- hopefully only needs an int ;)
    CONSTRAINT FK_Food_Node
        FOREIGN KEY (id) REFERENCES Node(id)
);

So now you can model relationships between any two entities, and look them up using a join.

For example, if you wanted find which foods belong to which people, you could say:

SELECT p.name AS person, f.name AS food
FROM Person AS p
INNER JOIN Relationships AS r
ON r.parent = p.id
INNER JOIN Food AS f
ON f.id = r.child

Of course, if you then wanted to find something a little deeper in the hierarchy, you'd need to query each level specifically. But because your entities are (assumedly) real things, and not just levels in a hierarchy, that should be ok :).