1

How should I design a relational schema to store graph documents that can contain plain nodes (shapes, in the example below) as well as nodes that can reference other graph documents?

To visually describe the data I'm storing, consider document A with three nodes, two of which are shapes and one is a reference to document B:

Sample graph document A

I started out by using two separate tables to store the document's node information, one containing shapes and the other containing documents. But this doesn't work well with the edges table, which can contain edges between shapes, between documents, or between a shape and a document.

create table documents (
  id uuid default uuid_generate_v4() primary key,
  created_on timestamp default now() not null,
  title character not null
);

create table shapes (
  id uuid default uuid_generate_v4() primary key,
  created_on timestamp default now(),
  name character,
  description text
);

create table document_nodes_shapes (
  document_id uuid references documents (id),
  shape_id uuid references shapes (id),
  local_name character,
  primary key(document_id, shape_id)
);

create table document_nodes_documents (
  document_id uuid references documents (id),
  other_document_id uuid references documents (id),
  local_name character,
  primary key(document_id, other_document_id)
);

/* how to accommodate this? */
create table document_edges (
  document_id uuid references documents (id),
  start_node uuid,
  end_node uuid
);

My RDBMS is PostgreSQL if that matters. As to why PostgreSQL was chosen rather than a graph database, there were various factors to lead to this decision. Alternatives that can be considered include MariaDB and possibly Microsoft SQL Server, though I don't think this fundamental design issue would be mitigated by switching RDBMS.

The problem with the existing structure is edges 2 and 3 are between shape nodes, whereas edges 1 and 4 are between shape and document nodes.

One solution I thought about was having one table with more columns:

create table document_nodes (
  node_id uuid default uuid_generate_v4() primary key,
  document_id uuid references documents (id),
  shape_id uuid references shapes (id),
  other_document_id uuid references documents (id),
  local_name character,
  unique key(document_id, shape_id),
  unique key(document_id, other_document_id)
)

And enforce a constraint which guarantees exactly one of shape_id or other_document_id.

This would solve the edges table problem by referencing document_nodes (node_id) for both start and end values, but the design of the document_nodes table seems iffy here.

6
  • 1
    Is it that important the referencial integrity as for you to have 1 table per different edge? I'm not an expert on the subject, but whenever I have implemented graphs or trees with multiple nodes (n-n) the constraints have been troublesome. If you can work without, you only need one edge table since all nodes (no matter the type) use uuid
    – Laiv
    Commented Jun 15, 2023 at 6:11
  • Why not use a NoSQL database, which is good at storing structural data that can be represented as XML or JSON? Commented Jun 15, 2023 at 13:15
  • Even if someone said, "use a RDMS", there is nothing wrong with going back to them with an alternate solution that would work better. Commented Jun 15, 2023 at 13:16
  • @DocBrown Would you mind adding an answer to expand on that with an example? I can't seem to grasp how the OOP pattern would map to relational tables. Commented Jun 15, 2023 at 22:50
  • @Laiv For that option, I suppose there will also only be one nodes table that have a type column to determine whether the uuid is a shape or document? Commented Jun 15, 2023 at 22:54

1 Answer 1

2

You need a generalized entity of shapes and documents - which in this case should be called "node" - and define the edges between shapes and documents in terms of nodes, not in terms of documents and shapes. This will lead to the following table design:

  • Table Node: contains an ID; if necessary, it can also hold type information if it represents a shape or a document. If you have more attributes common to shapes and documents, you can add them here, too.

  • Tables Shapes and Document: both have a mandatory 1:1 relationship to Node, as well as individual attributes for shapes and documents. Their foreign key nodeId is also their primary key. You can think of an OO model with Shape and Document as classes which inherit from a common base class Node, and then resolve that OO model to relational tables with the common "one table per class" mapping.

  • Table Edge: has two foreign keys fromNodeId and toNodeId, so it models a directed m:n relationship between nodes. If you want some restriction here like that only shapes can contain outgoing nodes but not documents, replace fromNodeId by fromShapeId.

This approach has some similarities to the Composite pattern, where composite and leaf both inherit from their generalization, a component.

Of course, it is not necessary to use 3 tables here, alternatively you can just make a node table which is filled with shapes and documents, and distinguish between the two by a type flag. That is the object-relational "one-table-per-class-hierarchy" mapping. The latter might be preferable when you don't expect shapes and documents to have a lot of different attributes.

4
  • I wonder if, from the DB -to->Entity mapping point of view, wouldn't be more efficient to work width edges instead of nodes. Pulling a graph from DB node by node can be challenging or the hell if there's an ORM doing the job. However, edges are "composed" of two nodes (up|down or start|end). It flattens the graph and the way to fetch it. I guess it depends on the depth of the graph and whether cyclic graphs are allowed or not.
    – Laiv
    Commented Jun 16, 2023 at 6:29
  • @Laiv: when one needs individual attributes for edges and nodes (which we don't know for this case), I think it is straightforward to have both, and edge table and a node table.
    – Doc Brown
    Commented Jun 16, 2023 at 6:53
  • I don't think that Edge describes a containment relation. It describes the edges (astonishingly). Containment could be modeled using a parent foreign key in Node which should always reference a Document. Commented Jun 16, 2023 at 11:45
  • @Hans-MartinMosner: ok, I renamed my example attributes and leave it open to whomever is using this.
    – Doc Brown
    Commented Jun 16, 2023 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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