Dacht aan ‘nodes’ => ‘edges’ => ‘graph’:
Does it Make Sense to Map a Graph Data-structure into a Relational Database?
It’s pretty straightforward to store a graph in a database: you have a table for nodes, and a table for edges, which acts as a many-to-many relationship table between the nodes table and itself. Like this:
create table node ( id integer primary key ); create table edge ( start_id integer references node, end_id integer references node, primary key (start_id, end_id) );However, there are a couple of sticky points about storing a graph this way.
Meer antwoorden op deze vraag bij Stackoverflow:
- It’s an acceptable approach. You need to consider how that information will be manipulated. More than likely you’ll need a language separate from your database to do the kinds graph related computations this type of data implies. Skiena’s Algorithm Design Manual has an extensive section graph data structures and their manipulation.
- Without considering what types of queries you might execute, start with two tables vertices and edges. Vertices are simple, an identifier and a name. Edges are complex given the multigraph. Edges should be uniquely identified by a combination two vertices (i.e. foreign keys) and some additional information. The additional information is dependent on the problem you’re solving. For instance, if flight information, the departure and arrival times and airline. Furthermore you’ll need to decide if the edge is directed (i.e. one way) or not and keep track if that information as well.
- Consider how Facebook might implement the social graph in their database. They might have a table for people and another table for friendships. The friendships table has at least two columns, each being foreign keys to the table of people.
Since friendship is symmetric (on Facebook) they might ensure that the ID for the first foreign key is always less than the ID for the second foreign key. Twitter has a directed graph for its social network, so it wouldn’t use a canonical representation like that.
Als je dat spoor volgt blijkt er van alles te bestaan, bijv. Graph Engine (GE) van Microsoft:
Before we can ingest data to the system, we need to first describe the schema of the data to the system so that the system can parse the data. There are many ways to model a data set, from easy to hard. Let us illustrate this using an example:
Leonhard Euler Born April 15, 1707 Leonhard Euler Age 76 Leonhard Euler Education University of Basel Leonhard Euler Book Elements of Algebra Leonhard Euler Son Johann Euler Johann Euler Born Nov 27, 1734 Johann Euler Daughter Charlotte Euler
Zelf niet gekeken maar ze beloven dat je vervolgens snel en efficiënt relaties kan afvragen.
Meer in jouw straatje, segmenten? Demo application:
Single Source Shortest Paths - Source Code on GitHub
A sample output of executing SSSP.exe -q 123:
Current vertex is 123, the distance to the source vertex is 3. Current vertex is 1001, the distance to the source vertex is 2. Current vertex is 2432, the distance to the source vertex is 1. Current vertex is 1, the distance to the source vertex is 0.
En:
We briefly introduce the usage of Graph Engine Visual Studio Extension in this chapter.
We usually start with creating a Graph Engine Data Modeling Project. In the Visual Studio New Project dialog, select Graph Engine Data Modeling Project project template, make sure .NET Framework 4.5 is chosen, and provide a project name.
Dus g++ in bovenstaande plaatje kan je vervangen door “Visual Studio 2015”.
