## RelGraph : a relational model for graphs

Terminology

{ graphs } = { trees } ∪ { networks }

A graph = { nodes } ∪ { edges }

Why a relational model for graphs ?

It is more natural to implement graph structures with a graph oriented database. But we have good reasons to use a relational database as explained here.

The Predicate Calculus is a very simple theory : it is the basic set theory that every child knows. Of course, with the relational model, we are obligated to follow the strict discipline of normal forms. But we see the benefits when we write queries because the Predicate Calculus is a very elegant theory : the queries are naturally deductible from the data model. It is like geometry : with a good system of axes, the equations can be greatly simplified.

How to represent a graph with relations

A graph is the union of two sets : the set of nodes and the set of edges. It is natural to represent a graph by two relations (two tables in SQL jargon).

```node(id, info)
edge(from_node, to_node, name, info)```

where from_node and to_node (the nodes connected in this order) are FKs to node_id.

The actual implementation can be done by a specialized library. Something like ltree for trees in PostgreSQL. The implementation is encapsulated in our model. The relation between PKs and FKs is hidden. It is of course not necessary that this implementation follows the relational model. The application developer sees usual relational tables.

Functions

To node and edge,  we would like to ask a lot of things :

• Select/insert/update/delete nodes, edges and subgraphs
• Enumerate nodes and edges
• List all nodes pointing to a given node
• List all nodes pointed by a given node
• Do you find cycles ? or trees ?
• Do  you find disconnected graphs or isolated nodes ?
• If the graph is a network, build spanning trees

For a tree, we would like to ask :

• Do a breadth-first or a depth-first search
• Give lexicographic notation (1, 1.1, 1.1.1,…)
• Delete a subtree starting at a given node
• Give all the ancestors of descendants of a given node

Associations and groups

Having interactive visualizations in our agenda, we need two other relations : associations and groups.

Association : we would like to connect nodes with specific edges.

```association(from_node, to_node, name, info)
```

Groups : we would like to group nodes having a common property. We don’t forget that a node can be belong to several groups : there is a relation many-to-many between the relations node and groups. We need a go-between relation populated with the PKs of both relations.

```node(id, name, nfo)
node-grouping(node_id, grouping_id)
grouping(id, name, info)
```

where node_id is a FK to node(id) and grouping_id is a FK to grouping(id).

The logical model

We add a relation graph that keeps track of all the graphs created in the schema. In such a way, all graphs use the same basic relations that are created only once.

```graph(id, name, info)

node(id, graph_id, name, info)

edge(edge_id, from_node, to_node, name, info)

association(from_node, to_node, name, info)

node_grouping(node_id, grouping_id)

group(grouping_id, name, info)
```

With the relations node, edge, association and groups well populated, we can expect

• to have access to data from a programming language in a very direct way
• find a visualization library for graphs that will interpret our data structures in a very direct way

The physical model

```create sequence graph_sequence;
create table graph (
id integer not null
default nextval('graph_sequence')
primary key
,name text
,info text
);

create sequence node_sequence;
create table node (
id integer not null
default nextval('node_sequence')
primary key
,graph_id integer not null
references graph(id)
,name text
,info text
);

create sequence edge_sequence;
create table edge (
id integer not null
default nextval('edge_sequence')
,from_node integer not null
references node(id)
,to_node integer not null
references node(id)
,primary key(from_node, to_node)
);

create sequence association_sequence;
create table association (
id integer not null
default nextval('association_sequence')
primary key
,from_node integer not null
references node(node_id)
,to_node integer not null
references node(node_id)
,name text
,info text
);

create sequence grouping_sequence;
create table grouping (
grouping_id integer not null
default nextval('grouping_sequence')
primary key
,name text
,info text
);

create table node_grouping (
node_id integer not null
references node(id)
,grouping_id integer not null
references grouping(id)
,primary key(node_id, grouping_id)
);```