In this blog we will learn further about built-in Graph functionalities supported in SAP HANA, graph options.
To review what are graphs and how do we create graphs in SAP HANA kindly refer to
SAP HANA, graph options - part 1
Below are the graph functions supported.
- Neighbourhood Search - This function is used to get neighbouring vertices from the input vertex with a given radius.
- Shortest Path (One-to-all) - This function, also known as Single Source Shortest path, provides shortest path from given vertex to all vertices in the graph. The resulting shortest paths form a tree structure.
- Shortest Path (One-to-One) - This is a variant of the Shortest Path(One-to-all) which provides shortest path between a start vertex and a target vertex.
- Strongly Connected Components - A directed graph is strongly connected if every vertex is reachable from every other vertex.
Now, we will look at scripts for each one of the above stated functionalities.
First we define Graph.
In the below code snippet we define reference vertex, edge tables and graph workspace object.
DROP SCHEMA "GRAPHOPTION" CASCADE;
CREATE SCHEMA "GRAPHOPTION";
CREATE COLUMN TABLE "GRAPHOPTION"."NODES" (
"ID" BIGINT PRIMARY KEY
);
CREATE COLUMN TABLE "GRAPHOPTION"."EDGES" (
"ID" BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
"SOURCE" BIGINT REFERENCES "GRAPHOPTION"."NODES"("ID") ON DELETE CASCADE NOT NULL,
"TARGET" BIGINT REFERENCES "GRAPHOPTION"."NODES"("ID") ON DELETE CASCADE NOT NULL,
"WEIGHT" DOUBLE
);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (1);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (2);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (3);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (4);
INSERT INTO "GRAPHOPTION"."NODES" VALUES (5);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (1, 2, 0.5);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (1, 3, 0.1);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (2, 3, 1.5);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (2, 4, 0.1);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (3, 4, 0.2);
INSERT INTO "GRAPHOPTION"."EDGES"("SOURCE", "TARGET", "WEIGHT") VALUES (5, 4, 0.8);
CREATE GRAPH WORKSPACE "GRAPHOPTION"."GRAPHWS"
EDGE TABLE "GRAPHOPTION"."EDGES"
SOURCE COLUMN "SOURCE"
TARGET COLUMN "TARGET"
KEY COLUMN "ID"
VERTEX TABLE "GRAPHOPTION"."NODES"
KEY COLUMN "ID";
Now, we will look at sample implementations of custom graph functions provided in SAP HANA, graph options mentioned above.
CREATE TYPE "GRAPHOPTION"."TT_NODES_NEI" AS TABLE ("ID" BIGINT); -- Table type for getting neighbour output for target vertices ids from input source vertex.
CREATE TYPE "GRAPHOPTION"."TT_EDGES_NEI" AS TABLE ("ID" BIGINT, "SOURCE" BIGINT, "TARGET" BIGINT);- Table type for getting neighbour output for edges that form the neighburhood.
CREATE OR REPLACE PROCEDURE "GRAPHOPTION"."GS_NEIGHBORS"(
IN i_startNode BIGINT, -- the ID of the start node
IN i_min BIGINT, -- the minimum hop distance
IN i_max BIGINT, -- the maximum hop distance
OUT o_nodes "GRAPHOPTION"."TT_NODES_NEI",
OUT o_nodesCount BIGINT,
OUT o_edges "GRAPHOPTION"."TT_EDGES_NEI"
)
LANGUAGE GRAPH READS SQL DATA AS
BEGIN
-- create an instance of the graph, refering to the graph workspace object
GRAPH g = Graph("GRAPHOPTION", "GRAPHWS");
-- create an instance of the start node
VERTEX v_start = Vertex(:g, :i_startNode);
-- create a multiset of all neighbor nodes of the start node
MULTISET<Vertex> m_neighbors = Neighbors(:g, :v_start, :i_min, :i_max);
-- project the result from the multiset
o_nodes = SELECT :v."ID" FOREACH v IN :m_neighbors;
o_nodesCount = COUNT(:m_neighbors);
-- create a vertex induced subgraph to get all edges between the nodes in the neighbors multiset
GRAPH g_sub = SubGraph(:g, :m_neighbors);
o_edges = SELECT :e."ID", :e."SOURCE", :e."TARGET" FOREACH e IN Edges(:g_sub);
END;
CALL "GRAPHOPTION"."GS_NEIGHBORS"(i_startNode => 1, i_min => 0, i_max => 1000, o_nodes => ?, o_nodesCount => ?, o_edges => ?);
- Shortest Path One-to-All
/*************************************/
-- Shortest Paths One to All procedure
CREATE TYPE "GRAPHOPTION"."TT_NODES_SPOA" AS TABLE ("ID" BIGINT, "CALCULATED_COST" DOUBLE);
CREATE TYPE "GRAPHOPTION"."TT_EDGES_SPOA" AS TABLE ("ID" BIGINT, "SOURCE" BIGINT, "TARGET" BIGINT, "WEIGHT" DOUBLE);
CREATE OR REPLACE PROCEDURE "GRAPHOPTION"."GS_SPOA"(
IN i_startNode BIGINT, -- the ID of the start node
OUT o_nodes "GRAPHOPTION"."TT_NODES_SPOA",
OUT o_edges "GRAPHOPTION"."TT_EDGES_SPOA"
)
LANGUAGE GRAPH READS SQL DATA AS
BEGIN
-- create an instance of the graph, refering to the graph workspace object
GRAPH g = Graph("GRAPHOPTION", "GRAPHWS");
-- create an instance of the start node
VERTEX v_start = Vertex(:g, :i_startNode);
-- running shortest paths one to all, which returns a subgraph. The WEIGHT based path length to a node is stored in the attribute CALCULATED_COST
GRAPH g_spoa = SHORTEST_PATHS_ONE_TO_ALL(:g, :v_start, "CALCULATED_COST", (Edge e) => DOUBLE{ return :e."WEIGHT"; });
o_nodes = SELECT :v."ID", :v."CALCULATED_COST" FOREACH v IN Vertices(:g_spoa);
o_edges = SELECT :e."ID", :e."SOURCE", :e."TARGET", :e."WEIGHT" FOREACH e IN Edges(:g_spoa);
END;
CALL "GRAPHOPTION"."GS_SPOA"(i_startNode => 1, o_nodes => ?, o_edges => ?);
- Shortest path One-to-One
/*************************************/
-- Shortest Path One to One procedure
CREATE TYPE "GRAPHOPTION"."TT_NODES_SPOO" AS TABLE ("ID" BIGINT);
CREATE TYPE "GRAPHOPTION"."TT_EDGES_SPOO" AS TABLE ("ID" BIGINT, "SOURCE" BIGINT, "TARGET" BIGINT);
CREATE OR REPLACE PROCEDURE "GRAPHOPTION"."GS_SPOO"(
IN i_startNode BIGINT, -- the ID of the start node
IN i_endNode BIGINT, -- the ID of the end node
OUT o_path_length BIGINT, -- the hop distance between start and end
OUT o_path_weight DOUBLE, -- the path weight/cost based on the WEIGHT attribute
OUT o_nodes "GRAPHOPTION"."TT_NODES_SPOO",
OUT o_edges "GRAPHOPTION"."TT_EDGES_SPOO"
)
LANGUAGE GRAPH READS SQL DATA AS
BEGIN
-- create an instance of the graph, refering to the graph workspace object
GRAPH g = Graph("GRAPHOPTION", "GRAPHWS");
-- create an instance of the start/end node
VERTEX v_start = Vertex(:g, :i_startNode);
VERTEX v_end = Vertex(:g, :i_endNode);
-- running shortest path using the WEIGHT column as cost
WeightedPath<DOUBLE> p = Shortest_Path(:g, :v_start, :v_end, (Edge e) => DOUBLE{ return :e."WEIGHT"; });
-- project the results from the path
o_path_length = LENGTH(:p);
o_path_weight = WEIGHT(:p);
o_nodes = SELECT :v."ID" FOREACH v IN Vertices(:p);
o_edges = SELECT :e."ID", :e."SOURCE", :e."TARGET" FOREACH e IN Edges(:p);
END;
CALL "GRAPHOPTION"."GS_SPOO"(i_startNode => 1, i_endNode => 4, o_path_length => ?, o_path_weight => ?, o_nodes => ?, o_edges => ?);
And that's the out-of-the-box algorithms for SAP HANA, graph options.
In the next article we will check out some custom algorithms with Graphs.
