All the tree organisations for databases I've found documentation, papers or blogs about were built on a one parent node can have many children, but a child node can have only one parent, with a single original node - basis.

I am looking for a way to organise a database efficiently on a basis that a parent node can have many children, a child node can have many parents, and there are multiple original nodes.

The data is not going to change or move around much, but there will be insertions in the middle of the tree on a regular basis.

Any ideas or links to papers appreciated.

  • "one to many relationship both ways" is called "many-to-many", no? – mustaccio Oct 6 '18 at 16:57
  • @mustaccio true. I meant that one node can have many parents and many children, but indeed between two "node" items in the db it's a many to many relationship. – Saryk Oct 6 '18 at 17:01
  • The basic approach is a node table and a relation table that defines the relation between two nodes. By having a from_node and to_node in the relation table that association has a direction as well. – a_horse_with_no_name Oct 9 '18 at 12:25
  • @a_horse_with_no_name that is what I intended to do, and what I was looking for documentation on to learn the best practices / things not to do – Saryk Oct 9 '18 at 17:54

A tree is, by definition, one parent with many children, each of which can have many children. What you desire is a generalised network, not a tree.

There are many DBMS products which present a graph (i.e. generalised network) data model. Both items and the relationships between items are first-class objects. Typically both can have arbitrary labels and attributes. These products are also optimised for relationship-based processing such as friends-of-friends, shortest path or cluster detection. If navigating the network is more important for your use case than OLTP point updates or calculating bulk aggregates then one of these DBMS may suit.

From comment:

Is there a way of having a direction to this network though ? It's for storing school programme data, and the prerequisite knowledge for a certain course for example. (And that course can have many prerequisites and can be prerequisite to others, but there is a direction to the structure.)

All graph DBMSs implemented directed graphs. This means there is a "from" and a "to" in each relationship. This is analogous to, but different from, the "parent" and "child" in a relational database foreign key. A relationship's direction is set when the relationship is written to the DB. Relationships can be read in either direction, however, much like a SQL query can follow a foreign key to find the children given the parent, or the parent given a child.

A hypothetical graph for your school prerequisites might look like:

Basic math   <-- requires --  Advanced math  <--- requires ---¬
        ^                                                     |
        └-------  requires -----------¬                    Medicine
                                      |                       |
Basic chemistry  <-- requires --  Advanced chemistry  <-- requires

Medicine has two prerequisites - advanced math & advanced chemistry. Basic math is a prerequisite for two other subjects.

Not the answer you're looking for? Browse other questions tagged or ask your own question.