Storing a complete graph in a RDBMS

Question

I have several types of entities, each with their own fields, which are stored in separate tables.
Each record in such a table may be connected to zero or more records in a different table, i.e., linked to records from different entity types.
If I go with lookup tables, I get (m(m-1))/2=O(m^2) separate lookup tables that need to be initialized.
While still feasible for 6 or 7 different entity types, would it still be relevant for 50+ such types?
In particular, a given record would need to have links to most other entity types so theoretically speaking I would be dealing with a nearly-complete, non-directed, n-sided graph.
Can anyone shed some light on how to store this structure in a relational DBMS?
(I'm using Postgresql if it matters, but any solutions for other DBMS's would be equally helpful).
Thank you for your time!

Yuval

Answer 1

This is Object-Relational Mapping, a classically hard problem. You really need a ORM tool to do this properly, or it'll drive you nuts.

The connection problem you refer to is one of the pitfalls, and it needs very careful optimisation and query tuning, else it'll kill performance (e.g. the N+1 SELECT problem).

I can't be any more specific without knowing what your application platform is - the actual DBMS used isn't really relevent to the problem.

Answer 2

The other option would be to use an Object Oriented Database such as db40 or Cache. It may be looking into this if performance isn't a huge concern and you are determined to store your entire object graph.

Answer 3

First, thank you for your answer. It is highly appreciated. My application is written in .Net and I'm using the CLSA framework (http://www.lhotka.net/cslanet/) as my ORM. However, I still need to do the DB design myself...

Answer 4

You could use a common base type for all entity types, and handle relationships through that base type - this is something virtually any ORM tool can do using a discriminator column and foreign key relationships (I'm not familiar with CLSA, though).

This approach leaves you with exactly one relationship table.

Edit: This is how you set this up:

CREATE TABLE base (
  id int(10) unsigned NOT NULL auto_increment,
  type enum('type1','type2') NOT NULL,
  PRIMARY KEY  (id)
);

CREATE TABLE type1 (
  id int(10) unsigned NOT NULL,
  PRIMARY KEY  (id),
  CONSTRAINT FK_type1_1 FOREIGN KEY (id) REFERENCES base (id)
);

CREATE TABLE type2 (
  id int(10) unsigned NOT NULL,
  PRIMARY KEY  (id),
  CONSTRAINT FK_type2_1 FOREIGN KEY (id) REFERENCES base (id)
);


CREATE TABLE x_relations (
  from_id int(10) unsigned NOT NULL,
  to_id int(10) unsigned NOT NULL,
  PRIMARY KEY  (from_id,to_id),
  KEY FK_x_relations_2 (to_id),
  CONSTRAINT FK_x_relations_1 FOREIGN KEY (from_id) REFERENCES base (id),
  CONSTRAINT FK_x_relations_2 FOREIGN KEY (to_id) REFERENCES base (id) 
  ON DELETE CASCADE ON UPDATE CASCADE
);

Note the discriminator column (type) which will help your ORM solution find the correct subtype for a row (type1 or type2). The ORM documentation should have a section on how to map polymorphism with a base table.