1

i have a website that simulate courses dependencies like this : courses dependencies

i found that network model is the best model or my case but i haven't found any implementation to it in RDBMS.

  • i am using now adjacent list but it have problems in some scenarios and weak performance.
  • i have read about modified pre-order traversal tree but it is useful in tress not graphs

so how can i simulate graph in database ?

ahmedakef
  • 171
  • 1
  • 6
  • Possible duplicate of [What are the options for storing hierarchical data in a relational database?](https://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database) – philipxy Apr 19 '18 at 23:20
  • @philipxy i read this answer before but it is for tree not graph – ahmedakef Apr 20 '18 at 00:39
  • It is not limited to trees. There are also other similar answers. Also google dba.stackexchange.com. – philipxy Apr 20 '18 at 00:42
  • 1
    Have you looked at https://github.com/django-mptt/django-mptt – rtindru Apr 20 '18 at 06:57
  • As a basic concept you could store the courses and the dependencies in separate database tables. The problem would be the performance of complex queries depending on the algorithms you intend to apply to this data. – Lukisn Apr 20 '18 at 07:09
  • @rtindru yes i mentioned this in the question but it is for trees not graph – ahmedakef Apr 20 '18 at 12:45

1 Answers1

3

A naive Django model could look like this:

from django.db import models

class Graph(models.Model):
    name = models.CharField(max_length=100)
    description = models.TextField()

class Node(models.Model):
    name = models.CharField(max_length=100)
    graph = models.ForeignKey(Graph, on_delete=models.CASCADE)

class Edge(models.Model):
    name = models.CharField(max_length=100)
    graph = models.ForeignKey(Graph, on_delete=models.CASCADE)
    from_node = models.ForeignKey(Node, on_delete=models.CASCADE, related_name="from_node")
    to_node = models.ForeignKey(Node, on_delete=models.CASCADE, related_name="to_node")

This lets you store arbitrary graph information. In your case the nodes would be the courses and the edges would be the dependencies. For working with this information a relational database is not an ideal tool. Maybe you could minimize queries by querying a whole graph and process this data with graph related tools like e.g. NetworkX.

Another issue of this model I would like to point out is that it is generally possible to store edges that go from one to another graph. Also other graph related properties like duplicate edges or loops have to be considered.

Lukisn
  • 190
  • 8