7.3 Graph Algorithm Functions Supported by DBMS_OGA

This section describes the graph algorithm functions supported by the DBMS_OGA package.

• BELLMAN-FORD
  The BELLMAN-FORD algorithm finds the length of the shortest weighted directed path from a given start vertex to all other vertices in the graph.
• PAGERANK
  The PAGERANK algorithm computes, for every vertex in the graph, a measure of how important this vertex is in the graph.
• PERSONALIZED_PAGERANK
  In the PERSONALIZED_PAGERANK algorithm, the PageRank computation is personalized for a single vertex.
• PERSONALIZED_PAGERANK_SET
  In the PERSONALIZED_PAGERANK_SET algorithm, the PageRank computation is personalized for a set of vertices.
• WCC
  The WCC (Weakly Connected Components) algorithm finds the connected components in a graph.

7.3.1 BELLMAN-FORD

The BELLMAN-FORD algorithm finds the length of the shortest weighted directed path from a given start vertex to all other vertices in the graph.

For example, in the following figure, the BELLMAN-FORD algorithm computes the length of the shortest path from the start vertex (in yellow) to all vertices in the graph. This diagram shows in red the edges followed to get the shortest path.

Figure 7-1 Bellman-Ford Algorithm

Description of "Figure 7-1 Bellman-Ford Algorithm"

The shortest path is defined as the one with the shortest length. The length of a path is defined as the sum of the length of each edge traversed in the path. The length of each edge in the graph is represented as a property. The property to use as edge length is passed as an input property to the BELLMAN-FORD algorithm.

See BELLMAN-FORD in Oracle AI Database PL/SQL Packages and Types Reference for more information on the function signature and usage notes.

Example 7-1 Running BELLMAN-FORD on a SQL Property Graph

The following example query runs the DBMS_OGA.BELLMAN_FORD algorithm on bank_graph (see Using Sample Graph Data for instructions on setting up bank_graph) and returns the computed shortest distance from the BANK_ACCOUNTS vertex with ID = 101 to all other BANK_ACCOUNTS vertices.

SELECT *
FROM GRAPH_TABLE(
  DBMS_OGA.BELLMAN_FORD(
    bank_graph,
    JSON(
      '{
         "GRAPH_OWNER" : "GRAPHUSER",
         "GRAPH_NAME"  : "BANK_GRAPH",
         "ELEM_TABLE"  : "BANK_ACCOUNTS",
         "KEY_VALUE"   : {"ID" : 101}
       }'
    ),
    PROPERTY(EDGE INPUT amount DEFAULT ON NULL 0),
    PROPERTY(VERTEX OUTPUT cost)
  )
  MATCH (a IS accounts)
  COLUMNS (a.id, a.cost)
) ORDER BY cost ASC
  FETCH FIRST 5 ROWS ONLY;

As seen in the preceding code, the query uses each edge's amount property as the edge weight for the Bellman–Ford algorithm. The function writes the computed distance from the source to each reachable vertex into a property named cost. The example returns the first five rows of the query output:

"ID"     "COST"
 101	  0
 418	  1751
 207	  3065
 261	  3888
 794	  5046

7.3.2 PAGERANK

The PAGERANK algorithm computes, for every vertex in the graph, a measure of how important this vertex is in the graph.

The measure of importance is based on the number of incoming neighbors for the vertex, as well as how important are these neighbors.

See PAGERANK in Oracle AI Database PL/SQL Packages and Types Reference for more information on the function signature and usage notes.

Example 7-2 Running PAGERANK on a SQL Property Graph

The following example runs the DBMS_OGA.PAGERANK algorithm on bank_graph (see Using Sample Graph Data for instructions on setting up bank_graph) and projects the id values of BANK_ACCOUNTS vertices and their corresponding rank values.

SELECT id, rank
FROM GRAPH_TABLE(
  DBMS_OGA.pagerank(
    bank_graph,
    PROPERTY(VERTEX OUTPUT rank),
    10, 1.0, 0.85d, FALSE
  )
  MATCH (a IS accounts)
  COLUMNS (a.id, a.rank)
)
ORDER BY rank DESC
FETCH FIRST 5 ROWS ONLY;

The function writes the computed PageRank score into a property named rank. The example returns the first five rows of the query output:

"ID"       "RANK"
 387	    0.006779999999999995
 934	    0.006779999999999995
 135	    0.006269999999999996
 534	    0.005589999999999997
 380	    0.005419999999999998

7.3.3 PERSONALIZED_PAGERANK

In the PERSONALIZED_PAGERANK algorithm, the PageRank computation is personalized for a single vertex.

This is a variant of the PAGERANK algorithm. This variant gives more weight to a specific vertex in the graph. See PERSONALIZED_PAGERANK in Oracle AI Database PL/SQL Packages and Types Reference for more information on the function signature and usage notes.

Example 7-3 Running PERSONALIZED_PAGERANK on a SQL Property Graph

The following example computes the personalized PageRank score on bank_graph (see Using Sample Graph Data for instructions on setting up bank_graph), giving importance to the input BANK_ACCOUNTS vertex with ID = 200. It then projects the id and rank values.

SELECT *
FROM GRAPH_TABLE (
  DBMS_OGA.PERSONALIZED_PAGERANK(
    bank_graph,
    PROPERTY(VERTEX OUTPUT rank),
    JSON('{
      "GRAPH_OWNER": "GRAPHUSER",
      "GRAPH_NAME": "BANK_GRAPH",
      "ELEM_TABLE": "BANK_ACCOUNTS",
      "KEY_VALUE": { "ID": 200 }
    }'),
    50, 0.5, 0.85d, FALSE
  )
  MATCH (a IS accounts)
  COLUMNS (a.id, a.rank)
) ORDER BY rank DESC
  FETCH FIRST 5 ROWS ONLY;

The function writes the computed PageRank score into a property named rank. The example returns the first five rows of the query output:

"ID"   "RANK"
 200	0.15056794280000008
 872	0.0318331171
 439	0.0290869813
 264	0.0274480045
 851	0.0267444629

7.3.4 PERSONALIZED_PAGERANK_SET

In the PERSONALIZED_PAGERANK_SET algorithm, the PageRank computation is personalized for a set of vertices.

This is a variant of the PAGERANK algorithm function. This variant gives more weight to specific vertices in the graph. See PERSONALIZED_PAGERANK_SET in Oracle AI Database PL/SQL Packages and Types Reference for more information on the function signature and usage notes.

Example 7-4 Running PERSONALIZED_PAGERANK_SET on a SQL Property Graph

The example is executed in two steps as shown:

1. Construct the set of vertices targeting BANK_ACCOUNTS with ID values 100, 200, and 300 on bank_graph (see Using Sample Graph Data for instructions on setting up bank_graph).

   SELECT JSON_ARRAYAGG (p_json)
   FROM GRAPH_TABLE(
   bank_graph
   MATCH (a IS Accounts)
   WHERE a.id IN (100, 200, 300)
   COLUMNS(VERTEX_ID(a) AS p_json)
   );

   The query produces the following output:

   [{"GRAPH_OWNER":"GRAPHUSER","GRAPH_NAME":"BANK_GRAPH","ELEM_TABLE":"BANK_ACCOUNTS","KEY_VALUE":{"ID":100}},
    {"GRAPH_OWNER":"GRAPHUSER","GRAPH_NAME":"BANK_GRAPH","ELEM_TABLE":"BANK_ACCOUNTS","KEY_VALUE":{"ID":200}},
    {"GRAPH_OWNER":"GRAPHUSER","GRAPH_NAME":"BANK_GRAPH","ELEM_TABLE":"BANK_ACCOUNTS","KEY_VALUE":{"ID":300}}
   ]

2. Run the DBMS_OGA.PERSONALIZED_PAGERANK_SET algorithm to compute the personalized PageRank scores biased towards the vertex set obtained in the previous step.

   SELECT *
   FROM GRAPH_TABLE (
     DBMS_OGA.personalized_pagerank_set(
       bank_graph,
       PROPERTY(VERTEX OUTPUT rank),
       JSON('[{"GRAPH_OWNER":"GRAPHUSER","GRAPH_NAME":"BANK_GRAPH","ELEM_TABLE":"BANK_ACCOUNTS","KEY_VALUE":{"ID":100}},
    {"GRAPH_OWNER":"GRAPHUSER","GRAPH_NAME":"BANK_GRAPH","ELEM_TABLE":"BANK_ACCOUNTS","KEY_VALUE":{"ID":200}},
    {"GRAPH_OWNER":"GRAPHUSER","GRAPH_NAME":"BANK_GRAPH","ELEM_TABLE":"BANK_ACCOUNTS","KEY_VALUE":{"ID":300}}
   ]'),
       50, 0.5, 0.85d, FALSE
     )
     MATCH (a IS Accounts)
     COLUMNS (a.id, a.rank)
   ) ORDER BY rank DESC 
     FETCH FIRST 5 ROWS ONLY;

   The function writes the computed PageRank score into a property named rank and the query returns the first five rows of the output:

   "ID"  "RANK"
    200   0.05056237473333334
    100   0.05
    300   0.05
    559   0.013113229933333331
    439   0.010976970833333334

7.3.5 WCC

The WCC (Weakly Connected Components) algorithm finds the connected components in a graph.

A WCC is a maximal subset of vertices of the graph, such that, for any two vertices in the subset, a path exists between them when edge directions are ignored.

The following shows the graphical representation of WCC:

Figure 7-2 Weakly Connected Components

Description of "Figure 7-2 Weakly Connected Components"

If two vertices are assigned the same component ID, then they belong to the same weakly connected component. This means that there exists a path between them in the underlying undirected graph (that is, when edge directions are ignored). If the graph contains more than one component ID value, it means there are non-connected components in the graph (sets of vertices that are not connected to each other).

See WCC in Oracle AI Database PL/SQL Packages and Types Reference for more information on the function signature and usage notes.

Example 7-5 Running WCC on a SQL Property Graph

The following example uses the DBMS_OGA.WCC function to find the connected components in bank_graph (see Using Sample Graph Data for instructions on setting up bank_graph). It then projects the id and component ID for every BANK_ACCOUNTS vertex in the graph.

SELECT id, comp_id
FROM GRAPH_TABLE (
  DBMS_OGA.wcc (
    bank_graph,
    PROPERTY(VERTEX OUTPUT comp_id))
  MATCH (a IS Accounts)
  COLUMNS (a.id, a.comp_id)
) FETCH FIRST 5 ROWS ONLY;

The example returns the first five rows of the query output. All accounts have COMP_ID = 1, which indicates they are all connected.

"ID"   "COMP_ID"
 597	  1
 603	  1
 610	  1
 618	  1
 625	  1