<p>The paper <a href="https://arxiv.org/pdf/1802.09478.pdf" rel="nofollow noreferrer">In-database connected component analysis</a> describes a SQL-based algorithm (using quite a few tables to store the intermediate results. The paper evaluates the algorithm in the Apache HAWQ DBMS but it seems to be portable to PostgreSQL.</p>
A number of connected components of a graph in SQL
<p>I have a graph in my <strong>PostgreSQL</strong> database, for the sake of example let's define it so:</p>

<pre><code>CREATE TABLE nodes (node_id INTEGER);
CREATE TABLE roads (road_id INTEGER, nodes INTEGER[]);
INSERT INTO nodes VALUES (1), (2), (3), (4), (5);
INSERT INTO roads VALUES (1, {1, 2}), (2, {3, 4}));
</code></pre>

<p>I want to create SQL query that returns the number of <a href="https://en.wikipedia.org/wiki/Connected_component_(graph_theory)" rel="nofollow">connected components</a> of the graph, in this example the number is <strong>3</strong>, because nodes 1/2 are connected, 3/4 as well, while 5 is not connected to anything.</p>

<p>I tried searching for <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="nofollow">find&amp;union</a> implementations in SQL but to no avail, I then turned to <a href="http://www.postgresql.org/docs/8.4/static/queries-with.html" rel="nofollow">CTEs</a> but I can't do it on my own, I was thinking of something like this:</p>

<pre><code>WITH RECURSIVE cc(iterator_id, node_id, rank, iterator) AS
(
        SELECT row_number() OVER(), n.node_id, row_number() OVER (), 1 FROM nodes AS n
    UNION ALL
        # Something here that does the magic
)
SELECT
    COUNT(DISTINCT rank) AS no_of_cc
FROM
    cc,
    (SELECT COUNT(*) FROM nodes) AS last_iterator_id
WHERE iterator = last_iterator_id;
</code></pre>

<p>where in each iteration we update the ranks of rows whose iterator_id &lt;= iterator. We iterate until <code>iterator</code> is equal to the biggest <code>iterator_id</code>
but I can't think of the recursive part.</p>

<p>Can you help me find the number of connected components?</p>