Graph Algorithms (extension)
The functions of the schema GRAPH_ALGO run graph algorithms over a table of edges. Each is a table reference of the FROM clause, a row for each vertex and its value, so its result joins to the table the vertices' keys are of. INTO PROPERTY writes a result to a column of that table instead. The examples here make the tables of a small graph, the people P and who follows whom, F:
CREATE TABLE P (ID INTEGER PRIMARY KEY, NAME VARCHAR(10));
INSERT INTO P VALUES (1, 'ann'), (2, 'bob'), (3, 'cy'), (4, 'dee'), (5, 'eve');
CREATE TABLE F (WHO INTEGER, WHOM INTEGER, COST DOUBLE PRECISION);
INSERT INTO F VALUES (1, 2, 1), (2, 3, 2), (3, 1, 1), (3, 4, 5), (1, 4, 10);
OK
OK
OK
OK
Syntax
GRAPH_ALGO . <algorithm> ( <edges> [ , <argument> ]... )
[ [ AS ] <correlation name> [ ( <derived column list> ) ] ]
<edges> ::= TABLE ( <table name> ) | TABLE ( <query expression> )
| <property graph name>
<argument> ::= <value> | <parameter name> => <value>
The invocation may be written TABLE ( GRAPH_ALGO . ... ) too, as a polymorphic table function's is. The edges are a table argument: the first two columns of each row are an edge's source and destination, the keys of its vertices. A row of a null key is no edge. The keys of every table argument are of types that compare, and the result's vertex columns are of the type of the edges' source.
The edges may be a property graph's name instead, of CREATE PROPERTY GRAPH or a schema's SYS_GRAPH of its node and edge tables. Its vertex tables' rows are then the vertices, and VERTICES is not written. Each edge table's rows are the edges, each joining the vertices whose columns its endpoints reference, so an edge of no such vertex is none, and an undirected edge joins them both ways. COST may name a column that every edge table has alike. A graph is read through its tables, with the statement's privileges on them.
Of such a graph, a vertex is its identity, as ELEMENT_ID gives it: the
text {"table":"ACCOUNT","key":[6]} of its element table's name and its
key's values in order, of VARCHAR(8192). So keys of two vertex tables,
and keys of any number of columns, name vertices apart, and START is an
identity too. Of a SYS_GRAPH, a vertex is its $NODE_ID, the identity
its node table holds.
Arguments follow the edges in the order of the parameters, then by name. Once one is named, the rest are too. An argument not written, or NULL, takes its parameter's default. Without a correlation name a result is named by its algorithm.
The algorithms
| Algorithm | Parameters after EDGES | Columns of the result |
|---|---|---|
| PAGERANK | DAMPING 0.85, ITERATIONS 20, TOLERANCE 1E-6 | VERTEX, RANK |
| WCC | VERTEX, COMPONENT | |
| SCC | VERTEX, COMPONENT | |
| BFS_LEVELS | START | VERTEX, DEPTH |
| SSSP | START, COST | VERTEX, DISTANCE |
| TRIANGLE_COUNT | VERTEX, TRIANGLES | |
| LOCAL_CLUSTERING | VERTEX, COEFFICIENT | |
| BETWEENNESS | SAMPLE, SEED 0 | VERTEX, CENTRALITY |
| LOUVAIN | RESOLUTION 1, LEVELS 10, TOLERANCE 1E-7, SEED 0, COST | VERTEX, COMMUNITY |
| LABEL_PROPAGATION | ITERATIONS 10 | VERTEX, COMMUNITY |
| K_CORE | VERTEX, CORE | |
| JACCARD_SIMILARITY | TOP_K, THRESHOLD 0 | VERTEX1, VERTEX2, SIMILARITY |
Each takes VERTICES last, a table argument whose first column holds keys of vertices to count though no edge has them.
PAGERANK gives each vertex its rank, the ranks summing to 1, the rank of a vertex of no outgoing edge shared by all. It stops after ITERATIONS, or sooner once the ranks move less than TOLERANCE in all. WCC and SCC give each vertex its weakly or strongly connected component, named by the least key in it.
BFS_LEVELS gives each vertex START reaches the least number of edges from it. SSSP gives the least sum of the edges' COST, the name of a column of the edges, or of edges counted as 1 without one. A negative cost is taken, but not a cycle of them START reaches. A vertex not reached has no row, nor does any if START is no vertex.
TRIANGLE_COUNT, LOCAL_CLUSTERING, LOUVAIN, LABEL_PROPAGATION, K_CORE and JACCARD_SIMILARITY read the edges with no direction, each pair of vertices joined once. TRIANGLE_COUNT gives each vertex the triangles it is in, and LOCAL_CLUSTERING the share of pairs of its neighbours that are joined. K_CORE gives each vertex the greatest k of a subgraph it is in whose every vertex has k neighbours in it.
BETWEENNESS gives each vertex the share it is on of the shortest paths between other vertices. With SAMPLE it starts from that many vertices, drawn by SEED, and scales the sums up to estimate it.
LOUVAIN finds communities that raise the modularity at RESOLUTION, over LEVELS levels of communities merged, with COST as the edges' weights. LABEL_PROPAGATION finds them by each vertex taking the label most of its neighbours have. Each names a community by the least key in it, and each is the same on every run of its SEED.
JACCARD_SIMILARITY gives pairs of vertices that share neighbours and the share of their neighbours both have, those of at least THRESHOLD. With TOP_K it gives each vertex's TOP_K pairs, of both orders, and without it each pair once, its lesser key first.
Examples
SELECT P.NAME, R.COMPONENT
FROM P JOIN GRAPH_ALGO.SCC(TABLE (F)) AS R ON P.ID = R.VERTEX
ORDER BY P.NAME;
NAME | COMPONENT
------------+--------------
ann | 1
bob | 1
cy | 1
dee | 4
(4 rows)
SELECT * FROM GRAPH_ALGO.SSSP(TABLE (F), 1, COST => 'COST') AS D ORDER BY VERTEX;
VERTEX | DISTANCE
--------------+--------------------------
1 | 0E0
2 | 1E0
3 | 3E0
4 | 8E0
(4 rows)
SELECT * FROM GRAPH_ALGO.WCC(TABLE (F), VERTICES => TABLE (P)) AS W ORDER BY VERTEX;
VERTEX | COMPONENT
--------------+--------------
1 | 1
2 | 1
3 | 1
4 | 1
5 | 5
(5 rows)
SELECT VERTEX, CAST(RANK * 1000 AS INTEGER) AS PERMILLE
FROM GRAPH_ALGO.PAGERANK(TABLE (F), DAMPING => 0.85, ITERATIONS => 50) AS R
ORDER BY VERTEX;
VERTEX | PERMILLE
--------------+--------------
1 | 219
2 | 197
3 | 271
4 | 312
(4 rows)
The edges are any query, so a subgraph is a WHERE:
SELECT * FROM GRAPH_ALGO.TRIANGLE_COUNT(TABLE (SELECT WHO, WHOM FROM F WHERE COST < 10)) AS T
ORDER BY VERTEX;
VERTEX | TRIANGLES
--------------+----------------------
1 | 1
2 | 1
3 | 1
4 | 0
(4 rows)
A property graph's vertices are named by their identities, so a graph of several vertex tables, here accounts and the cities they are in, keeps them apart:
CREATE TABLE CITY (CID INTEGER PRIMARY KEY, CNAME VARCHAR(10));
CREATE TABLE LIVES (WHO INTEGER PRIMARY KEY, CID INTEGER);
INSERT INTO CITY VALUES (1, 'oslo'), (2, 'rome');
INSERT INTO LIVES VALUES (1, 1), (2, 1), (4, 2);
CREATE PROPERTY GRAPH SOCIAL
VERTEX TABLES (P, CITY)
EDGE TABLES (
F KEY (WHO, WHOM) SOURCE KEY (WHO) REFERENCES P (ID) DESTINATION KEY (WHOM) REFERENCES P (ID),
LIVES SOURCE KEY (WHO) REFERENCES P (ID) DESTINATION KEY (CID) REFERENCES CITY (CID))
OPTIONS (TRUSTED MODE);
SELECT * FROM GRAPH_ALGO.WCC(SOCIAL) AS W ORDER BY VERTEX;
OK
OK
OK
OK
OK
VERTEX | COMPONENT
--------------------------------------------------------------+--------------------------------------------------------------
{"table":"CITY","key":[1]} | {"table":"CITY","key":[1]}
{"table":"CITY","key":[2]} | {"table":"CITY","key":[1]}
{"table":"P","key":[1]} | {"table":"CITY","key":[1]}
{"table":"P","key":[2]} | {"table":"CITY","key":[1]}
{"table":"P","key":[3]} | {"table":"CITY","key":[1]}
{"table":"P","key":[4]} | {"table":"CITY","key":[1]}
{"table":"P","key":[5]} | {"table":"P","key":[5]}
(7 rows)
A schema's node and edge tables are its graph SYS_GRAPH, each vertex
its $NODE_ID, so a result joins to the node tables by it:
CREATE TABLE TOWN (NAME VARCHAR(10)) AS NODE;
CREATE TABLE ROAD (KM DOUBLE PRECISION) AS EDGE;
INSERT INTO TOWN VALUES ('alba'), ('bra'), ('cuneo');
INSERT INTO ROAD ($FROM_ID, $TO_ID, KM)
SELECT A.$NODE_ID, B.$NODE_ID, 50 FROM TOWN AS A, TOWN AS B WHERE A.NAME < B.NAME;
SELECT TOWN.NAME, CAST(R.RANK * 1000 AS INTEGER) AS PERMILLE
FROM GRAPH_ALGO.PAGERANK(SYS_GRAPH) AS R JOIN TOWN ON TOWN.$NODE_ID = R.VERTEX
ORDER BY TOWN.NAME;
OK
OK
OK
OK
NAME | PERMILLE
------------+--------------
alba | 198
bra | 282
cuneo | 521
(3 rows)
INTO PROPERTY
GRAPH_ALGO . <algorithm> ( <edges> [ , <argument> ]... )
INTO PROPERTY <column name> [ OF <table name> [ ( <key column name> ) ] ]
INTO PROPERTY writes each vertex's value to the column of the row of the table whose key column holds its key. The key column is the table's primary key of one column unless named. If the table has no column of the name, it is added first, of DOUBLE PRECISION, BIGINT or the key's type, as the result's value column is. A row of no vertex keeps the value it had, null in a column just added. All of it is in the statement's transaction, so ROLLBACK undoes it. JACCARD_SIMILARITY, whose result is of pairs, writes no property. Of a table of edges, OF names the table.
Of a property graph named in place of the edges, the property is
written to its vertex tables, each row's the value of the vertex its
identity names, matched by the table's key. OF names one vertex table to
write alone, and no key column is written. Each table without the
column has it added, of DOUBLE PRECISION, BIGINT, or the type of an
identity: VARCHAR(8192), or of a SYS_GRAPH a $NODE_ID's. Each vertex
table is written by a MERGE of its own, so the statement needs UPDATE
of the column on each. The algorithm runs once, and each MERGE reads
the rows that run gave.
GRAPH_ALGO.BFS_LEVELS(TABLE (F), 1) INTO PROPERTY HOPS OF P;
SELECT ID, NAME, HOPS FROM P ORDER BY ID;
OK
ID | NAME | HOPS
--------------+------------+----------------------
1 | ann | 0
2 | bob | 1
3 | cy | 2
4 | dee | 1
5 | eve | NULL
(5 rows)
GRAPH_ALGO.PAGERANK(SOCIAL) INTO PROPERTY PR;
SELECT CNAME, CAST(PR * 1000 AS INTEGER) AS PERMILLE FROM CITY ORDER BY CNAME;
OK
CNAME | PERMILLE
------------+--------------
oslo | 163
rome | 220
(2 rows)
Runs
A run reads its edges in the statement's snapshot, through the privileges the statement has on them. It runs on as many threads as EXECUTOR.GRAPH_THREADS says, 1 unless set, and gives the same rows on any number. Its arrays are held within MEMORY.WORK_BYTES, and one that needs more is refused with SQLCODE -918. Cancelled, or past the statement's timeout, it stops with SQLCODE -920.
INFORMATION_SCHEMA.GRAPH_ALGO_RUNS shows the latest 1000 runs, each with its number, algorithm, arguments, user, start and time taken, its graph's vertices and edges, its rows, its threads, and DONE or FAILED with the message. The database's owner sees every run, another user their own.
SELECT RUN_ID, ALGORITHM, ARGUMENTS, VERTICES, EDGES, ROWS_RETURNED, STATUS
FROM INFORMATION_SCHEMA.GRAPH_ALGO_RUNS ORDER BY RUN_ID;
RUN_ID | ALGORITHM | ARGUMENTS | VERTICES | EDGES | ROWS_RETURNED | STATUS
----------------------+--------------------------------------------------------------+--------------------------------------------------------------+----------------------+----------------------+----------------------+--------
1 | SCC | | 4 | 5 | 4 | DONE
2 | SSSP | START => 1, COST => 'COST' | 4 | 5 | 4 | DONE
3 | WCC | | 5 | 5 | 5 | DONE
4 | PAGERANK | DAMPING => 8.5E-1, ITERATIONS => 50 | 4 | 5 | 4 | DONE
5 | TRIANGLE_COUNT | | 4 | 4 | 4 | DONE
6 | WCC | | 7 | 8 | 7 | DONE
7 | PAGERANK | | 3 | 3 | 3 | DONE
8 | BFS_LEVELS | START => 1 | 4 | 5 | 4 | DONE
9 | PAGERANK | | 7 | 8 | 7 | DONE
(9 rows)
Errors
| SQLSTATE | SQLCODE | Cause |
|---|---|---|
| 2A000 | -103 | GRAPH_ALGO has no algorithm of the name, an argument names no parameter, two are of one, one without a name follows a named one, START is missing, the edges are a value that names no property graph, VERTICES is written with a graph, or a key is not of a type that compares with the source's |
| 22000 | -301 | An argument is out of its range, as a DAMPING past 1 |
| 22W34 | -301 | GRF-0034, of a COST that names no column, is null or not a number, is negative where the algorithm takes no negative cost, or makes a negative cycle SSSP's START reaches |
| TB918 | -918 | The run needs more memory than MEMORY.WORK_BYTES |
| TB920 | -920 | The statement was cancelled or ran past its timeout |
Standard
The functions of GRAPH_ALGO and INTO PROPERTY are the graph
implementation standard's §18, its run log GRAPH_ALGO_RUNS of §20, and
GRF-0034 of §22. Named arguments, name => value, are those of
ISO/IEC 9075-2:2023 §10.4, here mixed with positional ones as the graph
standard writes them.