Press "Enter" to skip to content

Category: Graph

Shortest Path Calculations with Dijkstra’s Algorithm

Holger von Jouanne-Diedrich takes us through Dijkstra’s algorithm for shortest path calculations:

This post is partly based on this essay Python Patterns – Implementing Graphs, the example is from the German book “Das Geheimnis des kürzesten Weges” (“The secret of the shortest path”) by my colleague Professor Gritzmann and Dr. Brandenberg. For finding the most elegant way to convert data frames into igraph-objects I got help (once again!) from the wonderful R community over at StackOverflow.

Dijkstra’s algorithm is a recursive algorithm. If you are not familiar with recursion you might want to read my post To understand Recursion you have to understand Recursion… first.

Click through for an implementation in R.

Comments closed

Modifying Graph Edges with T-SQL

Louis Davidson shows how you can update edges in SQL Server’s graph functionality:

As I have been writing a section on SQL Server graph tables in my Database Design book, (and prepping for a hopeful book on the subject next year), I find that there are a few really annoying things about dealing with graph tables. This blog serves to clear up the first, most annoying of them. Inserting, updating, and deleting edges.

Because the key values in the graph database structures are hidden, you can’t just insert a new edge without translating your table’s key values to the graph database internal values. Edges aren’t even available for an update of the from or to references. As I wrote stored procedures to do this, I realized “why not use a view and trigger to make this happen”. So I did. The result is that I can insert, delete, and even update graph tables using normal SQL syntax. What makes this better than the stored procedure is that I can insert multiple rows simultaneously.

Read on to see what this entails.

Comments closed

Connecting to Cosmos DB from the Gremlin Console

Hasan Savran shows how to connect to Cosmos DB’s Gremlin API via the Gremlin Console:

Graph Databases have been popular lately. You can use Azure Cosmos DB as your  Graph database source by selecting Gremlin API. Gremlin programing language is developed by Apache TinkerPop of the Apache Software Foundation. I will show you how to connect to Cosmos DB Gremlin API from TinkerPop Gremlin console.

     You can download the latest version of Gremlin console from here. The latest version was 3.4.6 when I wrote this post. I was able to connect to the Cosmos DB by using the versions 3.4.3 and 3.4.6.  You can run the console from Linux or Windows, I will focus on the Windows version here but Linux version should work the same way. You must have Java SDK 8 to run this console. Latest version of Java SDK does not work with this console.

There are a couple of configuration steps, but nothing crazy.

Comments closed

Family History with SQL Graph

Mala Mahadevan takes us through family histories in a graph database:

I have been working a lot of SQL Graph related queries and applications of the graph data concept to the extent possible within SQL Server’s graph capabilities. Genealogy, or querying family trees is an important graph data application. A lot of us may not have work related applications that are genealogy related, necessarily. But conceptually, this can apply to many similar tree/hierarchy type structures. I was looking into some data to play with in this regard. Sometime ago – we were discussing novels by famed novelist James Michener. My friend Buck Woody made a tweet-remark that it would need a graph database to keep track of the characters and relationships in some of Michener’s novels. I am a big fan of Michener’s novels, and the most recent one I have read is ‘Hawaii’. It is based on history and evolution of the Hawaiian islands, and has a rather complex network of characters, with many ethnicities and several interwoven relationships. I decided to use the characters in Hawaii as my test data to understand how to query geneological data, stored in graph database format.

Read on to see Mala’s table and a procedure to retrieve this data.

Comments closed

Shortest Path in Graphs

Mala Mahadevan looks at the shortest path function in SQL Server Graph:

‘Shortest path’ is the term accorded to the shortest distance between any two points, referred to as nodes in graph databases. The algorithm that helps you find the shortest distance between node A and node B is called the Shortest Path Algorithm.

Let us go back to the movie database. We have two people, say Amrish Puri and Harrison Ford. Amrish wants to meet Harrison Ford. He has not acted with Ford, he may have a few connections in common – or people who know him. Or people who know him who know him. This is one way to get an introduction. Or, let us say you are interviewing for a job. You want to see if someone in your network works at that place – so that you can get an idea of what the job or the company is like. So you go on linkedin – do a search for the company, look under ‘people’, and it tells you if anyone in your network is there, or someone is 2 levels away, or 3. Those numbers are what we get from the shortest path feature.

Read on for a few examples of shortest path in action.

Comments closed

Building Graph Queries with SQL Server Graph

Mala Mahadevan takes us through a few examples of queries in SQL Server’s built-in graph engine:

The main goal behind a graph design is to help you answer queries – so what are the questions you’d ask of a movie database, if you had one? Mine would typically be like below.

1 Who are the actors in this movie?
2 Who is this movie directed by?
3 Who is the most prolific actor, according this dataset?
4 How many actors are also directors?
..and so on.

Read on to see how you can write these queries.

Comments closed

Creating Graph Tables in SQL Server

Mala Mahadevan continues a series on graph tables in SQL Server:

I have highlighted in red what SQL Server adds to the table – the two system columns – graph id, which is bigint, and node id, which is nvarchar and stores json, and the unique index to help with queries.

We can also see from constraint type that this table is similar to other relational tables – it can be enabled for replication and can have related delete or update actions defined on it if need be.

This post gives a bit more insight into how graph tables work in SQL Server under the covers.

Comments closed

Combining Neo4j with Kafka

David Allen shows how you can use Neo4j to visualize graphic data living in Kafka:

We’re enabling the plugin to work as both a source and a sink. In the NEO4J_streams_sink_topic_cypher_friends item, we’re writing a Cypher query. In this query, we’re MERGE-ing two Person nodes. The plugin gives us a variable named event, which we can use to pull out the properties we need. When we MERGE nodes, it creates them only if they do not already exist. Finally, it creates a relationship between the two nodes (p1) and (p2).

This sink configuration is how we’ll turn a stream of records from Kafka into an ever-growing and changing graph. The rest of the configuration handles our connection to a Confluent Cloud instance, where all of our event streaming will be managed for us. If you’re trying this out for yourself, make sure to replace KAFKA_BOOTSTRAP_SERVERSAPI_SECRET, and API_KEY with the values that Confluent Cloud gives you when you generate an API access key.

Click through for the example.

Comments closed

The Structure of Graph Data

Mala Mahadevan begins a series on graph data in SQL Server:

The simplest way to understand a graph data model is that there are just two entities – Nodes, which is what we call Entities in the relational world, and Edges, which are what we call relationships. They are typically represented like below, with the circles standing for nodes, and the arrows for relationships. The emphasis, as we can see is on the bold arrows – because relationships are what graph data is about, with less emphasis on entities/nodes.

Read the whole thing.

Comments closed