DEV Community

Volodymyr Pavlyshyn
Volodymyr Pavlyshyn

Posted on

HyperGraphs In Relation Model

In my last article, we model different kinds of graphs in abstract relational databases.

We talk about hypergraphs and even model Undirected hypergraphs. Let's recap our undirected models.

Hypergraph

Undirected Hypergraph

A hypergraph is a mathematical generalization of graphs where a hyperedge could connect multiple or no nodes. So, you have a set of nodes instead of a pair of nodes. Hypergraphs are an emerging domain for modeling complex and dynamic systems and are widely used for temporal and event-dependent graphs. We will model undirected hypergraphs.

Usually, a hypergraph is drawn assets that overlap or as Vin diagrams.

As far as edges now have many-to-many relations with nodes, we just need a joint table.

Nodes

Edges

Edge to nodes

The table could increase if you have a significant edge with a comprehensive set of nodes.

Directed HyperGraph

In directed HyperGraph, we divide nodes into a subset of in-nodes and out-nodes. So, we have a directed edge from one subset to another subset.

We have multiple options for modeling this structure.

As directed, edge-node relations

The most straightforward way is to add a direction attribute to edge-node pairs.

Now Nodes and edges stay the same as in preve example

But relations now has a directions

Pros of this model

  • simplicity
  • ability to create mixed graphs — directed and undirected

Cons of this model

  • it could be hard to build queries
  • The model could encode invalid states. Nobody prevents us from having the same node on the same edge in two directions.
  • for a strictly directed graph we need extra application-level constraints

As directed Graph of nodesets

We could be more explicit and extend a model from a directed graph to operate with node sets

Now, the source and object of the edge point to a node-set relation. For simplicity, we expect that in the case of individual nodes, we create separate node-set for these nodes

Pros of this model

  • more explicit

Cons of this model

  • Require to create a node set for single nodes
  • more complex

Top comments (0)